Context Navigation

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

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

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

Download in other formats: