Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp @ 1909

Revision 1909, 72.8 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "BvHierarchy.h"
6	#include "ViewCell.h"
7	#include "Plane3.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 "VspTree.h"
19	#include "HierarchyManager.h"
20
21
22	namespace GtpVisibilityPreprocessor {
23
24
25	#define PROBABILIY_IS_BV_VOLUME 1
26	#define USE_FIXEDPOINT_T 0
27	#define USE_VOLUMES_FOR_HEURISTICS 1
28
29	//int BvhNode::sMailId = 10000; //2147483647;
30	//int BvhNode::sReservedMailboxes = 1;
31
32	BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;
33
34
35	/// sorting operator
36	inline static bool ilt(Intersectable obj1, Intersectable obj2)
37	{
38	return obj1->mId < obj2->mId;
39	}
40
41
42	/// sorting operator
43	inline static bool smallerSize(Intersectable obj1, Intersectable obj2)
44	{
45	return obj1->GetBox().SurfaceArea() < obj2->GetBox().SurfaceArea();
46	}
47
48
49
50	/***************************************************************/
51	/* class BvhNode implementation */
52	/***************************************************************/
53
54	BvhNode::BvhNode():
55	mParent(NULL),
56	mTimeStamp(0),
57	mRenderCost(-1)
58
59	{
60
61	}
62
63	BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
64	mParent(NULL),
65	mBoundingBox(bbox),
66	mTimeStamp(0),
67	mRenderCost(-1)
68	{
69	}
70
71
72	BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
73	mBoundingBox(bbox),
74	mParent(parent),
75	mTimeStamp(0),
76	mRenderCost(-1)
77	{
78	}
79
80
81	bool BvhNode::IsRoot() const
82	{
83	return mParent == NULL;
84	}
85
86
87	BvhInterior *BvhNode::GetParent()
88	{
89	return mParent;
90	}
91
92
93	void BvhNode::SetParent(BvhInterior *parent)
94	{
95	mParent = parent;
96	}
97
98
99	int BvhNode::GetRandomEdgePoint(Vector3 &point,
100	Vector3 &normal)
101	{
102	// get random edge
103	const int idx = Random(12);
104	Vector3 a, b;
105	mBoundingBox.GetEdge(idx, &a, &b);
106
107	const float w = RandomValue(0.0f, 1.0f);
108
109	point = a * w + b * (1.0f - w);
110
111	// TODO
112	normal = Vector3(0);
113
114	return idx;
115	}
116
117
118
119	/******************************************************************/
120	/* class BvhInterior implementation */
121	/******************************************************************/
122
123
124	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
125	BvhNode(bbox),
126	mSubdivisionCandidate(NULL),
127	mGlList(0)
128	{
129	mActiveNode = this;
130	}
131
132
133	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
134	BvhNode(bbox, parent),
135	mGlList(0)
136
137	{
138	mActiveNode = this;
139	}
140
141
142	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox,
143	BvhInterior *parent,
144	const int numObjects):
145	BvhNode(bbox, parent),
146	mGlList(0)
147
148	{
149	mObjects.reserve(numObjects);
150	mActiveNode = this;
151	}
152
153
154	bool BvhLeaf::IsLeaf() const
155	{
156	return true;
157	}
158
159
160	BvhLeaf::~BvhLeaf()
161	{
162	}
163
164
165	void BvhLeaf::CollectObjects(ObjectContainer &objects)
166	{
167	ObjectContainer::const_iterator oit, oit_end = mObjects.end();
168	for (oit = mObjects.begin(); oit != oit_end; ++ oit)
169	{
170	objects.push_back(*oit);
171	}
172	}
173
174	/******************************************************************/
175	/* class BvhInterior implementation */
176	/******************************************************************/
177
178
179	BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
180	BvhNode(bbox), mFront(NULL), mBack(NULL)
181	{
182	}
183
184
185	BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
186	BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
187	{
188	}
189
190
191	void BvhInterior::ReplaceChildLink(BvhNode oldChild, BvhNode newChild)
192	{
193	if (mBack == oldChild)
194	mBack = newChild;
195	else
196	mFront = newChild;
197	}
198
199
200	bool BvhInterior::IsLeaf() const
201	{
202	return false;
203	}
204
205
206	BvhInterior::~BvhInterior()
207	{
208	DEL_PTR(mFront);
209	DEL_PTR(mBack);
210	}
211
212
213	void BvhInterior::SetupChildLinks(BvhNode front, BvhNode back)
214	{
215	mBack = back;
216	mFront = front;
217	}
218
219
220	void BvhInterior::CollectObjects(ObjectContainer &objects)
221	{
222	mFront->CollectObjects(objects);
223	mBack->CollectObjects(objects);
224	}
225
226
227	/*******************************************************************/
228	/* class BvHierarchy implementation */
229	/*******************************************************************/
230
231
232	BvHierarchy::BvHierarchy():
233	mRoot(NULL),
234	mTimeStamp(1),
235	mIsInitialSubdivision(false)
236	{
237	ReadEnvironment();
238	mSubdivisionCandidates = new SortableEntryContainer;
239	// for (int i = 0; i < 4; ++ i)
240	// mSortedObjects[i] = NULL;
241	}
242
243
244	BvHierarchy::~BvHierarchy()
245	{
246	// delete the local subdivision candidates
247	DEL_PTR(mSubdivisionCandidates);
248
249	// delete the presorted objects
250	/*for (int i = 0; i < 4; ++ i)
251	{
252	DEL_PTR(mSortedObjects[i]);
253	}*/
254
255	// delete the tree
256	DEL_PTR(mRoot);
257	}
258
259
260	void BvHierarchy::ReadEnvironment()
261	{
262	bool randomize = false;
263	Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.randomize", randomize);
264
265	// initialise random generator for heuristics
266	if (randomize)
267	Randomize();
268
269	//////////////////////////////
270	//-- termination criteria for autopartition
271
272	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
273	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
274	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
275	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
276	Environment::GetSingleton()->GetFloatValue(
277	"BvHierarchy.Termination.minProbability", mTermMinProbability);
278	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);
279
280
281	//////////////////////////////
282	//-- max cost ratio for early tree termination
283
284	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);
285	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
286	mTermMinGlobalCostRatio);
287	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance",
288	mTermGlobalCostMissTolerance);
289
290
291	//////////////////////////////
292	//-- factors for subdivision heuristics
293
294	// if only the driving axis is used for splits
295	Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
296	Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
297	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);
298	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useSah", mUseSah);
299
300	char subdivisionStatsLog[100];
301	Environment::GetSingleton()->GetStringValue("BvHierarchy.subdivisionStats", subdivisionStatsLog);
302	mSubdivisionStats.open(subdivisionStatsLog);
303
304	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
305	Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
306	Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
307	Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests);
308	Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useInitialSubdivision", mApplyInitialPartition);
309	Environment::GetSingleton()->GetIntValue("BvHierarchy.Construction.Initial.minObjects", mInitialMinObjects);
310	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.Initial.maxAreaRatio", mInitialMaxAreaRatio);
311	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.Initial.minArea", mInitialMinArea);
312
313	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
314	//mMemoryConst = (float)sizeof(BvhLeaf);
315	mMemoryConst = 16;//(float)sizeof(ObjectContainer);
316
317	mUseBboxAreaForSah = true;
318
319	/////////////
320	//-- debug output
321
322	Debug << "***** Bvh hierarchy options ****** " << endl;
323	Debug << "max depth: " << mTermMaxDepth << endl;
324	Debug << "min probabiliy: " << mTermMinProbability<< endl;
325	Debug << "min objects: " << mTermMinObjects << endl;
326	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
327	Debug << "miss tolerance: " << mTermMissTolerance << endl;
328	Debug << "max leaves: " << mTermMaxLeaves << endl;
329	Debug << "randomize: " << randomize << endl;
330	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
331	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
332	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
333	Debug << "max memory: " << mMaxMemory << endl;
334	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
335	Debug << "use surface area heuristics: " << mUseSah << endl;
336	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
337	Debug << "split borders: " << mSplitBorder << endl;
338	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
339	Debug << "use global sort: " << mUseGlobalSorting << endl;
340	Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
341	Debug << "bvh mem const: " << mMemoryConst << endl;
342	Debug << "apply initial partition: " << mApplyInitialPartition << endl;
343	Debug << "min objects: " << mInitialMinObjects << endl;
344	Debug << "max area ratio: " << mInitialMaxAreaRatio << endl;
345	Debug << "min area: " << mInitialMinArea << endl;
346
347	Debug << endl;
348	}
349
350
351	void BvHierarchy::AssociateObjectsWithLeaf(BvhLeaf *leaf)
352	{
353	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
354
355	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
356	{
357	(*oit)->mBvhLeaf = leaf;
358	}
359	}
360
361
362	static int CountRays(const ObjectContainer &objects)
363	{
364	int nRays = 0;
365
366	ObjectContainer::const_iterator oit, oit_end = objects.end();
367
368	for (oit = objects.begin(); oit != oit_end; ++ oit)
369	{
370	nRays += (int)(*oit)->GetOrCreateRays()->size();
371	}
372
373	return nRays;
374	}
375
376
377	BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
378	BvhTraversalData &frontData,
379	BvhTraversalData &backData)
380	{
381	const BvhTraversalData &tData = sc.mParentData;
382	BvhLeaf *leaf = tData.mNode;
383	AxisAlignedBox3 parentBox = leaf->GetBoundingBox();
384
385	// update stats: we have two new leaves
386	mBvhStats.nodes += 2;
387
388	if (tData.mDepth > mBvhStats.maxDepth)
389	{
390	mBvhStats.maxDepth = tData.mDepth;
391	}
392
393	// add the new nodes to the tree
394	BvhInterior *node = new BvhInterior(parentBox, leaf->GetParent());
395
396
397	//////////////////
398	//-- create front and back leaf
399
400	AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
401	AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);
402
403	BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
404	BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
405
406	BvhInterior *parent = leaf->GetParent();
407
408	// replace a link from node's parent
409	if (parent)
410	{
411	parent->ReplaceChildLink(leaf, node);
412	node->SetParent(parent);
413	}
414	else // no parent => this node is the root
415	{
416	mRoot = node;
417	}
418
419	// and setup child links
420	node->SetupChildLinks(front, back);
421
422	++ mBvhStats.splits;
423
424
425	////////////////////////////////////////
426	//-- fill front and back traversal data with the new values
427
428	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
429
430	frontData.mNode = front;
431	backData.mNode = back;
432
433	back->mObjects = sc.mBackObjects;
434	front->mObjects = sc.mFrontObjects;
435
436	// if the number of rays is too low, no assumptions can be made
437	// (=> switch to surface area heuristics?)
438	frontData.mNumRays = CountRays(sc.mFrontObjects);
439	backData.mNumRays = CountRays(sc.mBackObjects);
440
441	AssociateObjectsWithLeaf(back);
442	AssociateObjectsWithLeaf(front);
443
444	#if PROBABILIY_IS_BV_VOLUME
445	// volume of bvh (= probability that this bvh can be seen)
446	frontData.mProbability = fbox.GetVolume();
447	backData.mProbability = bbox.GetVolume();
448	#else
449	// compute probability of this node being visible,
450	// i.e., volume of the view cells that can see this node
451	frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
452	backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
453	#endif
454
455	// how often was max cost ratio missed in this branch?
456	frontData.mMaxCostMisses = sc.GetMaxCostMisses();
457	backData.mMaxCostMisses = sc.GetMaxCostMisses();
458
459	// set the time stamp so the order of traversal can be reconstructed
460	node->SetTimeStamp(mHierarchyManager->mTimeStamp ++);
461
462	// assign the objects in sorted order
463	if (mUseGlobalSorting)
464	{
465	AssignSortedObjects(sc, frontData, backData);
466	}
467
468	// return the new interior node
469	return node;
470	}
471
472
473	BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
474	SubdivisionCandidate *splitCandidate,
475	const bool globalCriteriaMet)
476	{
477	BvhSubdivisionCandidate *sc =
478	dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
479	BvhTraversalData &tData = sc->mParentData;
480
481	BvhNode *currentNode = tData.mNode;
482
483	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
484	{
485	//////////////
486	//-- continue subdivision
487
488	BvhTraversalData tFrontData;
489	BvhTraversalData tBackData;
490
491	// create new interior node and two leaf node
492	currentNode = SubdivideNode(*sc, tFrontData, tBackData);
493
494	// decrease the weighted average cost of the subdivisoin
495	mTotalCost -= sc->GetRenderCostDecrease();
496	mPvsEntries += sc->GetPvsEntriesIncr();
497
498	// subdivision statistics
499	if (1) PrintSubdivisionStats(*sc);
500
501
502	///////////////////////////
503	//-- push the new split candidates on the queue
504
505	BvhSubdivisionCandidate *frontCandidate =
506	new BvhSubdivisionCandidate(tFrontData);
507	BvhSubdivisionCandidate *backCandidate =
508	new BvhSubdivisionCandidate(tBackData);
509
510	EvalSubdivisionCandidate(*frontCandidate);
511	EvalSubdivisionCandidate(*backCandidate);
512
513	// cross reference
514	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
515	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
516
517	//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
518	tQueue.Push(frontCandidate);
519	tQueue.Push(backCandidate);
520	}
521
522	/////////////////////////////////
523	//-- node is a leaf => terminate traversal
524
525	if (currentNode->IsLeaf())
526	{
527	/////////////////////
528	//-- store additional info
529	EvaluateLeafStats(tData);
530
531	// this leaf is no candidate for splitting anymore
532	// => detach subdivision candidate
533	tData.mNode->SetSubdivisionCandidate(NULL);
534	// detach node so we don't delete it with the traversal data
535	tData.mNode = NULL;
536	}
537
538	return currentNode;
539	}
540
541
542	float BvHierarchy::EvalPriority(const BvhSubdivisionCandidate &splitCandidate,
543	const float renderCostDecr,
544	const float oldRenderCost) const
545	{
546	float priority;
547
548	if (mIsInitialSubdivision)
549	{
550	priority = (float)-splitCandidate.mParentData.mDepth;
551	return priority;
552	}
553
554	BvhLeaf *leaf = splitCandidate.mParentData.mNode;
555
556	// surface area heuristics is used when there is
557	// no view space subdivision available.
558	// In order to have some prioritized traversal,
559	// we use this formula instead
560	if (mHierarchyManager->GetViewSpaceSubdivisionType() ==
561	HierarchyManager::NO_VIEWSPACE_SUBDIV)
562	{
563	priority = EvalSahCost(leaf);
564	}
565	else
566	{
567	// take render cost of node into account
568	// otherwise danger of being stuck in a local minimum!
569	const float factor = mRenderCostDecreaseWeight;
570
571	priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
572
573	if (mHierarchyManager->mConsiderMemory)
574	{
575	priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
576	}
577	}
578
579	// hack: don't allow empty splits to be taken
580	if (splitCandidate.mFrontObjects.empty() \|\| splitCandidate.mBackObjects.empty())
581	priority = 0;
582
583	return priority;
584	}
585
586
587	static float AvgRayContribution(const int pvs, const int nRays)
588	{
589	return (float)pvs / ((float)nRays + Limits::Small);
590	}
591
592
593	void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate,
594	bool computeSplitPlane)
595	{
596	if (computeSplitPlane)
597	{
598	const bool sufficientSamples =
599	splitCandidate.mParentData.mNumRays > mMinRaysForVisibility;
600
601	const bool useVisibiliyBasedHeuristics =
602	!mUseSah &&
603	(mHierarchyManager->GetViewSpaceSubdivisionType() ==
604	HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV) &&
605	sufficientSamples;
606
607	// compute best object partition
608	const float ratio = SelectObjectPartition(splitCandidate.mParentData,
609	splitCandidate.mFrontObjects,
610	splitCandidate.mBackObjects,
611	useVisibiliyBasedHeuristics);
612
613	// cost ratio violated?
614	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
615	const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;
616
617	splitCandidate.SetMaxCostMisses(maxCostRatioViolated ?
618	previousMisses + 1 : previousMisses);
619	}
620
621	BvhLeaf *leaf = splitCandidate.mParentData.mNode;
622
623	const float oldProp = EvalViewCellsVolume(leaf->mObjects);
624	const float oldRenderCost = EvalRenderCost(leaf->mObjects);
625
626	// compute global decrease in render cost
627	const float newRenderCost = EvalRenderCost(splitCandidate.mFrontObjects) +
628	EvalRenderCost(splitCandidate.mBackObjects);
629
630	const float renderCostDecr = oldRenderCost - newRenderCost;
631
632	splitCandidate.SetRenderCostDecrease(renderCostDecr);
633
634	// increase in pvs entries
635	const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
636	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
637
638	#ifdef GTP_DEBUG
639	Debug << "old render cost: " << oldRenderCost << endl;
640	Debug << "new render cost: " << newRenderCost << endl;
641	Debug << "render cost decrease: " << renderCostDecr << endl;
642	#endif
643
644	float priority = EvalPriority(splitCandidate,
645	renderCostDecr,
646	oldRenderCost);
647
648	if (USE_AVGRAYCONTRI)
649	{
650	// this leaf is a pvs entry in all the view cells
651	// that see one of the objects.
652	const int pvs = CountViewCells(leaf->mObjects);
653	//const int pvs = (int)leaf->mObjects.size();
654
655	// avg contribution of a ray to a pvs
656	const float avgRayContri =
657	AvgRayContribution(pvs, splitCandidate.mParentData.mNumRays);
658
659	// high avg ray contri, the result is influenced by undersampling
660	// => decrease priority
661	if (0 && (avgRayContri > mHierarchyManager->mMaxAvgRayContri))
662	{
663	const float factor = 1.0f + avgRayContri - mHierarchyManager->mMaxAvgRayContri;
664	priority /= factor;
665	}
666
667	//splitCandidate.SetAvgRayContri(avgRayContri);
668	}
669
670	// compute global decrease in render cost
671	splitCandidate.SetPriority(priority);
672	}
673
674
675	int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate) const
676	{
677	const int oldPvsSize = CountViewCells(splitCandidate.mParentData.mNode->mObjects);
678
679	const int fPvsSize = CountViewCells(splitCandidate.mFrontObjects);
680	const int bPvsSize = CountViewCells(splitCandidate.mBackObjects);
681
682	return fPvsSize + bPvsSize - oldPvsSize;
683	}
684
685
686	inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &tData) const
687	{
688	const bool terminationCriteriaMet =
689	(0
690	\|\| ((int)tData.mNode->mObjects.size() <= 1)//mTermMinObjects)
691	//\|\| (data.mProbability <= mTermMinProbability)
692	//\|\| (data.mNumRays <= mTermMinRays)
693	);
694
695	#ifdef _DEBUG
696	if (terminationCriteriaMet)
697	{
698	cout << "bvh local termination criteria met:" << endl;
699	cout << "objects: " << (int)tData.mNode->mObjects.size() << " " << mTermMinObjects << endl;
700	}
701	#endif
702	return terminationCriteriaMet;
703	}
704
705
706	inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
707	{
708	// note: tracking for global cost termination
709	// does not make much sense for interleaved vsp / osp partition
710	// as it is the responsibility of the hierarchy manager
711
712	const bool terminationCriteriaMet =
713	(0
714	\|\| (mBvhStats.Leaves() >= mTermMaxLeaves)
715	//\|\| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
716	//\|\| mOutOfMemory
717	);
718
719	#ifdef GTP_DEBUG
720	if (terminationCriteriaMet)
721	{
722	Debug << "bvh global termination criteria met:" << endl;
723	Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
724	Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
725	}
726	#endif
727	return terminationCriteriaMet;
728	}
729
730
731	void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
732	{
733	// the node became a leaf -> evaluate stats for leafs
734	BvhLeaf *leaf = data.mNode;
735
736	++ mCreatedLeaves;
737
738
739	if (data.mProbability <= mTermMinProbability)
740	{
741	++ mBvhStats.minProbabilityNodes;
742	}
743
744	////////////////////////////////////////////
745	// depth related stuff
746
747	if (data.mDepth < mBvhStats.minDepth)
748	{
749	mBvhStats.minDepth = data.mDepth;
750	}
751
752	if (data.mDepth >= mTermMaxDepth)
753	{
754	++ mBvhStats.maxDepthNodes;
755	}
756
757	// accumulate depth to compute average depth
758	mBvhStats.accumDepth += data.mDepth;
759
760
761	////////////////////////////////////////////
762	// objects related stuff
763
764	// note: the sum should alwaysbe total number of objects for bvh
765	mBvhStats.objectRefs += (int)leaf->mObjects.size();
766
767	if ((int)leaf->mObjects.size() <= mTermMinObjects)
768	{
769	++ mBvhStats.minObjectsNodes;
770	}
771
772	if (leaf->mObjects.empty())
773	{
774	++ mBvhStats.emptyNodes;
775	}
776
777	if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
778	{
779	mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
780	}
781
782	if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
783	{
784	mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
785	}
786
787	////////////////////////////////////////////
788	// ray related stuff
789
790	// note: this number should always accumulate to the total number of rays
791	mBvhStats.rayRefs += data.mNumRays;
792
793	if (data.mNumRays <= mTermMinRays)
794	{
795	++ mBvhStats.minRaysNodes;
796	}
797
798	if (data.mNumRays > mBvhStats.maxRayRefs)
799	{
800	mBvhStats.maxRayRefs = data.mNumRays;
801	}
802
803	if (data.mNumRays < mBvhStats.minRayRefs)
804	{
805	mBvhStats.minRayRefs = data.mNumRays;
806	}
807
808	#ifdef _DEBUG
809	cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size()
810	<< " rays: " << data.mNumRays << " rays / objects "
811	<< (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
812	#endif
813	}
814
815
816	#if 0
817
818	/// compute object boundaries using spatial mid split
819	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
820	const int axis,
821	ObjectContainer &objectsFront,
822	ObjectContainer &objectsBack)
823	{
824	const float maxBox = tData.mBoundingBox.Max(axis);
825	const float minBox = tData.mBoundingBox.Min(axis);
826
827	float midPoint = (maxBox + minBox) * 0.5f;
828
829	ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
830
831	for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
832	{
833	Intersectable obj = oit;
834	const AxisAlignedBox3 box = obj->GetBox();
835
836	const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;
837
838	// object mailed => belongs to back objects
839	if (objMid < midPoint)
840	{
841	objectsBack.push_back(obj);
842	}
843	else
844	{
845	objectsFront.push_back(obj);
846	}
847	}
848
849	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
850	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
851
852	const float ratio = newRenderCost / oldRenderCost;
853	return ratio;
854	}
855
856	#else
857
858	/// compute object partition by getting balanced objects on the left and right side
859	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
860	const int axis,
861	ObjectContainer &objectsFront,
862	ObjectContainer &objectsBack)
863	{
864	PrepareLocalSubdivisionCandidates(tData, axis);
865
866	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
867
868	int i = 0;
869	const int border = (int)tData.mNode->mObjects.size() / 2;
870
871	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
872	{
873	Intersectable obj = (cit).mObject;
874
875	// object mailed => belongs to back objects
876	if (i < border)
877	{
878	objectsBack.push_back(obj);
879	}
880	else
881	{
882	objectsFront.push_back(obj);
883	}
884	}
885
886	#if 1
887	const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
888	#else
889	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
890	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
891
892	const float cost = newRenderCost / oldRenderCost;
893	#endif
894
895	return cost;
896	}
897	#endif
898
899	#if 1
900
901	float BvHierarchy::EvalSah(const BvhTraversalData &tData,
902	const int axis,
903	ObjectContainer &objectsFront,
904	ObjectContainer &objectsBack)
905	{
906	// go through the lists, count the number of objects left and right
907	// and evaluate the following cost funcion:
908	// C = ct_div_ci + (ol + or) / queries
909	PrepareLocalSubdivisionCandidates(tData, axis);
910
911	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
912	float objectsLeft = 0, objectsRight = totalRenderCost;
913
914	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
915	const float boxArea = nodeBbox.SurfaceArea();
916
917	float minSum = 1e20f;
918
919	float minBorder = nodeBbox.Max(axis);
920	float maxBorder = nodeBbox.Min(axis);
921
922	float areaLeft = 0, areaRight = 0;
923
924	SortableEntryContainer::const_iterator currentPos =
925	mSubdivisionCandidates->begin();
926
927	vector<float> bordersRight;
928
929	// we keep track of both borders of the bounding boxes =>
930	// store the events in descending order
931
932	bordersRight.resize(mSubdivisionCandidates->size());
933
934	SortableEntryContainer::reverse_iterator rcit =
935	mSubdivisionCandidates->rbegin(), rcit_end =
936	mSubdivisionCandidates->rend();
937
938	vector<float>::reverse_iterator rbit = bordersRight.rbegin();
939
940	for (; rcit != rcit_end; ++ rcit, ++ rbit)
941	{
942	Intersectable obj = (rcit).mObject;
943	const AxisAlignedBox3 obox = obj->GetBox();
944
945	if (obox.Min(axis) < minBorder)
946	{
947	minBorder = obox.Min(axis);
948	}
949
950	(*rbit) = minBorder;
951	}
952
953	// temporary surface areas
954	float al = 0;
955	float ar = boxArea;
956
957	vector<float>::const_iterator bit = bordersRight.begin();
958	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
959
960	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
961	{
962	Intersectable obj = (cit).mObject;
963
964	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
965
966	objectsLeft += renderCost;
967	objectsRight -= renderCost;
968
969	const AxisAlignedBox3 obox = obj->GetBox();
970
971	// the borders of the bounding boxes have changed
972	if (obox.Max(axis) > maxBorder)
973	{
974	maxBorder = obox.Max(axis);
975	}
976
977	minBorder = (*bit);
978
979	AxisAlignedBox3 lbox = nodeBbox;
980	AxisAlignedBox3 rbox = nodeBbox;
981
982	lbox.SetMax(axis, maxBorder);
983	rbox.SetMin(axis, minBorder);
984
985	al = lbox.SurfaceArea();
986	ar = rbox.SurfaceArea();
987
988	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
989	const float sum = noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
990
991	/cout << "pos=" << (cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
992	<< lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
993	cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
994	cout << "cost= " << sum << endl;*/
995
996	if (sum < minSum)
997	{
998	minSum = sum;
999	areaLeft = al;
1000	areaRight = ar;
1001
1002	// objects belong to left side now
1003	for (; currentPos != (cit + 1); ++ currentPos);
1004	}
1005	}
1006
1007	////////////
1008	//-- assign object to front and back volume
1009
1010	// belongs to back bv
1011	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1012	objectsBack.push_back((*cit).mObject);
1013
1014	// belongs to front bv
1015	for (cit = currentPos; cit != cit_end; ++ cit)
1016	objectsFront.push_back((*cit).mObject);
1017
1018	float newCost = minSum / boxArea;
1019	float ratio = newCost / totalRenderCost;
1020
1021	#ifdef GTP_DEBUG
1022	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1023	<< (int)tData.mNode->mObjects.size() << ")\t area=("
1024	<< areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1025	<< "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1026	#endif
1027
1028	return ratio;
1029	}
1030
1031	#else
1032
1033	float BvHierarchy::EvalSah(const BvhTraversalData &tData,
1034	const int axis,
1035	ObjectContainer &objectsFront,
1036	ObjectContainer &objectsBack)
1037	{
1038	// go through the lists, count the number of objects left and right
1039	// and evaluate the following cost funcion:
1040	// C = ct_div_ci + (ol + or) / queries
1041	PrepareLocalSubdivisionCandidates(tData, axis);
1042
1043	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
1044	float objectsLeft = 0, objectsRight = totalRenderCost;
1045
1046	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
1047
1048	const float minBox = nodeBbox.Min(axis);
1049	const float maxBox = nodeBbox.Max(axis);
1050	const float boxArea = nodeBbox.SurfaceArea();
1051
1052	float minSum = 1e20f;
1053
1054	Vector3 minBorder = nodeBbox.Max();
1055	Vector3 maxBorder = nodeBbox.Min();
1056
1057	float areaLeft = 0, areaRight = 0;
1058
1059	SortableEntryContainer::const_iterator currentPos =
1060	mSubdivisionCandidates->begin();
1061
1062	vector<Vector3> bordersRight;
1063
1064	// we keep track of both borders of the bounding boxes =>
1065	// store the events in descending order
1066	bordersRight.resize(mSubdivisionCandidates->size());
1067
1068	SortableEntryContainer::reverse_iterator rcit =
1069	mSubdivisionCandidates->rbegin(), rcit_end =
1070	mSubdivisionCandidates->rend();
1071
1072	vector<Vector3>::reverse_iterator rbit = bordersRight.rbegin();
1073
1074	for (; rcit != rcit_end; ++ rcit, ++ rbit)
1075	{
1076	Intersectable obj = (rcit).mObject;
1077	const AxisAlignedBox3 obox = obj->GetBox();
1078
1079	for (int i = 0; i < 3; ++ i)
1080	{
1081	if (obox.Min(i) < minBorder[i])
1082	{
1083	minBorder[i] = obox.Min(i);
1084	}
1085	}
1086
1087	(*rbit) = minBorder;
1088	}
1089
1090	// temporary surface areas
1091	float al = 0;
1092	float ar = boxArea;
1093
1094	vector<Vector3>::const_iterator bit = bordersRight.begin();
1095	SortableEntryContainer::const_iterator cit, cit_end =
1096	mSubdivisionCandidates->end();
1097
1098	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
1099	{
1100	Intersectable obj = (cit).mObject;
1101
1102	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1103
1104	objectsLeft += renderCost;
1105	objectsRight -= renderCost;
1106
1107	const AxisAlignedBox3 obox = obj->GetBox();
1108
1109	AxisAlignedBox3 lbox = nodeBbox;
1110	AxisAlignedBox3 rbox = nodeBbox;
1111
1112	// the borders of the left bounding box have changed
1113	for (int i = 0; i < 3; ++ i)
1114	{
1115	if (obox.Max(i) > maxBorder[i])
1116	{
1117	maxBorder[i] = obox.Max(i);
1118	}
1119	}
1120
1121	minBorder = (*bit);
1122
1123	lbox.SetMax(maxBorder);
1124	rbox.SetMin(minBorder);
1125
1126	al = lbox.SurfaceArea();
1127	ar = rbox.SurfaceArea();
1128
1129	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
1130	const float sum = noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
1131
1132	/cout << "pos=" << (cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
1133	<< lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
1134	cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
1135	cout << "cost= " << sum << endl;*/
1136
1137	if (sum < minSum)
1138	{
1139	minSum = sum;
1140	areaLeft = al;
1141	areaRight = ar;
1142
1143	// objects belong to left side now
1144	for (; currentPos != (cit + 1); ++ currentPos);
1145	}
1146	}
1147
1148	/////////////
1149	//-- assign object to front and back volume
1150
1151	// belongs to back bv
1152	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1153	objectsBack.push_back((*cit).mObject);
1154
1155	// belongs to front bv
1156	for (cit = currentPos; cit != cit_end; ++ cit)
1157	objectsFront.push_back((*cit).mObject);
1158
1159	float newCost = minSum / boxArea;
1160	float ratio = newCost / totalRenderCost;
1161
1162	#ifdef GTP_DEBUG
1163	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1164	<< (int)tData.mNode->mObjects.size() << ")\t area=("
1165	<< areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1166	<< "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1167	#endif
1168
1169	return ratio;
1170	}
1171
1172	#endif
1173
1174	static bool PrepareOutput(const int axis,
1175	const int leaves,
1176	ofstream &sumStats,
1177	ofstream &vollStats,
1178	ofstream &volrStats)
1179	{
1180	if ((axis == 0) && (leaves > 0) && (leaves < 90))
1181	{
1182	char str[64];
1183	sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
1184	sumStats.open(str);
1185	sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
1186	vollStats.open(str);
1187	sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
1188	volrStats.open(str);
1189	}
1190
1191	return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
1192	}
1193
1194
1195	static void PrintHeuristics(const float objectsRight,
1196	const float sum,
1197	const float volLeft,
1198	const float volRight,
1199	const float viewSpaceVol,
1200	ofstream &sumStats,
1201	ofstream &vollStats,
1202	ofstream &volrStats)
1203	{
1204	sumStats
1205	<< "#Position\n" << objectsRight << endl
1206	<< "#Sum\n" << sum / viewSpaceVol << endl
1207	<< "#Vol\n" << (volLeft + volRight) / viewSpaceVol << endl;
1208
1209	vollStats
1210	<< "#Position\n" << objectsRight << endl
1211	<< "#Vol\n" << volLeft / viewSpaceVol << endl;
1212
1213	volrStats
1214	<< "#Position\n" << objectsRight << endl
1215	<< "#Vol\n" << volRight / viewSpaceVol << endl;
1216	}
1217
1218
1219	float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
1220	const int axis,
1221	ObjectContainer &objectsFront,
1222	ObjectContainer &objectsBack)
1223	{
1224	/////////////////////////////////////////////
1225	//-- go through the lists, count the number of objects
1226	//-- left and right and evaluate the cost funcion
1227
1228	// prepare the heuristics by setting mailboxes and counters
1229	const float totalVol = PrepareHeuristics(tData, axis);
1230
1231	// local helper variables
1232	float volLeft = 0;
1233	float volRight = totalVol;
1234
1235	const float nTotalObjects = EvalAbsCost(tData.mNode->mObjects);
1236	float nObjectsLeft = 0;
1237	float nObjectsRight = nTotalObjects;
1238
1239	const float viewSpaceVol =
1240	mViewCellsManager->GetViewSpaceBox().GetVolume();
1241
1242	SortableEntryContainer::const_iterator backObjectsStart =
1243	mSubdivisionCandidates->begin();
1244
1245	/////////////////////////////////
1246	//-- the parameters for the current optimum
1247
1248	float volBack = volLeft;
1249	float volFront = volRight;
1250	float newRenderCost = nTotalObjects * totalVol;
1251
1252	#ifdef GTP_DEBUG
1253	ofstream sumStats;
1254	ofstream vollStats;
1255	ofstream volrStats;
1256
1257	const bool printStats = PrepareOutput(axis,
1258	mBvhStats.Leaves(),
1259	sumStats,
1260	vollStats,
1261	volrStats);
1262	#endif
1263
1264	///////////////////////
1265	//-- the sweep heuristics
1266	//-- traverse through events and find best split plane
1267
1268	SortableEntryContainer::const_iterator cit,
1269	cit_end = cit_end = mSubdivisionCandidates->end();
1270
1271	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
1272	{
1273	Intersectable object = (cit).mObject;
1274
1275	// evaluate change in l and r volume
1276	// voll = view cells that see only left node (i.e., left pvs)
1277	// volr = view cells that see only right node (i.e., right pvs)
1278	EvalHeuristicsContribution(object, volLeft, volRight);
1279
1280	const float rc = mViewCellsManager->EvalRenderCost(object);
1281
1282	nObjectsLeft += rc;
1283	nObjectsRight -= rc;
1284
1285	// split is only valid if #objects on left and right is not zero
1286	const bool noValidSplit = ((nObjectsLeft <= Limits::Small) \|\|
1287	(nObjectsRight <= Limits::Small));
1288
1289	// the heuristics
1290	const float sum = noValidSplit ?
1291	1e25 : volLeft * (float)nObjectsLeft + volRight * (float)nObjectsRight;
1292
1293	#ifdef GTP_DEBUG
1294	if (printStats)
1295	{
1296	PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
1297	sumStats, vollStats, volrStats);
1298	}
1299	#endif
1300
1301	if (sum < newRenderCost)
1302	{
1303	newRenderCost = sum;
1304
1305	volBack = volLeft;
1306	volFront = volRight;
1307
1308	// objects belongs to left side now
1309	for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
1310	}
1311	}
1312
1313	////////////////////////////////////////
1314	//-- assign object to front and back volume
1315
1316	// belongs to back bv
1317	for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
1318	{
1319	objectsBack.push_back((*cit).mObject);
1320	}
1321	// belongs to front bv
1322	for (cit = backObjectsStart; cit != cit_end; ++ cit)
1323	{
1324	objectsFront.push_back((*cit).mObject);
1325	}
1326
1327	// render cost of the old parent
1328	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
1329	// the relative cost ratio
1330	const float ratio = newRenderCost / oldRenderCost;
1331
1332	#ifdef GTP_DEBUG
1333	Debug << "\n§§§§ bvh eval const decrease §§§§" << endl
1334	<< "back pvs: " << (int)objectsBack.size() << " front pvs: "
1335	<< (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl
1336	<< "back p: " << volBack / viewSpaceVol << " front p "
1337	<< volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
1338	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: "
1339	<< newRenderCost / viewSpaceVol << endl
1340	<< "render cost decrease: "
1341	<< oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
1342	#endif
1343
1344	return ratio;
1345	}
1346
1347
1348	void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
1349	const int axis)
1350	{
1351	//-- insert object queries
1352	ObjectContainer *objects = mUseGlobalSorting ?
1353	tData.mSortedObjects[axis] : &tData.mNode->mObjects;
1354
1355	CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
1356	}
1357
1358
1359	void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
1360	SortableEntryContainer **subdivisionCandidates,
1361	const bool sort,
1362	const int axis)
1363	{
1364	(*subdivisionCandidates)->clear();
1365
1366	// compute requested size and look if subdivision candidate has to be recomputed
1367	const int requestedSize = (int)objects.size() * 2;
1368
1369	// creates a sorted split candidates array
1370	if ((*subdivisionCandidates)->capacity() > 500000 &&
1371	requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
1372	{
1373	delete (*subdivisionCandidates);
1374	(*subdivisionCandidates) = new SortableEntryContainer;
1375	}
1376
1377	(*subdivisionCandidates)->reserve(requestedSize);
1378
1379	ObjectContainer::const_iterator oit, oit_end = objects.end();
1380
1381	for (oit = objects.begin(); oit < oit_end; ++ oit)
1382	{
1383	Intersectable object = oit;
1384	const AxisAlignedBox3 &box = object->GetBox();
1385	const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
1386
1387	(*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
1388	}
1389
1390	if (sort)
1391	{ // no presorted candidate list
1392	stable_sort((subdivisionCandidates)->begin(), (subdivisionCandidates)->end());
1393	}
1394	}
1395
1396
1397	const BvhStatistics &BvHierarchy::GetStatistics() const
1398	{
1399	return mBvhStats;
1400	}
1401
1402
1403	float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData,
1404	const int axis)
1405	{
1406	BvhLeaf *leaf = tData.mNode;
1407	float vol = 0;
1408
1409	// sort so we can use a sweep from right to left
1410	PrepareLocalSubdivisionCandidates(tData, axis);
1411
1412	// collect and mark the view cells as belonging to front pvs
1413	ViewCellContainer viewCells;
1414
1415	const int numRays = CollectViewCells(tData.mNode->mObjects, viewCells, true, true);
1416	//cout << "number of rays: " << numRays << endl;
1417
1418	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1419	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1420	{
1421	#if USE_VOLUMES_FOR_HEURISTICS
1422	const float volIncr = (*vit)->GetVolume();
1423	#else
1424	const float volIncr = 1.0f;
1425	#endif
1426	vol += volIncr;
1427	}
1428
1429	// we will mail view cells switching to the back side
1430	ViewCell::NewMail();
1431
1432	return vol;
1433	}
1434
1435	///////////////////////////////////////////////////////////
1436
1437
1438	void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
1439	float &volLeft,
1440	float &volRight)
1441	{
1442	// collect all view cells associated with this objects
1443	// (also multiple times, if they are pierced by several rays)
1444	ViewCellContainer viewCells;
1445	const bool useMailboxing = false;
1446
1447	CollectViewCells(obj, viewCells, useMailboxing, false, true);
1448
1449	// classify view cells and compute volume contri accordingly
1450	// possible view cell classifications:
1451	// view cell mailed => view cell can be seen from left child node
1452	// view cell counter > 0 view cell can be seen from right child node
1453	// combined: view cell volume belongs to both nodes
1454	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1455
1456	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1457	{
1458	// view cells can also be seen from left child node
1459	ViewCell viewCell = vit;
1460	#if USE_VOLUMES_FOR_HEURISTICS
1461	const float vol = viewCell->GetVolume();
1462	#else
1463	const float vol = 1.0f;
1464	#endif
1465	if (!viewCell->Mailed())
1466	{
1467	viewCell->Mail();
1468	// we now see view cell from both nodes
1469	// => add volume to left node
1470	volLeft += vol;
1471	}
1472
1473	// last reference into the right node
1474	if (-- viewCell->mCounter == 0)
1475	{
1476	// view cell was previously seen from both nodes =>
1477	// remove volume from right node
1478	volRight -= vol;
1479	}
1480	}
1481	}
1482
1483
1484	void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
1485	{
1486	mViewCellsManager = vcm;
1487	}
1488
1489
1490	AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
1491	{
1492	return mBoundingBox;
1493	}
1494
1495
1496	float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
1497	ObjectContainer &frontObjects,
1498	ObjectContainer &backObjects,
1499	bool useVisibilityBasedHeuristics)
1500	{
1501	if (mIsInitialSubdivision)
1502	{
1503	ApplyInitialSplit(tData, frontObjects, backObjects);
1504	return 0;
1505	}
1506
1507	ObjectContainer nFrontObjects[3];
1508	ObjectContainer nBackObjects[3];
1509	float nCostRatio[3];
1510
1511	int sAxis = 0;
1512	int bestAxis = -1;
1513
1514	if (mOnlyDrivingAxis)
1515	{
1516	const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
1517	sAxis = box.Size().DrivingAxis();
1518	}
1519
1520	// only use a subset of the rays for visibility based heuristics
1521	if (mUseCostHeuristics && useVisibilityBasedHeuristics)
1522	{
1523	VssRayContainer rays;
1524	// maximal 2 objects share the same ray
1525	rays.reserve(tData.mNumRays * 2);
1526	CollectRays(tData.mNode->mObjects, rays);
1527
1528	const float prop = (float)mMaxTests / (float)tData.mNumRays;
1529
1530	VssRay::NewMail();
1531
1532	VssRayContainer::const_iterator rit, rit_end = rays.end();
1533
1534	int nRays = 0;
1535
1536	for (rit = rays.begin(); rit != rit_end; ++ rit)
1537	{
1538	if ((mMaxTests >= (int)rays.size()) \|\| (Random(1.0f) < prop))
1539	{
1540	(*rit)->Mail();
1541	++ nRays;
1542	}
1543	}
1544	}
1545
1546	////////////////////////////////////
1547	//-- evaluate split cost for all three axis
1548
1549	for (int axis = 0; axis < 3; ++ axis)
1550	{
1551	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
1552	{
1553	if (mUseCostHeuristics)
1554	{
1555	//////////////////////////////////
1556	//-- split objects using heuristics
1557
1558	if (useVisibilityBasedHeuristics)
1559	{
1560	///////////
1561	//-- heuristics using objects weighted by view cells volume
1562	nCostRatio[axis] =
1563	EvalLocalCostHeuristics(tData,
1564	axis,
1565	nFrontObjects[axis],
1566	nBackObjects[axis]);
1567	}
1568	else
1569	{
1570	//////////////////
1571	//-- view cells not constructed yet => use surface area heuristic
1572	nCostRatio[axis] = EvalSah(tData,
1573	axis,
1574	nFrontObjects[axis],
1575	nBackObjects[axis]);
1576	}
1577	}
1578	else
1579	{
1580	//-- split objects using some simple criteria
1581	nCostRatio[axis] =
1582	EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1583	}
1584
1585	// no good results for degenerate axis split
1586	if (1 &&
1587	(tData.mNode->GetBoundingBox().Size(axis) < 0.0001))//Limits::Small))
1588	{
1589	nCostRatio[axis] += 9999;
1590	}
1591
1592	if ((bestAxis == -1) \|\| (nCostRatio[axis] < nCostRatio[bestAxis]))
1593	{
1594	bestAxis = axis;
1595	}
1596	}
1597	}
1598
1599	////////////////
1600	//-- assign values
1601
1602	frontObjects = nFrontObjects[bestAxis];
1603	backObjects = nBackObjects[bestAxis];
1604
1605	//cout << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1606	return nCostRatio[bestAxis];
1607	}
1608
1609
1610	int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
1611	{
1612	int nRays = 0;
1613	VssRayContainer::const_iterator rit, rit_end = rays.end();
1614
1615	VssRay::NewMail();
1616
1617	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1618	{
1619	VssRay ray = (rit);
1620
1621	if (ray->mTerminationObject)
1622	{
1623	ray->mTerminationObject->GetOrCreateRays()->push_back(ray);
1624	if (!ray->Mailed())
1625	{
1626	ray->Mail();
1627	++ nRays;
1628	}
1629	}
1630
1631	#if COUNT_ORIGIN_OBJECTS
1632
1633	if (ray->mOriginObject)
1634	{
1635	ray->mOriginObject->GetOrCreateRays()->push_back(ray);
1636
1637	if (!ray->Mailed())
1638	{
1639	ray->Mail();
1640	++ nRays;
1641	}
1642	}
1643	#endif
1644	}
1645
1646	return nRays;
1647	}
1648
1649
1650	void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
1651	{
1652	const float costDecr = sc.GetRenderCostDecrease();
1653
1654	mSubdivisionStats
1655	<< "#Leaves\n" << mBvhStats.Leaves() << endl
1656	<< "#RenderCostDecrease\n" << costDecr << endl
1657	<< "#TotalRenderCost\n" << mTotalCost << endl
1658	<< "#EntriesInPvs\n" << mPvsEntries << endl;
1659	}
1660
1661
1662	void BvHierarchy::CollectRays(const ObjectContainer &objects,
1663	VssRayContainer &rays) const
1664	{
1665	VssRay::NewMail();
1666	ObjectContainer::const_iterator oit, oit_end = objects.end();
1667
1668	// evaluate reverse pvs and view cell volume on left and right cell
1669	// note: should I take all leaf objects or rather the objects hit by rays?
1670	for (oit = objects.begin(); oit != oit_end; ++ oit)
1671	{
1672	Intersectable obj = oit;
1673	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1674
1675	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1676	{
1677	VssRay ray = (rit);
1678
1679	if (!ray->Mailed())
1680	{
1681	ray->Mail();
1682	rays.push_back(ray);
1683	}
1684	}
1685	}
1686	}
1687
1688
1689	float BvHierarchy::EvalAbsCost(const ObjectContainer &objects)// const
1690	{
1691	#if USE_BETTER_RENDERCOST_EST
1692	ObjectContainer::const_iterator oit, oit_end = objects.end();
1693
1694	for (oit = objects.begin(); oit != oit_end; ++ oit)
1695	{
1696	objRenderCost += ViewCellsManager::GetRendercost(*oit);
1697	}
1698	#else
1699	return (float)objects.size();
1700	#endif
1701	}
1702
1703
1704	float BvHierarchy::EvalSahCost(BvhLeaf *leaf) const
1705	{
1706	////////////////
1707	//-- surface area heuristics
1708	if (leaf->mObjects.empty())
1709	return 0.0f;
1710
1711	const AxisAlignedBox3 box = GetBoundingBox(leaf);
1712	const float area = box.SurfaceArea();
1713	const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
1714
1715	return EvalAbsCost(leaf->mObjects) * area / viewSpaceArea;
1716	}
1717
1718
1719	float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
1720	{
1721	///////////////
1722	//-- render cost heuristics
1723
1724	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1725
1726	// probability that view point lies in a view cell which sees this node
1727	const float p = EvalViewCellsVolume(objects) / viewSpaceVol;
1728	const float objRenderCost = EvalAbsCost(objects);
1729
1730	return objRenderCost * p;
1731	}
1732
1733
1734	AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
1735	const AxisAlignedBox3 *parentBox) const
1736	{
1737	// if there are no objects in this box, box size is set to parent box size.
1738	// Question: Invalidate box instead?
1739	if (parentBox && objects.empty())
1740	return *parentBox;
1741
1742	AxisAlignedBox3 box;
1743	box.Initialize();
1744
1745	ObjectContainer::const_iterator oit, oit_end = objects.end();
1746
1747	for (oit = objects.begin(); oit != oit_end; ++ oit)
1748	{
1749	Intersectable obj = oit;
1750	// grow bounding box to include all objects
1751	box.Include(obj->GetBox());
1752	}
1753
1754	return box;
1755	}
1756
1757
1758	void BvHierarchy::CollectLeaves(BvhNode root, vector<BvhLeaf > &leaves) const
1759	{
1760	stack<BvhNode *> nodeStack;
1761	nodeStack.push(root);
1762
1763	while (!nodeStack.empty())
1764	{
1765	BvhNode *node = nodeStack.top();
1766	nodeStack.pop();
1767
1768	if (node->IsLeaf())
1769	{
1770	BvhLeaf leaf = (BvhLeaf )node;
1771	leaves.push_back(leaf);
1772	}
1773	else
1774	{
1775	BvhInterior interior = (BvhInterior )node;
1776
1777	nodeStack.push(interior->GetBack());
1778	nodeStack.push(interior->GetFront());
1779	}
1780	}
1781	}
1782
1783
1784	AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1785	{
1786	return node->GetBoundingBox();
1787	}
1788
1789
1790	int BvHierarchy::CollectViewCells(const ObjectContainer &objects,
1791	ViewCellContainer &viewCells,
1792	const bool setCounter,
1793	const bool onlyMailedRays) const
1794	{
1795	ViewCell::NewMail();
1796	ObjectContainer::const_iterator oit, oit_end = objects.end();
1797
1798	int numRays = 0;
1799	// loop through all object and collect view cell pvs of this node
1800	for (oit = objects.begin(); oit != oit_end; ++ oit)
1801	{
1802	// always use only mailed objects
1803	numRays += CollectViewCells(*oit, viewCells, true, setCounter, onlyMailedRays);
1804	}
1805
1806	return numRays;
1807	}
1808
1809
1810	int BvHierarchy::CollectViewCells(Intersectable *obj,
1811	ViewCellContainer &viewCells,
1812	const bool useMailBoxing,
1813	const bool setCounter,
1814	const bool onlyMailedRays) const
1815	{
1816	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1817
1818	int numRays = 0;
1819
1820	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1821	{
1822	VssRay ray = (rit);
1823
1824	if (onlyMailedRays && !ray->Mailed())
1825	{
1826	continue;
1827	}
1828
1829	++ numRays;
1830
1831	ViewCellContainer tmpViewCells;
1832	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1833
1834	// matt: probably slow to allocate memory for view cells every time
1835	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1836
1837	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1838	{
1839	ViewCell vc = vit;
1840
1841	// store view cells
1842	if (!useMailBoxing \|\| !vc->Mailed())
1843	{
1844	if (useMailBoxing) // => view cell not mailed
1845	{
1846	vc->Mail();
1847	if (setCounter)
1848	{
1849	vc->mCounter = 0;
1850	}
1851	}
1852
1853	viewCells.push_back(vc);
1854	}
1855
1856	if (setCounter)
1857	{
1858	++ vc->mCounter;
1859	}
1860	}
1861	}
1862
1863	return numRays;
1864	}
1865
1866
1867	int BvHierarchy::CountViewCells(Intersectable *obj) const
1868	{
1869	int result = 0;
1870
1871	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1872
1873	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1874	{
1875	VssRay ray = (rit);
1876	ViewCellContainer tmpViewCells;
1877
1878	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1879
1880	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1881	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1882	{
1883	ViewCell vc = vit;
1884
1885	// store view cells
1886	if (!vc->Mailed())
1887	{
1888	vc->Mail();
1889	++ result;
1890	}
1891	}
1892	}
1893
1894	return result;
1895	}
1896
1897
1898	int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
1899	{
1900	int nViewCells = 0;
1901	ViewCell::NewMail();
1902	ObjectContainer::const_iterator oit, oit_end = objects.end();
1903
1904	// loop through all object and collect view cell pvs of this node
1905	for (oit = objects.begin(); oit != oit_end; ++ oit)
1906	{
1907	nViewCells += CountViewCells(*oit);
1908	}
1909
1910	return nViewCells;
1911	}
1912
1913
1914	void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1915	vector<SubdivisionCandidate *> &dirtyList,
1916	const bool onlyUnmailed)
1917	{
1918	BvhTraversalData &tData = sc->mParentData;
1919	BvhLeaf *node = tData.mNode;
1920
1921	ViewCellContainer viewCells;
1922	//ViewCell::NewMail();
1923	int numRays = CollectViewCells(node->mObjects, viewCells, false, false);
1924
1925	if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
1926
1927	// split candidates handling
1928	// these view cells are thrown into dirty list
1929	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1930
1931	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1932	{
1933	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
1934	VspLeaf *leaf = vc->mLeaves[0];
1935
1936	SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
1937
1938	// is this leaf still a split candidate?
1939	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
1940	{
1941	candidate->Mail();
1942	candidate->SetDirty(true);
1943	dirtyList.push_back(candidate);
1944	}
1945	}
1946	}
1947
1948
1949	BvhNode *BvHierarchy::GetRoot() const
1950	{
1951	return mRoot;
1952	}
1953
1954
1955	bool BvHierarchy::IsObjectInLeaf(BvhLeaf leaf, Intersectable object) const
1956	{
1957	ObjectContainer::const_iterator oit =
1958	lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
1959
1960	// objects sorted by id
1961	if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
1962	{
1963	return true;
1964	}
1965	else
1966	{
1967	return false;
1968	}
1969	}
1970
1971
1972	BvhLeaf BvHierarchy::GetLeaf(Intersectable object, BvhNode *node) const
1973	{
1974	// rather use the simple version
1975	if (!object)
1976	return NULL;
1977	return object->mBvhLeaf;
1978
1979	///////////////////////////////////////
1980	// start from root of tree
1981
1982	if (node == NULL)
1983	node = mRoot;
1984
1985	vector<BvhLeaf *> leaves;
1986
1987	stack<BvhNode *> nodeStack;
1988	nodeStack.push(node);
1989
1990	BvhLeaf *leaf = NULL;
1991
1992	while (!nodeStack.empty())
1993	{
1994	BvhNode *node = nodeStack.top();
1995	nodeStack.pop();
1996
1997	if (node->IsLeaf())
1998	{
1999	leaf = dynamic_cast<BvhLeaf *>(node);
2000
2001	if (IsObjectInLeaf(leaf, object))
2002	{
2003	return leaf;
2004	}
2005	}
2006	else
2007	{
2008	// find point
2009	BvhInterior interior = dynamic_cast<BvhInterior >(node);
2010
2011	if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
2012	{
2013	nodeStack.push(interior->GetBack());
2014	}
2015
2016	// search both sides as we are using bounding volumes
2017	if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
2018	{
2019	nodeStack.push(interior->GetFront());
2020	}
2021	}
2022	}
2023
2024	return leaf;
2025	}
2026
2027
2028	bool BvHierarchy::Export(OUT_STREAM &stream)
2029	{
2030	ExportNode(mRoot, stream);
2031
2032	return true;
2033	}
2034
2035
2036	void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
2037	{
2038	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2039	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2040	{
2041	stream << (*oit)->GetId() << " ";
2042	}
2043	}
2044
2045
2046	void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
2047	{
2048	if (node->IsLeaf())
2049	{
2050	BvhLeaf leaf = dynamic_cast<BvhLeaf >(node);
2051	const AxisAlignedBox3 box = leaf->GetBoundingBox();
2052	stream << "<Leaf"
2053	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
2054	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
2055	<< " objects=\"";
2056
2057	//-- export objects
2058	// tmp matt
2059	if (0) ExportObjects(leaf, stream);
2060
2061	stream << "\" />" << endl;
2062	}
2063	else
2064	{
2065	BvhInterior interior = dynamic_cast<BvhInterior >(node);
2066	const AxisAlignedBox3 box = interior->GetBoundingBox();
2067
2068	stream << "<Interior"
2069	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
2070	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
2071	<< "\">" << endl;
2072
2073	ExportNode(interior->GetBack(), stream);
2074	ExportNode(interior->GetFront(), stream);
2075
2076	stream << "</Interior>" << endl;
2077	}
2078	}
2079
2080
2081	float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
2082	{
2083	float vol = 0;
2084
2085	ViewCellContainer viewCells;
2086
2087	// we have to account for all view cells that can
2088	// be seen from the objects
2089	int numRays = CollectViewCells(objects, viewCells, false, false);
2090
2091	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2092
2093	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2094	{
2095	vol += (*vit)->GetVolume();
2096	}
2097
2098	return vol;
2099	}
2100
2101
2102	void BvHierarchy::Initialise(const ObjectContainer &objects)
2103	{
2104	AxisAlignedBox3 box = EvalBoundingBox(objects);
2105
2106	///////
2107	//-- create new root
2108
2109	BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
2110	bvhleaf->mObjects = objects;
2111	mRoot = bvhleaf;
2112
2113	// compute bounding box from objects
2114	mBoundingBox = mRoot->GetBoundingBox();
2115
2116	// associate root with current objects
2117	AssociateObjectsWithLeaf(bvhleaf);
2118	}
2119
2120
2121	/*
2122	Mesh *BvHierarchy::MergeLeafToMesh()
2123	{
2124	vector<BvhLeaf *> leaves;
2125	CollectLeaves(leaves);
2126
2127	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2128
2129	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2130	{
2131	Mesh mesh = MergeLeafToMesh(lit);
2132	}
2133	}*/
2134
2135
2136	void BvHierarchy::PrepareConstruction(SplitQueue &tQueue,
2137	const VssRayContainer &sampleRays,
2138	const ObjectContainer &objects)
2139	{
2140	///////////////////////////////////////
2141	//-- we assume that we have objects sorted by their id =>
2142	//-- we don't have to sort them here and an binary search
2143	//-- for identifying if a object is in a leaf.
2144
2145	mBvhStats.Reset();
2146	mBvhStats.Start();
2147	mBvhStats.nodes = 1;
2148
2149	// store pointer to this tree
2150	BvhSubdivisionCandidate::sBvHierarchy = this;
2151
2152	// root and bounding box was already constructed
2153	BvhLeaf bvhLeaf = dynamic_cast<BvhLeaf >(mRoot);
2154
2155	// multiply termination criterium for comparison,
2156	// so it can be set between zero and one and
2157	// no division is necessary during traversal
2158
2159	#if PROBABILIY_IS_BV_VOLUME
2160	mTermMinProbability *= mBoundingBox.GetVolume();
2161	// probability that bounding volume is seen
2162	const float prop = GetBoundingBox().GetVolume();
2163	#else
2164	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2165	// probability that volume is "seen" from the view cells
2166	const float prop = EvalViewCellsVolume(objects);
2167	#endif
2168
2169	// only rays intersecting objects in node are interesting
2170	const int nRays = AssociateObjectsWithRays(sampleRays);
2171	//cout << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
2172
2173	// create bvh traversal data
2174	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2175
2176	// create sorted object lists for the first data
2177	if (mUseGlobalSorting)
2178	{
2179	AssignInitialSortedObjectList(oData, objects);
2180	}
2181
2182
2183	///////////////////
2184	//-- add first candidate for object space partition
2185
2186	BvhSubdivisionCandidate *oSubdivisionCandidate =
2187	new BvhSubdivisionCandidate(oData);
2188
2189	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2190
2191	mTotalCost = EvalRenderCost(objects);
2192	mPvsEntries = CountViewCells(objects);
2193
2194	if (mApplyInitialPartition)
2195	{
2196	vector<SubdivisionCandidate *> candidateContainer;
2197
2198	mIsInitialSubdivision = true;
2199
2200	// evaluate priority
2201	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2202	PrintSubdivisionStats(*oSubdivisionCandidate);
2203
2204	ApplyInitialSubdivision(oSubdivisionCandidate, candidateContainer);
2205
2206	mIsInitialSubdivision = false;
2207
2208	vector<SubdivisionCandidate *>::const_iterator cit, cit_end = candidateContainer.end();
2209
2210	for (cit = candidateContainer.begin(); cit != cit_end; ++ cit)
2211	{
2212	BvhSubdivisionCandidate sCandidate = dynamic_cast<BvhSubdivisionCandidate >(*cit);
2213
2214	// reevaluate priority
2215	EvalSubdivisionCandidate(*sCandidate);
2216	tQueue.Push(sCandidate);
2217	}
2218	}
2219	else
2220	{
2221	// evaluate priority
2222	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2223	PrintSubdivisionStats(*oSubdivisionCandidate);
2224
2225	tQueue.Push(oSubdivisionCandidate);
2226	}
2227
2228	cout << "size of initial bv subdivision: " << GetStatistics().Leaves() << endl;
2229	}
2230
2231
2232	void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData,
2233	const ObjectContainer &objects)
2234	{
2235	// we sort the objects as a preprocess so they don't have
2236	// to be sorted for each split
2237	for (int i = 0; i < 3; ++ i)
2238	{
2239	SortableEntryContainer *sortedObjects = new SortableEntryContainer();
2240
2241	CreateLocalSubdivisionCandidates(objects,
2242	&sortedObjects,
2243	true,
2244	i);
2245
2246	// copy list into traversal data list
2247	tData.mSortedObjects[i] = new ObjectContainer();
2248	tData.mSortedObjects[i]->reserve((int)objects.size());
2249
2250	SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
2251
2252	for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
2253	{
2254	tData.mSortedObjects[i]->push_back((*oit).mObject);
2255	}
2256
2257	delete sortedObjects;
2258	}
2259
2260	// last sorted list: by size
2261	tData.mSortedObjects[3] = new ObjectContainer();
2262	tData.mSortedObjects[3]->reserve((int)objects.size());
2263
2264	*(tData.mSortedObjects[3]) = objects;
2265	stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
2266	}
2267
2268
2269	void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
2270	BvhTraversalData &frontData,
2271	BvhTraversalData &backData)
2272	{
2273	Intersectable::NewMail();
2274
2275	// we sorted the objects as a preprocess so they don't have
2276	// to be sorted for each split
2277	ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
2278
2279	for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
2280	{
2281	(*fit)->Mail();
2282	}
2283
2284	for (int i = 0; i < 4; ++ i)
2285	{
2286	frontData.mSortedObjects[i] = new ObjectContainer();
2287	backData.mSortedObjects[i] = new ObjectContainer();
2288
2289	frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2290	backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2291
2292	ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();
2293
2294	for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
2295	{
2296	if ((*oit)->Mailed())
2297	{
2298	frontData.mSortedObjects[i]->push_back(*oit);
2299	}
2300	else
2301	{
2302	backData.mSortedObjects[i]->push_back(*oit);
2303	}
2304	}
2305	}
2306	}
2307
2308
2309	void BvHierarchy::Reset(SplitQueue &tQueue,
2310	const VssRayContainer &sampleRays,
2311	const ObjectContainer &objects)
2312	{
2313	// reset stats
2314	mBvhStats.Reset();
2315	mBvhStats.Start();
2316	mBvhStats.nodes = 1;
2317
2318	// reset root
2319	DEL_PTR(mRoot);
2320
2321	BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
2322	bvhleaf->mObjects = objects;
2323	mRoot = bvhleaf;
2324
2325	#if PROBABILIY_IS_BV_VOLUME
2326	mTermMinProbability *= mBoundingBox.GetVolume();
2327	// probability that bounding volume is seen
2328	const float prop = GetBoundingBox().GetVolume();
2329	#else
2330	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2331	// probability that volume is "seen" from the view cells
2332	const float prop = EvalViewCellsVolume(objects);
2333	#endif
2334
2335	const int nRays = CountRays(objects);
2336	BvhLeaf bvhLeaf = dynamic_cast<BvhLeaf >(mRoot);
2337
2338	// create bvh traversal data
2339	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2340
2341	AssignInitialSortedObjectList(oData, objects);
2342
2343
2344	///////////////////
2345	//-- add first candidate for object space partition
2346
2347	BvhSubdivisionCandidate *oSubdivisionCandidate =
2348	new BvhSubdivisionCandidate(oData);
2349
2350	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2351	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2352
2353	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2354	mTotalCost = (float)objects.size() * prop / viewSpaceVol;
2355
2356	PrintSubdivisionStats(*oSubdivisionCandidate);
2357
2358	tQueue.Push(oSubdivisionCandidate);
2359	}
2360
2361
2362	void BvhStatistics::Print(ostream &app) const
2363	{
2364	app << "=========== BvHierarchy statistics ===============\n";
2365
2366	app << setprecision(4);
2367
2368	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
2369
2370	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
2371
2372	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
2373
2374	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
2375
2376	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;
2377
2378	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
2379	<< maxCostNodes * 100 / (double)Leaves() << endl;
2380
2381	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
2382	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
2383
2384
2385	//////////////////////////////////////////////////
2386
2387	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
2388	<< maxDepthNodes * 100 / (double)Leaves() << endl;
2389
2390	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
2391
2392	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
2393
2394	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
2395
2396
2397	////////////////////////////////////////////////////////
2398
2399	app << "#N_PMINOBJECTSLEAVES ( Percentage of leaves with mininum objects )\n"
2400	<< minObjectsNodes * 100 / (double)Leaves() << endl;
2401
2402	app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
2403
2404	app << "#N_MINOBJECTREFS ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";
2405
2406	app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
2407
2408	app << "#N_PAVGOBJECTSLEAVES ( average object refs / leaf)\n" << AvgObjectRefs() << endl;
2409
2410
2411	////////////////////////////////////////////////////////
2412
2413	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with mininum rays )\n"
2414	<< minRaysNodes * 100 / (double)Leaves() << endl;
2415
2416	app << "#N_MAXRAYREFS ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";
2417
2418	app << "#N_MINRAYREFS ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
2419
2420	app << "#N_PAVGRAYLEAVES ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
2421
2422	app << "#N_PAVGRAYCONTRIBLEAVES ( Average ray contribution)\n" <<
2423	rayRefs / (double)objectRefs << endl;
2424
2425	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<<
2426	maxRayContriNodes * 100 / (double)Leaves() << endl;
2427
2428	app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
2429
2430	app << "========== END OF BvHierarchy statistics ==========\n";
2431	}
2432
2433
2434	// TODO: return memory usage in MB
2435	float BvHierarchy::GetMemUsage() const
2436	{
2437	return (float)(sizeof(BvHierarchy)
2438	+ mBvhStats.Leaves() * sizeof(BvhLeaf)
2439	+ mBvhStats.Interior() * sizeof(BvhInterior)
2440	) / float(1024 * 1024);
2441	}
2442
2443
2444	void BvHierarchy::SetActive(BvhNode *node) const
2445	{
2446	vector<BvhLeaf *> leaves;
2447
2448	// sets the pointers to the currently active view cells
2449	CollectLeaves(node, leaves);
2450	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2451
2452	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2453	{
2454	(*lit)->SetActiveNode(node);
2455	}
2456	}
2457
2458
2459	BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue,
2460	SubdivisionCandidate *splitCandidate)
2461	{
2462	BvhSubdivisionCandidate *sc =
2463	dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
2464	BvhTraversalData &tData = sc->mParentData;
2465
2466	BvhNode *currentNode = tData.mNode;
2467	BvhNode oldNode = (BvhNode )splitCandidate->mEvaluationHack;
2468
2469	if (!oldNode->IsLeaf())
2470	{
2471	//////////////
2472	//-- continue subdivision
2473
2474	BvhTraversalData tFrontData;
2475	BvhTraversalData tBackData;
2476
2477	BvhInterior oldInterior = dynamic_cast<BvhInterior >(oldNode);
2478
2479	sc->mFrontObjects.clear();
2480	sc->mBackObjects.clear();
2481
2482	oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
2483	oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
2484
2485	// evaluate the changes in render cost and pvs entries
2486	EvalSubdivisionCandidate(*sc, false);
2487
2488	// create new interior node and two leaf node
2489	currentNode = SubdivideNode(*sc, tFrontData, tBackData);
2490
2491	//oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
2492	//oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
2493
2494	//oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
2495	//oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
2496
2497	///////////////////////////
2498	//-- push the new split candidates on the queue
2499
2500	BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
2501	BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
2502
2503	frontCandidate->SetPriority((float)-oldInterior->GetFront()->GetTimeStamp());
2504	backCandidate->SetPriority((float)-oldInterior->GetBack()->GetTimeStamp());
2505
2506	frontCandidate->mEvaluationHack = oldInterior->GetFront();
2507	backCandidate->mEvaluationHack = oldInterior->GetBack();
2508
2509	// cross reference
2510	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
2511	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
2512
2513	//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
2514	tQueue.Push(frontCandidate);
2515	tQueue.Push(backCandidate);
2516	}
2517
2518	/////////////////////////////////
2519	//-- node is a leaf => terminate traversal
2520
2521	if (currentNode->IsLeaf())
2522	{
2523	// this leaf is no candidate for splitting anymore
2524	// => detach subdivision candidate
2525	tData.mNode->SetSubdivisionCandidate(NULL);
2526	// detach node so we don't delete it with the traversal data
2527	tData.mNode = NULL;
2528	}
2529
2530	return currentNode;
2531	}
2532
2533
2534	void BvHierarchy::CollectObjects(const AxisAlignedBox3 &box,
2535	ObjectContainer &objects)
2536	{
2537	stack<BvhNode *> nodeStack;
2538
2539	nodeStack.push(mRoot);
2540
2541	while (!nodeStack.empty()) {
2542	BvhNode *node = nodeStack.top();
2543
2544	nodeStack.pop();
2545	if (node->IsLeaf()) {
2546	BvhLeaf leaf = (BvhLeaf )node;
2547	if (Overlap(box, leaf->GetBoundingBox())) {
2548	Intersectable *object = leaf;
2549	if (!object->Mailed()) {
2550	object->Mail();
2551	objects.push_back(object);
2552	}
2553	}
2554	}
2555	else
2556	{
2557	BvhInterior interior = (BvhInterior )node;
2558	if (Overlap(box, interior->GetBoundingBox())) {
2559	bool pushed = false;
2560	if (!interior->GetFront()->Mailed()) {
2561	nodeStack.push(interior->GetFront());
2562	pushed = true;
2563	}
2564	if (!interior->GetBack()->Mailed()) {
2565	nodeStack.push(interior->GetBack());
2566	pushed = true;
2567	}
2568	// avoid traversal of this node in the next query
2569	if (!pushed)
2570	interior->Mail();
2571	}
2572	}
2573	}
2574	}
2575
2576
2577	void BvHierarchy::CreateUniqueObjectIds()
2578	{
2579	stack<BvhNode *> nodeStack;
2580	nodeStack.push(mRoot);
2581
2582	int currentId = 0;
2583	while (!nodeStack.empty())
2584	{
2585	BvhNode *node = nodeStack.top();
2586	nodeStack.pop();
2587
2588	node->SetId(currentId ++);
2589
2590	if (!node->IsLeaf())
2591	{
2592	BvhInterior interior = (BvhInterior )node;
2593
2594	nodeStack.push(interior->GetFront());
2595	nodeStack.push(interior->GetBack());
2596	}
2597	}
2598	}
2599
2600
2601	void BvHierarchy::ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
2602	vector<SubdivisionCandidate *> &candidateContainer)
2603	{
2604	SplitQueue tempQueue;
2605	tempQueue.Push(firstCandidate);
2606
2607	while (!tempQueue.Empty())
2608	{
2609	SubdivisionCandidate *candidate = tempQueue.Top();
2610	tempQueue.Pop();
2611
2612	BvhSubdivisionCandidate *bsc =
2613	dynamic_cast<BvhSubdivisionCandidate *>(candidate);
2614
2615	if (!InitialTerminationCriteriaMet(bsc->mParentData))
2616	{
2617	const bool globalCriteriaMet = GlobalTerminationCriteriaMet(bsc->mParentData);
2618
2619	BvhNode *node = Subdivide(tempQueue, bsc, globalCriteriaMet);
2620
2621	// not needed anymore
2622	delete bsc;
2623	}
2624	else // initial preprocessing finished for this candidate
2625	{
2626	// add to candidate container
2627	candidateContainer.push_back(bsc);
2628	}
2629	}
2630	}
2631
2632
2633	void BvHierarchy::ApplyInitialSplit(const BvhTraversalData &tData,
2634	ObjectContainer &frontObjects,
2635	ObjectContainer &backObjects)
2636	{
2637	ObjectContainer *objects = tData.mSortedObjects[3];
2638
2639	ObjectContainer::const_iterator oit, oit_end = objects->end();
2640
2641	float maxAreaDiff = -1.0f;
2642
2643	ObjectContainer::const_iterator backObjectsStart = objects->begin();
2644
2645	for (oit = objects->begin(); oit != (objects->end() - 1); ++ oit)
2646	{
2647	Intersectable objS = oit;
2648	Intersectable objL = (oit + 1);
2649
2650	const float areaDiff =
2651	objL->GetBox().SurfaceArea() - objS->GetBox().SurfaceArea();
2652
2653	if (areaDiff > maxAreaDiff)
2654	{
2655	maxAreaDiff = areaDiff;
2656	backObjectsStart = oit + 1;
2657	}
2658	}
2659
2660	// belongs to back bv
2661	for (oit = objects->begin(); oit != backObjectsStart; ++ oit)
2662	{
2663	frontObjects.push_back(*oit);
2664	}
2665
2666	// belongs to front bv
2667	for (oit = backObjectsStart; oit != oit_end; ++ oit)
2668	{
2669	backObjects.push_back(*oit);
2670	}
2671
2672	cout << "front: " << (int)frontObjects.size() << " back: " << (int)backObjects.size() << " "
2673	<< backObjects.front()->GetBox().SurfaceArea() - frontObjects.back()->GetBox().SurfaceArea() << endl;
2674	}
2675
2676
2677	inline static float AreaRatio(Intersectable smallObj, Intersectable largeObj)
2678	{
2679	const float areaSmall = smallObj->GetBox().SurfaceArea();
2680	const float areaLarge = largeObj->GetBox().SurfaceArea();
2681
2682	return areaSmall / (areaLarge - areaSmall + Limits::Small);
2683	}
2684
2685
2686	bool BvHierarchy::InitialTerminationCriteriaMet(const BvhTraversalData &tData) const
2687	{
2688	const bool terminationCriteriaMet =
2689	(0
2690	\|\| ((int)tData.mNode->mObjects.size() < mInitialMinObjects)
2691	\|\| (tData.mNode->mObjects.back()->GetBox().SurfaceArea() < mInitialMinArea)
2692	\|\| (AreaRatio(tData.mNode->mObjects.front(), tData.mNode->mObjects.back()) > mInitialMaxAreaRatio)
2693	);
2694
2695	cout << "criteria met: "<< terminationCriteriaMet << "\n"
2696	<< "size: " << (int)tData.mNode->mObjects.size() << " max: " << mInitialMinObjects << endl
2697	<< "ratio: " << AreaRatio(tData.mNode->mObjects.front(), tData.mNode->mObjects.back()) << " max: " << mInitialMaxAreaRatio << endl
2698	<< "area: " << tData.mNode->mObjects.back()->GetBox().SurfaceArea() << " max: " << mInitialMinArea << endl << endl;
2699
2700	return terminationCriteriaMet;
2701	}
2702
2703
2704	// HACK
2705	float BvHierarchy::GetRenderCostIncrementially(BvhNode *node) const
2706	{
2707	if (node->mRenderCost < 0)
2708	{
2709	//cout <<"p";
2710	if (node->IsLeaf())
2711	{
2712	BvhLeaf leaf = dynamic_cast<BvhLeaf >(node);
2713	node->mRenderCost = EvalAbsCost(leaf->mObjects);
2714	}
2715	else
2716	{
2717	BvhInterior interior = dynamic_cast<BvhInterior >(node);
2718
2719	node->mRenderCost = GetRenderCostIncrementially(interior->GetFront()) +
2720	GetRenderCostIncrementially(interior->GetBack());
2721	}
2722	}
2723
2724	return node->mRenderCost;
2725	}
2726
2727
2728	void BvHierarchy::Compress()
2729	{
2730	}
2731
2732
2733	}

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

Download in other formats: