Context Navigation

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

Revision 1914, 74.7 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: