Context Navigation

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

Revision 1733, 65.7 KB checked in by mattausch, 18 years ago (diff)
removed bug from dirtycandidates

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

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

Download in other formats: