Context Navigation

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

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

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

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

Download in other formats: