Context Navigation

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

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

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

Download in other formats: