Context Navigation

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

Revision 2347, 88.1 KB checked in by mattausch, 17 years ago (diff)
debug version

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

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

Download in other formats: