Context Navigation

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

Revision 1021, 62.8 KB checked in by mattausch, 18 years ago (diff)
added view cells manager for vsposptree

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

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

Download in other formats: