Context Navigation

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

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

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

Download in other formats: