Context Navigation

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

Revision 2543, 85.9 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: