Context Navigation

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

Revision 1785, 69.0 KB checked in by bittner, 18 years ago (diff)
merge, filter update, renderebuffer made functional

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

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

Download in other formats: