Context Navigation

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

Revision 1727, 64.8 KB checked in by mattausch, 18 years ago (diff)
implemented several accelleration svhemes for the gradient method

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

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

Download in other formats: