Context Navigation

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

Revision 2547, 92.8 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: