Context Navigation

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

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

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

Download in other formats: