Context Navigation

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

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

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

Download in other formats: