Context Navigation

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

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

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

Download in other formats: