Context Navigation

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

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

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

Download in other formats: