Context Navigation

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

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

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

Download in other formats: