Context Navigation

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

Revision 1933, 74.7 KB checked in by mattausch, 17 years ago (diff)
worked on gvs reverse sampling (still in debug state)

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

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

Download in other formats: