Context Navigation

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

Revision 2199, 83.0 KB checked in by mattausch, 17 years ago (diff)
using mutationsamples for evaluation

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

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

Download in other formats: