Context Navigation

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

Revision 2005, 75.5 KB checked in by mattausch, 17 years ago (diff)
using large address space

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

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

Download in other formats: