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

Rev	Line
[1237]	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"
[1370]	19	#include "HierarchyManager.h"
[1237]	20
	21
	22	namespace GtpVisibilityPreprocessor {
	23
	24
[1370]	25	#define PROBABILIY_IS_BV_VOLUME 1
[1237]	26	#define USE_FIXEDPOINT_T 0
[1662]	27	#define USE_VOLUMES_FOR_HEURISTICS 1
[2003]	28	#define TEST_POWERPLANT 0
[2199]	29
[2332]	30
[2003]	31	//int BvhNode::sMailId = 10000;
	32	//int BvhNode::sReservedMailboxes = 1;
[1662]	33
[1237]	34	BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;
	35
	36
[1357]	37	/// sorting operator
[1237]	38	inline static bool ilt(Intersectable obj1, Intersectable obj2)
	39	{
	40	return obj1->mId < obj2->mId;
	41	}
	42
	43
[1778]	44	/// sorting operator
[1779]	45	inline static bool smallerSize(Intersectable obj1, Intersectable obj2)
[1778]	46	{
	47	return obj1->GetBox().SurfaceArea() < obj2->GetBox().SurfaceArea();
	48	}
	49
[1843]	50
	51
[1237]	52	/***************************************************************/
	53	/* class BvhNode implementation */
	54	/***************************************************************/
	55
[2347]	56
[1679]	57	BvhNode::BvhNode():
	58	mParent(NULL),
[1786]	59	mTimeStamp(0),
	60	mRenderCost(-1)
	61
[1237]	62	{
[1709]	63
[1237]	64	}
	65
	66	BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
[1679]	67	mParent(NULL),
	68	mBoundingBox(bbox),
[1786]	69	mTimeStamp(0),
	70	mRenderCost(-1)
[1237]	71	{
	72	}
	73
	74
	75	BvhNode::BvhNode(const AxisAlignedBox3 &bbox, BvhInterior *parent):
[1679]	76	mBoundingBox(bbox),
	77	mParent(parent),
[1786]	78	mTimeStamp(0),
	79	mRenderCost(-1)
[1237]	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
[1763]	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
[1768]	110	const float w = RandomValue(0.0f, 1.0f);
[1237]	111
[1768]	112	point = a * w + b * (1.0f - w);
[1763]	113
[1768]	114	// TODO
	115	normal = Vector3(0);
	116
[1763]	117	return idx;
	118	}
	119
	120
[1767]	121
[1237]	122	/******************************************************************/
	123	/* class BvhInterior implementation */
	124	/******************************************************************/
	125
	126
	127	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox):
[1709]	128	BvhNode(bbox),
[1785]	129	mSubdivisionCandidate(NULL),
	130	mGlList(0)
[1237]	131	{
[1785]	132	mActiveNode = this;
[1237]	133	}
	134
	135
	136	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent):
[1785]	137	BvhNode(bbox, parent),
	138	mGlList(0)
	139
[1237]	140	{
[1709]	141	mActiveNode = this;
[1237]	142	}
	143
	144
[1287]	145	BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox,
	146	BvhInterior *parent,
	147	const int numObjects):
[1785]	148	BvhNode(bbox, parent),
	149	mGlList(0)
	150
[1237]	151	{
	152	mObjects.reserve(numObjects);
[1709]	153	mActiveNode = this;
[1237]	154	}
	155
	156
	157	bool BvhLeaf::IsLeaf() const
	158	{
	159	return true;
	160	}
	161
	162
	163	BvhLeaf::~BvhLeaf()
	164	{
	165	}
	166
[1686]	167
[1614]	168	void BvhLeaf::CollectObjects(ObjectContainer &objects)
	169	{
[1686]	170	ObjectContainer::const_iterator oit, oit_end = mObjects.end();
	171	for (oit = mObjects.begin(); oit != oit_end; ++ oit)
[1614]	172	{
	173	objects.push_back(*oit);
	174	}
	175	}
[1237]	176
[2199]	177
	178
[1237]	179	/******************************************************************/
	180	/* class BvhInterior implementation */
	181	/******************************************************************/
	182
	183
	184	BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
[1287]	185	BvhNode(bbox), mFront(NULL), mBack(NULL)
[1237]	186	{
	187	}
	188
	189
	190	BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
[1287]	191	BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
[1237]	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()
[1999]	212	{
[1237]	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
[1614]	225	void BvhInterior::CollectObjects(ObjectContainer &objects)
	226	{
	227	mFront->CollectObjects(objects);
	228	mBack->CollectObjects(objects);
	229	}
[1237]	230
[1614]	231
[1237]	232	/*******************************************************************/
	233	/* class BvHierarchy implementation */
	234	/*******************************************************************/
	235
	236
	237	BvHierarchy::BvHierarchy():
	238	mRoot(NULL),
[1779]	239	mTimeStamp(1),
[2210]	240	mIsInitialSubdivision(false)
[1237]	241	{
	242	ReadEnvironment();
[1357]	243	mSubdivisionCandidates = new SortableEntryContainer;
[1779]	244	// for (int i = 0; i < 4; ++ i)
	245	// mSortedObjects[i] = NULL;
[1237]	246	}
	247
	248
	249	BvHierarchy::~BvHierarchy()
	250	{
[1696]	251	// delete the local subdivision candidates
[1237]	252	DEL_PTR(mSubdivisionCandidates);
	253
[1696]	254	// delete the presorted objects
[1779]	255	/*for (int i = 0; i < 4; ++ i)
[1580]	256	{
	257	DEL_PTR(mSortedObjects[i]);
[1779]	258	}*/
[1696]	259
	260	// delete the tree
	261	DEL_PTR(mRoot);
[1237]	262	}
	263
	264
	265	void BvHierarchy::ReadEnvironment()
	266	{
	267	bool randomize = false;
[1779]	268	Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.randomize", randomize);
[1698]	269
	270	// initialise random generator for heuristics
[1237]	271	if (randomize)
[1698]	272	Randomize();
[1237]	273
[1698]	274	//////////////////////////////
[1237]	275	//-- termination criteria for autopartition
[1643]	276
[1288]	277	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxDepth", mTermMaxDepth);
	278	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.maxLeaves", mTermMaxLeaves);
	279	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minObjects", mTermMinObjects);
[1370]	280	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.minRays", mTermMinRays);
[1934]	281	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minProbability", mTermMinProbability);
[1698]	282	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.missTolerance", mTermMissTolerance);
[1370]	283
	284
[1421]	285	//////////////////////////////
[1237]	286	//-- max cost ratio for early tree termination
[1370]	287
[1288]	288	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.maxCostRatio", mTermMaxCostRatio);
	289	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Termination.minGlobalCostRatio",
[1237]	290	mTermMinGlobalCostRatio);
[1294]	291	Environment::GetSingleton()->GetIntValue("BvHierarchy.Termination.globalCostMissTolerance",
	292	mTermGlobalCostMissTolerance);
[1237]	293
	294
[1421]	295	//////////////////////////////
[1370]	296	//-- factors for subdivision heuristics
	297
	298	// if only the driving axis is used for splits
[1288]	299	Environment::GetSingleton()->GetBoolValue("BvHierarchy.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
	300	Environment::GetSingleton()->GetFloatValue("BvHierarchy.maxStaticMemory", mMaxMemory);
	301	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useCostHeuristics", mUseCostHeuristics);
[1643]	302	Environment::GetSingleton()->GetBoolValue("BvHierarchy.useSah", mUseSah);
[1676]	303
	304	char subdivisionStatsLog[100];
[1288]	305	Environment::GetSingleton()->GetStringValue("BvHierarchy.subdivisionStats", subdivisionStatsLog);
[1237]	306	mSubdivisionStats.open(subdivisionStatsLog);
	307
[1779]	308	Environment::GetSingleton()->GetFloatValue("BvHierarchy.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
	309	Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useGlobalSorting", mUseGlobalSorting);
[1727]	310	Environment::GetSingleton()->GetIntValue("BvHierarchy.minRaysForVisibility", mMinRaysForVisibility);
	311	Environment::GetSingleton()->GetIntValue("BvHierarchy.maxTests", mMaxTests);
[1789]	312	Environment::GetSingleton()->GetBoolValue("BvHierarchy.Construction.useInitialSubdivision", mApplyInitialPartition);
[1786]	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);
[1784]	316
[1732]	317	//mMemoryConst = (float)(sizeof(VspLeaf) + sizeof(VspViewCell));
	318	//mMemoryConst = (float)sizeof(BvhLeaf);
[1760]	319	mMemoryConst = 16;//(float)sizeof(ObjectContainer);
[1744]	320
[1732]	321	mUseBboxAreaForSah = true;
	322
[1421]	323	/////////////
[1237]	324	//-- debug output
[1359]	325
[1237]	326	Debug << "***** Bvh hierarchy options ****** " << endl;
	327	Debug << "max depth: " << mTermMaxDepth << endl;
[1287]	328	Debug << "min probabiliy: " << mTermMinProbability<< endl;
[1237]	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;
[1736]	339	Debug << "use surface area heuristics: " << mUseSah << endl;
[1237]	340	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[2124]	341	//Debug << "split borders: " << mSplitBorder << endl;
[1237]	342	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
[1357]	343	Debug << "use global sort: " << mUseGlobalSorting << endl;
[1676]	344	Debug << "minimal rays for visibility: " << mMinRaysForVisibility << endl;
[1732]	345	Debug << "bvh mem const: " << mMemoryConst << endl;
[1779]	346	Debug << "apply initial partition: " << mApplyInitialPartition << endl;
[1786]	347	Debug << "min objects: " << mInitialMinObjects << endl;
	348	Debug << "max area ratio: " << mInitialMaxAreaRatio << endl;
	349	Debug << "min area: " << mInitialMinArea << endl;
	350
[1237]	351	Debug << endl;
	352	}
	353
	354
[1486]	355	void BvHierarchy::AssociateObjectsWithLeaf(BvhLeaf *leaf)
[1237]	356	{
	357	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1693]	358
[1237]	359	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	360	{
	361	(*oit)->mBvhLeaf = leaf;
	362	}
	363	}
	364
[1486]	365
[1370]	366	static int CountRays(const ObjectContainer &objects)
	367	{
	368	int nRays = 0;
[1237]	369
[1370]	370	ObjectContainer::const_iterator oit, oit_end = objects.end();
	371
[2198]	372	// warning: not exact number (there can be rays counted twice)
	373	// otherwise we would have to traverse trough all rays
[1370]	374	for (oit = objects.begin(); oit != oit_end; ++ oit)
	375	{
[1696]	376	nRays += (int)(*oit)->GetOrCreateRays()->size();
[1370]	377	}
	378
	379	return nRays;
	380	}
[2198]	381
[1680]	382
[1913]	383	float BvHierarchy::GetViewSpaceVolume() const
	384	{
	385	return mViewCellsManager->GetViewSpaceBox().GetVolume();
	386	}
[1680]	387
[1913]	388
[2332]	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
[2347]	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();
[2332]	400
[2347]	401	//cout << "totalTri: " << totalTri << " f: " << frontTri << " back: " << backTri << endl;
	402
[2332]	403	ViewCell::NewMail(3);
	404
[2342]	405	// mail view cells which can see front object
[2332]	406	ViewCellContainer::const_iterator fit, fit_end = frontViewCells.end();
	407
	408	for (fit = frontViewCells.begin(); fit != fit_end; ++ fit)
	409	{
[2347]	410	(*fit)->Mail(0);
[2332]	411	}
	412
[2342]	413	// mail view cells which can see back or both objects
[2332]	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
[2347]	426	// traverse through view cells and compute changes
[2332]	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
[2347]	433	int vcTri;
[2332]	434	int vcObj;
	435
[2347]	436	int oldVcTri = (int)vc->GetTrianglesInPvs();
[2332]	437	int oldVcObj = vc->GetEntriesInPvs();
	438
[2342]	439	// both objects seen from view cell
	440	// => no reduction, but an additional pvs entry
[2332]	441	if (vc->Mailed(2))
	442	{
	443	vcTri = oldVcTri;
	444	vcObj = oldVcObj + 1;
	445	}
[2342]	446	// only back object seen from view cell
	447	// => reduction in triangles
[2332]	448	else if (vc->Mailed(1))
	449	{
[2347]	450	vcTri = oldVcTri + backTri - totalTri;
[2332]	451	vcObj = oldVcObj;
	452	}
[2342]	453	else // front object
[2332]	454	{
[2347]	455	vcTri = oldVcTri + frontTri - totalTri;
[2332]	456	vcObj = oldVcObj;
	457	}
	458
[2347]	459	vc->SetTrianglesInPvs((float)vcTri);
[2332]	460	vc->SetEntriesInPvs(vcObj);
	461
	462	//cout << "old pvs tri: " << oldVcTri << " new: " << vcTri << endl;
[2347]	463	//cout << "old pvs obj: " << oldVcObj << " new: " << vcObj << endl;
[2332]	464	}
	465	}
	466
	467
[2347]	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
[1345]	529	BvhInterior *BvHierarchy::SubdivideNode(const BvhSubdivisionCandidate &sc,
[1237]	530	BvhTraversalData &frontData,
	531	BvhTraversalData &backData)
[2003]	532	{
[2347]	533	//TestEvaluation(sc);
	534
[2198]	535	// fill view cells cache
[2187]	536	mNodeTimer.Entry();
[2198]	537
[1345]	538	const BvhTraversalData &tData = sc.mParentData;
[1237]	539	BvhLeaf *leaf = tData.mNode;
[1912]	540
[1370]	541	AxisAlignedBox3 parentBox = leaf->GetBoundingBox();
[1237]	542
[1421]	543	// update stats: we have two new leaves
	544	mBvhStats.nodes += 2;
[1379]	545
	546	if (tData.mDepth > mBvhStats.maxDepth)
	547	{
	548	mBvhStats.maxDepth = tData.mDepth;
	549	}
	550
[1237]	551	// add the new nodes to the tree
[1370]	552	BvhInterior *node = new BvhInterior(parentBox, leaf->GetParent());
[1237]	553
[2198]	554
[1421]	555	//////////////////
[1237]	556	//-- create front and back leaf
	557
[1405]	558	AxisAlignedBox3 fbox = EvalBoundingBox(sc.mFrontObjects, &parentBox);
	559	AxisAlignedBox3 bbox = EvalBoundingBox(sc.mBackObjects, &parentBox);
[1370]	560
[1684]	561	BvhLeaf *back = new BvhLeaf(bbox, node, (int)sc.mBackObjects.size());
	562	BvhLeaf *front = new BvhLeaf(fbox, node, (int)sc.mFrontObjects.size());
[1237]	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	}
[1345]	572	else // no parent => this node is the root
[1237]	573	{
	574	mRoot = node;
	575	}
	576
	577	// and setup child links
	578	node->SetupChildLinks(front, back);
	579
	580	++ mBvhStats.splits;
	581
[2003]	582
[2332]	583	////////////////////////////////
[1912]	584	//-- fill front and back traversal data with the new values
[1370]	585
	586	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
	587
[1237]	588	frontData.mNode = front;
	589	backData.mNode = back;
	590
[2210]	591	backData.mSampledObjects = new ObjectContainer();
	592	frontData.mSampledObjects = new ObjectContainer();
	593
	594	*backData.mSampledObjects = sc.mSampledBackObjects;
	595	*frontData.mSampledObjects = sc.mSampledFrontObjects;
	596
[1345]	597	back->mObjects = sc.mBackObjects;
	598	front->mObjects = sc.mFrontObjects;
[1237]	599
[1370]	600	// if the number of rays is too low, no assumptions can be made
	601	// (=> switch to surface area heuristics?)
[2210]	602	frontData.mNumRays = CountRays(sc.mSampledFrontObjects);
	603	backData.mNumRays = CountRays(sc.mSampledBackObjects);
[1370]	604
[1237]	605	AssociateObjectsWithLeaf(back);
	606	AssociateObjectsWithLeaf(front);
[2003]	607
	608	////////////
[1912]	609	//-- compute pvs correction to cope with undersampling
[2003]	610
[2332]	611	frontData.mPvs = (float)sc.mNumFrontViewCells;
	612	backData.mPvs = (float)sc.mNumBackViewCells;
[1912]	613
	614	frontData.mCorrectedPvs = sc.mCorrectedFrontPvs;
	615	backData.mCorrectedPvs = sc.mCorrectedBackPvs;
	616
[2003]	617
[1345]	618	// compute probability of this node being visible,
	619	// i.e., volume of the view cells that can see this node
[2332]	620	frontData.mVolume = sc.mVolumeFrontViewCells;
	621	backData.mVolume = sc.mVolumeBackViewCells;
[1237]	622
[1913]	623	frontData.mCorrectedVolume = sc.mCorrectedFrontVolume;
	624	backData.mCorrectedVolume = sc.mCorrectedBackVolume;
[1912]	625
[2003]	626
[1345]	627	// how often was max cost ratio missed in this branch?
[1576]	628	frontData.mMaxCostMisses = sc.GetMaxCostMisses();
	629	backData.mMaxCostMisses = sc.GetMaxCostMisses();
[1912]	630
[1687]	631	// set the time stamp so the order of traversal can be reconstructed
[1763]	632	node->SetTimeStamp(mHierarchyManager->mTimeStamp ++);
[2003]	633
[1357]	634	// assign the objects in sorted order
[2005]	635	if (mUseGlobalSorting)
[1357]	636	{
	637	AssignSortedObjects(sc, frontData, backData);
	638	}
[2224]	639
[2342]	640	// compute new stats for the view cells which see this object,
	641	// e.g. new render cost decrease after the split
[2332]	642	UpdateViewCells(sc);
	643
[2187]	644	mNodeTimer.Exit();
	645
[1345]	646	// return the new interior node
[1237]	647	return node;
	648	}
	649
	650
	651	BvhNode *BvHierarchy::Subdivide(SplitQueue &tQueue,
	652	SubdivisionCandidate *splitCandidate,
[2224]	653	const bool globalCriteriaMet
	654	,vector<SubdivisionCandidate *> &dirtyList
	655	)
[1237]	656	{
[2187]	657	mSubdivTimer.Entry();
	658
[1779]	659	BvhSubdivisionCandidate *sc =
[2017]	660	static_cast<BvhSubdivisionCandidate *>(splitCandidate);
[1237]	661	BvhTraversalData &tData = sc->mParentData;
	662
[1345]	663	BvhNode *currentNode = tData.mNode;
[1237]	664
	665	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	666	{
[1421]	667	//////////////
[1294]	668	//-- continue subdivision
	669
[1237]	670	BvhTraversalData tFrontData;
	671	BvhTraversalData tBackData;
[2003]	672
[1237]	673	// create new interior node and two leaf node
[1664]	674	currentNode = SubdivideNode(*sc, tFrontData, tBackData);
[2187]	675
[1287]	676	// decrease the weighted average cost of the subdivisoin
[1237]	677	mTotalCost -= sc->GetRenderCostDecrease();
[1662]	678	mPvsEntries += sc->GetPvsEntriesIncr();
[1237]	679
	680	// subdivision statistics
[1287]	681	if (1) PrintSubdivisionStats(*sc);
[1237]	682
[1345]	683
[1421]	684	///////////////////////////
[1237]	685	//-- push the new split candidates on the queue
	686
[1779]	687	BvhSubdivisionCandidate *frontCandidate =
	688	new BvhSubdivisionCandidate(tFrontData);
	689	BvhSubdivisionCandidate *backCandidate =
	690	new BvhSubdivisionCandidate(tBackData);
[1786]	691
[2224]	692	// preprocess view cells
	693	AssociateViewCellsWithObjects(*tData.mSampledObjects);
[2187]	694
[2347]	695	EvalSubdivisionCandidate2(*frontCandidate, true, false);
	696	cout << "\nfc2: " << frontCandidate->GetPriority() << endl;
[2224]	697	EvalSubdivisionCandidate(*frontCandidate, true, false);
[2347]	698	cout << "fc1: " << frontCandidate->GetPriority() << endl;
[2224]	699	EvalSubdivisionCandidate(*backCandidate, true, false);
	700
	701	CollectDirtyCandidates(sc, dirtyList, true);
[2229]	702
	703	// release preprocessed view cells
[2224]	704	ReleaseViewCells(*tData.mSampledObjects);
	705
[1297]	706	// cross reference
	707	tFrontData.mNode->SetSubdivisionCandidate(frontCandidate);
	708	tBackData.mNode->SetSubdivisionCandidate(backCandidate);
[1305]	709
[1664]	710	//cout << "f: " << frontCandidate->GetPriority() << " b: " << backCandidate->GetPriority() << endl;
[1237]	711	tQueue.Push(frontCandidate);
	712	tQueue.Push(backCandidate);
	713	}
	714
[1345]	715	/////////////////////////////////
	716	//-- node is a leaf => terminate traversal
[1237]	717
[1345]	718	if (currentNode->IsLeaf())
[1237]	719	{
[1664]	720	/////////////////////
[1297]	721	//-- store additional info
[1237]	722	EvaluateLeafStats(tData);
	723
[1345]	724	// this leaf is no candidate for splitting anymore
	725	// => detach subdivision candidate
[1305]	726	tData.mNode->SetSubdivisionCandidate(NULL);
[1345]	727	// detach node so we don't delete it with the traversal data
[1294]	728	tData.mNode = NULL;
[1237]	729	}
	730
[2187]	731	mSubdivTimer.Exit();
	732
[1345]	733	return currentNode;
[1237]	734	}
	735
	736
[1779]	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
[2347]	751	// use urface area heuristics if no view space subdivision available.
	752	// For prioritized traversal we use this formula instead
[1779]	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!
[2347]	762	priority = mRenderCostDecreaseWeight * renderCostDecr +
	763	(1.0f - mRenderCostDecreaseWeight) * oldRenderCost;
[1779]	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
[1893]	779	static float AvgRayContribution(const int pvs, const int nRays)
	780	{
[1895]	781	return (float)pvs / ((float)nRays + Limits::Small);
[1893]	782	}
	783
	784
[2227]	785	static float AvgRaysPerObject(const int pvs, const int nRays)
	786	{
	787	return (float)nRays / ((float)pvs + Limits::Small);
	788	}
	789
	790
[2347]	791	void BvHierarchy::EvalSubdivisionCandidate2(BvhSubdivisionCandidate &splitCandidate,
[2224]	792	const bool computeSplitPlane,
	793	const bool preprocessViewCells)
[1237]	794	{
[2198]	795	mPlaneTimer.Entry();
	796
[2332]	797	const BvhTraversalData &tData = splitCandidate.mParentData;
	798	BvhLeaf *leaf = tData.mNode;
	799
[2198]	800	#if STORE_VIEWCELLS_WITH_BVH
[2224]	801	if (preprocessViewCells) // fill view cells cache
	802	AssociateViewCellsWithObjects(*splitCandidate.mParentData.mSampledObjects);
[2198]	803	#endif
	804
[1667]	805	if (computeSplitPlane)
	806	{
[2210]	807	splitCandidate.mFrontObjects.clear();
	808	splitCandidate.mBackObjects.clear();
[2332]	809
[2210]	810	splitCandidate.mSampledFrontObjects.clear();
	811	splitCandidate.mSampledBackObjects.clear();
	812
[1698]	813	const bool sufficientSamples =
[2332]	814	tData.mNumRays > mMinRaysForVisibility;
[1676]	815
	816	const bool useVisibiliyBasedHeuristics =
[1908]	817	!mUseSah &&
[1784]	818	(mHierarchyManager->GetViewSpaceSubdivisionType() ==
	819	HierarchyManager::KD_BASED_VIEWSPACE_SUBDIV) &&
	820	sufficientSamples;
[1676]	821
[1667]	822	// compute best object partition
[2332]	823	const float ratio = SelectObjectPartition(tData,
[1667]	824	splitCandidate.mFrontObjects,
[1676]	825	splitCandidate.mBackObjects,
	826	useVisibiliyBasedHeuristics);
[1287]	827
[1667]	828	// cost ratio violated?
	829	const bool maxCostRatioViolated = mTermMaxCostRatio < ratio;
	830	const int previousMisses = splitCandidate.mParentData.mMaxCostMisses;
[1287]	831
[1893]	832	splitCandidate.SetMaxCostMisses(maxCostRatioViolated ?
	833	previousMisses + 1 : previousMisses);
[2210]	834
	835	StoreSampledObjects(splitCandidate.mSampledFrontObjects, splitCandidate.mFrontObjects);
	836	StoreSampledObjects(splitCandidate.mSampledBackObjects, splitCandidate.mBackObjects);
[1667]	837	}
[2210]	838
[2198]	839	mPlaneTimer.Exit();
[1288]	840
[2332]	841
	842	///////////////////
	843
[2198]	844	mEvalTimer.Entry();
[2003]	845
[2347]	846	// mark view cells according to what part of the split they see
	847	// and compute volume
[2332]	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);
[1667]	853
[2332]	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	{
[2347]	879	// view cell sees front AND back object
[2332]	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
[2347]	892	//cout << "pvol: " << parentVol << " front: " << volFront << " back: " << volBack << " diff: " << parentVol - volFront - volBack << endl;
[2332]	893
[2347]	894
[2332]	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();
[2347]	900
	901	// for low #rays per object => the result is influenced by undersampling
[2227]	902	const float avgRaysPerObject = AvgRaysPerObject((int)pvs, tData.mNumRays);
[2347]	903	splitCandidate.SetAvgRaysPerObject(avgRaysPerObject);
[1911]	904
[2199]	905	const float viewSpaceVol = GetViewSpaceVolume();
[1911]	906
[2332]	907	splitCandidate.mVolumeFrontViewCells = volFront / viewSpaceVol;
	908	splitCandidate.mVolumeBackViewCells = volBack / viewSpaceVol;
[1911]	909
[2332]	910	splitCandidate.mNumFrontViewCells = (int)frontViewCells.size();
	911	splitCandidate.mNumBackViewCells = (int)backViewCells.size();
[1237]	912
[2347]	913
	914	////////////////////////
	915	// warning: currently not working for new evaluation method!
	916
	917	// todo matt: fix this to cope with undersampling
[1913]	918	splitCandidate.mCorrectedFrontVolume =
[2332]	919	mHierarchyManager->EvalCorrectedPvs(splitCandidate.mVolumeFrontViewCells,
	920	parentVol,
	921	avgRaysPerObject);
[1916]	922
[1913]	923	splitCandidate.mCorrectedBackVolume =
[2332]	924	mHierarchyManager->EvalCorrectedPvs(splitCandidate.mVolumeBackViewCells,
	925	parentVol,
	926	avgRaysPerObject);
[1913]	927
[2332]	928	///////////////////////////////////
	929
	930
	931	float newRenderCost = 0, oldRenderCost = 0;
	932
[2347]	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;
[2332]	940
[2347]	941	// compute render cost decrease in the view cells which can see the object
[2332]	942	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1912]	943
[2332]	944	for (vit = viewCells.begin(); vit != viewCells.end(); ++ vit)
	945	{
	946	ViewCell vc = vit;
[1663]	947
[2347]	948	const int oldVcTri = (int)vc->GetTrianglesInPvs();
	949	const int oldVcObj = vc->GetEntriesInPvs();
	950
[2332]	951	// triangles in this view cell
[2347]	952	int vcTri;
[2332]	953	// #entries in this view cell
	954	int vcObj;
[2347]	955
[2332]	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	{
[2347]	965	// only back node in this view cell: #triangles is decreasing
	966	vcTri = oldVcTri + backTri - totalTri;
[2332]	967	vcObj = oldVcObj;
	968	}
	969	else // (vc->Mailed(0))
	970	{
[2347]	971	// only front node in this view cell: #triangles is decreasing
	972	vcTri = oldVcTri + frontTri - totalTri;
[2332]	973	vcObj = oldVcObj;
	974	}
	975
[2347]	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;
[2332]	982	//cout << "old rc=" << oldRenderCost << " new rc " << newRenderCost << endl;
[2003]	983	}
[1916]	984
[2347]	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
[2332]	1000	// compute global decrease in render cost
[2347]	1001	const float dummyNewRenderCost = relfrontCost + relBackCost;
	1002	const float dummyRenderCostDecr = relParentCost - dummyNewRenderCost;
[1576]	1003
[1893]	1004
[2347]	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);
[2332]	1011	splitCandidate.SetRenderCostDecrease(renderCostDecr);
[2347]	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
[2332]	1136	splitCandidate.SetPvsEntriesIncr(pvsEntriesIncr);
	1137
[2347]	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
[2332]	1143
[2347]	1144	float priority = EvalPriority(splitCandidate,
	1145	renderCostDecr,
	1146	relParentCost);
	1147
	1148	// compute global decrease in render cost
[1237]	1149	splitCandidate.SetPriority(priority);
[2198]	1150
	1151	#if STORE_VIEWCELLS_WITH_BVH
[2224]	1152	if (preprocessViewCells)
	1153	ReleaseViewCells(*splitCandidate.mParentData.mSampledObjects);
[2198]	1154	#endif
	1155
[2187]	1156	mEvalTimer.Exit();
[1237]	1157	}
	1158
	1159
[1912]	1160	int BvHierarchy::EvalPvsEntriesIncr(BvhSubdivisionCandidate &splitCandidate,
[2227]	1161	const float avgRaysPerObjects,
[2210]	1162	const int numParentViewCells,
	1163	const int numFrontViewCells,
	1164	const int numBackViewCells) //const
[1576]	1165	{
[2332]	1166	const float oldPvsSize = (float)numParentViewCells;
	1167	const float oldPvsRatio =
	1168	(splitCandidate.mParentData.mPvs > 0) ? oldPvsSize / splitCandidate.mParentData.mPvs : 1;
[1912]	1169
	1170	const float parentPvs = splitCandidate.mParentData.mCorrectedPvs * oldPvsRatio;
	1171
[2332]	1172	const int frontViewCells = numFrontViewCells;
	1173	const int backViewCells = numBackViewCells;
[1576]	1174
[1912]	1175	splitCandidate.mCorrectedFrontPvs =
[2227]	1176	mHierarchyManager->EvalCorrectedPvs((float)frontViewCells, parentPvs, avgRaysPerObjects);
[1912]	1177	splitCandidate.mCorrectedBackPvs =
[2227]	1178	mHierarchyManager->EvalCorrectedPvs((float)backViewCells, parentPvs, avgRaysPerObjects);
[1912]	1179
[2347]	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
[1916]	1187
[1913]	1188	return (int)(splitCandidate.mCorrectedFrontPvs + splitCandidate.mCorrectedBackPvs - parentPvs);
[1576]	1189	}
	1190
	1191
[1779]	1192	inline bool BvHierarchy::LocalTerminationCriteriaMet(const BvhTraversalData &tData) const
[1237]	1193	{
[1705]	1194	const bool terminationCriteriaMet =
	1195	(0
[1779]	1196	\|\| ((int)tData.mNode->mObjects.size() <= 1)//mTermMinObjects)
[1634]	1197	//\|\| (data.mProbability <= mTermMinProbability)
[1705]	1198	//\|\| (data.mNumRays <= mTermMinRays)
[1237]	1199	);
[1705]	1200
	1201	#ifdef _DEBUG
	1202	if (terminationCriteriaMet)
	1203	{
[2347]	1204	Debug << "bvh local termination criteria met:" << endl;
	1205	Debug << "objects: " << (int)tData.mNode->mObjects.size() << " (" << mTermMinObjects << ")" << endl;
[1705]	1206	}
	1207	#endif
	1208	return terminationCriteriaMet;
[1237]	1209	}
	1210
	1211
[1251]	1212	inline bool BvHierarchy::GlobalTerminationCriteriaMet(const BvhTraversalData &data) const
[1237]	1213	{
[1610]	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
[1421]	1218	const bool terminationCriteriaMet =
	1219	(0
[1288]	1220	\|\| (mBvhStats.Leaves() >= mTermMaxLeaves)
[1522]	1221	//\|\| (mBvhStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
[1288]	1222	//\|\| mOutOfMemory
[1237]	1223	);
[1421]	1224
[1715]	1225	#ifdef GTP_DEBUG
[1633]	1226	if (terminationCriteriaMet)
[1421]	1227	{
	1228	Debug << "bvh global termination criteria met:" << endl;
[1449]	1229	Debug << "cost misses: " << mBvhStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
[1421]	1230	Debug << "leaves: " << mBvhStats.Leaves() << " " << mTermMaxLeaves << endl;
	1231	}
[1633]	1232	#endif
[1421]	1233	return terminationCriteriaMet;
[1237]	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
[2347]	1244	////////////////
[1370]	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
[1237]	1257	// accumulate depth to compute average depth
	1258	mBvhStats.accumDepth += data.mDepth;
[1370]	1259
	1260
[2347]	1261	//////////////////////
[1370]	1262	// objects related stuff
	1263
[1698]	1264	// note: the sum should alwaysbe total number of objects for bvh
[1370]	1265	mBvhStats.objectRefs += (int)leaf->mObjects.size();
	1266
	1267	if ((int)leaf->mObjects.size() <= mTermMinObjects)
	1268	{
[1288]	1269	++ mBvhStats.minObjectsNodes;
[1370]	1270	}
	1271
[1408]	1272	if (leaf->mObjects.empty())
	1273	{
	1274	++ mBvhStats.emptyNodes;
	1275	}
	1276
[1370]	1277	if ((int)leaf->mObjects.size() > mBvhStats.maxObjectRefs)
	1278	{
[1237]	1279	mBvhStats.maxObjectRefs = (int)leaf->mObjects.size();
[1370]	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
[1705]	1308	#ifdef _DEBUG
[2347]	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;
[1415]	1312	#endif
[1237]	1313	}
	1314
	1315
[2003]	1316	#if 1
[1370]	1317
	1318	/// compute object boundaries using spatial mid split
[1287]	1319	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
	1320	const int axis,
	1321	ObjectContainer &objectsFront,
	1322	ObjectContainer &objectsBack)
[1237]	1323	{
[2003]	1324	AxisAlignedBox3 parentBox = tData.mNode->GetBoundingBox();
[1237]	1325
[2003]	1326	const float maxBox = parentBox.Max(axis);
	1327	const float minBox = parentBox.Min(axis);
	1328
[1287]	1329	float midPoint = (maxBox + minBox) * 0.5f;
	1330
	1331	ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
[1237]	1332
[1287]	1333	for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
	1334	{
	1335	Intersectable obj = oit;
[1297]	1336	const AxisAlignedBox3 box = obj->GetBox();
[1291]	1337
[1294]	1338	const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5f;
[1291]	1339
[1287]	1340	// object mailed => belongs to back objects
	1341	if (objMid < midPoint)
[1370]	1342	{
[1287]	1343	objectsBack.push_back(obj);
[1370]	1344	}
[1287]	1345	else
[1370]	1346	{
[1287]	1347	objectsFront.push_back(obj);
[1370]	1348	}
[1287]	1349	}
[1237]	1350
[2003]	1351	AxisAlignedBox3 fbox = EvalBoundingBox(objectsFront, &parentBox);
	1352	AxisAlignedBox3 bbox = EvalBoundingBox(objectsBack, &parentBox);
[1237]	1353
[2003]	1354	const float oldRenderCost = (float)tData.mNode->mObjects.size() * parentBox.SurfaceArea();
[2347]	1355	const float newRenderCost = (float)objectsFront.size() * fbox.SurfaceArea() + (float)objectsBack.size() * bbox.SurfaceArea();
[2003]	1356
[1287]	1357	const float ratio = newRenderCost / oldRenderCost;
	1358	return ratio;
	1359	}
[1237]	1360
[1297]	1361	#else
[1237]	1362
[1370]	1363	/// compute object partition by getting balanced objects on the left and right side
[1297]	1364	float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
	1365	const int axis,
	1366	ObjectContainer &objectsFront,
	1367	ObjectContainer &objectsBack)
	1368	{
[1357]	1369	PrepareLocalSubdivisionCandidates(tData, axis);
[1297]	1370
[1357]	1371	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
[1297]	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)
[1379]	1382	{
[1297]	1383	objectsBack.push_back(obj);
[1379]	1384	}
[1297]	1385	else
[1379]	1386	{
[1297]	1387	objectsFront.push_back(obj);
[1379]	1388	}
[1297]	1389	}
	1390
[1705]	1391	#if 1
[2003]	1392	// hack: always take driving axis
[1705]	1393	const float cost = (tData.mNode->GetBoundingBox().Size().DrivingAxis() == axis) ? -1.0f : 0.0f;
	1394	#else
[2210]	1395	const float oldRenderCost = EvalAbsCost(tData.mLeaf->mObjects) / EvalProbability(tData.mSampledObjects);
[2003]	1396	const float newRenderCost = EvalRenderCost(objectsFront) + EvalRenderCost(objectsBack);
[1297]	1397
[1705]	1398	const float cost = newRenderCost / oldRenderCost;
	1399	#endif
[1703]	1400
[1705]	1401	return cost;
[1297]	1402	}
	1403	#endif
	1404
	1405
[1323]	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:
[1698]	1413	// C = ct_div_ci + (ol + or) / queries
[1379]	1414	PrepareLocalSubdivisionCandidates(tData, axis);
	1415
[2332]	1416	const float totalRenderCost = (float)tData.mNode->mObjects.size();
[1698]	1417	float objectsLeft = 0, objectsRight = totalRenderCost;
[1323]	1418
[1662]	1419	const AxisAlignedBox3 nodeBbox = tData.mNode->GetBoundingBox();
	1420	const float boxArea = nodeBbox.SurfaceArea();
[1323]	1421
	1422	float minSum = 1e20f;
	1423
[1718]	1424	float minBorder = nodeBbox.Max(axis);
	1425	float maxBorder = nodeBbox.Min(axis);
[1723]	1426
[1379]	1427	float areaLeft = 0, areaRight = 0;
[1323]	1428
[1357]	1429	SortableEntryContainer::const_iterator currentPos =
[1323]	1430	mSubdivisionCandidates->begin();
[1379]	1431
	1432	vector<float> bordersRight;
	1433
[1718]	1434	// we keep track of both borders of the bounding boxes =>
	1435	// store the events in descending order
[1662]	1436
[1718]	1437	bordersRight.resize(mSubdivisionCandidates->size());
[1662]	1438
[1718]	1439	SortableEntryContainer::reverse_iterator rcit =
[2198]	1440	mSubdivisionCandidates->rbegin(), rcit_end = mSubdivisionCandidates->rend();
[1323]	1441
[1718]	1442	vector<float>::reverse_iterator rbit = bordersRight.rbegin();
[1662]	1443
[1718]	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);
[1379]	1452	}
[1718]	1453
	1454	(*rbit) = minBorder;
[1323]	1455	}
	1456
[2003]	1457	// record surface areas during the sweep
[1662]	1458	float al = 0;
	1459	float ar = boxArea;
	1460
[1323]	1461	vector<float>::const_iterator bit = bordersRight.begin();
[1357]	1462	SortableEntryContainer::const_iterator cit, cit_end = mSubdivisionCandidates->end();
[1379]	1463
[1323]	1464	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
	1465	{
	1466	Intersectable obj = (cit).mObject;
	1467
[2199]	1468	++ objectsLeft;
	1469	-- objectsRight;
	1470
[2332]	1471	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
[1323]	1472	const AxisAlignedBox3 obox = obj->GetBox();
	1473
[1718]	1474	// the borders of the bounding boxes have changed
	1475	if (obox.Max(axis) > maxBorder)
[1379]	1476	{
[1718]	1477	maxBorder = obox.Max(axis);
	1478	}
[1323]	1479
[1718]	1480	minBorder = (*bit);
[1662]	1481
[1718]	1482	AxisAlignedBox3 lbox = nodeBbox;
	1483	AxisAlignedBox3 rbox = nodeBbox;
[1379]	1484
[1718]	1485	lbox.SetMax(axis, maxBorder);
	1486	rbox.SetMin(axis, minBorder);
[1662]	1487
[1718]	1488	al = lbox.SurfaceArea();
	1489	ar = rbox.SurfaceArea();
	1490
[2228]	1491	// should use classical approach here ...
[2227]	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;
[2238]	1497	#else
[2227]	1498
[2238]	1499	const float sum = noValidSplit ? 1e25f : objectsLeft * al + objectsRight * ar;
[2227]	1500	#endif
[1705]	1501
[1323]	1502	if (sum < minSum)
[1717]	1503	{
[1379]	1504	minSum = sum;
	1505	areaLeft = al;
	1506	areaRight = ar;
[1698]	1507
[1370]	1508	// objects belong to left side now
[1323]	1509	for (; currentPos != (cit + 1); ++ currentPos);
	1510	}
	1511	}
	1512
[1717]	1513	////////////
[1323]	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;
[1698]	1525	float ratio = newCost / totalRenderCost;
[1323]	1526
[1717]	1527	#ifdef GTP_DEBUG
[2347]	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;
[1713]	1532	#endif
	1533
	1534	return ratio;
	1535	}
[1717]	1536
[1713]	1537
[2227]	1538
	1539	float BvHierarchy::EvalSahWithTigherBbox(const BvhTraversalData &tData,
	1540	const int axis,
	1541	ObjectContainer &objectsFront,
	1542	ObjectContainer &objectsBack)
[1713]	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
[2332]	1549	const float totalRenderCost = (float)tData.mNode->mObjects.size();
[1713]	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
[1717]	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)
[1713]	1581	{
[1717]	1582	Intersectable obj = (rcit).mObject;
	1583	const AxisAlignedBox3 obox = obj->GetBox();
[1713]	1584
[1717]	1585	for (int i = 0; i < 3; ++ i)
[1713]	1586	{
[1717]	1587	if (obox.Min(i) < minBorder[i])
[1713]	1588	{
[1717]	1589	minBorder[i] = obox.Min(i);
[1713]	1590	}
	1591	}
[1717]	1592
	1593	(*rbit) = minBorder;
[1713]	1594	}
	1595
	1596	// temporary surface areas
	1597	float al = 0;
	1598	float ar = boxArea;
	1599
	1600	vector<Vector3>::const_iterator bit = bordersRight.begin();
[1717]	1601	SortableEntryContainer::const_iterator cit, cit_end =
	1602	mSubdivisionCandidates->end();
[1713]	1603
	1604	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit, ++ bit)
	1605	{
	1606	Intersectable obj = (cit).mObject;
	1607
[2332]	1608	objectsLeft ++;;
	1609	objectsRight --;
[1713]	1610
	1611	const AxisAlignedBox3 obox = obj->GetBox();
	1612
[1717]	1613	AxisAlignedBox3 lbox = nodeBbox;
	1614	AxisAlignedBox3 rbox = nodeBbox;
[1713]	1615
[1718]	1616	// the borders of the left bounding box have changed
[1717]	1617	for (int i = 0; i < 3; ++ i)
	1618	{
	1619	if (obox.Max(i) > maxBorder[i])
[1713]	1620	{
[1717]	1621	maxBorder[i] = obox.Max(i);
[1713]	1622	}
	1623	}
	1624
[1717]	1625	minBorder = (*bit);
[1713]	1626
[1717]	1627	lbox.SetMax(maxBorder);
	1628	rbox.SetMin(minBorder);
	1629
	1630	al = lbox.SurfaceArea();
	1631	ar = rbox.SurfaceArea();
	1632
[1713]	1633	const bool noValidSplit = ((objectsLeft <= Limits::Small) \|\| (objectsRight <= Limits::Small));
[2332]	1634	const float sum = noValidSplit ? 1e25f : objectsLeft * al + objectsRight * ar;
[1713]	1635
	1636	if (sum < minSum)
[1717]	1637	{
[1713]	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
[1717]	1647	/////////////
[1713]	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
[1715]	1661	#ifdef GTP_DEBUG
[2347]	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;
[1323]	1666	#endif
[1664]	1667
[1713]	1668	return ratio;
[1323]	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
[1717]	1693	static void PrintHeuristics(const float objectsRight,
[1323]	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
[1287]	1717	float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
	1718	const int axis,
	1719	ObjectContainer &objectsFront,
	1720	ObjectContainer &objectsBack)
	1721	{
[2347]	1722	////////
	1723	// traverse split candidates, count the number of objects
	1724	// left and right and evaluate the cost funcion
[1237]	1725
[2332]	1726	// prepare the heuristics, set mailboxes and counters
[1357]	1727	const float totalVol = PrepareHeuristics(tData, axis);
	1728
[1287]	1729	// local helper variables
	1730	float volLeft = 0;
	1731	float volRight = totalVol;
[1698]	1732
[2332]	1733	const float nTotalObjects = (float)tData.mNode->mObjects.size();
[1698]	1734	float nObjectsLeft = 0;
	1735	float nObjectsRight = nTotalObjects;
	1736
[1779]	1737	const float viewSpaceVol =
	1738	mViewCellsManager->GetViewSpaceBox().GetVolume();
[1237]	1739
[1624]	1740	SortableEntryContainer::const_iterator backObjectsStart =
	1741	mSubdivisionCandidates->begin();
[1287]	1742
[1237]	1743	/////////////////////////////////
[1357]	1744	//-- the parameters for the current optimum
[1237]	1745
[1287]	1746	float volBack = volLeft;
	1747	float volFront = volRight;
	1748	float newRenderCost = nTotalObjects * totalVol;
[1237]	1749
[1715]	1750	#ifdef GTP_DEBUG
[1314]	1751	ofstream sumStats;
	1752	ofstream vollStats;
	1753	ofstream volrStats;
[1237]	1754
[1778]	1755	const bool printStats = PrepareOutput(axis,
	1756	mBvhStats.Leaves(),
	1757	sumStats,
	1758	vollStats,
	1759	volrStats);
[1314]	1760	#endif
	1761
[1727]	1762	///////////////////////
[1357]	1763	//-- the sweep heuristics
[1237]	1764	//-- traverse through events and find best split plane
	1765
[1698]	1766	SortableEntryContainer::const_iterator cit,
	1767	cit_end = cit_end = mSubdivisionCandidates->end();
[1287]	1768
	1769	for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
[1237]	1770	{
[1287]	1771	Intersectable object = (cit).mObject;
[1370]	1772
[1287]	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);
[1237]	1777
[2199]	1778	++ nObjectsLeft;
	1779	-- nObjectsRight;
[2210]	1780
[2199]	1781	// split is only valid if #objects on left and right is not zero
[2210]	1782	const bool noValidSplit = (nObjectsRight <= Limits::Small);
[2199]	1783
[1287]	1784	// the heuristics
[1705]	1785	const float sum = noValidSplit ?
[2238]	1786	1e25f : volLeft * (float)nObjectsLeft + volRight * (float)nObjectsRight;
[2332]	1787
[2227]	1788
[1715]	1789	#ifdef GTP_DEBUG
[1314]	1790	if (printStats)
[1357]	1791	{
[2199]	1792	PrintHeuristics(nObjectsRight, sum, volLeft,
	1793	volRight, viewSpaceVol,
[1323]	1794	sumStats, vollStats, volrStats);
[1357]	1795	}
[1314]	1796	#endif
	1797
[1287]	1798	if (sum < newRenderCost)
[1237]	1799	{
[1287]	1800	newRenderCost = sum;
[1237]	1801
[1287]	1802	volBack = volLeft;
	1803	volFront = volRight;
[1237]	1804
[1287]	1805	// objects belongs to left side now
[1357]	1806	for (; backObjectsStart != (cit + 1); ++ backObjectsStart);
[1237]	1807	}
	1808	}
	1809
[1779]	1810	////////////////////////////////////////
[1287]	1811	//-- assign object to front and back volume
[1237]	1812
[1287]	1813	// belongs to back bv
[1357]	1814	for (cit = mSubdivisionCandidates->begin(); cit != backObjectsStart; ++ cit)
	1815	{
[1287]	1816	objectsBack.push_back((*cit).mObject);
[1357]	1817	}
[1287]	1818	// belongs to front bv
[1357]	1819	for (cit = backObjectsStart; cit != cit_end; ++ cit)
	1820	{
[1287]	1821	objectsFront.push_back((*cit).mObject);
[1357]	1822	}
[1237]	1823
[1357]	1824	// render cost of the old parent
[1287]	1825	const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
	1826	// the relative cost ratio
	1827	const float ratio = newRenderCost / oldRenderCost;
	1828
[1715]	1829	#ifdef GTP_DEBUG
[2347]	1830	Debug << "\neval bvh split cost decrease" << endl
[1703]	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;
[1654]	1839	#endif
[1237]	1840
	1841	return ratio;
	1842	}
	1843
	1844
[1357]	1845	void BvHierarchy::PrepareLocalSubdivisionCandidates(const BvhTraversalData &tData,
	1846	const int axis)
[2199]	1847	{
	1848	mSortTimer.Entry();
	1849
[1357]	1850	//-- insert object queries
[1692]	1851	ObjectContainer *objects = mUseGlobalSorting ?
	1852	tData.mSortedObjects[axis] : &tData.mNode->mObjects;
[1357]	1853
[1370]	1854	CreateLocalSubdivisionCandidates(*objects, &mSubdivisionCandidates, !mUseGlobalSorting, axis);
[2199]	1855
	1856	mSortTimer.Exit();
[1357]	1857	}
	1858
	1859
	1860	void BvHierarchy::CreateLocalSubdivisionCandidates(const ObjectContainer &objects,
	1861	SortableEntryContainer **subdivisionCandidates,
[2003]	1862	const bool sortEntries,
[1357]	1863	const int axis)
	1864	{
[1345]	1865	(*subdivisionCandidates)->clear();
[1237]	1866
[1357]	1867	// compute requested size and look if subdivision candidate has to be recomputed
[2003]	1868	const int requestedSize = (int)objects.size();
[1237]	1869
	1870	// creates a sorted split candidates array
[1345]	1871	if ((*subdivisionCandidates)->capacity() > 500000 &&
	1872	requestedSize < (int)((*subdivisionCandidates)->capacity() / 10) )
[1237]	1873	{
[1357]	1874	delete (*subdivisionCandidates);
	1875	(*subdivisionCandidates) = new SortableEntryContainer;
[1237]	1876	}
	1877
[1345]	1878	(*subdivisionCandidates)->reserve(requestedSize);
[1237]	1879
[1345]	1880	ObjectContainer::const_iterator oit, oit_end = objects.end();
[1287]	1881
[1345]	1882	for (oit = objects.begin(); oit < oit_end; ++ oit)
[1237]	1883	{
[2199]	1884	(subdivisionCandidates)->push_back(SortableEntry(oit, (*oit)->GetBox().Center(axis)));
[1237]	1885	}
	1886
[2003]	1887	if (sortEntries)
[1580]	1888	{ // no presorted candidate list
[2124]	1889	stable_sort((subdivisionCandidates)->begin(), (subdivisionCandidates)->end());
	1890	//sort((subdivisionCandidates)->begin(), (subdivisionCandidates)->end());
[1357]	1891	}
[1237]	1892	}
	1893
	1894
	1895	const BvhStatistics &BvHierarchy::GetStatistics() const
	1896	{
	1897	return mBvhStats;
	1898	}
	1899
	1900
[1727]	1901	float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData,
	1902	const int axis)
[1287]	1903	{
[1323]	1904	BvhLeaf *leaf = tData.mNode;
	1905	float vol = 0;
	1906
[1357]	1907	// sort so we can use a sweep from right to left
	1908	PrepareLocalSubdivisionCandidates(tData, axis);
	1909
[1287]	1910	// collect and mark the view cells as belonging to front pvs
	1911	ViewCellContainer viewCells;
[1778]	1912
[2198]	1913	const bool setCounter = true;
	1914	const bool onlyUnmailed = true;
	1915
[2199]	1916
[2210]	1917	CollectViewCells(*tData.mSampledObjects,
[2199]	1918	viewCells,
	1919	setCounter,
	1920	onlyUnmailed);
[2198]	1921
[2199]	1922	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1778]	1923
[1287]	1924	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	1925	{
[1662]	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;
[1287]	1932	}
	1933
[2199]	1934	// mail view cells that go from front node to back node
[1287]	1935	ViewCell::NewMail();
[1323]	1936
[1287]	1937	return vol;
	1938	}
[1576]	1939
[2347]	1940
	1941
[1287]	1942	///////////////////////////////////////////////////////////
	1943
	1944
[2347]	1945	void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
[1287]	1946	float &volLeft,
	1947	float &volRight)
[1237]	1948	{
[1287]	1949	// collect all view cells associated with this objects
	1950	// (also multiple times, if they are pierced by several rays)
[1237]	1951	ViewCellContainer viewCells;
[2199]	1952
[1287]	1953	const bool useMailboxing = false;
[2199]	1954	const bool setCounter = false;
	1955	const bool onlyUnmailedRays = true;
[1323]	1956
[2199]	1957	CollectViewCells(obj, viewCells, useMailboxing, setCounter, onlyUnmailedRays);
[1237]	1958
[1357]	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
[1237]	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;
[2199]	1970
[1662]	1971	#if USE_VOLUMES_FOR_HEURISTICS
[1237]	1972	const float vol = viewCell->GetVolume();
[1662]	1973	#else
	1974	const float vol = 1.0f;
	1975	#endif
[1237]	1976	if (!viewCell->Mailed())
	1977	{
	1978	viewCell->Mail();
	1979	// we now see view cell from both nodes
[1287]	1980	// => add volume to left node
	1981	volLeft += vol;
[1237]	1982	}
	1983
	1984	// last reference into the right node
	1985	if (-- viewCell->mCounter == 0)
[1357]	1986	{
[1237]	1987	// view cell was previously seen from both nodes =>
[1287]	1988	// remove volume from right node
	1989	volRight -= vol;
[1237]	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,
[1676]	2009	ObjectContainer &backObjects,
	2010	bool useVisibilityBasedHeuristics)
[1237]	2011	{
[2187]	2012	mSplitTimer.Entry();
	2013
[1779]	2014	if (mIsInitialSubdivision)
	2015	{
[1784]	2016	ApplyInitialSplit(tData, frontObjects, backObjects);
[1779]	2017	return 0;
	2018	}
	2019
[1237]	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	{
[1370]	2029	const AxisAlignedBox3 box = tData.mNode->GetBoundingBox();
[1237]	2030	sAxis = box.Size().DrivingAxis();
	2031	}
[1770]	2032
[2347]	2033	// if #rays high, consider only use a subset of the rays for
[1941]	2034	// visibility based heuristics
	2035	VssRay::NewMail();
	2036
	2037
[1580]	2038	////////////////////////////////////
[1357]	2039	//-- evaluate split cost for all three axis
[1237]	2040
	2041	for (int axis = 0; axis < 3; ++ axis)
	2042	{
	2043	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
	2044	{
[1287]	2045	if (mUseCostHeuristics)
[1298]	2046	{
[1370]	2047	//////////////////////////////////
	2048	//-- split objects using heuristics
	2049
[1676]	2050	if (useVisibilityBasedHeuristics)
[1370]	2051	{
[1634]	2052	///////////
[1370]	2053	//-- heuristics using objects weighted by view cells volume
	2054	nCostRatio[axis] =
[1703]	2055	EvalLocalCostHeuristics(tData,
	2056	axis,
	2057	nFrontObjects[axis],
	2058	nBackObjects[axis]);
[1370]	2059	}
	2060	else
[1744]	2061	{
[1580]	2062	//////////////////
	2063	//-- view cells not constructed yet => use surface area heuristic
[1703]	2064	nCostRatio[axis] = EvalSah(tData,
	2065	axis,
	2066	nFrontObjects[axis],
	2067	nBackObjects[axis]);
[1370]	2068	}
[1237]	2069	}
[1287]	2070	else
[1298]	2071	{
[1370]	2072	//-- split objects using some simple criteria
[1287]	2073	nCostRatio[axis] =
[1679]	2074	EvalLocalObjectPartition(tData, axis, nFrontObjects[axis], nBackObjects[axis]);
[1287]	2075	}
	2076
[2224]	2077	// avoid splits in degenerate axis with high penalty
[1827]	2078	if (1 &&
	2079	(tData.mNode->GetBoundingBox().Size(axis) < 0.0001))//Limits::Small))
[1811]	2080	{
	2081	nCostRatio[axis] += 9999;
	2082	}
[1789]	2083
[1703]	2084	if ((bestAxis == -1) \|\| (nCostRatio[axis] < nCostRatio[bestAxis]))
[1237]	2085	{
	2086	bestAxis = axis;
	2087	}
	2088	}
	2089	}
	2090
[1580]	2091	////////////////
[1237]	2092	//-- assign values
[1287]	2093
[1237]	2094	frontObjects = nFrontObjects[bestAxis];
[1287]	2095	backObjects = nBackObjects[bestAxis];
[1237]	2096
[2187]	2097	mSplitTimer.Exit();
	2098
[1703]	2099	//cout << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1237]	2100	return nCostRatio[bestAxis];
	2101	}
	2102
	2103
[1370]	2104	int BvHierarchy::AssociateObjectsWithRays(const VssRayContainer &rays) const
[1237]	2105	{
[1370]	2106	int nRays = 0;
[1237]	2107	VssRayContainer::const_iterator rit, rit_end = rays.end();
	2108
[2238]	2109	VssRay *lastVssRay = NULL;
	2110
[1370]	2111	VssRay::NewMail();
	2112
[1237]	2113	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2114	{
	2115	VssRay ray = (rit);
	2116
[2239]	2117	// filter out double rays (last ray the same as this ray)
	2118	if (
	2119	!lastVssRay \|\|
[2238]	2120	!(ray->mOrigin == lastVssRay->mTermination) \|\|
	2121	!(ray->mTermination == lastVssRay->mOrigin))
[1237]	2122	{
[2239]	2123	lastVssRay = ray;
[2238]	2124	//cout << "j";
	2125	if (ray->mTerminationObject)
[1370]	2126	{
[2238]	2127	ray->mTerminationObject->GetOrCreateRays()->push_back(ray);
	2128	if (!ray->Mailed())
	2129	{
	2130	ray->Mail();
	2131	++ nRays;
	2132	}
[1370]	2133	}
[1765]	2134
[1649]	2135	#if COUNT_ORIGIN_OBJECTS
[1765]	2136
[2238]	2137	if (ray->mOriginObject)
	2138	{
	2139	//cout << "o";
	2140	ray->mOriginObject->GetOrCreateRays()->push_back(ray);
[1370]	2141
[2238]	2142	if (!ray->Mailed())
	2143	{
	2144	ray->Mail();
	2145	++ nRays;
	2146	}
[1370]	2147	}
[2255]	2148	#endif
[1237]	2149	}
	2150	}
[1370]	2151
	2152	return nRays;
[1237]	2153	}
	2154
	2155
[1287]	2156	void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
[1237]	2157	{
[1709]	2158	const float costDecr = sc.GetRenderCostDecrease();
[1237]	2159
	2160	mSubdivisionStats
[1421]	2161	<< "#Leaves\n" << mBvhStats.Leaves() << endl
[1287]	2162	<< "#RenderCostDecrease\n" << costDecr << endl
[1662]	2163	<< "#TotalRenderCost\n" << mTotalCost << endl
	2164	<< "#EntriesInPvs\n" << mPvsEntries << endl;
[1237]	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;
[1696]	2179	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
[1237]	2180
[1696]	2181	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
[1237]	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
[1779]	2195	float BvHierarchy::EvalSahCost(BvhLeaf *leaf) const
[1705]	2196	{
	2197	////////////////
	2198	//-- surface area heuristics
[1911]	2199
[1705]	2200	const AxisAlignedBox3 box = GetBoundingBox(leaf);
	2201	const float area = box.SurfaceArea();
	2202	const float viewSpaceArea = mViewCellsManager->GetViewSpaceBox().SurfaceArea();
	2203
[2332]	2204	return (float)leaf->mObjects.size() * area / viewSpaceArea;
[1705]	2205	}
	2206
	2207
[2198]	2208	float BvHierarchy::EvalRenderCost(const ObjectContainer &objects)// const
[1698]	2209	{
	2210	///////////////
	2211	//-- render cost heuristics
[2227]	2212
[2332]	2213	const float objRenderCost = (float)objects.size();
[1379]	2214
[1698]	2215	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
[1379]	2216
[1698]	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;
[1287]	2221	}
	2222
	2223
[2210]	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
[1405]	2233	AxisAlignedBox3 BvHierarchy::EvalBoundingBox(const ObjectContainer &objects,
	2234	const AxisAlignedBox3 *parentBox) const
[1237]	2235	{
[1405]	2236	// if there are no objects in this box, box size is set to parent box size.
	2237	// Question: Invalidate box instead?
[1287]	2238	if (parentBox && objects.empty())
	2239	return *parentBox;
	2240
[1237]	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;
[1370]	2249	// grow bounding box to include all objects
[1287]	2250	box.Include(obj->GetBox());
[1237]	2251	}
[1287]	2252
[1237]	2253	return box;
	2254	}
	2255
	2256
[1707]	2257	void BvHierarchy::CollectLeaves(BvhNode root, vector<BvhLeaf > &leaves) const
[1237]	2258	{
	2259	stack<BvhNode *> nodeStack;
[1707]	2260	nodeStack.push(root);
[1237]	2261
	2262	while (!nodeStack.empty())
	2263	{
	2264	BvhNode *node = nodeStack.top();
	2265	nodeStack.pop();
[1287]	2266
[1237]	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
[2093]	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
[1237]	2306	AxisAlignedBox3 BvHierarchy::GetBoundingBox(BvhNode *node) const
	2307	{
	2308	return node->GetBoundingBox();
	2309	}
	2310
	2311
[2210]	2312	int BvHierarchy::CollectViewCells(const ObjectContainer &objects,
	2313	ViewCellContainer &viewCells,
	2314	const bool setCounter,
	2315	const bool onlyUnmailedRays)// const
	2316	{
	2317	ViewCell::NewMail();
[2198]	2318
[2210]	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
[2198]	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
[2210]	2350	void BvHierarchy::AssociateViewCellsWithObjects(const ObjectContainer &objects) const
[2198]	2351	{
	2352	ObjectContainer::const_iterator oit, oit_end = objects.end();
	2353
	2354	const bool useMailBoxing = true;
[2210]	2355	VssRay::NewMail();
[2206]	2356
[2198]	2357	for (oit = objects.begin(); oit != oit_end; ++ oit)
	2358	{
[2206]	2359	ViewCell::NewMail();
	2360	// use mailing to avoid duplicates
	2361	AssociateViewCellsWithObject(*oit, useMailBoxing);
[2198]	2362	}
	2363	}
	2364
	2365
	2366	int BvHierarchy::AssociateViewCellsWithObject(Intersectable *obj, const bool useMailBoxing) const
	2367	{
[2210]	2368	int nRays = 0;
	2369
[2198]	2370	if (!obj->GetOrCreateViewCells()->empty())
	2371	{
[2210]	2372	cerr << "AssociateViewCellsWithObject: view cells cache not working" << endl;
[2198]	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);
[2210]	2388
	2389	if (!useMailBoxing \|\| !ray->Mailed())
	2390	{
	2391	if (useMailBoxing)
	2392	ray->Mail();
	2393
	2394	++ nRays;
	2395	}
[2198]	2396	}
	2397
[2210]	2398	return nRays;
[2198]	2399	}
	2400
	2401
	2402
	2403	int BvHierarchy::CountViewCells(Intersectable *obj) //const
	2404	{
	2405	ViewCellContainer *viewCells = obj->GetOrCreateViewCells();
	2406
	2407	if (obj->GetOrCreateViewCells()->empty())
	2408	{
[2210]	2409	//cerr << "h";//CountViewCells: view cells empty, view cells cache not working" << endl;
[2198]	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
[1744]	2433	int BvHierarchy::CollectViewCells(Intersectable *obj,
	2434	ViewCellContainer &viewCells,
	2435	const bool useMailBoxing,
	2436	const bool setCounter,
[2198]	2437	const bool onlyUnmailedRays)// const
[1237]	2438	{
[2342]	2439	// view cells not cached
[2198]	2440	if (obj->GetOrCreateViewCells()->empty())
	2441	{
	2442	return CollectViewCellsFromRays(obj, viewCells, useMailBoxing, setCounter, onlyUnmailedRays);
	2443	}
	2444
[2342]	2445	///////////
	2446	//-- use view cells cache
	2447
[2198]	2448	mCollectTimer.Entry();
	2449
	2450	ViewCellContainer *objViewCells = obj->GetOrCreateViewCells();
	2451
	2452	// loop through view cells
[2342]	2453	// matt: probably slow to insert view cells one by one
[2198]	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();
[1696]	2493	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
[1237]	2494
[1744]	2495	int numRays = 0;
	2496
[1696]	2497	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
[1237]	2498	{
	2499	VssRay ray = (rit);
[1727]	2500
[1941]	2501	if (onlyUnmailedRays && ray->Mailed())
[1727]	2502	continue;
[2198]	2503
[1744]	2504	++ numRays;
[1727]	2505
[1287]	2506	ViewCellContainer tmpViewCells;
[1379]	2507	mHierarchyManager->mVspTree->GetViewCells(*ray, tmpViewCells);
[1237]	2508
[1640]	2509	// matt: probably slow to allocate memory for view cells every time
[1237]	2510	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
	2511
	2512	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
	2513	{
[1576]	2514	ViewCell vc = vit;
[1237]	2515
[1287]	2516	// store view cells
	2517	if (!useMailBoxing \|\| !vc->Mailed())
[1237]	2518	{
[1903]	2519	if (useMailBoxing) // => view cell not mailed
[1287]	2520	{
	2521	vc->Mail();
	2522	if (setCounter)
	2523	vc->mCounter = 0;
	2524	}
[1903]	2525
[1237]	2526	viewCells.push_back(vc);
	2527	}
[1287]	2528
	2529	if (setCounter)
	2530	++ vc->mCounter;
[1237]	2531	}
	2532	}
[1744]	2533
[2198]	2534	mCollectTimer.Exit();
[1744]	2535	return numRays;
[1287]	2536	}
[1237]	2537
	2538
[2198]	2539	int BvHierarchy::CountViewCellsFromRays(Intersectable *obj) //const
[1576]	2540	{
	2541	int result = 0;
	2542
[1696]	2543	VssRayContainer::const_iterator rit, rit_end = obj->GetOrCreateRays()->end();
[1576]	2544
[1696]	2545	for (rit = obj->GetOrCreateRays()->begin(); rit < rit_end; ++ rit)
[1576]	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
[2198]	2569	#else
[1576]	2570
[2198]	2571	int BvHierarchy::CountViewCells(Intersectable *obj) //const
[1576]	2572	{
[2198]	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
[2210]	2656	int BvHierarchy::CountViewCells(const ObjectContainer &objects)// const
	2657	{
	2658	int nViewCells = 0;
[2198]	2659
[2210]	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
[1287]	2673	void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
[1633]	2674	vector<SubdivisionCandidate *> &dirtyList,
	2675	const bool onlyUnmailed)
[1287]	2676	{
	2677	BvhTraversalData &tData = sc->mParentData;
	2678	BvhLeaf *node = tData.mNode;
	2679
	2680	ViewCellContainer viewCells;
[1904]	2681	//ViewCell::NewMail();
[2210]	2682	int numRays = CollectViewCells(*tData.mSampledObjects, viewCells, false, false);
[1633]	2683
[1415]	2684	if (0) cout << "collected " << (int)viewCells.size() << " dirty candidates" << endl;
[1633]	2685
[1287]	2686	// split candidates handling
	2687	// these view cells are thrown into dirty list
[1237]	2688	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	2689
	2690	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	2691	{
[2017]	2692	VspViewCell vc = static_cast<VspViewCell >(*vit);
[1551]	2693	VspLeaf *leaf = vc->mLeaves[0];
[1633]	2694
[1297]	2695	SubdivisionCandidate *candidate = leaf->GetSubdivisionCandidate();
	2696
[1633]	2697	// is this leaf still a split candidate?
	2698	if (candidate && (!onlyUnmailed \|\| !candidate->Mailed()))
[1305]	2699	{
[1633]	2700	candidate->Mail();
[1733]	2701	candidate->SetDirty(true);
[1305]	2702	dirtyList.push_back(candidate);
	2703	}
[1237]	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
[2210]	2730	#if 0
[1237]	2731	BvhLeaf BvHierarchy::GetLeaf(Intersectable object, BvhNode *node) const
	2732	{
[2210]	2733	// hack: we use the simpler but faster version
[1680]	2734	if (!object)
	2735	return NULL;
[2210]	2736
[1297]	2737	return object->mBvhLeaf;
	2738
[1237]	2739	///////////////////////////////////////
	2740	// start from root of tree
[2224]	2741
[1237]	2742	if (node == NULL)
	2743	node = mRoot;
[1297]	2744
[1237]	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	{
[2017]	2759	leaf = static_cast<BvhLeaf *>(node);
[1237]	2760
	2761	if (IsObjectInLeaf(leaf, object))
[1293]	2762	{
[1237]	2763	return leaf;
[1293]	2764	}
[1237]	2765	}
	2766	else
	2767	{
	2768	// find point
[2017]	2769	BvhInterior interior = static_cast<BvhInterior >(node);
[1237]	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	}
[2210]	2786	#endif
[1237]	2787
	2788	bool BvHierarchy::Export(OUT_STREAM &stream)
	2789	{
	2790	ExportNode(mRoot, stream);
	2791
	2792	return true;
	2793	}
	2794
	2795
[1286]	2796	void BvHierarchy::ExportObjects(BvhLeaf *leaf, OUT_STREAM &stream)
	2797	{
	2798	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1923]	2799
[1286]	2800	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	2801	{
	2802	stream << (*oit)->GetId() << " ";
	2803	}
	2804	}
	2805
	2806
[1237]	2807	void BvHierarchy::ExportNode(BvhNode *node, OUT_STREAM &stream)
	2808	{
	2809	if (node->IsLeaf())
	2810	{
[2017]	2811	BvhLeaf leaf = static_cast<BvhLeaf >(node);
[1287]	2812	const AxisAlignedBox3 box = leaf->GetBoundingBox();
[2048]	2813	stream << "<Leaf id=\"" << node->GetId() << "\""
[1287]	2814	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	2815	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
[1286]	2816	<< " objects=\"";
[1237]	2817
[1286]	2818	//-- export objects
[1843]	2819	// tmp matt
[1922]	2820	if (1) ExportObjects(leaf, stream);
[1237]	2821
	2822	stream << "\" />" << endl;
	2823	}
	2824	else
	2825	{
[2017]	2826	BvhInterior interior = static_cast<BvhInterior >(node);
[1287]	2827	const AxisAlignedBox3 box = interior->GetBoundingBox();
	2828
[2048]	2829	stream << "<Interior id=\"" << node->GetId() << "\""
[1287]	2830	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	2831	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
[1286]	2832	<< "\">" << endl;
[1237]	2833
	2834	ExportNode(interior->GetBack(), stream);
	2835	ExportNode(interior->GetFront(), stream);
	2836
	2837	stream << "</Interior>" << endl;
	2838	}
	2839	}
	2840
	2841
[2198]	2842	float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects)// const
[1237]	2843	{
	2844	float vol = 0;
	2845
[1287]	2846	ViewCellContainer viewCells;
[1744]	2847
	2848	// we have to account for all view cells that can
[1727]	2849	// be seen from the objects
[1744]	2850	int numRays = CollectViewCells(objects, viewCells, false, false);
[1237]	2851
[1287]	2852	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1237]	2853
[1287]	2854	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
[1237]	2855	{
[1287]	2856	vol += (*vit)->GetVolume();
[1237]	2857	}
	2858
	2859	return vol;
	2860	}
	2861
[1357]	2862
[1640]	2863	void BvHierarchy::Initialise(const ObjectContainer &objects)
[1294]	2864	{
[1698]	2865	AxisAlignedBox3 box = EvalBoundingBox(objects);
	2866
[1449]	2867	///////
[1294]	2868	//-- create new root
[1449]	2869
[1294]	2870	BvhLeaf *bvhleaf = new BvhLeaf(box, NULL, (int)objects.size());
	2871	bvhleaf->mObjects = objects;
	2872	mRoot = bvhleaf;
	2873
[1640]	2874	// compute bounding box from objects
	2875	mBoundingBox = mRoot->GetBoundingBox();
	2876
[1294]	2877	// associate root with current objects
	2878	AssociateObjectsWithLeaf(bvhleaf);
	2879	}
	2880
[1640]	2881
[2210]	2882	void BvHierarchy::StoreSampledObjects(ObjectContainer &sampledObjects, const ObjectContainer &objects)
[1404]	2883	{
[2210]	2884	ObjectContainer::const_iterator oit, oit_end = objects.end();
[1294]	2885
[2210]	2886	for (oit = objects.begin(); oit != objects.end(); ++ oit)
	2887	{
	2888	Intersectable obj = oit;
[1404]	2889
[2210]	2890	if (!obj->GetOrCreateRays()->empty())
[1404]	2891	{
[2210]	2892	sampledObjects.push_back(obj);
	2893	}
[1404]	2894	}
[2210]	2895	}
[1404]	2896
	2897
[1779]	2898	void BvHierarchy::PrepareConstruction(SplitQueue &tQueue,
	2899	const VssRayContainer &sampleRays,
	2900	const ObjectContainer &objects)
[1237]	2901	{
[1522]	2902	///////////////////////////////////////
	2903	//-- we assume that we have objects sorted by their id =>
[1404]	2904	//-- we don't have to sort them here and an binary search
	2905	//-- for identifying if a object is in a leaf.
[1421]	2906
[1308]	2907	mBvhStats.Reset();
	2908	mBvhStats.Start();
	2909	mBvhStats.nodes = 1;
[1522]	2910
[1237]	2911	// store pointer to this tree
	2912	BvhSubdivisionCandidate::sBvHierarchy = this;
[1421]	2913
[1640]	2914	// root and bounding box was already constructed
[2017]	2915	BvhLeaf bvhLeaf = static_cast<BvhLeaf >(mRoot);
[2003]	2916
[1370]	2917	// only rays intersecting objects in node are interesting
	2918	const int nRays = AssociateObjectsWithRays(sampleRays);
[1784]	2919	//cout << "using " << nRays << " of " << (int)sampleRays.size() << " rays" << endl;
[2003]	2920
[2210]	2921	ObjectContainer *sampledObjects = new ObjectContainer();
	2922	StoreSampledObjects(*sampledObjects, objects);
	2923
[2198]	2924	#if STORE_VIEWCELLS_WITH_BVH
[2210]	2925	AssociateViewCellsWithObjects(*sampledObjects);
[2198]	2926	#endif
	2927
[1914]	2928	// probability that volume is "seen" from the view cells
[2210]	2929	const float prop = EvalViewCellsVolume(*sampledObjects) / GetViewSpaceVolume();
[1914]	2930
[1288]	2931	// create bvh traversal data
[1548]	2932	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
[2017]	2933
[1357]	2934	// create sorted object lists for the first data
[2005]	2935	if (mUseGlobalSorting)
[1357]	2936	{
[1779]	2937	AssignInitialSortedObjectList(oData, objects);
[1357]	2938	}
	2939
[2210]	2940	oData.mSampledObjects = sampledObjects;
	2941
[1449]	2942	///////////////////
[1294]	2943	//-- add first candidate for object space partition
[1357]	2944
[1912]	2945	mTotalCost = EvalRenderCost(objects);
[2210]	2946	mPvsEntries = CountViewCells(*sampledObjects);
[1912]	2947
[1913]	2948	oData.mCorrectedPvs = oData.mPvs = (float)mPvsEntries;
	2949	oData.mCorrectedVolume = oData.mVolume = prop;
[1916]	2950
[1779]	2951	BvhSubdivisionCandidate *oSubdivisionCandidate =
	2952	new BvhSubdivisionCandidate(oData);
[1237]	2953
[1548]	2954	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
[1237]	2955
[2198]	2956	#if STORE_VIEWCELLS_WITH_BVH
[2210]	2957	ReleaseViewCells(*sampledObjects);
[2198]	2958	#endif
	2959
[1779]	2960	if (mApplyInitialPartition)
[1787]	2961	{
[1789]	2962	vector<SubdivisionCandidate *> candidateContainer;
	2963
	2964	mIsInitialSubdivision = true;
	2965
	2966	// evaluate priority
[2224]	2967	EvalSubdivisionCandidate(*oSubdivisionCandidate, true, true);
[1789]	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	{
[2017]	2978	BvhSubdivisionCandidate sCandidate = static_cast<BvhSubdivisionCandidate >(*cit);
[1841]	2979
[1789]	2980	// reevaluate priority
[2224]	2981	EvalSubdivisionCandidate(*sCandidate, true, true);
[1841]	2982	tQueue.Push(sCandidate);
[1789]	2983	}
[2003]	2984
	2985	cout << "size of initial bv subdivision: " << GetStatistics().Leaves() << endl;
[1779]	2986	}
	2987	else
[2003]	2988	{
[1789]	2989	// evaluate priority
[2224]	2990	EvalSubdivisionCandidate(*oSubdivisionCandidate, true, true);
[1789]	2991	PrintSubdivisionStats(*oSubdivisionCandidate);
	2992
[1779]	2993	tQueue.Push(oSubdivisionCandidate);
[2003]	2994	cout << "size of initial bv subdivision: " << GetStatistics().Leaves() << endl;
[1779]	2995	}
[1237]	2996	}
	2997
	2998
[1779]	2999	void BvHierarchy::AssignInitialSortedObjectList(BvhTraversalData &tData,
	3000	const ObjectContainer &objects)
[1357]	3001	{
[2187]	3002	const bool doSort = true;
	3003
[1357]	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	{
[1779]	3008	SortableEntryContainer *sortedObjects = new SortableEntryContainer();
[1580]	3009
[1779]	3010	CreateLocalSubdivisionCandidates(objects,
	3011	&sortedObjects,
[2187]	3012	doSort,
[1779]	3013	i);
	3014
[1580]	3015	// copy list into traversal data list
[1357]	3016	tData.mSortedObjects[i] = new ObjectContainer();
[1779]	3017	tData.mSortedObjects[i]->reserve((int)objects.size());
[1357]	3018
[1779]	3019	SortableEntryContainer::const_iterator oit, oit_end = sortedObjects->end();
[1580]	3020
[1779]	3021	for (oit = sortedObjects->begin(); oit != oit_end; ++ oit)
[1357]	3022	{
	3023	tData.mSortedObjects[i]->push_back((*oit).mObject);
	3024	}
[1779]	3025
	3026	delete sortedObjects;
[1357]	3027	}
[2017]	3028
[2210]	3029	// next sorted list: by size (for initial criteria)
[1778]	3030	tData.mSortedObjects[3] = new ObjectContainer();
[1779]	3031	tData.mSortedObjects[3]->reserve((int)objects.size());
[1778]	3032
[1779]	3033	*(tData.mSortedObjects[3]) = objects;
[2187]	3034
	3035	stable_sort(tData.mSortedObjects[3]->begin(), tData.mSortedObjects[3]->end(), smallerSize);
[1357]	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
[1784]	3054	for (int i = 0; i < 4; ++ i)
[1357]	3055	{
[1359]	3056	frontData.mSortedObjects[i] = new ObjectContainer();
	3057	backData.mSortedObjects[i] = new ObjectContainer();
	3058
[2347]	3059	frontData.mSortedObjects[i]->reserve(sc.mFrontObjects.size());
	3060	backData.mSortedObjects[i]->reserve(sc.mBackObjects.size());
[1357]	3061
[1370]	3062	ObjectContainer::const_iterator oit, oit_end = sc.mParentData.mSortedObjects[i]->end();
[1357]	3063
[2004]	3064	// all the front objects are mailed => assign the sorted object lists
[1370]	3065	for (oit = sc.mParentData.mSortedObjects[i]->begin(); oit != oit_end; ++ oit)
[1357]	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
[1779]	3080	void BvHierarchy::Reset(SplitQueue &tQueue,
	3081	const VssRayContainer &sampleRays,
	3082	const ObjectContainer &objects)
[1548]	3083	{
[2198]	3084
[1548]	3085	// reset stats
	3086	mBvhStats.Reset();
	3087	mBvhStats.Start();
	3088	mBvhStats.nodes = 1;
	3089
	3090	// reset root
	3091	DEL_PTR(mRoot);
	3092
[1640]	3093	BvhLeaf *bvhleaf = new BvhLeaf(mBoundingBox, NULL, (int)objects.size());
	3094	bvhleaf->mObjects = objects;
	3095	mRoot = bvhleaf;
	3096
[2210]	3097	ObjectContainer *sampledObjects = new ObjectContainer();
	3098	StoreSampledObjects(*sampledObjects, objects);
	3099
[2198]	3100	#if STORE_VIEWCELLS_WITH_BVH
[2210]	3101	AssociateViewCellsWithObjects(*sampledObjects);
[2198]	3102	#endif
	3103
[1914]	3104	//mTermMinProbability *= mVspTree->GetBoundingBox().GetVolume();
[1548]	3105	// probability that volume is "seen" from the view cells
[1914]	3106	const float viewSpaceVol = mViewCellsManager->GetViewSpaceBox().GetVolume();
[2210]	3107	const float prop = EvalViewCellsVolume(*sampledObjects);
[1548]	3108
[2210]	3109	const int nRays = CountRays(*sampledObjects);
[2017]	3110	BvhLeaf bvhLeaf = static_cast<BvhLeaf >(mRoot);
[1548]	3111
	3112	// create bvh traversal data
	3113	BvhTraversalData oData(bvhLeaf, 0, prop, nRays);
	3114
[2210]	3115	oData.mSampledObjects = sampledObjects;
	3116
[2005]	3117	if (mUseGlobalSorting)
[2003]	3118	AssignInitialSortedObjectList(oData, objects);
[1580]	3119
[2198]	3120	#if STORE_VIEWCELLS_WITH_BVH
[2210]	3121	ReleaseViewCells(*sampledObjects);
[2198]	3122	#endif
[1548]	3123	///////////////////
	3124	//-- add first candidate for object space partition
	3125
	3126	BvhSubdivisionCandidate *oSubdivisionCandidate =
	3127	new BvhSubdivisionCandidate(oData);
	3128
[2224]	3129	EvalSubdivisionCandidate(*oSubdivisionCandidate, true, true);
[1548]	3130	bvhLeaf->SetSubdivisionCandidate(oSubdivisionCandidate);
	3131
[1914]	3132	mTotalCost = (float)objects.size() * prop;
[1548]	3133
	3134	PrintSubdivisionStats(*oSubdivisionCandidate);
	3135
[1779]	3136	tQueue.Push(oSubdivisionCandidate);
[1548]	3137	}
	3138
	3139
[1279]	3140	void BvhStatistics::Print(ostream &app) const
	3141	{
[1288]	3142	app << "=========== BvHierarchy statistics ===============\n";
[1279]	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
[1288]	3162
[1370]	3163	//////////////////////////////////////////////////
	3164
	3165	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
	3166	<< maxDepthNodes * 100 / (double)Leaves() << endl;
	3167
[1279]	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
[1370]	3174
	3175	////////////////////////////////////////////////////////
	3176
	3177	app << "#N_PMINOBJECTSLEAVES ( Percentage of leaves with mininum objects )\n"
	3178	<< minObjectsNodes * 100 / (double)Leaves() << endl;
[1279]	3179
	3180	app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
	3181
[1370]	3182	app << "#N_MINOBJECTREFS ( Min number of object refs / leaf )\n" << minObjectRefs << "\n";
[1408]	3183
	3184	app << "#N_EMPTYLEAFS ( Empty leafs )\n" << emptyNodes << "\n";
[1279]	3185
[1370]	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
[1449]	3206	app << "#N_PGLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
	3207
[1370]	3208	app << "========== END OF BvHierarchy statistics ==========\n";
[1272]	3209	}
[1259]	3210
[1279]	3211
[1640]	3212	// TODO: return memory usage in MB
	3213	float BvHierarchy::GetMemUsage() const
	3214	{
[1686]	3215	return (float)(sizeof(BvHierarchy)
	3216	+ mBvhStats.Leaves() * sizeof(BvhLeaf)
	3217	+ mBvhStats.Interior() * sizeof(BvhInterior)
	3218	) / float(1024 * 1024);
[1640]	3219	}
	3220
	3221
[1707]	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);
[1713]	3228	vector<BvhLeaf *>::const_iterator lit, lit_end = leaves.end();
[1707]	3229
[1713]	3230	for (lit = leaves.begin(); lit != lit_end; ++ lit)
[1707]	3231	{
[1713]	3232	(*lit)->SetActiveNode(node);
[1707]	3233	}
	3234	}
	3235
	3236
[1877]	3237	void BvHierarchy::CollectObjects(const AxisAlignedBox3 &box,
	3238	ObjectContainer &objects)
[1718]	3239	{
[1737]	3240	stack<BvhNode *> nodeStack;
[1877]	3241
[1737]	3242	nodeStack.push(mRoot);
[1718]	3243
[1877]	3244	while (!nodeStack.empty()) {
[1757]	3245	BvhNode *node = nodeStack.top();
	3246
	3247	nodeStack.pop();
[1877]	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);
[1757]	3255	}
[1877]	3256	}
	3257	}
[1761]	3258	else
	3259	{
	3260	BvhInterior interior = (BvhInterior )node;
[1877]	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	}
[1757]	3275	}
[1877]	3276	}
[1715]	3277	}
[1718]	3278
[1774]	3279
[1843]	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
[1779]	3304	void BvHierarchy::ApplyInitialSubdivision(SubdivisionCandidate *firstCandidate,
[1789]	3305	vector<SubdivisionCandidate *> &candidateContainer)
[1774]	3306	{
[1779]	3307	SplitQueue tempQueue;
[1784]	3308	tempQueue.Push(firstCandidate);
[1830]	3309
[1779]	3310	while (!tempQueue.Empty())
[1787]	3311	{
[1784]	3312	SubdivisionCandidate *candidate = tempQueue.Top();
[1786]	3313	tempQueue.Pop();
[1778]	3314
[1779]	3315	BvhSubdivisionCandidate *bsc =
[2017]	3316	static_cast<BvhSubdivisionCandidate *>(candidate);
[1786]	3317
[1779]	3318	if (!InitialTerminationCriteriaMet(bsc->mParentData))
[1790]	3319	{
[1830]	3320	const bool globalCriteriaMet = GlobalTerminationCriteriaMet(bsc->mParentData);
	3321
[2224]	3322	SubdivisionCandidateContainer dirtyList;
	3323	BvhNode *node = Subdivide(tempQueue, bsc, globalCriteriaMet, dirtyList);
[1786]	3324
[1779]	3325	// not needed anymore
	3326	delete bsc;
[1778]	3327	}
[2003]	3328	else
[1790]	3329	{
[2003]	3330	// initial preprocessing finished for this candidate
[1830]	3331	// add to candidate container
[1789]	3332	candidateContainer.push_back(bsc);
[1779]	3333	}
	3334	}
[1718]	3335	}
[1774]	3336
	3337
[1784]	3338	void BvHierarchy::ApplyInitialSplit(const BvhTraversalData &tData,
	3339	ObjectContainer &frontObjects,
	3340	ObjectContainer &backObjects)
[1778]	3341	{
[1779]	3342	ObjectContainer *objects = tData.mSortedObjects[3];
	3343
	3344	ObjectContainer::const_iterator oit, oit_end = objects->end();
[1787]	3345
[1786]	3346	float maxAreaDiff = -1.0f;
	3347
[1779]	3348	ObjectContainer::const_iterator backObjectsStart = objects->begin();
[1830]	3349
[1841]	3350	for (oit = objects->begin(); oit != (objects->end() - 1); ++ oit)
[1787]	3351	{
[1779]	3352	Intersectable objS = oit;
	3353	Intersectable objL = (oit + 1);
[1778]	3354
	3355	const float areaDiff =
[1786]	3356	objL->GetBox().SurfaceArea() - objS->GetBox().SurfaceArea();
[1778]	3357
	3358	if (areaDiff > maxAreaDiff)
	3359	{
	3360	maxAreaDiff = areaDiff;
[1779]	3361	backObjectsStart = oit + 1;
[1774]	3362	}
[1778]	3363	}
[1774]	3364
[1779]	3365	// belongs to back bv
	3366	for (oit = objects->begin(); oit != backObjectsStart; ++ oit)
	3367	{
[1789]	3368	frontObjects.push_back(*oit);
[1779]	3369	}
[1774]	3370
[1779]	3371	// belongs to front bv
	3372	for (oit = backObjectsStart; oit != oit_end; ++ oit)
[1774]	3373	{
[1789]	3374	backObjects.push_back(*oit);
[1778]	3375	}
[1790]	3376
[1830]	3377	cout << "front: " << (int)frontObjects.size() << " back: " << (int)backObjects.size() << " "
	3378	<< backObjects.front()->GetBox().SurfaceArea() - frontObjects.back()->GetBox().SurfaceArea() << endl;
[1779]	3379	}
[1778]	3380
[1779]	3381
[1786]	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
[1843]	3387	return areaSmall / (areaLarge - areaSmall + Limits::Small);
[1786]	3388	}
	3389
	3390
[1779]	3391	bool BvHierarchy::InitialTerminationCriteriaMet(const BvhTraversalData &tData) const
	3392	{
[1830]	3393	const bool terminationCriteriaMet =
	3394	(0
[1786]	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)
[1779]	3398	);
[1830]	3399
[1841]	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;
[1830]	3404
	3405	return terminationCriteriaMet;
[1774]	3406	}
	3407
	3408
[1786]	3409	// HACK
[2332]	3410	float BvHierarchy::GetTriangleSizeIncrementially(BvhNode *node) const
[1786]	3411	{
[2332]	3412	if (node->mRenderCost < 0)
[1786]	3413	{
[2332]	3414	//cout <<"p";
[1786]	3415	if (node->IsLeaf())
	3416	{
[2017]	3417	BvhLeaf leaf = static_cast<BvhLeaf >(node);
[2332]	3418	node->mRenderCost = (float)leaf->mObjects.size();
[1786]	3419	}
	3420	else
	3421	{
[2017]	3422	BvhInterior interior = static_cast<BvhInterior >(node);
[1786]	3423
[2332]	3424	node->mRenderCost = GetTriangleSizeIncrementially(interior->GetFront()) +
	3425	GetTriangleSizeIncrementially(interior->GetBack());
[1786]	3426	}
	3427	}
	3428
	3429	return node->mRenderCost;
[1774]	3430	}
[1786]	3431
	3432
[1844]	3433	void BvHierarchy::Compress()
	3434	{
[1786]	3435	}
[1844]	3436
	3437
[2093]	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	}
[1844]	3454	}
[2093]	3455
	3456
	3457	}

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

Download in other formats: