Context Navigation

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

Revision 1778, 66.9 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "BvHierarchy.h"
6	#include "ViewCell.h"
7	#include "Plane3.h"
8	#include "Mesh.h"
9	#include "common.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellsManager.h"
17	#include "Beam.h"
18	#include "VspTree.h"
19	#include "HierarchyManager.h"
20
21
22	namespace GtpVisibilityPreprocessor {
23
24
25	#define PROBABILIY_IS_BV_VOLUME 1
26	#define USE_FIXEDPOINT_T 0
27	#define USE_VOLUMES_FOR_HEURISTICS 1
28
29	//int BvhNode::sMailId = 10000; //2147483647;
30	//int BvhNode::sReservedMailboxes = 1;
31
32	BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;
33
34
35	/// sorting operator
36	inline static bool ilt(Intersectable obj1, Intersectable obj2)
37	{
38	return obj1->mId < obj2->mId;
39	}
40
41
42	/// sorting operator
43	inline static bool ilt2(Intersectable obj1, Intersectable obj2)
44	{
45	return obj1->GetBox().SurfaceArea() < obj2->GetBox().SurfaceArea();
46	}
47
48	/***************************************************************/
49	/* class BvhNode implementation */
50	/***************************************************************/
51
52	BvhNode::BvhNode():
53	mParent(NULL),
54	mTimeStamp(0)
55	{
56
57	}
58
59	BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
60	mParent(NULL),
61	mBoundingBox(bbox),
62	mTimeStamp(0)
63	{
64	}
65
66
67	BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
68	mBoundingBox(bbox),
69	mParent(parent),
70	mTimeStamp(0)
71	{
72	}
73
74
75	bool BvhNode::IsRoot() const
76	{
77	return mParent == NULL;
78	}
79
80
81	BvhInterior *BvhNode::GetParent()
82	{
83	return mParent;
84	}
85
86
87	void BvhNode::SetParent(BvhInterior *parent)
88	{
89	mParent = parent;
90	}
91
92
93	int BvhNode::GetRandomEdgePoint(Vector3 &point,
94	Vector3 &normal)
95	{
96	// get random edge
97	const int idx = Random(12);
98	Vector3 a, b;
99	mBoundingBox.GetEdge(idx, &a, &b);
100
101	const float w = RandomValue(0.0f, 1.0f);
102
103	point = a * w + b * (1.0f - w);
104
105	// TODO
106	normal = Vector3(0);
107
108	return idx;
109	}
110
111
112
113	/******************************************************************/
114	/* class BvhInterior implementation */
115	/******************************************************************/
116
117
118	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
119	BvhNode(bbox),
120	mSubdivisionCandidate(NULL)
121	{
122	mActiveNode = this;
123	}
124
125
126	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
127	BvhNode(bbox, parent)
128	{
129	mActiveNode = this;
130	}
131
132
133	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox,
134	BvhInterior *parent,
135	const int numObjects):
136	BvhNode(bbox, parent)
137	{
138	mObjects.reserve(numObjects);
139	mActiveNode = this;
140	}
141
142
143	bool BvhLeaf::IsLeaf() const
144	{
145	return true;
146	}
147
148
149	BvhLeaf::~BvhLeaf()
150	{
151	}
152
153
154	void BvhLeaf::CollectObjects(ObjectContainer &objects)
155	{
156	ObjectContainer::const_iterator oit, oit_end = mObjects.end();
157	for (oit = mObjects.begin(); oit != oit_end; ++ oit)
158	{
159	objects.push_back(*oit);
160	}
161	}
162
163	/******************************************************************/
164	/* class BvhInterior implementation */
165	/******************************************************************/
166
167
168	BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
169	BvhNode(bbox), mFront(NULL), mBack(NULL)
170	{
171	}
172
173
174	BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
175	BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
176	{
177	}
178
179
180	void BvhInterior::ReplaceChildLink(BvhNode oldChild, BvhNode newChild)
181	{
182	if (mBack == oldChild)
183	mBack = newChild;
184	else
185	mFront = newChild;
186	}
187
188
189	bool BvhInterior::IsLeaf() const
190	{
191	return false;
192	}
193
194
195	BvhInterior::~BvhInterior()
196	{
197	DEL_PTR(mFront);
198	DEL_PTR(mBack);
199	}
200
201
202	void BvhInterior::SetupChildLinks(BvhNode front, BvhNode back)
203	{
204	mBack = back;
205	mFront = front;
206	}
207
208
209	void BvhInterior::CollectObjects(ObjectContainer &objects)
210	{
211	mFront->CollectObjects(objects);
212	mBack->CollectObjects(objects);
213	}
214
215
216	/*******************************************************************/
217	/* class BvHierarchy implementation */
218	/*******************************************************************/
219
220
221	BvHierarchy::BvHierarchy():
222	mRoot(NULL),
223	mTimeStamp(1)
224	{
225	ReadEnvironment();
226	mSubdivisionCandidates = new SortableEntryContainer;
227	for (int i = 0; i < 4; ++ i)
228	mSortedObjects[i] = NULL;
229	}
230
231
232	BvHierarchy::~BvHierarchy()
233	{
234	// delete the local subdivision candidates
235	DEL_PTR(mSubdivisionCandidates);
236
237	// delete the presorted objects
238	for (int i = 0; i < 4; ++ i)
239	{
240	DEL_PTR(mSortedObjects[i]);
241	}
242
243	// delete the tree
244	DEL_PTR(mRoot);
245	}
246
247
248	void BvHierarchy::ReadEnvironment()
249	{
250	bool randomize = false;
251	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
252
253	// initialise random generator for heuristics
254	if (randomize)
255	Randomize();
256
257	//////////////////////////////
258	//-- termination criteria for autopartition
259
260	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
261	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
262	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
263	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
264	Environment::GetSingleton()->GetFloatValue(
265	"BvHierarchy.Termination.minProbability", mTermMinProbability);
266	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);
267
268
269	//////////////////////////////
270	//-- max cost ratio for early tree termination
271
272	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);
273	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
274	mTermMinGlobalCostRatio);
275	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance",
276	mTermGlobalCostMissTolerance);
277
278
279	//////////////////////////////
280	//-- factors for subdivision heuristics
281
282	// if only the driving axis is used for splits
283	Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
284	Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
285	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);
286	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useSah", mUseSah);
287
288	char subdivisionStatsLog[100];
289	Environment::GetSingleton()->GetStringValue("BvHierarchy.subdivisionStats", subdivisionStatsLog);
290	mSubdivisionStats.open(subdivisionStatsLog);
291
292	Environment::GetSingleton()->GetFloatValue(
293	"BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
294	Environment::GetSingleton()->GetBoolValue(
295	"BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
296	Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
297	Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests);
298
299	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
300	//mMemoryConst = (float)sizeof(BvhLeaf);
301	mMemoryConst = 16;//(float)sizeof(ObjectContainer);
302
303	mUseBboxAreaForSah = true;
304
305	/////////////
306	//-- debug output
307
308	Debug << "***** Bvh hierarchy options ****** " << endl;
309	Debug << "max depth: " << mTermMaxDepth << endl;
310	Debug << "min probabiliy: " << mTermMinProbability<< endl;
311	Debug << "min objects: " << mTermMinObjects << endl;
312	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
313	Debug << "miss tolerance: " << mTermMissTolerance << endl;
314	Debug << "max leaves: " << mTermMaxLeaves << endl;
315	Debug << "randomize: " << randomize << endl;
316	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
317	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
318	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
319	Debug << "max memory: " << mMaxMemory << endl;
320	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
321	Debug << "use surface area heuristics: " << mUseSah << endl;
322	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
323	Debug << "split borders: " << mSplitBorder << endl;
324	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
325	Debug << "use global sort: " << mUseGlobalSorting << endl;
326	Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
327	Debug << "bvh mem const: " << mMemoryConst << endl;
328
329	Debug << endl;
330	}
331
332
333	void BvHierarchy::AssociateObjectsWithLeaf(BvhLeaf *leaf)
334	{
335	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
336
337	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
338	{
339	(*oit)->mBvhLeaf = leaf;
340	}
341	}
342
343
344	static int CountRays(const ObjectContainer &objects)
345	{
346	int nRays = 0;
347
348	ObjectContainer::const_iterator oit, oit_end = objects.end();
349
350	for (oit = objects.begin(); oit != oit_end; ++ oit)
351	{
352	nRays += (int)(*oit)->GetOrCreateRays()->size();
353	}
354
355	return nRays;
356	}
357
358
359	BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
360	BvhTraversalData &frontData,
361	BvhTraversalData &backData)
362	{
363	const BvhTraversalData &tData = sc.mParentData;
364	BvhLeaf *leaf = tData.mNode;
365	AxisAlignedBox3 parentBox = leaf->GetBoundingBox();
366
367	// update stats: we have two new leaves
368	mBvhStats.nodes += 2;
369
370	if (tData.mDepth > mBvhStats.maxDepth)
371	{
372	mBvhStats.maxDepth = tData.mDepth;
373	}
374
375	// add the new nodes to the tree
376	BvhInterior *node = new BvhInterior(parentBox, leaf->GetParent());
377
378
379	//////////////////
380	//-- create front and back leaf
381
382	AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
383	AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);
384
385	BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
386	BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
387
388	BvhInterior *parent = leaf->GetParent();
389
390	// replace a link from node's parent
391	if (parent)
392	{
393	parent->ReplaceChildLink(leaf, node);
394	node->SetParent(parent);
395	}
396	else // no parent => this node is the root
397	{
398	mRoot = node;
399	}
400
401	// and setup child links
402	node->SetupChildLinks(front, back);
403
404	++ mBvhStats.splits;
405
406
407	////////////////////////////////////////
408	//-- fill front and back traversal data with the new values
409
410	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
411
412	frontData.mNode = front;
413	backData.mNode = back;
414
415	back->mObjects = sc.mBackObjects;
416	front->mObjects = sc.mFrontObjects;
417
418	// if the number of rays is too low, no assumptions can be made
419	// (=> switch to surface area heuristics?)
420	frontData.mNumRays = CountRays(sc.mFrontObjects);
421	backData.mNumRays = CountRays(sc.mBackObjects);
422
423	AssociateObjectsWithLeaf(back);
424	AssociateObjectsWithLeaf(front);
425
426	#if PROBABILIY_IS_BV_VOLUME
427	// volume of bvh (= probability that this bvh can be seen)
428	frontData.mProbability = fbox.GetVolume();
429	backData.mProbability = bbox.GetVolume();
430	#else
431	// compute probability of this node being visible,
432	// i.e., volume of the view cells that can see this node
433	frontData.mProbability = EvalViewCellsVolume(sc.mFrontObjects);
434	backData.mProbability = EvalViewCellsVolume(sc.mBackObjects);
435	#endif
436
437	// how often was max cost ratio missed in this branch?
438	frontData.mMaxCostMisses = sc.GetMaxCostMisses();
439	backData.mMaxCostMisses = sc.GetMaxCostMisses();
440
441	// set the time stamp so the order of traversal can be reconstructed
442	node->SetTimeStamp(mHierarchyManager->mTimeStamp ++);
443
444	// assign the objects in sorted order
445	if (mUseGlobalSorting)
446	{
447	AssignSortedObjects(sc, frontData, backData);
448	}
449
450	// return the new interior node
451	return node;
452	}
453
454
455	BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
456	SubdivisionCandidate *splitCandidate,
457	const bool globalCriteriaMet)
458	{
459	BvhSubdivisionCandidate sc = dynamic_cast<BvhSubdivisionCandidate >(splitCandidate);
460	BvhTraversalData &tData = sc->mParentData;
461
462	BvhNode *currentNode = tData.mNode;
463
464	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
465	{
466	//////////////
467	//-- continue subdivision
468
469	BvhTraversalData tFrontData;
470	BvhTraversalData tBackData;
471
472	// create new interior node and two leaf node
473	currentNode = SubdivideNode(*sc, tFrontData, tBackData);
474
475	// decrease the weighted average cost of the subdivisoin
476	mTotalCost -= sc->GetRenderCostDecrease();
477	mPvsEntries += sc->GetPvsEntriesIncr();
478
479	// subdivision statistics
480	if (1) PrintSubdivisionStats(*sc);
481
482
483	///////////////////////////
484	//-- push the new split candidates on the queue
485
486	BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
487	BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
488
489	EvalSubdivisionCandidate(*frontCandidate);
490	EvalSubdivisionCandidate(*backCandidate);
491
492	// cross reference
493	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
494	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
495
496	//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
497	tQueue.Push(frontCandidate);
498	tQueue.Push(backCandidate);
499	}
500
501	/////////////////////////////////
502	//-- node is a leaf => terminate traversal
503
504	if (currentNode->IsLeaf())
505	{
506	/////////////////////
507	//-- store additional info
508	EvaluateLeafStats(tData);
509
510	// this leaf is no candidate for splitting anymore
511	// => detach subdivision candidate
512	tData.mNode->SetSubdivisionCandidate(NULL);
513	// detach node so we don't delete it with the traversal data
514	tData.mNode = NULL;
515	}
516
517	return currentNode;
518	}
519
520
521	void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate,
522	bool computeSplitPlane)
523	{
524	if (computeSplitPlane)
525	{
526	const bool sufficientSamples =
527	splitCandidate.mParentData.mNumRays > mMinRaysForVisibility;
528
529	const bool useVisibiliyBasedHeuristics =
530	!mUseSah &&
531	(mHierarchyManager->GetViewSpaceSubdivisionType() ==
532	HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV) &&
533	sufficientSamples;
534
535	// compute best object partition
536	const float ratio = SelectObjectPartition(splitCandidate.mParentData,
537	splitCandidate.mFrontObjects,
538	splitCandidate.mBackObjects,
539	useVisibiliyBasedHeuristics);
540
541	// cost ratio violated?
542	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
543	const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;
544
545	splitCandidate.SetMaxCostMisses(maxCostRatioViolated ? previousMisses + 1 : previousMisses);
546
547	}
548
549	BvhLeaf *leaf = splitCandidate.mParentData.mNode;
550
551	const float oldProp = EvalViewCellsVolume(leaf->mObjects);
552	const float oldRenderCost = EvalRenderCost(leaf->mObjects);
553
554	// compute global decrease in render cost
555	const float newRenderCost = EvalRenderCost(splitCandidate.mFrontObjects) +
556	EvalRenderCost(splitCandidate.mBackObjects);
557
558	const float renderCostDecr = oldRenderCost - newRenderCost;
559
560	splitCandidate.SetRenderCostDecrease(renderCostDecr);
561
562	// increase in pvs entries
563	const int pvsEntriesIncr = EvalPvsEntriesIncr(splitCandidate);
564	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
565
566	#ifdef GTP_DEBUG
567	Debug << "old render cost: " << oldRenderCost << endl;
568	Debug << "new render cost: " << newRenderCost << endl;
569	Debug << "render cost decrease: " << renderCostDecr << endl;
570	#endif
571
572	float priority;
573
574	// surface area heuristics is used when there is
575	// no view space subdivision available.
576	// In order to have some prioritized traversal,
577	// we use this formula instead
578	if (mHierarchyManager->GetViewSpaceSubdivisionType() ==
579	HierarchyManager::NO_VIEWSPACE_SUBDIV)
580	{
581	priority = EvalSahCost(leaf);
582	}
583	else
584	{
585	// take render cost of node into account
586	// otherwise danger of being stuck in a local minimum!
587	const float factor = mRenderCostDecreaseWeight;
588
589	if (1)
590	{
591	priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
592	if (mHierarchyManager->mConsiderMemory)
593	{
594	priority /= ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
595	}
596	}
597	else
598	{
599	if (!mHierarchyManager->mConsiderMemory)
600	{
601	priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
602	}
603	else
604	{
605	const float ratio =
606	renderCostDecr / ((float)splitCandidate.GetPvsEntriesIncr() + mMemoryConst);
607
608	priority = factor * ratio + (1.0f - factor) * oldRenderCost;
609	}
610	}
611	}
612
613	// hack: don't allow empty splits to be taken
614	if (splitCandidate.mFrontObjects.empty() \|\| splitCandidate.mBackObjects.empty())
615	priority = 0;
616	// compute global decrease in render cost
617	splitCandidate.SetPriority(priority);
618	}
619
620
621	int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate) const
622	{
623	const int oldPvsSize = CountViewCells(splitCandidate.mParentData.mNode->mObjects);
624
625	const int fPvsSize = CountViewCells(splitCandidate.mFrontObjects);
626	const int bPvsSize = CountViewCells(splitCandidate.mBackObjects);
627
628	return fPvsSize + bPvsSize - oldPvsSize;
629	}
630
631
632	inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &data) const
633	{
634	const bool terminationCriteriaMet =
635	(0
636	\|\| ((int)data.mNode->mObjects.size() <= 1)//mTermMinObjects)
637	//\|\| (data.mProbability <= mTermMinProbability)
638	//\|\| (data.mNumRays <= mTermMinRays)
639	);
640
641	#ifdef _DEBUG
642	if (terminationCriteriaMet)
643	{
644	cout << "bvh local termination criteria met:" << endl;
645	cout << "objects: " << data.mNode->mObjects.size() << " " << mTermMinObjects << endl;
646	}
647	#endif
648	return terminationCriteriaMet;
649	}
650
651
652	inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
653	{
654	// note: tracking for global cost termination
655	// does not make much sense for interleaved vsp / osp partition
656	// as it is the responsibility of the hierarchy manager
657
658	const bool terminationCriteriaMet =
659	(0
660	\|\| (mBvhStats.Leaves() >= mTermMaxLeaves)
661	//\|\| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
662	//\|\| mOutOfMemory
663	);
664
665	#ifdef GTP_DEBUG
666	if (terminationCriteriaMet)
667	{
668	Debug << "bvh global termination criteria met:" << endl;
669	Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
670	Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
671	}
672	#endif
673	return terminationCriteriaMet;
674	}
675
676
677	void BvHierarchy::EvaluateLeafStats(const BvhTraversalData &data)
678	{
679	// the node became a leaf -> evaluate stats for leafs
680	BvhLeaf *leaf = data.mNode;
681
682	++ mCreatedLeaves;
683
684
685	if (data.mProbability <= mTermMinProbability)
686	{
687	++ mBvhStats.minProbabilityNodes;
688	}
689
690	////////////////////////////////////////////
691	// depth related stuff
692
693	if (data.mDepth < mBvhStats.minDepth)
694	{
695	mBvhStats.minDepth = data.mDepth;
696	}
697
698	if (data.mDepth >= mTermMaxDepth)
699	{
700	++ mBvhStats.maxDepthNodes;
701	}
702
703	// accumulate depth to compute average depth
704	mBvhStats.accumDepth += data.mDepth;
705
706
707	////////////////////////////////////////////
708	// objects related stuff
709
710	// note: the sum should alwaysbe total number of objects for bvh
711	mBvhStats.objectRefs += (int)leaf->mObjects.size();
712
713	if ((int)leaf->mObjects.size() <= mTermMinObjects)
714	{
715	++ mBvhStats.minObjectsNodes;
716	}
717
718	if (leaf->mObjects.empty())
719	{
720	++ mBvhStats.emptyNodes;
721	}
722
723	if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
724	{
725	mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
726	}
727
728	if ((int)leaf->mObjects.size() < mBvhStats.minObjectRefs)
729	{
730	mBvhStats.minObjectRefs = (int)leaf->mObjects.size();
731	}
732
733	////////////////////////////////////////////
734	// ray related stuff
735
736	// note: this number should always accumulate to the total number of rays
737	mBvhStats.rayRefs += data.mNumRays;
738
739	if (data.mNumRays <= mTermMinRays)
740	{
741	++ mBvhStats.minRaysNodes;
742	}
743
744	if (data.mNumRays > mBvhStats.maxRayRefs)
745	{
746	mBvhStats.maxRayRefs = data.mNumRays;
747	}
748
749	if (data.mNumRays < mBvhStats.minRayRefs)
750	{
751	mBvhStats.minRayRefs = data.mNumRays;
752	}
753
754	#ifdef _DEBUG
755	cout << "depth: " << data.mDepth << " objects: " << (int)leaf->mObjects.size()
756	<< " rays: " << data.mNumRays << " rays / objects "
757	<< (float)data.mNumRays / (float)leaf->mObjects.size() << endl;
758	#endif
759	}
760
761
762	#if 0
763
764	/// compute object boundaries using spatial mid split
765	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
766	const int axis,
767	ObjectContainer &objectsFront,
768	ObjectContainer &objectsBack)
769	{
770	const float maxBox = tData.mBoundingBox.Max(axis);
771	const float minBox = tData.mBoundingBox.Min(axis);
772
773	float midPoint = (maxBox + minBox) * 0.5f;
774
775	ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
776
777	for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
778	{
779	Intersectable obj = oit;
780	const AxisAlignedBox3 box = obj->GetBox();
781
782	const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;
783
784	// object mailed => belongs to back objects
785	if (objMid < midPoint)
786	{
787	objectsBack.push_back(obj);
788	}
789	else
790	{
791	objectsFront.push_back(obj);
792	}
793	}
794
795	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
796	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
797
798	const float ratio = newRenderCost / oldRenderCost;
799	return ratio;
800	}
801
802	#else
803
804	/// compute object partition by getting balanced objects on the left and right side
805	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
806	const int axis,
807	ObjectContainer &objectsFront,
808	ObjectContainer &objectsBack)
809	{
810	PrepareLocalSubdivisionCandidates(tData, axis);
811
812	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
813
814	int i = 0;
815	const int border = (int)tData.mNode->mObjects.size() / 2;
816
817	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ i)
818	{
819	Intersectable obj = (cit).mObject;
820
821	// object mailed => belongs to back objects
822	if (i < border)
823	{
824	objectsBack.push_back(obj);
825	}
826	else
827	{
828	objectsFront.push_back(obj);
829	}
830	}
831
832	#if 1
833	const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
834	#else
835	const float oldRenderCost = EvalRenderCost(tData.mNode->mObjects);
836	const float newRenderCost = EvalRenderCost(objectsFront) * EvalRenderCost(objectsBack);
837
838	const float cost = newRenderCost / oldRenderCost;
839	#endif
840
841	return cost;
842	}
843	#endif
844
845	#if 1
846
847	float BvHierarchy::EvalSah(const BvhTraversalData &tData,
848	const int axis,
849	ObjectContainer &objectsFront,
850	ObjectContainer &objectsBack)
851	{
852	// go through the lists, count the number of objects left and right
853	// and evaluate the following cost funcion:
854	// C = ct_div_ci + (ol + or) / queries
855	PrepareLocalSubdivisionCandidates(tData, axis);
856
857	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
858	float objectsLeft = 0, objectsRight = totalRenderCost;
859
860	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
861	const float boxArea = nodeBbox.SurfaceArea();
862
863	float minSum = 1e20f;
864
865	float minBorder = nodeBbox.Max(axis);
866	float maxBorder = nodeBbox.Min(axis);
867
868	float areaLeft = 0, areaRight = 0;
869
870	SortableEntryContainer::const_iterator currentPos =
871	mSubdivisionCandidates->begin();
872
873	vector<float> bordersRight;
874
875	// we keep track of both borders of the bounding boxes =>
876	// store the events in descending order
877
878	bordersRight.resize(mSubdivisionCandidates->size());
879
880	SortableEntryContainer::reverse_iterator rcit =
881	mSubdivisionCandidates->rbegin(), rcit_end =
882	mSubdivisionCandidates->rend();
883
884	vector<float>::reverse_iterator rbit = bordersRight.rbegin();
885
886	for (; rcit != rcit_end; ++ rcit, ++ rbit)
887	{
888	Intersectable obj = (rcit).mObject;
889	const AxisAlignedBox3 obox = obj->GetBox();
890
891	if (obox.Min(axis) < minBorder)
892	{
893	minBorder = obox.Min(axis);
894	}
895
896	(*rbit) = minBorder;
897	}
898
899	// temporary surface areas
900	float al = 0;
901	float ar = boxArea;
902
903	vector<float>::const_iterator bit = bordersRight.begin();
904	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
905
906	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
907	{
908	Intersectable obj = (cit).mObject;
909
910	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
911
912	objectsLeft += renderCost;
913	objectsRight -= renderCost;
914
915	const AxisAlignedBox3 obox = obj->GetBox();
916
917	// the borders of the bounding boxes have changed
918	if (obox.Max(axis) > maxBorder)
919	{
920	maxBorder = obox.Max(axis);
921	}
922
923	minBorder = (*bit);
924
925	AxisAlignedBox3 lbox = nodeBbox;
926	AxisAlignedBox3 rbox = nodeBbox;
927
928	lbox.SetMax(axis, maxBorder);
929	rbox.SetMin(axis, minBorder);
930
931	al = lbox.SurfaceArea();
932	ar = rbox.SurfaceArea();
933
934	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
935	const float sum = noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
936
937	/cout << "pos=" << (cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
938	<< lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
939	cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
940	cout << "cost= " << sum << endl;*/
941
942	if (sum < minSum)
943	{
944	minSum = sum;
945	areaLeft = al;
946	areaRight = ar;
947
948	// objects belong to left side now
949	for (; currentPos != (cit + 1); ++ currentPos);
950	}
951	}
952
953	////////////
954	//-- assign object to front and back volume
955
956	// belongs to back bv
957	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
958	objectsBack.push_back((*cit).mObject);
959
960	// belongs to front bv
961	for (cit = currentPos; cit != cit_end; ++ cit)
962	objectsFront.push_back((*cit).mObject);
963
964	float newCost = minSum / boxArea;
965	float ratio = newCost / totalRenderCost;
966
967	#ifdef GTP_DEBUG
968	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
969	<< (int)tData.mNode->mObjects.size() << ")\t area=("
970	<< areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
971	<< "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
972	#endif
973
974	return ratio;
975	}
976
977	#else
978
979	float BvHierarchy::EvalSah(const BvhTraversalData &tData,
980	const int axis,
981	ObjectContainer &objectsFront,
982	ObjectContainer &objectsBack)
983	{
984	// go through the lists, count the number of objects left and right
985	// and evaluate the following cost funcion:
986	// C = ct_div_ci + (ol + or) / queries
987	PrepareLocalSubdivisionCandidates(tData, axis);
988
989	const float totalRenderCost = EvalAbsCost(tData.mNode->mObjects);
990	float objectsLeft = 0, objectsRight = totalRenderCost;
991
992	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
993
994	const float minBox = nodeBbox.Min(axis);
995	const float maxBox = nodeBbox.Max(axis);
996	const float boxArea = nodeBbox.SurfaceArea();
997
998	float minSum = 1e20f;
999
1000	Vector3 minBorder = nodeBbox.Max();
1001	Vector3 maxBorder = nodeBbox.Min();
1002
1003	float areaLeft = 0, areaRight = 0;
1004
1005	SortableEntryContainer::const_iterator currentPos =
1006	mSubdivisionCandidates->begin();
1007
1008	vector<Vector3> bordersRight;
1009
1010	// we keep track of both borders of the bounding boxes =>
1011	// store the events in descending order
1012	bordersRight.resize(mSubdivisionCandidates->size());
1013
1014	SortableEntryContainer::reverse_iterator rcit =
1015	mSubdivisionCandidates->rbegin(), rcit_end =
1016	mSubdivisionCandidates->rend();
1017
1018	vector<Vector3>::reverse_iterator rbit = bordersRight.rbegin();
1019
1020	for (; rcit != rcit_end; ++ rcit, ++ rbit)
1021	{
1022	Intersectable obj = (rcit).mObject;
1023	const AxisAlignedBox3 obox = obj->GetBox();
1024
1025	for (int i = 0; i < 3; ++ i)
1026	{
1027	if (obox.Min(i) < minBorder[i])
1028	{
1029	minBorder[i] = obox.Min(i);
1030	}
1031	}
1032
1033	(*rbit) = minBorder;
1034	}
1035
1036	// temporary surface areas
1037	float al = 0;
1038	float ar = boxArea;
1039
1040	vector<Vector3>::const_iterator bit = bordersRight.begin();
1041	SortableEntryContainer::const_iterator cit, cit_end =
1042	mSubdivisionCandidates->end();
1043
1044	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
1045	{
1046	Intersectable obj = (cit).mObject;
1047
1048	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1049
1050	objectsLeft += renderCost;
1051	objectsRight -= renderCost;
1052
1053	const AxisAlignedBox3 obox = obj->GetBox();
1054
1055	AxisAlignedBox3 lbox = nodeBbox;
1056	AxisAlignedBox3 rbox = nodeBbox;
1057
1058	// the borders of the left bounding box have changed
1059	for (int i = 0; i < 3; ++ i)
1060	{
1061	if (obox.Max(i) > maxBorder[i])
1062	{
1063	maxBorder[i] = obox.Max(i);
1064	}
1065	}
1066
1067	minBorder = (*bit);
1068
1069	lbox.SetMax(maxBorder);
1070	rbox.SetMin(minBorder);
1071
1072	al = lbox.SurfaceArea();
1073	ar = rbox.SurfaceArea();
1074
1075	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
1076	const float sum = noValidSplit ? 1e25 : objectsLeft * al + objectsRight * ar;
1077
1078	/cout << "pos=" << (cit).mPos << "\t q=(" << objectsLeft << "," << objectsRight <<")\t r=("
1079	<< lbox.SurfaceArea() << "," << rbox.SurfaceArea() << ")" << endl;
1080	cout << "minborder: " << minBorder << " maxborder: " << maxBorder << endl;
1081	cout << "cost= " << sum << endl;*/
1082
1083	if (sum < minSum)
1084	{
1085	minSum = sum;
1086	areaLeft = al;
1087	areaRight = ar;
1088
1089	// objects belong to left side now
1090	for (; currentPos != (cit + 1); ++ currentPos);
1091	}
1092	}
1093
1094	/////////////
1095	//-- assign object to front and back volume
1096
1097	// belongs to back bv
1098	for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
1099	objectsBack.push_back((*cit).mObject);
1100
1101	// belongs to front bv
1102	for (cit = currentPos; cit != cit_end; ++ cit)
1103	objectsFront.push_back((*cit).mObject);
1104
1105	float newCost = minSum / boxArea;
1106	float ratio = newCost / totalRenderCost;
1107
1108	#ifdef GTP_DEBUG
1109	cout << "\n\nobjects=(" << (int)objectsBack.size() << "," << (int)objectsFront.size() << " of "
1110	<< (int)tData.mNode->mObjects.size() << ")\t area=("
1111	<< areaLeft << ", " << areaRight << ", " << boxArea << ")" << endl
1112	<< "cost= " << newCost << " oldCost=" << totalRenderCost / boxArea << endl;
1113	#endif
1114
1115	return ratio;
1116	}
1117
1118	#endif
1119
1120	static bool PrepareOutput(const int axis,
1121	const int leaves,
1122	ofstream &sumStats,
1123	ofstream &vollStats,
1124	ofstream &volrStats)
1125	{
1126	if ((axis == 0) && (leaves > 0) && (leaves < 90))
1127	{
1128	char str[64];
1129	sprintf(str, "tmp/bvh_heur_sum-%04d.log", leaves);
1130	sumStats.open(str);
1131	sprintf(str, "tmp/bvh_heur_voll-%04d.log", leaves);
1132	vollStats.open(str);
1133	sprintf(str, "tmp/bvh_heur_volr-%04d.log", leaves);
1134	volrStats.open(str);
1135	}
1136
1137	return sumStats.is_open() && vollStats.is_open() && volrStats.is_open();
1138	}
1139
1140
1141	static void PrintHeuristics(const float objectsRight,
1142	const float sum,
1143	const float volLeft,
1144	const float volRight,
1145	const float viewSpaceVol,
1146	ofstream &sumStats,
1147	ofstream &vollStats,
1148	ofstream &volrStats)
1149	{
1150	sumStats
1151	<< "#Position\n" << objectsRight << endl
1152	<< "#Sum\n" << sum / viewSpaceVol << endl
1153	<< "#Vol\n" << (volLeft + volRight) / viewSpaceVol << endl;
1154
1155	vollStats
1156	<< "#Position\n" << objectsRight << endl
1157	<< "#Vol\n" << volLeft / viewSpaceVol << endl;
1158
1159	volrStats
1160	<< "#Position\n" << objectsRight << endl
1161	<< "#Vol\n" << volRight / viewSpaceVol << endl;
1162	}
1163
1164
1165	float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
1166	const int axis,
1167	ObjectContainer &objectsFront,
1168	ObjectContainer &objectsBack)
1169	{
1170	///////////////////////////////////////////////////////
1171	//-- go through the lists, count the number of objects left
1172	//-- and right and evaluate the cost funcion
1173
1174	// prepare the heuristics by setting mailboxes and counters.
1175	const float totalVol = PrepareHeuristics(tData, axis);
1176
1177	// local helper variables
1178	float volLeft = 0;
1179	float volRight = totalVol;
1180
1181	const float nTotalObjects = EvalAbsCost(tData.mNode->mObjects);
1182	float nObjectsLeft = 0;
1183	float nObjectsRight = nTotalObjects;
1184
1185	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1186
1187	SortableEntryContainer::const_iterator backObjectsStart =
1188	mSubdivisionCandidates->begin();
1189
1190	/////////////////////////////////
1191	//-- the parameters for the current optimum
1192
1193	float volBack = volLeft;
1194	float volFront = volRight;
1195	float newRenderCost = nTotalObjects * totalVol;
1196
1197	#ifdef GTP_DEBUG
1198	ofstream sumStats;
1199	ofstream vollStats;
1200	ofstream volrStats;
1201
1202	const bool printStats = PrepareOutput(axis,
1203	mBvhStats.Leaves(),
1204	sumStats,
1205	vollStats,
1206	volrStats);
1207	#endif
1208
1209	///////////////////////
1210	//-- the sweep heuristics
1211	//-- traverse through events and find best split plane
1212
1213	SortableEntryContainer::const_iterator cit,
1214	cit_end = cit_end = mSubdivisionCandidates->end();
1215
1216	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
1217	{
1218	Intersectable object = (cit).mObject;
1219
1220	// evaluate change in l and r volume
1221	// voll = view cells that see only left node (i.e., left pvs)
1222	// volr = view cells that see only right node (i.e., right pvs)
1223	EvalHeuristicsContribution(object, volLeft, volRight);
1224
1225	const float rc = mViewCellsManager->EvalRenderCost(object);
1226
1227	nObjectsLeft += rc;
1228	nObjectsRight -= rc;
1229
1230	const bool noValidSplit = ((nObjectsLeft <= Limits::Small) \|\| (nObjectsRight <= Limits::Small));
1231
1232	// the heuristics
1233	const float sum = noValidSplit ?
1234	1e25 : volLeft * (float)nObjectsLeft + volRight * (float)nObjectsRight;
1235
1236	#ifdef GTP_DEBUG
1237	if (printStats)
1238	{
1239	PrintHeuristics(nObjectsRight, sum, volLeft, volRight, viewSpaceVol,
1240	sumStats, vollStats, volrStats);
1241	}
1242	#endif
1243
1244	if (sum < newRenderCost)
1245	{
1246	newRenderCost = sum;
1247
1248	volBack = volLeft;
1249	volFront = volRight;
1250
1251	// objects belongs to left side now
1252	for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
1253	}
1254	}
1255
1256	////////////////////////////////////////////
1257	//-- assign object to front and back volume
1258
1259	// belongs to back bv
1260	for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
1261	{
1262	objectsBack.push_back((*cit).mObject);
1263	}
1264	// belongs to front bv
1265	for (cit = backObjectsStart; cit != cit_end; ++ cit)
1266	{
1267	objectsFront.push_back((*cit).mObject);
1268	}
1269
1270	// render cost of the old parent
1271	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
1272	// the relative cost ratio
1273	const float ratio = newRenderCost / oldRenderCost;
1274
1275	#ifdef GTP_DEBUG
1276	Debug << "\n§§§§ bvh eval const decrease §§§§" << endl
1277	<< "back pvs: " << (int)objectsBack.size() << " front pvs: "
1278	<< (int)objectsFront.size() << " total pvs: " << nTotalObjects << endl
1279	<< "back p: " << volBack / viewSpaceVol << " front p "
1280	<< volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
1281	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: "
1282	<< newRenderCost / viewSpaceVol << endl
1283	<< "render cost decrease: "
1284	<< oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
1285	#endif
1286
1287	return ratio;
1288	}
1289
1290
1291	void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
1292	const int axis)
1293	{
1294	//-- insert object queries
1295	ObjectContainer *objects = mUseGlobalSorting ?
1296	tData.mSortedObjects[axis] : &tData.mNode->mObjects;
1297
1298	CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
1299	}
1300
1301
1302	void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
1303	SortableEntryContainer **subdivisionCandidates,
1304	const bool sort,
1305	const int axis)
1306	{
1307	(*subdivisionCandidates)->clear();
1308
1309	// compute requested size and look if subdivision candidate has to be recomputed
1310	const int requestedSize = (int)objects.size() * 2;
1311
1312	// creates a sorted split candidates array
1313	if ((*subdivisionCandidates)->capacity() > 500000 &&
1314	requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
1315	{
1316	delete (*subdivisionCandidates);
1317	(*subdivisionCandidates) = new SortableEntryContainer;
1318	}
1319
1320	(*subdivisionCandidates)->reserve(requestedSize);
1321
1322	ObjectContainer::const_iterator oit, oit_end = objects.end();
1323
1324	for (oit = objects.begin(); oit < oit_end; ++ oit)
1325	{
1326	Intersectable object = oit;
1327	const AxisAlignedBox3 &box = object->GetBox();
1328	const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
1329
1330	(*subdivisionCandidates)->push_back(SortableEntry(object, midPt));
1331	}
1332
1333	if (sort)
1334	{ // no presorted candidate list
1335	stable_sort((subdivisionCandidates)->begin(), (subdivisionCandidates)->end());
1336	}
1337	}
1338
1339
1340	const BvhStatistics &BvHierarchy::GetStatistics() const
1341	{
1342	return mBvhStats;
1343	}
1344
1345
1346	float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData,
1347	const int axis)
1348	{
1349	BvhLeaf *leaf = tData.mNode;
1350	float vol = 0;
1351
1352	// sort so we can use a sweep from right to left
1353	PrepareLocalSubdivisionCandidates(tData, axis);
1354
1355	// collect and mark the view cells as belonging to front pvs
1356	ViewCellContainer viewCells;
1357
1358	const int numRays = CollectViewCells(tData.mNode->mObjects, viewCells, true, true);
1359	//cout << "here4 " << numRays << endl;
1360
1361	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1362	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1363	{
1364	#if USE_VOLUMES_FOR_HEURISTICS
1365	const float volIncr = (*vit)->GetVolume();
1366	#else
1367	const float volIncr = 1.0f;
1368	#endif
1369	vol += volIncr;
1370	}
1371
1372	// we will mail view cells switching to the back side
1373	ViewCell::NewMail();
1374
1375	return vol;
1376	}
1377
1378	///////////////////////////////////////////////////////////
1379
1380
1381	void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
1382	float &volLeft,
1383	float &volRight)
1384	{
1385	// collect all view cells associated with this objects
1386	// (also multiple times, if they are pierced by several rays)
1387	ViewCellContainer viewCells;
1388	const bool useMailboxing = false;
1389
1390	CollectViewCells(obj, viewCells, useMailboxing, false, true);
1391
1392	// classify view cells and compute volume contri accordingly
1393	// possible view cell classifications:
1394	// view cell mailed => view cell can be seen from left child node
1395	// view cell counter > 0 view cell can be seen from right child node
1396	// combined: view cell volume belongs to both nodes
1397	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1398
1399	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1400	{
1401	// view cells can also be seen from left child node
1402	ViewCell viewCell = vit;
1403	#if USE_VOLUMES_FOR_HEURISTICS
1404	const float vol = viewCell->GetVolume();
1405	#else
1406	const float vol = 1.0f;
1407	#endif
1408	if (!viewCell->Mailed())
1409	{
1410	viewCell->Mail();
1411	// we now see view cell from both nodes
1412	// => add volume to left node
1413	volLeft += vol;
1414	}
1415
1416	// last reference into the right node
1417	if (-- viewCell->mCounter == 0)
1418	{
1419	// view cell was previously seen from both nodes =>
1420	// remove volume from right node
1421	volRight -= vol;
1422	}
1423	}
1424	}
1425
1426
1427	void BvHierarchy::SetViewCellsManager(ViewCellsManager *vcm)
1428	{
1429	mViewCellsManager = vcm;
1430	}
1431
1432
1433	AxisAlignedBox3 BvHierarchy::GetBoundingBox() const
1434	{
1435	return mBoundingBox;
1436	}
1437
1438
1439	float BvHierarchy::SelectObjectPartition(const BvhTraversalData &tData,
1440	ObjectContainer &frontObjects,
1441	ObjectContainer &backObjects,
1442	bool useVisibilityBasedHeuristics)
1443	{
1444	ObjectContainer nFrontObjects[3];
1445	ObjectContainer nBackObjects[3];
1446	float nCostRatio[3];
1447
1448	int sAxis = 0;
1449	int bestAxis = -1;
1450
1451	if (mOnlyDrivingAxis)
1452	{
1453	const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
1454	sAxis = box.Size().DrivingAxis();
1455	}
1456
1457	// only use a subset of the rays for visibility based heuristics
1458	if (mUseCostHeuristics && useVisibilityBasedHeuristics)
1459	{
1460	VssRayContainer rays;
1461	// maximal 2 objects share the same ray
1462	rays.reserve(tData.mNumRays * 2);
1463	CollectRays(tData.mNode->mObjects, rays);
1464
1465	const float prop = (float)mMaxTests / (float)tData.mNumRays;
1466
1467	VssRay::NewMail();
1468
1469	VssRayContainer::const_iterator rit, rit_end = rays.end();
1470
1471	int nRays = 0;
1472
1473	for (rit = rays.begin(); rit != rit_end; ++ rit)
1474	{
1475	if ((mMaxTests >= (int)rays.size()) \|\| (Random(1.0f) < prop))
1476	{
1477	(*rit)->Mail();
1478	++ nRays;
1479	}
1480	}
1481	}
1482
1483	////////////////////////////////////
1484	//-- evaluate split cost for all three axis
1485
1486	for (int axis = 0; axis < 3; ++ axis)
1487	{
1488	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
1489	{
1490	if (mUseCostHeuristics)
1491	{
1492	//////////////////////////////////
1493	//-- split objects using heuristics
1494
1495	if (useVisibilityBasedHeuristics)
1496	{
1497	///////////
1498	//-- heuristics using objects weighted by view cells volume
1499	nCostRatio[axis] =
1500	EvalLocalCostHeuristics(tData,
1501	axis,
1502	nFrontObjects[axis],
1503	nBackObjects[axis]);
1504	}
1505	else
1506	{
1507	//////////////////
1508	//-- view cells not constructed yet => use surface area heuristic
1509	nCostRatio[axis] = EvalSah(tData,
1510	axis,
1511	nFrontObjects[axis],
1512	nBackObjects[axis]);
1513	}
1514	}
1515	else
1516	{
1517	//-- split objects using some simple criteria
1518	nCostRatio[axis] =
1519	EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
1520	}
1521
1522	if ((bestAxis == -1) \|\| (nCostRatio[axis] < nCostRatio[bestAxis]))
1523	{
1524	bestAxis = axis;
1525	}
1526	}
1527	}
1528
1529	////////////////
1530	//-- assign values
1531
1532	frontObjects = nFrontObjects[bestAxis];
1533	backObjects = nBackObjects[bestAxis];
1534
1535	//cout << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1536	return nCostRatio[bestAxis];
1537	}
1538
1539
1540	int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
1541	{
1542	int nRays = 0;
1543	VssRayContainer::const_iterator rit, rit_end = rays.end();
1544
1545	VssRay::NewMail();
1546
1547	for (rit = rays.begin(); rit != rays.end(); ++ rit)
1548	{
1549	VssRay ray = (rit);
1550
1551	if (ray->mTerminationObject)
1552	{
1553	ray->mTerminationObject->GetOrCreateRays()->push_back(ray);
1554	if (!ray->Mailed())
1555	{
1556	ray->Mail();
1557	++ nRays;
1558	}
1559	}
1560
1561	#if COUNT_ORIGIN_OBJECTS
1562
1563	if (ray->mOriginObject)
1564	{
1565	ray->mOriginObject->GetOrCreateRays()->push_back(ray);
1566
1567	if (!ray->Mailed())
1568	{
1569	ray->Mail();
1570	++ nRays;
1571	}
1572	}
1573	#endif
1574	}
1575
1576	return nRays;
1577	}
1578
1579
1580	void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
1581	{
1582	const float costDecr = sc.GetRenderCostDecrease();
1583
1584	mSubdivisionStats
1585	<< "#Leaves\n" << mBvhStats.Leaves() << endl
1586	<< "#RenderCostDecrease\n" << costDecr << endl
1587	<< "#TotalRenderCost\n" << mTotalCost << endl
1588	<< "#EntriesInPvs\n" << mPvsEntries << endl;
1589	}
1590
1591
1592	void BvHierarchy::CollectRays(const ObjectContainer &objects,
1593	VssRayContainer &rays) const
1594	{
1595	VssRay::NewMail();
1596	ObjectContainer::const_iterator oit, oit_end = objects.end();
1597
1598	// evaluate reverse pvs and view cell volume on left and right cell
1599	// note: should I take all leaf objects or rather the objects hit by rays?
1600	for (oit = objects.begin(); oit != oit_end; ++ oit)
1601	{
1602	Intersectable obj = oit;
1603	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1604
1605	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1606	{
1607	VssRay ray = (rit);
1608
1609	if (!ray->Mailed())
1610	{
1611	ray->Mail();
1612	rays.push_back(ray);
1613	}
1614	}
1615	}
1616	}
1617
1618
1619	float BvHierarchy::EvalAbsCost(const ObjectContainer &objects)// const
1620	{
1621	#if USE_BETTER_RENDERCOST_EST
1622	ObjectContainer::const_iterator oit, oit_end = objects.end();
1623
1624	for (oit = objects.begin(); oit != oit_end; ++ oit)
1625	{
1626	objRenderCost += ViewCellsManager::GetRendercost(*oit);
1627	}
1628	#else
1629	return (float)objects.size();
1630	#endif
1631	}
1632
1633
1634	float BvHierarchy::EvalSahCost(BvhLeaf *leaf)
1635	{
1636	////////////////
1637	//-- surface area heuristics
1638	if (leaf->mObjects.empty())
1639	return 0.0f;
1640
1641	const AxisAlignedBox3 box = GetBoundingBox(leaf);
1642	const float area = box.SurfaceArea();
1643	const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
1644
1645	return EvalAbsCost(leaf->mObjects) * area / viewSpaceArea;
1646	}
1647
1648
1649	float BvHierarchy::EvalRenderCost(const ObjectContainer &objects) const
1650	{
1651	///////////////
1652	//-- render cost heuristics
1653
1654	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
1655
1656	// probability that view point lies in a view cell which sees this node
1657	const float p = EvalViewCellsVolume(objects) / viewSpaceVol;
1658	const float objRenderCost = EvalAbsCost(objects);
1659
1660	return objRenderCost * p;
1661	}
1662
1663
1664	AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
1665	const AxisAlignedBox3 *parentBox) const
1666	{
1667	// if there are no objects in this box, box size is set to parent box size.
1668	// Question: Invalidate box instead?
1669	if (parentBox && objects.empty())
1670	return *parentBox;
1671
1672	AxisAlignedBox3 box;
1673	box.Initialize();
1674
1675	ObjectContainer::const_iterator oit, oit_end = objects.end();
1676
1677	for (oit = objects.begin(); oit != oit_end; ++ oit)
1678	{
1679	Intersectable obj = oit;
1680	// grow bounding box to include all objects
1681	box.Include(obj->GetBox());
1682	}
1683
1684	return box;
1685	}
1686
1687
1688	void BvHierarchy::CollectLeaves(BvhNode root, vector<BvhLeaf > &leaves) const
1689	{
1690	stack<BvhNode *> nodeStack;
1691	nodeStack.push(root);
1692
1693	while (!nodeStack.empty())
1694	{
1695	BvhNode *node = nodeStack.top();
1696	nodeStack.pop();
1697
1698	if (node->IsLeaf())
1699	{
1700	BvhLeaf leaf = (BvhLeaf )node;
1701	leaves.push_back(leaf);
1702	}
1703	else
1704	{
1705	BvhInterior interior = (BvhInterior )node;
1706
1707	nodeStack.push(interior->GetBack());
1708	nodeStack.push(interior->GetFront());
1709	}
1710	}
1711	}
1712
1713
1714	AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
1715	{
1716	return node->GetBoundingBox();
1717	}
1718
1719
1720	int BvHierarchy::CollectViewCells(const ObjectContainer &objects,
1721	ViewCellContainer &viewCells,
1722	const bool setCounter,
1723	const bool onlyMailedRays) const
1724	{
1725	ViewCell::NewMail();
1726	ObjectContainer::const_iterator oit, oit_end = objects.end();
1727
1728	int numRays = 0;
1729	// loop through all object and collect view cell pvs of this node
1730	for (oit = objects.begin(); oit != oit_end; ++ oit)
1731	{
1732	// always use only mailed objects
1733	numRays += CollectViewCells(*oit, viewCells, true, setCounter, onlyMailedRays);
1734	}
1735
1736	return numRays;
1737	}
1738
1739
1740	int BvHierarchy::CollectViewCells(Intersectable *obj,
1741	ViewCellContainer &viewCells,
1742	const bool useMailBoxing,
1743	const bool setCounter,
1744	const bool onlyMailedRays) const
1745	{
1746	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1747
1748	int numRays = 0;
1749
1750	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1751	{
1752	VssRay ray = (rit);
1753
1754	if (onlyMailedRays && !ray->Mailed())
1755	{//if (onlyMailedRays)cout << "u";
1756	continue;
1757	}//else if (onlyMailedRays) cout << "z";
1758
1759	//ray->Mail();
1760	++ numRays;
1761
1762	ViewCellContainer tmpViewCells;
1763	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1764
1765	// matt: probably slow to allocate memory for view cells every time
1766	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1767
1768	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1769	{
1770	ViewCell vc = vit;
1771
1772	// store view cells
1773	if (!useMailBoxing \|\| !vc->Mailed())
1774	{
1775	if (useMailBoxing)
1776	{
1777	vc->Mail();
1778	if (setCounter)
1779	{
1780	vc->mCounter = 0;
1781	}
1782	}
1783	viewCells.push_back(vc);
1784	}
1785
1786	if (setCounter)
1787	{
1788	++ vc->mCounter;
1789	}
1790	}
1791	}
1792
1793	return numRays;
1794	}
1795
1796
1797	int BvHierarchy::CountViewCells(Intersectable *obj) const
1798	{
1799	int result = 0;
1800
1801	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
1802
1803	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
1804	{
1805	VssRay ray = (rit);
1806	ViewCellContainer tmpViewCells;
1807
1808	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
1809
1810	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1811	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1812	{
1813	ViewCell vc = vit;
1814
1815	// store view cells
1816	if (!vc->Mailed())
1817	{
1818	vc->Mail();
1819	++ result;
1820	}
1821	}
1822	}
1823
1824	return result;
1825	}
1826
1827
1828	int BvHierarchy::CountViewCells(const ObjectContainer &objects) const
1829	{
1830	int nViewCells = 0;
1831	ViewCell::NewMail();
1832	ObjectContainer::const_iterator oit, oit_end = objects.end();
1833
1834	// loop through all object and collect view cell pvs of this node
1835	for (oit = objects.begin(); oit != oit_end; ++ oit)
1836	{
1837	nViewCells += CountViewCells(*oit);
1838	}
1839
1840	return nViewCells;
1841	}
1842
1843
1844	void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
1845	vector<SubdivisionCandidate *> &dirtyList,
1846	const bool onlyUnmailed)
1847	{
1848	BvhTraversalData &tData = sc->mParentData;
1849	BvhLeaf *node = tData.mNode;
1850
1851	ViewCellContainer viewCells;
1852	ViewCell::NewMail();
1853	int numRays = CollectViewCells(node->mObjects, viewCells, false, false);
1854
1855	if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
1856
1857	// split candidates handling
1858	// these view cells are thrown into dirty list
1859	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1860
1861	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1862	{
1863	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
1864	VspLeaf *leaf = vc->mLeaves[0];
1865
1866	SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
1867
1868	// is this leaf still a split candidate?
1869	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
1870	{
1871	candidate->Mail();
1872	candidate->SetDirty(true);
1873	dirtyList.push_back(candidate);
1874	}
1875	}
1876	}
1877
1878
1879	BvhNode *BvHierarchy::GetRoot() const
1880	{
1881	return mRoot;
1882	}
1883
1884
1885	bool BvHierarchy::IsObjectInLeaf(BvhLeaf leaf, Intersectable object) const
1886	{
1887	ObjectContainer::const_iterator oit =
1888	lower_bound(leaf->mObjects.begin(), leaf->mObjects.end(), object, ilt);
1889
1890	// objects sorted by id
1891	if ((oit != leaf->mObjects.end()) && ((*oit)->GetId() == object->GetId()))
1892	{
1893	return true;
1894	}
1895	else
1896	{
1897	return false;
1898	}
1899	}
1900
1901
1902	BvhLeaf BvHierarchy::GetLeaf(Intersectable object, BvhNode *node) const
1903	{
1904	// rather use the simple version
1905	if (!object)
1906	return NULL;
1907	return object->mBvhLeaf;
1908
1909	///////////////////////////////////////
1910	// start from root of tree
1911
1912	if (node == NULL)
1913	node = mRoot;
1914
1915	vector<BvhLeaf *> leaves;
1916
1917	stack<BvhNode *> nodeStack;
1918	nodeStack.push(node);
1919
1920	BvhLeaf *leaf = NULL;
1921
1922	while (!nodeStack.empty())
1923	{
1924	BvhNode *node = nodeStack.top();
1925	nodeStack.pop();
1926
1927	if (node->IsLeaf())
1928	{
1929	leaf = dynamic_cast<BvhLeaf *>(node);
1930
1931	if (IsObjectInLeaf(leaf, object))
1932	{
1933	return leaf;
1934	}
1935	}
1936	else
1937	{
1938	// find point
1939	BvhInterior interior = dynamic_cast<BvhInterior >(node);
1940
1941	if (interior->GetBack()->GetBoundingBox().Includes(object->GetBox()))
1942	{
1943	nodeStack.push(interior->GetBack());
1944	}
1945
1946	// search both sides as we are using bounding volumes
1947	if (interior->GetFront()->GetBoundingBox().Includes(object->GetBox()))
1948	{
1949	nodeStack.push(interior->GetFront());
1950	}
1951	}
1952	}
1953
1954	return leaf;
1955	}
1956
1957
1958	bool BvHierarchy::Export(OUT_STREAM &stream)
1959	{
1960	ExportNode(mRoot, stream);
1961
1962	return true;
1963	}
1964
1965
1966	void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
1967	{
1968	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1969	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1970	{
1971	stream << (*oit)->GetId() << " ";
1972	}
1973	}
1974
1975
1976	void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
1977	{
1978	if (node->IsLeaf())
1979	{
1980	BvhLeaf leaf = dynamic_cast<BvhLeaf >(node);
1981	const AxisAlignedBox3 box = leaf->GetBoundingBox();
1982	stream << "<Leaf"
1983	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1984	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
1985	<< " objects=\"";
1986
1987	//-- export objects
1988	ExportObjects(leaf, stream);
1989
1990	stream << "\" />" << endl;
1991	}
1992	else
1993	{
1994	BvhInterior interior = dynamic_cast<BvhInterior >(node);
1995	const AxisAlignedBox3 box = interior->GetBoundingBox();
1996
1997	stream << "<Interior"
1998	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1999	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
2000	<< "\">" << endl;
2001
2002	ExportNode(interior->GetBack(), stream);
2003	ExportNode(interior->GetFront(), stream);
2004
2005	stream << "</Interior>" << endl;
2006	}
2007	}
2008
2009
2010	float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
2011	{
2012	float vol = 0;
2013
2014	ViewCellContainer viewCells;
2015
2016	// we have to account for all view cells that can
2017	// be seen from the objects
2018	int numRays = CollectViewCells(objects, viewCells, false, false);
2019
2020	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2021
2022	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2023	{
2024	vol += (*vit)->GetVolume();
2025	}
2026
2027	return vol;
2028	}
2029
2030
2031	void BvHierarchy::Initialise(const ObjectContainer &objects)
2032	{
2033	AxisAlignedBox3 box = EvalBoundingBox(objects);
2034
2035	///////
2036	//-- create new root
2037
2038	BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
2039	bvhleaf->mObjects = objects;
2040	mRoot = bvhleaf;
2041
2042	// compute bounding box from objects
2043	mBoundingBox = mRoot->GetBoundingBox();
2044
2045	// associate root with current objects
2046	AssociateObjectsWithLeaf(bvhleaf);
2047	}
2048
2049
2050	/*
2051	Mesh *BvHierarchy::MergeLeafToMesh()
2052	{
2053	vector<BvhLeaf *> leaves;
2054	CollectLeaves(leaves);
2055
2056	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2057
2058	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2059	{
2060	Mesh mesh = MergeLeafToMesh(lit);
2061	}
2062	}*/
2063
2064
2065	SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
2066	const ObjectContainer &objects)
2067	{
2068	///////////////////////////////////////
2069	//-- we assume that we have objects sorted by their id =>
2070	//-- we don't have to sort them here and an binary search
2071	//-- for identifying if a object is in a leaf.
2072
2073	mBvhStats.Reset();
2074	mBvhStats.Start();
2075	mBvhStats.nodes = 1;
2076
2077	// store pointer to this tree
2078	BvhSubdivisionCandidate::sBvHierarchy = this;
2079
2080	// root and bounding box was already constructed
2081	BvhLeaf bvhLeaf = dynamic_cast<BvhLeaf >(mRoot);
2082
2083	// multiply termination criterium for comparison,
2084	// so it can be set between zero and one and
2085	// no division is necessary during traversal
2086
2087	#if PROBABILIY_IS_BV_VOLUME
2088	mTermMinProbability *= mBoundingBox.GetVolume();
2089	// probability that bounding volume is seen
2090	const float prop = GetBoundingBox().GetVolume();
2091	#else
2092	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2093	// probability that volume is "seen" from the view cells
2094	const float prop = EvalViewCellsVolume(objects);
2095	#endif
2096
2097	// only rays intersecting objects in node are interesting
2098	const int nRays = AssociateObjectsWithRays(sampleRays);
2099	//Debug << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
2100
2101	// create bvh traversal data
2102	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2103
2104	// create sorted object lists for the first data
2105	if (mUseGlobalSorting)
2106	{
2107	AssignInitialSortedObjectList(oData);
2108	}
2109
2110
2111	///////////////////
2112	//-- add first candidate for object space partition
2113
2114	BvhSubdivisionCandidate *oSubdivisionCandidate = new BvhSubdivisionCandidate(oData);
2115
2116	// evaluate priority
2117	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2118	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2119
2120	mTotalCost = EvalRenderCost(objects);
2121	mPvsEntries = CountViewCells(objects);
2122
2123	PrintSubdivisionStats(*oSubdivisionCandidate);
2124
2125	return oSubdivisionCandidate;
2126	}
2127
2128
2129	void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData)
2130	{
2131	// we sort the objects as a preprocess so they don't have
2132	// to be sorted for each split
2133	for (int i = 0; i < 3; ++ i)
2134	{
2135	// create new objects
2136	if (!mSortedObjects[i])
2137	{
2138	mSortedObjects[i] = new SortableEntryContainer();
2139	CreateLocalSubdivisionCandidates(tData.mNode->mObjects, &mSortedObjects[i], true, i);
2140	}
2141
2142	// copy list into traversal data list
2143	tData.mSortedObjects[i] = new ObjectContainer();
2144	tData.mSortedObjects[i]->reserve((int)mSortedObjects[i]->size());
2145
2146	SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();
2147
2148	for (oit = mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
2149	{
2150	tData.mSortedObjects[i]->push_back((*oit).mObject);
2151	}
2152	}
2153
2154	// create new objects
2155	if (!mSortedObjects[3])
2156	{
2157	mSortedObjects[3] = new SortableEntryContainer();
2158	}
2159	/*
2160	// last sorted list: by size
2161	tData.mSortedObjects[3] = new ObjectContainer();
2162	tData.mSortedObjects[3]->reserve((int)mSortedObjects[i]->size());
2163
2164	SortableEntryContainer::const_iterator oit, oit_end = mSortedObjects[i]->end();
2165
2166	for (oit = mSortedObjects[3]->begin(); oit != oit_end; ++ oit)
2167	{
2168	tData.mSortedObjects[3]->push_back((*oit).mObject);
2169	}
2170	*/
2171	}
2172
2173
2174	void BvHierarchy::AssignSortedObjects(const BvhSubdivisionCandidate &sc,
2175	BvhTraversalData &frontData,
2176	BvhTraversalData &backData)
2177	{
2178	Intersectable::NewMail();
2179
2180	// we sorted the objects as a preprocess so they don't have
2181	// to be sorted for each split
2182	ObjectContainer::const_iterator fit, fit_end = sc.mFrontObjects.end();
2183
2184	for (fit = sc.mFrontObjects.begin(); fit != fit_end; ++ fit)
2185	{
2186	(*fit)->Mail();
2187	}
2188
2189	for (int i = 0; i < 3; ++ i)
2190	{
2191	frontData.mSortedObjects[i] = new ObjectContainer();
2192	backData.mSortedObjects[i] = new ObjectContainer();
2193
2194	frontData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2195	backData.mSortedObjects[i]->reserve((int)sc.mFrontObjects.size());
2196
2197	ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();
2198
2199	for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
2200	{
2201	if ((*oit)->Mailed())
2202	{
2203	frontData.mSortedObjects[i]->push_back(*oit);
2204	}
2205	else
2206	{
2207	backData.mSortedObjects[i]->push_back(*oit);
2208	}
2209	}
2210	}
2211	}
2212
2213
2214	SubdivisionCandidate *BvHierarchy::Reset(const VssRayContainer &sampleRays,
2215	const ObjectContainer &objects)
2216	{
2217	// reset stats
2218	mBvhStats.Reset();
2219	mBvhStats.Start();
2220	mBvhStats.nodes = 1;
2221
2222	// reset root
2223	DEL_PTR(mRoot);
2224
2225	BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
2226	bvhleaf->mObjects = objects;
2227	mRoot = bvhleaf;
2228
2229	#if PROBABILIY_IS_BV_VOLUME
2230	mTermMinProbability *= mBoundingBox.GetVolume();
2231	// probability that bounding volume is seen
2232	const float prop = GetBoundingBox().GetVolume();
2233	#else
2234	mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
2235	// probability that volume is "seen" from the view cells
2236	const float prop = EvalViewCellsVolume(objects);
2237	#endif
2238
2239	const int nRays = CountRays(objects);
2240	BvhLeaf bvhLeaf = dynamic_cast<BvhLeaf >(mRoot);
2241
2242	// create bvh traversal data
2243	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
2244
2245	AssignInitialSortedObjectList(oData);
2246
2247
2248	///////////////////
2249	//-- add first candidate for object space partition
2250
2251	BvhSubdivisionCandidate *oSubdivisionCandidate =
2252	new BvhSubdivisionCandidate(oData);
2253
2254	EvalSubdivisionCandidate(*oSubdivisionCandidate);
2255	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
2256
2257	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2258	mTotalCost = (float)objects.size() * prop / viewSpaceVol;
2259
2260	PrintSubdivisionStats(*oSubdivisionCandidate);
2261
2262	return oSubdivisionCandidate;
2263	}
2264
2265
2266	void BvhStatistics::Print(ostream &app) const
2267	{
2268	app << "=========== BvHierarchy statistics ===============\n";
2269
2270	app << setprecision(4);
2271
2272	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
2273
2274	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
2275
2276	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
2277
2278	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
2279
2280	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits << endl;
2281
2282	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
2283	<< maxCostNodes * 100 / (double)Leaves() << endl;
2284
2285	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
2286	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
2287
2288
2289	//////////////////////////////////////////////////
2290
2291	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
2292	<< maxDepthNodes * 100 / (double)Leaves() << endl;
2293
2294	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
2295
2296	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
2297
2298	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
2299
2300
2301	////////////////////////////////////////////////////////
2302
2303	app << "#N_PMINOBJECTSLEAVES ( Percentage of leaves with mininum objects )\n"
2304	<< minObjectsNodes * 100 / (double)Leaves() << endl;
2305
2306	app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
2307
2308	app << "#N_MINOBJECTREFS ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";
2309
2310	app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
2311
2312	app << "#N_PAVGOBJECTSLEAVES ( average object refs / leaf)\n" << AvgObjectRefs() << endl;
2313
2314
2315	////////////////////////////////////////////////////////
2316
2317	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with mininum rays )\n"
2318	<< minRaysNodes * 100 / (double)Leaves() << endl;
2319
2320	app << "#N_MAXRAYREFS ( Max number of ray refs / leaf )\n" << maxRayRefs << "\n";
2321
2322	app << "#N_MINRAYREFS ( Min number of ray refs / leaf )\n" << minRayRefs << "\n";
2323
2324	app << "#N_PAVGRAYLEAVES ( average ray refs / leaf )\n" << AvgRayRefs() << endl;
2325
2326	app << "#N_PAVGRAYCONTRIBLEAVES ( Average ray contribution)\n" <<
2327	rayRefs / (double)objectRefs << endl;
2328
2329	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<<
2330	maxRayContriNodes * 100 / (double)Leaves() << endl;
2331
2332	app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
2333
2334	app << "========== END OF BvHierarchy statistics ==========\n";
2335	}
2336
2337
2338	// TODO: return memory usage in MB
2339	float BvHierarchy::GetMemUsage() const
2340	{
2341	return (float)(sizeof(BvHierarchy)
2342	+ mBvhStats.Leaves() * sizeof(BvhLeaf)
2343	+ mBvhStats.Interior() * sizeof(BvhInterior)
2344	) / float(1024 * 1024);
2345	}
2346
2347
2348	void BvHierarchy::SetActive(BvhNode *node) const
2349	{
2350	vector<BvhLeaf *> leaves;
2351
2352	// sets the pointers to the currently active view cells
2353	CollectLeaves(node, leaves);
2354	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
2355
2356	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2357	{
2358	(*lit)->SetActiveNode(node);
2359	}
2360	}
2361
2362
2363	BvhNode *BvHierarchy::SubdivideAndCopy(SplitQueue &tQueue,
2364	SubdivisionCandidate *splitCandidate)
2365	{
2366	BvhSubdivisionCandidate *sc =
2367	dynamic_cast<BvhSubdivisionCandidate *>(splitCandidate);
2368	BvhTraversalData &tData = sc->mParentData;
2369
2370	BvhNode *currentNode = tData.mNode;
2371	BvhNode oldNode = (BvhNode )splitCandidate->mEvaluationHack;
2372
2373	if (!oldNode->IsLeaf())
2374	{
2375	//////////////
2376	//-- continue subdivision
2377
2378	BvhTraversalData tFrontData;
2379	BvhTraversalData tBackData;
2380
2381	BvhInterior oldInterior = dynamic_cast<BvhInterior >(oldNode);
2382
2383	sc->mFrontObjects.clear();
2384	sc->mBackObjects.clear();
2385
2386	oldInterior->GetFront()->CollectObjects(sc->mFrontObjects);
2387	oldInterior->GetBack()->CollectObjects(sc->mBackObjects);
2388
2389	// evaluate the changes in render cost and pvs entries
2390	EvalSubdivisionCandidate(*sc, false);
2391
2392	// create new interior node and two leaf node
2393	currentNode = SubdivideNode(*sc, tFrontData, tBackData);
2394
2395	//oldNode->mRenderCostDecr += sc->GetRenderCostDecrease();
2396	//oldNode->mPvsEntriesIncr += sc->GetPvsEntriesIncr();
2397
2398	//oldNode->mRenderCostDecr = sc->GetRenderCostDecrease();
2399	//oldNode->mPvsEntriesIncr = sc->GetPvsEntriesIncr();
2400
2401	///////////////////////////
2402	//-- push the new split candidates on the queue
2403
2404	BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
2405	BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
2406
2407	frontCandidate->SetPriority((float)-oldInterior->GetFront()->GetTimeStamp());
2408	backCandidate->SetPriority((float)-oldInterior->GetBack()->GetTimeStamp());
2409
2410	frontCandidate->mEvaluationHack = oldInterior->GetFront();
2411	backCandidate->mEvaluationHack = oldInterior->GetBack();
2412
2413	// cross reference
2414	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
2415	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
2416
2417	//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
2418	tQueue.Push(frontCandidate);
2419	tQueue.Push(backCandidate);
2420	}
2421
2422	/////////////////////////////////
2423	//-- node is a leaf => terminate traversal
2424
2425	if (currentNode->IsLeaf())
2426	{
2427	// this leaf is no candidate for splitting anymore
2428	// => detach subdivision candidate
2429	tData.mNode->SetSubdivisionCandidate(NULL);
2430	// detach node so we don't delete it with the traversal data
2431	tData.mNode = NULL;
2432	}
2433
2434	return currentNode;
2435	}
2436
2437
2438	void BvHierarchy::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2439	{
2440	stack<BvhNode *> nodeStack;
2441
2442	nodeStack.push(mRoot);
2443
2444	while (!nodeStack.empty())
2445	{
2446	BvhNode *node = nodeStack.top();
2447
2448	nodeStack.pop();
2449
2450	if (node->IsLeaf())
2451	{
2452	BvhLeaf leaf = (BvhLeaf )node;
2453	if (Overlap(box, leaf->GetBoundingBox())) {
2454	Intersectable *object = leaf;
2455	if (!object->Mailed()) {
2456	object->Mail();
2457	objects.push_back(object);
2458	}
2459	}
2460	}
2461	else
2462	{
2463	BvhInterior interior = (BvhInterior )node;
2464
2465	if (Overlap(box, interior->GetBoundingBox()))
2466	nodeStack.push(interior->GetFront());
2467
2468	if (Overlap(box, interior->GetBoundingBox()))
2469	nodeStack.push(interior->GetBack());
2470	}
2471	}
2472	}
2473
2474
2475	void BvHierarchy::InititialSubdivision(ObjectContainer &objects)
2476	{
2477	/*std::stable_sort(objects.begin(), objects.end(), ilt2);
2478	ObjectContainer::iterator oit;
2479
2480	stack<BvhLeaf *> tStack;
2481
2482	while (!tStack.empty())
2483	{
2484	BvhLeaf *leaf = tStack.top();
2485
2486	if (!InitialTerminationCriteriaMet(leaf))
2487	{
2488	ChooseSplitIndex(objects, oit);
2489	SubdivideLeaf(leaf, oit);
2490	}
2491	}*/
2492	}
2493
2494
2495	void BvHierarchy::ChooseSplitIndex(const ObjectContainer &objects,
2496	ObjectContainer::const_iterator &oit)
2497	{
2498	ObjectContainer::const_iterator oit2, oit2_end = objects.end();
2499
2500	float maxAreaDiff = 0.0f;
2501
2502	for (oit2 = objects.begin(); oit2 != (objects.end() - 1); ++ oit2)
2503	{
2504	Intersectable obj = oit2;
2505	Intersectable obj2 = (oit2 + 1);
2506
2507	const float areaDiff =
2508	fabs(obj->GetBox().SurfaceArea() - obj2->GetBox().SurfaceArea());
2509
2510	if (areaDiff > maxAreaDiff)
2511	{
2512	maxAreaDiff = areaDiff;
2513	oit = oit2;
2514	}
2515	}
2516	}
2517
2518
2519	bool BvHierarchy::InitialTerminationCriteriaMet(BvhLeaf *leaf) const
2520	{
2521	if (((int)leaf->mObjects.size() < mInititialObjectsSize) \|\|
2522	(leaf->mObjects.back()->GetBox().SurfaceArea() < mMinInitialSurfaceArea))
2523
2524	{
2525	return true;
2526	}
2527
2528	return false;
2529	}
2530
2531
2532	}

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

Download in other formats: