Context Navigation

VspTree.cpp @ 2588

Revision 2588, 89.2 KB checked in by bittner, 17 years ago (diff)
sceneBox bugfix

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

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

Context Navigation

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

Download in other formats: