Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp @ 1052

Revision 1052, 65.8 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "VspOspTree.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
20
21	namespace GtpVisibilityPreprocessor {
22
23	#define USE_FIXEDPOINT_T 0
24
25
26	//-- static members
27
28	int VspTree::sFrontId = 0;
29	int VspTree::sBackId = 0;
30	int VspTree::sFrontAndBackId = 0;
31
32
33
34	// pvs penalty can be different from pvs size
35	inline static float EvalPvsPenalty(const int pvs,
36	const int lower,
37	const int upper)
38	{
39	// clamp to minmax values
40	if (pvs < lower)
41	return (float)lower;
42	if (pvs > upper)
43	return (float)upper;
44
45	return (float)pvs;
46	}
47
48
49	int VspNode::sMailId = 1;
50
51
52
53	void VspTreeStatistics::Print(ostream &app) const
54	{
55	app << "===== VspTree statistics ===============\n";
56
57	app << setprecision(4);
58
59	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
60
61	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
62
63	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
64
65	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
66
67	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
68
69	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
70
71	for (int i = 0; i < 3; ++ i)
72	app << splits[i] << " ";
73	app << endl;
74
75	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
76	<< maxDepthNodes * 100 / (double)Leaves() << endl;
77
78	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
79	<< minPvsNodes * 100 / (double)Leaves() << endl;
80
81	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
82	<< minRaysNodes * 100 / (double)Leaves() << endl;
83
84	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
85	<< maxCostNodes * 100 / (double)Leaves() << endl;
86
87	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
88	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
89
90	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
91	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
92
93	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
94
95	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
96
97	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
98
99	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
100
101	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
102	//app << "#N_PVS: " << pvs << endl;
103
104	app << "===== END OF VspTree statistics ==========\n";
105	}
106
107
108	/******************************************************************/
109	/* class VspNode implementation */
110	/******************************************************************/
111
112
113	VspNode::VspNode():
114	mParent(NULL), mTreeValid(true), mTimeStamp(0)
115	{}
116
117
118	VspNode::VspNode(VspInterior *parent):
119	mParent(parent), mTreeValid(true)
120	{}
121
122
123	bool VspNode::IsRoot() const
124	{
125	return mParent == NULL;
126	}
127
128
129	VspInterior *VspNode::GetParent()
130	{
131	return mParent;
132	}
133
134
135	void VspNode::SetParent(VspInterior *parent)
136	{
137	mParent = parent;
138	}
139
140
141	bool VspNode::IsSibling(VspNode *n) const
142	{
143	return ((this != n) && mParent &&
144	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
145	}
146
147
148	int VspNode::GetDepth() const
149	{
150	int depth = 0;
151	VspNode *p = mParent;
152
153	while (p)
154	{
155	p = p->mParent;
156	++ depth;
157	}
158
159	return depth;
160	}
161
162
163	bool VspNode::TreeValid() const
164	{
165	return mTreeValid;
166	}
167
168
169	void VspNode::SetTreeValid(const bool v)
170	{
171	mTreeValid = v;
172	}
173
174
175	/****************************************************************/
176	/* class VspInterior implementation */
177	/****************************************************************/
178
179
180	VspInterior::VspInterior(const AxisAlignedPlane &plane):
181	mPlane(plane), mFront(NULL), mBack(NULL)
182	{}
183
184
185	VspInterior::~VspInterior()
186	{
187	DEL_PTR(mFront);
188	DEL_PTR(mBack);
189	}
190
191
192	bool VspInterior::IsLeaf() const
193	{
194	return false;
195	}
196
197
198	VspNode *VspInterior::GetBack()
199	{
200	return mBack;
201	}
202
203
204	VspNode *VspInterior::GetFront()
205	{
206	return mFront;
207	}
208
209
210	AxisAlignedPlane VspInterior::GetPlane() const
211	{
212	return mPlane;
213	}
214
215
216	float VspInterior::GetPosition() const
217	{
218	return mPlane.mPosition;
219	}
220
221
222	int VspInterior::GetAxis() const
223	{
224	return mPlane.mAxis;
225	}
226
227
228	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
229	{
230	if (mBack == oldChild)
231	mBack = newChild;
232	else
233	mFront = newChild;
234	}
235
236
237	void VspInterior::SetupChildLinks(VspNode b, VspNode f)
238	{
239	mBack = b;
240	mFront = f;
241	}
242
243
244	AxisAlignedBox3 VspInterior::GetBoundingBox() const
245	{
246	return mBoundingBox;
247	}
248
249
250	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
251	{
252	mBoundingBox = box;
253	}
254
255
256	int VspInterior::Type() const
257	{
258	return Interior;
259	}
260
261
262
263	/****************************************************************/
264	/* class VspLeaf implementation */
265	/****************************************************************/
266
267
268	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
269	{
270	}
271
272
273	VspLeaf::~VspLeaf()
274	{
275	DEL_PTR(mPvs);
276	}
277
278
279	int VspLeaf::Type() const
280	{
281	return Leaf;
282	}
283
284
285	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
286	mViewCell(viewCell)
287	{
288	}
289
290
291	VspLeaf::VspLeaf(VspInterior *parent):
292	VspNode(parent), mViewCell(NULL), mPvs(NULL)
293	{}
294
295
296
297	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
298	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
299	{
300	}
301
302	ViewCellLeaf *VspLeaf::GetViewCell() const
303	{
304	return mViewCell;
305	}
306
307	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
308	{
309	mViewCell = viewCell;
310	}
311
312
313	bool VspLeaf::IsLeaf() const
314	{
315	return true;
316	}
317
318
319	/******************************************************************************/
320	/* class VspTree implementation */
321	/******************************************************************************/
322
323
324	VspTree::VspTree():
325	mRoot(NULL),
326	mOutOfBoundsCell(NULL),
327	mStoreRays(false),
328	mTimeStamp(1)
329	{
330	bool randomize = false;
331	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
332	if (randomize)
333	Randomize(); // initialise random generator for heuristics
334
335	//-- termination criteria for autopartition
336	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
337	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
338	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
339	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
340	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
341
342	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
343	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
344
345	//-- max cost ratio for early tree termination
346	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
347
348	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
349	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
350
351	// HACK//mTermMinPolygons = 25;
352
353	//-- factors for bsp tree split plane heuristics
354	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
355
356	//-- partition criteria
357	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
358
359	// if only the driving axis is used for axis aligned split
360	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
361
362	//Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
363	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
364
365	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
366	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
367
368
369	char subdivisionStatsLog[100];
370	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
371	mSubdivisionStats.open(subdivisionStatsLog);
372
373	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
374	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
375
376
377	//-- debug output
378
379	Debug << "***** VSP BSP options ****** " << endl;
380	Debug << "max depth: " << mTermMaxDepth << endl;
381	Debug << "min PVS: " << mTermMinPvs << endl;
382	Debug << "min probabiliy: " << mTermMinProbability << endl;
383	Debug << "min rays: " << mTermMinRays << endl;
384	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
385	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
386	Debug << "miss tolerance: " << mTermMissTolerance << endl;
387	Debug << "max view cells: " << mMaxViewCells << endl;
388	Debug << "randomize: " << randomize << endl;
389
390	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
391	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
392	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
393	Debug << "max memory: " << mMaxMemory << endl;
394	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
395	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
396
397	Debug << "circulating axis: " << mCirculatingAxis << endl;
398	Debug << "minband: " << mMinBand << endl;
399	Debug << "maxband: " << mMaxBand << endl;
400
401
402	mSplitCandidates = new vector<SortableEntry>;
403
404	Debug << endl;
405	}
406
407
408	VspViewCell *VspTree::GetOutOfBoundsCell()
409	{
410	return mOutOfBoundsCell;
411	}
412
413
414	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
415	{
416	if (!mOutOfBoundsCell)
417	{
418	mOutOfBoundsCell = new VspViewCell();
419	mOutOfBoundsCell->SetId(-1);
420	mOutOfBoundsCell->SetValid(false);
421	}
422
423	return mOutOfBoundsCell;
424	}
425
426
427	const VspTreeStatistics &VspTree::GetStatistics() const
428	{
429	return mVspStats;
430	}
431
432
433	VspTree::~VspTree()
434	{
435	DEL_PTR(mRoot);
436	DEL_PTR(mSplitCandidates);
437	}
438
439
440	void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
441	AxisAlignedBox3 *forcedBoundingBox)
442	{
443	mVspStats.nodes = 1;
444
445	if (forcedBoundingBox)
446	{
447	mBoundingBox = *forcedBoundingBox;
448	}
449	else // compute vsp tree bounding box
450	{
451	mBoundingBox.Initialize();
452
453	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
454
455	//-- compute bounding box
456	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
457	{
458	VssRay ray = rit;
459
460	// compute bounding box of view space
461	mBoundingBox.Include(ray->GetTermination());
462	mBoundingBox.Include(ray->GetOrigin());
463	}
464
465	mTermMinProbability *= mBoundingBox.GetVolume();
466	mGlobalCostMisses = 0;
467	}
468	}
469
470
471	void VspTree::AddSubdivisionStats(const int viewCells,
472	const float renderCostDecr,
473	const float splitCandidateCost,
474	const float totalRenderCost,
475	const float avgRenderCost)
476	{
477	mSubdivisionStats
478	<< "#ViewCells\n" << viewCells << endl
479	<< "#RenderCostDecrease\n" << renderCostDecr << endl
480	<< "#SplitCandidateCost\n" << splitCandidateCost << endl
481	<< "#TotalRenderCost\n" << totalRenderCost << endl
482	<< "#AvgRenderCost\n" << avgRenderCost << endl;
483	}
484
485
486	// TODO: return memory usage in MB
487	float VspTree::GetMemUsage() const
488	{
489	return (float)
490	(sizeof(VspTree) +
491	mVspStats.Leaves() * sizeof(VspLeaf) +
492	mCreatedViewCells * sizeof(VspViewCell) +
493	mVspStats.pvs * sizeof(ObjectPvsData) +
494	mVspStats.Interior() * sizeof(VspInterior) +
495	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
496	}
497
498
499	bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
500	{
501	return
502	#if TODO
503	(((int)data.mRays->size() <= mTermMinRays) \|\|
504	(data.mPvs <= mTermMinPvs) \|\|
505	(data.mProbability <= mTermMinProbability) \|\|
506	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
507	(data.mDepth >= mTermMaxDepth));
508	#else
509	false;
510	#endif
511	}
512
513
514	bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
515	{
516	return
517	#if TODO
518	(mOutOfMemory \|\|
519	(mVspStats.Leaves() >= mMaxViewCells) \|\|
520	(mGlobalCostMisses >= mTermGlobalCostMissTolerance));
521	#else
522	(mVspStats.Leaves() >= mMaxViewCells) ;
523	#endif
524	}
525
526
527	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
528	VspSplitCandidate &splitCandidate,
529	const bool globalCriteriaMet)
530	{
531	VspTraversalData &tData = splitCandidate.mParentData;
532
533	VspNode *newNode = tData.mNode;
534
535	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
536	{
537	VspTraversalData tFrontData;
538	VspTraversalData tBackData;
539
540	//-- continue subdivision
541
542	// create new interior node and two leaf node
543	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
544	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
545
546	const int maxCostMisses = splitCandidate.mMaxCostMisses;
547
548
549	// how often was max cost ratio missed in this branch?
550	tFrontData.mMaxCostMisses = maxCostMisses;
551	tBackData.mMaxCostMisses = maxCostMisses;
552
553	//-- statistics
554	if (1)
555	{
556	const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
557	const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
558	const float cData = (float)tData.mPvs * tData.mProbability;
559
560	const float costDecr =
561	(cFront + cBack - cData) / mBoundingBox.GetVolume();
562
563	mTotalCost += costDecr;
564	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
565
566	AddSubdivisionStats(mVspStats.Leaves(),
567	-costDecr,
568	splitCandidate.GetPriority(),
569	mTotalCost,
570	(float)mTotalPvsSize / (float)mVspStats.Leaves());
571	}
572
573
574	//-- push the new split candidates on the queue
575	VspSplitCandidate *frontCandidate = new VspSplitCandidate();
576	VspSplitCandidate *backCandidate = new VspSplitCandidate();
577
578	EvalSplitCandidate(tFrontData, *frontCandidate);
579	EvalSplitCandidate(tBackData, *backCandidate);
580
581	tQueue.push(frontCandidate);
582	tQueue.push(backCandidate);
583
584	// delete old leaf node
585	DEL_PTR(tData.mNode);
586	}
587
588
589	//-- terminate traversal and create new view cell
590	if (newNode->IsLeaf())
591	{
592	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
593
594	VspViewCell *viewCell = new VspViewCell();
595	leaf->SetViewCell(viewCell);
596
597	//-- update pvs
598	int conSamp = 0;
599	float sampCon = 0.0f;
600	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
601
602	// update scalar pvs size value
603	mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
604
605	mVspStats.contributingSamples += conSamp;
606	mVspStats.sampleContributions +=(int) sampCon;
607
608	//-- store additional info
609	if (mStoreRays)
610	{
611	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
612	for (it = tData.mRays->begin(); it != it_end; ++ it)
613	{
614	(*it).mRay->Ref();
615	leaf->mVssRays.push_back((*it).mRay);
616	}
617	}
618
619	viewCell->mLeaf = leaf;
620
621	viewCell->SetVolume(tData.mProbability);
622	leaf->mProbability = tData.mProbability;
623
624	// finally evaluate stats until this leaf
625	EvaluateLeafStats(tData);
626	}
627
628	//-- cleanup
629	tData.Clear();
630
631	return newNode;
632	}
633
634
635	void VspTree::EvalSplitCandidate(VspTraversalData &tData,
636	VspSplitCandidate &splitCandidate)
637	{
638	float frontProb;
639	float backProb;
640
641	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
642
643	// compute locally best split plane
644	const bool success =
645	SelectSplitPlane(tData, splitCandidate.mSplitPlane, frontProb, backProb);
646
647	// compute global decrease in render cost
648	splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData);
649	splitCandidate.mParentData = tData;
650	splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
651
652	Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
653	}
654
655
656	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
657	VspTraversalData &tData,
658	VspTraversalData &frontData,
659	VspTraversalData &backData)
660	{
661	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
662
663	//-- the front and back traversal data is filled with the new values
664	frontData.mDepth = tData.mDepth + 1;
665	frontData.mRays = new RayInfoContainer();
666
667	backData.mDepth = tData.mDepth + 1;
668	backData.mRays = new RayInfoContainer();
669
670	//-- subdivide rays
671	SplitRays(splitPlane,
672	*tData.mRays,
673	*frontData.mRays,
674	*backData.mRays);
675
676	Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
677	//-- compute pvs
678	frontData.mPvs = ComputePvsSize(*frontData.mRays);
679	backData.mPvs = ComputePvsSize(*backData.mRays);
680
681	// split front and back node geometry and compute area
682	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
683	frontData.mBoundingBox, backData.mBoundingBox);
684
685
686	frontData.mProbability = frontData.mBoundingBox.GetVolume();
687	backData.mProbability = tData.mProbability - frontData.mProbability;
688
689
690	///////////////////////////////////////////
691	// subdivide further
692
693	// store maximal and minimal depth
694	if (tData.mDepth > mVspStats.maxDepth)
695	{
696	Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
697	mVspStats.maxDepth = tData.mDepth;
698	}
699
700	mVspStats.nodes += 2;
701
702
703	VspInterior *interior = new VspInterior(splitPlane);
704
705	#ifdef _DEBUG
706	Debug << interior << endl;
707	#endif
708
709
710	//-- create front and back leaf
711
712	VspInterior *parent = leaf->GetParent();
713
714	// replace a link from node's parent
715	if (parent)
716	{
717	parent->ReplaceChildLink(leaf, interior);
718	interior->SetParent(parent);
719	}
720	else // new root
721	{
722	mRoot = interior;
723	}
724
725	// and setup child links
726	interior->SetupChildLinks(new VspLeaf(interior), new VspLeaf(interior));
727	// add bounding box
728	interior->SetBoundingBox(tData.mBoundingBox);
729
730	frontData.mNode = interior->GetFront();
731	backData.mNode = interior->GetBack();
732
733	interior->mTimeStamp = mTimeStamp ++;
734
735	return interior;
736	}
737
738
739	void VspTree::AddToPvs(VspLeaf *leaf,
740	const RayInfoContainer &rays,
741	float &sampleContributions,
742	int &contributingSamples)
743	{
744	sampleContributions = 0;
745	contributingSamples = 0;
746
747	RayInfoContainer::const_iterator it, it_end = rays.end();
748
749	ViewCellLeaf *vc = leaf->GetViewCell();
750
751	// add contributions from samples to the PVS
752	for (it = rays.begin(); it != it_end; ++ it)
753	{
754	float sc = 0.0f;
755	VssRay ray = (it).mRay;
756
757	bool madeContrib = false;
758	float contribution;
759
760	if (ray->mTerminationObject)
761	{
762	if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
763	madeContrib = true;
764	sc += contribution;
765	}
766
767	if (ray->mOriginObject)
768	{
769	if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
770	madeContrib = true;
771	sc += contribution;
772	}
773
774	sampleContributions += sc;
775
776	if (madeContrib)
777	++ contributingSamples;
778
779	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
780	}
781	}
782
783
784	void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
785	const int axis,
786	float minBand,
787	float maxBand)
788	{
789	mSplitCandidates->clear();
790
791	int requestedSize = 2 * (int)(rays.size());
792
793	// creates a sorted split candidates array
794	if (mSplitCandidates->capacity() > 500000 &&
795	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
796	{
797	delete mSplitCandidates;
798	mSplitCandidates = new vector<SortableEntry>;
799	}
800
801	mSplitCandidates->reserve(requestedSize);
802
803	float pos;
804
805	// float values => don't compare with exact values
806	if (0)
807	{
808	minBand += Limits::Small;
809	maxBand -= Limits::Small;
810	}
811
812	// insert all queries
813	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
814	{
815	const bool positive = (*ri).mRay->HasPosDir(axis);
816
817	pos = (*ri).ExtrapOrigin(axis);
818	// clamp to min / max band
819	if (0) ClipValue(pos, minBand, maxBand);
820
821	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
822	pos, (*ri).mRay));
823
824	pos = (*ri).ExtrapTermination(axis);
825	// clamp to min / max band
826	if (0) ClipValue(pos, minBand, maxBand);
827
828	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
829	pos, (*ri).mRay));
830	}
831
832	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
833	}
834
835
836	float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
837	const AxisAlignedBox3 &box,
838	const int pvsSize,
839	const int axis,
840	float &position)
841	{
842	const float minBox = box.Min(axis);
843	const float maxBox = box.Max(axis);
844
845	const float sizeBox = maxBox - minBox;
846
847	const float minBand = minBox + mMinBand * sizeBox;
848	const float maxBand = minBox + mMaxBand * sizeBox;
849
850	SortSplitCandidates(rays, axis, minBand, maxBand);
851
852	// go through the lists, count the number of objects left and right
853	// and evaluate the following cost funcion:
854	// C = ct_div_ci + (qlrl + qrrr)/queries
855
856	int pvsl = 0;
857	int pvsr = pvsSize;
858
859	int pvsBack = pvsl;
860	int pvsFront = pvsr;
861
862	float sum = (float)pvsSize * sizeBox;
863	float minSum = 1e20f;
864
865
866	// if no good split can be found, take mid split
867	position = minBox + 0.5f * sizeBox;
868
869	// the relative cost ratio
870	float ratio = /Limits::Infinity;/99999999.0f;
871	bool splitPlaneFound = false;
872
873	Intersectable::NewMail();
874
875	RayInfoContainer::const_iterator ri, ri_end = rays.end();
876
877	// set all object as belonging to the front pvs
878	for(ri = rays.begin(); ri != ri_end; ++ ri)
879	{
880	Intersectable oObject = (ri).mRay->mOriginObject;
881	Intersectable tObject = (ri).mRay->mTerminationObject;
882
883	if (oObject)
884	{
885	if (!oObject->Mailed())
886	{
887	oObject->Mail();
888	oObject->mCounter = 1;
889	}
890	else
891	{
892	++ oObject->mCounter;
893	}
894	}
895	if (tObject)
896	{
897	if (!tObject->Mailed())
898	{
899	tObject->Mail();
900	tObject->mCounter = 1;
901	}
902	else
903	{
904	++ tObject->mCounter;
905	}
906	}
907	}
908
909	Intersectable::NewMail();
910
911	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
912
913	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
914	{
915	VssRay *ray;
916	ray = (*ci).ray;
917
918	Intersectable *oObject = ray->mOriginObject;
919	Intersectable *tObject = ray->mTerminationObject;
920
921
922	switch ((*ci).type)
923	{
924	case SortableEntry::ERayMin:
925	{
926	if (oObject && !oObject->Mailed())
927	{
928	oObject->Mail();
929	++ pvsl;
930	}
931	if (tObject && !tObject->Mailed())
932	{
933	tObject->Mail();
934	++ pvsl;
935	}
936	break;
937	}
938	case SortableEntry::ERayMax:
939	{
940	if (oObject)
941	{
942	if (-- oObject->mCounter == 0)
943	-- pvsr;
944	}
945
946	if (tObject)
947	{
948	if (-- tObject->mCounter == 0)
949	-- pvsr;
950	}
951
952	break;
953	}
954	}
955
956
957	// Note: sufficient to compare size of bounding boxes of front and back side?
958	if (((ci).value >= minBand) && ((ci).value <= maxBand))
959	{
960	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
961
962	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl;
963	//Debug << "cost= " << sum << endl;
964
965	if (sum < minSum)
966	{
967	splitPlaneFound = true;
968
969	minSum = sum;
970	position = (*ci).value;
971
972	pvsBack = pvsl;
973	pvsFront = pvsr;
974	}
975	}
976	}
977
978
979	// -- compute cost
980
981	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
982	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
983
984	const float pOverall = sizeBox;
985	const float pBack = position - minBox;
986	const float pFront = maxBox - position;
987
988	/*const float pOverall = box.GetVolume();
989
990	AxisAlignedBox3 bbox;
991	AxisAlignedBox3 fbox;
992
993	box.Split(axis, position, bbox, fbox);
994
995	const float pBack = fbox.GetVolume();
996	const float pFront = bbox.GetVolume();*/
997
998	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
999	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1000	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1001
1002	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1003	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1004
1005	if (splitPlaneFound)
1006	{
1007	ratio = newRenderCost / oldRenderCost;
1008	}
1009	//if (axis != 1)
1010	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1011	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
1012
1013	return ratio;
1014	}
1015
1016
1017	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1018	AxisAlignedPlane &plane,
1019	float &pFront,
1020	float &pBack)
1021	{
1022	float nPosition[3];
1023	float nCostRatio[3];
1024	float nProbFront[3];
1025	float nProbBack[3];
1026
1027	// create bounding box of node geometry
1028	AxisAlignedBox3 box = tData.mBoundingBox;
1029
1030	int sAxis = 0;
1031	int bestAxis = -1;
1032
1033	//mOnlyDrivingAxis = true;
1034
1035	// if we use some kind of specialised fixed axis
1036	const bool useSpecialAxis =
1037	mOnlyDrivingAxis \|\| mCirculatingAxis;
1038	Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
1039	if (mCirculatingAxis)
1040	{
1041	int parentAxis = 0;
1042	VspNode *parent = tData.mNode->GetParent();
1043
1044	if (parent)
1045	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
1046
1047	sAxis = (parentAxis + 1) % 3;
1048	}
1049	else if (mOnlyDrivingAxis)
1050	{
1051	sAxis = box.Size().DrivingAxis();
1052	}
1053	//sAxis = 2;
1054	for (int axis = 0; axis < 3; ++ axis)
1055	{
1056	if (!useSpecialAxis \|\| (axis == sAxis))
1057	{
1058	//-- place split plane using heuristics
1059
1060	if (mUseCostHeuristics)
1061	{
1062	nCostRatio[axis] =
1063	EvalLocalCostHeuristics(*tData.mRays,
1064	box,
1065	tData.mPvs,
1066	axis,
1067	nPosition[axis]);
1068	}
1069	else //-- split plane position is spatial median
1070	{
1071	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1072
1073	nCostRatio[axis] = EvalLocalSplitCost(tData,
1074	box,
1075	axis,
1076	nPosition[axis],
1077	nProbFront[axis],
1078	nProbBack[axis]);
1079	}
1080
1081	if (bestAxis == -1)
1082	{
1083	bestAxis = axis;
1084	}
1085	else if (nCostRatio[axis] < nCostRatio[bestAxis])
1086	{
1087	Debug << "old: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1088	bestAxis = axis;
1089
1090	Debug << "new: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1091	}
1092	}
1093	}
1094
1095
1096	//-- assign values
1097
1098	plane.mAxis = bestAxis;
1099	// split plane position
1100	plane.mPosition = nPosition[bestAxis];
1101
1102	pFront = nProbFront[bestAxis];
1103	pBack = nProbBack[bestAxis];
1104
1105
1106	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1107	return nCostRatio[bestAxis];
1108	}
1109
1110
1111	inline void VspTree::GenerateUniqueIdsForPvs()
1112	{
1113	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
1114	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
1115	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
1116	}
1117
1118
1119	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1120	const VspTraversalData &data) const
1121	{
1122	#if 0
1123	return (float)-data.mDepth;
1124	#endif
1125	float pvsFront = 0;
1126	float pvsBack = 0;
1127	float totalPvs = 0;
1128
1129	// probability that view point lies in back / front node
1130	float pOverall = data.mProbability;
1131	float pFront = 0;
1132	float pBack = 0;
1133
1134
1135	// create unique ids for pvs heuristics
1136	GenerateUniqueIdsForPvs();
1137
1138	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1139
1140	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1141	{
1142	RayInfo rayInf = *rit;
1143
1144	float t;
1145	VssRay *ray = rayInf.mRay;
1146
1147	const int cf =
1148	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1149	candidatePlane.mPosition, t);
1150
1151	// find front and back pvs for origing and termination object
1152	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1153	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1154	}
1155
1156
1157	AxisAlignedBox3 frontBox;
1158	AxisAlignedBox3 backBox;
1159
1160	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1161
1162	pFront = frontBox.GetVolume();
1163	pBack = pOverall - pFront;
1164
1165
1166	//-- pvs rendering heuristics
1167	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1168	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1169
1170	//-- only render cost heuristics or combined with standard deviation
1171	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1172	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1173	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1174
1175	const float oldRenderCost = pOverall * penaltyOld;
1176	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1177
1178	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
1179	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
1180
1181	// take render cost of node into account
1182	// otherwise danger of being stuck in a local minimum!!
1183	const float factor = 0.99f;
1184
1185	const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
1186	return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
1187	}
1188
1189
1190	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
1191	const AxisAlignedBox3 &box,
1192	const int axis,
1193	const float &position,
1194	float &pFront,
1195	float &pBack) const
1196	{
1197	float pvsTotal = 0;
1198	float pvsFront = 0;
1199	float pvsBack = 0;
1200
1201	// create unique ids for pvs heuristics
1202	GenerateUniqueIdsForPvs();
1203
1204	const int pvsSize = data.mPvs;
1205
1206	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1207
1208	// this is the main ray classification loop!
1209	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1210	{
1211	// determine the side of this ray with respect to the plane
1212	float t;
1213	const int side = (*rit).ComputeRayIntersection(axis, position, t);
1214
1215	AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1216	AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1217	}
1218
1219	//-- pvs heuristics
1220	float pOverall;
1221
1222	//-- compute heurstics
1223
1224	pOverall = data.mProbability;
1225	// we take simplified computation for mid split
1226	pBack = pFront = pOverall * 0.5f;
1227
1228
1229	#ifdef _DEBUG
1230	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1231	Debug << pFront << " " << pBack << " " << pOverall << endl;
1232	#endif
1233
1234
1235	const float newCost = pvsBack * pBack + pvsFront * pFront;
1236	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1237
1238	return (mCtDivCi + newCost) / oldCost;
1239	}
1240
1241
1242	void VspTree::AddObjToPvs(Intersectable *obj,
1243	const int cf,
1244	float &frontPvs,
1245	float &backPvs,
1246	float &totalPvs) const
1247	{
1248	if (!obj)
1249	return;
1250
1251	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1252
1253	// new object
1254	if ((obj->mMailbox != sFrontId) &&
1255	(obj->mMailbox != sBackId) &&
1256	(obj->mMailbox != sFrontAndBackId))
1257	{
1258	totalPvs += renderCost;
1259	}
1260
1261	// TODO: does this really belong to no pvs?
1262	//if (cf == Ray::COINCIDENT) return;
1263
1264	// object belongs to both PVS
1265	if (cf >= 0)
1266	{
1267	if ((obj->mMailbox != sFrontId) &&
1268	(obj->mMailbox != sFrontAndBackId))
1269	{
1270	frontPvs += renderCost;
1271
1272	if (obj->mMailbox == sBackId)
1273	obj->mMailbox = sFrontAndBackId;
1274	else
1275	obj->mMailbox = sFrontId;
1276	}
1277	}
1278
1279	if (cf <= 0)
1280	{
1281	if ((obj->mMailbox != sBackId) &&
1282	(obj->mMailbox != sFrontAndBackId))
1283	{
1284	backPvs += renderCost;
1285
1286	if (obj->mMailbox == sFrontId)
1287	obj->mMailbox = sFrontAndBackId;
1288	else
1289	obj->mMailbox = sBackId;
1290	}
1291	}
1292	}
1293
1294
1295	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1296	const bool onlyUnmailed,
1297	const int maxPvsSize) const
1298	{
1299	stack<VspNode *> nodeStack;
1300	nodeStack.push(mRoot);
1301
1302	while (!nodeStack.empty())
1303	{
1304	VspNode *node = nodeStack.top();
1305	nodeStack.pop();
1306
1307	if (node->IsLeaf())
1308	{
1309	// test if this leaf is in valid view space
1310	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1311	if (leaf->TreeValid() &&
1312	(!onlyUnmailed \|\| !leaf->Mailed()) &&
1313	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
1314	{
1315	leaves.push_back(leaf);
1316	}
1317	}
1318	else
1319	{
1320	VspInterior interior = dynamic_cast<VspInterior >(node);
1321
1322	nodeStack.push(interior->GetBack());
1323	nodeStack.push(interior->GetFront());
1324	}
1325	}
1326	}
1327
1328
1329	AxisAlignedBox3 VspTree::GetBoundingBox() const
1330	{
1331	return mBoundingBox;
1332	}
1333
1334
1335	VspNode *VspTree::GetRoot() const
1336	{
1337	return mRoot;
1338	}
1339
1340
1341	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1342	{
1343	// the node became a leaf -> evaluate stats for leafs
1344	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
1345
1346
1347	if (data.mPvs > mVspStats.maxPvs)
1348	{
1349	mVspStats.maxPvs = data.mPvs;
1350	}
1351
1352	mVspStats.pvs += data.mPvs;
1353
1354	if (data.mDepth < mVspStats.minDepth)
1355	{
1356	mVspStats.minDepth = data.mDepth;
1357	}
1358
1359	if (data.mDepth >= mTermMaxDepth)
1360	{
1361	++ mVspStats.maxDepthNodes;
1362	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1363	}
1364
1365	// accumulate rays to compute rays / leaf
1366	mVspStats.accumRays += (int)data.mRays->size();
1367
1368	if (data.mPvs < mTermMinPvs)
1369	++ mVspStats.minPvsNodes;
1370
1371	if ((int)data.mRays->size() < mTermMinRays)
1372	++ mVspStats.minRaysNodes;
1373
1374	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1375	++ mVspStats.maxRayContribNodes;
1376
1377	if (data.mProbability <= mTermMinProbability)
1378	++ mVspStats.minProbabilityNodes;
1379
1380	// accumulate depth to compute average depth
1381	mVspStats.accumDepth += data.mDepth;
1382
1383	++ mCreatedViewCells;
1384
1385	//#ifdef _DEBUG
1386	Debug << "BSP stats: "
1387	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1388	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1389	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1390	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
1391	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1392	//#endif
1393	}
1394
1395
1396	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1397	{
1398	ViewCell::NewMail();
1399	CollectViewCells(mRoot, onlyValid, viewCells, true);
1400	}
1401
1402
1403	void VspTree::CollapseViewCells()
1404	{
1405	// TODO
1406	#if HAS_TO_BE_REDONE
1407	stack<VspNode *> nodeStack;
1408
1409	if (!mRoot)
1410	return;
1411
1412	nodeStack.push(mRoot);
1413
1414	while (!nodeStack.empty())
1415	{
1416	VspNode *node = nodeStack.top();
1417	nodeStack.pop();
1418
1419	if (node->IsLeaf())
1420	{
1421	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1422
1423	if (!viewCell->GetValid())
1424	{
1425	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
1426
1427	ViewCellContainer leaves;
1428	mViewCellsTree->CollectLeaves(viewCell, leaves);
1429
1430	ViewCellContainer::const_iterator it, it_end = leaves.end();
1431
1432	for (it = leaves.begin(); it != it_end; ++ it)
1433	{
1434	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
1435	l->SetViewCell(GetOrCreateOutOfBoundsCell());
1436	++ mVspStats.invalidLeaves;
1437	}
1438
1439	// add to unbounded view cell
1440	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1441	DEL_PTR(viewCell);
1442	}
1443	}
1444	else
1445	{
1446	VspInterior interior = dynamic_cast<VspInterior >(node);
1447
1448	nodeStack.push(interior->GetFront());
1449	nodeStack.push(interior->GetBack());
1450	}
1451	}
1452
1453	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1454	#endif
1455	}
1456
1457
1458	void VspTree::CollectRays(VssRayContainer &rays)
1459	{
1460	vector<VspLeaf *> leaves;
1461
1462	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1463
1464	for (lit = leaves.begin(); lit != lit_end; ++ lit)
1465	{
1466	VspLeaf leaf = lit;
1467	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1468
1469	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1470	rays.push_back(*rit);
1471	}
1472	}
1473
1474
1475	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
1476	{
1477	mViewCellsManager = vcm;
1478	}
1479
1480
1481	void VspTree::ValidateTree()
1482	{
1483	mVspStats.invalidLeaves = 0;
1484
1485	stack<VspNode *> nodeStack;
1486
1487	if (!mRoot)
1488	return;
1489
1490	nodeStack.push(mRoot);
1491
1492	while (!nodeStack.empty())
1493	{
1494	VspNode *node = nodeStack.top();
1495	nodeStack.pop();
1496
1497	if (node->IsLeaf())
1498	{
1499	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1500
1501	if (!leaf->GetViewCell()->GetValid())
1502	++ mVspStats.invalidLeaves;
1503
1504	// validity flags don't match => repair
1505	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
1506	{
1507	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
1508	PropagateUpValidity(leaf);
1509	}
1510	}
1511	else
1512	{
1513	VspInterior interior = dynamic_cast<VspInterior >(node);
1514
1515	nodeStack.push(interior->GetFront());
1516	nodeStack.push(interior->GetBack());
1517	}
1518	}
1519
1520	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1521	}
1522
1523
1524
1525	void VspTree::CollectViewCells(VspNode *root,
1526	bool onlyValid,
1527	ViewCellContainer &viewCells,
1528	bool onlyUnmailed) const
1529	{
1530	stack<VspNode *> nodeStack;
1531
1532	if (!root)
1533	return;
1534
1535	nodeStack.push(root);
1536
1537	while (!nodeStack.empty())
1538	{
1539	VspNode *node = nodeStack.top();
1540	nodeStack.pop();
1541
1542	if (node->IsLeaf())
1543	{
1544	if (!onlyValid \|\| node->TreeValid())
1545	{
1546	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
1547
1548	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
1549
1550	if (!onlyUnmailed \|\| !viewCell->Mailed())
1551	{
1552	viewCell->Mail();
1553	viewCells.push_back(viewCell);
1554	}
1555	}
1556	}
1557	else
1558	{
1559	VspInterior interior = dynamic_cast<VspInterior >(node);
1560
1561	nodeStack.push(interior->GetFront());
1562	nodeStack.push(interior->GetBack());
1563	}
1564	}
1565	}
1566
1567
1568	int VspTree::FindNeighbors(VspLeaf *n,
1569	vector<VspLeaf *> &neighbors,
1570	const bool onlyUnmailed) const
1571	{
1572	stack<VspNode *> nodeStack;
1573	nodeStack.push(mRoot);
1574
1575	const AxisAlignedBox3 box = GetBBox(n);
1576
1577	while (!nodeStack.empty())
1578	{
1579	VspNode *node = nodeStack.top();
1580	nodeStack.pop();
1581
1582	if (node->IsLeaf())
1583	{
1584	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1585
1586	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
1587	neighbors.push_back(leaf);
1588	}
1589	else
1590	{
1591	VspInterior interior = dynamic_cast<VspInterior >(node);
1592
1593	if (interior->GetPosition() > box.Max(interior->GetAxis()))
1594	nodeStack.push(interior->GetBack());
1595	else
1596	{
1597	if (interior->GetPosition() < box.Min(interior->GetAxis()))
1598	nodeStack.push(interior->GetFront());
1599	else
1600	{
1601	// random decision
1602	nodeStack.push(interior->GetBack());
1603	nodeStack.push(interior->GetFront());
1604	}
1605	}
1606	}
1607	}
1608
1609	return (int)neighbors.size();
1610	}
1611
1612
1613	// Find random neighbor which was not mailed
1614	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
1615	{
1616	stack<VspNode *> nodeStack;
1617	nodeStack.push(mRoot);
1618
1619	int mask = rand();
1620
1621	while (!nodeStack.empty())
1622	{
1623	VspNode *node = nodeStack.top();
1624
1625	nodeStack.pop();
1626
1627	if (node->IsLeaf())
1628	{
1629	return dynamic_cast<VspLeaf *>(node);
1630	}
1631	else
1632	{
1633	VspInterior interior = dynamic_cast<VspInterior >(node);
1634	VspNode *next;
1635
1636	if (GetBBox(interior->GetBack()).Side(plane) < 0)
1637	{
1638	next = interior->GetFront();
1639	}
1640	else
1641	{
1642	if (GetBBox(interior->GetFront()).Side(plane) < 0)
1643	{
1644	next = interior->GetBack();
1645	}
1646	else
1647	{
1648	// random decision
1649	if (mask & 1)
1650	next = interior->GetBack();
1651	else
1652	next = interior->GetFront();
1653	mask = mask >> 1;
1654	}
1655	}
1656
1657	nodeStack.push(next);
1658	}
1659	}
1660
1661	return NULL;
1662	}
1663
1664
1665	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
1666	{
1667	stack<VspNode *> nodeStack;
1668
1669	nodeStack.push(mRoot);
1670
1671	int mask = rand();
1672
1673	while (!nodeStack.empty())
1674	{
1675	VspNode *node = nodeStack.top();
1676	nodeStack.pop();
1677
1678	if (node->IsLeaf())
1679	{
1680	if ( (!onlyUnmailed \|\| !node->Mailed()) )
1681	return dynamic_cast<VspLeaf *>(node);
1682	}
1683	else
1684	{
1685	VspInterior interior = dynamic_cast<VspInterior >(node);
1686
1687	// random decision
1688	if (mask & 1)
1689	nodeStack.push(interior->GetBack());
1690	else
1691	nodeStack.push(interior->GetFront());
1692
1693	mask = mask >> 1;
1694	}
1695	}
1696
1697	return NULL;
1698	}
1699
1700
1701	int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
1702	{
1703	int pvsSize = 0;
1704
1705	RayInfoContainer::const_iterator rit, rit_end = rays.end();
1706
1707	Intersectable::NewMail();
1708
1709	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1710	{
1711	VssRay ray = (rit).mRay;
1712
1713	if (ray->mOriginObject)
1714	{
1715	if (!ray->mOriginObject->Mailed())
1716	{
1717	ray->mOriginObject->Mail();
1718	++ pvsSize;
1719	}
1720	}
1721	if (ray->mTerminationObject)
1722	{
1723	if (!ray->mTerminationObject->Mailed())
1724	{
1725	ray->mTerminationObject->Mail();
1726	++ pvsSize;
1727	}
1728	}
1729	}
1730
1731	return pvsSize;
1732	}
1733
1734
1735	float VspTree::GetEpsilon() const
1736	{
1737	return mEpsilon;
1738	}
1739
1740
1741	int VspTree::CastLineSegment(const Vector3 &origin,
1742	const Vector3 &termination,
1743	ViewCellContainer &viewcells)
1744	{
1745	int hits = 0;
1746
1747	float mint = 0.0f, maxt = 1.0f;
1748	const Vector3 dir = termination - origin;
1749
1750	stack<LineTraversalData> tStack;
1751
1752	Intersectable::NewMail();
1753	ViewCell::NewMail();
1754
1755	Vector3 entp = origin;
1756	Vector3 extp = termination;
1757
1758	VspNode *node = mRoot;
1759	VspNode *farChild;
1760
1761	float position;
1762	int axis;
1763
1764	while (1)
1765	{
1766	if (!node->IsLeaf())
1767	{
1768	VspInterior in = dynamic_cast<VspInterior >(node);
1769	position = in->GetPosition();
1770	axis = in->GetAxis();
1771
1772	if (entp[axis] <= position)
1773	{
1774	if (extp[axis] <= position)
1775	{
1776	node = in->GetBack();
1777	// cases N1,N2,N3,P5,Z2,Z3
1778	continue;
1779	} else
1780	{
1781	// case N4
1782	node = in->GetBack();
1783	farChild = in->GetFront();
1784	}
1785	}
1786	else
1787	{
1788	if (position <= extp[axis])
1789	{
1790	node = in->GetFront();
1791	// cases P1,P2,P3,N5,Z1
1792	continue;
1793	}
1794	else
1795	{
1796	node = in->GetFront();
1797	farChild = in->GetBack();
1798	// case P4
1799	}
1800	}
1801
1802	// $$ modification 3.5.2004 - hints from Kamil Ghais
1803	// case N4 or P4
1804	const float tdist = (position - origin[axis]) / dir[axis];
1805	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
1806
1807	extp = origin + dir * tdist;
1808	maxt = tdist;
1809	}
1810	else
1811	{
1812	// compute intersection with all objects in this leaf
1813	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1814	ViewCell *vc = leaf->GetViewCell();
1815
1816	if (!vc->Mailed())
1817	{
1818	vc->Mail();
1819	viewcells.push_back(vc);
1820	++ hits;
1821	}
1822	#if 0
1823	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
1824	#endif
1825	// get the next node from the stack
1826	if (tStack.empty())
1827	break;
1828
1829	entp = extp;
1830	mint = maxt;
1831
1832	LineTraversalData &s = tStack.top();
1833	node = s.mNode;
1834	extp = s.mExitPoint;
1835	maxt = s.mMaxT;
1836	tStack.pop();
1837	}
1838	}
1839
1840	return hits;
1841	}
1842
1843
1844	int VspTree::CastRay(Ray &ray)
1845	{
1846	int hits = 0;
1847
1848	stack<LineTraversalData> tStack;
1849	const Vector3 dir = ray.GetDir();
1850
1851	float maxt, mint;
1852
1853	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
1854	return 0;
1855
1856	Intersectable::NewMail();
1857	ViewCell::NewMail();
1858
1859	Vector3 entp = ray.Extrap(mint);
1860	Vector3 extp = ray.Extrap(maxt);
1861
1862	const Vector3 origin = entp;
1863
1864	VspNode *node = mRoot;
1865	VspNode *farChild = NULL;
1866
1867	float position;
1868	int axis;
1869
1870	while (1)
1871	{
1872	if (!node->IsLeaf())
1873	{
1874	VspInterior in = dynamic_cast<VspInterior >(node);
1875	position = in->GetPosition();
1876	axis = in->GetAxis();
1877
1878	if (entp[axis] <= position)
1879	{
1880	if (extp[axis] <= position)
1881	{
1882	node = in->GetBack();
1883	// cases N1,N2,N3,P5,Z2,Z3
1884	continue;
1885	}
1886	else
1887	{
1888	// case N4
1889	node = in->GetBack();
1890	farChild = in->GetFront();
1891	}
1892	}
1893	else
1894	{
1895	if (position <= extp[axis])
1896	{
1897	node = in->GetFront();
1898	// cases P1,P2,P3,N5,Z1
1899	continue;
1900	}
1901	else
1902	{
1903	node = in->GetFront();
1904	farChild = in->GetBack();
1905	// case P4
1906	}
1907	}
1908
1909	// $$ modification 3.5.2004 - hints from Kamil Ghais
1910	// case N4 or P4
1911	const float tdist = (position - origin[axis]) / dir[axis];
1912	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
1913	extp = origin + dir * tdist;
1914	maxt = tdist;
1915	}
1916	else
1917	{
1918	// compute intersection with all objects in this leaf
1919	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
1920	ViewCell *vc = leaf->GetViewCell();
1921
1922	if (!vc->Mailed())
1923	{
1924	vc->Mail();
1925	// todo: add view cells to ray
1926	++ hits;
1927	}
1928	#if 0
1929	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
1930	#endif
1931	// get the next node from the stack
1932	if (tStack.empty())
1933	break;
1934
1935	entp = extp;
1936	mint = maxt;
1937
1938	LineTraversalData &s = tStack.top();
1939	node = s.mNode;
1940	extp = s.mExitPoint;
1941	maxt = s.mMaxT;
1942	tStack.pop();
1943	}
1944	}
1945
1946	return hits;
1947	}
1948
1949
1950	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
1951	{
1952	if (mRoot == NULL)
1953	return NULL;
1954
1955	stack<VspNode *> nodeStack;
1956	nodeStack.push(mRoot);
1957
1958	ViewCellLeaf *viewcell = NULL;
1959
1960	while (!nodeStack.empty())
1961	{
1962	VspNode *node = nodeStack.top();
1963	nodeStack.pop();
1964
1965	if (node->IsLeaf())
1966	{
1967	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1968	break;
1969	}
1970	else
1971	{
1972	VspInterior interior = dynamic_cast<VspInterior >(node);
1973
1974	// random decision
1975	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
1976	nodeStack.push(interior->GetBack());
1977	else
1978	nodeStack.push(interior->GetFront());
1979	}
1980	}
1981
1982	if (active)
1983	return mViewCellsTree->GetActiveViewCell(viewcell);
1984	else
1985	return viewcell;
1986	}
1987
1988
1989	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
1990	{
1991	VspNode *node = mRoot;
1992
1993	while (1)
1994	{
1995	// early exit
1996	if (node->TreeValid())
1997	return true;
1998
1999	if (node->IsLeaf())
2000	return false;
2001
2002	VspInterior in = dynamic_cast<VspInterior >(node);
2003
2004	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2005	{
2006	node = in->GetBack();
2007	}
2008	else
2009	{
2010	node = in->GetFront();
2011	}
2012	}
2013
2014	// should never come here
2015	return false;
2016	}
2017
2018
2019	void VspTree::PropagateUpValidity(VspNode *node)
2020	{
2021	const bool isValid = node->TreeValid();
2022
2023	// propagative up invalid flag until only invalid nodes exist over this node
2024	if (!isValid)
2025	{
2026	while (!node->IsRoot() && node->GetParent()->TreeValid())
2027	{
2028	node = node->GetParent();
2029	node->SetTreeValid(false);
2030	}
2031	}
2032	else
2033	{
2034	// propagative up valid flag until one of the subtrees is invalid
2035	while (!node->IsRoot() && !node->TreeValid())
2036	{
2037	node = node->GetParent();
2038	VspInterior interior = dynamic_cast<VspInterior >(node);
2039
2040	// the parent is valid iff both leaves are valid
2041	node->SetTreeValid(interior->GetBack()->TreeValid() &&
2042	interior->GetFront()->TreeValid());
2043	}
2044	}
2045	}
2046
2047	#if ZIPPED_VIEWCELLS
2048	bool VspTree::Export(ogzstream &stream)
2049	#else
2050	bool VspTree::Export(ofstream &stream)
2051	#endif
2052	{
2053	ExportNode(mRoot, stream);
2054
2055	return true;
2056	}
2057
2058
2059	#if ZIPPED_VIEWCELLS
2060	void VspTree::ExportNode(VspNode *node, ogzstream &stream)
2061	#else
2062	void VspTree::ExportNode(VspNode *node, ofstream &stream)
2063	#endif
2064	{
2065	if (node->IsLeaf())
2066	{
2067	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
2068	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2069
2070	int id = -1;
2071	if (viewCell != mOutOfBoundsCell)
2072	id = viewCell->GetId();
2073
2074	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2075	}
2076	else
2077	{
2078	VspInterior interior = dynamic_cast<VspInterior >(node);
2079
2080	AxisAlignedPlane plane = interior->GetPlane();
2081	stream << "<Interior plane=\"" << plane.mPosition << " "
2082	<< plane.mAxis << "\">" << endl;
2083
2084	ExportNode(interior->GetBack(), stream);
2085	ExportNode(interior->GetFront(), stream);
2086
2087	stream << "</Interior>" << endl;
2088	}
2089	}
2090
2091
2092	int VspTree::SplitRays(const AxisAlignedPlane &plane,
2093	RayInfoContainer &rays,
2094	RayInfoContainer &frontRays,
2095	RayInfoContainer &backRays) const
2096	{
2097	int splits = 0;
2098
2099	RayInfoContainer::const_iterator rit, rit_end = rays.end();
2100
2101	for (rit = rays.begin(); rit != rit_end; ++ rit)
2102	{
2103	RayInfo bRay = *rit;
2104
2105	VssRay *ray = bRay.mRay;
2106	float t;
2107
2108	// get classification and receive new t
2109	//-- test if start point behind or in front of plane
2110	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2111
2112
2113	#if 1
2114	if (side == 0)
2115	{
2116	++ splits;
2117
2118	if (ray->HasPosDir(plane.mAxis))
2119	{
2120	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2121	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2122	}
2123	else
2124	{
2125	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2126	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2127	}
2128	}
2129	else if (side == 1)
2130	{
2131	frontRays.push_back(bRay);
2132	}
2133	else
2134	{
2135	backRays.push_back(bRay);
2136	}
2137	#else
2138	if (side == 0)
2139	{
2140	++ splits;
2141
2142	if (ray->HasPosDir(plane.mAxis))
2143	{
2144	backRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
2145	frontRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
2146	}
2147	else
2148	{
2149	frontRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
2150	backRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
2151	}
2152	}
2153	else if (side == 1)
2154	{
2155	backRays.push_back(bRay);
2156	}
2157	else
2158	{
2159	frontRays.push_back(bRay);
2160
2161	}
2162	#endif
2163	}
2164
2165	return splits;
2166	}
2167
2168
2169	AxisAlignedBox3 VspTree::GetBBox(VspNode *node) const
2170	{
2171	if (!node->GetParent())
2172	return mBoundingBox;
2173
2174	if (!node->IsLeaf())
2175	{
2176	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
2177	}
2178
2179	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
2180
2181	AxisAlignedBox3 box(parent->GetBoundingBox());
2182
2183	if (parent->GetFront() == node)
2184	box.SetMin(parent->GetAxis(), parent->GetPosition());
2185	else
2186	box.SetMax(parent->GetAxis(), parent->GetPosition());
2187
2188	return box;
2189	}
2190
2191
2192
2193
2194	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2195	ViewCellContainer &viewCells) const
2196	{
2197	stack<VspNode *> nodeStack;
2198
2199	ViewCell::NewMail();
2200
2201	while (!nodeStack.empty())
2202	{
2203	VspNode *node = nodeStack.top();
2204	nodeStack.pop();
2205
2206	const AxisAlignedBox3 bbox = GetBBox(node);
2207
2208	if (bbox.Includes(box))
2209	{
2210	// node geometry is contained in box
2211	CollectViewCells(node, true, viewCells, true);
2212	}
2213	else if (Overlap(bbox, box))
2214	{
2215	if (node->IsLeaf())
2216	{
2217	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
2218
2219	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2220	{
2221	leaf->GetViewCell()->Mail();
2222	viewCells.push_back(leaf->GetViewCell());
2223	}
2224	}
2225	else
2226	{
2227	VspInterior interior = dynamic_cast<VspInterior >(node);
2228
2229	VspNode *first = interior->GetFront();
2230	VspNode *second = interior->GetBack();
2231
2232	nodeStack.push(first);
2233	nodeStack.push(second);
2234	}
2235	}
2236	// default: cull
2237	}
2238
2239	return (int)viewCells.size();
2240	}
2241
2242
2243
2244	/*****************************************************************/
2245	/* class OspTree implementation */
2246	/*****************************************************************/
2247
2248
2249	OspTree::OspTree():
2250	mRoot(NULL)
2251	#if TODO
2252	mOutOfBoundsCell(NULL),
2253	mStoreRays(false),
2254	mUseRandomAxis(false),
2255	mTimeStamp(1)
2256	#endif
2257	{
2258	#if TODO
2259	bool randomize = false;
2260	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
2261	if (randomize)
2262	Randomize(); // initialise random generator for heuristics
2263
2264	//-- termination criteria for autopartition
2265	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
2266	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
2267	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
2268	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
2269	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
2270
2271	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
2272	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
2273
2274	//-- max cost ratio for early tree termination
2275	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
2276
2277	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
2278	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
2279
2280	// HACK//mTermMinPolygons = 25;
2281
2282	//-- factors for bsp tree split plane heuristics
2283	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
2284
2285	//-- partition criteria
2286	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
2287
2288	// if only the driving axis is used for axis aligned split
2289	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
2290
2291	//Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
2292	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
2293
2294	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
2295	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
2296
2297
2298	char subdivisionStatsLog[100];
2299	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
2300	mSubdivisionStats.open(subdivisionStatsLog);
2301
2302	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
2303	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
2304
2305
2306	//-- debug output
2307
2308	Debug << "***** VSP BSP options ****** " << endl;
2309	Debug << "max depth: " << mTermMaxDepth << endl;
2310	Debug << "min PVS: " << mTermMinPvs << endl;
2311	Debug << "min probabiliy: " << mTermMinProbability << endl;
2312	Debug << "min rays: " << mTermMinRays << endl;
2313	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
2314	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
2315	Debug << "miss tolerance: " << mTermMissTolerance << endl;
2316	Debug << "max view cells: " << mMaxViewCells << endl;
2317	Debug << "randomize: " << randomize << endl;
2318
2319	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
2320	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
2321	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
2322	Debug << "max memory: " << mMaxMemory << endl;
2323	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
2324	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
2325
2326	Debug << "circulating axis: " << mCirculatingAxis << endl;
2327	Debug << "minband: " << mMinBand << endl;
2328	Debug << "maxband: " << mMaxBand << endl;
2329
2330
2331	mSplitCandidates = new vector<SortableEntry>;
2332
2333	Debug << endl;
2334	#endif
2335	}
2336
2337
2338
2339	void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
2340	const ObjectContainer &objects,
2341	ObjectContainer &back,
2342	ObjectContainer &front)
2343	{
2344	ObjectContainer::const_iterator oit, oit_end = objects.end();
2345
2346	for (oit = objects.begin(); oit != oit_end; ++ oit)
2347	{
2348	// determine the side of this ray with respect to the plane
2349	const AxisAlignedBox3 box = (*oit)->GetBox();
2350
2351	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
2352	front.push_back(*oit);
2353
2354	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
2355	back.push_back(*oit);
2356	#if TODO
2357	mStat.objectRefs -= (int)objects.size();
2358	mStat.objectRefs += objectsBack + objectsFront;
2359	#endif
2360	}
2361	}
2362
2363
2364	KdInterior OspTree::SubdivideNode(KdLeaf leaf,
2365	const AxisAlignedPlane &splitPlane,
2366	const AxisAlignedBox3 &box,
2367	AxisAlignedBox3 &backBBox,
2368	AxisAlignedBox3 &frontBBox)
2369	{
2370	#if TODO
2371	mSpatialStat.nodes += 2;
2372	mSpatialStat.splits[axis];
2373	#endif
2374
2375	// add the new nodes to the tree
2376	KdInterior *node = new KdInterior(leaf->mParent);
2377
2378	const int axis = splitPlane.mAxis;
2379	const float position = splitPlane.mPosition;
2380
2381	node->mAxis = axis;
2382	node->mPosition = position;
2383	node->mBox = box;
2384
2385	backBBox = box;
2386	frontBBox = box;
2387
2388	// first count ray sides
2389	int objectsBack = 0;
2390	int objectsFront = 0;
2391
2392	backBBox.SetMax(axis, position);
2393	frontBBox.SetMin(axis, position);
2394
2395	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
2396
2397	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
2398	{
2399	// determine the side of this ray with respect to the plane
2400	const AxisAlignedBox3 box = (*mi)->GetBox();
2401
2402	if (box.Max(axis) > position)
2403	++ objectsFront;
2404
2405	if (box.Min(axis) < position)
2406	++ objectsBack;
2407	}
2408
2409	KdLeaf *back = new KdLeaf(node, objectsBack);
2410	KdLeaf *front = new KdLeaf(node, objectsFront);
2411
2412	// replace a link from node's parent
2413	if (leaf->mParent)
2414	leaf->mParent->ReplaceChildLink(leaf, node);
2415
2416	// and setup child links
2417	node->SetupChildLinks(back, front);
2418
2419	SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
2420
2421	//delete leaf;
2422	return node;
2423	}
2424
2425
2426	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
2427	OspSplitCandidate &splitCandidate,
2428	const bool globalCriteriaMet)
2429	{
2430	OspTraversalData &tData = splitCandidate.mParentData;
2431
2432	KdNode *newNode = tData.mNode;
2433
2434	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
2435	{
2436	OspTraversalData tFrontData;
2437	OspTraversalData tBackData;
2438
2439	//-- continue subdivision
2440
2441	// create new interior node and two leaf node
2442	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
2443
2444	newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode),
2445	splitPlane,
2446	tData.mBoundingBox,
2447	tFrontData.mBoundingBox,
2448	tBackData.mBoundingBox);
2449
2450	const int maxCostMisses = splitCandidate.mMaxCostMisses;
2451
2452	// how often was max cost ratio missed in this branch?
2453	tFrontData.mMaxCostMisses = maxCostMisses;
2454	tBackData.mMaxCostMisses = maxCostMisses;
2455
2456	//-- push the new split candidates on the queue
2457	OspSplitCandidate *frontCandidate = new OspSplitCandidate();
2458	OspSplitCandidate *backCandidate = new OspSplitCandidate();
2459
2460	EvalSplitCandidate(tFrontData, *frontCandidate);
2461	EvalSplitCandidate(tBackData, *backCandidate);
2462
2463	tQueue.push(frontCandidate);
2464	tQueue.push(backCandidate);
2465
2466	// delete old leaf node
2467	DEL_PTR(tData.mNode);
2468	}
2469
2470
2471	//-- terminate traversal
2472	if (newNode->IsLeaf())
2473	{
2474	//KdLeaf leaf = dynamic_cast<KdLeaf >(newNode);
2475	EvaluateLeafStats(tData);
2476	}
2477
2478	//-- cleanup
2479	tData.Clear();
2480
2481	return newNode;
2482	}
2483
2484
2485	void OspTree::EvalSplitCandidate(OspTraversalData &tData,
2486	OspSplitCandidate &splitData)
2487	{
2488	float frontProb;
2489	float backtProb;
2490
2491	KdLeaf leaf = dynamic_cast<KdLeaf >(tData.mNode);
2492
2493	// compute locally best split plane
2494	const bool success = false;
2495	#if TODO
2496	SelectPlane(tData, splitData.mSplitPlane,
2497	frontData.mProbability, backData.mProbability);
2498
2499	//TODO
2500	// compute global decrease in render cost
2501	splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
2502	splitData.mParentData = tData;
2503	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
2504	#endif
2505	}
2506
2507
2508	bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
2509	{
2510	// matt: TODO
2511	return true;
2512	/* (((int)data.mRays->size() <= mTermMinRays) \|\|
2513	(data.mPvs <= mTermMinPvs) \|\|
2514	(data.mProbability <= mTermMinProbability) \|\|
2515	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
2516	(data.mDepth >= mTermMaxDepth));*/
2517	}
2518
2519
2520	bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
2521	{
2522	// matt: TODO
2523	return true;
2524	/*(mOutOfMemory \|\|
2525	(mVspStats.Leaves() >= mMaxViewCells) \|\|
2526	(mGlobalCostMisses >= mTermGlobalCostMissTolerance));*/
2527	}
2528
2529
2530	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
2531	{
2532	#if TODO
2533	// the node became a leaf -> evaluate stats for leafs
2534	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
2535
2536	if (data.mPvs > mVspStats.maxPvs)
2537	{
2538	mVspStats.maxPvs = data.mPvs;
2539	}
2540
2541	mVspStats.pvs += data.mPvs;
2542
2543	if (data.mDepth < mVspStats.minDepth)
2544	{
2545	mVspStats.minDepth = data.mDepth;
2546	}
2547
2548	if (data.mDepth >= mTermMaxDepth)
2549	{
2550	++ mVspStats.maxDepthNodes;
2551	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
2552	}
2553
2554	// accumulate rays to compute rays / leaf
2555	mVspStats.accumRays += (int)data.mRays->size();
2556
2557	if (data.mPvs < mTermMinPvs)
2558	++ mVspStats.minPvsNodes;
2559
2560	if ((int)data.mRays->size() < mTermMinRays)
2561	++ mVspStats.minRaysNodes;
2562
2563	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
2564	++ mVspStats.maxRayContribNodes;
2565
2566	if (data.mProbability <= mTermMinProbability)
2567	++ mVspStats.minProbabilityNodes;
2568
2569	// accumulate depth to compute average depth
2570	mVspStats.accumDepth += data.mDepth;
2571
2572	++ mCreatedViewCells;
2573
2574	#ifdef _DEBUG
2575	Debug << "BSP stats: "
2576	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
2577	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
2578	// << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
2579	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
2580	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
2581	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
2582	#endif
2583
2584	#endif
2585	}
2586
2587
2588	/*********************************************************************/
2589	/* class HierarchyManager implementation */
2590	/*********************************************************************/
2591
2592	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
2593	mVspTree(vspTree), mOspTree(ospTree)
2594	{
2595	}
2596
2597
2598	SplitCandidate *HierarchyManager::NextSplitCandidate()
2599	{
2600	SplitCandidate *splitCandidate = mTQueue.top();
2601	Debug << "priority: " << splitCandidate->GetPriority() << endl;
2602	mTQueue.pop();
2603
2604	return splitCandidate;
2605	}
2606
2607
2608	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
2609	const ObjectContainer &objects,
2610	AxisAlignedBox3 *forcedViewSpace,
2611	RayInfoContainer &rays)
2612	{
2613	mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
2614
2615	long startTime = GetTime();
2616
2617	cout << "storing rays ... ";
2618
2619	Intersectable::NewMail();
2620
2621	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2622
2623	//-- store rays
2624	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2625	{
2626	VssRay ray = rit;
2627
2628	float minT, maxT;
2629
2630	static Ray hray;
2631	hray.Init(*ray);
2632
2633	// TODO: not very efficient to implictly cast between rays types
2634	if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
2635	{
2636	float len = ray->Length();
2637
2638	if (!len)
2639	len = Limits::Small;
2640
2641	rays.push_back(RayInfo(ray, minT / len, maxT / len));
2642	}
2643	}
2644
2645	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2646
2647	/// add first candidate for view space partition
2648	mVspTree.mRoot = new VspLeaf();
2649	const float prop = mVspTree.mBoundingBox.GetVolume();
2650
2651	/// first traversal data
2652	VspTree::VspTraversalData tData(mVspTree.mRoot,
2653	0,
2654	&rays,
2655	(int)objects.size(),
2656	//mVspTree.ComputePvsSize(rays),
2657	prop,
2658	mVspTree.mBoundingBox);
2659
2660	// compute first split candidate
2661	VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate();
2662	mVspTree.EvalSplitCandidate(tData, *splitCandidate);
2663
2664	mTQueue.push(splitCandidate);
2665
2666	//mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
2667	}
2668
2669
2670	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
2671	{
2672	if (candidate->Type() == SplitCandidate::VIEW_SPACE)
2673	{
2674	VspTree::VspSplitCandidate *sc =
2675	dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
2676
2677	return mVspTree.GlobalTerminationCriteriaMet(sc->mParentData);
2678	}
2679
2680	return true;
2681	}
2682
2683
2684	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
2685	const ObjectContainer &objects,
2686	AxisAlignedBox3 *forcedViewSpace)
2687	{
2688	RayInfoContainer *rays = new RayInfoContainer();
2689
2690	// prepare vsp and osp trees for traversal
2691	PrepareConstruction(sampleRays, objects, forcedViewSpace, *rays);
2692
2693	mVspTree.mVspStats.Reset();
2694	mVspTree.mVspStats.Start();
2695
2696	cout << "Constructing view space / object space tree ... \n";
2697	const long startTime = GetTime();
2698
2699	while (!FinishedConstruction())
2700	{
2701	SplitCandidate *splitCandidate = NextSplitCandidate();
2702
2703	const bool globalTerminationCriteriaMet =
2704	GlobalTerminationCriteriaMet(splitCandidate);
2705
2706	Debug << "cost: " << splitCandidate->GetPriority();
2707
2708	// cost ratio of cost decrease / totalCost
2709	const float costRatio = splitCandidate->GetPriority() / mTotalCost;
2710	//Debug << "cost ratio: " << costRatio << endl;
2711
2712	if (costRatio < mTermMinGlobalCostRatio)
2713	++ mGlobalCostMisses;
2714
2715	//-- subdivide leaf node
2716	//-- either a object space or view space split
2717	if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
2718	{
2719	VspTree::VspSplitCandidate *sc =
2720	dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
2721
2722	VspNode r = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
2723	}
2724	else // object space split
2725	{
2726	#if TODO
2727	KdNode *r = mKdtree.Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
2728	#endif
2729	}
2730
2731	DEL_PTR(splitCandidate);
2732	}
2733
2734	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
2735
2736	mVspTree.mVspStats.Stop();
2737	}
2738
2739
2740	bool HierarchyManager::FinishedConstruction()
2741	{
2742	return mTQueue.empty();
2743	}
2744
2745
2746	}

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

Download in other formats: