Context Navigation

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

Revision 1890, 72.2 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: