Context Navigation

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

Revision 1146, 113.3 KB checked in by mattausch, 18 years ago (diff)
use qt renderer as dll changed vsp render heuristics sweep capsulated thread

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

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

Download in other formats: