Context Navigation

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

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

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

Download in other formats: