Context Navigation

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

Revision 2229, 86.4 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: