Context Navigation

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

Revision 1713, 64.1 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: