Context Navigation

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

Revision 1072, 76.2 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: