Context Navigation

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

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

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

Download in other formats: