Context Navigation

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

Revision 2350, 86.0 KB checked in by mattausch, 18 years ago (diff)
fixed new evaluation method

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

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

Download in other formats: