Context Navigation

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

Revision 2210, 85.2 KB checked in by mattausch, 17 years ago (diff)
improved performance of osp

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

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

Download in other formats: