Context Navigation

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

Revision 2347, 92.8 KB checked in by mattausch, 17 years ago (diff)
debug version

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

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

Download in other formats: