Context Navigation

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

Revision 2560, 85.9 KB checked in by mattausch, 17 years ago (diff)
added functionality for visualization

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

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

Download in other formats: