Context Navigation

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

Revision 1877, 72.0 KB checked in by bittner, 18 years ago (diff)
sampling updates

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

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

Download in other formats: