Context Navigation

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

Revision 2332, 85.0 KB checked in by mattausch, 17 years ago (diff)
implemented part of rendering estimation of wimmer et al. for view space / object space subdivision. warning: not working with undersampling estimation + local visibility based subdivision.

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

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

Download in other formats: