Context Navigation

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

Revision 1168, 113.9 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: