Context Navigation

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

Revision 2224, 85.4 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: