Context Navigation

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

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

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

Download in other formats: