Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp @ 1111

Revision 1111, 90.5 KB checked in by mattausch, 18 years ago (diff)

Rev	Line
[1002]	1	#include <stack>
	2	#include <time.h>
	3	#include <iomanip>
	4
[1010]	5	#include "ViewCell.h"
[1002]	6	#include "Plane3.h"
[1006]	7	#include "VspOspTree.h"
[1002]	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"
[1020]	18	#include "KdTree.h"
[1002]	19
[1020]	20
[1002]	21	namespace GtpVisibilityPreprocessor {
	22
	23	#define USE_FIXEDPOINT_T 0
[1106]	24	#define COUNT_OBJECTS 1
[1002]	25
	26	//-- static members
	27
[1099]	28	VspTree *VspTree::VspSplitCandidate::sVspTree = NULL;
	29	OspTree *OspTree::OspSplitCandidate::sOspTree = NULL;
[1002]	30
	31	// pvs penalty can be different from pvs size
	32	inline static float EvalPvsPenalty(const int pvs,
	33	const int lower,
	34	const int upper)
	35	{
	36	// clamp to minmax values
	37	if (pvs < lower)
	38	return (float)lower;
[1077]	39	else if (pvs > upper)
[1002]	40	return (float)upper;
	41
	42	return (float)pvs;
	43	}
	44
	45
[1008]	46	int VspNode::sMailId = 1;
[1002]	47
	48
[1021]	49
	50	void VspTreeStatistics::Print(ostream &app) const
	51	{
[1027]	52	app << "===== VspTree statistics ===============\n";
[1021]	53
	54	app << setprecision(4);
	55
	56	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
	57
	58	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
	59
	60	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	61
	62	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	63
	64	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
	65
	66	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
	67
	68	for (int i = 0; i < 3; ++ i)
	69	app << splits[i] << " ";
	70	app << endl;
	71
	72	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
	73	<< maxDepthNodes * 100 / (double)Leaves() << endl;
	74
	75	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
	76	<< minPvsNodes * 100 / (double)Leaves() << endl;
	77
	78	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
	79	<< minRaysNodes * 100 / (double)Leaves() << endl;
	80
	81	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
	82	<< maxCostNodes * 100 / (double)Leaves() << endl;
	83
	84	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
	85	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
	86
	87	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
	88	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
	89
	90	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
	91
	92	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
	93
	94	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
	95
	96	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
	97
	98	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
	99	//app << "#N_PVS: " << pvs << endl;
	100
[1027]	101	app << "===== END OF VspTree statistics ==========\n";
[1021]	102	}
	103
	104
[1008]	105	/******************************************************************/
	106	/* class VspNode implementation */
	107	/******************************************************************/
	108
	109
	110	VspNode::VspNode():
	111	mParent(NULL), mTreeValid(true), mTimeStamp(0)
	112	{}
	113
	114
	115	VspNode::VspNode(VspInterior *parent):
	116	mParent(parent), mTreeValid(true)
	117	{}
	118
	119
	120	bool VspNode::IsRoot() const
	121	{
	122	return mParent == NULL;
	123	}
	124
	125
	126	VspInterior *VspNode::GetParent()
	127	{
	128	return mParent;
	129	}
	130
	131
	132	void VspNode::SetParent(VspInterior *parent)
	133	{
	134	mParent = parent;
	135	}
	136
	137
	138	bool VspNode::IsSibling(VspNode *n) const
	139	{
	140	return ((this != n) && mParent &&
	141	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
	142	}
	143
	144
	145	int VspNode::GetDepth() const
	146	{
	147	int depth = 0;
	148	VspNode *p = mParent;
	149
	150	while (p)
	151	{
	152	p = p->mParent;
	153	++ depth;
	154	}
	155
	156	return depth;
	157	}
	158
	159
	160	bool VspNode::TreeValid() const
	161	{
	162	return mTreeValid;
	163	}
	164
	165
	166	void VspNode::SetTreeValid(const bool v)
	167	{
	168	mTreeValid = v;
	169	}
	170
	171
	172	/****************************************************************/
	173	/* class VspInterior implementation */
	174	/****************************************************************/
	175
	176
	177	VspInterior::VspInterior(const AxisAlignedPlane &plane):
	178	mPlane(plane), mFront(NULL), mBack(NULL)
	179	{}
	180
[1011]	181
[1008]	182	VspInterior::~VspInterior()
	183	{
	184	DEL_PTR(mFront);
	185	DEL_PTR(mBack);
	186	}
	187
[1011]	188
[1008]	189	bool VspInterior::IsLeaf() const
	190	{
	191	return false;
	192	}
	193
[1011]	194
[1008]	195	VspNode *VspInterior::GetBack()
	196	{
	197	return mBack;
	198	}
	199
[1011]	200
[1008]	201	VspNode *VspInterior::GetFront()
	202	{
	203	return mFront;
	204	}
	205
[1011]	206
[1008]	207	AxisAlignedPlane VspInterior::GetPlane() const
	208	{
	209	return mPlane;
	210	}
	211
[1011]	212
[1012]	213	float VspInterior::GetPosition() const
	214	{
	215	return mPlane.mPosition;
	216	}
	217
	218
	219	int VspInterior::GetAxis() const
	220	{
	221	return mPlane.mAxis;
	222	}
	223
	224
[1008]	225	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
	226	{
	227	if (mBack == oldChild)
	228	mBack = newChild;
	229	else
	230	mFront = newChild;
	231	}
	232
[1011]	233
[1109]	234	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
[1008]	235	{
[1109]	236	mBack = back;
	237	mFront = front;
[1008]	238	}
	239
	240
[1016]	241	AxisAlignedBox3 VspInterior::GetBoundingBox() const
[1012]	242	{
[1016]	243	return mBoundingBox;
[1012]	244	}
	245
	246
[1016]	247	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
[1012]	248	{
[1016]	249	mBoundingBox = box;
[1012]	250	}
	251
	252
	253	int VspInterior::Type() const
	254	{
	255	return Interior;
	256	}
	257
[1027]	258
	259
[1008]	260	/****************************************************************/
	261	/* class VspLeaf implementation */
	262	/****************************************************************/
	263
	264
	265	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
	266	{
	267	}
	268
	269
	270	VspLeaf::~VspLeaf()
	271	{
	272	DEL_PTR(mPvs);
[1074]	273	CLEAR_CONTAINER(mVssRays);
[1008]	274	}
	275
[1021]	276
[1012]	277	int VspLeaf::Type() const
	278	{
	279	return Leaf;
	280	}
[1008]	281
[1012]	282
[1008]	283	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
	284	mViewCell(viewCell)
	285	{
	286	}
	287
	288
	289	VspLeaf::VspLeaf(VspInterior *parent):
	290	VspNode(parent), mViewCell(NULL), mPvs(NULL)
	291	{}
	292
	293
	294
	295	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
	296	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
	297	{
	298	}
	299
	300	ViewCellLeaf *VspLeaf::GetViewCell() const
	301	{
	302	return mViewCell;
	303	}
	304
	305	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
	306	{
	307	mViewCell = viewCell;
	308	}
	309
	310
	311	bool VspLeaf::IsLeaf() const
	312	{
	313	return true;
	314	}
	315
	316
[1002]	317	/******************************************************************************/
[1016]	318	/* class VspTree implementation */
[1002]	319	/******************************************************************************/
	320
	321
[1016]	322	VspTree::VspTree():
[1002]	323	mRoot(NULL),
	324	mOutOfBoundsCell(NULL),
	325	mStoreRays(false),
	326	mTimeStamp(1)
	327	{
	328	bool randomize = false;
[1016]	329	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
[1002]	330	if (randomize)
	331	Randomize(); // initialise random generator for heuristics
	332
	333	//-- termination criteria for autopartition
[1016]	334	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
	335	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
	336	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
	337	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
	338	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
[1023]	339
[1016]	340	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
	341	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
[1002]	342
	343	//-- max cost ratio for early tree termination
[1016]	344	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[1002]	345
[1016]	346	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	347	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
[1002]	348
	349	//-- factors for bsp tree split plane heuristics
[1016]	350	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
[1002]	351
	352	//-- partition criteria
[1016]	353	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
[1002]	354
	355	// if only the driving axis is used for axis aligned split
[1016]	356	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[1002]	357
[1016]	358	//Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
	359	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
[1002]	360
[1016]	361	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
	362	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
[1002]	363
[1074]	364	Environment::GetSingleton()->GetIntValue("VspTree.pvsCountMethod", mPvsCountMethod);
[1023]	365
[1002]	366	char subdivisionStatsLog[100];
[1016]	367	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
[1002]	368	mSubdivisionStats.open(subdivisionStatsLog);
	369
[1016]	370	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
	371	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
[1006]	372
[1002]	373
	374	//-- debug output
	375
[1076]	376	Debug << "***** VSP options ****** " << endl;
[1106]	377
[1002]	378	Debug << "max depth: " << mTermMaxDepth << endl;
	379	Debug << "min PVS: " << mTermMinPvs << endl;
	380	Debug << "min probabiliy: " << mTermMinProbability << endl;
	381	Debug << "min rays: " << mTermMinRays << endl;
	382	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	383	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	384	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	385	Debug << "max view cells: " << mMaxViewCells << endl;
	386	Debug << "randomize: " << randomize << endl;
	387
	388	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	389	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	390	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	391	Debug << "max memory: " << mMaxMemory << endl;
	392	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	393	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1023]	394
[1002]	395	Debug << "circulating axis: " << mCirculatingAxis << endl;
	396	Debug << "minband: " << mMinBand << endl;
	397	Debug << "maxband: " << mMaxBand << endl;
	398
[1106]	399	if (mPvsCountMethod == 0)
	400	Debug << "pvs count method: per object" << endl;
	401	else
	402	Debug << "pvs count method: per kd node" << endl;
[1084]	403
[1002]	404	mSplitCandidates = new vector<SortableEntry>;
	405
	406	Debug << endl;
	407	}
	408
	409
[1016]	410	VspViewCell *VspTree::GetOutOfBoundsCell()
[1002]	411	{
	412	return mOutOfBoundsCell;
	413	}
	414
	415
[1016]	416	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
[1002]	417	{
	418	if (!mOutOfBoundsCell)
	419	{
[1008]	420	mOutOfBoundsCell = new VspViewCell();
[1002]	421	mOutOfBoundsCell->SetId(-1);
	422	mOutOfBoundsCell->SetValid(false);
	423	}
	424
	425	return mOutOfBoundsCell;
	426	}
	427
	428
[1016]	429	const VspTreeStatistics &VspTree::GetStatistics() const
[1002]	430	{
[1008]	431	return mVspStats;
[1002]	432	}
	433
	434
[1016]	435	VspTree::~VspTree()
[1002]	436	{
	437	DEL_PTR(mRoot);
	438	DEL_PTR(mSplitCandidates);
	439	}
	440
[1008]	441
[1020]	442	void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
	443	AxisAlignedBox3 *forcedBoundingBox)
[1002]	444	{
[1099]	445	// store pointer to this tree
	446	VspSplitCandidate::sVspTree = this;
	447
[1008]	448	mVspStats.nodes = 1;
[1027]	449
[1002]	450	if (forcedBoundingBox)
[1027]	451	{
[1020]	452	mBoundingBox = *forcedBoundingBox;
[1027]	453	}
	454	else // compute vsp tree bounding box
[1002]	455	{
[1027]	456	mBoundingBox.Initialize();
[1002]	457
[1027]	458	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	459
	460	//-- compute bounding box
	461	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
[1002]	462	{
[1027]	463	VssRay ray = rit;
	464
	465	// compute bounding box of view space
[1020]	466	mBoundingBox.Include(ray->GetTermination());
	467	mBoundingBox.Include(ray->GetOrigin());
[1002]	468	}
[1027]	469	}
[1108]	470
	471	mTermMinProbability *= mBoundingBox.GetVolume();
	472	mGlobalCostMisses = 0;
[1020]	473	}
[1002]	474
	475
[1020]	476	void VspTree::AddSubdivisionStats(const int viewCells,
	477	const float renderCostDecr,
	478	const float splitCandidateCost,
	479	const float totalRenderCost,
[1027]	480	const float avgRenderCost)
[1020]	481	{
	482	mSubdivisionStats
	483	<< "#ViewCells\n" << viewCells << endl
	484	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	485	<< "#SplitCandidateCost\n" << splitCandidateCost << endl
	486	<< "#TotalRenderCost\n" << totalRenderCost << endl
	487	<< "#AvgRenderCost\n" << avgRenderCost << endl;
[1002]	488	}
	489
	490
	491	// TODO: return memory usage in MB
[1016]	492	float VspTree::GetMemUsage() const
[1002]	493	{
	494	return (float)
[1016]	495	(sizeof(VspTree) +
[1008]	496	mVspStats.Leaves() * sizeof(VspLeaf) +
[1010]	497	mCreatedViewCells * sizeof(VspViewCell) +
[1008]	498	mVspStats.pvs * sizeof(ObjectPvsData) +
	499	mVspStats.Interior() * sizeof(VspInterior) +
	500	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
[1002]	501	}
	502
	503
[1016]	504	bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
[1002]	505	{
[1106]	506	return(
	507	((int)data.mRays->size() <= mTermMinRays) \|\|
	508	(data.mPvs <= mTermMinPvs) \|\|
	509	(data.mProbability <= mTermMinProbability) \|\|
	510	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
	511	(data.mDepth >= mTermMaxDepth)
	512	);
	513
[1002]	514	}
	515
	516
[1016]	517	bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
[1002]	518	{
[1108]	519	Debug << "cost misses " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
	520	Debug << "leaves " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
	521
[1106]	522	return (
	523	// mOutOfMemory \|\|
[1011]	524	(mVspStats.Leaves() >= mMaxViewCells) \|\|
[1106]	525	(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
	526	);
[1002]	527	}
	528
	529
[1108]	530	void VspTree::CreateViewCell(VspTraversalData &tData)
	531	{
	532	//-- create new view cell
	533	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
	534
	535	VspViewCell *viewCell = new VspViewCell();
	536	leaf->SetViewCell(viewCell);
	537
	538	//-- update pvs
	539	int conSamp = 0;
	540	float sampCon = 0.0f;
	541	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
	542
	543	// update scalar pvs size value
	544	mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
	545
	546	mVspStats.contributingSamples += conSamp;
	547	mVspStats.sampleContributions +=(int) sampCon;
	548
	549	//-- store additional info
	550	if (mStoreRays)
	551	{
	552	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
[1109]	553
[1108]	554	for (it = tData.mRays->begin(); it != it_end; ++ it)
	555	{
	556	(*it).mRay->Ref();
	557	leaf->mVssRays.push_back((*it).mRay);
	558	}
	559	}
	560
	561	viewCell->mLeaf = leaf;
	562
	563	viewCell->SetVolume(tData.mProbability);
	564	leaf->mProbability = tData.mProbability;
	565
	566	mVspStats.contributingSamples += conSamp;
[1109]	567	mVspStats.sampleContributions += (int)sampCon;
[1108]	568
	569	// finally evaluate statistics for this leaf
	570	EvaluateLeafStats(tData);
	571	}
	572
	573
[1016]	574	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
[1020]	575	VspSplitCandidate &splitCandidate,
	576	const bool globalCriteriaMet)
[1002]	577	{
[1016]	578	VspTraversalData &tData = splitCandidate.mParentData;
[1002]	579
[1008]	580	VspNode *newNode = tData.mNode;
[1002]	581
[1020]	582	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
[1002]	583	{
[1016]	584	VspTraversalData tFrontData;
	585	VspTraversalData tBackData;
[1002]	586
	587	//-- continue subdivision
	588
	589	// create new interior node and two leaf node
[1008]	590	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
[1006]	591	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
[1002]	592
	593	const int maxCostMisses = splitCandidate.mMaxCostMisses;
	594
	595
	596	// how often was max cost ratio missed in this branch?
	597	tFrontData.mMaxCostMisses = maxCostMisses;
	598	tBackData.mMaxCostMisses = maxCostMisses;
	599
[1108]	600
[1002]	601	if (1)
	602	{
[1108]	603	//-- subdivision statistics
	604
[1020]	605	const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
	606	const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
	607	const float cData = (float)tData.mPvs * tData.mProbability;
	608
	609	const float costDecr =
	610	(cFront + cBack - cData) / mBoundingBox.GetVolume();
[1002]	611
	612	mTotalCost += costDecr;
	613	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
	614
[1020]	615	AddSubdivisionStats(mVspStats.Leaves(),
	616	-costDecr,
	617	splitCandidate.GetPriority(),
	618	mTotalCost,
	619	(float)mTotalPvsSize / (float)mVspStats.Leaves());
[1002]	620	}
	621
	622
[1108]	623	//-- evaluate new split candidates for global greedy cost heuristics
[1099]	624	VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData);
	625	VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData);
[1002]	626
[1099]	627	EvalSplitCandidate(*frontCandidate);
	628	EvalSplitCandidate(*backCandidate);
[1020]	629
[1099]	630	tQueue.Push(frontCandidate);
	631	tQueue.Push(backCandidate);
[1020]	632
[1002]	633	// delete old leaf node
	634	DEL_PTR(tData.mNode);
	635	}
	636
[1108]	637	// subdivision terminated
[1002]	638	if (newNode->IsLeaf())
	639	{
[1108]	640	//-- create new view cell
[1109]	641	//CreateViewCell(tData);
[1020]	642
[1002]	643	//-- store additional info
	644	if (mStoreRays)
	645	{
	646	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	647	for (it = tData.mRays->begin(); it != it_end; ++ it)
	648	{
	649	(*it).mRay->Ref();
[1108]	650	dynamic_cast<VspLeaf >(newNode)->mVssRays.push_back((it).mRay);
[1002]	651	}
	652	}
	653
[1108]	654	// finally evaluate statistics for this leaf
[1020]	655	EvaluateLeafStats(tData);
[1002]	656	}
	657
	658	//-- cleanup
	659	tData.Clear();
[1020]	660
[1002]	661	return newNode;
	662	}
	663
	664
[1099]	665	void VspTree::EvalSplitCandidate(VspSplitCandidate &splitCandidate)
[1002]	666	{
[1020]	667	float frontProb;
[1027]	668	float backProb;
[1020]	669
[1099]	670	VspLeaf leaf = dynamic_cast<VspLeaf >(splitCandidate.mParentData.mNode);
[1020]	671
[1002]	672	// compute locally best split plane
[1008]	673	const bool success =
[1099]	674	SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
[1008]	675
[1002]	676	// compute global decrease in render cost
[1099]	677	const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData);
	678	splitCandidate.SetPriority(priority);
	679	splitCandidate.mMaxCostMisses = success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
[1074]	680	//Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
[1002]	681	}
	682
	683
[1016]	684	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
	685	VspTraversalData &tData,
	686	VspTraversalData &frontData,
	687	VspTraversalData &backData)
[1002]	688	{
[1008]	689	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
[1002]	690
	691	//-- the front and back traversal data is filled with the new values
[1108]	692
[1002]	693	frontData.mDepth = tData.mDepth + 1;
	694	frontData.mRays = new RayInfoContainer();
	695
	696	backData.mDepth = tData.mDepth + 1;
	697	backData.mRays = new RayInfoContainer();
	698
	699	//-- subdivide rays
	700	SplitRays(splitPlane,
	701	*tData.mRays,
	702	*frontData.mRays,
	703	*backData.mRays);
	704
[1109]	705
[1074]	706	//Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
[1011]	707	//-- compute pvs
[1002]	708	frontData.mPvs = ComputePvsSize(*frontData.mRays);
	709	backData.mPvs = ComputePvsSize(*backData.mRays);
	710
	711	// split front and back node geometry and compute area
[1006]	712	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
	713	frontData.mBoundingBox, backData.mBoundingBox);
[1002]	714
	715
[1006]	716	frontData.mProbability = frontData.mBoundingBox.GetVolume();
	717	backData.mProbability = tData.mProbability - frontData.mProbability;
[1002]	718
	719
[1006]	720	///////////////////////////////////////////
[1002]	721	// subdivide further
	722
	723	// store maximal and minimal depth
[1008]	724	if (tData.mDepth > mVspStats.maxDepth)
[1002]	725	{
[1008]	726	Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
	727	mVspStats.maxDepth = tData.mDepth;
[1002]	728	}
	729
[1109]	730	// two more leaves
[1008]	731	mVspStats.nodes += 2;
[1002]	732
[1008]	733	VspInterior *interior = new VspInterior(splitPlane);
[1002]	734
	735	#ifdef _DEBUG
	736	Debug << interior << endl;
	737	#endif
	738
	739
	740	//-- create front and back leaf
	741
[1008]	742	VspInterior *parent = leaf->GetParent();
[1002]	743
	744	// replace a link from node's parent
	745	if (parent)
	746	{
	747	parent->ReplaceChildLink(leaf, interior);
	748	interior->SetParent(parent);
	749	}
	750	else // new root
	751	{
	752	mRoot = interior;
	753	}
	754
[1109]	755	VspLeaf *frontLeaf = new VspLeaf(interior);
	756	VspLeaf *backLeaf = new VspLeaf(interior);
	757
[1002]	758	// and setup child links
[1109]	759	interior->SetupChildLinks(frontLeaf, backLeaf);
[1106]	760
[1016]	761	// add bounding box
	762	interior->SetBoundingBox(tData.mBoundingBox);
[1002]	763
[1106]	764	// set front and back leaf
[1109]	765	frontData.mNode = frontLeaf;
	766	backData.mNode = backLeaf;
[1106]	767
[1109]	768	// explicitely create front and back view cell
	769	CreateViewCell(frontData);
	770	CreateViewCell(backData);
	771
	772	// TODO:
	773	// create front and back view cell
	774	// remove "parent" view cell from pvs of all objects (traverse trough rays)
	775	// add front and back view cell to "Potentially Visbilie View Cells"
	776	// of the objects in front and back pvs
[1110]	777	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
	778	AddViewCellReferences(frontLeaf->GetViewCell());
	779	AddViewCellReferences(backLeaf->GetViewCell());
[1109]	780
	781
[1002]	782	interior->mTimeStamp = mTimeStamp ++;
	783
	784	return interior;
	785	}
	786
	787
[1109]	788	/*void VspTree::RemoveParentViewCellReferences(VspTraversalData &parentData)
	789	{
	790	RayInfoContainer::const_iterator it, it_end = parentData.mRays->end();
[1089]	791
[1109]	792	KdLeaf::NewMail();
	793	Intersectable::NewMail();
	794
	795	ViewCell *vc = parentData.mNode->mViewCell;
	796
	797	const float highestContri = 1e25;
	798
	799	// add contributions from samples to the PVS
	800	for (it = parentData.mRays->begin(); it != it_end; ++ it)
[1089]	801	{
[1109]	802	VssRay ray = (it).mRay;
[1089]	803
[1109]	804	Intersectable *obj = ray->mTerminationObject;
	805
	806	if (obj && !obj->Mailed())
[1089]	807	{
[1109]	808	obj->Mail();
	809	// reduce object reference count by one
	810	-- obj->mViewCellPvs;
	811
	812	set<KdLeaf *>::const_iterator kit, kit_end = obj->mKdLeaves.end();
	813
	814	for (kit = obj->mKdLeaves.begin(); kit != kit_end; ++ kit)
	815	{
	816	KdLeaf leaf = kit;
	817
	818	if (!leaf->Mailed())
	819	{
	820	leaf->Mail();
	821	leaf->mViewCellPvs.RemoveSample(vc, highestContri);
	822	}
	823	}
[1089]	824	}
[1109]	825
	826	Intersectable *obj = ray->mOriginObject;
	827
	828	if (obj && !obj->Mailed())
	829	{
	830	obj->Mail();
	831	// reduce object reference count by one
	832	-- obj->mViewCellPvs;
	833
	834	set<KdLeaf *>::const_iterator kit, kit_end = obj->mKdLeaves.end();
	835
	836	for (kit = obj->mKdLeaves.begin(); kit != kit_end; ++ kit)
	837	{
	838	KdLeaf leaf = kit;
	839
	840	if (!leaf->Mailed())
	841	{
	842	leaf->Mail();
	843	leaf->mViewCellPvs.RemoveSample(vc, highestContri);
	844	}
	845	}
	846	}
[1089]	847	}
[1109]	848	}*/
[1089]	849
[1109]	850
	851	void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
	852	{
	853	KdLeaf::NewMail();
	854
	855	// remove the parents from the object pvss
	856	ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
	857
	858	for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
[1089]	859	{
[1109]	860	Intersectable object = (oit).first;
	861	// HACK: make sure that the view cell is removed from the pvs
	862	const float high_contri = 9999999;
[1089]	863
[1109]	864	// remove reference count of view cells
[1110]	865	object->mViewCellPvs.RemoveSample(parent, high_contri);
[1089]	866	}
[1109]	867	}
[1089]	868
[1109]	869
	870	void VspTree::AddViewCellReferences(ViewCell *vc) const
	871	{
	872	KdLeaf::NewMail();
	873
	874	// Add front view cell to the object pvsss
[1110]	875	ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
[1109]	876
[1110]	877	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
[1089]	878	{
[1109]	879	Intersectable object = (oit).first;
[1089]	880
[1109]	881	// increase reference count of view cells
[1110]	882	object->mViewCellPvs.AddSample(vc, 1);
[1089]	883	}
	884	}
	885
	886
[1016]	887	void VspTree::AddToPvs(VspLeaf *leaf,
[1089]	888	const RayInfoContainer &rays,
	889	float &sampleContributions,
	890	int &contributingSamples)
[1002]	891	{
	892	sampleContributions = 0;
	893	contributingSamples = 0;
	894
	895	RayInfoContainer::const_iterator it, it_end = rays.end();
	896
	897	ViewCellLeaf *vc = leaf->GetViewCell();
	898
	899	// add contributions from samples to the PVS
	900	for (it = rays.begin(); it != it_end; ++ it)
	901	{
	902	float sc = 0.0f;
	903	VssRay ray = (it).mRay;
	904
	905	bool madeContrib = false;
	906	float contribution;
	907
[1109]	908	Intersectable *obj = ray->mTerminationObject;
	909
	910	if (obj)
[1002]	911	{
[1109]	912	if (vc->AddPvsSample(obj, ray->mPdf, contribution))
[1089]	913	{
[1002]	914	madeContrib = true;
[1089]	915	}
	916
[1002]	917	sc += contribution;
	918	}
[1109]	919
[1110]	920	obj = ray->mOriginObject;
[1109]	921
	922	if (obj)
[1002]	923	{
[1109]	924	if (vc->AddPvsSample(obj, ray->mPdf, contribution))
[1089]	925	{
[1002]	926	madeContrib = true;
[1089]	927	}
	928
[1002]	929	sc += contribution;
	930	}
	931
[1109]	932
[1047]	933	if (madeContrib)
	934	++ contributingSamples;
[1002]	935
[1077]	936	// store rays for visualization
	937	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
[1002]	938	}
	939	}
	940
	941
[1047]	942	void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
	943	const int axis,
	944	float minBand,
	945	float maxBand)
[1002]	946	{
	947	mSplitCandidates->clear();
	948
	949	int requestedSize = 2 * (int)(rays.size());
[1047]	950
[1002]	951	// creates a sorted split candidates array
	952	if (mSplitCandidates->capacity() > 500000 &&
	953	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
	954	{
	955	delete mSplitCandidates;
	956	mSplitCandidates = new vector<SortableEntry>;
	957	}
	958
	959	mSplitCandidates->reserve(requestedSize);
	960
	961	float pos;
	962
[1084]	963	//-- insert all queries
[1002]	964	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
	965	{
	966	const bool positive = (*ri).mRay->HasPosDir(axis);
	967
	968	pos = (*ri).ExtrapOrigin(axis);
	969
	970	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
	971	pos, (*ri).mRay));
	972
	973	pos = (*ri).ExtrapTermination(axis);
	974
	975	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
	976	pos, (*ri).mRay));
	977	}
	978
	979	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
	980	}
	981
	982
[1072]	983	int VspTree::GetPvsContribution(Intersectable *object) const
	984	{
	985	int pvsContri = 0;
	986
	987	KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
	988
	989	Intersectable::NewMail();
	990
	991	// Search kd leaves this object is attached to
	992	for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	993	{
	994	KdNode l = (kit).first;
	995
	996	// new object found during sweep
	997	// => increase pvs contribution of this kd node
	998	if (!l->Mailed())
	999	{
	1000	l->Mail();
	1001	++ pvsContri;
	1002	}
	1003	}
	1004
	1005	return pvsContri;
	1006	}
	1007
	1008
[1074]	1009	int VspTree::PrepareHeuristics(Intersectable *object)
	1010	{
	1011	set<KdLeaf *>::const_iterator kit, kit_end = object->mKdLeaves.end();
	1012
	1013	int pvsSize = 0;
	1014
	1015	for (kit = object->mKdLeaves.begin(); kit != kit_end; ++ kit)
	1016	{
	1017	KdLeaf node = dynamic_cast<KdLeaf >(*kit);
	1018
	1019	if (!node->Mailed())
	1020	{
	1021	node->Mail();
	1022	node->mCounter = 1;
	1023
	1024	// add objects without the objects which are in several kd leaves
	1025	pvsSize += (int)(node->mObjects.size() - node->mMultipleObjects.size());
	1026	}
	1027	else
	1028	{
	1029	++ node->mCounter;
	1030	}
	1031
	1032	//-- the objects belonging to several leaves must be handled seperately
	1033	ObjectContainer::const_iterator oit, oit_end = node->mMultipleObjects.end();
	1034
	1035	for (oit = node->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1036	{
	1037	Intersectable object = oit;
	1038
	1039	if (!object->Mailed())
	1040	{
	1041	object->Mail();
	1042	object->mCounter = 1;
	1043
	1044	++ pvsSize;
	1045	}
	1046	else
	1047	{
	1048	++ object->mCounter;
	1049	}
	1050	}
	1051	}
	1052
	1053	return pvsSize;
	1054	}
	1055
	1056
	1057	int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
[1072]	1058	{
[1074]	1059	Intersectable::NewMail();
	1060	KdNode::NewMail();
[1072]	1061
[1074]	1062	int pvsSize = 0;
[1072]	1063
[1074]	1064	RayInfoContainer::const_iterator ri, ri_end = rays.end();
[1072]	1065
[1074]	1066	//-- set all kd nodes as belonging to the front pvs
	1067
	1068	for (ri = rays.begin(); ri != ri_end; ++ ri)
[1072]	1069	{
[1074]	1070	Intersectable oObject = (ri).mRay->mOriginObject;
	1071
	1072	if (oObject)
	1073	{
	1074	if (mPvsCountMethod == PER_OBJECT)
	1075	{
	1076	if (!oObject->Mailed())
	1077	{
	1078	oObject->Mail();
	1079	oObject->mCounter = 1;
	1080	++ pvsSize;
	1081	}
	1082	else
	1083	{
	1084	++ oObject->mCounter;
	1085	}
	1086	}
	1087	else
	1088	{
	1089	pvsSize += PrepareHeuristics(oObject);
	1090	}
	1091	}
	1092
	1093	Intersectable tObject = (ri).mRay->mTerminationObject;
	1094
	1095	if (tObject)
	1096	{
	1097	if (mPvsCountMethod == PER_OBJECT)
	1098	{
	1099	if (!tObject->Mailed())
	1100	{
	1101	tObject->Mail();
	1102	tObject->mCounter = 1;
	1103	++ pvsSize;
	1104	}
	1105	else
	1106	{
	1107	++ tObject->mCounter;
	1108	}
	1109	}
	1110	else
	1111	{
	1112	pvsSize += PrepareHeuristics(tObject);
	1113	}
	1114	}
[1072]	1115	}
[1074]	1116
	1117	return pvsSize;
[1072]	1118	}
	1119
	1120
[1074]	1121	void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const
[1072]	1122	{
[1074]	1123	// leaf falls out of right pvs
	1124	if (-- leaf->mCounter == 0)
[1072]	1125	{
[1074]	1126	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
	1127	}
[1072]	1128
[1074]	1129	//-- handle objects which are in several kd leaves separately
	1130	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
[1072]	1131
[1074]	1132	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1133	{
	1134	Intersectable object = oit;
[1072]	1135
[1074]	1136	if (-- object->mCounter == 0)
	1137	{
	1138	-- pvs;
	1139	}
[1072]	1140	}
	1141	}
	1142
	1143
[1074]	1144	void VspTree::AddContriToPvs(KdLeaf *leaf, int &pvs) const
[1072]	1145	{
[1074]	1146	if (!leaf->Mailed())
	1147	{
	1148	leaf->Mail();
[1072]	1149
[1077]	1150	// add objects without those which are part of several kd leaves
[1074]	1151	pvs += ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
[1072]	1152
[1074]	1153	//-- handle objects of several kd leaves separately
	1154	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
[1072]	1155
[1074]	1156	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1157	{
	1158	Intersectable object = oit;
[1072]	1159
[1074]	1160	// object not previously in left pvs
	1161	if (!object->Mailed())
	1162	{
	1163	object->Mail();
	1164	++ pvs;
	1165	}
	1166	}
	1167	}
	1168	}
[1072]	1169
	1170
[1074]	1171	void VspTree::EvalPvsIncr(const SortableEntry &ci,
	1172	int &pvsLeft,
	1173	int &pvsRight) const
	1174	{
	1175	VssRay *ray = ci.ray;
[1072]	1176
[1074]	1177	Intersectable *oObject = ray->mOriginObject;
	1178	Intersectable *tObject = ray->mTerminationObject;
[1072]	1179
[1074]	1180	if (oObject)
	1181	{
	1182	if (mPvsCountMethod == PER_OBJECT)
[1072]	1183	{
[1074]	1184	if (ci.type == SortableEntry::ERayMin)
[1072]	1185	{
[1074]	1186	if (!oObject->Mailed())
[1072]	1187	{
[1074]	1188	oObject->Mail();
	1189	++ pvsLeft;
[1072]	1190	}
[1074]	1191	}
	1192	else if (ci.type == SortableEntry::ERayMax)
	1193	{
	1194	if (-- oObject->mCounter == 0)
	1195	-- pvsRight;
	1196	}
[1072]	1197	}
[1074]	1198	else // per kd node
[1072]	1199	{
[1074]	1200	set<KdLeaf *>::const_iterator kit, kit_end = oObject->mKdLeaves.end();
	1201
	1202	for (kit = oObject->mKdLeaves.begin(); kit != kit_end; ++ kit)
[1072]	1203	{
[1074]	1204	KdLeaf node = dynamic_cast<KdLeaf >(*kit);
[1072]	1205
[1074]	1206	// add contributions of the kd nodes
	1207	if (ci.type == SortableEntry::ERayMin)
[1072]	1208	{
[1074]	1209	AddContriToPvs(node, pvsLeft);
[1072]	1210	}
[1074]	1211	else if (ci.type == SortableEntry::ERayMax)
[1072]	1212	{
[1074]	1213	RemoveContriFromPvs(node, pvsRight);
[1072]	1214	}
[1074]	1215	}
[1072]	1216	}
[1074]	1217
[1072]	1218
[1074]	1219	}
	1220
	1221	if (tObject)
	1222	{
	1223	if (mPvsCountMethod == PER_OBJECT)
	1224	{
	1225	if (ci.type == SortableEntry::ERayMin)
[1072]	1226	{
[1074]	1227	if (!tObject->Mailed())
	1228	{
	1229	tObject->Mail();
	1230	++ pvsLeft;
	1231	}
[1072]	1232	}
[1074]	1233	else if (ci.type == SortableEntry::ERayMax)
[1072]	1234	{
[1074]	1235	if (-- tObject->mCounter == 0)
	1236	-- pvsRight;
[1072]	1237	}
	1238	}
[1074]	1239	else // per kd node
[1072]	1240	{
[1074]	1241	set<KdLeaf *>::const_iterator kit, kit_end = tObject->mKdLeaves.end();
[1077]	1242
[1074]	1243	for (kit = tObject->mKdLeaves.begin(); kit != kit_end; ++ kit)
[1072]	1244	{
[1074]	1245	KdLeaf node = dynamic_cast<KdLeaf >(*kit);
[1072]	1246
[1074]	1247	if (ci.type == SortableEntry::ERayMin)
	1248	{
	1249	AddContriToPvs(node, pvsLeft);
	1250	}
	1251	else if (ci.type == SortableEntry::ERayMax)
	1252	{
	1253	RemoveContriFromPvs(node, pvsRight);
	1254	}
[1072]	1255	}
	1256	}
	1257	}
	1258	}
	1259
	1260
[1074]	1261	float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
	1262	const AxisAlignedBox3 &box,
	1263	int pvsSize,
	1264	const int axis,
	1265	float &position)
[1072]	1266	{
	1267	const float minBox = box.Min(axis);
	1268	const float maxBox = box.Max(axis);
	1269
	1270	const float sizeBox = maxBox - minBox;
	1271
	1272	const float minBand = minBox + mMinBand * sizeBox;
	1273	const float maxBand = minBox + mMaxBand * sizeBox;
	1274
	1275	SortSplitCandidates(rays, axis, minBand, maxBand);
	1276
[1077]	1277	// prepare the sweep
[1074]	1278	// (note: returns pvs size, so there would be no need
	1279	// to give pvs size as argument)
	1280	pvsSize = PrepareHeuristics(rays);
	1281
[1072]	1282	// go through the lists, count the number of objects left and right
	1283	// and evaluate the following cost funcion:
	1284	// C = ct_div_ci + (qlrl + qrrr)/queries
	1285
	1286	int pvsl = 0;
	1287	int pvsr = pvsSize;
	1288
	1289	int pvsBack = pvsl;
	1290	int pvsFront = pvsr;
	1291
	1292	float sum = (float)pvsSize * sizeBox;
	1293	float minSum = 1e20f;
	1294
	1295
	1296	// if no good split can be found, take mid split
	1297	position = minBox + 0.5f * sizeBox;
	1298
	1299	// the relative cost ratio
[1074]	1300	float ratio = 99999999.0f;
[1072]	1301	bool splitPlaneFound = false;
	1302
	1303	Intersectable::NewMail();
[1074]	1304	KdLeaf::NewMail();
[1072]	1305
	1306
[1074]	1307	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
[1072]	1308
[1074]	1309	//-- traverse through visibility events
	1310
	1311	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
[1072]	1312	{
[1074]	1313	EvalPvsIncr(*ci, pvsl, pvsr);
	1314
[1072]	1315	// Note: sufficient to compare size of bounding boxes of front and back side?
	1316	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	1317	{
	1318	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
	1319
[1074]	1320	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl;
[1072]	1321
	1322	if (sum < minSum)
	1323	{
	1324	splitPlaneFound = true;
	1325
	1326	minSum = sum;
	1327	position = (*ci).value;
	1328
	1329	pvsBack = pvsl;
	1330	pvsFront = pvsr;
	1331	}
	1332	}
	1333	}
	1334
[1074]	1335
[1072]	1336	// -- compute cost
	1337
	1338	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1339	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1340
	1341	const float pOverall = sizeBox;
	1342	const float pBack = position - minBox;
	1343	const float pFront = maxBox - position;
	1344
	1345	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	1346	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1347	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1348
	1349	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
	1350	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1351
	1352	if (splitPlaneFound)
	1353	{
	1354	ratio = newRenderCost / oldRenderCost;
	1355	}
[1074]	1356
[1072]	1357	//if (axis != 1)
[1074]	1358	Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1359	<<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
[1072]	1360
	1361	return ratio;
[1077]	1362	}
[1072]	1363
	1364
[1027]	1365	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
	1366	AxisAlignedPlane &plane,
	1367	float &pFront,
	1368	float &pBack)
[1002]	1369	{
	1370	float nPosition[3];
	1371	float nCostRatio[3];
	1372	float nProbFront[3];
	1373	float nProbBack[3];
	1374
	1375	// create bounding box of node geometry
[1006]	1376	AxisAlignedBox3 box = tData.mBoundingBox;
[1002]	1377
	1378	int sAxis = 0;
[1006]	1379	int bestAxis = -1;
[1002]	1380
	1381	// if we use some kind of specialised fixed axis
	1382	const bool useSpecialAxis =
[1023]	1383	mOnlyDrivingAxis \|\| mCirculatingAxis;
[1074]	1384	//Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
[1047]	1385	if (mCirculatingAxis)
	1386	{
	1387	int parentAxis = 0;
	1388	VspNode *parent = tData.mNode->GetParent();
[1002]	1389
[1047]	1390	if (parent)
	1391	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
[1027]	1392
	1393	sAxis = (parentAxis + 1) % 3;
[1047]	1394	}
[1002]	1395	else if (mOnlyDrivingAxis)
[1047]	1396	{
[1002]	1397	sAxis = box.Size().DrivingAxis();
[1047]	1398	}
[1106]	1399
[1047]	1400	for (int axis = 0; axis < 3; ++ axis)
[1002]	1401	{
	1402	if (!useSpecialAxis \|\| (axis == sAxis))
	1403	{
	1404	if (mUseCostHeuristics)
	1405	{
[1106]	1406	//-- place split plane using heuristics
[1002]	1407	nCostRatio[axis] =
[1027]	1408	EvalLocalCostHeuristics(*tData.mRays,
	1409	box,
[1002]	1410	tData.mPvs,
	1411	axis,
	1412	nPosition[axis]);
	1413	}
[1106]	1414	else
[1002]	1415	{
[1106]	1416	//-- split plane position is spatial median
[1002]	1417	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
[1027]	1418	nCostRatio[axis] = EvalLocalSplitCost(tData,
	1419	box,
	1420	axis,
	1421	nPosition[axis],
	1422	nProbFront[axis],
	1423	nProbBack[axis]);
[1002]	1424	}
	1425
[1006]	1426	if (bestAxis == -1)
[1002]	1427	{
[1006]	1428	bestAxis = axis;
[1002]	1429	}
[1006]	1430	else if (nCostRatio[axis] < nCostRatio[bestAxis])
[1002]	1431	{
[1006]	1432	bestAxis = axis;
[1002]	1433	}
	1434	}
	1435	}
	1436
[1047]	1437
[1108]	1438	//-- assign values of best split
[1047]	1439
[1006]	1440	plane.mAxis = bestAxis;
[1108]	1441	plane.mPosition = nPosition[bestAxis]; // split plane position
[1047]	1442
[1002]	1443	pFront = nProbFront[bestAxis];
	1444	pBack = nProbBack[bestAxis];
	1445
[1074]	1446	//Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1002]	1447	return nCostRatio[bestAxis];
	1448	}
	1449
	1450
[1016]	1451	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	1452	const VspTraversalData &data) const
[1002]	1453	{
[1047]	1454	#if 0
	1455	return (float)-data.mDepth;
[1027]	1456	#endif
[1002]	1457	float pvsFront = 0;
	1458	float pvsBack = 0;
	1459	float totalPvs = 0;
	1460
	1461	// probability that view point lies in back / front node
	1462	float pOverall = data.mProbability;
	1463	float pFront = 0;
	1464	float pBack = 0;
	1465
	1466
	1467	// create unique ids for pvs heuristics
[1089]	1468	Intersectable::NewMail();
[1002]	1469
[1016]	1470	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
[1015]	1471
[1016]	1472	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
[1002]	1473	{
[1015]	1474	RayInfo rayInf = *rit;
[1002]	1475
	1476	float t;
	1477	VssRay *ray = rayInf.mRay;
[1027]	1478
[1008]	1479	const int cf =
	1480	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
	1481	candidatePlane.mPosition, t);
[1002]	1482
	1483	// find front and back pvs for origing and termination object
	1484	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
	1485	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
	1486	}
	1487
[1027]	1488
[1011]	1489	AxisAlignedBox3 frontBox;
	1490	AxisAlignedBox3 backBox;
	1491
	1492	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
	1493
	1494	pFront = frontBox.GetVolume();
[1006]	1495	pBack = pOverall - pFront;
	1496
	1497
[1020]	1498	//-- pvs rendering heuristics
[1002]	1499	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1500	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1501
[1020]	1502	//-- only render cost heuristics or combined with standard deviation
	1503	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	1504	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	1505	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[1002]	1506
	1507	const float oldRenderCost = pOverall * penaltyOld;
	1508	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1509
	1510	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
[1020]	1511	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
[1002]	1512
[1020]	1513	// take render cost of node into account
	1514	// otherwise danger of being stuck in a local minimum!!
[1027]	1515	const float factor = 0.99f;
	1516
[1020]	1517	const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
[1027]	1518	return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
[1002]	1519	}
	1520
	1521
[1027]	1522	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
	1523	const AxisAlignedBox3 &box,
	1524	const int axis,
	1525	const float &position,
	1526	float &pFront,
	1527	float &pBack) const
[1002]	1528	{
	1529	float pvsTotal = 0;
	1530	float pvsFront = 0;
	1531	float pvsBack = 0;
	1532
	1533	// create unique ids for pvs heuristics
[1089]	1534	Intersectable::NewMail();
[1002]	1535
	1536	const int pvsSize = data.mPvs;
	1537
	1538	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
	1539
	1540	// this is the main ray classification loop!
	1541	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
	1542	{
	1543	// determine the side of this ray with respect to the plane
	1544	float t;
	1545	const int side = (*rit).ComputeRayIntersection(axis, position, t);
	1546
	1547	AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
	1548	AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
	1549	}
	1550
[1108]	1551	//-- cost heuristics
[1002]	1552	float pOverall;
[1027]	1553
[1002]	1554	pOverall = data.mProbability;
[1108]	1555
	1556	// we take simplified computation for spatial mid split
[1006]	1557	pBack = pFront = pOverall * 0.5f;
	1558
[1108]	1559	const float newCost = pvsBack * pBack + pvsFront * pFront;
	1560	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
[1006]	1561
[1002]	1562	#ifdef _DEBUG
	1563	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	1564	Debug << pFront << " " << pBack << " " << pOverall << endl;
	1565	#endif
	1566
	1567	return (mCtDivCi + newCost) / oldCost;
	1568	}
	1569
	1570
[1016]	1571	void VspTree::AddObjToPvs(Intersectable *obj,
[1027]	1572	const int cf,
	1573	float &frontPvs,
	1574	float &backPvs,
	1575	float &totalPvs) const
[1002]	1576	{
	1577	if (!obj)
	1578	return;
	1579
[1076]	1580	//const float renderCost = mViewCellsManager->EvalRenderCost(obj);
	1581	const int renderCost = 1;
[1002]	1582
[1089]	1583	// object in no pvs => new
	1584	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
[1002]	1585	{
	1586	totalPvs += renderCost;
	1587	}
	1588
	1589	// TODO: does this really belong to no pvs?
	1590	//if (cf == Ray::COINCIDENT) return;
	1591
[1089]	1592	if (cf >= 0) // front pvs
[1002]	1593	{
[1089]	1594	if (!obj->Mailed() && !obj->Mailed(2))
[1002]	1595	{
	1596	frontPvs += renderCost;
	1597
[1089]	1598	// already in back pvs => in both pvss
	1599	if (obj->Mailed(1))
	1600	obj->Mail(2);
[1002]	1601	else
[1089]	1602	obj->Mail();
[1002]	1603	}
	1604	}
	1605
[1089]	1606	if (cf <= 0) // back pvs
[1002]	1607	{
[1089]	1608	if (!obj->Mailed(1) && !obj->Mailed(2))
[1002]	1609	{
	1610	backPvs += renderCost;
	1611
[1089]	1612	// already in front pvs => in both pvss
	1613	if (obj->Mailed())
	1614	obj->Mail(2);
[1002]	1615	else
[1089]	1616	obj->Mail(1);
[1002]	1617	}
	1618	}
	1619	}
	1620
	1621
[1016]	1622	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
[1002]	1623	const bool onlyUnmailed,
	1624	const int maxPvsSize) const
	1625	{
[1008]	1626	stack<VspNode *> nodeStack;
[1002]	1627	nodeStack.push(mRoot);
	1628
	1629	while (!nodeStack.empty())
	1630	{
[1008]	1631	VspNode *node = nodeStack.top();
[1002]	1632	nodeStack.pop();
	1633
	1634	if (node->IsLeaf())
	1635	{
	1636	// test if this leaf is in valid view space
[1008]	1637	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1638	if (leaf->TreeValid() &&
	1639	(!onlyUnmailed \|\| !leaf->Mailed()) &&
	1640	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
	1641	{
	1642	leaves.push_back(leaf);
	1643	}
	1644	}
	1645	else
	1646	{
[1008]	1647	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1648
	1649	nodeStack.push(interior->GetBack());
	1650	nodeStack.push(interior->GetFront());
	1651	}
	1652	}
	1653	}
	1654
	1655
[1016]	1656	AxisAlignedBox3 VspTree::GetBoundingBox() const
[1002]	1657	{
[1020]	1658	return mBoundingBox;
[1002]	1659	}
	1660
	1661
[1016]	1662	VspNode *VspTree::GetRoot() const
[1002]	1663	{
	1664	return mRoot;
	1665	}
	1666
	1667
[1016]	1668	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
[1002]	1669	{
	1670	// the node became a leaf -> evaluate stats for leafs
[1008]	1671	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
[1002]	1672
	1673
[1008]	1674	if (data.mPvs > mVspStats.maxPvs)
[1002]	1675	{
[1008]	1676	mVspStats.maxPvs = data.mPvs;
[1002]	1677	}
	1678
[1008]	1679	mVspStats.pvs += data.mPvs;
[1002]	1680
[1008]	1681	if (data.mDepth < mVspStats.minDepth)
[1002]	1682	{
[1008]	1683	mVspStats.minDepth = data.mDepth;
[1002]	1684	}
	1685
	1686	if (data.mDepth >= mTermMaxDepth)
	1687	{
[1008]	1688	++ mVspStats.maxDepthNodes;
	1689	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
[1002]	1690	}
	1691
	1692	// accumulate rays to compute rays / leaf
[1008]	1693	mVspStats.accumRays += (int)data.mRays->size();
[1002]	1694
	1695	if (data.mPvs < mTermMinPvs)
[1008]	1696	++ mVspStats.minPvsNodes;
[1002]	1697
	1698	if ((int)data.mRays->size() < mTermMinRays)
[1008]	1699	++ mVspStats.minRaysNodes;
[1002]	1700
	1701	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
[1008]	1702	++ mVspStats.maxRayContribNodes;
[1002]	1703
	1704	if (data.mProbability <= mTermMinProbability)
[1008]	1705	++ mVspStats.minProbabilityNodes;
[1002]	1706
	1707	// accumulate depth to compute average depth
[1008]	1708	mVspStats.accumDepth += data.mDepth;
[1002]	1709
	1710	++ mCreatedViewCells;
	1711
[1074]	1712	#ifdef _DEBUG
[1002]	1713	Debug << "BSP stats: "
	1714	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	1715	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	1716	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1027]	1717	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
[1002]	1718	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
[1074]	1719	#endif
[1002]	1720	}
	1721
	1722
[1016]	1723	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
[1002]	1724	{
	1725	ViewCell::NewMail();
	1726	CollectViewCells(mRoot, onlyValid, viewCells, true);
	1727	}
	1728
	1729
[1016]	1730	void VspTree::CollapseViewCells()
[1002]	1731	{
[1111]	1732	// TODO matt
[1002]	1733	#if HAS_TO_BE_REDONE
[1008]	1734	stack<VspNode *> nodeStack;
[1002]	1735
	1736	if (!mRoot)
	1737	return;
	1738
	1739	nodeStack.push(mRoot);
	1740
	1741	while (!nodeStack.empty())
	1742	{
[1008]	1743	VspNode *node = nodeStack.top();
[1002]	1744	nodeStack.pop();
	1745
	1746	if (node->IsLeaf())
	1747	{
[1008]	1748	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1749
	1750	if (!viewCell->GetValid())
	1751	{
[1008]	1752	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1753
	1754	ViewCellContainer leaves;
	1755	mViewCellsTree->CollectLeaves(viewCell, leaves);
	1756
	1757	ViewCellContainer::const_iterator it, it_end = leaves.end();
	1758
	1759	for (it = leaves.begin(); it != it_end; ++ it)
	1760	{
[1008]	1761	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
[1002]	1762	l->SetViewCell(GetOrCreateOutOfBoundsCell());
[1008]	1763	++ mVspStats.invalidLeaves;
[1002]	1764	}
	1765
	1766	// add to unbounded view cell
	1767	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
	1768	DEL_PTR(viewCell);
	1769	}
	1770	}
	1771	else
	1772	{
[1008]	1773	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1774
	1775	nodeStack.push(interior->GetFront());
	1776	nodeStack.push(interior->GetBack());
	1777	}
	1778	}
	1779
[1008]	1780	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	1781	#endif
	1782	}
	1783
	1784
[1016]	1785	void VspTree::CollectRays(VssRayContainer &rays)
[1002]	1786	{
[1008]	1787	vector<VspLeaf *> leaves;
[1002]	1788
[1008]	1789	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
[1002]	1790
	1791	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	1792	{
[1008]	1793	VspLeaf leaf = lit;
[1002]	1794	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	1795
	1796	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	1797	rays.push_back(*rit);
	1798	}
	1799	}
	1800
	1801
[1021]	1802	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
	1803	{
	1804	mViewCellsManager = vcm;
	1805	}
	1806
	1807
[1016]	1808	void VspTree::ValidateTree()
[1002]	1809	{
[1020]	1810	mVspStats.invalidLeaves = 0;
	1811
[1008]	1812	stack<VspNode *> nodeStack;
[1002]	1813
	1814	if (!mRoot)
	1815	return;
	1816
	1817	nodeStack.push(mRoot);
[1020]	1818
[1002]	1819	while (!nodeStack.empty())
	1820	{
[1008]	1821	VspNode *node = nodeStack.top();
[1002]	1822	nodeStack.pop();
	1823
	1824	if (node->IsLeaf())
	1825	{
[1008]	1826	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1827
	1828	if (!leaf->GetViewCell()->GetValid())
[1008]	1829	++ mVspStats.invalidLeaves;
[1002]	1830
	1831	// validity flags don't match => repair
	1832	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
	1833	{
	1834	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
	1835	PropagateUpValidity(leaf);
	1836	}
	1837	}
	1838	else
	1839	{
[1008]	1840	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1841
	1842	nodeStack.push(interior->GetFront());
	1843	nodeStack.push(interior->GetBack());
	1844	}
	1845	}
	1846
[1008]	1847	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	1848	}
	1849
	1850
	1851
[1016]	1852	void VspTree::CollectViewCells(VspNode *root,
[1002]	1853	bool onlyValid,
	1854	ViewCellContainer &viewCells,
	1855	bool onlyUnmailed) const
	1856	{
[1008]	1857	stack<VspNode *> nodeStack;
[1002]	1858
	1859	if (!root)
	1860	return;
	1861
	1862	nodeStack.push(root);
	1863
	1864	while (!nodeStack.empty())
	1865	{
[1008]	1866	VspNode *node = nodeStack.top();
[1002]	1867	nodeStack.pop();
	1868
	1869	if (node->IsLeaf())
	1870	{
	1871	if (!onlyValid \|\| node->TreeValid())
	1872	{
[1008]	1873	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1874
	1875	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
	1876
	1877	if (!onlyUnmailed \|\| !viewCell->Mailed())
	1878	{
	1879	viewCell->Mail();
	1880	viewCells.push_back(viewCell);
	1881	}
	1882	}
	1883	}
	1884	else
	1885	{
[1008]	1886	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1887
	1888	nodeStack.push(interior->GetFront());
	1889	nodeStack.push(interior->GetBack());
	1890	}
	1891	}
	1892	}
	1893
	1894
[1016]	1895	int VspTree::FindNeighbors(VspLeaf *n,
[1020]	1896	vector<VspLeaf *> &neighbors,
	1897	const bool onlyUnmailed) const
[1002]	1898	{
[1012]	1899	stack<VspNode *> nodeStack;
	1900	nodeStack.push(mRoot);
[1002]	1901
[1012]	1902	const AxisAlignedBox3 box = GetBBox(n);
[1002]	1903
	1904	while (!nodeStack.empty())
	1905	{
[1008]	1906	VspNode *node = nodeStack.top();
[1002]	1907	nodeStack.pop();
	1908
	1909	if (node->IsLeaf())
	1910	{
[1012]	1911	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	1912
	1913	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
	1914	neighbors.push_back(leaf);
[1002]	1915	}
	1916	else
	1917	{
[1008]	1918	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	1919
	1920	if (interior->GetPosition() > box.Max(interior->GetAxis()))
	1921	nodeStack.push(interior->GetBack());
	1922	else
	1923	{
	1924	if (interior->GetPosition() < box.Min(interior->GetAxis()))
	1925	nodeStack.push(interior->GetFront());
	1926	else
	1927	{
	1928	// random decision
	1929	nodeStack.push(interior->GetBack());
	1930	nodeStack.push(interior->GetFront());
	1931	}
	1932	}
	1933	}
	1934	}
[1002]	1935
[1012]	1936	return (int)neighbors.size();
	1937	}
[1002]	1938
	1939
[1012]	1940	// Find random neighbor which was not mailed
[1016]	1941	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
[1012]	1942	{
	1943	stack<VspNode *> nodeStack;
	1944	nodeStack.push(mRoot);
	1945
	1946	int mask = rand();
	1947
	1948	while (!nodeStack.empty())
	1949	{
	1950	VspNode *node = nodeStack.top();
	1951
	1952	nodeStack.pop();
	1953
	1954	if (node->IsLeaf())
	1955	{
	1956	return dynamic_cast<VspLeaf *>(node);
	1957	}
	1958	else
	1959	{
	1960	VspInterior interior = dynamic_cast<VspInterior >(node);
	1961	VspNode *next;
	1962
	1963	if (GetBBox(interior->GetBack()).Side(plane) < 0)
[1027]	1964	{
[1002]	1965	next = interior->GetFront();
[1027]	1966	}
[1012]	1967	else
[1027]	1968	{
[1012]	1969	if (GetBBox(interior->GetFront()).Side(plane) < 0)
[1027]	1970	{
[1002]	1971	next = interior->GetBack();
[1027]	1972	}
[1012]	1973	else
	1974	{
	1975	// random decision
	1976	if (mask & 1)
	1977	next = interior->GetBack();
	1978	else
	1979	next = interior->GetFront();
	1980	mask = mask >> 1;
	1981	}
[1027]	1982	}
	1983
	1984	nodeStack.push(next);
[1002]	1985	}
	1986	}
[1012]	1987
[1002]	1988	return NULL;
	1989	}
	1990
	1991
[1016]	1992	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
[1002]	1993	{
[1008]	1994	stack<VspNode *> nodeStack;
[1002]	1995
	1996	nodeStack.push(mRoot);
	1997
	1998	int mask = rand();
	1999
	2000	while (!nodeStack.empty())
	2001	{
[1008]	2002	VspNode *node = nodeStack.top();
[1002]	2003	nodeStack.pop();
	2004
	2005	if (node->IsLeaf())
	2006	{
	2007	if ( (!onlyUnmailed \|\| !node->Mailed()) )
[1008]	2008	return dynamic_cast<VspLeaf *>(node);
[1002]	2009	}
	2010	else
	2011	{
[1008]	2012	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2013
	2014	// random decision
	2015	if (mask & 1)
	2016	nodeStack.push(interior->GetBack());
	2017	else
	2018	nodeStack.push(interior->GetFront());
	2019
	2020	mask = mask >> 1;
	2021	}
	2022	}
	2023
	2024	return NULL;
	2025	}
	2026
	2027
[1072]	2028	void VspTree::CollectPvs(const RayInfoContainer &rays,
	2029	ObjectContainer &objects) const
	2030	{
	2031	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2032
	2033	Intersectable::NewMail();
	2034
	2035	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2036	{
	2037	VssRay ray = (rit).mRay;
	2038
	2039	Intersectable *object;
	2040	object = ray->mOriginObject;
	2041
	2042	if (object)
	2043	{
	2044	if (!object->Mailed())
	2045	{
	2046	object->Mail();
	2047	objects.push_back(object);
	2048	}
	2049	}
	2050
	2051	object = ray->mTerminationObject;
	2052
	2053	if (object)
	2054	{
	2055	if (!object->Mailed())
	2056	{
	2057	object->Mail();
	2058	objects.push_back(object);
	2059	}
	2060	}
	2061	}
	2062	}
	2063
	2064
[1016]	2065	int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
[1002]	2066	{
	2067	int pvsSize = 0;
	2068
	2069	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2070
	2071	Intersectable::NewMail();
	2072
	2073	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2074	{
	2075	VssRay ray = (rit).mRay;
	2076
	2077	if (ray->mOriginObject)
	2078	{
	2079	if (!ray->mOriginObject->Mailed())
	2080	{
	2081	ray->mOriginObject->Mail();
	2082	++ pvsSize;
	2083	}
	2084	}
	2085	if (ray->mTerminationObject)
	2086	{
	2087	if (!ray->mTerminationObject->Mailed())
	2088	{
	2089	ray->mTerminationObject->Mail();
	2090	++ pvsSize;
	2091	}
	2092	}
	2093	}
	2094
	2095	return pvsSize;
	2096	}
	2097
	2098
[1016]	2099	float VspTree::GetEpsilon() const
[1002]	2100	{
	2101	return mEpsilon;
	2102	}
	2103
	2104
[1016]	2105	int VspTree::CastLineSegment(const Vector3 &origin,
[1027]	2106	const Vector3 &termination,
	2107	ViewCellContainer &viewcells)
[1002]	2108	{
	2109	int hits = 0;
	2110
	2111	float mint = 0.0f, maxt = 1.0f;
[1012]	2112	const Vector3 dir = termination - origin;
[1002]	2113
[1012]	2114	stack<LineTraversalData> tStack;
	2115
[1002]	2116	Intersectable::NewMail();
	2117	ViewCell::NewMail();
	2118
	2119	Vector3 entp = origin;
	2120	Vector3 extp = termination;
	2121
[1008]	2122	VspNode *node = mRoot;
[1012]	2123	VspNode *farChild;
[1002]	2124
[1012]	2125	float position;
	2126	int axis;
	2127
[1002]	2128	while (1)
	2129	{
	2130	if (!node->IsLeaf())
	2131	{
[1008]	2132	VspInterior in = dynamic_cast<VspInterior >(node);
[1012]	2133	position = in->GetPosition();
	2134	axis = in->GetAxis();
[1002]	2135
[1012]	2136	if (entp[axis] <= position)
[1002]	2137	{
[1012]	2138	if (extp[axis] <= position)
	2139	{
[1047]	2140	node = in->GetBack();
[1012]	2141	// cases N1,N2,N3,P5,Z2,Z3
[1002]	2142	continue;
[1012]	2143	} else
	2144	{
	2145	// case N4
[1047]	2146	node = in->GetBack();
	2147	farChild = in->GetFront();
[1012]	2148	}
	2149	}
	2150	else
[1002]	2151	{
[1012]	2152	if (position <= extp[axis])
	2153	{
[1047]	2154	node = in->GetFront();
[1012]	2155	// cases P1,P2,P3,N5,Z1
[1002]	2156	continue;
[1012]	2157	}
	2158	else
	2159	{
[1047]	2160	node = in->GetFront();
	2161	farChild = in->GetBack();
[1012]	2162	// case P4
	2163	}
[1002]	2164	}
	2165
[1012]	2166	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2167	// case N4 or P4
	2168	const float tdist = (position - origin[axis]) / dir[axis];
	2169	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
[1002]	2170
[1012]	2171	extp = origin + dir * tdist;
	2172	maxt = tdist;
	2173	}
[1002]	2174	else
	2175	{
[1012]	2176	// compute intersection with all objects in this leaf
[1008]	2177	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1012]	2178	ViewCell *vc = leaf->GetViewCell();
	2179
	2180	if (!vc->Mailed())
	2181	{
	2182	vc->Mail();
	2183	viewcells.push_back(vc);
	2184	++ hits;
	2185	}
	2186	#if 0
	2187	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
	2188	#endif
	2189	// get the next node from the stack
	2190	if (tStack.empty())
	2191	break;
	2192
	2193	entp = extp;
	2194	mint = maxt;
[1002]	2195
[1012]	2196	LineTraversalData &s = tStack.top();
	2197	node = s.mNode;
	2198	extp = s.mExitPoint;
	2199	maxt = s.mMaxT;
	2200	tStack.pop();
	2201	}
	2202	}
	2203
	2204	return hits;
	2205	}
	2206
	2207
[1016]	2208	int VspTree::CastRay(Ray &ray)
[1012]	2209	{
	2210	int hits = 0;
	2211
	2212	stack<LineTraversalData> tStack;
	2213	const Vector3 dir = ray.GetDir();
	2214
	2215	float maxt, mint;
	2216
[1020]	2217	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
[1012]	2218	return 0;
	2219
	2220	Intersectable::NewMail();
	2221	ViewCell::NewMail();
	2222
	2223	Vector3 entp = ray.Extrap(mint);
	2224	Vector3 extp = ray.Extrap(maxt);
	2225
	2226	const Vector3 origin = entp;
	2227
	2228	VspNode *node = mRoot;
	2229	VspNode *farChild = NULL;
	2230
	2231	float position;
	2232	int axis;
	2233
	2234	while (1)
	2235	{
	2236	if (!node->IsLeaf())
	2237	{
	2238	VspInterior in = dynamic_cast<VspInterior >(node);
	2239	position = in->GetPosition();
	2240	axis = in->GetAxis();
	2241
	2242	if (entp[axis] <= position)
	2243	{
	2244	if (extp[axis] <= position)
	2245	{
	2246	node = in->GetBack();
	2247	// cases N1,N2,N3,P5,Z2,Z3
	2248	continue;
[1020]	2249	}
	2250	else
[1012]	2251	{
	2252	// case N4
	2253	node = in->GetBack();
	2254	farChild = in->GetFront();
	2255	}
	2256	}
[1002]	2257	else
[1012]	2258	{
	2259	if (position <= extp[axis])
	2260	{
	2261	node = in->GetFront();
	2262	// cases P1,P2,P3,N5,Z1
	2263	continue;
	2264	}
	2265	else
	2266	{
	2267	node = in->GetFront();
	2268	farChild = in->GetBack();
	2269	// case P4
	2270	}
	2271	}
[1002]	2272
[1012]	2273	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2274	// case N4 or P4
	2275	const float tdist = (position - origin[axis]) / dir[axis];
	2276	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
	2277	extp = origin + dir * tdist;
	2278	maxt = tdist;
	2279	}
	2280	else
	2281	{
	2282	// compute intersection with all objects in this leaf
	2283	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	2284	ViewCell *vc = leaf->GetViewCell();
	2285
	2286	if (!vc->Mailed())
[1002]	2287	{
[1012]	2288	vc->Mail();
	2289	// todo: add view cells to ray
[1002]	2290	++ hits;
	2291	}
[1012]	2292	#if 0
[1020]	2293	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
[1012]	2294	#endif
	2295	// get the next node from the stack
[1002]	2296	if (tStack.empty())
	2297	break;
	2298
	2299	entp = extp;
[1012]	2300	mint = maxt;
[1002]	2301
[1012]	2302	LineTraversalData &s = tStack.top();
[1002]	2303	node = s.mNode;
	2304	extp = s.mExitPoint;
[1012]	2305	maxt = s.mMaxT;
[1002]	2306	tStack.pop();
	2307	}
	2308	}
[1012]	2309
[1002]	2310	return hits;
	2311	}
	2312
	2313
[1016]	2314	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
[1002]	2315	{
	2316	if (mRoot == NULL)
	2317	return NULL;
	2318
[1008]	2319	stack<VspNode *> nodeStack;
[1002]	2320	nodeStack.push(mRoot);
	2321
	2322	ViewCellLeaf *viewcell = NULL;
	2323
	2324	while (!nodeStack.empty())
	2325	{
[1008]	2326	VspNode *node = nodeStack.top();
[1002]	2327	nodeStack.pop();
	2328
	2329	if (node->IsLeaf())
	2330	{
[1008]	2331	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
[1002]	2332	break;
	2333	}
	2334	else
	2335	{
[1008]	2336	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	2337
[1002]	2338	// random decision
[1012]	2339	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
[1002]	2340	nodeStack.push(interior->GetBack());
	2341	else
	2342	nodeStack.push(interior->GetFront());
	2343	}
	2344	}
	2345
	2346	if (active)
	2347	return mViewCellsTree->GetActiveViewCell(viewcell);
	2348	else
	2349	return viewcell;
	2350	}
	2351
	2352
[1016]	2353	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
[1002]	2354	{
[1008]	2355	VspNode *node = mRoot;
[1002]	2356
	2357	while (1)
	2358	{
	2359	// early exit
	2360	if (node->TreeValid())
	2361	return true;
	2362
	2363	if (node->IsLeaf())
	2364	return false;
	2365
[1008]	2366	VspInterior in = dynamic_cast<VspInterior >(node);
[1002]	2367
[1012]	2368	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
[1002]	2369	{
	2370	node = in->GetBack();
	2371	}
	2372	else
	2373	{
	2374	node = in->GetFront();
	2375	}
	2376	}
[1012]	2377
[1002]	2378	// should never come here
	2379	return false;
	2380	}
	2381
	2382
[1016]	2383	void VspTree::PropagateUpValidity(VspNode *node)
[1002]	2384	{
	2385	const bool isValid = node->TreeValid();
	2386
	2387	// propagative up invalid flag until only invalid nodes exist over this node
	2388	if (!isValid)
	2389	{
	2390	while (!node->IsRoot() && node->GetParent()->TreeValid())
	2391	{
	2392	node = node->GetParent();
	2393	node->SetTreeValid(false);
	2394	}
	2395	}
	2396	else
	2397	{
	2398	// propagative up valid flag until one of the subtrees is invalid
	2399	while (!node->IsRoot() && !node->TreeValid())
	2400	{
	2401	node = node->GetParent();
[1008]	2402	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2403
	2404	// the parent is valid iff both leaves are valid
	2405	node->SetTreeValid(interior->GetBack()->TreeValid() &&
	2406	interior->GetFront()->TreeValid());
	2407	}
	2408	}
	2409	}
	2410
	2411	#if ZIPPED_VIEWCELLS
[1016]	2412	bool VspTree::Export(ogzstream &stream)
[1002]	2413	#else
[1016]	2414	bool VspTree::Export(ofstream &stream)
[1002]	2415	#endif
	2416	{
	2417	ExportNode(mRoot, stream);
	2418
	2419	return true;
	2420	}
	2421
[1006]	2422
[1002]	2423	#if ZIPPED_VIEWCELLS
[1016]	2424	void VspTree::ExportNode(VspNode *node, ogzstream &stream)
[1002]	2425	#else
[1016]	2426	void VspTree::ExportNode(VspNode *node, ofstream &stream)
[1002]	2427	#endif
	2428	{
	2429	if (node->IsLeaf())
	2430	{
[1008]	2431	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	2432	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
	2433
	2434	int id = -1;
	2435	if (viewCell != mOutOfBoundsCell)
	2436	id = viewCell->GetId();
	2437
	2438	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
	2439	}
	2440	else
[1012]	2441	{
[1008]	2442	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2443
[1012]	2444	AxisAlignedPlane plane = interior->GetPlane();
	2445	stream << "<Interior plane=\"" << plane.mPosition << " "
	2446	<< plane.mAxis << "\">" << endl;
[1002]	2447
	2448	ExportNode(interior->GetBack(), stream);
	2449	ExportNode(interior->GetFront(), stream);
[1012]	2450
[1002]	2451	stream << "</Interior>" << endl;
	2452	}
	2453	}
	2454
[1011]	2455
[1016]	2456	int VspTree::SplitRays(const AxisAlignedPlane &plane,
[1020]	2457	RayInfoContainer &rays,
	2458	RayInfoContainer &frontRays,
	2459	RayInfoContainer &backRays) const
[1011]	2460	{
	2461	int splits = 0;
	2462
	2463	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2464
	2465	for (rit = rays.begin(); rit != rit_end; ++ rit)
	2466	{
	2467	RayInfo bRay = *rit;
	2468
	2469	VssRay *ray = bRay.mRay;
	2470	float t;
	2471
	2472	// get classification and receive new t
	2473	//-- test if start point behind or in front of plane
[1047]	2474	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
	2475
	2476
[1027]	2477	#if 1
[1011]	2478	if (side == 0)
	2479	{
	2480	++ splits;
	2481
	2482	if (ray->HasPosDir(plane.mAxis))
	2483	{
	2484	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2485	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2486	}
	2487	else
	2488	{
	2489	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2490	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2491	}
	2492	}
	2493	else if (side == 1)
	2494	{
	2495	frontRays.push_back(bRay);
	2496	}
	2497	else
	2498	{
	2499	backRays.push_back(bRay);
	2500	}
[1027]	2501	#else
	2502	if (side == 0)
	2503	{
	2504	++ splits;
[1011]	2505
[1027]	2506	if (ray->HasPosDir(plane.mAxis))
	2507	{
	2508	backRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
	2509	frontRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
	2510	}
	2511	else
	2512	{
	2513	frontRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
	2514	backRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
	2515	}
	2516	}
	2517	else if (side == 1)
	2518	{
	2519	backRays.push_back(bRay);
	2520	}
	2521	else
	2522	{
	2523	frontRays.push_back(bRay);
	2524
	2525	}
	2526	#endif
[1011]	2527	}
	2528
	2529	return splits;
	2530	}
	2531
[1012]	2532
[1016]	2533	AxisAlignedBox3 VspTree::GetBBox(VspNode *node) const
[1012]	2534	{
	2535	if (!node->GetParent())
[1020]	2536	return mBoundingBox;
[1012]	2537
	2538	if (!node->IsLeaf())
	2539	{
[1016]	2540	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
[1012]	2541	}
	2542
	2543	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
	2544
[1016]	2545	AxisAlignedBox3 box(parent->GetBoundingBox());
[1012]	2546
[1047]	2547	if (parent->GetFront() == node)
	2548	box.SetMin(parent->GetAxis(), parent->GetPosition());
	2549	else
	2550	box.SetMax(parent->GetAxis(), parent->GetPosition());
[1012]	2551
	2552	return box;
	2553	}
	2554
	2555
[1020]	2556
[1021]	2557
	2558	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
	2559	ViewCellContainer &viewCells) const
	2560	{
[1027]	2561	stack<VspNode *> nodeStack;
	2562
[1021]	2563	ViewCell::NewMail();
	2564
	2565	while (!nodeStack.empty())
	2566	{
[1027]	2567	VspNode *node = nodeStack.top();
[1021]	2568	nodeStack.pop();
	2569
[1027]	2570	const AxisAlignedBox3 bbox = GetBBox(node);
	2571
	2572	if (bbox.Includes(box))
[1021]	2573	{
	2574	// node geometry is contained in box
	2575	CollectViewCells(node, true, viewCells, true);
[1027]	2576	}
	2577	else if (Overlap(bbox, box))
	2578	{
[1021]	2579	if (node->IsLeaf())
	2580	{
	2581	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2582
	2583	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
	2584	{
	2585	leaf->GetViewCell()->Mail();
	2586	viewCells.push_back(leaf->GetViewCell());
	2587	}
	2588	}
	2589	else
	2590	{
[1027]	2591	VspInterior interior = dynamic_cast<VspInterior >(node);
[1021]	2592
[1027]	2593	VspNode *first = interior->GetFront();
	2594	VspNode *second = interior->GetBack();
[1021]	2595
[1027]	2596	nodeStack.push(first);
	2597	nodeStack.push(second);
[1021]	2598	}
[1027]	2599	}
	2600	// default: cull
[1021]	2601	}
	2602
	2603	return (int)viewCells.size();
	2604	}
	2605
	2606
	2607
[1016]	2608	/*****************************************************************/
[1021]	2609	/* class OspTree implementation */
[1016]	2610	/*****************************************************************/
	2611
[1027]	2612
[1022]	2613	OspTree::OspTree():
[1099]	2614	mRoot(NULL),
[1022]	2615	mTimeStamp(1)
	2616	{
[1106]	2617
[1022]	2618	bool randomize = false;
	2619	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
	2620	if (randomize)
	2621	Randomize(); // initialise random generator for heuristics
[1020]	2622
[1022]	2623	//-- termination criteria for autopartition
[1106]	2624	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
	2625	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
	2626	Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
	2627	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
[1023]	2628
[1106]	2629	Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
	2630
[1022]	2631	//-- max cost ratio for early tree termination
[1106]	2632	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[1022]	2633
[1106]	2634	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	2635	Environment::GetSingleton()->GetIntValue("OspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
[1022]	2636
	2637
	2638	//-- factors for bsp tree split plane heuristics
[1106]	2639	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
[1022]	2640
	2641	//-- partition criteria
[1106]	2642	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
[1022]	2643
	2644	// if only the driving axis is used for axis aligned split
[1106]	2645	Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[1022]	2646
[1106]	2647	Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
[1022]	2648
[1106]	2649	Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
[1023]	2650
	2651
[1022]	2652	char subdivisionStatsLog[100];
[1106]	2653	Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
[1022]	2654	mSubdivisionStats.open(subdivisionStatsLog);
	2655
[1106]	2656	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
	2657	//mSplitBorder = 0.1f;
[1022]	2658
[1084]	2659
[1022]	2660	//-- debug output
	2661
[1076]	2662	Debug << "***** OSP options ****** " << endl;
[1106]	2663
[1022]	2664	Debug << "max depth: " << mTermMaxDepth << endl;
	2665	Debug << "min probabiliy: " << mTermMinProbability << endl;
[1106]	2666	Debug << "min objects: " << mTermMinObjects << endl;
[1022]	2667	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	2668	Debug << "miss tolerance: " << mTermMissTolerance << endl;
[1106]	2669	Debug << "max leaves: " << mTermMaxLeaves << endl;
	2670
[1022]	2671	Debug << "randomize: " << randomize << endl;
	2672
	2673	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	2674	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	2675	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	2676	Debug << "max memory: " << mMaxMemory << endl;
	2677	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	2678	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1023]	2679
[1106]	2680	Debug << "split borders: " << mSplitBorder << endl;
[1022]	2681
[1106]	2682
[1022]	2683	mSplitCandidates = new vector<SortableEntry>;
	2684
	2685	Debug << endl;
	2686	}
	2687
	2688
	2689
[1020]	2690	void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
	2691	const ObjectContainer &objects,
[1106]	2692	ObjectContainer &front,
	2693	ObjectContainer &back)
[1016]	2694	{
[1020]	2695	ObjectContainer::const_iterator oit, oit_end = objects.end();
	2696
	2697	for (oit = objects.begin(); oit != oit_end; ++ oit)
	2698	{
	2699	// determine the side of this ray with respect to the plane
	2700	const AxisAlignedBox3 box = (*oit)->GetBox();
	2701
	2702	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
	2703	front.push_back(*oit);
	2704
	2705	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
	2706	back.push_back(*oit);
	2707	}
[1106]	2708
	2709	mOspStats.objectRefs -= (int)objects.size();
	2710	mOspStats.objectRefs += (int)back.size() + (int)front.size();
[1016]	2711	}
	2712
	2713
[1106]	2714	KdInterior *OspTree::SubdivideNode(
[1020]	2715	const AxisAlignedPlane &splitPlane,
[1108]	2716	const OspTraversalData &tData,
[1106]	2717	OspTraversalData &frontData,
	2718	OspTraversalData &backData
	2719	)
[1016]	2720	{
[1108]	2721	KdLeaf *leaf = tData.mNode;
	2722
	2723	// two new leaves
[1106]	2724	mOspStats.nodes += 2;
[1016]	2725
[1020]	2726	// add the new nodes to the tree
	2727	KdInterior *node = new KdInterior(leaf->mParent);
	2728
	2729	const int axis = splitPlane.mAxis;
	2730	const float position = splitPlane.mPosition;
	2731
	2732	node->mAxis = axis;
	2733	node->mPosition = position;
[1108]	2734	node->mBox = tData.mBoundingBox;
[1020]	2735
[1108]	2736
	2737	//-- the front and back traversal data is filled with the new values
	2738
	2739	// bounding boxes: split front and back node geometry
	2740	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
	2741	frontData.mBoundingBox, backData.mBoundingBox);
	2742
	2743	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
	2744
	2745	// TODO matt: compute pvs
	2746	frontData.mPvs = 999; // ComputePvsSize(*frontData.mRays);
	2747	backData.mPvs = -999; //ComputePvsSize(*backData.mRays);
	2748
	2749	frontData.mProbability = frontData.mBoundingBox.GetVolume();
	2750
	2751
	2752	// classify objects
[1020]	2753	int objectsBack = 0;
	2754	int objectsFront = 0;
	2755
	2756	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
	2757
	2758	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
	2759	{
	2760	// determine the side of this ray with respect to the plane
	2761	const AxisAlignedBox3 box = (*mi)->GetBox();
	2762
	2763	if (box.Max(axis) > position)
	2764	++ objectsFront;
	2765
	2766	if (box.Min(axis) < position)
	2767	++ objectsBack;
	2768	}
	2769
	2770	KdLeaf *back = new KdLeaf(node, objectsBack);
	2771	KdLeaf *front = new KdLeaf(node, objectsFront);
	2772
[1106]	2773	/////////////
	2774	//-- create front and back leaf
	2775
	2776	KdInterior *parent = leaf->mParent;
	2777
[1020]	2778	// replace a link from node's parent
[1106]	2779	if (parent)
	2780	{
	2781	parent->ReplaceChildLink(leaf, node);
	2782	node->mParent = parent;
	2783	}
	2784	else // new root
	2785	{
	2786	mRoot = node;
	2787	}
[1020]	2788
	2789	// and setup child links
	2790	node->SetupChildLinks(back, front);
	2791
[1106]	2792	SplitObjects(splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
[1089]	2793
	2794	ProcessLeafObjects(back, leaf);
	2795	ProcessLeafObjects(front, leaf);
[1020]	2796
[1106]	2797	backData.mNode = back;
	2798	frontData.mNode = front;
	2799
[1020]	2800	//delete leaf;
	2801	return node;
[1016]	2802	}
	2803
	2804
[1020]	2805	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
	2806	OspSplitCandidate &splitCandidate,
	2807	const bool globalCriteriaMet)
[1108]	2808	{
[1020]	2809	OspTraversalData &tData = splitCandidate.mParentData;
	2810	KdNode *newNode = tData.mNode;
[1016]	2811
[1020]	2812	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	2813	{
	2814	OspTraversalData tFrontData;
	2815	OspTraversalData tBackData;
[1108]	2816
[1020]	2817	//-- continue subdivision
	2818
	2819	// create new interior node and two leaf node
	2820	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
[1027]	2821
[1108]	2822	newNode = SubdivideNode(splitPlane,
	2823	tData,
[1106]	2824	tFrontData,
	2825	tBackData);
[1020]	2826
	2827	const int maxCostMisses = splitCandidate.mMaxCostMisses;
[1016]	2828
[1020]	2829	// how often was max cost ratio missed in this branch?
	2830	tFrontData.mMaxCostMisses = maxCostMisses;
	2831	tBackData.mMaxCostMisses = maxCostMisses;
	2832
	2833	//-- push the new split candidates on the queue
[1099]	2834	OspSplitCandidate *frontCandidate = new OspSplitCandidate(tFrontData);
	2835	OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData);
[1016]	2836
[1099]	2837	EvalSplitCandidate(*frontCandidate);
	2838	EvalSplitCandidate(*backCandidate);
[1016]	2839
[1099]	2840	tQueue.Push(frontCandidate);
	2841	tQueue.Push(backCandidate);
[1020]	2842
	2843	// delete old leaf node
	2844	DEL_PTR(tData.mNode);
[1109]	2845	DEL_PTR(tData.mNode->mViewCell);
[1020]	2846	}
	2847
	2848
	2849	//-- terminate traversal
	2850	if (newNode->IsLeaf())
	2851	{
	2852	EvaluateLeafStats(tData);
	2853	}
[1108]	2854
[1020]	2855	//-- cleanup
	2856	tData.Clear();
[1108]	2857
[1020]	2858	return newNode;
	2859	}
[1016]	2860
	2861
[1099]	2862	void OspTree::EvalSplitCandidate(OspSplitCandidate &splitCandidate)
[1020]	2863	{
	2864	float frontProb;
[1089]	2865	float backProb;
[1020]	2866
	2867	// compute locally best split plane
[1084]	2868	const bool success =
[1099]	2869	SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
[1020]	2870
[1106]	2871	const float priority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, splitCandidate.mParentData);
[1020]	2872	// compute global decrease in render cost
[1106]	2873	splitCandidate.SetPriority(priority);
	2874
	2875	splitCandidate.mMaxCostMisses =
	2876	success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
[1016]	2877	}
	2878
	2879
[1021]	2880	bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
	2881	{
	2882	// matt: TODO
[1106]	2883	return (
	2884	//(data.mNode->mObjects.size() < mTermMinObjects) \|\|
	2885	//(data.mProbability <= mTermMinProbability) \|\|
	2886	(data.mDepth >= mTermMaxDepth)
	2887	);
[1021]	2888	}
[1020]	2889
[1021]	2890
	2891	bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
	2892	{
	2893	// matt: TODO
[1106]	2894	Debug << "here888 " << mTermMaxLeaves << " " << mOspStats.Leaves() << endl;
	2895	return (
	2896	(mOspStats.Leaves() >= mTermMaxLeaves)
	2897	//mOutOfMemory \|\|
	2898	//(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
	2899	);
[1021]	2900	}
	2901
	2902
	2903	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
	2904	{
	2905	// the node became a leaf -> evaluate stats for leafs
[1106]	2906	KdLeaf *leaf = data.mNode;
[1021]	2907
[1106]	2908	if (data.mPvs > mOspStats.maxPvs)
[1021]	2909	{
[1106]	2910	mOspStats.maxPvs = data.mPvs;
[1021]	2911	}
	2912
[1106]	2913	mOspStats.pvs += data.mPvs;
[1021]	2914
[1106]	2915	if (data.mDepth < mOspStats.minDepth)
[1021]	2916	{
[1106]	2917	mOspStats.minDepth = data.mDepth;
[1021]	2918	}
	2919
	2920	if (data.mDepth >= mTermMaxDepth)
	2921	{
[1106]	2922	++ mOspStats.maxDepthNodes;
[1021]	2923	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
	2924	}
	2925
[1106]	2926	// if (data.mPvs < mTermMinPvs)
	2927	// ++ mOspStats.minPvsNodes;
[1021]	2928
	2929	if (data.mProbability <= mTermMinProbability)
[1106]	2930	++ mOspStats.minProbabilityNodes;
[1021]	2931
	2932	// accumulate depth to compute average depth
[1106]	2933	mOspStats.accumDepth += data.mDepth;
[1021]	2934
[1106]	2935	++ mCreatedLeaves;
[1021]	2936
	2937	#ifdef _DEBUG
	2938	Debug << "BSP stats: "
	2939	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
[1106]	2940	// << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	2941	<< "Prob: " << data.mProbability << " (min: " << mTermMinProbability << "), "
	2942	<< "#pvs: " << data.mPvs << ")\n";
[1021]	2943	#endif
	2944	}
	2945
	2946
[1084]	2947	float OspTree::EvalLocalCostHeuristics(KdLeaf *node,
[1077]	2948	const AxisAlignedBox3 &box,
	2949	const int axis,
[1084]	2950	float &position,
[1106]	2951	int &objectsFront,
	2952	int &objectsBack)
[1077]	2953	{
[1084]	2954
	2955	SortSplitCandidates(node, axis);
	2956
	2957	// go through the lists, count the number of objects left and right
	2958	// and evaluate the following cost funcion:
	2959	// C = ct_div_ci + (ol + or)/queries
	2960
[1106]	2961	int pvsSize = PrepareHeuristics(node->mObjects);
[1084]	2962	int pvsl = 0, pvsr = pvsSize;
	2963
[1077]	2964	const float minBox = box.Min(axis);
	2965	const float maxBox = box.Max(axis);
[1072]	2966
[1077]	2967	const float sizeBox = maxBox - minBox;
	2968
[1084]	2969
[1077]	2970	// if no good split can be found, take mid split
	2971	position = minBox + 0.5f * sizeBox;
	2972
	2973	// the relative cost ratio
	2974	float ratio = 99999999.0f;
	2975	bool splitPlaneFound = false;
[1084]	2976
	2977	float minBand = minBox + mSplitBorder * (maxBox - minBox);
	2978	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
[1077]	2979
[1084]	2980	float minSum = 1e20f;
[1077]	2981
[1084]	2982	int pvsBack = pvsl;
	2983	int pvsFront = pvsr;
[1077]	2984
[1084]	2985	float sum = (float)pvsSize * sizeBox;
	2986
[1077]	2987	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
	2988
	2989	//-- traverse through visibility events
	2990	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
	2991	{
	2992	EvalPvsIncr(*ci, pvsl, pvsr);
	2993
	2994	// Note: sufficient to compare size of bounding boxes of front and back side?
	2995	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	2996	{
	2997	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
	2998
	2999	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl;
	3000
	3001	if (sum < minSum)
	3002	{
	3003	splitPlaneFound = true;
	3004
	3005	minSum = sum;
	3006	position = (*ci).value;
	3007
	3008	pvsBack = pvsl;
	3009	pvsFront = pvsr;
	3010	}
	3011	}
	3012	}
	3013
	3014
	3015	// -- compute cost
	3016
	3017	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	3018	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	3019
	3020	const float pOverall = sizeBox;
	3021	const float pBack = position - minBox;
	3022	const float pFront = maxBox - position;
	3023
	3024	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	3025	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	3026	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	3027
	3028	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
	3029	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	3030
	3031	if (splitPlaneFound)
	3032	{
	3033	ratio = newRenderCost / oldRenderCost;
	3034	}
	3035
	3036	//if (axis != 1)
	3037	Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	3038	<<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
	3039
	3040	return ratio;
	3041	}
	3042
[1084]	3043	void OspTree::SortSplitCandidates(KdLeaf *node, const int axis)
[1077]	3044	{
[1084]	3045	mSplitCandidates->clear();
[1077]	3046
[1084]	3047	int requestedSize = 2*(int)node->mObjects.size();
[1077]	3048
[1084]	3049	// creates a sorted split candidates array
	3050	if (mSplitCandidates->capacity() > 500000 &&
	3051	requestedSize < (int)(mSplitCandidates->capacity()/10))
[1077]	3052	{
[1084]	3053	delete mSplitCandidates;
	3054	mSplitCandidates = new vector<SortableEntry>;
[1077]	3055	}
	3056
[1084]	3057	mSplitCandidates->reserve(requestedSize);
[1077]	3058
[1084]	3059	ObjectContainer::const_iterator mi, mi_end = node->mObjects.end();
[1077]	3060
[1084]	3061	// insert all queries
	3062	for(mi = node->mObjects.begin(); mi != mi_end; ++ mi)
[1077]	3063	{
[1084]	3064	AxisAlignedBox3 box = (*mi)->GetBox();
[1077]	3065
[1084]	3066	mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN,
	3067	box.Min(axis), *mi));
[1077]	3068
	3069
[1084]	3070	mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX,
	3071	box.Max(axis), *mi));
[1077]	3072	}
	3073
[1084]	3074	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
[1077]	3075	}
	3076
	3077
	3078
	3079	int OspTree::PrepareHeuristics(Intersectable *object)
	3080	{
[1106]	3081	#if COUNT_OBJECTS
	3082	return 1;
	3083	#else
[1108]	3084	// the priotity of the object is the number of view cell pvs entries of the object
	3085	return object->mViewCellPvs.GetSize();
[1106]	3086	#endif
[1077]	3087	}
	3088
	3089
[1084]	3090	int OspTree::PrepareHeuristics(const ObjectContainer &objects)
[1077]	3091	{
	3092	Intersectable::NewMail();
[1084]	3093	ViewCell::NewMail();
[1077]	3094
	3095	int pvsSize = 0;
	3096
[1084]	3097	ObjectContainer::const_iterator oit, oit_end = objects.end();
[1077]	3098
[1084]	3099	//-- set all pvs as belonging to the front pvs
	3100	for (oit = objects.begin(); oit != oit_end; ++ oit)
[1077]	3101	{
[1084]	3102	Intersectable obj = oit;
	3103	pvsSize += PrepareHeuristics(obj);
[1077]	3104	}
	3105
	3106	return pvsSize;
	3107	}
	3108
	3109
	3110	void OspTree::EvalPvsIncr(const SortableEntry &ci,
	3111	int &pvsLeft,
	3112	int &pvsRight) const
	3113	{
	3114	Intersectable *obj = ci.mObject;
	3115
	3116	switch (ci.type)
	3117	{
	3118	case SortableEntry::BOX_MIN:
	3119	AddContriToPvs(obj, pvsLeft);
	3120	break;
	3121
	3122	case SortableEntry::BOX_MAX:
	3123	RemoveContriFromPvs(obj, pvsRight);
	3124	break;
	3125	}
	3126	}
	3127
	3128
[1106]	3129	void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
	3130	{
	3131	mViewCellsManager = vcm;
	3132	}
	3133
	3134
	3135	AxisAlignedBox3 OspTree::GetBoundingBox() const
	3136	{
	3137	return mBoundingBox;
	3138	}
	3139
	3140
[1077]	3141	void OspTree::RemoveContriFromPvs(Intersectable *object, int &pvs) const
	3142	{
[1106]	3143	#if COUNT_OBJECTS
	3144	-- pvs;
	3145	#else
[1108]	3146	// the cost of an object is the number of view cells it is part of
	3147	pvs -= object->mViewCellPvs.GetSize();
[1106]	3148	#endif
[1077]	3149	}
	3150
	3151
	3152	void OspTree::AddContriToPvs(Intersectable *object, int &pvs) const
	3153	{
[1106]	3154	#if COUNT_OBJECTS
	3155	++ pvs;
	3156	#else
[1108]	3157	// the cost of an object is the number of view cells it is part of
	3158	pvs += object->mViewCellPvs.GetSize();
[1106]	3159	#endif
[1077]	3160	}
	3161
	3162
[1089]	3163	float OspTree::SelectSplitPlane(const OspTraversalData &tData,
[1084]	3164	AxisAlignedPlane &plane,
	3165	float &pFront,
	3166	float &pBack)
	3167	{
	3168	float nPosition[3];
	3169	float nCostRatio[3];
	3170	float nProbFront[3];
	3171	float nProbBack[3];
	3172
	3173	// create bounding box of node geometry
	3174	AxisAlignedBox3 box = tData.mBoundingBox;
	3175
	3176	int sAxis = 0;
	3177	int bestAxis = -1;
	3178
	3179	if (mOnlyDrivingAxis)
	3180	{
	3181	sAxis = box.Size().DrivingAxis();
	3182	}
	3183
[1106]	3184	// -- evaluate split cost for all three axis
[1084]	3185	for (int axis = 0; axis < 3; ++ axis)
	3186	{
	3187	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
	3188	{
[1106]	3189	if (1 \|\| mUseCostHeuristics)
	3190	{
	3191	//-- place split plane using heuristics
	3192	int objectsFront, objectsBack;
[1084]	3193
	3194	nCostRatio[axis] =
[1106]	3195	EvalLocalCostHeuristics(tData.mNode,
	3196	tData.mBoundingBox,
	3197	axis,
	3198	nPosition[axis],
	3199	objectsFront,
	3200	objectsBack);
[1084]	3201	}
[1106]	3202	/* else
[1084]	3203	{
[1106]	3204	//-- split plane position is spatial median
	3205
[1084]	3206	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	3207
	3208	nCostRatio[axis] = EvalLocalSplitCost(tData,
	3209	box,
	3210	axis,
	3211	nPosition[axis],
	3212	nProbFront[axis],
	3213	nProbBack[axis]);
[1106]	3214	}*/
[1084]	3215
	3216	if (bestAxis == -1)
	3217	{
	3218	bestAxis = axis;
	3219	}
	3220	else if (nCostRatio[axis] < nCostRatio[bestAxis])
	3221	{
	3222	bestAxis = axis;
	3223	}
	3224	}
	3225	}
	3226
	3227	//-- assign values
[1106]	3228
[1084]	3229	plane.mAxis = bestAxis;
	3230	// split plane position
	3231	plane.mPosition = nPosition[bestAxis];
	3232
	3233	pFront = nProbFront[bestAxis];
	3234	pBack = nProbBack[bestAxis];
	3235
	3236	//Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
	3237	return nCostRatio[bestAxis];
	3238	}
	3239
	3240
[1089]	3241	float OspTree::EvalViewCellPvsIncr(Intersectable *object) const
	3242	{
[1106]	3243	// TODO
	3244	return 1;
[1089]	3245	}
	3246
	3247
	3248	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	3249	const OspTraversalData &data) const
	3250	{
	3251	#if 0
	3252	return (float)-data.mDepth;
	3253	#endif
	3254
	3255	float pvsFront = 0;
	3256	float pvsBack = 0;
	3257	float totalPvs = 0;
	3258
	3259	// probability that view point lies in back / front node
[1108]	3260	float pOverall = data.mBoundingBox.GetVolume();//data.mProbability;
[1089]	3261	float pFront = 0;
	3262	float pBack = 0;
	3263
	3264	Intersectable::NewMail();
[1106]	3265	KdLeaf::NewMail();
[1089]	3266	ViewCell::NewMail();
	3267
[1106]	3268	KdLeaf *leaf = data.mNode;
[1089]	3269	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3270
	3271	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	3272	{
	3273	Intersectable obj = oit;
	3274	const AxisAlignedBox3 box = obj->GetBox();
[1108]	3275
	3276	const float pvsIncr = EvalViewCellPvsIncr(obj);
	3277	totalPvs += pvsIncr;
[1089]	3278
	3279	if (box.Max(candidatePlane.mAxis) > candidatePlane.mPosition)
[1108]	3280	{
	3281	pvsFront += pvsIncr;
	3282	}
[1089]	3283	if (box.Min(candidatePlane.mAxis) > candidatePlane.mPosition)
[1108]	3284	{
	3285	pvsBack += pvsIncr;
	3286	}
[1089]	3287	}
	3288
	3289
	3290	AxisAlignedBox3 frontBox;
	3291	AxisAlignedBox3 backBox;
	3292
	3293	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
	3294
	3295	pFront = frontBox.GetVolume();
	3296	pBack = pOverall - pFront;
	3297
	3298
	3299	//-- pvs rendering heuristics
	3300	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	3301	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	3302
	3303	//-- only render cost heuristics or combined with standard deviation
[1108]	3304	const float penaltyOld = totalPvs;//EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	3305	const float penaltyFront = pvsFront;//EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	3306	const float penaltyBack = pvsBack;//EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[1089]	3307
[1108]	3308	Debug << "total pvs: " << totalPvs << " p " << pOverall << endl;
[1089]	3309	const float oldRenderCost = pOverall * penaltyOld;
	3310	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	3311
[1108]	3312	Debug << "old: " << oldRenderCost << " new: " << newRenderCost << " decrease: " << oldRenderCost - newRenderCost << endl;
[1089]	3313	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
	3314
	3315	// take render cost of node into account
	3316	// otherwise danger of being stuck in a local minimum!!
	3317	const float factor = 0.99f;
	3318
	3319	const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
[1106]	3320
[1089]	3321	return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
	3322	}
	3323
	3324
	3325	void OspTree::PrepareConstruction(const ObjectContainer &objects,
	3326	AxisAlignedBox3 *forcedBoundingBox)
	3327	{
[1099]	3328	// store pointer to this tree
	3329	OspSplitCandidate::sOspTree = this;
	3330
[1089]	3331	mOspStats.nodes = 1;
	3332
	3333	if (forcedBoundingBox)
	3334	{
	3335	mBoundingBox = *forcedBoundingBox;
	3336	}
	3337	else // compute vsp tree bounding box
	3338	{
	3339	mBoundingBox.Initialize();
	3340
	3341	ObjectContainer::const_iterator oit, oit_end = objects.end();
	3342
	3343	//-- compute bounding box
	3344	for (oit = objects.begin(); oit != oit_end; ++ oit)
	3345	{
	3346	Intersectable obj = oit;
	3347
	3348	// compute bounding box of view space
	3349	mBoundingBox.Include(obj->GetBox());
	3350	mBoundingBox.Include(obj->GetBox());
	3351	}
	3352	}
[1108]	3353
	3354	mTermMinProbability *= mBoundingBox.GetVolume();
	3355	mGlobalCostMisses = 0;
[1089]	3356	}
	3357
	3358
	3359	void OspTree::ProcessLeafObjects(KdLeaf leaf, KdLeaf parent) const
	3360	{
	3361	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3362
	3363	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	3364	{
	3365	Intersectable object = oit;
	3366
	3367	if (parent)
	3368	{
	3369	set<KdLeaf *>::iterator kdit = object->mKdLeaves.find(parent);
	3370
	3371	// remove parent leaf
	3372	if (kdit != object->mKdLeaves.end())
	3373	object->mKdLeaves.erase(kdit);
	3374	}
	3375
	3376	object->mKdLeaves.insert(leaf);
	3377
	3378	if (object->mKdLeaves.size() > 1)
	3379	leaf->mMultipleObjects.push_back(object);
	3380	}
	3381	}
	3382
	3383
[1106]	3384	void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
	3385	{
	3386	stack<KdNode *> nodeStack;
	3387	nodeStack.push(mRoot);
[1089]	3388
[1106]	3389	while (!nodeStack.empty())
	3390	{
	3391	KdNode *node = nodeStack.top();
	3392	nodeStack.pop();
	3393	if (node->IsLeaf())
	3394	{
	3395	KdLeaf leaf = (KdLeaf )node;
	3396	leaves.push_back(leaf);
	3397	}
	3398	else
	3399	{
	3400	KdInterior interior = (KdInterior )node;
	3401	nodeStack.push(interior->mBack);
	3402	nodeStack.push(interior->mFront);
	3403	}
	3404	}
	3405	}
[1021]	3406
[1072]	3407
[1106]	3408	AxisAlignedBox3 OspTree::GetBBox(KdNode *node) const
	3409	{
	3410	if (!node->mParent)
	3411	return mBoundingBox;
[1072]	3412
[1106]	3413	if (!node->IsLeaf())
	3414	{
	3415	return (dynamic_cast<KdInterior *>(node))->mBox;
	3416	}
	3417
	3418	KdInterior parent = dynamic_cast<KdInterior >(node->mParent);
	3419
	3420	AxisAlignedBox3 box(parent->mBox);
	3421
	3422	if (parent->mFront == node)
	3423	box.SetMin(parent->mAxis, parent->mPosition);
	3424	else
	3425	box.SetMax(parent->mAxis, parent->mPosition);
	3426
	3427	return box;
	3428	}
	3429
	3430
	3431	/********************************************************************/
	3432	/* class HierarchyManager implementation */
	3433	/********************************************************************/
	3434
	3435
	3436
[1027]	3437	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
	3438	mVspTree(vspTree), mOspTree(ospTree)
[1016]	3439	{
[1020]	3440	}
	3441
	3442
	3443	SplitCandidate *HierarchyManager::NextSplitCandidate()
	3444	{
[1106]	3445	SplitCandidate *splitCandidate = mTQueue.Top();
	3446
	3447	Debug << "next candidate: " << splitCandidate->Type()
	3448	<< ", priority: " << splitCandidate->GetPriority() << endl;
	3449
[1099]	3450	mTQueue.Pop();
[1020]	3451
	3452	return splitCandidate;
	3453	}
	3454
	3455
	3456	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
[1027]	3457	const ObjectContainer &objects,
[1020]	3458	AxisAlignedBox3 *forcedViewSpace,
	3459	RayInfoContainer &rays)
	3460	{
[1027]	3461	mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
[1020]	3462
	3463	long startTime = GetTime();
	3464
	3465	cout << "storing rays ... ";
	3466
	3467	Intersectable::NewMail();
	3468
[1027]	3469	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[1020]	3470
[1016]	3471	//-- store rays
	3472	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	3473	{
	3474	VssRay ray = rit;
	3475
	3476	float minT, maxT;
	3477
	3478	static Ray hray;
	3479	hray.Init(*ray);
[1027]	3480
[1016]	3481	// TODO: not very efficient to implictly cast between rays types
[1027]	3482	if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
[1016]	3483	{
	3484	float len = ray->Length();
	3485
	3486	if (!len)
	3487	len = Limits::Small;
	3488
[1020]	3489	rays.push_back(RayInfo(ray, minT / len, maxT / len));
[1016]	3490	}
	3491	}
[1020]	3492
[1027]	3493	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1020]	3494
[1089]	3495
	3496	int pvsSize = mVspTree.ComputePvsSize(rays);
	3497
	3498	// -- prepare view space partition
	3499
	3500	// add first candidate for view space partition
[1109]	3501	VspLeaf *leaf = new VspLeaf();
	3502	mVspTree.mRoot = leaf;
[1027]	3503	const float prop = mVspTree.mBoundingBox.GetVolume();
	3504
[1089]	3505	// first vsp traversal data
[1109]	3506	VspTree::VspTraversalData vData(leaf,
[1027]	3507	0,
	3508	&rays,
[1074]	3509	//(int)objects.size(),
[1089]	3510	pvsSize,
[1027]	3511	prop,
	3512	mVspTree.mBoundingBox);
	3513
[1089]	3514
[1027]	3515	// compute first split candidate
[1099]	3516	VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate(vData);
	3517	mVspTree.EvalSplitCandidate(*splitCandidate);
[1027]	3518
[1099]	3519	mTQueue.Push(splitCandidate);
[1027]	3520
[1089]	3521
	3522	//-- object space partition
	3523
	3524	mOspTree.PrepareConstruction(objects, forcedViewSpace);
	3525
	3526	// add first candidate for view space partition
[1109]	3527	KdLeaf *kdleaf = new KdLeaf(NULL, 0);
	3528	kdleaf->mObjects = objects;
[1089]	3529
[1109]	3530	mOspTree.mRoot = kdleaf;
[1089]	3531
	3532
	3533	// first osp traversal data
[1109]	3534	OspTree::OspTraversalData oData(kdleaf,
[1089]	3535	0,
	3536	pvsSize,
	3537	prop,
	3538	mOspTree.mBoundingBox);
	3539
	3540
[1109]	3541	mOspTree.ProcessLeafObjects(kdleaf, NULL);
[1089]	3542
	3543	// compute first split candidate
[1099]	3544	OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate(oData);
	3545	mOspTree.EvalSplitCandidate(*oSplitCandidate);
[1089]	3546
[1099]	3547	mTQueue.Push(splitCandidate);
[1016]	3548	}
	3549
	3550
[1020]	3551	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
[1016]	3552	{
[1108]	3553	// TODO matt: make virtual by creating superclasss for traveral data
	3554	return candidate->GlobalTerminationCriteriaMet();
[1016]	3555	}
	3556
	3557
[1101]	3558	void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
[1106]	3559	const ObjectContainer &objects,
	3560	AxisAlignedBox3 *forcedViewSpace)
[1101]	3561	{
	3562	RayInfoContainer *rays = new RayInfoContainer();
	3563
	3564	mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
	3565
	3566	long startTime = GetTime();
	3567
	3568	cout << "storing rays ... ";
	3569
	3570	Intersectable::NewMail();
	3571
	3572	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	3573
	3574	//-- store rays
	3575	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	3576	{
	3577	VssRay ray = rit;
	3578
	3579	float minT, maxT;
	3580
	3581	static Ray hray;
	3582	hray.Init(*ray);
	3583
	3584	// TODO: not very efficient to implictly cast between rays types
	3585	if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
	3586	{
	3587	float len = ray->Length();
	3588
	3589	if (!len)
	3590	len = Limits::Small;
	3591
	3592	rays->push_back(RayInfo(ray, minT / len, maxT / len));
	3593	}
	3594	}
	3595
	3596	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	3597
	3598	const int pvsSize = mVspTree.ComputePvsSize(*rays);
	3599
	3600
	3601	// -- prepare view space partition
	3602
	3603	// add first candidate for view space partition
[1109]	3604	VspLeaf *vspleaf = new VspLeaf();
	3605
	3606	mVspTree.mRoot = vspleaf;
[1101]	3607	const float prop = mVspTree.mBoundingBox.GetVolume();
	3608
	3609	// first vsp traversal data
[1109]	3610	VspTree::VspTraversalData vData(vspleaf,
[1101]	3611	0,
	3612	rays,
	3613	pvsSize,
	3614	prop,
	3615	mVspTree.mBoundingBox);
	3616
	3617
	3618	//-- compute first split candidate
	3619	VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate(vData);
	3620	mVspTree.EvalSplitCandidate(*splitCandidate);
	3621
	3622	mTQueue.Push(splitCandidate);
	3623
	3624	int i = 0;
	3625
	3626	while (!FinishedConstruction())
	3627	{
	3628	SplitCandidate *splitCandidate = NextSplitCandidate();
	3629
	3630	const bool globalTerminationCriteriaMet =
	3631	GlobalTerminationCriteriaMet(splitCandidate);
	3632
[1108]	3633	//cout << "vsp nodes: " << i ++ << endl;
[1101]	3634
	3635	// cost ratio of cost decrease / totalCost
	3636	const float costRatio = splitCandidate->GetPriority() / mTotalCost;
	3637	//Debug << "cost ratio: " << costRatio << endl;
	3638
	3639	if (costRatio < mTermMinGlobalCostRatio)
	3640	++ mGlobalCostMisses;
	3641
	3642	//-- subdivide leaf node
	3643
	3644	// we have either a object space or view space split
	3645	VspTree::VspSplitCandidate *sc =
	3646	dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
	3647
	3648	VspNode r = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
	3649
	3650	DEL_PTR(splitCandidate);
	3651	}
	3652
	3653	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	3654	mVspTree.mVspStats.Stop();
[1106]	3655
	3656	Debug << "object space" << endl;
[1101]	3657
	3658	//-- object space partition
	3659
	3660	mOspTree.PrepareConstruction(objects, forcedViewSpace);
	3661
	3662	// add first candidate for view space partition
	3663	KdLeaf *leaf = new KdLeaf(NULL, 0);
	3664	leaf->mObjects = objects;
	3665
	3666	mOspTree.mRoot = leaf;
	3667
	3668
	3669	//-- first osp traversal data
[1106]	3670	OspTree::OspTraversalData oData(leaf,
[1101]	3671	0,
	3672	pvsSize,
	3673	prop,
	3674	mOspTree.mBoundingBox);
	3675
	3676
	3677	mOspTree.ProcessLeafObjects(leaf, NULL);
	3678
	3679	// compute first split candidate
	3680	OspTree::OspSplitCandidate *oSplitCandidate = new OspTree::OspSplitCandidate(oData);
	3681	mOspTree.EvalSplitCandidate(*oSplitCandidate);
	3682
[1106]	3683	mTQueue.Push(oSplitCandidate);
[1101]	3684
	3685	i = 0;
	3686	while (!FinishedConstruction())
	3687	{
	3688	SplitCandidate *splitCandidate = NextSplitCandidate();
	3689
	3690	const bool globalTerminationCriteriaMet =
	3691	GlobalTerminationCriteriaMet(splitCandidate);
	3692
	3693	// cost ratio of cost decrease / totalCost
	3694	const float costRatio = splitCandidate->GetPriority() / mTotalCost;
[1108]	3695
[1101]	3696	//Debug << "cost ratio: " << costRatio << endl;
[1108]	3697	//cout << "kd nodes: " << i ++ << endl;
[1101]	3698
	3699	if (costRatio < mTermMinGlobalCostRatio)
	3700	++ mGlobalCostMisses;
	3701
	3702	//-- subdivide leaf node
	3703
	3704	// object space split
	3705	OspTree::OspSplitCandidate *sc =
	3706	dynamic_cast<OspTree::OspSplitCandidate *>(splitCandidate);
	3707
	3708	KdNode r = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
	3709
	3710	DEL_PTR(splitCandidate);
	3711	}
[1106]	3712
[1101]	3713	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	3714	}
	3715
	3716
[1020]	3717	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
	3718	const ObjectContainer &objects,
	3719	AxisAlignedBox3 *forcedViewSpace)
[1016]	3720	{
[1020]	3721	RayInfoContainer *rays = new RayInfoContainer();
	3722
	3723	// prepare vsp and osp trees for traversal
[1027]	3724	PrepareConstruction(sampleRays, objects, forcedViewSpace, *rays);
[1016]	3725
[1027]	3726	mVspTree.mVspStats.Reset();
	3727	mVspTree.mVspStats.Start();
[1016]	3728
[1020]	3729	cout << "Constructing view space / object space tree ... \n";
[1016]	3730	const long startTime = GetTime();
[1074]	3731
	3732	int i = 0;
[1016]	3733	while (!FinishedConstruction())
	3734	{
	3735	SplitCandidate *splitCandidate = NextSplitCandidate();
	3736
[1020]	3737	const bool globalTerminationCriteriaMet =
	3738	GlobalTerminationCriteriaMet(splitCandidate);
	3739
[1074]	3740	cout << "view cells: " << i ++ << endl;
[1027]	3741
[1016]	3742	// cost ratio of cost decrease / totalCost
	3743	const float costRatio = splitCandidate->GetPriority() / mTotalCost;
	3744	//Debug << "cost ratio: " << costRatio << endl;
	3745
	3746	if (costRatio < mTermMinGlobalCostRatio)
	3747	++ mGlobalCostMisses;
[1027]	3748
[1020]	3749	//-- subdivide leaf node
[1101]	3750
	3751	// we have either a object space or view space split
[1016]	3752	if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
	3753	{
	3754	VspTree::VspSplitCandidate *sc =
	3755	dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
	3756
[1027]	3757	VspNode r = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1016]	3758	}
[1020]	3759	else // object space split
[1089]	3760	{
	3761	OspTree::OspSplitCandidate *sc =
	3762	dynamic_cast<OspTree::OspSplitCandidate *>(splitCandidate);
	3763
	3764	KdNode r = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1016]	3765	}
[1020]	3766
	3767	DEL_PTR(splitCandidate);
[1016]	3768	}
	3769
[1074]	3770	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
[1016]	3771
[1027]	3772	mVspTree.mVspStats.Stop();
[1016]	3773	}
	3774
[1020]	3775
	3776	bool HierarchyManager::FinishedConstruction()
	3777	{
[1099]	3778	return mTQueue.Empty();
[1020]	3779	}
	3780
	3781
[1099]	3782	void HierarchyManager::RepairQueue(const vector<SplitCandidate *> &dirtyList)
[1093]	3783	{
	3784	// TODO
	3785	// for each update of the view space partition:
	3786	// the candidates from object space partition which
	3787	// have been afected by the view space split (the kd split candidates
	3788	// which saw the view cell which was split) must be reevaluated
	3789	// (maybe not locally, just reinsert them into the queue)
	3790	//
	3791	// vice versa for the view cells
	3792	// for each update of the object space partition
	3793	// reevaluate split candidate for view cells which saw the split kd cell
	3794	//
	3795	// the priority queue update can be solved by implementing a binary heap
	3796	// (explicit data structure, binary tree)
	3797	// *) inserting and removal is efficient
[1099]	3798	// *) search is not efficient => store queue position with each
[1093]	3799	// split candidate
	3800
[1099]	3801	vector<SplitCandidate *>::const_iterator sit, sit_end = dirtyList.end();
[1093]	3802
[1099]	3803	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
[1093]	3804	{
[1099]	3805	SplitCandidate* sc = *sit;
[1093]	3806
[1099]	3807	mTQueue.Erase(sc);
[1093]	3808
[1099]	3809	// reevaluate
	3810	sc->EvalPriority();
[1093]	3811
[1099]	3812	// reinsert
	3813	mTQueue.Push(sc);
	3814	}
[1093]	3815	}
	3816
[1002]	3817	}

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

Download in other formats: