Context Navigation

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

Revision 2206, 85.0 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: