Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp @ 2546

Revision 2546, 92.6 KB checked in by mattausch, 17 years ago (diff)
added new sampling strategies

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "VspTree.h"
8	#include "Mesh.h"
9	#include "common.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellsManager.h"
17	#include "Beam.h"
18	#include "KdTree.h"
19	#include "IntersectableWrapper.h"
20	#include "HierarchyManager.h"
21	#include "BvHierarchy.h"
22	#include "OspTree.h"
23
24
25
26	namespace GtpVisibilityPreprocessor {
27
28
29	#define VISUALIZE_SPLIT 0
30	#define USE_FIXEDPOINT_T 0
31	#define HACK_PERFORMANCE 1
32
33
34	#define TYPE_INTERIOR -2
35	#define TYPE_LEAF -3
36
37
38	/////////////
39	//-- static members
40
41	VspTree *VspTree::VspSubdivisionCandidate::sVspTree = NULL;
42	int VspNode::sMailId = 1;
43
44	// variable for debugging volume contribution for heuristics
45	static float debugVol;
46
47
48
49	inline static bool ilt(Intersectable obj1, Intersectable obj2)
50	{
51	return obj1->mId < obj2->mId;
52	}
53
54
55	// pvs penalty can be different from pvs size
56	inline static float EvalPvsPenalty(const float pvs,
57	const float lower,
58	const float upper)
59	{
60	// clamp to minmax values
61	if (pvs < lower)
62	{
63	return (float)lower;
64	}
65	else if (pvs > upper)
66	{
67	return (float)upper;
68	}
69	return (float)pvs;
70	}
71
72
73	void VspTreeStatistics::Print(ostream &app) const
74	{
75	app << "=========== VspTree statistics ===============\n";
76
77	app << setprecision(4);
78
79	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
80
81	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
82
83	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
84
85	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
86
87	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
88
89	for (int i = 0; i < 3; ++ i)
90	app << splits[i] << " ";
91
92	app << endl;
93
94	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
95	<< maxDepthNodes * 100 / (double)Leaves() << endl;
96
97	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
98	<< minPvsNodes * 100 / (double)Leaves() << endl;
99
100	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
101	<< minRaysNodes * 100 / (double)Leaves() << endl;
102
103	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
104	<< maxCostNodes * 100 / (double)Leaves() << endl;
105
106	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
107	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
108
109	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
110	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
111
112	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
113
114	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
115
116	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
117
118	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
119
120	app << "#AVGRAYS (number of rays / leaf)\n" << AvgRays() << endl;
121
122	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
123
124	app << "========== END OF VspTree statistics ==========\n";
125	}
126
127
128
129	VspTree::VspTraversalData::VspTraversalData():
130	mNode(NULL),
131	mDepth(0),
132	mRays(NULL),
133	mPvs(0),
134	mProbability(0.0),
135	mMaxCostMisses(0),
136	mPriority(0),
137	mCorrectedPvs(0)
138	{}
139
140
141	VspTree::VspTraversalData::VspTraversalData(VspLeaf *node,
142	const int depth,
143	RayInfoContainer *rays,
144	const float pvs,
145	const float p,
146	const AxisAlignedBox3 &box):
147	mNode(node),
148	mDepth(depth),
149	mRays(rays),
150	mProbability(p),
151	mBoundingBox(box),
152	mMaxCostMisses(0),
153	mPriority(0),
154	mCorrectedPvs(0),
155	mPvs(pvs),
156	mRenderCost(0),
157	mCorrectedRenderCost(0)
158	{}
159
160
161	float VspTree::VspTraversalData::GetAvgRayContribution() const
162	{
163	return (float)mPvs / ((float)mRays->size() + Limits::Small);
164	}
165
166
167	float VspTree::VspTraversalData::GetAvgRaysPerObject() const
168	{
169	return (float)mRays->size() / ((float)mPvs + Limits::Small);
170	}
171
172
173	float VspTree::VspTraversalData::GetCost() const
174	{
175	return mPriority;
176	}
177
178
179	void VspTree::VspTraversalData::Clear()
180	{
181	DEL_PTR(mRays);
182
183	if (mNode)
184	{ // delete old view cell
185	delete mNode->GetViewCell();
186	delete mNode;
187	mNode = NULL;
188	}
189	}
190
191
192	/******************************************************************/
193	/* class VspNode implementation */
194	/******************************************************************/
195
196
197	VspNode::VspNode():
198	mParent(NULL),
199	mTreeValid(true),
200	mTimeStamp(0)
201	{}
202
203
204	VspNode::VspNode(VspInterior *parent):
205	mParent(parent),
206	mTreeValid(true),
207	mTimeStamp(0)
208	{}
209
210
211	bool VspNode::IsRoot() const
212	{
213	return mParent == NULL;
214	}
215
216
217	VspInterior *VspNode::GetParent()
218	{
219	return mParent;
220	}
221
222
223	void VspNode::SetParent(VspInterior *parent)
224	{
225	mParent = parent;
226	}
227
228
229	bool VspNode::IsSibling(VspNode *n) const
230	{
231	return ((this != n) && mParent &&
232	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
233	}
234
235
236	int VspNode::GetDepth() const
237	{
238	int depth = 0;
239	VspNode *p = mParent;
240
241	while (p)
242	{
243	p = p->mParent;
244	++ depth;
245	}
246
247	return depth;
248	}
249
250
251	bool VspNode::TreeValid() const
252	{
253	return mTreeValid;
254	}
255
256
257	void VspNode::SetTreeValid(const bool v)
258	{
259	mTreeValid = v;
260	}
261
262
263
264	/****************************************************************/
265	/* class VspInterior implementation */
266	/****************************************************************/
267
268
269	VspInterior::VspInterior(const AxisAlignedPlane &plane):
270	mPlane(plane), mFront(NULL), mBack(NULL)
271	{}
272
273
274	VspInterior::~VspInterior()
275	{
276	DEL_PTR(mFront);
277	DEL_PTR(mBack);
278	}
279
280
281
282
283
284
285	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
286	{
287	if (mBack == oldChild)
288	mBack = newChild;
289	else
290	mFront = newChild;
291	}
292
293
294	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
295	{
296	mBack = back;
297	mFront = front;
298	}
299
300
301	AxisAlignedBox3 VspInterior::GetBoundingBox() const
302	{
303	return mBoundingBox;
304	}
305
306
307	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
308	{
309	mBoundingBox = box;
310	}
311
312
313	int VspInterior::Type() const
314	{
315	return Interior;
316	}
317
318
319
320	/****************************************************************/
321	/* class VspLeaf implementation */
322	/****************************************************************/
323
324
325	VspLeaf::VspLeaf():
326	mViewCell(NULL), mSubdivisionCandidate(NULL)
327	{
328	}
329
330
331	VspLeaf::~VspLeaf()
332	{
333	VssRayContainer::const_iterator vit, vit_end = mVssRays.end();
334
335	for (vit = mVssRays.begin(); vit != vit_end; ++ vit)
336	{
337	VssRay ray = vit;
338	ray->Unref();
339
340	if (!ray->IsActive())
341	delete ray;
342	}
343	}
344
345
346	int VspLeaf::Type() const
347	{
348	return Leaf;
349	}
350
351
352	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
353	mViewCell(viewCell)
354	{
355	}
356
357
358	VspLeaf::VspLeaf(VspInterior *parent):
359	VspNode(parent), mViewCell(NULL)
360	{}
361
362
363	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
364	VspNode(parent), mViewCell(viewCell)
365	{
366	}
367
368
369
370
371	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
372	{
373	mViewCell = viewCell;
374	}
375
376
377
378
379
380	/*************************************************************************/
381	/* class VspTree implementation */
382	/*************************************************************************/
383
384
385	VspTree::VspTree():
386	mRoot(NULL),
387	mOutOfBoundsCell(NULL),
388	mStoreRays(false),
389	//mStoreRays(true),
390	mTimeStamp(1),
391	mHierarchyManager(NULL)
392	{
393	mLocalSubdivisionCandidates = new vector<SortableEntry>;
394
395	bool randomize = false;
396	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
397	if (randomize)
398	Randomize(); // initialise random generator for heuristics
399
400	char subdivisionStatsLog[100];
401	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
402	mSubdivisionStats.open(subdivisionStatsLog);
403
404	/////////////
405	//-- termination criteria for autopartition
406
407	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
408	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
409	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
410	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
411	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
412
413	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
414	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
415	// max cost ratio for early tree termination
416	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
417
418	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
419	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
420
421	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
422
423
424	//////////////
425	//-- factors for bsp tree split plane heuristics
426
427	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
428	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
429	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
430	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
431	Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
432
433	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
434
435	// if only the driving axis is used for axis aligned split
436	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
437	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
438	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
439
440	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
441	//mMemoryConst = 50;//(float)(sizeof(VspViewCell));
442	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(ObjectPvs));
443
444	mMemoryConst = 16;//(float)sizeof(ObjectPvs);
445
446
447	//////////////
448	//-- debug output
449
450	Debug << "***** VSP options ******" << endl;
451
452	Debug << "max depth: " << mTermMaxDepth << endl;
453	Debug << "min PVS: " << mTermMinPvs << endl;
454	Debug << "min probabiliy: " << mTermMinProbability << endl;
455	Debug << "min rays: " << mTermMinRays << endl;
456	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
457	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
458	Debug << "miss tolerance: " << mTermMissTolerance << endl;
459	Debug << "max view cells: " << mMaxViewCells << endl;
460	Debug << "randomize: " << randomize << endl;
461
462	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
463	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
464	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
465	Debug << "max memory: " << mMaxMemory << endl;
466	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
467	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
468	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
469
470	Debug << "circulating axis: " << mCirculatingAxis << endl;
471	Debug << "minband: " << mMinBand << endl;
472	Debug << "maxband: " << mMaxBand << endl;
473
474	Debug << "vsp mem const: " << mMemoryConst << endl;
475
476	Debug << endl;
477	}
478
479
480	VspViewCell *VspTree::GetOutOfBoundsCell()
481	{
482	return mOutOfBoundsCell;
483	}
484
485
486	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
487	{
488	if (!mOutOfBoundsCell)
489	{
490	mOutOfBoundsCell = new VspViewCell();
491	mOutOfBoundsCell->SetId(-1);
492	mOutOfBoundsCell->SetValid(false);
493	}
494
495	return mOutOfBoundsCell;
496	}
497
498
499	const VspTreeStatistics &VspTree::GetStatistics() const
500	{
501	return mVspStats;
502	}
503
504
505	VspTree::~VspTree()
506	{
507	DEL_PTR(mRoot);
508	DEL_PTR(mLocalSubdivisionCandidates);
509	}
510
511
512	void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
513	AxisAlignedBox3 *forcedBoundingBox)
514	{
515	if (forcedBoundingBox)
516	{
517	mBoundingBox = *forcedBoundingBox;
518	return;
519	}
520
521	//////////////////////////////////////////////
522	// bounding box of view space includes all visibility events
523
524	mBoundingBox.Initialize();
525	VssRayContainer::const_iterator rit, rit_end = rays.end();
526
527	for (rit = rays.begin(); rit != rit_end; ++ rit)
528	{
529	VssRay ray = rit;
530
531	mBoundingBox.Include(ray->GetTermination());
532	mBoundingBox.Include(ray->GetOrigin());
533	}
534	}
535
536
537	void VspTree::AddSubdivisionStats(const int viewCells,
538	const float renderCostDecr,
539	const float totalRenderCost,
540	const float avgRenderCost)
541	{
542	mSubdivisionStats
543	<< "#ViewCells\n" << viewCells << endl
544	<< "#RenderCostDecrease\n" << renderCostDecr << endl
545	<< "#TotalRenderCost\n" << totalRenderCost << endl
546	<< "#AvgRenderCost\n" << avgRenderCost << endl;
547	}
548
549
550	// $$matt temporary: number of rayrefs + pvs should be in there, but
551	// commented out for testing
552	float VspTree::GetMemUsage() const
553	{
554	return (float)
555	(sizeof(VspTree)
556	+ mVspStats.Leaves() * sizeof(VspLeaf)
557	+ mVspStats.Leaves() * sizeof(VspViewCell)
558	+ mVspStats.Interior() * sizeof(VspInterior)
559	//+ mVspStats.pvs * sizeof(PvsData)
560	//+ mVspStats.rayRefs * sizeof(RayInfo)
561	) / (1024.0f * 1024.0f);
562	}
563
564
565	inline bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
566	{
567	const bool localTerminationCriteriaMet = (0
568	\|\| ((int)data.mRays->size() <= mTermMinRays)
569	\|\| (data.mPvs <= mTermMinPvs)
570	\|\| (data.mProbability <= mTermMinProbability)
571	\|\| (data.mDepth >= mTermMaxDepth)
572	);
573
574	#if GTP_DEBUG
575	if (localTerminationCriteriaMet)
576	{
577	Debug << "local termination criteria met:" << endl;
578	Debug << "rays: " << (int)data.mRays->size() << " " << mTermMinRays << endl;
579	Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
580	Debug << "p: " << data.mProbability << " " << mTermMinProbability << endl;
581	Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
582	Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
583	}
584	#endif
585	return localTerminationCriteriaMet;
586	}
587
588
589	inline bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
590	{
591	// note: to track for global cost misses does not really
592	// make sense because termination on cost or memory is done
593	// in the hierarchy mananger
594	const bool terminationCriteriaMet = (0
595	// \|\| mOutOfMemory
596	\|\| (mVspStats.Leaves() >= mMaxViewCells)
597	// \|\| (mVspStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
598	);
599
600	#if GTP_DEBUG
601	if (terminationCriteriaMet)
602	{
603	Debug << "vsp global termination criteria met:" << endl;
604	Debug << "cost misses: " << mVspStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
605	Debug << "leaves: " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
606	}
607	#endif
608
609	return terminationCriteriaMet;
610	}
611
612
613	void VspTree::CreateViewCell(VspTraversalData &tData,
614	const bool updatePvs,
615	const float renderCost,
616	const int pvs)
617	{
618	///////////////
619	//-- create new view cell
620
621	VspLeaf *leaf = tData.mNode;
622
623	VspViewCell *viewCell = new VspViewCell();
624	leaf->SetViewCell(viewCell);
625
626	int conSamp = 0;
627	float sampCon = 0.0f;
628
629	if (updatePvs)
630	{
631	// store pvs of view cell
632	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
633
634	// update scalar pvs size value
635	ObjectPvs &pvs = viewCell->GetPvs();
636	mViewCellsManager->UpdateScalarPvsSize(viewCell,
637	pvs.EvalPvsCost(),
638	pvs.GetSize());
639
640	mVspStats.contributingSamples += conSamp;
641	mVspStats.sampleContributions += (int)sampCon;
642	}
643	else
644	{
645	viewCell->SetTrianglesInPvs(renderCost);
646	viewCell->SetEntriesInPvs(pvs);
647
648	//cout << "create view cell with tri=" << (int)renderCost << " pvs=" << pvs << endl;
649	}
650
651	if (mStoreRays)
652	{
653	///////////
654	//-- store sampling rays
655
656	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
657
658	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
659	{
660	VssRay ray = new VssRay((*rit).mRay);
661	ray->Ref();
662
663	// note: should rather store rays with view cell
664	leaf->mVssRays.push_back(ray);
665	}
666	}
667
668	// set view cell values
669	viewCell->mLeaves.push_back(leaf);
670
671	viewCell->SetVolume(tData.mProbability);
672	leaf->mProbability = tData.mProbability;
673	}
674
675
676	void VspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
677	{
678	const float costDecr = sc.GetRenderCostDecrease();
679
680	AddSubdivisionStats(mVspStats.Leaves(),
681	costDecr,
682	mTotalCost,
683	(float)mTotalPvsSize / (float)mVspStats.Leaves());
684	}
685
686
687	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
688	SubdivisionCandidate *splitCandidate,
689	const bool globalCriteriaMet)
690	{
691	mSubdivTimer.Entry();
692
693	// todo remove dynamic cast
694	VspSubdivisionCandidate *sc =
695	static_cast<VspSubdivisionCandidate *>(splitCandidate);
696
697	VspTraversalData &tData = sc->mParentData;
698	VspNode *newNode = tData.mNode;
699
700	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
701	{
702	///////////
703	//-- continue subdivision
704
705	VspTraversalData tFrontData;
706	VspTraversalData tBackData;
707
708	// create new interior node and two leaf node
709	const int maxCostMisses = sc->GetMaxCostMisses();
710
711	newNode = SubdivideNode(*sc, tFrontData, tBackData);
712
713	// how often was max cost ratio missed in this branch?
714	tFrontData.mMaxCostMisses = maxCostMisses;
715	tBackData.mMaxCostMisses = maxCostMisses;
716
717	mTotalCost -= sc->GetRenderCostDecrease();
718	//mTotalPvsSize += (int)(tFrontData.mPvs + tBackData.mPvs - tData.mPvs);
719	mPvsEntries += sc->GetPvsEntriesIncr();
720
721	// subdivision statistics
722	if (1) EvalSubdivisionStats(*sc);
723
724	/////////////
725	//-- evaluate new split candidates for global greedy cost heuristics
726
727	VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
728	VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
729
730	EvalSubdivisionCandidate(*frontCandidate);
731	EvalSubdivisionCandidate(*backCandidate);
732
733	// cross reference
734	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
735	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
736
737	tQueue.Push(frontCandidate);
738	tQueue.Push(backCandidate);
739
740	// note: leaf is not destroyed because it is needed to collect
741	// dirty candidates in hierarchy manager
742	}
743
744	if (newNode->IsLeaf()) // subdivision terminated
745	{
746	VspLeaf leaf = static_cast<VspLeaf >(newNode);
747
748	if (0 && mStoreRays)
749	{
750	//////////
751	//-- store rays piercing this view cell
752
753	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
754	for (it = tData.mRays->begin(); it != it_end; ++ it)
755	{
756	(*it).mRay->Ref();
757	leaf->mVssRays.push_back((*it).mRay);
758	}
759	}
760
761	// finally evaluate statistics for this leaf
762	EvaluateLeafStats(tData);
763	// detach subdivision candidate: this leaf is no candidate for
764	// splitting anymore
765	tData.mNode->SetSubdivisionCandidate(NULL);
766	// detach node so it won't get deleted
767	tData.mNode = NULL;
768	}
769
770	mSubdivTimer.Exit();
771
772	return newNode;
773	}
774
775
776	void VspTree::EvalSubdivisionCandidate(VspSubdivisionCandidate &splitCandidate,
777	bool computeSplitPlane)
778	{
779	mPlaneTimer.Entry();
780
781	if (computeSplitPlane)
782	{
783	float frontProb;
784	float backProb;
785
786	// compute locally best split plane
787	const float ratio = SelectSplitPlane(splitCandidate.mParentData,
788	splitCandidate.mSplitPlane,
789	frontProb,
790	backProb);
791
792	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
793
794	const int maxCostMisses = splitCandidate.mParentData.mMaxCostMisses;
795	// max cost threshold violated?
796	splitCandidate.SetMaxCostMisses(maxCostRatioViolated ?
797	maxCostMisses + 1: maxCostMisses);
798	}
799
800	mPlaneTimer.Exit();
801	mEvalTimer.Entry();
802
803	VspLeaf leaf = static_cast<VspLeaf >(splitCandidate.mParentData.mNode);
804
805
806	//////////////
807	//-- compute global decrease in render cost
808
809	const AxisAlignedPlane candidatePlane = splitCandidate.mSplitPlane;
810
811	RayInfoContainer::const_iterator rit, rit_end = splitCandidate.mParentData.mRays->end();
812
813	SplitData sData;
814
815	Intersectable::NewMail(3);
816	KdLeaf::NewMail(3);
817
818	for (rit = splitCandidate.mParentData.mRays->begin(); rit != rit_end; ++ rit)
819	{
820	RayInfo rayInf = *rit;
821
822	float t;
823
824	// classify ray
825	const int cf = rayInf.ComputeRayIntersection(candidatePlane.mAxis,
826	candidatePlane.mPosition,
827	t);
828
829	VssRay *ray = rayInf.mRay;
830
831	#if HACK_PERFORMANCE
832	Intersectable obj = (ray).mTerminationObject;
833
834	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
835
836	// evaluate contribution of ray endpoint to front
837	// and back pvs with respect to the classification
838	UpdateContributionsToPvs(leaf, cf, sData);
839
840	#if COUNT_ORIGIN_OBJECTS
841	obj = (*ray).mOriginObject;
842
843	if (obj)
844	{
845	leaf = mBvHierarchy->GetLeaf(obj);
846	UpdateContributionsToPvs(leaf, cf, sData);
847	}
848	#endif
849
850	#else
851	cerr << "TODO classify" << endl;
852	#endif
853	}
854
855	sData.mTotalRenderCost = mViewCellsManager->ComputeRenderCost(sData.mTotalTriangles, sData.mTotalObjects);
856	sData.mBackRenderCost = mViewCellsManager->ComputeRenderCost(sData.mBackTriangles, sData.mBackObjects);
857	sData.mFrontRenderCost = mViewCellsManager->ComputeRenderCost(sData.mFrontTriangles, sData.mFrontObjects);
858
859
860	/////////////
861	// avg ray contri
862
863	const float avgRayContri = (float)sData.mTotalObjects /
864	((float)splitCandidate.mParentData.mRays->size() + Limits::Small);
865
866	const float avgRaysPerObject = (float)splitCandidate.mParentData.mRays->size() /
867	((float)sData.mTotalObjects + Limits::Small);
868
869	//cout << "avg rays per obj: " << avgRaysPerObject << endl;
870
871	splitCandidate.SetAvgRayContribution(avgRayContri);
872	splitCandidate.SetAvgRaysPerObject(avgRaysPerObject);
873
874	// todo: compute old render cost in the function
875	// using michi's render cost evaluation
876	float oldRenderCost;
877	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate, oldRenderCost, sData);
878	splitCandidate.SetRenderCostDecrease(renderCostDecr);
879
880	// the increase in pvs entries num induced by this split
881	const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate, sData);
882	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
883
884	splitCandidate.mFrontTriangles = (float)sData.mFrontTriangles;
885	splitCandidate.mBackTriangles = (float)sData.mBackTriangles;
886
887	// take render cost of node into account
888	// otherwise danger of being stuck in a local minimum!
889	float priority = mRenderCostDecreaseWeight * renderCostDecr + (1.0f - mRenderCostDecreaseWeight) * oldRenderCost;
890
891	if (mHierarchyManager->mConsiderMemory)
892	{
893	priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
894	}
895
896	splitCandidate.SetPriority(priority);
897
898	//cout << "vsp render cost decrease=" << renderCostDecr << endl;
899	mEvalTimer.Exit();
900	}
901
902
903	int VspTree::EvalPvsEntriesIncr(VspSubdivisionCandidate &splitCandidate,
904	const SplitData &sData) const
905	{
906	const float oldPvsRatio = (splitCandidate.mParentData.mPvs > 0) ?
907	sData.mTotalObjects / splitCandidate.mParentData.mPvs : 1;
908	const float correctedOldPvs = splitCandidate.mParentData.mCorrectedPvs * oldPvsRatio;
909
910	splitCandidate.mCorrectedFrontPvs =
911	mHierarchyManager->EvalCorrectedPvs((float)sData.mFrontObjects,
912	(float)correctedOldPvs,
913	splitCandidate.GetAvgRaysPerObject());
914	splitCandidate.mCorrectedBackPvs =
915	mHierarchyManager->EvalCorrectedPvs((float)sData.mBackObjects,
916	(float)correctedOldPvs,
917	splitCandidate.GetAvgRaysPerObject());
918
919	splitCandidate.mFrontPvs = (float)sData.mFrontObjects;
920	splitCandidate.mBackPvs = (float)sData.mBackObjects;
921
922	return (int)(splitCandidate.mCorrectedFrontPvs + splitCandidate.mCorrectedBackPvs - correctedOldPvs);
923	}
924
925
926	VspInterior *VspTree::SubdivideNode(const VspSubdivisionCandidate &sc,
927	VspTraversalData &frontData,
928	VspTraversalData &backData)
929	{
930	mNodeTimer.Entry();
931
932	VspLeaf leaf = static_cast<VspLeaf >(sc.mParentData.mNode);
933
934	const VspTraversalData &tData = sc.mParentData;
935	const AxisAlignedPlane &splitPlane = sc.mSplitPlane;
936
937	///////////////
938	//-- new traversal values
939
940	frontData.mDepth = tData.mDepth + 1;
941	backData.mDepth = tData.mDepth + 1;
942
943	frontData.mRays = new RayInfoContainer();
944	backData.mRays = new RayInfoContainer();
945
946	//-- subdivide rays
947	SplitRays(splitPlane, tData.mRays, frontData.mRays, *backData.mRays);
948
949	//-- compute pvs
950	frontData.mPvs = sc.mFrontPvs;
951	backData.mPvs = sc.mBackPvs;
952
953	//-- compute pvs correction for coping with undersampling
954	frontData.mCorrectedPvs = sc.mCorrectedFrontPvs;
955	backData.mCorrectedPvs = sc.mCorrectedBackPvs;
956
957	//-- split front and back node geometry and compute area
958	tData.mBoundingBox.Split(splitPlane.mAxis,
959	splitPlane.mPosition,
960	frontData.mBoundingBox,
961	backData.mBoundingBox);
962
963	frontData.mProbability = frontData.mBoundingBox.GetVolume();
964	backData.mProbability = tData.mProbability - frontData.mProbability;
965
966	//-- compute render cost
967	frontData.mRenderCost = sc.mFrontRenderCost;
968	backData.mRenderCost = sc.mBackRenderCost;
969
970	frontData.mCorrectedRenderCost = sc.mCorrectedFrontRenderCost;
971	backData.mCorrectedRenderCost = sc.mCorrectedBackRenderCost;
972
973	////////
974	//-- update some stats
975
976	if (tData.mDepth > mVspStats.maxDepth)
977	{
978	mVspStats.maxDepth = tData.mDepth;
979	}
980
981	// two more leaves per split
982	mVspStats.nodes += 2;
983	// and a new split
984	++ mVspStats.splits[splitPlane.mAxis];
985
986
987	////////////////
988	//-- create front and back and subdivide further
989
990	VspInterior *interior = new VspInterior(splitPlane);
991	VspInterior *parent = leaf->GetParent();
992
993	// replace a link from node's parent
994	if (parent)
995	{
996	parent->ReplaceChildLink(leaf, interior);
997	interior->SetParent(parent);
998	}
999	else // new root
1000	{
1001	mRoot = interior;
1002	}
1003
1004	VspLeaf *frontLeaf = new VspLeaf(interior);
1005	VspLeaf *backLeaf = new VspLeaf(interior);
1006
1007	// and setup child links
1008	interior->SetupChildLinks(frontLeaf, backLeaf);
1009
1010	// add bounding box
1011	interior->SetBoundingBox(tData.mBoundingBox);
1012
1013	// set front and back leaf
1014	frontData.mNode = frontLeaf;
1015	backData.mNode = backLeaf;
1016
1017	// create front and back view cell for the new leaves
1018	CreateViewCell(frontData, false, sc.mFrontTriangles, (int)sc.mFrontPvs);
1019	CreateViewCell(backData, false, sc.mBackTriangles, (int)sc.mBackPvs);
1020
1021	// set the time stamp so the order of traversal can be reconstructed
1022	interior->mTimeStamp = mHierarchyManager->mTimeStamp ++;
1023
1024	mNodeTimer.Exit();
1025
1026	return interior;
1027	}
1028
1029
1030	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
1031	const RayInfoContainer &rays,
1032	float &sampleContributions,
1033	int &contributingSamples)
1034	{
1035	sampleContributions = 0;
1036	contributingSamples = 0;
1037
1038	RayInfoContainer::const_iterator it, it_end = rays.end();
1039
1040	ViewCellLeaf *vc = leaf->GetViewCell();
1041
1042	// add contributions from samples to the pvs
1043	for (it = rays.begin(); it != it_end; ++ it)
1044	{
1045	float sc = 0.0f;
1046	VssRay ray = (it).mRay;
1047
1048	bool madeContrib = false;
1049	float contribution = 1;
1050
1051	Intersectable *entry =
1052	mHierarchyManager->GetIntersectable(ray->mTerminationObject, true);
1053
1054	if (entry)
1055	{
1056	madeContrib =
1057	vc->GetPvs().AddSample(entry, ray->mPdf);
1058
1059	sc += contribution;
1060	}
1061	#if COUNT_ORIGIN_OBJECTS
1062	entry = mHierarchyManager->GetIntersectable(ray->mOriginObject, true);
1063
1064	if (entry)
1065	{
1066	madeContrib =
1067	vc->GetPvs().AddSample(entry, ray->mPdf);
1068
1069	sc += contribution;
1070	}
1071	#endif
1072	if (madeContrib)
1073	{
1074	++ contributingSamples;
1075	}
1076	}
1077	}
1078
1079
1080	void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
1081	const int axis,
1082	float minBand,
1083	float maxBand)
1084	{
1085	mSortTimer.Entry();
1086
1087	mLocalSubdivisionCandidates->clear();
1088
1089	const int requestedSize = 2 * (int)(rays.size());
1090
1091	// creates a sorted split candidates array
1092	if (mLocalSubdivisionCandidates->capacity() > 500000 &&
1093	requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
1094	{
1095	delete mLocalSubdivisionCandidates;
1096	mLocalSubdivisionCandidates = new vector<SortableEntry>;
1097	}
1098
1099	mLocalSubdivisionCandidates->reserve(requestedSize);
1100
1101	float pos;
1102	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1103
1104	const bool delayMinEvent = false;
1105
1106	////////////
1107	//-- insert all queries
1108	for (rit = rays.begin(); rit != rit_end; ++ rit)
1109	{
1110	const bool positive = (*rit).mRay->HasPosDir(axis);
1111
1112	// origin point
1113	pos = (*rit).ExtrapOrigin(axis);
1114	const int oType = positive ? SortableEntry::ERayMin : SortableEntry::ERayMax;
1115
1116	if (delayMinEvent && oType == SortableEntry::ERayMin)
1117	pos += mEpsilon; // could be useful feature for walls
1118
1119	mLocalSubdivisionCandidates->push_back(SortableEntry(oType, pos, (*rit).mRay));
1120
1121	// termination point
1122	pos = (*rit).ExtrapTermination(axis);
1123	const int tType = positive ? SortableEntry::ERayMax : SortableEntry::ERayMin;
1124
1125	if (delayMinEvent && tType == SortableEntry::ERayMin)
1126	pos += mEpsilon; // could be useful feature for walls
1127
1128	mLocalSubdivisionCandidates->push_back(SortableEntry(tType, pos, (*rit).mRay));
1129	}
1130
1131	if (1)
1132	stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1133	else
1134	sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1135
1136	mSortTimer.Exit();
1137	}
1138
1139
1140	float VspTree::PrepareHeuristics(KdLeaf *leaf)
1141	{
1142	float pvsSize = 0;
1143
1144	if (!leaf->Mailed())
1145	{
1146	leaf->Mail();
1147	leaf->mCounter = 1;
1148	// add objects without the objects which are in several kd leaves
1149	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1150	}
1151	else
1152	{
1153	++ leaf->mCounter;
1154	}
1155
1156	//-- the objects belonging to several leaves must be handled seperately
1157	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1158
1159	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1160	{
1161	Intersectable object = oit;
1162
1163	if (!object->Mailed())
1164	{
1165	object->Mail();
1166	object->mCounter = 1;
1167
1168	++ pvsSize;
1169	}
1170	else
1171	{
1172	++ object->mCounter;
1173	}
1174	}
1175
1176	return pvsSize;
1177	}
1178
1179
1180	float VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1181	{
1182	Intersectable::NewMail();
1183	KdNode::NewMail();
1184
1185	float pvsSize = 0;
1186
1187	RayInfoContainer::const_iterator ri, ri_end = rays.end();
1188
1189	// set all kd nodes / objects as belonging to the front pvs
1190	for (ri = rays.begin(); ri != ri_end; ++ ri)
1191	{
1192	VssRay ray = (ri).mRay;
1193
1194	pvsSize += PrepareHeuristics(*ray, true);
1195	#if COUNT_ORIGIN_OBJECTS
1196	pvsSize += PrepareHeuristics(*ray, false);
1197	#endif
1198	}
1199
1200	return pvsSize;
1201	}
1202
1203
1204	float VspTree::EvalMaxEventContribution(KdLeaf *leaf) const
1205	{
1206	float pvs = 0;
1207
1208	// leaf falls out of right pvs
1209	if (-- leaf->mCounter == 0)
1210	{
1211	pvs -= ((float)leaf->mObjects.size() - (float)leaf->mMultipleObjects.size());
1212	}
1213
1214	//////
1215	//-- separately handle objects which are in several kd leaves
1216
1217	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1218
1219	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1220	{
1221	Intersectable object = oit;
1222
1223	if (-- object->mCounter == 0)
1224	{
1225	++ pvs;
1226	}
1227	}
1228
1229	return pvs;
1230	}
1231
1232
1233	float VspTree::EvalMinEventContribution(KdLeaf *leaf) const
1234	{
1235	if (leaf->Mailed())
1236	return 0;
1237
1238	leaf->Mail();
1239
1240	// add objects without those which are part of several kd leaves
1241	float pvs = ((float)leaf->mObjects.size() - (float)leaf->mMultipleObjects.size());
1242
1243	// separately handle objects which are part of several kd leaves
1244	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1245
1246	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1247	{
1248	Intersectable object = oit;
1249
1250	// object not previously in pvs
1251	if (!object->Mailed())
1252	{
1253	object->Mail();
1254	++ pvs;
1255	}
1256	}
1257
1258	return pvs;
1259	}
1260
1261
1262	void VspTree::EvalHeuristics(const SortableEntry &ci,
1263	float &pvsLeft,
1264	float &pvsRight) const
1265	{
1266	VssRay *ray = ci.ray;
1267
1268	// eval changes in pvs causes by min event
1269	if (ci.type == SortableEntry::ERayMin)
1270	{
1271	pvsLeft += EvalMinEventContribution(*ray, true);
1272	#if COUNT_ORIGIN_OBJECTS
1273	pvsLeft += EvalMinEventContribution(*ray, false);
1274	#endif
1275	}
1276	else // eval changes in pvs causes by max event
1277	{
1278	pvsRight -= EvalMaxEventContribution(*ray, true);
1279	#if COUNT_ORIGIN_OBJECTS
1280	pvsRight -= EvalMaxEventContribution(*ray, false);
1281	#endif
1282	}
1283	}
1284
1285
1286	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1287	const AxisAlignedBox3 &box,
1288	const int axis,
1289	float &position,
1290	const RayInfoContainer &usedRays)
1291	{
1292	const float minBox = box.Min(axis);
1293	const float maxBox = box.Max(axis);
1294
1295	const float sizeBox = maxBox - minBox;
1296
1297	const float minBand = minBox + mMinBand * sizeBox;
1298	const float maxBand = minBox + mMaxBand * sizeBox;
1299
1300	// sort by the current dimension
1301	SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1302
1303	// prepare the sweep
1304	// note: returns pvs size => no need t give pvs size as function parameter
1305	const float pvsCost = PrepareHeuristics(usedRays);
1306
1307	// go through the lists, count the number of objects left and right
1308	// and evaluate the following cost funcion:
1309	// C = ct_div_ci + (qlrl + qrrr)/queries
1310
1311	float pvsl = 0;
1312	float pvsr = pvsCost;
1313
1314	float pvsBack = pvsl;
1315	float pvsFront = pvsr;
1316
1317	float sum = pvsCost * sizeBox;
1318	float minSum = 1e20f;
1319
1320	// if no good split can be found, take mid split
1321	position = minBox + 0.5f * sizeBox;
1322
1323	// the relative cost ratio
1324	float ratio = 99999999.0f;
1325	bool splitPlaneFound = false;
1326
1327	Intersectable::NewMail();
1328	KdLeaf::NewMail();
1329
1330	const float volRatio =
1331	tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1332
1333	////////
1334	//-- iterate through visibility events
1335
1336	vector<SortableEntry>::const_iterator ci,
1337	ci_end = mLocalSubdivisionCandidates->end();
1338
1339	#ifdef GTP_DEBUG
1340	const int leaves = mVspStats.Leaves();
1341	const bool printStats = ((axis == 0) && (leaves > 0) && (leaves < 90));
1342
1343	ofstream sumStats;
1344	ofstream pvslStats;
1345	ofstream pvsrStats;
1346
1347	if (printStats)
1348	{
1349	char str[64];
1350
1351	sprintf(str, "tmp/vsp_heur_sum-%04d.log", leaves);
1352	sumStats.open(str);
1353	sprintf(str, "tmp/vsp_heur_pvsl-%04d.log", leaves);
1354	pvslStats.open(str);
1355	sprintf(str, "tmp/vsp_heur_pvsr-%04d.log", leaves);
1356	pvsrStats.open(str);
1357	}
1358
1359	#endif
1360
1361
1362	for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1363	{
1364	// compute changes to front and back pvs
1365	EvalHeuristics(*ci, pvsl, pvsr);
1366
1367	// Note: sufficient to compare size of bounding boxes of front and back side?
1368	if (((ci).value >= minBand) && ((ci).value <= maxBand))
1369	{
1370	float currentPos;
1371
1372	// HACK: current positition is BETWEEN visibility events
1373	if (0 && ((ci + 1) != ci_end))
1374	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
1375	else
1376	currentPos = (*ci).value;
1377
1378	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
1379
1380	#ifdef GTP_DEBUG
1381	if (printStats)
1382	{
1383	sumStats
1384	<< "#Position\n" << currentPos << endl
1385	<< "#Sum\n" << sum * volRatio << endl
1386	<< "#Pvs\n" << pvsl + pvsr << endl;
1387
1388	pvslStats
1389	<< "#Position\n" << currentPos << endl
1390	<< "#Pvsl\n" << pvsl << endl;
1391
1392	pvsrStats
1393	<< "#Position\n" << currentPos << endl
1394	<< "#Pvsr\n" << pvsr << endl;
1395	}
1396	#endif
1397
1398	if (sum < minSum)
1399	{
1400	splitPlaneFound = true;
1401
1402	minSum = sum;
1403	position = currentPos;
1404
1405	pvsBack = pvsl;
1406	pvsFront = pvsr;
1407	}
1408	}
1409	}
1410
1411	/////////
1412	//-- compute cost
1413
1414	const float pOverall = sizeBox;
1415	const float pBack = position - minBox;
1416	const float pFront = maxBox - position;
1417
1418	const float penaltyOld = pvsCost;
1419	const float penaltyFront = pvsFront;
1420	const float penaltyBack = pvsBack;
1421
1422	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1423	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1424
1425	#if VISUALIZE_SPLIT
1426
1427	const int leaves = mVspStats.Leaves();
1428	const bool showViz = (leaves >= 3000) && (leaves % 497 == 0);
1429
1430	if (showViz)
1431	{
1432	//cout << "========================== exporting split ===================" << endl;
1433
1434	Exporter *exporter;
1435
1436	char str[64]; sprintf(str, "vc-%04d_%d.wrl", leaves, axis);
1437
1438	exporter = Exporter::GetExporter(str);
1439
1440	Material m;
1441	m.mDiffuseColor.r = 1.0f;
1442	m.mDiffuseColor.g = 0.0f;
1443	m.mDiffuseColor.b = 0.0f;
1444
1445	exporter->SetForcedMaterial(m);
1446	exporter->SetWireframe();
1447
1448	exporter->ExportBox(tData.mBoundingBox);
1449
1450	exporter->ResetForcedMaterial();
1451
1452	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1453
1454	exporter->SetFilled();
1455
1456	m.mDiffuseColor.r = 0.0f;
1457	m.mDiffuseColor.g = 1.0f;
1458	m.mDiffuseColor.b = 0.0f;
1459
1460	exporter->SetForcedMaterial(m);
1461
1462	// create unique ids for pvs heuristics
1463	Intersectable::NewMail(3);
1464
1465	float a = 0, b = 0, c = 0;
1466
1467	// this is the main ray classification loop!
1468	for(rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1469	{
1470	VssRay ray = (rit).mRay;
1471
1472	// determine the side of this ray with respect to the plane
1473	float t;
1474	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1475
1476	UpdateContributionsToPvs(*ray, true, side, a, b, c);
1477	UpdateContributionsToPvs(*ray, false, side, a, b, c);
1478	}
1479
1480
1481	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1482	{
1483	RayInfo rayInf = *rit;
1484
1485	// export objects
1486	VssRay *ray = rayInf.mRay;
1487	BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray->mTerminationObject);
1488
1489	//left and right
1490	if (leaf->Mailed(2))
1491	{
1492	m.mDiffuseColor.r = 0.0f;
1493	m.mDiffuseColor.g = 1.0f;
1494	m.mDiffuseColor.b = 1.0f;
1495	}
1496	else if (leaf->Mailed(1)) // only right
1497	{
1498	m.mDiffuseColor.r = 0.0f;
1499	m.mDiffuseColor.g = 1.0f;
1500	m.mDiffuseColor.b = 0.0f;
1501	}
1502	else // left
1503	{
1504	m.mDiffuseColor.r = 0.0f;
1505	m.mDiffuseColor.g = 0.0f;
1506	m.mDiffuseColor.b = 1.0f;
1507	}
1508
1509	exporter->SetForcedMaterial(m);
1510	exporter->ExportIntersectable(leaf);
1511
1512	}
1513
1514	m.mDiffuseColor.r = 1.0f;
1515	m.mDiffuseColor.g = 0.0f;
1516	m.mDiffuseColor.b = 1.0f;
1517
1518	exporter->SetForcedMaterial(m);
1519	AxisAlignedBox3 vizPlaneBox;
1520	vizPlaneBox = tData.mBoundingBox;
1521
1522	vizPlaneBox.SetMin(axis, position - 0.01);
1523	vizPlaneBox.SetMax(axis, position + 0.01);
1524
1525	exporter->ExportBox(vizPlaneBox);
1526
1527	delete exporter;
1528	}
1529
1530	#endif
1531
1532	if (splitPlaneFound)
1533	{
1534	ratio = newRenderCost / oldRenderCost;
1535	}
1536
1537
1538	#ifdef GTP_DEBUG
1539	Debug << "\n((((( eval local vsp cost )))))" << endl
1540	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1541	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1542	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1543	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1544	#endif
1545
1546	return ratio;
1547	}
1548
1549
1550	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1551	AxisAlignedPlane &plane,
1552	float &pFront,
1553	float &pBack)
1554	{
1555	mSplitTimer.Entry();
1556
1557	float nPosition[3];
1558	float nCostRatio[3];
1559	float nProbFront[3];
1560	float nProbBack[3];
1561
1562	// create bounding box of node geometry
1563	AxisAlignedBox3 box = tData.mBoundingBox;
1564
1565	int sAxis = 0;
1566	int bestAxis = -1;
1567
1568	// do we use some kind of specialised "fixed" axis?
1569	const bool useSpecialAxis =
1570	mOnlyDrivingAxis \|\| mCirculatingAxis;
1571
1572	// get subset of rays
1573	RayInfoContainer randomRays;
1574	randomRays.reserve(min(mMaxTests, (int)tData.mRays->size()));
1575
1576	RayInfoContainer *usedRays;
1577
1578	if (mMaxTests < (int)tData.mRays->size())
1579	{
1580	GetRayInfoSets(*tData.mRays, mMaxTests, randomRays);
1581	usedRays = &randomRays;
1582	}
1583	else
1584	{
1585	usedRays = tData.mRays;
1586	}
1587
1588	if (mCirculatingAxis)
1589	{
1590	int parentAxis = 0;
1591	VspNode *parent = tData.mNode->GetParent();
1592
1593	if (parent)
1594	{
1595	parentAxis = static_cast<VspInterior *>(parent)->GetAxis();
1596	}
1597
1598	sAxis = (parentAxis + 1) % 3;
1599	}
1600	else if (mOnlyDrivingAxis)
1601	{
1602	sAxis = box.Size().DrivingAxis();
1603	}
1604
1605	for (int axis = 0; axis < 3; ++ axis)
1606	{
1607	if (!useSpecialAxis \|\| (axis == sAxis))
1608	{
1609	if (mUseCostHeuristics)
1610	{
1611	//-- place split plane using heuristics
1612	nCostRatio[axis] =
1613	EvalLocalCostHeuristics(tData,
1614	box,
1615	axis,
1616	nPosition[axis],
1617	*usedRays);
1618	}
1619	else
1620	{
1621	//-- split plane position is spatial median
1622	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1623	nCostRatio[axis] = EvalLocalSplitCost(tData,
1624	box,
1625	axis,
1626	nPosition[axis],
1627	nProbFront[axis],
1628	nProbBack[axis]);
1629	}
1630
1631	if (bestAxis == -1)
1632	{
1633	bestAxis = axis;
1634	}
1635	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1636	{
1637	bestAxis = axis;
1638	}
1639	}
1640	}
1641
1642	/////////////////////////
1643	//-- assign values of best split
1644
1645	plane.mAxis = bestAxis;
1646	// best split plane position
1647	plane.mPosition = nPosition[bestAxis];
1648
1649	pFront = nProbFront[bestAxis];
1650	pBack = nProbBack[bestAxis];
1651
1652	mSplitTimer.Exit();
1653
1654	return nCostRatio[bestAxis];
1655	}
1656
1657
1658	float VspTree::EvalRenderCostDecrease(VspSubdivisionCandidate &sc,
1659	float &normalizedOldRenderCost,
1660	const SplitData &sData) const
1661	{
1662	const float viewSpaceVol = mBoundingBox.GetVolume();
1663	const VspTraversalData &tData = sc.mParentData;
1664
1665	const AxisAlignedPlane &candidatePlane = sc.mSplitPlane;
1666	const float avgRaysPerObject = sc.GetAvgRaysPerObject();
1667
1668
1669	AxisAlignedBox3 frontBox;
1670	AxisAlignedBox3 backBox;
1671
1672	tData.mBoundingBox.Split(candidatePlane.mAxis,
1673	candidatePlane.mPosition,
1674	frontBox,
1675	backBox);
1676
1677	// probability that view point lies in back / front node
1678	float pOverall = tData.mProbability;
1679	float pFront = frontBox.GetVolume();
1680	float pBack = pOverall - pFront;
1681
1682
1683	///////////////////
1684	//-- evaluate render cost heuristics
1685
1686	// ratio of how render cost changed since last evaluation
1687	const float oldRenderCostRatio = (tData.mRenderCost > 0)? (sData.mTotalRenderCost / tData.mRenderCost) : 1;
1688	const float penaltyOld = tData.mCorrectedRenderCost * oldRenderCostRatio;
1689
1690	sc.mCorrectedFrontRenderCost = mHierarchyManager->EvalCorrectedPvs(sData.mFrontRenderCost, penaltyOld, avgRaysPerObject);
1691	sc.mCorrectedBackRenderCost = mHierarchyManager->EvalCorrectedPvs(sData.mBackRenderCost, penaltyOld, avgRaysPerObject);
1692
1693	sc.mFrontRenderCost = sData.mFrontRenderCost;
1694	sc.mBackRenderCost = sData.mBackRenderCost;
1695
1696	const float oldRenderCost = penaltyOld * pOverall;
1697	const float newRenderCost = sc.mCorrectedFrontRenderCost * pFront + sc.mCorrectedBackRenderCost * pBack;
1698
1699
1700	// the normalized old render cost is needed for the priority
1701	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1702
1703	// the render cost decrase for this split
1704	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1705
1706	#if GTP_DEBUG
1707	Debug << "old: " << normalizedOldRenderCost << " new: " << newRenderCost / viewSpaceVol
1708	<< " corr: " << tData.mCorrectedRenderCost << " ratio: " << oldRenderCostRatio << endl;
1709	#endif
1710
1711	return renderCostDecrease;
1712	}
1713
1714
1715	float VspTree::EvalLocalSplitCost(const VspTraversalData &tData,
1716	const AxisAlignedBox3 &box,
1717	const int axis,
1718	const float &position,
1719	float &pFront,
1720	float &pBack) const
1721	{
1722	float pvsTotal = 0;
1723	float pvsFront = 0;
1724	float pvsBack = 0;
1725
1726	// create unique ids for pvs heuristics
1727	Intersectable::NewMail(3);
1728	KdLeaf::NewMail(3);
1729
1730	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1731
1732	// this is the main ray classification loop!
1733	for(rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1734	{
1735	VssRay ray = (rit).mRay;
1736
1737	// determine the side of this ray with respect to the plane
1738	float t;
1739	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1740
1741	UpdateContributionsToPvs(*ray, true, side, pvsFront, pvsBack, pvsTotal);
1742	UpdateContributionsToPvs(*ray, false, side, pvsFront, pvsBack, pvsTotal);
1743	}
1744
1745	//////////////
1746	//-- evaluate cost heuristics
1747
1748	float pOverall = tData.mProbability;
1749
1750	// we use spatial mid split => simplified computation
1751	pBack = pFront = pOverall * 0.5f;
1752
1753	const float newCost = pvsBack * pBack + pvsFront * pFront;
1754	const float oldCost = (float)pvsTotal * pOverall + Limits::Small;
1755
1756	#ifdef GTPGTP_DEBUG
1757	Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1758	Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
1759	#endif
1760
1761	return (mCtDivCi + newCost) / oldCost;
1762	}
1763
1764
1765	void VspTree::UpdateContributionsToPvs(Intersectable *obj,
1766	const int cf,
1767	float &frontPvs,
1768	float &backPvs,
1769	float &totalPvs) const
1770	{
1771	if (!obj) return;
1772
1773	// object in none of the pvss => new object
1774	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1775	{
1776	totalPvs += 1.0f;
1777	}
1778
1779	// QUESTION matt: is it safe to assume that
1780	// the object belongs to no pvs in this case?
1781	//if (cf == Ray::COINCIDENT) return;
1782	if (cf >= 0) // front pvs
1783	{
1784	if (!obj->Mailed() && !obj->Mailed(2))
1785	{
1786	frontPvs += 1.0f;
1787
1788	// already in back pvs => in both pvss
1789	if (obj->Mailed(1))
1790	obj->Mail(2);
1791	else
1792	obj->Mail();
1793	}
1794	}
1795
1796	if (cf <= 0) // back pvs
1797	{
1798	if (!obj->Mailed(1) && !obj->Mailed(2))
1799	{
1800	backPvs += 1.0f;
1801
1802	// already in front pvs => in both pvss
1803	if (obj->Mailed())
1804	obj->Mail(2);
1805	else
1806	obj->Mail(1);
1807	}
1808	}
1809	}
1810
1811
1812	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1813	const int cf,
1814	float &frontPvs,
1815	float &backPvs,
1816	float &totalPvs,
1817	const bool countEntries) const
1818	{
1819	if (!leaf) return;
1820
1821	const float renderCost = countEntries ? 1 :
1822	(float)leaf->mObjects.size();
1823
1824	// leaf in no pvs => new
1825	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1826	{
1827	totalPvs += renderCost;
1828	}
1829
1830	if (cf >= 0) // front pvs
1831	{
1832	if (!leaf->Mailed() && !leaf->Mailed(2))
1833	{
1834	frontPvs += renderCost;
1835
1836	// already in back pvs => in both pvss
1837	if (leaf->Mailed(1))
1838	leaf->Mail(2);
1839	else
1840	leaf->Mail();
1841	}
1842	}
1843
1844	if (cf <= 0) // back pvs
1845	{
1846	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1847	{
1848	backPvs += renderCost;
1849
1850	// already in front pvs => in both pvss
1851	if (leaf->Mailed())
1852	leaf->Mail(2);
1853	else
1854	leaf->Mail(1);
1855	}
1856	}
1857	}
1858
1859
1860	void VspTree::UpdateContributionsToPvs(BvhLeaf *leaf,
1861	const int cf,
1862	SplitData &sData) const
1863	{
1864	const int triSize = (int)leaf->mObjects.size();
1865
1866	// object in no pvs => count as new
1867	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1868	{
1869	sData.mTotalTriangles += (int)triSize;
1870	++ sData.mTotalObjects;
1871	}
1872
1873	if (cf >= 0) // front pvs
1874	{
1875	if (!leaf->Mailed() && !leaf->Mailed(2))
1876	{
1877	sData.mFrontTriangles += triSize;
1878	++ sData.mFrontObjects;
1879
1880	// already in back pvs => in both pvss
1881	if (leaf->Mailed(1))
1882	leaf->Mail(2);
1883	else
1884	leaf->Mail();
1885	}
1886	}
1887
1888	if (cf <= 0) // back pvs
1889	{
1890	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1891	{
1892	sData.mBackTriangles += triSize;
1893	++ sData.mBackObjects;
1894
1895	// already in front pvs => in both pvss
1896	if (leaf->Mailed())
1897	leaf->Mail(2);
1898	else
1899	leaf->Mail(1);
1900	}
1901	}
1902	}
1903
1904
1905	void VspTree::UpdateContributionsToPvs(KdLeaf *leaf,
1906	const int cf,
1907	float &frontPvs,
1908	float &backPvs,
1909	float &totalPvs) const
1910	{
1911	if (!leaf) return;
1912
1913	// the objects which are referenced in this and only this leaf
1914	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1915
1916	// newly found leaf
1917	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1918	{
1919	totalPvs += contri;
1920	}
1921
1922	// recursivly update contributions of yet unclassified objects
1923	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1924
1925	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1926	{
1927	UpdateContributionsToPvs(*oit, cf, frontPvs, backPvs, totalPvs);
1928	}
1929
1930	if (cf >= 0) // front pvs
1931	{
1932	if (!leaf->Mailed() && !leaf->Mailed(2))
1933	{
1934	frontPvs += contri;
1935
1936	// already in back pvs => in both pvss
1937	if (leaf->Mailed(1))
1938	leaf->Mail(2);
1939	else
1940	leaf->Mail();
1941	}
1942	}
1943
1944	if (cf <= 0) // back pvs
1945	{
1946	if (!leaf->Mailed(1) && !leaf->Mailed(2))
1947	{
1948	backPvs += contri;
1949
1950	// already in front pvs => in both pvss
1951	if (leaf->Mailed())
1952	leaf->Mail(2);
1953	else
1954	leaf->Mail(1);
1955	}
1956	}
1957	}
1958
1959
1960	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1961	const bool onlyUnmailed,
1962	const int maxPvsSize) const
1963	{
1964	stack<VspNode *> nodeStack;
1965	nodeStack.push(mRoot);
1966
1967	while (!nodeStack.empty())
1968	{
1969	VspNode *node = nodeStack.top();
1970	nodeStack.pop();
1971
1972	if (node->IsLeaf())
1973	{
1974	// test if this leaf is in valid view space
1975	VspLeaf leaf = static_cast<VspLeaf >(node);
1976
1977	if (leaf->TreeValid() &&
1978	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1979	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().EvalPvsCost() <= maxPvsSize)))
1980	{
1981	leaves.push_back(leaf);
1982	}
1983	}
1984	else
1985	{
1986	VspInterior interior = static_cast<VspInterior >(node);
1987
1988	nodeStack.push(interior->GetBack());
1989	nodeStack.push(interior->GetFront());
1990	}
1991	}
1992	}
1993
1994
1995	AxisAlignedBox3 VspTree::GetBoundingBox() const
1996	{
1997	return mBoundingBox;
1998	}
1999
2000
2001	VspNode *VspTree::GetRoot() const
2002	{
2003	return mRoot;
2004	}
2005
2006
2007	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
2008	{
2009	// the node became a leaf -> evaluate stats for leafs
2010	VspLeaf leaf = static_cast<VspLeaf >(data.mNode);
2011
2012	if (data.mPvs > mVspStats.maxPvs)
2013	{
2014	mVspStats.maxPvs = (int)data.mPvs;
2015	}
2016
2017	mVspStats.pvs += (int)data.mPvs;
2018
2019	if (data.mDepth < mVspStats.minDepth)
2020	{
2021	mVspStats.minDepth = data.mDepth;
2022	}
2023
2024	if (data.mDepth >= mTermMaxDepth)
2025	{
2026	++ mVspStats.maxDepthNodes;
2027	}
2028
2029	// accumulate rays to compute rays / leaf
2030	mVspStats.rayRefs += (int)data.mRays->size();
2031
2032	if (data.mPvs < mTermMinPvs)
2033	++ mVspStats.minPvsNodes;
2034
2035	if ((int)data.mRays->size() < mTermMinRays)
2036	++ mVspStats.minRaysNodes;
2037
2038	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
2039	++ mVspStats.maxRayContribNodes;
2040
2041	if (data.mProbability <= mTermMinProbability)
2042	++ mVspStats.minProbabilityNodes;
2043
2044	// accumulate depth to compute average depth
2045	mVspStats.accumDepth += data.mDepth;
2046
2047	++ mCreatedViewCells;
2048
2049	#ifdef GTP_DEBUG
2050	Debug << "BSP stats: "
2051	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
2052	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
2053	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
2054	<< "#pvs: " << leaf->GetViewCell()->GetPvs().EvalPvsCost() << "), "
2055	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
2056	#endif
2057	}
2058
2059
2060	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
2061	{
2062	ViewCell::NewMail();
2063	CollectViewCells(mRoot, onlyValid, viewCells, true);
2064	}
2065
2066
2067	void VspTree::CollectRays(VssRayContainer &rays)
2068	{
2069	vector<VspLeaf *> leaves;
2070	CollectLeaves(leaves);
2071
2072	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
2073
2074	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2075	{
2076	VspLeaf leaf = lit;
2077	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2078
2079	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2080	rays.push_back(*rit);
2081	}
2082	}
2083
2084
2085	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
2086	{
2087	mViewCellsManager = vcm;
2088	}
2089
2090
2091	void VspTree::ValidateTree()
2092	{
2093	if (!mRoot)
2094	return;
2095
2096	mVspStats.invalidLeaves = 0;
2097	stack<VspNode *> nodeStack;
2098
2099	nodeStack.push(mRoot);
2100
2101	while (!nodeStack.empty())
2102	{
2103	VspNode *node = nodeStack.top();
2104	nodeStack.pop();
2105
2106	if (node->IsLeaf())
2107	{
2108	VspLeaf leaf = static_cast<VspLeaf >(node);
2109
2110	if (!leaf->GetViewCell()->GetValid())
2111	++ mVspStats.invalidLeaves;
2112
2113	// validity flags don't match => repair
2114	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2115	{
2116	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2117	PropagateUpValidity(leaf);
2118	}
2119	}
2120	else
2121	{
2122	VspInterior interior = static_cast<VspInterior >(node);
2123
2124	nodeStack.push(interior->GetFront());
2125	nodeStack.push(interior->GetBack());
2126	}
2127	}
2128
2129	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
2130	}
2131
2132
2133
2134	void VspTree::CollectViewCells(VspNode *root,
2135	bool onlyValid,
2136	ViewCellContainer &viewCells,
2137	bool onlyUnmailed) const
2138	{
2139	if (!root)
2140	return;
2141
2142	stack<VspNode *> nodeStack;
2143	nodeStack.push(root);
2144
2145	while (!nodeStack.empty())
2146	{
2147	VspNode *node = nodeStack.top();
2148	nodeStack.pop();
2149
2150	if (node->IsLeaf())
2151	{
2152	if (!onlyValid \|\| node->TreeValid())
2153	{
2154	ViewCellLeaf leafVc = static_cast<VspLeaf >(node)->GetViewCell();
2155
2156	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
2157
2158	if (!onlyUnmailed \|\| !viewCell->Mailed())
2159	{
2160	viewCell->Mail();
2161	viewCells.push_back(viewCell);
2162	}
2163	}
2164	}
2165	else
2166	{
2167	VspInterior interior = static_cast<VspInterior >(node);
2168
2169	nodeStack.push(interior->GetFront());
2170	nodeStack.push(interior->GetBack());
2171	}
2172	}
2173	}
2174
2175
2176	int VspTree::FindNeighbors(VspLeaf *n,
2177	vector<VspLeaf *> &neighbors,
2178	const bool onlyUnmailed) const
2179	{
2180	stack<VspNode *> nodeStack;
2181	nodeStack.push(mRoot);
2182
2183	const AxisAlignedBox3 box = GetBoundingBox(n);
2184
2185	while (!nodeStack.empty())
2186	{
2187	VspNode *node = nodeStack.top();
2188	nodeStack.pop();
2189
2190	if (node->IsLeaf())
2191	{
2192	VspLeaf leaf = static_cast<VspLeaf >(node);
2193
2194	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
2195	neighbors.push_back(leaf);
2196	}
2197	else
2198	{
2199	VspInterior interior = static_cast<VspInterior >(node);
2200
2201	if (interior->GetPosition() > box.Max(interior->GetAxis()))
2202	nodeStack.push(interior->GetBack());
2203	else
2204	{
2205	if (interior->GetPosition() < box.Min(interior->GetAxis()))
2206	nodeStack.push(interior->GetFront());
2207	else
2208	{
2209	// random decision
2210	nodeStack.push(interior->GetBack());
2211	nodeStack.push(interior->GetFront());
2212	}
2213	}
2214	}
2215	}
2216
2217	return (int)neighbors.size();
2218	}
2219
2220
2221	// Find random neighbor which was not mailed
2222	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2223	{
2224	stack<VspNode *> nodeStack;
2225	nodeStack.push(mRoot);
2226
2227	int mask = rand();
2228
2229	while (!nodeStack.empty())
2230	{
2231	VspNode *node = nodeStack.top();
2232
2233	nodeStack.pop();
2234
2235	if (node->IsLeaf())
2236	{
2237	return static_cast<VspLeaf *>(node);
2238	}
2239	else
2240	{
2241	VspInterior interior = static_cast<VspInterior >(node);
2242	VspNode *next;
2243
2244	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2245	{
2246	next = interior->GetFront();
2247	}
2248	else
2249	{
2250	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2251	{
2252	next = interior->GetBack();
2253	}
2254	else
2255	{
2256	// random decision
2257	if (mask & 1)
2258	next = interior->GetBack();
2259	else
2260	next = interior->GetFront();
2261	mask = mask >> 1;
2262	}
2263	}
2264
2265	nodeStack.push(next);
2266	}
2267	}
2268
2269	return NULL;
2270	}
2271
2272
2273	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2274	{
2275	stack<VspNode *> nodeStack;
2276
2277	nodeStack.push(mRoot);
2278
2279	int mask = rand();
2280
2281	while (!nodeStack.empty())
2282	{
2283	VspNode *node = nodeStack.top();
2284	nodeStack.pop();
2285
2286	if (node->IsLeaf())
2287	{
2288	if ( (!onlyUnmailed \|\| !node->Mailed()) )
2289	return static_cast<VspLeaf *>(node);
2290	}
2291	else
2292	{
2293	VspInterior interior = static_cast<VspInterior >(node);
2294
2295	// random decision
2296	if (mask & 1)
2297	nodeStack.push(interior->GetBack());
2298	else
2299	nodeStack.push(interior->GetFront());
2300
2301	mask = mask >> 1;
2302	}
2303	}
2304
2305	return NULL;
2306	}
2307
2308
2309	float VspTree::EvalPvsCost(const RayInfoContainer &rays) const
2310	{
2311	float pvsCost = 0;
2312
2313	Intersectable::NewMail();
2314	KdNode::NewMail();
2315
2316	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2317
2318	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2319	{
2320	VssRay ray = (rit).mRay;
2321
2322	pvsCost += EvalContributionToPvs(*ray, true);
2323
2324	#if COUNT_ORIGIN_OBJECTS
2325	pvsCost += EvalContributionToPvs(*ray, false);
2326	#endif
2327	}
2328
2329	return pvsCost;
2330	}
2331
2332
2333	int VspTree::EvalPvsEntriesContribution(const VssRay &ray,
2334	const bool isTermination) const
2335
2336	{
2337
2338	#if HACK_PERFORMANCE
2339	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
2340
2341	if (!obj) return 0;
2342	BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
2343
2344	if (!bvhleaf->Mailed())
2345	{
2346	bvhleaf->Mail();
2347	return 1;
2348	}
2349
2350	#else
2351
2352	Intersectable *obj;
2353	static Vector3 pt;
2354	KdNode *node;
2355
2356	ray.GetSampleData(isTermination, pt, &obj, &node);
2357
2358	if (!obj) return 0;
2359
2360	switch(mHierarchyManager->GetObjectSpaceSubdivisionType())
2361	{
2362	case HierarchyManager::NO_OBJ_SUBDIV:
2363	{
2364	if (!obj->Mailed())
2365	{
2366	obj->Mail();
2367	return 1;
2368	}
2369
2370	return 0;
2371	}
2372
2373	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
2374	{
2375	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
2376	if (!leaf->Mailed())
2377	{
2378	leaf->Mail();
2379	return 1;
2380	}
2381
2382	return 0;
2383	}
2384	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
2385	{
2386	BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
2387
2388	if (!bvhleaf->Mailed())
2389	{
2390	bvhleaf->Mail();
2391	return 1;
2392	}
2393
2394	return 0;
2395	}
2396	default:
2397	break;
2398	}
2399	#endif
2400	return 0;
2401	}
2402
2403
2404	int VspTree::EvalPvsEntriesSize(const RayInfoContainer &rays) const
2405	{
2406	int pvsSize = 0;
2407
2408	Intersectable::NewMail();
2409	KdNode::NewMail();
2410
2411	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2412
2413	for (rit = rays.begin(); rit != rays.end(); ++ rit)
2414	{
2415	VssRay ray = (rit).mRay;
2416
2417	pvsSize += EvalPvsEntriesContribution(*ray, true);
2418
2419	#if COUNT_ORIGIN_OBJECTS
2420	pvsSize += EvalPvsEntriesContribution(*ray, false);
2421	#endif
2422	}
2423
2424	return pvsSize;
2425	}
2426
2427
2428	float VspTree::GetEpsilon() const
2429	{
2430	return mEpsilon;
2431	}
2432
2433
2434	int VspTree::CastLineSegment(const Vector3 &origin,
2435	const Vector3 &termination,
2436	ViewCellContainer &viewcells,
2437	const bool useMailboxing)
2438	{
2439	int hits = 0;
2440
2441	float mint = 0.0f, maxt = 1.0f;
2442	const Vector3 dir = termination - origin;
2443
2444	stack<LineTraversalData> tStack;
2445
2446	Vector3 entp = origin;
2447	Vector3 extp = termination;
2448
2449	VspNode *node = mRoot;
2450	VspNode *farChild;
2451
2452	float position;
2453	int axis;
2454
2455	while (1)
2456	{
2457	if (!node->IsLeaf())
2458	{
2459	VspInterior in = static_cast<VspInterior >(node);
2460	position = in->GetPosition();
2461	axis = in->GetAxis();
2462
2463	if (entp[axis] <= position)
2464	{
2465	if (extp[axis] <= position)
2466	{
2467	node = in->GetBack();
2468	// cases N1,N2,N3,P5,Z2,Z3
2469	continue;
2470	}
2471	else
2472	{
2473	// case N4
2474	node = in->GetBack();
2475	farChild = in->GetFront();
2476	}
2477	}
2478	else
2479	{
2480	if (position <= extp[axis])
2481	{
2482	node = in->GetFront();
2483	// cases P1,P2,P3,N5,Z1
2484	continue;
2485	}
2486	else
2487	{
2488	node = in->GetFront();
2489	farChild = in->GetBack();
2490	// case P4
2491	}
2492	}
2493
2494	// $$ modification 3.5.2004 - hints from Kamil Ghais
2495	// case N4 or P4
2496	const float tdist = (position - origin[axis]) / dir[axis];
2497	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2498
2499	// new exit point for near child
2500	extp = origin + dir * tdist;
2501	maxt = tdist;
2502	}
2503	else
2504	{
2505	// compute intersection with all objects in this leaf
2506	VspLeaf leaf = static_cast<VspLeaf >(node);
2507	ViewCell *viewCell;
2508
2509	if (0)
2510	viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2511	else
2512	viewCell = leaf->GetViewCell();
2513
2514	// don't have to mail if each view cell belongs to exactly one leaf
2515	if (!useMailboxing \|\| !viewCell->Mailed())
2516	{
2517	if (useMailboxing)
2518	viewCell->Mail();
2519
2520	viewcells.push_back(viewCell);
2521	++ hits;
2522	}
2523
2524	// get the next node from the stack
2525	if (tStack.empty())
2526	break;
2527
2528	// set new entry point for far child
2529	entp = extp;
2530	mint = maxt;
2531
2532	LineTraversalData &s = tStack.top();
2533	node = s.mNode;
2534	extp = s.mExitPoint;
2535	maxt = s.mMaxT;
2536
2537	tStack.pop();
2538	}
2539	}
2540
2541	return hits;
2542	}
2543
2544
2545	int VspTree::TraverseRayPacket(RayPacket &rp, const bool useMailboxing)
2546	{
2547	#ifdef USE_SSE
2548	int hits = 0;
2549
2550	// reciprocal of ray directions
2551	float one = 1.0f;
2552	float zero = 0.0f;
2553
2554	__m128 one4 = _mm_load1_ps(&one);
2555	__m128 zero4 = _mm_load1_ps(&zero);
2556
2557	union { __m128 mask4; float mask[4];};
2558	union { __m128 mask4_2; float mask_2[4];};
2559
2560	mask4 = one4;
2561
2562	__declspec(align(16)) __m128 entp4[] = {rp.mOriginX4, rp.mOriginY4, rp.mOriginZ4};
2563	__declspec(align(16)) __m128 extp4[] = {rp.mTerminationX4, rp.mTerminationY4, rp.mTerminationZ4};
2564
2565	__m128 *origin = &rp.mOriginX4;
2566	__m128 *termination = &rp.mTerminationX4;
2567
2568	// ray directions
2569	__m128 dirX4 = _mm_sub_ps(rp.mTerminationX4, rp.mOriginX4);
2570	__m128 dirY4 = _mm_sub_ps(rp.mTerminationY4, rp.mOriginY4);;
2571	__m128 dirZ4 = _mm_sub_ps(rp.mTerminationZ4, rp.mOriginZ4);;
2572
2573	__m128 rdx4 = _mm_div_ps(one4, dirX4);
2574	__m128 rdy4 = _mm_div_ps(one4, dirY4);
2575	__m128 rdz4 = _mm_div_ps(one4, dirZ4);
2576
2577	__m128 maxT4 = one4;
2578	__m128 minT4 = zero4;
2579
2580	PacketTraversalStack tStack(1000);
2581
2582	VspNode *node = mRoot;
2583	VspNode *farChild;
2584
2585	float position;
2586	int axis;
2587
2588	__m128 position4;
2589
2590	while (1)
2591	{
2592	if (!node->IsLeaf())
2593	{
2594	VspInterior in = static_cast<VspInterior >(node);
2595
2596	position = in->GetPosition();
2597	axis = in->GetAxis();
2598
2599	position4 = _mm_load1_ps(&position);
2600
2601	// are the entry points all in near leaf?
2602	if (_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(entp4[axis], position4), mask4)))
2603	{
2604	// are the exit points all in near leaf?
2605	if (_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(extp4[axis], position4), mask4)))
2606	{
2607	node = in->GetBack();
2608	// cases N1,N2,N3,P5,Z2,Z3
2609	continue;
2610	}
2611	else // traverse both children
2612	{
2613	// case N4
2614	node = in->GetBack();
2615	farChild = in->GetFront();
2616	}
2617	}
2618	else
2619	{
2620	if (_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(position4, entp4[axis]), mask4)) &&
2621	_mm_movemask_ps(_mm_and_ps(_mm_cmple_ps(position4, extp4[axis]), mask4)))
2622	{
2623	node = in->GetFront();
2624	// cases P1,P2,P3,N5,Z1
2625	continue;
2626	}
2627	else // traverse both children
2628	{
2629	node = in->GetFront();
2630	farChild = in->GetBack();
2631	// case P4
2632	}
2633	}
2634
2635	// $$ modification 3.5.2004 - hints from Kamil Ghais
2636	// case N4 or P4
2637	const __m128 tDist4 = _mm_mul_ps(_mm_sub_ps(position4, origin[axis]), termination[axis]);
2638
2639	mask4 = _mm_and_ps(_mm_cmplt_ps(tDist4, minT4), mask4);
2640	mask4_2 = _mm_and_ps(_mm_cmpgt_ps(tDist4, minT4), mask4);
2641
2642	// push far child for further processing
2643	tStack.Push(PacketTraversalData(farChild, extp4[0], extp4[1], extp4[2], maxT4, mask4_2));
2644
2645	// compute new exit point
2646	extp4[0] = _mm_add_ps(_mm_mul_ps(dirX4, tDist4), rp.mOriginX4);
2647	extp4[1] = _mm_add_ps(_mm_mul_ps(dirY4, tDist4), rp.mOriginY4);
2648	extp4[2] = _mm_add_ps(_mm_mul_ps(dirZ4, tDist4), rp.mOriginZ4);
2649
2650	maxT4 = tDist4;
2651	}
2652	else
2653	{
2654	// compute intersection with all objects in this leaf
2655	VspLeaf leaf = static_cast<VspLeaf >(node);
2656	ViewCell *viewCell;
2657
2658	viewCell = leaf->GetViewCell();
2659
2660	// note: don't have to mail if each view
2661	// cell belongs to exactly one leaf
2662	if (!useMailboxing \|\| !viewCell->Mailed())
2663	{
2664	if (useMailboxing)
2665	viewCell->Mail();
2666
2667	for (int i = 0; i < 4; ++i)
2668	{
2669	// push view cells for all valid rays
2670	if (mask[i])
2671	rp.mViewCells[i].push_back(viewCell);
2672	}
2673
2674	++ hits;
2675	}
2676
2677	// get the next node from the stack
2678	if (tStack.Empty())
2679	break;
2680
2681	// use memcopy?
2682	entp4[0] = extp4[0];
2683	entp4[1] = extp4[1];
2684	entp4[2] = extp4[2];
2685
2686	minT4 = maxT4;
2687
2688	const PacketTraversalData &s = tStack.Top();
2689	node = s.mNode;
2690
2691	extp4[0] = s.mExitPointX4;
2692	extp4[1] = s.mExitPointY4;
2693	extp4[2] = s.mExitPointZ4;
2694
2695	maxT4 = s.mMaxT4;
2696	mask4 = s.mMask4;
2697
2698	tStack.Pop();
2699	}
2700	}
2701
2702	return hits;
2703
2704	#else
2705
2706	return 0;
2707	#endif
2708	}
2709
2710
2711	int VspTree::CastRay(Ray &ray)
2712	{
2713	int hits = 0;
2714
2715	stack<LineTraversalData> tStack;
2716	const Vector3 dir = ray.GetDir();
2717
2718	float maxt, mint;
2719
2720	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2721	return 0;
2722
2723	Intersectable::NewMail();
2724	ViewCell::NewMail();
2725
2726	Vector3 entp = ray.Extrap(mint);
2727	Vector3 extp = ray.Extrap(maxt);
2728
2729	const Vector3 origin = entp;
2730
2731	VspNode *node = mRoot;
2732	VspNode *farChild = NULL;
2733
2734	float position;
2735	int axis;
2736
2737	while (1)
2738	{
2739	if (!node->IsLeaf())
2740	{
2741	VspInterior in = static_cast<VspInterior >(node);
2742	position = in->GetPosition();
2743	axis = in->GetAxis();
2744
2745	if (entp[axis] <= position)
2746	{
2747	if (extp[axis] <= position)
2748	{
2749	node = in->GetBack();
2750	// cases N1,N2,N3,P5,Z2,Z3
2751	continue;
2752	}
2753	else
2754	{
2755	// case N4
2756	node = in->GetBack();
2757	farChild = in->GetFront();
2758	}
2759	}
2760	else
2761	{
2762	if (position <= extp[axis])
2763	{
2764	node = in->GetFront();
2765	// cases P1,P2,P3,N5,Z1
2766	continue;
2767	}
2768	else
2769	{
2770	node = in->GetFront();
2771	farChild = in->GetBack();
2772	// case P4
2773	}
2774	}
2775
2776	// $$ modification 3.5.2004 - hints from Kamil Ghais
2777	// case N4 or P4
2778	const float tdist = (position - origin[axis]) / dir[axis];
2779	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2780	extp = origin + dir * tdist;
2781	maxt = tdist;
2782	}
2783	else
2784	{
2785	// compute intersection with all objects in this leaf
2786	VspLeaf leaf = static_cast<VspLeaf >(node);
2787	ViewCell *vc = leaf->GetViewCell();
2788
2789	if (!vc->Mailed())
2790	{
2791	vc->Mail();
2792	// todo: add view cells to ray
2793	++ hits;
2794	}
2795
2796	// get the next node from the stack
2797	if (tStack.empty())
2798	break;
2799
2800	entp = extp;
2801	mint = maxt;
2802
2803	LineTraversalData &s = tStack.top();
2804	node = s.mNode;
2805	extp = s.mExitPoint;
2806	maxt = s.mMaxT;
2807	tStack.pop();
2808	}
2809	}
2810
2811	return hits;
2812	}
2813
2814
2815	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2816	{
2817	if (!mRoot)
2818	return NULL;
2819
2820	stack<VspNode *> nodeStack;
2821	nodeStack.push(mRoot);
2822
2823	ViewCellLeaf *viewcell = NULL;
2824
2825	while (!nodeStack.empty())
2826	{
2827	VspNode *node = nodeStack.top();
2828	nodeStack.pop();
2829
2830	if (node->IsLeaf())
2831	{
2832	const AxisAlignedBox3 box = GetBoundingBox(static_cast<VspLeaf *>(node));
2833
2834	if (!box.IsInside(point))
2835	Debug << "error, point " << point << " should be in view cell " << box << endl;
2836
2837	viewcell = static_cast<VspLeaf *>(node)->GetViewCell();
2838	break;
2839	}
2840	else
2841	{
2842	VspInterior interior = static_cast<VspInterior >(node);
2843
2844	// random decision
2845	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2846	{
2847	nodeStack.push(interior->GetFront());
2848	}
2849	else
2850	{
2851	nodeStack.push(interior->GetBack());
2852	}
2853	}
2854	}
2855
2856	// return active or leaf view cell
2857	if (active)
2858	{
2859	return mViewCellsTree->GetActiveViewCell(viewcell);
2860	}
2861	else
2862	{
2863	return viewcell;
2864	}
2865	}
2866
2867
2868	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2869	{
2870	VspNode *node = mRoot;
2871
2872	while (1)
2873	{
2874	// early exit
2875	if (node->TreeValid())
2876	return true;
2877
2878	if (node->IsLeaf())
2879	return false;
2880
2881	VspInterior in = static_cast<VspInterior >(node);
2882
2883	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2884	{
2885	node = in->GetBack();
2886	}
2887	else
2888	{
2889	node = in->GetFront();
2890	}
2891	}
2892
2893	// should never come here
2894	return false;
2895	}
2896
2897
2898	void VspTree::PropagateUpValidity(VspNode *node)
2899	{
2900	const bool isValid = node->TreeValid();
2901
2902	// propagative up invalid flag until only invalid nodes exist over this node
2903	if (!isValid)
2904	{
2905	while (!node->IsRoot() && node->GetParent()->TreeValid())
2906	{
2907	node = node->GetParent();
2908	node->SetTreeValid(false);
2909	}
2910	}
2911	else
2912	{
2913	// propagative up valid flag until one of the subtrees is invalid
2914	while (!node->IsRoot() && !node->TreeValid())
2915	{
2916	node = node->GetParent();
2917	VspInterior interior = static_cast<VspInterior >(node);
2918
2919	// the parent is valid iff both leaves are valid
2920	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2921	interior->GetFront()->TreeValid());
2922	}
2923	}
2924	}
2925
2926
2927	bool VspTree::Export(OUT_STREAM &stream)
2928	{
2929	ExportNode(mRoot, stream);
2930
2931	return true;
2932	}
2933
2934
2935	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2936	{
2937	if (node->IsLeaf())
2938	{
2939	VspLeaf leaf = static_cast<VspLeaf >(node);
2940	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2941
2942	int id = -1;
2943	if (viewCell != mOutOfBoundsCell)
2944	id = viewCell->GetId();
2945
2946	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2947	}
2948	else
2949	{
2950	VspInterior interior = static_cast<VspInterior >(node);
2951
2952	AxisAlignedPlane plane = interior->GetPlane();
2953	stream << "<Interior plane=\"" << plane.mPosition << " "
2954	<< plane.mAxis << "\">" << endl;
2955
2956	ExportNode(interior->GetBack(), stream);
2957	ExportNode(interior->GetFront(), stream);
2958
2959	stream << "</Interior>" << endl;
2960	}
2961	}
2962
2963
2964	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2965	RayInfoContainer &rays,
2966	RayInfoContainer &frontRays,
2967	RayInfoContainer &backRays) const
2968	{
2969	int splits = 0;
2970
2971	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2972
2973	for (rit = rays.begin(); rit != rit_end; ++ rit)
2974	{
2975	RayInfo bRay = *rit;
2976
2977	VssRay *ray = bRay.mRay;
2978	float t;
2979
2980	// get classification and receive new t
2981	// test if start point behind or in front of plane
2982	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2983
2984	if (side == 0)
2985	{
2986	++ splits;
2987
2988	if (ray->HasPosDir(plane.mAxis))
2989	{
2990	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2991	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2992	}
2993	else
2994	{
2995	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2996	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2997	}
2998	}
2999	else if (side == 1)
3000	{
3001	frontRays.push_back(bRay);
3002	}
3003	else
3004	{
3005	backRays.push_back(bRay);
3006	}
3007	}
3008
3009	return splits;
3010	}
3011
3012
3013	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
3014	{
3015	if (!node->GetParent())
3016	return mBoundingBox;
3017
3018	if (!node->IsLeaf())
3019	{
3020	return (static_cast<VspInterior *>(node))->GetBoundingBox();
3021	}
3022
3023	VspInterior parent = static_cast<VspInterior >(node->GetParent());
3024
3025	AxisAlignedBox3 box(parent->GetBoundingBox());
3026
3027	if (parent->GetFront() == node)
3028	box.SetMin(parent->GetAxis(), parent->GetPosition());
3029	else
3030	box.SetMax(parent->GetAxis(), parent->GetPosition());
3031
3032	return box;
3033	}
3034
3035
3036	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
3037	ViewCellContainer &viewCells) const
3038	{
3039	stack<VspNode *> nodeStack;
3040
3041	ViewCell::NewMail();
3042
3043	nodeStack.push(mRoot);
3044
3045	while (!nodeStack.empty())
3046	{
3047	VspNode *node = nodeStack.top();
3048	nodeStack.pop();
3049
3050	const AxisAlignedBox3 bbox = GetBoundingBox(node);
3051
3052	if (Overlap(bbox, box))
3053	{
3054	if (node->IsLeaf())
3055	{
3056	VspLeaf leaf = static_cast<VspLeaf >(node);
3057
3058	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
3059	{
3060	leaf->GetViewCell()->Mail();
3061	viewCells.push_back(leaf->GetViewCell());
3062	}
3063	}
3064	else
3065	{
3066	VspInterior interior = static_cast<VspInterior >(node);
3067
3068	VspNode *first = interior->GetFront();
3069	VspNode *second = interior->GetBack();
3070
3071	nodeStack.push(first);
3072	nodeStack.push(second);
3073	}
3074	}
3075	// default: cull
3076	}
3077
3078	return (int)viewCells.size();
3079	}
3080
3081
3082	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
3083	RayInfoContainer &rays)
3084	{
3085	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
3086
3087	long startTime = GetTime();
3088
3089	cout << "storing rays ... ";
3090
3091	Intersectable::NewMail();
3092
3093	////////////////
3094	//-- store rays and objects
3095
3096	VssRay *lastVssRay = NULL;
3097
3098	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
3099	{
3100	VssRay ray = rit;
3101
3102	// filter out double rays (last ray the same as this ray
3103	if (
3104	!lastVssRay \|\|
3105	!(ray->mOrigin == lastVssRay->mTermination) \|\|
3106	!(ray->mTermination == lastVssRay->mOrigin))
3107	{
3108	lastVssRay = ray;
3109
3110	float minT, maxT;
3111	static Ray hray;
3112
3113	hray.Init(*ray);
3114
3115	// TODO: not very efficient to implictly cast between rays types
3116	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
3117	{
3118	const float len = ray->Length();
3119
3120	if (len) // ray not degenerate
3121	{ //len = Limits::Small;
3122	rays.push_back(RayInfo(ray, minT / len, maxT / len));
3123	}
3124	}
3125	}
3126	else
3127	{
3128	//cout << "r";
3129	// store object only for one ray
3130	//lastVssRay->mOriginObject = ray->mTerminationObject;
3131	}
3132	}
3133
3134	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3135	}
3136
3137
3138	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
3139	{
3140	mViewCellsTimer.Entry();
3141
3142	static Ray hray;
3143	hray.Init(ray);
3144
3145	float tmin = 0, tmax = 1.0;
3146
3147	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
3148	return;
3149
3150	const Vector3 origin = hray.Extrap(tmin);
3151	const Vector3 termination = hray.Extrap(tmax);
3152
3153	// view cells were not precomputed and are extracted on the fly
3154	// don't mail because the same view cells can be found for different rays
3155	CastLineSegment(origin, termination, viewCells, false);
3156
3157	mViewCellsTimer.Exit();
3158	}
3159
3160
3161	void VspTree::Initialise(const VssRayContainer &rays,
3162	AxisAlignedBox3 *forcedBoundingBox,
3163	const ObjectContainer &objects)
3164	{
3165	ComputeBoundingBox(rays, forcedBoundingBox);
3166
3167	VspLeaf *leaf = new VspLeaf();
3168	mRoot = leaf;
3169
3170	VspViewCell *viewCell = new VspViewCell();
3171	leaf->SetViewCell(viewCell);
3172
3173	viewCell->SetTrianglesInPvs((float)objects.size());
3174	viewCell->SetEntriesInPvs(1);
3175
3176	// set view cell values
3177	viewCell->mLeaves.push_back(leaf);
3178	viewCell->SetVolume(mBoundingBox.GetVolume());
3179
3180	leaf->mProbability = mBoundingBox.GetVolume();
3181	}
3182
3183
3184	void VspTree::PrepareConstruction(SplitQueue &tQueue,
3185	const VssRayContainer &sampleRays,
3186	RayInfoContainer &rays)
3187	{
3188	mVspStats.Reset();
3189	mVspStats.Start();
3190	mVspStats.nodes = 1;
3191
3192	// store pointer to this tree
3193	VspSubdivisionCandidate::sVspTree = this;
3194
3195	mBvHierarchy = mHierarchyManager->mBvHierarchy;
3196
3197	// initialise termination criteria
3198	mTermMinProbability *= mBoundingBox.GetVolume();
3199
3200	// get clipped rays
3201	PreprocessRays(sampleRays, rays);
3202
3203	/// collect pvs from rays
3204	const float pvsCost = EvalPvsCost(rays);
3205
3206	// root and bounding box were already constructed
3207	VspLeaf leaf = static_cast<VspLeaf >(mRoot);
3208
3209	//////////
3210	//-- prepare view space partition
3211
3212	const float prop = mBoundingBox.GetVolume();
3213
3214	// first vsp traversal data
3215	VspTraversalData vData(leaf, 0, &rays, pvsCost, prop, mBoundingBox);
3216
3217	mTotalCost = vData.mCorrectedRenderCost = vData.mRenderCost = pvsCost;
3218	mPvsEntries = EvalPvsEntriesSize(rays);
3219	vData.mCorrectedPvs = vData.mPvs = (float)mPvsEntries;
3220
3221	//////////////
3222	//-- create the first split candidate
3223
3224	VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
3225	EvalSubdivisionCandidate(*splitCandidate);
3226	leaf->SetSubdivisionCandidate(splitCandidate);
3227
3228	EvalSubdivisionStats(*splitCandidate);
3229
3230	tQueue.Push(splitCandidate);
3231	}
3232
3233
3234	void VspTree::AddCandidateToDirtyList(const VssRay &ray,
3235	const bool isTermination,
3236	vector<SubdivisionCandidate *> &dirtyList,
3237	const bool onlyUnmailed) const
3238
3239	{
3240	#if HACK_PERFORMANCE
3241	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3242
3243	if (!obj) return;
3244
3245	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3246	SubdivisionCandidate *candidate;
3247
3248	if (!leaf->Mailed())
3249	{
3250	leaf->Mail();
3251	candidate = leaf->GetSubdivisionCandidate();
3252	}
3253	else
3254	{
3255	candidate = NULL;
3256	}
3257	#else
3258	SubdivisionCandidate *candidate = NULL;
3259
3260	Intersectable *obj;
3261	Vector3 pt;
3262	KdNode *node;
3263
3264	ray.GetSampleData(isTermination, pt, &obj, &node);
3265
3266	if (!obj) return;
3267
3268	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3269	{
3270	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3271	{
3272	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3273
3274	if (!leaf->Mailed())
3275	{
3276	leaf->Mail();
3277	candidate = leaf->mSubdivisionCandidate;
3278	}
3279	break;
3280	}
3281	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3282	{
3283	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3284
3285	if (!leaf->Mailed())
3286	{
3287	leaf->Mail();
3288	candidate = leaf->GetSubdivisionCandidate();
3289	}
3290	break;
3291	}
3292	default:
3293	cerr << "collectdirtycandidates not implemented yet" << endl;
3294	candidate = NULL;
3295	break;
3296	}
3297	#endif
3298
3299	// is this leaf still a split candidate?
3300	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
3301	{
3302	candidate->Mail();
3303	candidate->SetDirty(true);
3304	dirtyList.push_back(candidate);
3305	}
3306	}
3307
3308
3309	void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
3310	vector<SubdivisionCandidate *> &dirtyList,
3311	const bool onlyUnmailed)
3312	{
3313	VspTraversalData &tData = sc->mParentData;
3314	VspLeaf *node = tData.mNode;
3315
3316	KdLeaf::NewMail();
3317	Intersectable::NewMail();
3318
3319	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
3320
3321	// add all nodes seen by the rays
3322	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
3323	{
3324	VssRay ray = (rit).mRay;
3325
3326	AddCandidateToDirtyList(*ray, true, dirtyList, onlyUnmailed);
3327
3328	#if COUNT_ORIGIN_OBJECTS
3329	AddCandidateToDirtyList(*ray, false, dirtyList, onlyUnmailed);
3330	#endif
3331	}
3332	}
3333
3334
3335	float VspTree::EvalMaxEventContribution(const VssRay &ray,
3336	const bool isTermination) const
3337	{
3338	#if HACK_PERFORMANCE
3339
3340	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3341
3342	if (!obj) return 0.0f;
3343
3344	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3345
3346	// simple render cost evaluation
3347	if (-- leaf->mCounter == 0)
3348	return (float)leaf->mObjects.size();
3349	else
3350	return 0.0f;
3351	#else
3352
3353	Intersectable *obj;
3354	Vector3 pt;
3355	KdNode *node;
3356
3357	ray.GetSampleData(isTermination, pt, &obj, &node);
3358
3359	if (!obj) return 0.0f;
3360
3361	float pvs = 0.0f;
3362
3363	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3364	{
3365	case HierarchyManager::NO_OBJ_SUBDIV:
3366	{
3367	if (-- obj->mCounter == 0)
3368	++ pvs;
3369	break;
3370	}
3371	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3372	{
3373	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3374
3375	// add contributions of the kd nodes
3376	pvs += EvalMaxEventContribution(leaf);
3377	break;
3378	}
3379	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3380	{
3381	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3382
3383	// simple render cost evaluation
3384	if (-- leaf->mCounter == 0)
3385	pvs += BvHierarchy::EvalAbsCost(leaf->mObjects);
3386
3387	break;
3388	}
3389	default:
3390	break;
3391	}
3392	return pvs;
3393
3394	#endif
3395	}
3396
3397
3398	float VspTree::PrepareHeuristics(const VssRay &ray, const bool isTermination)
3399	{
3400
3401	#if HACK_PERFORMANCE
3402
3403	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3404
3405	if (!obj) return 0.0f;
3406
3407	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3408
3409	if (!leaf->Mailed())
3410	{
3411	leaf->Mail();
3412	leaf->mCounter = 1;
3413	return (float)leaf->mObjects.size();
3414	}
3415	else
3416	{
3417	++ leaf->mCounter;
3418	return 0.0f;
3419	}
3420
3421	#else
3422
3423	float pvsSize = 0;
3424
3425	Intersectable *obj;
3426	Vector3 pt;
3427	KdNode *node;
3428
3429	ray.GetSampleData(isTermination, pt, &obj, &node);
3430
3431	if (!obj) return 0.0f;
3432
3433	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3434	{
3435	case HierarchyManager::NO_OBJ_SUBDIV:
3436	{
3437	if (!obj->Mailed())
3438	{
3439	obj->Mail();
3440	obj->mCounter = 0;
3441	++ pvsSize;
3442	}
3443
3444	++ obj->mCounter;
3445	break;
3446	}
3447	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3448	{
3449	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3450	pvsSize += PrepareHeuristics(leaf);
3451	break;
3452	}
3453	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3454	{
3455	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3456
3457	if (!leaf->Mailed())
3458	{
3459	leaf->Mail();
3460	leaf->mCounter = 0;
3461	pvsSize += BvHierarchy::EvalAbsCost(leaf->mObjects);
3462	}
3463
3464	++ leaf->mCounter;
3465	break;
3466	}
3467	default:
3468	break;
3469	}
3470	return pvsSize;
3471	#endif
3472	}
3473
3474
3475	float VspTree::EvalMinEventContribution(const VssRay &ray,
3476	const bool isTermination) const
3477	{
3478	#if HACK_PERFORMANCE
3479
3480	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3481
3482	if (!obj) return 0.0f;
3483
3484	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3485
3486	if (!leaf->Mailed())
3487	{
3488	leaf->Mail();
3489	return (float)leaf->mObjects.size();
3490	}
3491	else
3492	{
3493	return 0.0f;
3494	}
3495	#else
3496
3497	Intersectable *obj;
3498	static Vector3 pt;
3499	KdNode *node;
3500
3501	ray.GetSampleData(isTermination, pt, &obj, &node);
3502
3503	if (!obj) return 0;
3504
3505	float pvs = 0.0f;
3506
3507	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3508	{
3509	case HierarchyManager::NO_OBJ_SUBDIV:
3510	{
3511	if (!obj->Mailed())
3512	{
3513	obj->Mail();
3514	++ pvs;
3515	}
3516	break;
3517	}
3518	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3519	{
3520	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3521	// add contributions of the kd nodes
3522	pvs += EvalMinEventContribution(leaf);
3523	break;
3524	}
3525	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3526	{
3527	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3528	if (!leaf->Mailed())
3529	{
3530	leaf->Mail();
3531	pvs += BvHierarchy->EvalAbsCost(leaf->mObjects);
3532	}
3533	break;
3534	}
3535	default:
3536	break;
3537	}
3538	return pvs;
3539
3540	#endif
3541	}
3542
3543
3544	void VspTree::UpdateContributionsToPvs(const VssRay &ray,
3545	const bool isTermination,
3546	const int cf,
3547	float &frontPvs,
3548	float &backPvs,
3549	float &totalPvs) const
3550	{
3551	#if HACK_PERFORMANCE
3552
3553	BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
3554	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs, false);
3555
3556	#else
3557
3558	Intersectable *obj;
3559	static Vector3 pt;
3560	KdNode *node;
3561
3562	ray.GetSampleData(isTermination, pt, &obj, &node);
3563
3564	if (!obj) return;
3565
3566	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3567	{
3568	case HierarchyManager::NO_OBJ_SUBDIV:
3569	{
3570	// find front and back pvs for origing and termination object
3571	UpdateContributionsToPvs(obj, cf, frontPvs, backPvs, totalPvs);
3572	break;
3573	}
3574	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3575	{
3576	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3577	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs);
3578	break;
3579	}
3580	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3581	{
3582	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3583	UpdateContributionsToPvs(leaf, cf, frontPvs, backPvs, totalPvs, false);
3584	break;
3585	}
3586	}
3587	#endif
3588	}
3589
3590
3591	void VspTree::UpdatePvsEntriesContribution(const VssRay &ray,
3592	const bool isTermination,
3593	const int cf,
3594	float &pvsFront,
3595	float &pvsBack,
3596	float &totalPvs) const
3597	{
3598	#if HACK_PERFORMANCE
3599
3600	BvhLeaf *leaf = mBvHierarchy->GetLeaf(ray.mTerminationObject);
3601	UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
3602
3603	#else
3604
3605	Intersectable *obj;
3606	static Vector3 pt;
3607	KdNode *node;
3608
3609	ray.GetSampleData(isTermination, pt, &obj, &node);
3610	if (!obj) return;
3611
3612	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3613	{
3614	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3615	// TODO
3616	break;
3617	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3618	{
3619	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3620	UpdateContributionsToPvs(leaf, cf, pvsFront, pvsBack, totalPvs, true);
3621	break;
3622	}
3623	default:
3624	{
3625	UpdateContributionsToPvs(obj, cf, pvsFront, pvsBack, totalPvs);
3626	break;
3627	}
3628	}
3629	#endif
3630	}
3631
3632
3633	float VspTree::EvalContributionToPvs(const VssRay &ray, const bool isTermination) const
3634	{
3635
3636	#if HACK_PERFORMANCE
3637
3638	Intersectable *obj = isTermination ? ray.mTerminationObject : ray.mOriginObject;
3639
3640	if (!obj) return 0;
3641
3642	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
3643
3644	if (!leaf->Mailed())
3645	{
3646	leaf->Mail();
3647	return (float)leaf->mObjects.size();
3648	}
3649	else
3650	{
3651	return 0.0f;
3652	}
3653
3654	#else
3655
3656	Intersectable *obj;
3657	static Vector3 pt;
3658	KdNode *node;
3659
3660	ray.GetSampleData(isTermination, pt, &obj, &node);
3661
3662	if (!obj) return 0;
3663
3664	float pvs = 0.0f;
3665
3666	switch (mHierarchyManager->GetObjectSpaceSubdivisionType())
3667	{
3668	case HierarchyManager::NO_OBJ_SUBDIV:
3669	{
3670	if (!obj->Mailed())
3671	{
3672	obj->Mail();
3673	++ pvs;
3674	}
3675	break;
3676	}
3677	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
3678	{
3679	KdLeaf *leaf = mHierarchyManager->mOspTree->GetLeaf(pt, node);
3680	pvs += EvalContributionToPvs(leaf);
3681	break;
3682	}
3683	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
3684	{
3685	BvhLeaf *bvhleaf = mBvHierarchy->GetLeaf(obj);
3686
3687	if (!bvhleaf->Mailed())
3688	{
3689	bvhleaf->Mail();
3690	pvs += BvHierarchy::EvalAbsCost(bvhleaf->mObjects);
3691	}
3692	break;
3693	}
3694	default:
3695	break;
3696	}
3697	return pvs;
3698
3699	#endif
3700	}
3701
3702
3703	float VspTree::EvalContributionToPvs(KdLeaf *leaf) const
3704	{
3705	if (leaf->Mailed()) // leaf already mailed
3706	return 0;
3707
3708	leaf->Mail();
3709
3710	// this is the pvs which is uniquely part of this kd leaf
3711	float pvs = (float)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
3712
3713	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
3714
3715	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
3716	{
3717	Intersectable obj = oit;
3718	if (!obj->Mailed())
3719	{
3720	obj->Mail();
3721	++ pvs;
3722	}
3723	}
3724
3725	return pvs;
3726	}
3727
3728
3729	int VspTree::CompressObjects(VspLeaf *leaf)
3730	{
3731	bool compressed = true;
3732
3733	while (compressed)
3734	{
3735	BvhNode::NewMail(2);
3736
3737	ObjectPvsIterator oit = leaf->GetViewCell()->GetPvs().GetIterator();
3738	vector<BvhNode *> parents;
3739	ObjectPvs newPvs;
3740
3741	compressed = false;
3742
3743	while (oit.HasMoreEntries())
3744	{
3745	BvhNode obj = static_cast<BvhNode >(oit.Next());
3746
3747	if (!obj->IsRoot())
3748	{
3749	BvhNode *parent = obj->GetParent();
3750
3751	if (!parent->Mailed())
3752	{
3753	if (parent->Mailed(1))
3754	cout << "error!!" << endl;
3755	parent->Mail();
3756	}
3757	else
3758	{
3759	// sibling was already found =>
3760	// this entry can be exchanged by the parent
3761	parents.push_back(parent);
3762	parent->Mail(1);
3763
3764	compressed = true;
3765	}
3766	}
3767	}
3768
3769	PvsData pvsData;
3770	oit = leaf->GetViewCell()->GetPvs().GetIterator();
3771
3772	while (oit.HasMoreEntries())
3773	{
3774	BvhNode obj = static_cast<BvhNode >(oit.Next(pvsData));
3775
3776	if (!obj->IsRoot())
3777	{
3778	BvhNode *parent = obj->GetParent();
3779
3780	// add only entries that cannot be exchanged with the parent
3781	if (!parent->Mailed(1))
3782	{
3783	newPvs.AddSampleDirty(obj, pvsData.mSumPdf);
3784	}
3785	}
3786	}
3787
3788	// add parents
3789	vector<BvhNode *>::const_iterator bit, bit_end = parents.end();
3790
3791	for (bit = parents.begin(); bit != bit_end; ++ bit)
3792	{
3793	newPvs.AddSampleDirty(*bit, 1);
3794	}
3795
3796	//cout << "size " << newPvs.GetSize() << endl;
3797	leaf->GetViewCell()->SetPvs(newPvs);
3798	}
3799
3800	return leaf->GetViewCell()->GetPvs().GetSize();
3801	}
3802
3803
3804	int VspTree::CompressObjects()
3805	{
3806	vector<VspLeaf *> leaves;
3807	CollectLeaves(leaves);
3808
3809	int numEntries = 0;
3810
3811	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
3812
3813	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3814	{
3815	numEntries += CompressObjects(*lit);
3816	}
3817
3818	return numEntries;
3819	}
3820
3821
3822	void VspTree::EvalMinMaxDepth(int &minDepth, int &maxDepth)
3823	{
3824	stack<pair<VspNode *, int> > nodeStack;
3825	nodeStack.push(pair<VspNode *, int>(mRoot, 0));
3826
3827	minDepth = 999999;
3828	maxDepth = 0;
3829
3830	while (!nodeStack.empty())
3831	{
3832	VspNode *node = nodeStack.top().first;
3833	const int depth = nodeStack.top().second;
3834
3835	nodeStack.pop();
3836
3837	if (node->IsLeaf())
3838	{
3839	// test if this leaf is in valid view space
3840	VspLeaf leaf = static_cast<VspLeaf >(node);
3841
3842	if (depth < minDepth)
3843	minDepth = depth;
3844
3845	if (depth > maxDepth)
3846	maxDepth = depth;
3847	}
3848	else
3849	{
3850	VspInterior interior = static_cast<VspInterior >(node);
3851
3852	nodeStack.push(pair<VspNode *, int>(interior->GetBack(), depth + 1));
3853	nodeStack.push(pair<VspNode *, int>(interior->GetFront(), depth + 1));
3854	}
3855	}
3856	}
3857
3858
3859	//////////
3860	// Binary export
3861
3862	void VspTree::ExportBinInterior(OUT_STREAM &stream, VspInterior *interior)
3863	{
3864	int type = TYPE_INTERIOR;
3865	stream.write(reinterpret_cast<char *>(&type), sizeof(int));
3866
3867	int axis = interior->GetAxis();
3868	float pos = interior->GetPosition();
3869
3870	stream.write(reinterpret_cast<char *>(&axis), sizeof(int));
3871	stream.write(reinterpret_cast<char *>(&pos), sizeof(float));
3872	}
3873
3874
3875	void VspTree::ExportBinLeaf(OUT_STREAM &stream, VspLeaf *leaf)
3876	{
3877	int type = TYPE_LEAF;
3878	stream.write(reinterpret_cast<char *>(&type), sizeof(int));
3879	}
3880
3881
3882	bool VspTree::ExportBinary(OUT_STREAM &stream)
3883	{
3884	// export binary version of mesh
3885	queue<VspNode *> tStack;
3886	tStack.push(mRoot);
3887
3888	while(!tStack.empty())
3889	{
3890	VspNode *node = tStack.front();
3891	tStack.pop();
3892
3893	if (node->IsLeaf())
3894	{
3895	ExportBinLeaf(stream, static_cast<VspLeaf *>(node));
3896	}
3897	else
3898	{
3899	VspInterior interior = static_cast<VspInterior >(node);
3900
3901	ExportBinInterior(stream, interior);
3902
3903	tStack.push(interior->GetFront());
3904	tStack.push(interior->GetBack());
3905	}
3906	}
3907
3908	return true;
3909	}
3910
3911
3912	//////////////////
3913	// import binary
3914
3915	VspInterior VspTree::ImportBinInterior(IN_STREAM &stream, VspInterior parent)
3916	{
3917	AxisAlignedPlane plane;
3918
3919	stream.read(reinterpret_cast<char *>(&plane.mAxis), sizeof(int));
3920	stream.read(reinterpret_cast<char *>(&plane.mPosition), sizeof(float));
3921
3922	VspInterior *interior = new VspInterior(plane);
3923
3924	return interior;
3925	}
3926
3927
3928	VspLeaf *VspTree::ImportBinLeaf(IN_STREAM &stream,
3929	VspInterior *parent)
3930	{
3931	int leafId = TYPE_LEAF;
3932	int objId = leafId;
3933
3934	VspLeaf *leaf = new VspLeaf(parent);
3935
3936	// pvs is loaded by view cell
3937	return leaf;
3938	}
3939
3940
3941	VspNode *VspTree::ImportNextNode(IN_STREAM &stream,
3942	VspInterior *parent)
3943	{
3944	int nodeType;
3945	stream.read(reinterpret_cast<char *>(&nodeType), sizeof(int));
3946
3947	if (nodeType == TYPE_LEAF)
3948	{
3949	//cerr << "l";
3950	return ImportBinLeaf(stream, static_cast<VspInterior *>(parent));
3951	}
3952
3953	if (nodeType == TYPE_INTERIOR)
3954	{
3955	//cerr << "i";
3956	return ImportBinInterior(stream, static_cast<VspInterior *>(parent));
3957	}
3958
3959	cerr << "error! loading vsp node failed!" << endl;
3960	return NULL;
3961	}
3962
3963
3964	/** Data used for tree traversal
3965	*/
3966	struct MyTraversalData
3967	{
3968	public:
3969
3970	MyTraversalData(VspNode *node, const int depth, const AxisAlignedBox3 &box):
3971	mNode(node), mDepth(depth), mBox(box)
3972	{}
3973
3974
3975	//////////////////////
3976
3977	/// the current node
3978	VspNode *mNode;
3979	/// current depth
3980	int mDepth;
3981	/// the bounding box
3982	AxisAlignedBox3 mBox;
3983	};
3984
3985
3986	bool VspTree::ImportBinary(IN_STREAM &stream)
3987	{
3988	// export binary version of mesh
3989	queue<MyTraversalData> tStack;
3990
3991	// hack: we make a new root
3992	DEL_PTR(mRoot);
3993	mRoot = ImportNextNode(stream, NULL);
3994
3995	tStack.push(MyTraversalData(mRoot, 0, mBoundingBox));
3996	mVspStats.Reset();
3997	mVspStats.nodes = 1;
3998
3999	while(!tStack.empty())
4000	{
4001	MyTraversalData tData = tStack.front();
4002	tStack.pop();
4003
4004	VspNode *node = tData.mNode;
4005
4006	if (!node->IsLeaf())
4007	{
4008	mVspStats.nodes += 2;
4009
4010	VspInterior interior = static_cast<VspInterior >(node);
4011	interior->SetBoundingBox(tData.mBox);
4012
4013	VspNode *front = ImportNextNode(stream, interior);
4014	VspNode *back = ImportNextNode(stream, interior);
4015
4016	interior->SetupChildLinks(front, back);
4017
4018	++ mVspStats.splits[interior->GetAxis()];
4019
4020	// compute new bounding box
4021	AxisAlignedBox3 frontBox, backBox;
4022
4023	tData.mBox.Split(interior->GetAxis(),
4024	interior->GetPosition(),
4025	frontBox,
4026	backBox);
4027
4028	tStack.push(MyTraversalData(front, tData.mDepth + 1, frontBox));
4029	tStack.push(MyTraversalData(back, tData.mDepth + 1, backBox));
4030	}
4031	else
4032	{
4033	//EvaluateLeafStats(tData);
4034	//cout << "l";
4035	}
4036	}
4037
4038	return true;
4039	}
4040
4041
4042	void VspTree::TestOutput(const std::string &filename)
4043	{
4044	ofstream str(filename.c_str());
4045
4046	vector<VspLeaf *> vspLeaves;
4047	CollectLeaves(vspLeaves);
4048
4049	str << "root: " << mBoundingBox << endl;
4050
4051	vector<VspLeaf *>::const_iterator vit, vit_end = vspLeaves.end();
4052
4053	for (vit = vspLeaves.begin(); vit != vit_end; ++ vit)
4054	{
4055	VspLeaf leaf = vit;
4056	ViewCell *vc = leaf->GetViewCell();
4057
4058	str << "\nleaf: " << GetBoundingBox(leaf) << endl;
4059
4060	ObjectContainer pvsObjects;
4061
4062	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4063
4064	while (pit.HasMoreEntries())
4065	{
4066	Intersectable *obj = pit.Next();
4067	pvsObjects.push_back(obj);
4068	}
4069
4070	sort(pvsObjects.begin(), pvsObjects.end(), ilt);
4071	str << "pvs: " << pvsObjects.size() << endl;
4072
4073	for (int i = 0; i < pvsObjects.size(); ++ i)
4074	str << pvsObjects[i]->GetId() << " ";
4075	}
4076	}
4077
4078
4079	}

Note: See TracBrowser for help on using the repository browser.

Download in other formats: