Context Navigation

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

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

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

Download in other formats: