Context Navigation

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

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

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

Download in other formats: