Context Navigation

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

Revision 1908, 72.9 KB checked in by mattausch, 18 years ago (diff)
remopved bug when choosing bvh heuristics

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	//Debug << "bvh avgRayContri: " << avgRayContri << " #pvs: " << pvs << " #rays: " << splitCandidate.mParentData.mNumRays << endl;
660	//cout << "bvh avgRayContri: " << avgRayContri << endl;
661
662	// high avg ray contri, the result is influenced by undersampling
663	// => decrease priority
664	if (0 && (avgRayContri > mHierarchyManager->mMaxAvgRayContri))
665	{
666	const float factor = 1.0f + avgRayContri - mHierarchyManager->mMaxAvgRayContri;
667	priority /= factor;
668	}
669
670	//splitCandidate.SetAvgRayContri(avgRayContri);
671	}
672
673	// compute global decrease in render cost
674	splitCandidate.SetPriority(priority);
675	}
676
677
678	int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate) const
679	{
680	const int oldPvsSize = CountViewCells(splitCandidate.mParentData.mNode->mObjects);
681
682	const int fPvsSize = CountViewCells(splitCandidate.mFrontObjects);
683	const int bPvsSize = CountViewCells(splitCandidate.mBackObjects);
684
685	return fPvsSize + bPvsSize - oldPvsSize;
686	}
687
688
689	inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &tData) const
690	{
691	const bool terminationCriteriaMet =
692	(0
693	\|\| ((int)tData.mNode->mObjects.size() <= 1)//mTermMinObjects)
694	//\|\| (data.mProbability <= mTermMinProbability)
695	//\|\| (data.mNumRays <= mTermMinRays)
696	);
697
698	#ifdef _DEBUG
699	if (terminationCriteriaMet)
700	{
701	cout << "bvh local termination criteria met:" << endl;
702	cout << "objects: " << (int)tData.mNode->mObjects.size() << " " << mTermMinObjects << endl;
703	}
704	#endif
705	return terminationCriteriaMet;
706	}
707
708
709	inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
710	{
711	// note: tracking for global cost termination
712	// does not make much sense for interleaved vsp / osp partition
713	// as it is the responsibility of the hierarchy manager
714
715	const bool terminationCriteriaMet =
716	(0
717	\|\| (mBvhStats.Leaves() >= mTermMaxLeaves)
718	//\|\| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
719	//\|\| mOutOfMemory
720	);
721
722	#ifdef GTP_DEBUG
723	if (terminationCriteriaMet)
724	{
725	Debug << "bvh global termination criteria met:" << endl;
726	Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
727	Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
728	}
729	#endif
730	return terminationCriteriaMet;
731	}
732
733
734	void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
735	{
736	// the node became a leaf -> evaluate stats for leafs
737	BvhLeaf *leaf = data.mNode;
738
739	++ mCreatedLeaves;
740
741
742	if (data.mProbability <= mTermMinProbability)
743	{
744	++ mBvhStats.minProbabilityNodes;
745	}
746
747	////////////////////////////////////////////
748	// depth related stuff
749
750	if (data.mDepth < mBvhStats.minDepth)
751	{
752	mBvhStats.minDepth = data.mDepth;
753	}
754
755	if (data.mDepth >= mTermMaxDepth)
756	{
757	++ mBvhStats.maxDepthNodes;
758	}
759
760	// accumulate depth to compute average depth
761	mBvhStats.accumDepth += data.mDepth;
762
763
764	////////////////////////////////////////////
765	// objects related stuff
766
767	// note: the sum should alwaysbe total number of objects for bvh
768	mBvhStats.objectRefs += (int)leaf->mObjects.size();
769
770	if ((int)leaf->mObjects.size() <= mTermMinObjects)
771	{
772	++ mBvhStats.minObjectsNodes;
773	}
774
775	if (leaf->mObjects.empty())
776	{
777	++ mBvhStats.emptyNodes;
778	}
779
780	if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
781	{
782	mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
783	}
784
785	if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
786	{
787	mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
788	}
789
790	////////////////////////////////////////////
791	// ray related stuff
792
793	// note: this number should always accumulate to the total number of rays
794	mBvhStats.rayRefs += data.mNumRays;
795
796	if (data.mNumRays <= mTermMinRays)
797	{
798	++ mBvhStats.minRaysNodes;
799	}
800
801	if (data.mNumRays > mBvhStats.maxRayRefs)
802	{
803	mBvhStats.maxRayRefs = data.mNumRays;
804	}
805
806	if (data.mNumRays < mBvhStats.minRayRefs)
807	{
808	mBvhStats.minRayRefs = data.mNumRays;
809	}
810
811	#ifdef _DEBUG
812	cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size()
813	<< " rays: " << data.mNumRays << " rays / objects "
814	<< (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
815	#endif
816	}
817
818
819	#if 0
820
821	/// compute object boundaries using spatial mid split
822	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
823	const int axis,
824	ObjectContainer &objectsFront,
825	ObjectContainer &objectsBack)
826	{
827	const float maxBox = tData.mBoundingBox.Max(axis);
828	const float minBox = tData.mBoundingBox.Min(axis);
829
830	float midPoint = (maxBox + minBox) * 0.5f;
831
832	ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
833
834	for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
835	{
836	Intersectable obj = oit;
837	const AxisAlignedBox3 box = obj->GetBox();
838
839	const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;
840
841	// object mailed => belongs to back objects
842	if (objMid < midPoint)
843	{
844	objectsBack.push_back(obj);
845	}
846	else
847	{
848	objectsFront.push_back(obj);
849	}
850	}
851
852	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
853	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
854
855	const float ratio = newRenderCost / oldRenderCost;
856	return ratio;
857	}
858
859	#else
860
861	/// compute object partition by getting balanced objects on the left and right side
862	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
863	const int axis,
864	ObjectContainer &objectsFront,
865	ObjectContainer &objectsBack)
866	{
867	PrepareLocalSubdivisionCandidates(tData, axis);
868
869	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
870
871	int i = 0;
872	const int border = (int)tData.mNode->mObjects.size() / 2;
873
874	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
875	{
876	Intersectable obj = (cit).mObject;
877
878	// object mailed => belongs to back objects
879	if (i < border)
880	{
881	objectsBack.push_back(obj);
882	}
883	else
884	{
885	objectsFront.push_back(obj);
886	}
887	}
888
889	#if 1
890	const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
891	#else
892	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
893	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
894
895	const float cost = newRenderCost / oldRenderCost;
896	#endif
897
898	return cost;
899	}
900	#endif
901
902	#if 1
903
904	float BvHierarchy::EvalSah(const BvhTraversalData &tData,
905	const int axis,
906	ObjectContainer &objectsFront,
907	ObjectContainer &objectsBack)
908	{
909	// go through the lists, count the number of objects left and right
910	// and evaluate the following cost funcion:
911	// C = ct_div_ci + (ol + or) / queries
912	PrepareLocalSubdivisionCandidates(tData, axis);
913
914	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
915	float objectsLeft = 0, objectsRight = totalRenderCost;
916
917	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
918	const float boxArea = nodeBbox.SurfaceArea();
919
920	float minSum = 1e20f;
921
922	float minBorder = nodeBbox.Max(axis);
923	float maxBorder = nodeBbox.Min(axis);
924
925	float areaLeft = 0, areaRight = 0;
926
927	SortableEntryContainer::const_iterator currentPos =
928	mSubdivisionCandidates->begin();
929
930	vector<float> bordersRight;
931
932	// we keep track of both borders of the bounding boxes =>
933	// store the events in descending order
934
935	bordersRight.resize(mSubdivisionCandidates->size());
936
937	SortableEntryContainer::reverse_iterator rcit =
938	mSubdivisionCandidates->rbegin(), rcit_end =
939	mSubdivisionCandidates->rend();
940
941	vector<float>::reverse_iterator rbit = bordersRight.rbegin();
942
943	for (; rcit != rcit_end; ++ rcit, ++ rbit)
944	{
945	Intersectable obj = (rcit).mObject;
946	const AxisAlignedBox3 obox = obj->GetBox();
947
948	if (obox.Min(axis) < minBorder)
949	{
950	minBorder = obox.Min(axis);
951	}
952
953	(*rbit) = minBorder;
954	}
955
956	// temporary surface areas
957	float al = 0;
958	float ar = boxArea;
959
960	vector<float>::const_iterator bit = bordersRight.begin();
961	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
962
963	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
964	{
965	Intersectable obj = (cit).mObject;
966
967	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
968
969	objectsLeft += renderCost;
970	objectsRight -= renderCost;
971
972	const AxisAlignedBox3 obox = obj->GetBox();
973
974	// the borders of the bounding boxes have changed
975	if (obox.Max(axis) > maxBorder)
976	{
977	maxBorder = obox.Max(axis);
978	}
979
980	minBorder = (*bit);
981
982	AxisAlignedBox3 lbox = nodeBbox;
983	AxisAlignedBox3 rbox = nodeBbox;
984
985	lbox.SetMax(axis, maxBorder);
986	rbox.SetMin(axis, minBorder);
987
988	al = lbox.SurfaceArea();
989	ar = rbox.SurfaceArea();
990
991	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
992	const float sum = noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
993
994	/cout << "pos=" << (cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
995	<< lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
996	cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
997	cout << "cost= " << sum << endl;*/
998
999	if (sum < minSum)
1000	{
1001	minSum = sum;
1002	areaLeft = al;
1003	areaRight = ar;
1004
1005	// objects belong to left side now
1006	for (; currentPos != (cit + 1); ++ currentPos);
1007	}
1008	}
1009
1010	////////////
1011	//-- assign object to front and back volume
1012
1013	// belongs to back bv
1014	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1015	objectsBack.push_back((*cit).mObject);
1016
1017	// belongs to front bv
1018	for (cit = currentPos; cit != cit_end; ++ cit)
1019	objectsFront.push_back((*cit).mObject);
1020
1021	float newCost = minSum / boxArea;
1022	float ratio = newCost / totalRenderCost;
1023
1024	#ifdef GTP_DEBUG
1025	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1026	<< (int)tData.mNode->mObjects.size() << ")\t area=("
1027	<< areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1028	<< "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1029	#endif
1030
1031	return ratio;
1032	}
1033
1034	#else
1035
1036	float BvHierarchy::EvalSah(const BvhTraversalData &tData,
1037	const int axis,
1038	ObjectContainer &objectsFront,
1039	ObjectContainer &objectsBack)
1040	{
1041	// go through the lists, count the number of objects left and right
1042	// and evaluate the following cost funcion:
1043	// C = ct_div_ci + (ol + or) / queries
1044	PrepareLocalSubdivisionCandidates(tData, axis);
1045
1046	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
1047	float objectsLeft = 0, objectsRight = totalRenderCost;
1048
1049	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
1050
1051	const float minBox = nodeBbox.Min(axis);
1052	const float maxBox = nodeBbox.Max(axis);
1053	const float boxArea = nodeBbox.SurfaceArea();
1054
1055	float minSum = 1e20f;
1056
1057	Vector3 minBorder = nodeBbox.Max();
1058	Vector3 maxBorder = nodeBbox.Min();
1059
1060	float areaLeft = 0, areaRight = 0;
1061
1062	SortableEntryContainer::const_iterator currentPos =
1063	mSubdivisionCandidates->begin();
1064
1065	vector<Vector3> bordersRight;
1066
1067	// we keep track of both borders of the bounding boxes =>
1068	// store the events in descending order
1069	bordersRight.resize(mSubdivisionCandidates->size());
1070
1071	SortableEntryContainer::reverse_iterator rcit =
1072	mSubdivisionCandidates->rbegin(), rcit_end =
1073	mSubdivisionCandidates->rend();
1074
1075	vector<Vector3>::reverse_iterator rbit = bordersRight.rbegin();
1076
1077	for (; rcit != rcit_end; ++ rcit, ++ rbit)
1078	{
1079	Intersectable obj = (rcit).mObject;
1080	const AxisAlignedBox3 obox = obj->GetBox();
1081
1082	for (int i = 0; i < 3; ++ i)
1083	{
1084	if (obox.Min(i) < minBorder[i])
1085	{
1086	minBorder[i] = obox.Min(i);
1087	}
1088	}
1089
1090	(*rbit) = minBorder;
1091	}
1092
1093	// temporary surface areas
1094	float al = 0;
1095	float ar = boxArea;
1096
1097	vector<Vector3>::const_iterator bit = bordersRight.begin();
1098	SortableEntryContainer::const_iterator cit, cit_end =
1099	mSubdivisionCandidates->end();
1100
1101	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
1102	{
1103	Intersectable obj = (cit).mObject;
1104
1105	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1106
1107	objectsLeft += renderCost;
1108	objectsRight -= renderCost;
1109
1110	const AxisAlignedBox3 obox = obj->GetBox();
1111
1112	AxisAlignedBox3 lbox = nodeBbox;
1113	AxisAlignedBox3 rbox = nodeBbox;
1114
1115	// the borders of the left bounding box have changed
1116	for (int i = 0; i < 3; ++ i)
1117	{
1118	if (obox.Max(i) > maxBorder[i])
1119	{
1120	maxBorder[i] = obox.Max(i);
1121	}
1122	}
1123
1124	minBorder = (*bit);
1125
1126	lbox.SetMax(maxBorder);
1127	rbox.SetMin(minBorder);
1128
1129	al = lbox.SurfaceArea();
1130	ar = rbox.SurfaceArea();
1131
1132	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
1133	const float sum = noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
1134
1135	/cout << "pos=" << (cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
1136	<< lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
1137	cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
1138	cout << "cost= " << sum << endl;*/
1139
1140	if (sum < minSum)
1141	{
1142	minSum = sum;
1143	areaLeft = al;
1144	areaRight = ar;
1145
1146	// objects belong to left side now
1147	for (; currentPos != (cit + 1); ++ currentPos);
1148	}
1149	}
1150
1151	/////////////
1152	//-- assign object to front and back volume
1153
1154	// belongs to back bv
1155	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1156	objectsBack.push_back((*cit).mObject);
1157
1158	// belongs to front bv
1159	for (cit = currentPos; cit != cit_end; ++ cit)
1160	objectsFront.push_back((*cit).mObject);
1161
1162	float newCost = minSum / boxArea;
1163	float ratio = newCost / totalRenderCost;
1164
1165	#ifdef GTP_DEBUG
1166	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1167	<< (int)tData.mNode->mObjects.size() << ")\t area=("
1168	<< areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1169	<< "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1170	#endif
1171
1172	return ratio;
1173	}
1174
1175	#endif
1176
1177	static bool PrepareOutput(const int axis,
1178	const int leaves,
1179	ofstream &sumStats,
1180	ofstream &vollStats,
1181	ofstream &volrStats)
1182	{
1183	if ((axis == 0) && (leaves > 0) && (leaves < 90))
1184	{
1185	char str[64];
1186	sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
1187	sumStats.open(str);
1188	sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
1189	vollStats.open(str);
1190	sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
1191	volrStats.open(str);
1192	}
1193
1194	return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
1195	}
1196
1197
1198	static void PrintHeuristics(const float objectsRight,
1199	const float sum,
1200	const float volLeft,
1201	const float volRight,
1202	const float viewSpaceVol,
1203	ofstream &sumStats,
1204	ofstream &vollStats,
1205	ofstream &volrStats)
1206	{
1207	sumStats
1208	<< "#Position\n" << objectsRight << endl
1209	<< "#Sum\n" << sum / viewSpaceVol << endl
1210	<< "#Vol\n" << (volLeft + volRight) / viewSpaceVol << endl;
1211
1212	vollStats
1213	<< "#Position\n" << objectsRight << endl
1214	<< "#Vol\n" << volLeft / viewSpaceVol << endl;
1215
1216	volrStats
1217	<< "#Position\n" << objectsRight << endl
1218	<< "#Vol\n" << volRight / viewSpaceVol << endl;
1219	}
1220
1221
1222	float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
1223	const int axis,
1224	ObjectContainer &objectsFront,
1225	ObjectContainer &objectsBack)
1226	{
1227	/////////////////////////////////////////////
1228	//-- go through the lists, count the number of objects
1229	//-- left and right and evaluate the cost funcion
1230
1231	// prepare the heuristics by setting mailboxes and counters
1232	const float totalVol = PrepareHeuristics(tData, axis);
1233
1234	// local helper variables
1235	float volLeft = 0;
1236	float volRight = totalVol;
1237
1238	const float nTotalObjects = EvalAbsCost(tData.mNode->mObjects);
1239	float nObjectsLeft = 0;
1240	float nObjectsRight = nTotalObjects;
1241
1242	const float viewSpaceVol =
1243	mViewCellsManager->GetViewSpaceBox().GetVolume();
1244
1245	SortableEntryContainer::const_iterator backObjectsStart =
1246	mSubdivisionCandidates->begin();
1247
1248	/////////////////////////////////
1249	//-- the parameters for the current optimum
1250
1251	float volBack = volLeft;
1252	float volFront = volRight;
1253	float newRenderCost = nTotalObjects * totalVol;
1254
1255	#ifdef GTP_DEBUG
1256	ofstream sumStats;
1257	ofstream vollStats;
1258	ofstream volrStats;
1259
1260	const bool printStats = PrepareOutput(axis,
1261	mBvhStats.Leaves(),
1262	sumStats,
1263	vollStats,
1264	volrStats);
1265	#endif
1266
1267	///////////////////////
1268	//-- the sweep heuristics
1269	//-- traverse through events and find best split plane
1270
1271	SortableEntryContainer::const_iterator cit,
1272	cit_end = cit_end = mSubdivisionCandidates->end();
1273
1274	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
1275	{
1276	Intersectable object = (cit).mObject;
1277
1278	// evaluate change in l and r volume
1279	// voll = view cells that see only left node (i.e., left pvs)
1280	// volr = view cells that see only right node (i.e., right pvs)
1281	EvalHeuristicsContribution(object, volLeft, volRight);
1282
1283	const float rc = mViewCellsManager->EvalRenderCost(object);
1284
1285	nObjectsLeft += rc;
1286	nObjectsRight -= rc;
1287
1288	// split is only valid if #objects on left and right is not zero
1289	const bool noValidSplit = ((nObjectsLeft <= Limits::Small) \|\|
1290	(nObjectsRight <= Limits::Small));
1291
1292	// the heuristics
1293	const float sum = noValidSplit ?
1294	1e25 : volLeft * (float)nObjectsLeft + volRight * (float)nObjectsRight;
1295
1296	#ifdef GTP_DEBUG
1297	if (printStats)
1298	{
1299	PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
1300	sumStats, vollStats, volrStats);
1301	}
1302	#endif
1303
1304	if (sum < newRenderCost)
1305	{
1306	newRenderCost = sum;
1307
1308	volBack = volLeft;
1309	volFront = volRight;
1310
1311	// objects belongs to left side now
1312	for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
1313	}
1314	}
1315
1316	////////////////////////////////////////
1317	//-- assign object to front and back volume
1318
1319	// belongs to back bv
1320	for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
1321	{
1322	objectsBack.push_back((*cit).mObject);
1323	}
1324	// belongs to front bv
1325	for (cit = backObjectsStart; cit != cit_end; ++ cit)
1326	{
1327	objectsFront.push_back((*cit).mObject);
1328	}
1329
1330	// render cost of the old parent
1331	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
1332	// the relative cost ratio
1333	const float ratio = newRenderCost / oldRenderCost;
1334
1335	#ifdef GTP_DEBUG
1336	Debug << "\n§§§§ bvh eval const decrease §§§§" << endl
1337	<< "back pvs: " << (int)objectsBack.size() << " front pvs: "
1338	<< (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl
1339	<< "back p: " << volBack / viewSpaceVol << " front p "
1340	<< volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
1341	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: "
1342	<< newRenderCost / viewSpaceVol << endl
1343	<< "render cost decrease: "
1344	<< oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
1345	#endif
1346
1347	return ratio;
1348	}
1349
1350
1351	void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
1352	const int axis)
1353	{
1354	//-- insert object queries
1355	ObjectContainer *objects = mUseGlobalSorting ?
1356	tData.mSortedObjects[axis] : &tData.mNode->mObjects;
1357
1358	CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
1359	}
1360
1361
1362	void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
1363	SortableEntryContainer **subdivisionCandidates,
1364	const bool sort,
1365	const int axis)
1366	{
1367	(*subdivisionCandidates)->clear();
1368
1369	// compute requested size and look if subdivision candidate has to be recomputed
1370	const int requestedSize = (int)objects.size() * 2;
1371
1372	// creates a sorted split candidates array
1373	if ((*subdivisionCandidates)->capacity() > 500000 &&
1374	requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
1375	{
1376	delete (*subdivisionCandidates);
1377	(*subdivisionCandidates) = new SortableEntryContainer;
1378	}
1379
1380	(*subdivisionCandidates)->reserve(requestedSize);
1381
1382	ObjectContainer::const_iterator oit, oit_end = objects.end();
1383
1384	for (oit = objects.begin(); oit < oit_end; ++ oit)
1385	{
1386	Intersectable object = oit;
1387	const AxisAlignedBox3 &box = object->GetBox();
1388	const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
1389
1390	(*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
1391	}
1392
1393	if (sort)
1394	{ // no presorted candidate list
1395	stable_sort((subdivisionCandidates)->begin(), (subdivisionCandidates)->end());
1396	}
1397	}
1398
1399
1400	const BvhStatistics &BvHierarchy::GetStatistics() const
1401	{
1402	return mBvhStats;
1403	}
1404
1405
1406	float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData,
1407	const int axis)
1408	{
1409	BvhLeaf *leaf = tData.mNode;
1410	float vol = 0;
1411
1412	// sort so we can use a sweep from right to left
1413	PrepareLocalSubdivisionCandidates(tData, axis);
1414
1415	// collect and mark the view cells as belonging to front pvs
1416	ViewCellContainer viewCells;
1417
1418	const int numRays = CollectViewCells(tData.mNode->mObjects, viewCells, true, true);
1419	//cout << "number of rays: " << numRays << endl;
1420
1421	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1422	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1423	{
1424	#if USE_VOLUMES_FOR_HEURISTICS
1425	const float volIncr = (*vit)->GetVolume();
1426	#else
1427	const float volIncr = 1.0f;
1428	#endif
1429	vol += volIncr;
1430	}
1431
1432	// we will mail view cells switching to the back side
1433	ViewCell::NewMail();
1434
1435	return vol;
1436	}
1437
1438	///////////////////////////////////////////////////////////
1439
1440
1441	void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
1442	float &volLeft,
1443	float &volRight)
1444	{
1445	// collect all view cells associated with this objects
1446	// (also multiple times, if they are pierced by several rays)
1447	ViewCellContainer viewCells;
1448	const bool useMailboxing = false;
1449
1450	CollectViewCells(obj, viewCells, useMailboxing, false, true);
1451
1452	// classify view cells and compute volume contri accordingly
1453	// possible view cell classifications:
1454	// view cell mailed => view cell can be seen from left child node
1455	// view cell counter > 0 view cell can be seen from right child node
1456	// combined: view cell volume belongs to both nodes
1457	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1458
1459	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1460	{
1461	// view cells can also be seen from left child node
1462	ViewCell viewCell = vit;
1463	#if USE_VOLUMES_FOR_HEURISTICS
1464	const float vol = viewCell->GetVolume();
1465	#else
1466	const float vol = 1.0f;
1467	#endif
1468	if (!viewCell->Mailed())
1469	{
1470	viewCell->Mail();
1471	// we now see view cell from both nodes
1472	// => add volume to left node
1473	volLeft += vol;
1474	}
1475
1476	// last reference into the right node
1477	if (-- viewCell->mCounter == 0)
1478	{
1479	// view cell was previously seen from both nodes =>
1480	// remove volume from right node
1481	volRight -= vol;
1482	}
1483	}
1484	}
1485
1486
1487	void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
1488	{
1489	mViewCellsManager = vcm;
1490	}
1491
1492
1493	AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
1494	{
1495	return mBoundingBox;
1496	}
1497
1498
1499	float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
1500	ObjectContainer &frontObjects,
1501	ObjectContainer &backObjects,
1502	bool useVisibilityBasedHeuristics)
1503	{
1504	if (mIsInitialSubdivision)
1505	{
1506	ApplyInitialSplit(tData, frontObjects, backObjects);
1507	return 0;
1508	}
1509
1510	ObjectContainer nFrontObjects[3];
1511	ObjectContainer nBackObjects[3];
1512	float nCostRatio[3];
1513
1514	int sAxis = 0;
1515	int bestAxis = -1;
1516
1517	if (mOnlyDrivingAxis)
1518	{
1519	const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
1520	sAxis = box.Size().DrivingAxis();
1521	}
1522
1523	// only use a subset of the rays for visibility based heuristics
1524	if (mUseCostHeuristics && useVisibilityBasedHeuristics)
1525	{
1526	VssRayContainer rays;
1527	// maximal 2 objects share the same ray
1528	rays.reserve(tData.mNumRays * 2);
1529	CollectRays(tData.mNode->mObjects, rays);
1530
1531	const float prop = (float)mMaxTests / (float)tData.mNumRays;
1532
1533	VssRay::NewMail();
1534
1535	VssRayContainer::const_iterator rit, rit_end = rays.end();
1536
1537	int nRays = 0;
1538
1539	for (rit = rays.begin(); rit != rit_end; ++ rit)
1540	{
1541	if ((mMaxTests >= (int)rays.size()) \|\| (Random(1.0f) < prop))
1542	{
1543	(*rit)->Mail();
1544	++ nRays;
1545	}
1546	}
1547	}
1548
1549	////////////////////////////////////
1550	//-- evaluate split cost for all three axis
1551
1552	for (int axis = 0; axis < 3; ++ axis)
1553	{
1554	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
1555	{
1556	if (mUseCostHeuristics)
1557	{
1558	//////////////////////////////////
1559	//-- split objects using heuristics
1560
1561	if (useVisibilityBasedHeuristics)
1562	{
1563	///////////
1564	//-- heuristics using objects weighted by view cells volume
1565	nCostRatio[axis] =
1566	EvalLocalCostHeuristics(tData,
1567	axis,
1568	nFrontObjects[axis],
1569	nBackObjects[axis]);
1570	}
1571	else
1572	{
1573	//////////////////
1574	//-- view cells not constructed yet => use surface area heuristic
1575	nCostRatio[axis] = EvalSah(tData,
1576	axis,
1577	nFrontObjects[axis],
1578	nBackObjects[axis]);
1579	}
1580	}
1581	else
1582	{
1583	//-- split objects using some simple criteria
1584	nCostRatio[axis] =
1585	EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1586	}
1587
1588	// no good results for degenerate axis split
1589	if (1 &&
1590	(tData.mNode->GetBoundingBox().Size(axis) < 0.0001))//Limits::Small))
1591	{
1592	nCostRatio[axis] += 9999;
1593	}
1594
1595	if ((bestAxis == -1) \|\| (nCostRatio[axis] < nCostRatio[bestAxis]))
1596	{
1597	bestAxis = axis;
1598	}
1599	}
1600	}
1601
1602	////////////////
1603	//-- assign values
1604
1605	frontObjects = nFrontObjects[bestAxis];
1606	backObjects = nBackObjects[bestAxis];
1607
1608	//cout << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1609	return nCostRatio[bestAxis];
1610	}
1611
1612
1613	int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
1614	{
1615	int nRays = 0;
1616	VssRayContainer::const_iterator rit, rit_end = rays.end();
1617
1618	VssRay::NewMail();
1619
1620	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1621	{
1622	VssRay ray = (rit);
1623
1624	if (ray->mTerminationObject)
1625	{
1626	ray->mTerminationObject->GetOrCreateRays()->push_back(ray);
1627	if (!ray->Mailed())
1628	{
1629	ray->Mail();
1630	++ nRays;
1631	}
1632	}
1633
1634	#if COUNT_ORIGIN_OBJECTS
1635
1636	if (ray->mOriginObject)
1637	{
1638	ray->mOriginObject->GetOrCreateRays()->push_back(ray);
1639
1640	if (!ray->Mailed())
1641	{
1642	ray->Mail();
1643	++ nRays;
1644	}
1645	}
1646	#endif
1647	}
1648
1649	return nRays;
1650	}
1651
1652
1653	void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
1654	{
1655	const float costDecr = sc.GetRenderCostDecrease();
1656
1657	mSubdivisionStats
1658	<< "#Leaves\n" << mBvhStats.Leaves() << endl
1659	<< "#RenderCostDecrease\n" << costDecr << endl
1660	<< "#TotalRenderCost\n" << mTotalCost << endl
1661	<< "#EntriesInPvs\n" << mPvsEntries << endl;
1662	}
1663
1664
1665	void BvHierarchy::CollectRays(const ObjectContainer &objects,
1666	VssRayContainer &rays) const
1667	{
1668	VssRay::NewMail();
1669	ObjectContainer::const_iterator oit, oit_end = objects.end();
1670
1671	// evaluate reverse pvs and view cell volume on left and right cell
1672	// note: should I take all leaf objects or rather the objects hit by rays?
1673	for (oit = objects.begin(); oit != oit_end; ++ oit)
1674	{
1675	Intersectable obj = oit;
1676	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1677
1678	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1679	{
1680	VssRay ray = (rit);
1681
1682	if (!ray->Mailed())
1683	{
1684	ray->Mail();
1685	rays.push_back(ray);
1686	}
1687	}
1688	}
1689	}
1690
1691
1692	float BvHierarchy::EvalAbsCost(const ObjectContainer &objects)// const
1693	{
1694	#if USE_BETTER_RENDERCOST_EST
1695	ObjectContainer::const_iterator oit, oit_end = objects.end();
1696
1697	for (oit = objects.begin(); oit != oit_end; ++ oit)
1698	{
1699	objRenderCost += ViewCellsManager::GetRendercost(*oit);
1700	}
1701	#else
1702	return (float)objects.size();
1703	#endif
1704	}
1705
1706
1707	float BvHierarchy::EvalSahCost(BvhLeaf *leaf) const
1708	{
1709	////////////////
1710	//-- surface area heuristics
1711	if (leaf->mObjects.empty())
1712	return 0.0f;
1713
1714	const AxisAlignedBox3 box = GetBoundingBox(leaf);
1715	const float area = box.SurfaceArea();
1716	const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
1717
1718	return EvalAbsCost(leaf->mObjects) * area / viewSpaceArea;
1719	}
1720
1721
1722	float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
1723	{
1724	///////////////
1725	//-- render cost heuristics
1726
1727	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1728
1729	// probability that view point lies in a view cell which sees this node
1730	const float p = EvalViewCellsVolume(objects) / viewSpaceVol;
1731	const float objRenderCost = EvalAbsCost(objects);
1732
1733	return objRenderCost * p;
1734	}
1735
1736
1737	AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
1738	const AxisAlignedBox3 *parentBox) const
1739	{
1740	// if there are no objects in this box, box size is set to parent box size.
1741	// Question: Invalidate box instead?
1742	if (parentBox && objects.empty())
1743	return *parentBox;
1744
1745	AxisAlignedBox3 box;
1746	box.Initialize();
1747
1748	ObjectContainer::const_iterator oit, oit_end = objects.end();
1749
1750	for (oit = objects.begin(); oit != oit_end; ++ oit)
1751	{
1752	Intersectable obj = oit;
1753	// grow bounding box to include all objects
1754	box.Include(obj->GetBox());
1755	}
1756
1757	return box;
1758	}
1759
1760
1761	void BvHierarchy::CollectLeaves(BvhNode root, vector<BvhLeaf > &leaves) const
1762	{
1763	stack<BvhNode *> nodeStack;
1764	nodeStack.push(root);
1765
1766	while (!nodeStack.empty())
1767	{
1768	BvhNode *node = nodeStack.top();
1769	nodeStack.pop();
1770
1771	if (node->IsLeaf())
1772	{
1773	BvhLeaf leaf = (BvhLeaf )node;
1774	leaves.push_back(leaf);
1775	}
1776	else
1777	{
1778	BvhInterior interior = (BvhInterior )node;
1779
1780	nodeStack.push(interior->GetBack());
1781	nodeStack.push(interior->GetFront());
1782	}
1783	}
1784	}
1785
1786
1787	AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1788	{
1789	return node->GetBoundingBox();
1790	}
1791
1792
1793	int BvHierarchy::CollectViewCells(const ObjectContainer &objects,
1794	ViewCellContainer &viewCells,
1795	const bool setCounter,
1796	const bool onlyMailedRays) const
1797	{
1798	ViewCell::NewMail();
1799	ObjectContainer::const_iterator oit, oit_end = objects.end();
1800
1801	int numRays = 0;
1802	// loop through all object and collect view cell pvs of this node
1803	for (oit = objects.begin(); oit != oit_end; ++ oit)
1804	{
1805	// always use only mailed objects
1806	numRays += CollectViewCells(*oit, viewCells, true, setCounter, onlyMailedRays);
1807	}
1808
1809	return numRays;
1810	}
1811
1812
1813	int BvHierarchy::CollectViewCells(Intersectable *obj,
1814	ViewCellContainer &viewCells,
1815	const bool useMailBoxing,
1816	const bool setCounter,
1817	const bool onlyMailedRays) const
1818	{
1819	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1820
1821	int numRays = 0;
1822
1823	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1824	{
1825	VssRay ray = (rit);
1826
1827	if (onlyMailedRays && !ray->Mailed())
1828	{
1829	continue;
1830	}
1831
1832	++ numRays;
1833
1834	ViewCellContainer tmpViewCells;
1835	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1836
1837	// matt: probably slow to allocate memory for view cells every time
1838	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1839
1840	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1841	{
1842	ViewCell vc = vit;
1843
1844	// store view cells
1845	if (!useMailBoxing \|\| !vc->Mailed())
1846	{
1847	if (useMailBoxing) // => view cell not mailed
1848	{
1849	vc->Mail();
1850	if (setCounter)
1851	{
1852	vc->mCounter = 0;
1853	}
1854	}
1855
1856	viewCells.push_back(vc);
1857	}
1858
1859	if (setCounter)
1860	{
1861	++ vc->mCounter;
1862	}
1863	}
1864	}
1865
1866	return numRays;
1867	}
1868
1869
1870	int BvHierarchy::CountViewCells(Intersectable *obj) const
1871	{
1872	int result = 0;
1873
1874	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1875
1876	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1877	{
1878	VssRay ray = (rit);
1879	ViewCellContainer tmpViewCells;
1880
1881	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1882
1883	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1884	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1885	{
1886	ViewCell vc = vit;
1887
1888	// store view cells
1889	if (!vc->Mailed())
1890	{
1891	vc->Mail();
1892	++ result;
1893	}
1894	}
1895	}
1896
1897	return result;
1898	}
1899
1900
1901	int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
1902	{
1903	int nViewCells = 0;
1904	ViewCell::NewMail();
1905	ObjectContainer::const_iterator oit, oit_end = objects.end();
1906
1907	// loop through all object and collect view cell pvs of this node
1908	for (oit = objects.begin(); oit != oit_end; ++ oit)
1909	{
1910	nViewCells += CountViewCells(*oit);
1911	}
1912
1913	return nViewCells;
1914	}
1915
1916
1917	void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1918	vector<SubdivisionCandidate *> &dirtyList,
1919	const bool onlyUnmailed)
1920	{
1921	BvhTraversalData &tData = sc->mParentData;
1922	BvhLeaf *node = tData.mNode;
1923
1924	ViewCellContainer viewCells;
1925	//ViewCell::NewMail();
1926	int numRays = CollectViewCells(node->mObjects, viewCells, false, false);
1927
1928	if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
1929
1930	// split candidates handling
1931	// these view cells are thrown into dirty list
1932	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1933
1934	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1935	{
1936	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
1937	VspLeaf *leaf = vc->mLeaves[0];
1938
1939	SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
1940
1941	// is this leaf still a split candidate?
1942	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
1943	{
1944	candidate->Mail();
1945	candidate->SetDirty(true);
1946	dirtyList.push_back(candidate);
1947	}
1948	}
1949	}
1950
1951
1952	BvhNode *BvHierarchy::GetRoot() const
1953	{
1954	return mRoot;
1955	}
1956
1957
1958	bool BvHierarchy::IsObjectInLeaf(BvhLeaf leaf, Intersectable object) const
1959	{
1960	ObjectContainer::const_iterator oit =
1961	lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
1962
1963	// objects sorted by id
1964	if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
1965	{
1966	return true;
1967	}
1968	else
1969	{
1970	return false;
1971	}
1972	}
1973
1974
1975	BvhLeaf BvHierarchy::GetLeaf(Intersectable object, BvhNode *node) const
1976	{
1977	// rather use the simple version
1978	if (!object)
1979	return NULL;
1980	return object->mBvhLeaf;
1981
1982	///////////////////////////////////////
1983	// start from root of tree
1984
1985	if (node == NULL)
1986	node = mRoot;
1987
1988	vector<BvhLeaf *> leaves;
1989
1990	stack<BvhNode *> nodeStack;
1991	nodeStack.push(node);
1992
1993	BvhLeaf *leaf = NULL;
1994
1995	while (!nodeStack.empty())
1996	{
1997	BvhNode *node = nodeStack.top();
1998	nodeStack.pop();
1999
2000	if (node->IsLeaf())
2001	{
2002	leaf = dynamic_cast<BvhLeaf *>(node);
2003
2004	if (IsObjectInLeaf(leaf, object))
2005	{
2006	return leaf;
2007	}
2008	}
2009	else
2010	{
2011	// find point
2012	BvhInterior interior = dynamic_cast<BvhInterior >(node);
2013
2014	if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
2015	{
2016	nodeStack.push(interior->GetBack());
2017	}
2018
2019	// search both sides as we are using bounding volumes
2020	if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
2021	{
2022	nodeStack.push(interior->GetFront());
2023	}
2024	}
2025	}
2026
2027	return leaf;
2028	}
2029
2030
2031	bool BvHierarchy::Export(OUT_STREAM &stream)
2032	{
2033	ExportNode(mRoot, stream);
2034
2035	return true;
2036	}
2037
2038
2039	void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
2040	{
2041	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2042	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2043	{
2044	stream << (*oit)->GetId() << " ";
2045	}
2046	}
2047
2048
2049	void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
2050	{
2051	if (node->IsLeaf())
2052	{
2053	BvhLeaf leaf = dynamic_cast<BvhLeaf >(node);
2054	const AxisAlignedBox3 box = leaf->GetBoundingBox();
2055	stream << "<Leaf"
2056	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
2057	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
2058	<< " objects=\"";
2059
2060	//-- export objects
2061	// tmp matt
2062	if (0) ExportObjects(leaf, stream);
2063
2064	stream << "\" />" << endl;
2065	}
2066	else
2067	{
2068	BvhInterior interior = dynamic_cast<BvhInterior >(node);
2069	const AxisAlignedBox3 box = interior->GetBoundingBox();
2070
2071	stream << "<Interior"
2072	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
2073	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
2074	<< "\">" << endl;
2075
2076	ExportNode(interior->GetBack(), stream);
2077	ExportNode(interior->GetFront(), stream);
2078
2079	stream << "</Interior>" << endl;
2080	}
2081	}
2082
2083
2084	float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
2085	{
2086	float vol = 0;
2087
2088	ViewCellContainer viewCells;
2089
2090	// we have to account for all view cells that can
2091	// be seen from the objects
2092	int numRays = CollectViewCells(objects, viewCells, false, false);
2093
2094	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2095
2096	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2097	{
2098	vol += (*vit)->GetVolume();
2099	}
2100
2101	return vol;
2102	}
2103
2104
2105	void BvHierarchy::Initialise(const ObjectContainer &objects)
2106	{
2107	AxisAlignedBox3 box = EvalBoundingBox(objects);
2108
2109	///////
2110	//-- create new root
2111
2112	BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
2113	bvhleaf->mObjects = objects;
2114	mRoot = bvhleaf;
2115
2116	// compute bounding box from objects
2117	mBoundingBox = mRoot->GetBoundingBox();
2118
2119	// associate root with current objects
2120	AssociateObjectsWithLeaf(bvhleaf);
2121	}
2122
2123
2124	/*
2125	Mesh *BvHierarchy::MergeLeafToMesh()
2126	{
2127	vector<BvhLeaf *> leaves;
2128	CollectLeaves(leaves);
2129
2130	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2131
2132	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2133	{
2134	Mesh mesh = MergeLeafToMesh(lit);
2135	}
2136	}*/
2137
2138
2139	void BvHierarchy::PrepareConstruction(SplitQueue &tQueue,
2140	const VssRayContainer &sampleRays,
2141	const ObjectContainer &objects)
2142	{
2143	///////////////////////////////////////
2144	//-- we assume that we have objects sorted by their id =>
2145	//-- we don't have to sort them here and an binary search
2146	//-- for identifying if a object is in a leaf.
2147
2148	mBvhStats.Reset();
2149	mBvhStats.Start();
2150	mBvhStats.nodes = 1;
2151
2152	// store pointer to this tree
2153	BvhSubdivisionCandidate::sBvHierarchy = this;
2154
2155	// root and bounding box was already constructed
2156	BvhLeaf bvhLeaf = dynamic_cast<BvhLeaf >(mRoot);
2157
2158	// multiply termination criterium for comparison,
2159	// so it can be set between zero and one and
2160	// no division is necessary during traversal
2161
2162	#if PROBABILIY_IS_BV_VOLUME
2163	mTermMinProbability *= mBoundingBox.GetVolume();
2164	// probability that bounding volume is seen
2165	const float prop = GetBoundingBox().GetVolume();
2166	#else
2167	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2168	// probability that volume is "seen" from the view cells
2169	const float prop = EvalViewCellsVolume(objects);
2170	#endif
2171
2172	// only rays intersecting objects in node are interesting
2173	const int nRays = AssociateObjectsWithRays(sampleRays);
2174	//cout << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
2175
2176	// create bvh traversal data
2177	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2178
2179	// create sorted object lists for the first data
2180	if (mUseGlobalSorting)
2181	{
2182	AssignInitialSortedObjectList(oData, objects);
2183	}
2184
2185
2186	///////////////////
2187	//-- add first candidate for object space partition
2188
2189	BvhSubdivisionCandidate *oSubdivisionCandidate =
2190	new BvhSubdivisionCandidate(oData);
2191
2192	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2193
2194	mTotalCost = EvalRenderCost(objects);
2195	mPvsEntries = CountViewCells(objects);
2196
2197	if (mApplyInitialPartition)
2198	{
2199	vector<SubdivisionCandidate *> candidateContainer;
2200
2201	mIsInitialSubdivision = true;
2202
2203	// evaluate priority
2204	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2205	PrintSubdivisionStats(*oSubdivisionCandidate);
2206
2207	ApplyInitialSubdivision(oSubdivisionCandidate, candidateContainer);
2208
2209	mIsInitialSubdivision = false;
2210
2211	vector<SubdivisionCandidate *>::const_iterator cit, cit_end = candidateContainer.end();
2212
2213	for (cit = candidateContainer.begin(); cit != cit_end; ++ cit)
2214	{
2215	BvhSubdivisionCandidate sCandidate = dynamic_cast<BvhSubdivisionCandidate >(*cit);
2216
2217	// reevaluate priority
2218	EvalSubdivisionCandidate(*sCandidate);
2219	tQueue.Push(sCandidate);
2220	}
2221	}
2222	else
2223	{
2224	// evaluate priority
2225	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2226	PrintSubdivisionStats(*oSubdivisionCandidate);
2227
2228	tQueue.Push(oSubdivisionCandidate);
2229	}
2230
2231	cout << "size of initial bv subdivision: " << GetStatistics().Leaves() << endl;
2232	}
2233
2234
2235	void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData,
2236	const ObjectContainer &objects)
2237	{
2238	// we sort the objects as a preprocess so they don't have
2239	// to be sorted for each split
2240	for (int i = 0; i < 3; ++ i)
2241	{
2242	SortableEntryContainer *sortedObjects = new SortableEntryContainer();
2243
2244	CreateLocalSubdivisionCandidates(objects,
2245	&sortedObjects,
2246	true,
2247	i);
2248
2249	// copy list into traversal data list
2250	tData.mSortedObjects[i] = new ObjectContainer();
2251	tData.mSortedObjects[i]->reserve((int)objects.size());
2252
2253	SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
2254
2255	for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
2256	{
2257	tData.mSortedObjects[i]->push_back((*oit).mObject);
2258	}
2259
2260	delete sortedObjects;
2261	}
2262
2263	// last sorted list: by size
2264	tData.mSortedObjects[3] = new ObjectContainer();
2265	tData.mSortedObjects[3]->reserve((int)objects.size());
2266
2267	*(tData.mSortedObjects[3]) = objects;
2268	stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
2269	}
2270
2271
2272	void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
2273	BvhTraversalData &frontData,
2274	BvhTraversalData &backData)
2275	{
2276	Intersectable::NewMail();
2277
2278	// we sorted the objects as a preprocess so they don't have
2279	// to be sorted for each split
2280	ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
2281
2282	for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
2283	{
2284	(*fit)->Mail();
2285	}
2286
2287	for (int i = 0; i < 4; ++ i)
2288	{
2289	frontData.mSortedObjects[i] = new ObjectContainer();
2290	backData.mSortedObjects[i] = new ObjectContainer();
2291
2292	frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2293	backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2294
2295	ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();
2296
2297	for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
2298	{
2299	if ((*oit)->Mailed())
2300	{
2301	frontData.mSortedObjects[i]->push_back(*oit);
2302	}
2303	else
2304	{
2305	backData.mSortedObjects[i]->push_back(*oit);
2306	}
2307	}
2308	}
2309	}
2310
2311
2312	void BvHierarchy::Reset(SplitQueue &tQueue,
2313	const VssRayContainer &sampleRays,
2314	const ObjectContainer &objects)
2315	{
2316	// reset stats
2317	mBvhStats.Reset();
2318	mBvhStats.Start();
2319	mBvhStats.nodes = 1;
2320
2321	// reset root
2322	DEL_PTR(mRoot);
2323
2324	BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
2325	bvhleaf->mObjects = objects;
2326	mRoot = bvhleaf;
2327
2328	#if PROBABILIY_IS_BV_VOLUME
2329	mTermMinProbability *= mBoundingBox.GetVolume();
2330	// probability that bounding volume is seen
2331	const float prop = GetBoundingBox().GetVolume();
2332	#else
2333	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2334	// probability that volume is "seen" from the view cells
2335	const float prop = EvalViewCellsVolume(objects);
2336	#endif
2337
2338	const int nRays = CountRays(objects);
2339	BvhLeaf bvhLeaf = dynamic_cast<BvhLeaf >(mRoot);
2340
2341	// create bvh traversal data
2342	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2343
2344	AssignInitialSortedObjectList(oData, objects);
2345
2346
2347	///////////////////
2348	//-- add first candidate for object space partition
2349
2350	BvhSubdivisionCandidate *oSubdivisionCandidate =
2351	new BvhSubdivisionCandidate(oData);
2352
2353	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2354	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2355
2356	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2357	mTotalCost = (float)objects.size() * prop / viewSpaceVol;
2358
2359	PrintSubdivisionStats(*oSubdivisionCandidate);
2360
2361	tQueue.Push(oSubdivisionCandidate);
2362	}
2363
2364
2365	void BvhStatistics::Print(ostream &app) const
2366	{
2367	app << "=========== BvHierarchy statistics ===============\n";
2368
2369	app << setprecision(4);
2370
2371	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
2372
2373	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
2374
2375	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
2376
2377	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
2378
2379	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;
2380
2381	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
2382	<< maxCostNodes * 100 / (double)Leaves() << endl;
2383
2384	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
2385	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
2386
2387
2388	//////////////////////////////////////////////////
2389
2390	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
2391	<< maxDepthNodes * 100 / (double)Leaves() << endl;
2392
2393	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
2394
2395	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
2396
2397	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
2398
2399
2400	////////////////////////////////////////////////////////
2401
2402	app << "#N_PMINOBJECTSLEAVES ( Percentage of leaves with mininum objects )\n"
2403	<< minObjectsNodes * 100 / (double)Leaves() << endl;
2404
2405	app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
2406
2407	app << "#N_MINOBJECTREFS ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";
2408
2409	app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
2410
2411	app << "#N_PAVGOBJECTSLEAVES ( average object refs / leaf)\n" << AvgObjectRefs() << endl;
2412
2413
2414	////////////////////////////////////////////////////////
2415
2416	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with mininum rays )\n"
2417	<< minRaysNodes * 100 / (double)Leaves() << endl;
2418
2419	app << "#N_MAXRAYREFS ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";
2420
2421	app << "#N_MINRAYREFS ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
2422
2423	app << "#N_PAVGRAYLEAVES ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
2424
2425	app << "#N_PAVGRAYCONTRIBLEAVES ( Average ray contribution)\n" <<
2426	rayRefs / (double)objectRefs << endl;
2427
2428	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<<
2429	maxRayContriNodes * 100 / (double)Leaves() << endl;
2430
2431	app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
2432
2433	app << "========== END OF BvHierarchy statistics ==========\n";
2434	}
2435
2436
2437	// TODO: return memory usage in MB
2438	float BvHierarchy::GetMemUsage() const
2439	{
2440	return (float)(sizeof(BvHierarchy)
2441	+ mBvhStats.Leaves() * sizeof(BvhLeaf)
2442	+ mBvhStats.Interior() * sizeof(BvhInterior)
2443	) / float(1024 * 1024);
2444	}
2445
2446
2447	void BvHierarchy::SetActive(BvhNode *node) const
2448	{
2449	vector<BvhLeaf *> leaves;
2450
2451	// sets the pointers to the currently active view cells
2452	CollectLeaves(node, leaves);
2453	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2454
2455	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2456	{
2457	(*lit)->SetActiveNode(node);
2458	}
2459	}
2460
2461
2462	BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue,
2463	SubdivisionCandidate *splitCandidate)
2464	{
2465	BvhSubdivisionCandidate *sc =
2466	dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
2467	BvhTraversalData &tData = sc->mParentData;
2468
2469	BvhNode *currentNode = tData.mNode;
2470	BvhNode oldNode = (BvhNode )splitCandidate->mEvaluationHack;
2471
2472	if (!oldNode->IsLeaf())
2473	{
2474	//////////////
2475	//-- continue subdivision
2476
2477	BvhTraversalData tFrontData;
2478	BvhTraversalData tBackData;
2479
2480	BvhInterior oldInterior = dynamic_cast<BvhInterior >(oldNode);
2481
2482	sc->mFrontObjects.clear();
2483	sc->mBackObjects.clear();
2484
2485	oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
2486	oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
2487
2488	// evaluate the changes in render cost and pvs entries
2489	EvalSubdivisionCandidate(*sc, false);
2490
2491	// create new interior node and two leaf node
2492	currentNode = SubdivideNode(*sc, tFrontData, tBackData);
2493
2494	//oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
2495	//oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
2496
2497	//oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
2498	//oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
2499
2500	///////////////////////////
2501	//-- push the new split candidates on the queue
2502
2503	BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
2504	BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
2505
2506	frontCandidate->SetPriority((float)-oldInterior->GetFront()->GetTimeStamp());
2507	backCandidate->SetPriority((float)-oldInterior->GetBack()->GetTimeStamp());
2508
2509	frontCandidate->mEvaluationHack = oldInterior->GetFront();
2510	backCandidate->mEvaluationHack = oldInterior->GetBack();
2511
2512	// cross reference
2513	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
2514	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
2515
2516	//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
2517	tQueue.Push(frontCandidate);
2518	tQueue.Push(backCandidate);
2519	}
2520
2521	/////////////////////////////////
2522	//-- node is a leaf => terminate traversal
2523
2524	if (currentNode->IsLeaf())
2525	{
2526	// this leaf is no candidate for splitting anymore
2527	// => detach subdivision candidate
2528	tData.mNode->SetSubdivisionCandidate(NULL);
2529	// detach node so we don't delete it with the traversal data
2530	tData.mNode = NULL;
2531	}
2532
2533	return currentNode;
2534	}
2535
2536
2537	void BvHierarchy::CollectObjects(const AxisAlignedBox3 &box,
2538	ObjectContainer &objects)
2539	{
2540	stack<BvhNode *> nodeStack;
2541
2542	nodeStack.push(mRoot);
2543
2544	while (!nodeStack.empty()) {
2545	BvhNode *node = nodeStack.top();
2546
2547	nodeStack.pop();
2548	if (node->IsLeaf()) {
2549	BvhLeaf leaf = (BvhLeaf )node;
2550	if (Overlap(box, leaf->GetBoundingBox())) {
2551	Intersectable *object = leaf;
2552	if (!object->Mailed()) {
2553	object->Mail();
2554	objects.push_back(object);
2555	}
2556	}
2557	}
2558	else
2559	{
2560	BvhInterior interior = (BvhInterior )node;
2561	if (Overlap(box, interior->GetBoundingBox())) {
2562	bool pushed = false;
2563	if (!interior->GetFront()->Mailed()) {
2564	nodeStack.push(interior->GetFront());
2565	pushed = true;
2566	}
2567	if (!interior->GetBack()->Mailed()) {
2568	nodeStack.push(interior->GetBack());
2569	pushed = true;
2570	}
2571	// avoid traversal of this node in the next query
2572	if (!pushed)
2573	interior->Mail();
2574	}
2575	}
2576	}
2577	}
2578
2579
2580	void BvHierarchy::CreateUniqueObjectIds()
2581	{
2582	stack<BvhNode *> nodeStack;
2583	nodeStack.push(mRoot);
2584
2585	int currentId = 0;
2586	while (!nodeStack.empty())
2587	{
2588	BvhNode *node = nodeStack.top();
2589	nodeStack.pop();
2590
2591	node->SetId(currentId ++);
2592
2593	if (!node->IsLeaf())
2594	{
2595	BvhInterior interior = (BvhInterior )node;
2596
2597	nodeStack.push(interior->GetFront());
2598	nodeStack.push(interior->GetBack());
2599	}
2600	}
2601	}
2602
2603
2604	void BvHierarchy::ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
2605	vector<SubdivisionCandidate *> &candidateContainer)
2606	{
2607	SplitQueue tempQueue;
2608	tempQueue.Push(firstCandidate);
2609
2610	while (!tempQueue.Empty())
2611	{
2612	SubdivisionCandidate *candidate = tempQueue.Top();
2613	tempQueue.Pop();
2614
2615	BvhSubdivisionCandidate *bsc =
2616	dynamic_cast<BvhSubdivisionCandidate *>(candidate);
2617
2618	if (!InitialTerminationCriteriaMet(bsc->mParentData))
2619	{
2620	const bool globalCriteriaMet = GlobalTerminationCriteriaMet(bsc->mParentData);
2621
2622	BvhNode *node = Subdivide(tempQueue, bsc, globalCriteriaMet);
2623
2624	// not needed anymore
2625	delete bsc;
2626	}
2627	else // initial preprocessing finished for this candidate
2628	{
2629	// add to candidate container
2630	candidateContainer.push_back(bsc);
2631	}
2632	}
2633	}
2634
2635
2636	void BvHierarchy::ApplyInitialSplit(const BvhTraversalData &tData,
2637	ObjectContainer &frontObjects,
2638	ObjectContainer &backObjects)
2639	{
2640	ObjectContainer *objects = tData.mSortedObjects[3];
2641
2642	ObjectContainer::const_iterator oit, oit_end = objects->end();
2643
2644	float maxAreaDiff = -1.0f;
2645
2646	ObjectContainer::const_iterator backObjectsStart = objects->begin();
2647
2648	for (oit = objects->begin(); oit != (objects->end() - 1); ++ oit)
2649	{
2650	Intersectable objS = oit;
2651	Intersectable objL = (oit + 1);
2652
2653	const float areaDiff =
2654	objL->GetBox().SurfaceArea() - objS->GetBox().SurfaceArea();
2655
2656	if (areaDiff > maxAreaDiff)
2657	{
2658	maxAreaDiff = areaDiff;
2659	backObjectsStart = oit + 1;
2660	}
2661	}
2662
2663	// belongs to back bv
2664	for (oit = objects->begin(); oit != backObjectsStart; ++ oit)
2665	{
2666	frontObjects.push_back(*oit);
2667	}
2668
2669	// belongs to front bv
2670	for (oit = backObjectsStart; oit != oit_end; ++ oit)
2671	{
2672	backObjects.push_back(*oit);
2673	}
2674
2675	cout << "front: " << (int)frontObjects.size() << " back: " << (int)backObjects.size() << " "
2676	<< backObjects.front()->GetBox().SurfaceArea() - frontObjects.back()->GetBox().SurfaceArea() << endl;
2677	}
2678
2679
2680	inline static float AreaRatio(Intersectable smallObj, Intersectable largeObj)
2681	{
2682	const float areaSmall = smallObj->GetBox().SurfaceArea();
2683	const float areaLarge = largeObj->GetBox().SurfaceArea();
2684
2685	return areaSmall / (areaLarge - areaSmall + Limits::Small);
2686	}
2687
2688
2689	bool BvHierarchy::InitialTerminationCriteriaMet(const BvhTraversalData &tData) const
2690	{
2691	const bool terminationCriteriaMet =
2692	(0
2693	\|\| ((int)tData.mNode->mObjects.size() < mInitialMinObjects)
2694	\|\| (tData.mNode->mObjects.back()->GetBox().SurfaceArea() < mInitialMinArea)
2695	\|\| (AreaRatio(tData.mNode->mObjects.front(), tData.mNode->mObjects.back()) > mInitialMaxAreaRatio)
2696	);
2697
2698	cout << "criteria met: "<< terminationCriteriaMet << "\n"
2699	<< "size: " << (int)tData.mNode->mObjects.size() << " max: " << mInitialMinObjects << endl
2700	<< "ratio: " << AreaRatio(tData.mNode->mObjects.front(), tData.mNode->mObjects.back()) << " max: " << mInitialMaxAreaRatio << endl
2701	<< "area: " << tData.mNode->mObjects.back()->GetBox().SurfaceArea() << " max: " << mInitialMinArea << endl << endl;
2702
2703	return terminationCriteriaMet;
2704	}
2705
2706
2707	// HACK
2708	float BvHierarchy::GetRenderCostIncrementially(BvhNode *node) const
2709	{
2710	if (node->mRenderCost < 0)
2711	{
2712	//cout <<"p";
2713	if (node->IsLeaf())
2714	{
2715	BvhLeaf leaf = dynamic_cast<BvhLeaf >(node);
2716	node->mRenderCost = EvalAbsCost(leaf->mObjects);
2717	}
2718	else
2719	{
2720	BvhInterior interior = dynamic_cast<BvhInterior >(node);
2721
2722	node->mRenderCost = GetRenderCostIncrementially(interior->GetFront()) +
2723	GetRenderCostIncrementially(interior->GetBack());
2724	}
2725	}
2726
2727	return node->mRenderCost;
2728	}
2729
2730
2731	void BvHierarchy::Compress()
2732	{
2733	}
2734
2735
2736	}

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

Download in other formats: