Context Navigation

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

Revision 1201, 146.2 KB checked in by mattausch, 18 years ago (diff)
added loader for osp trees

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"
[1139]	19	#include "KdIntersectable.h"
[1002]	20
[1020]	21
[1002]	22	namespace GtpVisibilityPreprocessor {
	23
[1189]	24
[1002]	25	#define USE_FIXEDPOINT_T 0
	26
[1123]	27
[1002]	28	//-- static members
	29
[1099]	30	VspTree *VspTree::VspSplitCandidate::sVspTree = NULL;
	31	OspTree *OspTree::OspSplitCandidate::sOspTree = NULL;
[1002]	32
[1178]	33	// variable for debugging volume contribution for heuristics
	34	static float debugVol;
	35
[1189]	36	int VspNode::sMailId = 1;
	37
[1002]	38	// pvs penalty can be different from pvs size
	39	inline static float EvalPvsPenalty(const int pvs,
	40	const int lower,
	41	const int upper)
	42	{
	43	// clamp to minmax values
	44	if (pvs < lower)
[1189]	45	{
[1002]	46	return (float)lower;
[1189]	47	}
[1077]	48	else if (pvs > upper)
[1189]	49	{
[1002]	50	return (float)upper;
[1189]	51	}
[1002]	52
	53	return (float)pvs;
	54	}
	55
	56
[1189]	57	static bool ViewCellHasMultipleReferences(Intersectable *obj,
	58	ViewCell *vc,
	59	bool checkOnlyMailed)
	60	{
	61	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1193]	62	//return false;
[1189]	63	if (vdata)
	64	{
	65	// more than one view cell sees this object inside different kd cells
	66	if (!checkOnlyMailed \|\| !vdata->Mailed())
	67	{
	68	if (checkOnlyMailed)
	69	vdata->Mail();
[1193]	70	//Debug << "sumpdf: " << vdata->mSumPdf << endl;
[1189]	71	if (vdata->mSumPdf > 1.5f)
	72	return true;
	73	}
	74	}
	75
	76	return false;
	77	}
	78
	79
[1021]	80	void VspTreeStatistics::Print(ostream &app) const
	81	{
[1121]	82	app << "=========== VspTree statistics ===============\n";
[1021]	83
	84	app << setprecision(4);
	85
	86	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
	87
	88	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
	89
	90	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	91
	92	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	93
	94	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
	95
	96	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
	97
	98	for (int i = 0; i < 3; ++ i)
	99	app << splits[i] << " ";
	100	app << endl;
	101
	102	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
	103	<< maxDepthNodes * 100 / (double)Leaves() << endl;
	104
	105	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
	106	<< minPvsNodes * 100 / (double)Leaves() << endl;
	107
	108	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
	109	<< minRaysNodes * 100 / (double)Leaves() << endl;
	110
	111	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
	112	<< maxCostNodes * 100 / (double)Leaves() << endl;
	113
	114	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
	115	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
	116
	117	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
	118	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
	119
	120	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
	121
	122	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
	123
	124	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
	125
	126	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
	127
	128	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
	129	//app << "#N_PVS: " << pvs << endl;
	130
[1184]	131	//app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
	132
[1121]	133	app << "========== END OF VspTree statistics ==========\n";
[1021]	134	}
	135
	136
[1145]	137	void OspTreeStatistics::Print(ostream &app) const
	138	{
	139	app << "=========== OspTree statistics ===============\n";
	140
	141	app << setprecision(4);
	142
	143	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
	144
	145	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
	146
	147	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	148
	149	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	150
	151	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
	152
	153	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
	154
	155	for (int i = 0; i < 3; ++ i)
	156	app << splits[i] << " ";
	157	app << endl;
	158
	159	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
	160	<< maxDepthNodes * 100 / (double)Leaves() << endl;
	161
	162	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
	163	<< minPvsNodes * 100 / (double)Leaves() << endl;
	164
[1184]	165	//app << "#N_PMINOBJECTREFLEAVES ( Percentage of leaves with minimal number of object ref)\n"
	166	//<< minObjectNodes * 100 / (double)Leaves() << endl;
[1145]	167
	168	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
	169	<< maxCostNodes * 100 / (double)Leaves() << endl;
	170
	171	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
	172	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
	173
	174	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
	175
	176	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
	177
	178	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
	179
	180	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
	181
[1184]	182	app << "#N_MAXOBJECTREFS ( Max number of object refs / leaf )\n" <<
	183	maxObjectRefs << "\n";
	184
[1145]	185	// app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
	186	//app << "#N_PVS: " << pvs << endl;
	187
	188	app << "========== END OF VspTree statistics ==========\n";
	189	}
	190
	191
[1008]	192	/******************************************************************/
	193	/* class VspNode implementation */
	194	/******************************************************************/
	195
	196
	197	VspNode::VspNode():
	198	mParent(NULL), mTreeValid(true), mTimeStamp(0)
	199	{}
	200
	201
	202	VspNode::VspNode(VspInterior *parent):
	203	mParent(parent), mTreeValid(true)
	204	{}
	205
	206
	207	bool VspNode::IsRoot() const
	208	{
	209	return mParent == NULL;
	210	}
	211
	212
	213	VspInterior *VspNode::GetParent()
	214	{
	215	return mParent;
	216	}
	217
	218
	219	void VspNode::SetParent(VspInterior *parent)
	220	{
	221	mParent = parent;
	222	}
	223
	224
	225	bool VspNode::IsSibling(VspNode *n) const
	226	{
	227	return ((this != n) && mParent &&
	228	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
	229	}
	230
	231
	232	int VspNode::GetDepth() const
	233	{
	234	int depth = 0;
	235	VspNode *p = mParent;
	236
	237	while (p)
	238	{
	239	p = p->mParent;
	240	++ depth;
	241	}
	242
	243	return depth;
	244	}
	245
	246
	247	bool VspNode::TreeValid() const
	248	{
	249	return mTreeValid;
	250	}
	251
	252
	253	void VspNode::SetTreeValid(const bool v)
	254	{
	255	mTreeValid = v;
	256	}
	257
	258
	259	/****************************************************************/
	260	/* class VspInterior implementation */
	261	/****************************************************************/
	262
	263
	264	VspInterior::VspInterior(const AxisAlignedPlane &plane):
	265	mPlane(plane), mFront(NULL), mBack(NULL)
	266	{}
	267
[1011]	268
[1008]	269	VspInterior::~VspInterior()
	270	{
	271	DEL_PTR(mFront);
	272	DEL_PTR(mBack);
	273	}
	274
[1011]	275
[1008]	276	bool VspInterior::IsLeaf() const
	277	{
	278	return false;
	279	}
	280
[1011]	281
[1008]	282	VspNode *VspInterior::GetBack()
	283	{
	284	return mBack;
	285	}
	286
[1011]	287
[1008]	288	VspNode *VspInterior::GetFront()
	289	{
	290	return mFront;
	291	}
	292
[1011]	293
[1008]	294	AxisAlignedPlane VspInterior::GetPlane() const
	295	{
	296	return mPlane;
	297	}
	298
[1011]	299
[1012]	300	float VspInterior::GetPosition() const
	301	{
	302	return mPlane.mPosition;
	303	}
	304
	305
	306	int VspInterior::GetAxis() const
	307	{
	308	return mPlane.mAxis;
	309	}
	310
	311
[1008]	312	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
	313	{
	314	if (mBack == oldChild)
	315	mBack = newChild;
	316	else
	317	mFront = newChild;
	318	}
	319
[1011]	320
[1109]	321	void VspInterior::SetupChildLinks(VspNode front, VspNode back)
[1008]	322	{
[1109]	323	mBack = back;
	324	mFront = front;
[1008]	325	}
	326
	327
[1016]	328	AxisAlignedBox3 VspInterior::GetBoundingBox() const
[1012]	329	{
[1016]	330	return mBoundingBox;
[1012]	331	}
	332
	333
[1016]	334	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
[1012]	335	{
[1016]	336	mBoundingBox = box;
[1012]	337	}
	338
	339
	340	int VspInterior::Type() const
	341	{
	342	return Interior;
	343	}
	344
[1027]	345
	346
[1008]	347	/****************************************************************/
	348	/* class VspLeaf implementation */
	349	/****************************************************************/
	350
	351
	352	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
	353	{
	354	}
	355
	356
	357	VspLeaf::~VspLeaf()
	358	{
	359	DEL_PTR(mPvs);
[1074]	360	CLEAR_CONTAINER(mVssRays);
[1008]	361	}
	362
[1021]	363
[1012]	364	int VspLeaf::Type() const
	365	{
	366	return Leaf;
	367	}
[1008]	368
[1012]	369
[1008]	370	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
	371	mViewCell(viewCell)
	372	{
	373	}
	374
	375
	376	VspLeaf::VspLeaf(VspInterior *parent):
	377	VspNode(parent), mViewCell(NULL), mPvs(NULL)
	378	{}
	379
	380
	381
	382	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
	383	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
	384	{
	385	}
	386
	387	ViewCellLeaf *VspLeaf::GetViewCell() const
	388	{
	389	return mViewCell;
	390	}
	391
	392	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
	393	{
	394	mViewCell = viewCell;
	395	}
	396
	397
	398	bool VspLeaf::IsLeaf() const
	399	{
	400	return true;
	401	}
	402
	403
[1176]	404	/*************************************************************************/
	405	/* class VspTree implementation */
	406	/*************************************************************************/
[1002]	407
	408
[1016]	409	VspTree::VspTree():
[1002]	410	mRoot(NULL),
	411	mOutOfBoundsCell(NULL),
	412	mStoreRays(false),
[1133]	413	mTimeStamp(1),
	414	mOspTree(NULL)
[1002]	415	{
	416	bool randomize = false;
[1016]	417	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
[1002]	418	if (randomize)
	419	Randomize(); // initialise random generator for heuristics
	420
	421	//-- termination criteria for autopartition
[1016]	422	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
	423	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
	424	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
	425	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
	426	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
[1023]	427
[1016]	428	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
	429	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
[1002]	430
	431	//-- max cost ratio for early tree termination
[1016]	432	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[1002]	433
[1016]	434	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	435	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
[1002]	436
	437	//-- factors for bsp tree split plane heuristics
[1016]	438	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
[1002]	439
	440	//-- partition criteria
[1016]	441	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
[1121]	442	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
[1002]	443
	444	// if only the driving axis is used for axis aligned split
[1016]	445	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[1002]	446
[1149]	447	Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
[1016]	448	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
[1002]	449
[1016]	450	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
	451	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
[1002]	452
[1141]	453	Environment::GetSingleton()->GetBoolValue("VspTree.useKdPvsForHeuristics", mUseKdPvsForHeuristics);
[1023]	454
[1002]	455	char subdivisionStatsLog[100];
[1016]	456	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
[1002]	457	mSubdivisionStats.open(subdivisionStatsLog);
	458
[1016]	459	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
	460	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
[1006]	461
[1002]	462
	463	//-- debug output
	464
[1076]	465	Debug << "***** VSP options ****** " << endl;
[1106]	466
[1002]	467	Debug << "max depth: " << mTermMaxDepth << endl;
	468	Debug << "min PVS: " << mTermMinPvs << endl;
	469	Debug << "min probabiliy: " << mTermMinProbability << endl;
	470	Debug << "min rays: " << mTermMinRays << endl;
	471	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	472	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	473	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	474	Debug << "max view cells: " << mMaxViewCells << endl;
	475	Debug << "randomize: " << randomize << endl;
	476
	477	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	478	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	479	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	480	Debug << "max memory: " << mMaxMemory << endl;
	481	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	482	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1121]	483	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
	484
[1002]	485	Debug << "circulating axis: " << mCirculatingAxis << endl;
	486	Debug << "minband: " << mMinBand << endl;
	487	Debug << "maxband: " << mMaxBand << endl;
	488
[1141]	489	if (!mUseKdPvsForHeuristics)
[1143]	490	Debug << "pvs heuristics: per object" << endl;
[1106]	491	else
[1143]	492	Debug << "pvs heuristics: per kd node" << endl;
[1084]	493
[1178]	494	mLocalSplitCandidates = new vector<SortableEntry>;
[1002]	495
	496	Debug << endl;
	497	}
	498
	499
[1016]	500	VspViewCell *VspTree::GetOutOfBoundsCell()
[1002]	501	{
	502	return mOutOfBoundsCell;
	503	}
	504
	505
[1016]	506	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
[1002]	507	{
	508	if (!mOutOfBoundsCell)
	509	{
[1008]	510	mOutOfBoundsCell = new VspViewCell();
[1002]	511	mOutOfBoundsCell->SetId(-1);
	512	mOutOfBoundsCell->SetValid(false);
	513	}
	514
	515	return mOutOfBoundsCell;
	516	}
	517
	518
[1016]	519	const VspTreeStatistics &VspTree::GetStatistics() const
[1002]	520	{
[1008]	521	return mVspStats;
[1002]	522	}
	523
	524
[1016]	525	VspTree::~VspTree()
[1002]	526	{
	527	DEL_PTR(mRoot);
[1178]	528	DEL_PTR(mLocalSplitCandidates);
[1002]	529	}
	530
[1008]	531
[1143]	532	void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
[1135]	533	AxisAlignedBox3 *forcedBoundingBox)
	534	{
[1002]	535	if (forcedBoundingBox)
[1027]	536	{
[1020]	537	mBoundingBox = *forcedBoundingBox;
[1027]	538	}
	539	else // compute vsp tree bounding box
[1002]	540	{
[1027]	541	mBoundingBox.Initialize();
[1143]	542	VssRayContainer::const_iterator rit, rit_end = rays.end();
[1027]	543
	544	//-- compute bounding box
[1135]	545	for (rit = rays.begin(); rit != rit_end; ++ rit)
[1002]	546	{
[1143]	547	VssRay ray = rit;
[1027]	548
	549	// compute bounding box of view space
[1020]	550	mBoundingBox.Include(ray->GetTermination());
	551	mBoundingBox.Include(ray->GetOrigin());
[1002]	552	}
[1027]	553	}
[1020]	554	}
[1002]	555
	556
[1020]	557	void VspTree::AddSubdivisionStats(const int viewCells,
	558	const float renderCostDecr,
	559	const float totalRenderCost,
[1027]	560	const float avgRenderCost)
[1020]	561	{
	562	mSubdivisionStats
	563	<< "#ViewCells\n" << viewCells << endl
	564	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	565	<< "#TotalRenderCost\n" << totalRenderCost << endl
	566	<< "#AvgRenderCost\n" << avgRenderCost << endl;
[1002]	567	}
	568
	569
	570	// TODO: return memory usage in MB
[1016]	571	float VspTree::GetMemUsage() const
[1002]	572	{
	573	return (float)
[1016]	574	(sizeof(VspTree) +
[1008]	575	mVspStats.Leaves() * sizeof(VspLeaf) +
[1010]	576	mCreatedViewCells * sizeof(VspViewCell) +
[1189]	577	mVspStats.pvs * sizeof(PvsData) +
[1008]	578	mVspStats.Interior() * sizeof(VspInterior) +
	579	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
[1002]	580	}
	581
	582
[1016]	583	bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
[1002]	584	{
[1143]	585	const bool localTerminationCriteriaMet = (
[1106]	586	((int)data.mRays->size() <= mTermMinRays) \|\|
	587	(data.mPvs <= mTermMinPvs) \|\|
	588	(data.mProbability <= mTermMinProbability) \|\|
	589	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
	590	(data.mDepth >= mTermMaxDepth)
	591	);
[1143]	592
	593	if (0 && localTerminationCriteriaMet)
	594	{
	595	Debug << "******local termination *******" << endl;
	596	Debug << "rays: " << (int)data.mRays->size() << " " << mTermMinRays << endl;
	597	Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
	598	Debug << "p: " << data.mProbability << " " << mTermMinProbability << endl;
	599	Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
	600	Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
	601	}
	602
	603	return localTerminationCriteriaMet;
[1106]	604
[1002]	605	}
	606
	607
[1016]	608	bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
[1002]	609	{
[1143]	610	const bool terminationCriteriaMet = (
	611	// mOutOfMemory \|\|
[1011]	612	(mVspStats.Leaves() >= mMaxViewCells) \|\|
[1106]	613	(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
[1143]	614	);
	615
	616	if (0 && terminationCriteriaMet)
	617	{
	618	Debug << "******* terminationCriteriaMet *******" << endl;
	619	Debug << "cost misses: " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
	620	Debug << "leaves: " << mVspStats.Leaves() << " " << mMaxViewCells << endl;
	621	}
	622	return terminationCriteriaMet;
[1002]	623	}
	624
	625
[1142]	626	void VspTree::CreateViewCell(VspTraversalData &tData, const bool updatePvs)
[1108]	627	{
	628	//-- create new view cell
	629	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
	630
	631	VspViewCell *viewCell = new VspViewCell();
	632	leaf->SetViewCell(viewCell);
[1142]	633
[1108]	634	int conSamp = 0;
	635	float sampCon = 0.0f;
	636
[1142]	637	if (updatePvs)
	638	{
[1180]	639	//-- update pvs of view cell
[1142]	640	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
[1108]	641
[1142]	642	// update scalar pvs size value
[1160]	643	ObjectPvs &pvs = viewCell->GetPvs();
[1168]	644	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
[1108]	645
[1142]	646	mVspStats.contributingSamples += conSamp;
	647	mVspStats.sampleContributions += (int)sampCon;
	648	}
	649
	650
[1108]	651	//-- store additional info
	652	if (mStoreRays)
	653	{
	654	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
[1109]	655
[1108]	656	for (it = tData.mRays->begin(); it != it_end; ++ it)
	657	{
	658	(*it).mRay->Ref();
	659	leaf->mVssRays.push_back((*it).mRay);
	660	}
	661	}
	662
[1184]	663	// set view cell values
[1108]	664	viewCell->mLeaf = leaf;
	665
	666	viewCell->SetVolume(tData.mProbability);
	667	leaf->mProbability = tData.mProbability;
	668	}
	669
	670
[1174]	671	void VspTree::EvalSubdivisionStats(const SplitCandidate &sc)
[1145]	672	{
[1174]	673	const float costDecr = sc.GetRenderCostDecrease();
[1145]	674
	675	AddSubdivisionStats(mVspStats.Leaves(),
[1176]	676	costDecr,
[1145]	677	mTotalCost,
	678	(float)mTotalPvsSize / (float)mVspStats.Leaves());
	679	}
	680
	681
[1016]	682	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
[1145]	683	SplitCandidate *splitCandidate,
[1020]	684	const bool globalCriteriaMet)
[1002]	685	{
[1174]	686	// todo remove dynamic cast
[1145]	687	VspSplitCandidate sc = dynamic_cast<VspSplitCandidate >(splitCandidate);
	688	VspTraversalData &tData = sc->mParentData;
[1002]	689
[1008]	690	VspNode *newNode = tData.mNode;
[1002]	691
[1174]	692
[1020]	693	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
[1002]	694	{
[1016]	695	VspTraversalData tFrontData;
	696	VspTraversalData tBackData;
[1002]	697
	698	//-- continue subdivision
	699
	700	// create new interior node and two leaf node
[1145]	701	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
[1006]	702	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
[1002]	703
[1145]	704	const int maxCostMisses = sc->mMaxCostMisses;
[1002]	705
	706
	707	// how often was max cost ratio missed in this branch?
	708	tFrontData.mMaxCostMisses = maxCostMisses;
	709	tBackData.mMaxCostMisses = maxCostMisses;
	710
[1174]	711	mTotalCost -= sc->GetRenderCostDecrease();
	712	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
	713
	714	// subdivision statistics
	715	if (1) EvalSubdivisionStats(*sc);
[1145]	716
	717	//-- evaluate new split candidates for global greedy cost heuristics
[1108]	718
[1099]	719	VspSplitCandidate *frontCandidate = new VspSplitCandidate(tFrontData);
	720	VspSplitCandidate *backCandidate = new VspSplitCandidate(tBackData);
[1002]	721
[1099]	722	EvalSplitCandidate(*frontCandidate);
	723	EvalSplitCandidate(*backCandidate);
[1020]	724
[1099]	725	tQueue.Push(frontCandidate);
	726	tQueue.Push(backCandidate);
[1121]	727
	728	// delete old view cell
[1143]	729	delete tData.mNode->mViewCell;
[1145]	730
[1002]	731	// delete old leaf node
	732	DEL_PTR(tData.mNode);
	733	}
	734
[1143]	735	if (newNode->IsLeaf()) // subdivision terminated
[1002]	736	{
[1178]	737	// view cell is created during subdivision
	738	//CreateViewCell(tData);
[1143]	739
	740	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
	741	ViewCell *viewCell = leaf->GetViewCell();
	742
	743	int conSamp = 0;
	744	float sampCon = 0.0f;
	745
[1180]	746	#if 0
	747	//-- store pvs optained from rays
[1143]	748
	749	AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
	750
	751	// update scalar pvs size value
[1160]	752	ObjectPvs &pvs = viewCell->GetPvs();
[1168]	753	mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
[1143]	754
	755	mVspStats.contributingSamples += conSamp;
	756	mVspStats.sampleContributions += (int)sampCon;
[1180]	757	#endif
[1002]	758	//-- store additional info
	759	if (mStoreRays)
	760	{
	761	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	762	for (it = tData.mRays->begin(); it != it_end; ++ it)
	763	{
	764	(*it).mRay->Ref();
[1184]	765	leaf->mVssRays.push_back((*it).mRay);
[1002]	766	}
	767	}
	768
[1108]	769	// finally evaluate statistics for this leaf
[1020]	770	EvaluateLeafStats(tData);
[1002]	771	}
	772
	773	//-- cleanup
	774	tData.Clear();
[1020]	775
[1002]	776	return newNode;
	777	}
	778
	779
[1099]	780	void VspTree::EvalSplitCandidate(VspSplitCandidate &splitCandidate)
[1002]	781	{
[1020]	782	float frontProb;
[1027]	783	float backProb;
[1020]	784
[1099]	785	VspLeaf leaf = dynamic_cast<VspLeaf >(splitCandidate.mParentData.mNode);
[1020]	786
[1002]	787	// compute locally best split plane
[1008]	788	const bool success =
[1099]	789	SelectSplitPlane(splitCandidate.mParentData, splitCandidate.mSplitPlane, frontProb, backProb);
[1008]	790
[1145]	791	float oldRenderCost;
	792
[1002]	793	// compute global decrease in render cost
[1145]	794	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
	795	splitCandidate.mParentData,
	796	oldRenderCost);
	797
	798	splitCandidate.SetRenderCostDecrease(renderCostDecr);
	799
	800	#if 0
	801	const float priority = (float)-data.mDepth;
	802	#else
	803
	804	// take render cost of node into account
	805	// otherwise danger of being stuck in a local minimum!!
	806	const float factor = mRenderCostDecreaseWeight;
	807	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
	808	#endif
	809
[1099]	810	splitCandidate.SetPriority(priority);
[1145]	811
	812	// max cost threshold violated?
	813	splitCandidate.mMaxCostMisses =
	814	success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
[1074]	815	//Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
[1002]	816	}
	817
	818
[1016]	819	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
	820	VspTraversalData &tData,
	821	VspTraversalData &frontData,
	822	VspTraversalData &backData)
[1002]	823	{
[1008]	824	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
[1002]	825
	826	//-- the front and back traversal data is filled with the new values
[1108]	827
[1002]	828	frontData.mDepth = tData.mDepth + 1;
[1135]	829	backData.mDepth = tData.mDepth + 1;
	830
[1002]	831	frontData.mRays = new RayInfoContainer();
	832	backData.mRays = new RayInfoContainer();
[1135]	833
[1002]	834	//-- subdivide rays
	835	SplitRays(splitPlane,
	836	*tData.mRays,
	837	*frontData.mRays,
	838	*backData.mRays);
[1109]	839
[1074]	840	//Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
[1166]	841
[1011]	842	//-- compute pvs
[1181]	843	frontData.mPvs = EvalPvsSize(*frontData.mRays);
	844	backData.mPvs = EvalPvsSize(*backData.mRays);
[1002]	845
	846	// split front and back node geometry and compute area
[1006]	847	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
	848	frontData.mBoundingBox, backData.mBoundingBox);
[1002]	849
	850
[1006]	851	frontData.mProbability = frontData.mBoundingBox.GetVolume();
	852	backData.mProbability = tData.mProbability - frontData.mProbability;
[1002]	853
	854
[1006]	855	///////////////////////////////////////////
[1002]	856	// subdivide further
	857
	858	// store maximal and minimal depth
[1008]	859	if (tData.mDepth > mVspStats.maxDepth)
[1002]	860	{
[1008]	861	Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
	862	mVspStats.maxDepth = tData.mDepth;
[1002]	863	}
	864
[1109]	865	// two more leaves
[1008]	866	mVspStats.nodes += 2;
[1002]	867
[1008]	868	VspInterior *interior = new VspInterior(splitPlane);
[1002]	869
	870	#ifdef _DEBUG
	871	Debug << interior << endl;
[1166]	872	#endif+
[1002]	873
	874
	875	//-- create front and back leaf
	876
[1008]	877	VspInterior *parent = leaf->GetParent();
[1002]	878
	879	// replace a link from node's parent
	880	if (parent)
	881	{
	882	parent->ReplaceChildLink(leaf, interior);
	883	interior->SetParent(parent);
[1121]	884
	885	// remove "parent" view cell from pvs of all objects (traverse trough rays)
	886	RemoveParentViewCellReferences(tData.mNode->GetViewCell());
[1002]	887	}
	888	else // new root
	889	{
	890	mRoot = interior;
	891	}
	892
[1109]	893	VspLeaf *frontLeaf = new VspLeaf(interior);
	894	VspLeaf *backLeaf = new VspLeaf(interior);
	895
[1002]	896	// and setup child links
[1109]	897	interior->SetupChildLinks(frontLeaf, backLeaf);
[1106]	898
[1016]	899	// add bounding box
	900	interior->SetBoundingBox(tData.mBoundingBox);
[1002]	901
[1106]	902	// set front and back leaf
[1109]	903	frontData.mNode = frontLeaf;
	904	backData.mNode = backLeaf;
[1106]	905
[1109]	906	// explicitely create front and back view cell
[1143]	907	CreateViewCell(frontData, false);
	908	CreateViewCell(backData, false);
[1109]	909
[1174]	910
	911	#if WORK_WITH_VIEWCELL_PVS
[1109]	912	// create front and back view cell
	913	// add front and back view cell to "Potentially Visbilie View Cells"
	914	// of the objects in front and back pvs
	915
[1174]	916	AddViewCellReferences(frontLeaf->GetViewCell());
	917	AddViewCellReferences(backLeaf->GetViewCell());
	918	#endif
[1142]	919
[1002]	920	interior->mTimeStamp = mTimeStamp ++;
	921
	922	return interior;
	923	}
	924
	925
[1109]	926	void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
	927	{
	928	KdLeaf::NewMail();
	929
	930	// remove the parents from the object pvss
	931	ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
	932
	933	for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
[1089]	934	{
[1109]	935	Intersectable object = (oit).first;
	936	// HACK: make sure that the view cell is removed from the pvs
	937	const float high_contri = 9999999;
[1089]	938
[1109]	939	// remove reference count of view cells
[1110]	940	object->mViewCellPvs.RemoveSample(parent, high_contri);
[1089]	941	}
[1109]	942	}
[1089]	943
[1109]	944
	945	void VspTree::AddViewCellReferences(ViewCell *vc) const
	946	{
	947	KdLeaf::NewMail();
	948
	949	// Add front view cell to the object pvsss
[1110]	950	ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
[1109]	951
[1110]	952	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
[1089]	953	{
[1109]	954	Intersectable object = (oit).first;
[1089]	955
[1109]	956	// increase reference count of view cells
[1110]	957	object->mViewCellPvs.AddSample(vc, 1);
[1089]	958	}
	959	}
	960
	961
[1141]	962	bool VspTree::AddKdLeafToPvs(KdLeaf *leaf,
	963	ViewCell *vc,
[1184]	964	const float pdf,
[1141]	965	float &contribution)
[1002]	966	{
[1141]	967	bool contri = false;
	968
	969	#if 1 // add kd intersecable to pvs
	970	KdIntersectable *kdObj = mOspTree->GetOrCreateKdIntersectable(leaf);
	971
	972	if (vc->AddPvsSample(kdObj, pdf, contribution))
	973	{
	974	return true;
	975	}
	976
	977	#else // add all objects of kd node
	978
	979	contribution = 0;
	980
	981	ObjectContainer::const_iterator it, it_end = leaf->mObjects.end();
	982
	983	for (it = leaf->mObjects.begin(); it != it_end; ++ it)
	984	{
	985	Intersectable object = it;
	986
	987	float newcontri;
	988
[1184]	989	if (vc->AddPvsSample(object, pdf, newcontri))
[1141]	990	{
	991	contri = true;
	992	}
	993
[1184]	994	//pdf += newPdf;
[1141]	995	newContri += contribution;
	996	}
	997
	998	#endif
	999
	1000	return contri;
	1001	}
	1002
	1003	void VspTree::AddSamplesToPvs(VspLeaf *leaf,
[1180]	1004	const RayInfoContainer &rays,
	1005	float &sampleContributions,
	1006	int &contributingSamples)
[1141]	1007	{
[1002]	1008	sampleContributions = 0;
	1009	contributingSamples = 0;
	1010
	1011	RayInfoContainer::const_iterator it, it_end = rays.end();
	1012
	1013	ViewCellLeaf *vc = leaf->GetViewCell();
[1178]	1014
[1002]	1015	// add contributions from samples to the PVS
	1016	for (it = rays.begin(); it != it_end; ++ it)
	1017	{
	1018	float sc = 0.0f;
	1019	VssRay ray = (it).mRay;
	1020
	1021	bool madeContrib = false;
	1022	float contribution;
	1023
[1109]	1024	Intersectable *obj = ray->mTerminationObject;
	1025
	1026	if (obj)
[1002]	1027	{
[1141]	1028	if (mStoreKdPvs)
[1139]	1029	{
[1144]	1030	// potentially visible kd cells
[1139]	1031	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
[1141]	1032	AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
[1139]	1033	}
	1034	else
[1089]	1035	{
[1141]	1036	if (vc->AddPvsSample(obj, ray->mPdf, contribution))
	1037	{
	1038	madeContrib = true;
	1039	}
[1089]	1040	}
	1041
[1002]	1042	sc += contribution;
	1043	}
[1109]	1044
[1110]	1045	obj = ray->mOriginObject;
[1109]	1046
	1047	if (obj)
[1002]	1048	{
[1139]	1049	// potentially visible kd cells
[1178]	1050	if (!mStoreKdPvs) // matt Todo: remove storekdpvs!!
[1139]	1051	{
[1141]	1052	if (vc->AddPvsSample(obj, ray->mPdf, contribution))
	1053	{
	1054	madeContrib = true;
	1055	}
[1089]	1056	}
[1176]	1057	else
	1058	{
	1059	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
	1060	AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
	1061	}
	1062
	1063
[1089]	1064
[1002]	1065	sc += contribution;
	1066	}
	1067
[1047]	1068	if (madeContrib)
[1141]	1069	{
[1047]	1070	++ contributingSamples;
[1141]	1071	}
	1072
[1077]	1073	// store rays for visualization
	1074	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
[1002]	1075	}
	1076	}
	1077
	1078
[1047]	1079	void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
	1080	const int axis,
	1081	float minBand,
	1082	float maxBand)
[1002]	1083	{
[1178]	1084	mLocalSplitCandidates->clear();
[1002]	1085
	1086	int requestedSize = 2 * (int)(rays.size());
[1047]	1087
[1002]	1088	// creates a sorted split candidates array
[1178]	1089	if (mLocalSplitCandidates->capacity() > 500000 &&
	1090	requestedSize < (int)(mLocalSplitCandidates->capacity() / 10) )
[1002]	1091	{
[1178]	1092	delete mLocalSplitCandidates;
	1093	mLocalSplitCandidates = new vector<SortableEntry>;
[1002]	1094	}
	1095
[1178]	1096	mLocalSplitCandidates->reserve(requestedSize);
[1002]	1097
[1178]	1098
[1002]	1099	float pos;
	1100
[1137]	1101	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	1102
[1084]	1103	//-- insert all queries
[1137]	1104	for (rit = rays.begin(); rit != rit_end; ++ rit)
[1002]	1105	{
[1137]	1106	const bool positive = (*rit).mRay->HasPosDir(axis);
[1002]	1107
[1137]	1108	pos = (*rit).ExtrapOrigin(axis);
[1002]	1109
[1178]	1110	mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
[1137]	1111	pos, (*rit).mRay));
[1002]	1112
[1137]	1113	pos = (*rit).ExtrapTermination(axis);
[1002]	1114
[1178]	1115	mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
[1137]	1116	pos, (*rit).mRay));
[1002]	1117	}
	1118
[1178]	1119	stable_sort(mLocalSplitCandidates->begin(), mLocalSplitCandidates->end());
[1002]	1120	}
	1121
	1122
[1072]	1123	int VspTree::GetPvsContribution(Intersectable *object) const
	1124	{
	1125	int pvsContri = 0;
	1126
	1127	KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
	1128
	1129	Intersectable::NewMail();
	1130
	1131	// Search kd leaves this object is attached to
	1132	for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	1133	{
	1134	KdNode l = (kit).first;
	1135
	1136	// new object found during sweep
	1137	// => increase pvs contribution of this kd node
	1138	if (!l->Mailed())
	1139	{
	1140	l->Mail();
	1141	++ pvsContri;
	1142	}
	1143	}
	1144
	1145	return pvsContri;
	1146	}
	1147
	1148
[1138]	1149	int VspTree::PrepareHeuristics(KdLeaf *leaf)
[1135]	1150	{
	1151	int pvsSize = 0;
[1138]	1152
	1153	if (!leaf->Mailed())
	1154	{
	1155	leaf->Mail();
	1156	leaf->mCounter = 1;
[1074]	1157
[1138]	1158	// add objects without the objects which are in several kd leaves
	1159	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
[1166]	1160	//Debug << "adding " << (int)leaf->mObjects.size() << " " << leaf->mMultipleObjects.size() << endl;
[1138]	1161	}
	1162	else
[1074]	1163	{
[1138]	1164	++ leaf->mCounter;
	1165	}
[1074]	1166
[1138]	1167	//-- the objects belonging to several leaves must be handled seperately
	1168
	1169	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
	1170
	1171	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1172	{
	1173	Intersectable object = oit;
	1174
	1175	if (!object->Mailed())
[1074]	1176	{
[1138]	1177	object->Mail();
	1178	object->mCounter = 1;
[1074]	1179
[1138]	1180	++ pvsSize;
[1074]	1181	}
	1182	else
	1183	{
[1138]	1184	++ object->mCounter;
[1074]	1185	}
	1186	}
[1138]	1187
[1074]	1188	return pvsSize;
	1189	}
	1190
	1191
	1192	int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
[1072]	1193	{
[1074]	1194	Intersectable::NewMail();
	1195	KdNode::NewMail();
[1072]	1196
[1074]	1197	int pvsSize = 0;
[1072]	1198
[1074]	1199	RayInfoContainer::const_iterator ri, ri_end = rays.end();
[1072]	1200
[1144]	1201	//-- set all kd nodes / objects as belonging to the front pvs
[1074]	1202
	1203	for (ri = rays.begin(); ri != ri_end; ++ ri)
[1072]	1204	{
[1138]	1205	VssRay ray = (ri).mRay;
	1206	Intersectable *oObject = ray->mOriginObject;
[1074]	1207
	1208	if (oObject)
	1209	{
[1141]	1210	if (!mUseKdPvsForHeuristics)
[1074]	1211	{
	1212	if (!oObject->Mailed())
	1213	{
	1214	oObject->Mail();
	1215	oObject->mCounter = 1;
[1176]	1216
[1074]	1217	++ pvsSize;
	1218	}
	1219	else
	1220	{
	1221	++ oObject->mCounter;
	1222	}
	1223	}
	1224	else
	1225	{
[1138]	1226	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
	1227	pvsSize += PrepareHeuristics(leaf);
[1074]	1228	}
	1229	}
	1230
	1231	Intersectable tObject = (ri).mRay->mTerminationObject;
	1232
	1233	if (tObject)
	1234	{
[1141]	1235	if (!mUseKdPvsForHeuristics)
[1074]	1236	{
	1237	if (!tObject->Mailed())
	1238	{
	1239	tObject->Mail();
	1240	tObject->mCounter = 1;
	1241	++ pvsSize;
	1242	}
	1243	else
	1244	{
	1245	++ tObject->mCounter;
	1246	}
	1247	}
	1248	else
	1249	{
[1138]	1250	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
	1251	pvsSize += PrepareHeuristics(leaf);
[1074]	1252	}
	1253	}
[1072]	1254	}
[1074]	1255
	1256	return pvsSize;
[1072]	1257	}
	1258
	1259
[1074]	1260	void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const
[1072]	1261	{
[1074]	1262	// leaf falls out of right pvs
	1263	if (-- leaf->mCounter == 0)
[1072]	1264	{
[1074]	1265	pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
	1266	}
[1072]	1267
[1074]	1268	//-- handle objects which are in several kd leaves separately
	1269	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
[1072]	1270
[1074]	1271	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1272	{
	1273	Intersectable object = oit;
[1072]	1274
[1074]	1275	if (-- object->mCounter == 0)
	1276	{
	1277	-- pvs;
	1278	}
[1072]	1279	}
	1280	}
	1281
	1282
[1074]	1283	void VspTree::AddContriToPvs(KdLeaf *leaf, int &pvs) const
[1072]	1284	{
[1121]	1285	if (leaf->Mailed())
	1286	return;
	1287
	1288	leaf->Mail();
[1072]	1289
[1121]	1290	// add objects without those which are part of several kd leaves
	1291	pvs += ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
[1072]	1292
[1121]	1293	//-- handle objects of several kd leaves separately
	1294	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
[1072]	1295
[1121]	1296	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1297	{
	1298	Intersectable object = oit;
	1299
[1144]	1300	// object not previously in pvs
[1121]	1301	if (!object->Mailed())
[1074]	1302	{
[1121]	1303	object->Mail();
	1304	++ pvs;
[1074]	1305	}
	1306	}
	1307	}
[1072]	1308
	1309
[1074]	1310	void VspTree::EvalPvsIncr(const SortableEntry &ci,
	1311	int &pvsLeft,
	1312	int &pvsRight) const
	1313	{
	1314	VssRay *ray = ci.ray;
[1072]	1315
[1074]	1316	Intersectable *oObject = ray->mOriginObject;
	1317	Intersectable *tObject = ray->mTerminationObject;
[1072]	1318
[1074]	1319	if (oObject)
	1320	{
[1141]	1321	if (!mUseKdPvsForHeuristics)
[1072]	1322	{
[1074]	1323	if (ci.type == SortableEntry::ERayMin)
[1072]	1324	{
[1074]	1325	if (!oObject->Mailed())
[1072]	1326	{
[1074]	1327	oObject->Mail();
	1328	++ pvsLeft;
[1072]	1329	}
[1074]	1330	}
	1331	else if (ci.type == SortableEntry::ERayMax)
	1332	{
	1333	if (-- oObject->mCounter == 0)
	1334	-- pvsRight;
	1335	}
[1072]	1336	}
[1074]	1337	else // per kd node
[1072]	1338	{
[1138]	1339	KdLeaf *node = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
[1074]	1340
[1138]	1341	// add contributions of the kd nodes
	1342	if (ci.type == SortableEntry::ERayMin)
[1072]	1343	{
[1138]	1344	AddContriToPvs(node, pvsLeft);
[1074]	1345	}
[1138]	1346	else if (ci.type == SortableEntry::ERayMax)
	1347	{
	1348	RemoveContriFromPvs(node, pvsRight);
	1349	}
[1072]	1350	}
[1074]	1351	}
	1352
	1353	if (tObject)
	1354	{
[1141]	1355	if (!mUseKdPvsForHeuristics)
[1074]	1356	{
	1357	if (ci.type == SortableEntry::ERayMin)
[1072]	1358	{
[1074]	1359	if (!tObject->Mailed())
	1360	{
	1361	tObject->Mail();
	1362	++ pvsLeft;
	1363	}
[1072]	1364	}
[1074]	1365	else if (ci.type == SortableEntry::ERayMax)
[1072]	1366	{
[1074]	1367	if (-- tObject->mCounter == 0)
	1368	-- pvsRight;
[1072]	1369	}
	1370	}
[1074]	1371	else // per kd node
[1072]	1372	{
[1138]	1373	KdLeaf *node = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
[1072]	1374
[1138]	1375	if (ci.type == SortableEntry::ERayMin)
	1376	{
	1377	AddContriToPvs(node, pvsLeft);
[1072]	1378	}
[1138]	1379	else if (ci.type == SortableEntry::ERayMax)
	1380	{
	1381	RemoveContriFromPvs(node, pvsRight);
	1382	}
[1072]	1383	}
	1384	}
	1385	}
	1386
	1387
[1135]	1388	float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
[1074]	1389	const AxisAlignedBox3 &box,
	1390	const int axis,
	1391	float &position)
[1072]	1392	{
[1149]	1393	RayInfoContainer usedRays;
	1394
	1395	if (mMaxTests < (int)tData.mRays->size())
	1396	{
	1397	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
	1398	}
	1399	else
	1400	{
	1401	usedRays = *tData.mRays;
	1402	}
	1403
[1135]	1404	int pvsSize = tData.mPvs;
	1405
[1072]	1406	const float minBox = box.Min(axis);
	1407	const float maxBox = box.Max(axis);
	1408
	1409	const float sizeBox = maxBox - minBox;
	1410
	1411	const float minBand = minBox + mMinBand * sizeBox;
	1412	const float maxBand = minBox + mMaxBand * sizeBox;
	1413
[1149]	1414	SortSplitCandidates(usedRays, axis, minBand, maxBand);
[1072]	1415
[1077]	1416	// prepare the sweep
[1074]	1417	// (note: returns pvs size, so there would be no need
	1418	// to give pvs size as argument)
[1149]	1419	pvsSize = PrepareHeuristics(usedRays);
[1074]	1420
[1072]	1421	// go through the lists, count the number of objects left and right
	1422	// and evaluate the following cost funcion:
	1423	// C = ct_div_ci + (qlrl + qrrr)/queries
	1424
	1425	int pvsl = 0;
	1426	int pvsr = pvsSize;
	1427
	1428	int pvsBack = pvsl;
	1429	int pvsFront = pvsr;
	1430
	1431	float sum = (float)pvsSize * sizeBox;
	1432	float minSum = 1e20f;
	1433
	1434
	1435	// if no good split can be found, take mid split
	1436	position = minBox + 0.5f * sizeBox;
	1437
	1438	// the relative cost ratio
[1074]	1439	float ratio = 99999999.0f;
[1072]	1440	bool splitPlaneFound = false;
	1441
	1442	Intersectable::NewMail();
[1074]	1443	KdLeaf::NewMail();
[1072]	1444
	1445
[1074]	1446	//-- traverse through visibility events
	1447
[1178]	1448	vector<SortableEntry>::const_iterator ci, ci_end = mLocalSplitCandidates->end();
	1449
	1450	for (ci = mLocalSplitCandidates->begin(); ci != ci_end; ++ ci)
[1072]	1451	{
[1074]	1452	EvalPvsIncr(*ci, pvsl, pvsr);
	1453
[1072]	1454	// Note: sufficient to compare size of bounding boxes of front and back side?
	1455	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	1456	{
[1146]	1457
	1458	float currentPos;
	1459
	1460	// HACK: current positition is BETWEEN visibility events
[1149]	1461	if (0 && ((ci + 1) != ci_end))
[1146]	1462	currentPos = ((ci).value + ((ci + 1)).value) * 0.5f;
	1463	else
	1464	currentPos = (*ci).value;
	1465
[1072]	1466	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
[1147]	1467	//Debug << "pos=" << (*ci).value << "\t newpos=" << currentPos << "\t pvs=(" << pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl;
[1072]	1468
	1469	if (sum < minSum)
	1470	{
	1471	splitPlaneFound = true;
	1472
	1473	minSum = sum;
[1147]	1474	position = currentPos;
[1072]	1475
	1476	pvsBack = pvsl;
	1477	pvsFront = pvsr;
	1478	}
	1479	}
	1480	}
	1481
[1074]	1482
[1147]	1483	//-- compute cost
[1072]	1484
	1485	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1486	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1487
	1488	const float pOverall = sizeBox;
	1489	const float pBack = position - minBox;
	1490	const float pFront = maxBox - position;
	1491
	1492	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	1493	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1494	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1495
	1496	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
	1497	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1498
	1499	if (splitPlaneFound)
	1500	{
	1501	ratio = newRenderCost / oldRenderCost;
	1502	}
[1074]	1503
[1178]	1504	const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
	1505
	1506	/*
	1507	//if (axis != 1)
[1145]	1508	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1509	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
[1072]	1510
[1178]	1511	Debug << "\n§§§§ eval local cost §§§§" << endl
[1145]	1512	<< "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
	1513	<< "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
	1514	<< "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
	1515	<< "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
[1178]	1516	*/
[1072]	1517	return ratio;
[1077]	1518	}
[1072]	1519
	1520
[1027]	1521	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
	1522	AxisAlignedPlane &plane,
	1523	float &pFront,
	1524	float &pBack)
[1002]	1525	{
	1526	float nPosition[3];
	1527	float nCostRatio[3];
	1528	float nProbFront[3];
	1529	float nProbBack[3];
	1530
	1531	// create bounding box of node geometry
[1006]	1532	AxisAlignedBox3 box = tData.mBoundingBox;
[1002]	1533
	1534	int sAxis = 0;
[1006]	1535	int bestAxis = -1;
[1002]	1536
	1537	// if we use some kind of specialised fixed axis
	1538	const bool useSpecialAxis =
[1023]	1539	mOnlyDrivingAxis \|\| mCirculatingAxis;
[1074]	1540	//Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
[1047]	1541	if (mCirculatingAxis)
	1542	{
	1543	int parentAxis = 0;
	1544	VspNode *parent = tData.mNode->GetParent();
[1002]	1545
[1047]	1546	if (parent)
	1547	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
[1027]	1548
	1549	sAxis = (parentAxis + 1) % 3;
[1047]	1550	}
[1002]	1551	else if (mOnlyDrivingAxis)
[1047]	1552	{
[1002]	1553	sAxis = box.Size().DrivingAxis();
[1047]	1554	}
[1106]	1555
[1047]	1556	for (int axis = 0; axis < 3; ++ axis)
[1002]	1557	{
	1558	if (!useSpecialAxis \|\| (axis == sAxis))
	1559	{
	1560	if (mUseCostHeuristics)
	1561	{
[1106]	1562	//-- place split plane using heuristics
[1002]	1563	nCostRatio[axis] =
[1135]	1564	EvalLocalCostHeuristics(tData,
[1027]	1565	box,
[1002]	1566	axis,
	1567	nPosition[axis]);
	1568	}
[1106]	1569	else
[1002]	1570	{
[1106]	1571	//-- split plane position is spatial median
[1002]	1572	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
[1027]	1573	nCostRatio[axis] = EvalLocalSplitCost(tData,
	1574	box,
	1575	axis,
	1576	nPosition[axis],
	1577	nProbFront[axis],
	1578	nProbBack[axis]);
[1002]	1579	}
	1580
[1006]	1581	if (bestAxis == -1)
[1002]	1582	{
[1006]	1583	bestAxis = axis;
[1002]	1584	}
[1006]	1585	else if (nCostRatio[axis] < nCostRatio[bestAxis])
[1002]	1586	{
[1006]	1587	bestAxis = axis;
[1002]	1588	}
	1589	}
	1590	}
	1591
[1047]	1592
[1108]	1593	//-- assign values of best split
[1047]	1594
[1006]	1595	plane.mAxis = bestAxis;
[1108]	1596	plane.mPosition = nPosition[bestAxis]; // split plane position
[1047]	1597
[1002]	1598	pFront = nProbFront[bestAxis];
	1599	pBack = nProbBack[bestAxis];
	1600
[1074]	1601	//Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1002]	1602	return nCostRatio[bestAxis];
	1603	}
	1604
	1605
[1016]	1606	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
[1145]	1607	const VspTraversalData &data,
	1608	float &normalizedOldRenderCost) const
[1002]	1609	{
	1610	float pvsFront = 0;
	1611	float pvsBack = 0;
	1612	float totalPvs = 0;
	1613
	1614	// probability that view point lies in back / front node
	1615	float pOverall = data.mProbability;
	1616	float pFront = 0;
	1617	float pBack = 0;
	1618
[1145]	1619	const float viewSpaceVol = mBoundingBox.GetVolume();
[1002]	1620
	1621	// create unique ids for pvs heuristics
[1145]	1622	Intersectable::NewMail(3);
[1176]	1623	KdLeaf::NewMail(3);
	1624
[1016]	1625	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
[1015]	1626
[1016]	1627	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
[1002]	1628	{
[1015]	1629	RayInfo rayInf = *rit;
[1002]	1630
	1631	float t;
	1632	VssRay *ray = rayInf.mRay;
[1027]	1633
[1008]	1634	const int cf =
	1635	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
	1636	candidatePlane.mPosition, t);
[1002]	1637
[1176]	1638	if (!mUseKdPvsForHeuristics)
	1639	{
	1640	// find front and back pvs for origing and termination object
	1641	UpdateObjPvsContri(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
	1642	UpdateObjPvsContri(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
	1643	}
	1644	else
	1645	{
	1646	if (ray->mTerminationObject)
	1647	{
	1648	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
	1649	UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
	1650	}
	1651
	1652	if (ray->mOriginObject)
	1653	{
	1654	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
	1655	UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
	1656	}
	1657	}
[1002]	1658	}
	1659
[1027]	1660
[1011]	1661	AxisAlignedBox3 frontBox;
	1662	AxisAlignedBox3 backBox;
	1663
	1664	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
	1665
	1666	pFront = frontBox.GetVolume();
[1006]	1667	pBack = pOverall - pFront;
	1668
	1669
[1020]	1670	//-- pvs rendering heuristics
[1002]	1671	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1672	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1673
[1020]	1674	//-- only render cost heuristics or combined with standard deviation
	1675	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	1676	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	1677	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[1002]	1678
	1679	const float oldRenderCost = pOverall * penaltyOld;
	1680	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1681
[1145]	1682	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
	1683
	1684	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
[1178]	1685	/*
[1145]	1686	Debug << "\n==== eval render cost decrease ===" << endl
	1687	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
	1688	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
	1689	<< "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
	1690	<< "render cost decrease: " << renderCostDecrease << endl;
[1178]	1691	*/
[1145]	1692	return renderCostDecrease;
[1002]	1693	}
	1694
	1695
[1027]	1696	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
	1697	const AxisAlignedBox3 &box,
	1698	const int axis,
	1699	const float &position,
	1700	float &pFront,
	1701	float &pBack) const
[1002]	1702	{
	1703	float pvsTotal = 0;
	1704	float pvsFront = 0;
	1705	float pvsBack = 0;
	1706
	1707	// create unique ids for pvs heuristics
[1145]	1708	Intersectable::NewMail(3);
[1002]	1709
	1710	const int pvsSize = data.mPvs;
	1711
	1712	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
	1713
	1714	// this is the main ray classification loop!
	1715	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
	1716	{
	1717	// determine the side of this ray with respect to the plane
	1718	float t;
	1719	const int side = (*rit).ComputeRayIntersection(axis, position, t);
	1720
[1176]	1721	UpdateObjPvsContri((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
	1722	UpdateObjPvsContri((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
[1002]	1723	}
	1724
[1178]	1725	//-- evaluate cost heuristics
	1726
[1002]	1727	float pOverall;
[1027]	1728
[1002]	1729	pOverall = data.mProbability;
[1108]	1730
[1145]	1731	// we use spatial mid split => simplified computation
[1006]	1732	pBack = pFront = pOverall * 0.5f;
	1733
[1108]	1734	const float newCost = pvsBack * pBack + pvsFront * pFront;
	1735	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
[1006]	1736
[1002]	1737	#ifdef _DEBUG
	1738	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	1739	Debug << pFront << " " << pBack << " " << pOverall << endl;
	1740	#endif
	1741
	1742	return (mCtDivCi + newCost) / oldCost;
	1743	}
	1744
	1745
[1176]	1746	void VspTree::UpdateObjPvsContri(Intersectable *obj,
[1027]	1747	const int cf,
	1748	float &frontPvs,
	1749	float &backPvs,
	1750	float &totalPvs) const
[1002]	1751	{
[1176]	1752	if (!obj) return;
[1002]	1753
[1145]	1754	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
[1076]	1755	const int renderCost = 1;
[1002]	1756
[1089]	1757	// object in no pvs => new
	1758	if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
[1002]	1759	{
	1760	totalPvs += renderCost;
	1761	}
	1762
[1145]	1763	// QUESTION matt: is it safe to assume that
	1764	// the object belongs to no pvs in this case?
[1002]	1765	//if (cf == Ray::COINCIDENT) return;
	1766
[1089]	1767	if (cf >= 0) // front pvs
[1002]	1768	{
[1089]	1769	if (!obj->Mailed() && !obj->Mailed(2))
[1002]	1770	{
	1771	frontPvs += renderCost;
	1772
[1089]	1773	// already in back pvs => in both pvss
	1774	if (obj->Mailed(1))
	1775	obj->Mail(2);
[1002]	1776	else
[1089]	1777	obj->Mail();
[1002]	1778	}
	1779	}
	1780
[1089]	1781	if (cf <= 0) // back pvs
[1002]	1782	{
[1089]	1783	if (!obj->Mailed(1) && !obj->Mailed(2))
[1002]	1784	{
	1785	backPvs += renderCost;
	1786
[1089]	1787	// already in front pvs => in both pvss
	1788	if (obj->Mailed())
	1789	obj->Mail(2);
[1002]	1790	else
[1089]	1791	obj->Mail(1);
[1002]	1792	}
	1793	}
	1794	}
	1795
	1796
[1176]	1797	void VspTree::UpdateKdLeafPvsContri(KdLeaf *leaf,
	1798	const int cf,
	1799	float &frontPvs,
	1800	float &backPvs,
	1801	float &totalPvs) const
	1802	{
	1803	if (!leaf) return;
	1804
	1805	// the objects which are referenced in this and only this leaf
	1806	const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
	1807
	1808	// newly found leaf
	1809	if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
	1810	{
	1811	totalPvs += contri;
	1812	}
	1813
	1814	// compute contribution of yet unclassified objects
	1815	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
	1816
	1817	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1818	{
	1819	UpdateObjPvsContri(*oit, cf, frontPvs, backPvs, totalPvs);
	1820	}
	1821
	1822	// QUESTION matt: is it safe to assume that
	1823	// the object belongs to no pvs in this case?
	1824	//if (cf == Ray::COINCIDENT) return;
	1825
	1826	if (cf >= 0) // front pvs
	1827	{
	1828	if (!leaf->Mailed() && !leaf->Mailed(2))
	1829	{
	1830	frontPvs += contri;
	1831
	1832	// already in back pvs => in both pvss
	1833	if (leaf->Mailed(1))
	1834	leaf->Mail(2);
	1835	else
	1836	leaf->Mail();
	1837	}
	1838	}
	1839
	1840	if (cf <= 0) // back pvs
	1841	{
	1842	if (!leaf->Mailed(1) && !leaf->Mailed(2))
	1843	{
	1844	backPvs += contri;
	1845
	1846	// already in front pvs => in both pvss
	1847	if (leaf->Mailed())
	1848	leaf->Mail(2);
	1849	else
	1850	leaf->Mail(1);
	1851	}
	1852	}
	1853	}
	1854
	1855
[1016]	1856	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
[1176]	1857	const bool onlyUnmailed,
	1858	const int maxPvsSize) const
[1002]	1859	{
[1008]	1860	stack<VspNode *> nodeStack;
[1002]	1861	nodeStack.push(mRoot);
	1862
	1863	while (!nodeStack.empty())
	1864	{
[1008]	1865	VspNode *node = nodeStack.top();
[1002]	1866	nodeStack.pop();
	1867
	1868	if (node->IsLeaf())
	1869	{
	1870	// test if this leaf is in valid view space
[1008]	1871	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1872	if (leaf->TreeValid() &&
	1873	(!onlyUnmailed \|\| !leaf->Mailed()) &&
[1168]	1874	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
[1002]	1875	{
	1876	leaves.push_back(leaf);
	1877	}
	1878	}
	1879	else
	1880	{
[1008]	1881	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1882
	1883	nodeStack.push(interior->GetBack());
	1884	nodeStack.push(interior->GetFront());
	1885	}
	1886	}
	1887	}
	1888
	1889
[1016]	1890	AxisAlignedBox3 VspTree::GetBoundingBox() const
[1002]	1891	{
[1020]	1892	return mBoundingBox;
[1002]	1893	}
	1894
	1895
[1016]	1896	VspNode *VspTree::GetRoot() const
[1002]	1897	{
	1898	return mRoot;
	1899	}
	1900
	1901
[1016]	1902	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
[1002]	1903	{
	1904	// the node became a leaf -> evaluate stats for leafs
[1008]	1905	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
[1002]	1906
	1907
[1008]	1908	if (data.mPvs > mVspStats.maxPvs)
[1002]	1909	{
[1008]	1910	mVspStats.maxPvs = data.mPvs;
[1002]	1911	}
	1912
[1008]	1913	mVspStats.pvs += data.mPvs;
[1002]	1914
[1008]	1915	if (data.mDepth < mVspStats.minDepth)
[1002]	1916	{
[1008]	1917	mVspStats.minDepth = data.mDepth;
[1002]	1918	}
	1919
	1920	if (data.mDepth >= mTermMaxDepth)
	1921	{
[1008]	1922	++ mVspStats.maxDepthNodes;
	1923	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
[1002]	1924	}
	1925
	1926	// accumulate rays to compute rays / leaf
[1008]	1927	mVspStats.accumRays += (int)data.mRays->size();
[1002]	1928
	1929	if (data.mPvs < mTermMinPvs)
[1008]	1930	++ mVspStats.minPvsNodes;
[1002]	1931
	1932	if ((int)data.mRays->size() < mTermMinRays)
[1008]	1933	++ mVspStats.minRaysNodes;
[1002]	1934
	1935	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
[1008]	1936	++ mVspStats.maxRayContribNodes;
[1002]	1937
	1938	if (data.mProbability <= mTermMinProbability)
[1008]	1939	++ mVspStats.minProbabilityNodes;
[1002]	1940
	1941	// accumulate depth to compute average depth
[1008]	1942	mVspStats.accumDepth += data.mDepth;
[1002]	1943
	1944	++ mCreatedViewCells;
	1945
[1074]	1946	#ifdef _DEBUG
[1002]	1947	Debug << "BSP stats: "
	1948	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	1949	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	1950	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1168]	1951	<< "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
[1002]	1952	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
[1074]	1953	#endif
[1002]	1954	}
	1955
	1956
[1016]	1957	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
[1002]	1958	{
	1959	ViewCell::NewMail();
	1960	CollectViewCells(mRoot, onlyValid, viewCells, true);
	1961	}
	1962
	1963
[1016]	1964	void VspTree::CollapseViewCells()
[1002]	1965	{
[1111]	1966	// TODO matt
[1002]	1967	#if HAS_TO_BE_REDONE
[1008]	1968	stack<VspNode *> nodeStack;
[1002]	1969
	1970	if (!mRoot)
	1971	return;
	1972
	1973	nodeStack.push(mRoot);
	1974
	1975	while (!nodeStack.empty())
	1976	{
[1008]	1977	VspNode *node = nodeStack.top();
[1002]	1978	nodeStack.pop();
	1979
	1980	if (node->IsLeaf())
	1981	{
[1008]	1982	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1983
	1984	if (!viewCell->GetValid())
	1985	{
[1008]	1986	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1987
	1988	ViewCellContainer leaves;
	1989	mViewCellsTree->CollectLeaves(viewCell, leaves);
	1990
	1991	ViewCellContainer::const_iterator it, it_end = leaves.end();
	1992
	1993	for (it = leaves.begin(); it != it_end; ++ it)
	1994	{
[1008]	1995	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
[1002]	1996	l->SetViewCell(GetOrCreateOutOfBoundsCell());
[1008]	1997	++ mVspStats.invalidLeaves;
[1002]	1998	}
	1999
	2000	// add to unbounded view cell
	2001	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
	2002	DEL_PTR(viewCell);
	2003	}
	2004	}
	2005	else
	2006	{
[1008]	2007	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2008
	2009	nodeStack.push(interior->GetFront());
	2010	nodeStack.push(interior->GetBack());
	2011	}
	2012	}
	2013
[1008]	2014	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	2015	#endif
	2016	}
	2017
	2018
[1016]	2019	void VspTree::CollectRays(VssRayContainer &rays)
[1002]	2020	{
[1008]	2021	vector<VspLeaf *> leaves;
[1178]	2022	CollectLeaves(leaves);
[1002]	2023
[1008]	2024	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
[1002]	2025
	2026	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	2027	{
[1008]	2028	VspLeaf leaf = lit;
[1002]	2029	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	2030
	2031	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	2032	rays.push_back(*rit);
	2033	}
	2034	}
	2035
	2036
[1021]	2037	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
	2038	{
	2039	mViewCellsManager = vcm;
	2040	}
	2041
	2042
[1016]	2043	void VspTree::ValidateTree()
[1002]	2044	{
[1020]	2045	mVspStats.invalidLeaves = 0;
	2046
[1008]	2047	stack<VspNode *> nodeStack;
[1002]	2048
	2049	if (!mRoot)
	2050	return;
	2051
	2052	nodeStack.push(mRoot);
[1020]	2053
[1002]	2054	while (!nodeStack.empty())
	2055	{
[1008]	2056	VspNode *node = nodeStack.top();
[1002]	2057	nodeStack.pop();
	2058
	2059	if (node->IsLeaf())
	2060	{
[1008]	2061	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	2062
	2063	if (!leaf->GetViewCell()->GetValid())
[1008]	2064	++ mVspStats.invalidLeaves;
[1002]	2065
	2066	// validity flags don't match => repair
	2067	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
	2068	{
	2069	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
	2070	PropagateUpValidity(leaf);
	2071	}
	2072	}
	2073	else
	2074	{
[1008]	2075	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2076
	2077	nodeStack.push(interior->GetFront());
	2078	nodeStack.push(interior->GetBack());
	2079	}
	2080	}
	2081
[1008]	2082	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	2083	}
	2084
	2085
	2086
[1016]	2087	void VspTree::CollectViewCells(VspNode *root,
[1002]	2088	bool onlyValid,
	2089	ViewCellContainer &viewCells,
	2090	bool onlyUnmailed) const
	2091	{
[1008]	2092	stack<VspNode *> nodeStack;
[1002]	2093
	2094	if (!root)
	2095	return;
	2096
	2097	nodeStack.push(root);
	2098
	2099	while (!nodeStack.empty())
	2100	{
[1008]	2101	VspNode *node = nodeStack.top();
[1002]	2102	nodeStack.pop();
	2103
	2104	if (node->IsLeaf())
	2105	{
	2106	if (!onlyValid \|\| node->TreeValid())
	2107	{
[1008]	2108	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	2109
	2110	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
	2111
	2112	if (!onlyUnmailed \|\| !viewCell->Mailed())
	2113	{
	2114	viewCell->Mail();
	2115	viewCells.push_back(viewCell);
	2116	}
	2117	}
	2118	}
	2119	else
	2120	{
[1008]	2121	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2122
	2123	nodeStack.push(interior->GetFront());
	2124	nodeStack.push(interior->GetBack());
	2125	}
	2126	}
	2127	}
	2128
	2129
[1016]	2130	int VspTree::FindNeighbors(VspLeaf *n,
[1020]	2131	vector<VspLeaf *> &neighbors,
	2132	const bool onlyUnmailed) const
[1002]	2133	{
[1012]	2134	stack<VspNode *> nodeStack;
	2135	nodeStack.push(mRoot);
[1002]	2136
[1144]	2137	const AxisAlignedBox3 box = GetBoundingBox(n);
[1002]	2138
	2139	while (!nodeStack.empty())
	2140	{
[1008]	2141	VspNode *node = nodeStack.top();
[1002]	2142	nodeStack.pop();
	2143
	2144	if (node->IsLeaf())
	2145	{
[1012]	2146	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	2147
	2148	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
	2149	neighbors.push_back(leaf);
[1002]	2150	}
	2151	else
	2152	{
[1008]	2153	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	2154
	2155	if (interior->GetPosition() > box.Max(interior->GetAxis()))
	2156	nodeStack.push(interior->GetBack());
	2157	else
	2158	{
	2159	if (interior->GetPosition() < box.Min(interior->GetAxis()))
	2160	nodeStack.push(interior->GetFront());
	2161	else
	2162	{
	2163	// random decision
	2164	nodeStack.push(interior->GetBack());
	2165	nodeStack.push(interior->GetFront());
	2166	}
	2167	}
	2168	}
	2169	}
[1002]	2170
[1012]	2171	return (int)neighbors.size();
	2172	}
[1002]	2173
	2174
[1012]	2175	// Find random neighbor which was not mailed
[1016]	2176	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
[1012]	2177	{
	2178	stack<VspNode *> nodeStack;
	2179	nodeStack.push(mRoot);
	2180
	2181	int mask = rand();
	2182
	2183	while (!nodeStack.empty())
	2184	{
	2185	VspNode *node = nodeStack.top();
	2186
	2187	nodeStack.pop();
	2188
	2189	if (node->IsLeaf())
	2190	{
	2191	return dynamic_cast<VspLeaf *>(node);
	2192	}
	2193	else
	2194	{
	2195	VspInterior interior = dynamic_cast<VspInterior >(node);
	2196	VspNode *next;
	2197
[1144]	2198	if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
[1027]	2199	{
[1002]	2200	next = interior->GetFront();
[1027]	2201	}
[1012]	2202	else
[1027]	2203	{
[1144]	2204	if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
[1027]	2205	{
[1002]	2206	next = interior->GetBack();
[1027]	2207	}
[1012]	2208	else
	2209	{
	2210	// random decision
	2211	if (mask & 1)
	2212	next = interior->GetBack();
	2213	else
	2214	next = interior->GetFront();
	2215	mask = mask >> 1;
	2216	}
[1027]	2217	}
	2218
	2219	nodeStack.push(next);
[1002]	2220	}
	2221	}
[1012]	2222
[1002]	2223	return NULL;
	2224	}
	2225
	2226
[1016]	2227	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
[1002]	2228	{
[1008]	2229	stack<VspNode *> nodeStack;
[1002]	2230
	2231	nodeStack.push(mRoot);
	2232
	2233	int mask = rand();
	2234
	2235	while (!nodeStack.empty())
	2236	{
[1008]	2237	VspNode *node = nodeStack.top();
[1002]	2238	nodeStack.pop();
	2239
	2240	if (node->IsLeaf())
	2241	{
	2242	if ( (!onlyUnmailed \|\| !node->Mailed()) )
[1008]	2243	return dynamic_cast<VspLeaf *>(node);
[1002]	2244	}
	2245	else
	2246	{
[1008]	2247	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2248
	2249	// random decision
	2250	if (mask & 1)
	2251	nodeStack.push(interior->GetBack());
	2252	else
	2253	nodeStack.push(interior->GetFront());
	2254
	2255	mask = mask >> 1;
	2256	}
	2257	}
	2258
	2259	return NULL;
	2260	}
	2261
	2262
[1072]	2263	void VspTree::CollectPvs(const RayInfoContainer &rays,
	2264	ObjectContainer &objects) const
	2265	{
	2266	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2267
	2268	Intersectable::NewMail();
	2269
	2270	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2271	{
	2272	VssRay ray = (rit).mRay;
	2273
	2274	Intersectable *object;
	2275	object = ray->mOriginObject;
	2276
	2277	if (object)
	2278	{
	2279	if (!object->Mailed())
	2280	{
	2281	object->Mail();
	2282	objects.push_back(object);
	2283	}
	2284	}
	2285
	2286	object = ray->mTerminationObject;
	2287
	2288	if (object)
	2289	{
	2290	if (!object->Mailed())
	2291	{
	2292	object->Mail();
	2293	objects.push_back(object);
	2294	}
	2295	}
	2296	}
	2297	}
	2298
	2299
[1181]	2300	int VspTree::EvalPvsSize(const RayInfoContainer &rays) const
[1002]	2301	{
	2302	int pvsSize = 0;
[1176]	2303	Intersectable::NewMail();
[1002]	2304
	2305	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2306
[1176]	2307	if (!mUseKdPvsForHeuristics)
[1002]	2308	{
[1176]	2309	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2310	{
	2311	VssRay ray = (rit).mRay;
[1002]	2312
[1176]	2313	if (ray->mOriginObject)
[1002]	2314	{
[1176]	2315	if (!ray->mOriginObject->Mailed())
	2316	{
	2317	ray->mOriginObject->Mail();
	2318	++ pvsSize;
	2319	}
[1002]	2320	}
[1176]	2321	if (ray->mTerminationObject)
	2322	{
	2323	if (!ray->mTerminationObject->Mailed())
	2324	{
	2325	ray->mTerminationObject->Mail();
	2326	++ pvsSize;
	2327	}
	2328	}
[1002]	2329	}
[1176]	2330	}
[1181]	2331	else // compute pvs from kd nodes
[1176]	2332	{
	2333	KdNode::NewMail();
	2334
	2335	for (rit = rays.begin(); rit != rays.end(); ++ rit)
[1002]	2336	{
[1176]	2337	VssRay ray = (rit).mRay;
	2338
	2339	if (ray->mTerminationObject)
[1002]	2340	{
[1176]	2341	KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
	2342
	2343	if (!leaf->Mailed())
	2344	{
	2345	leaf->Mail();
	2346	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
	2347
	2348	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
	2349	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	2350	{
	2351	Intersectable obj = oit;
	2352
	2353	if (!obj->Mailed())
	2354	{
	2355	obj->Mail();
	2356	++ pvsSize;
	2357	}
	2358	}
	2359	}
[1002]	2360	}
[1176]	2361
	2362	if (ray->mOriginObject)
	2363	{
	2364	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
	2365
	2366	if (!leaf->Mailed())
	2367	{
	2368	leaf->Mail();
	2369	pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
	2370
	2371	ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
	2372	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	2373	{
	2374	Intersectable obj = oit;
	2375
	2376	if (!obj->Mailed())
	2377	{
	2378	obj->Mail();
	2379	++ pvsSize;
	2380	}
	2381	}
	2382	}
	2383	}
[1002]	2384	}
	2385	}
	2386
	2387	return pvsSize;
	2388	}
	2389
	2390
[1016]	2391	float VspTree::GetEpsilon() const
[1002]	2392	{
	2393	return mEpsilon;
	2394	}
	2395
	2396
[1016]	2397	int VspTree::CastLineSegment(const Vector3 &origin,
[1027]	2398	const Vector3 &termination,
	2399	ViewCellContainer &viewcells)
[1002]	2400	{
	2401	int hits = 0;
	2402
	2403	float mint = 0.0f, maxt = 1.0f;
[1012]	2404	const Vector3 dir = termination - origin;
[1002]	2405
[1012]	2406	stack<LineTraversalData> tStack;
	2407
[1184]	2408	//Intersectable::NewMail();
[1145]	2409	//ViewCell::NewMail();
[1002]	2410
	2411	Vector3 entp = origin;
	2412	Vector3 extp = termination;
	2413
[1008]	2414	VspNode *node = mRoot;
[1012]	2415	VspNode *farChild;
[1002]	2416
[1012]	2417	float position;
	2418	int axis;
	2419
[1002]	2420	while (1)
	2421	{
	2422	if (!node->IsLeaf())
	2423	{
[1008]	2424	VspInterior in = dynamic_cast<VspInterior >(node);
[1012]	2425	position = in->GetPosition();
	2426	axis = in->GetAxis();
[1002]	2427
[1012]	2428	if (entp[axis] <= position)
[1002]	2429	{
[1012]	2430	if (extp[axis] <= position)
	2431	{
[1047]	2432	node = in->GetBack();
[1012]	2433	// cases N1,N2,N3,P5,Z2,Z3
[1002]	2434	continue;
[1012]	2435	} else
	2436	{
	2437	// case N4
[1047]	2438	node = in->GetBack();
	2439	farChild = in->GetFront();
[1012]	2440	}
	2441	}
	2442	else
[1002]	2443	{
[1012]	2444	if (position <= extp[axis])
	2445	{
[1047]	2446	node = in->GetFront();
[1012]	2447	// cases P1,P2,P3,N5,Z1
[1002]	2448	continue;
[1012]	2449	}
	2450	else
	2451	{
[1047]	2452	node = in->GetFront();
	2453	farChild = in->GetBack();
[1012]	2454	// case P4
	2455	}
[1002]	2456	}
	2457
[1012]	2458	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2459	// case N4 or P4
	2460	const float tdist = (position - origin[axis]) / dir[axis];
	2461	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
[1002]	2462
[1012]	2463	extp = origin + dir * tdist;
	2464	maxt = tdist;
	2465	}
[1002]	2466	else
	2467	{
[1012]	2468	// compute intersection with all objects in this leaf
[1008]	2469	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1012]	2470	ViewCell *vc = leaf->GetViewCell();
	2471
[1145]	2472	// don't have to mail because each view cell belongs to exactly one leaf
	2473	//if (!vc->Mailed())
	2474	//{
	2475	// vc->Mail();
[1012]	2476	viewcells.push_back(vc);
	2477	++ hits;
[1145]	2478	//}
[1012]	2479	#if 0
	2480	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
	2481	#endif
	2482	// get the next node from the stack
	2483	if (tStack.empty())
	2484	break;
	2485
	2486	entp = extp;
	2487	mint = maxt;
[1002]	2488
[1012]	2489	LineTraversalData &s = tStack.top();
	2490	node = s.mNode;
	2491	extp = s.mExitPoint;
	2492	maxt = s.mMaxT;
	2493	tStack.pop();
	2494	}
	2495	}
	2496
	2497	return hits;
	2498	}
	2499
	2500
[1016]	2501	int VspTree::CastRay(Ray &ray)
[1012]	2502	{
	2503	int hits = 0;
	2504
	2505	stack<LineTraversalData> tStack;
	2506	const Vector3 dir = ray.GetDir();
	2507
	2508	float maxt, mint;
	2509
[1020]	2510	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
[1012]	2511	return 0;
	2512
	2513	Intersectable::NewMail();
	2514	ViewCell::NewMail();
	2515
	2516	Vector3 entp = ray.Extrap(mint);
	2517	Vector3 extp = ray.Extrap(maxt);
	2518
	2519	const Vector3 origin = entp;
	2520
	2521	VspNode *node = mRoot;
	2522	VspNode *farChild = NULL;
	2523
	2524	float position;
	2525	int axis;
	2526
	2527	while (1)
	2528	{
	2529	if (!node->IsLeaf())
	2530	{
	2531	VspInterior in = dynamic_cast<VspInterior >(node);
	2532	position = in->GetPosition();
	2533	axis = in->GetAxis();
	2534
	2535	if (entp[axis] <= position)
	2536	{
	2537	if (extp[axis] <= position)
	2538	{
	2539	node = in->GetBack();
	2540	// cases N1,N2,N3,P5,Z2,Z3
	2541	continue;
[1020]	2542	}
	2543	else
[1012]	2544	{
	2545	// case N4
	2546	node = in->GetBack();
	2547	farChild = in->GetFront();
	2548	}
	2549	}
[1002]	2550	else
[1012]	2551	{
	2552	if (position <= extp[axis])
	2553	{
	2554	node = in->GetFront();
	2555	// cases P1,P2,P3,N5,Z1
	2556	continue;
	2557	}
	2558	else
	2559	{
	2560	node = in->GetFront();
	2561	farChild = in->GetBack();
	2562	// case P4
	2563	}
	2564	}
[1002]	2565
[1012]	2566	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2567	// case N4 or P4
	2568	const float tdist = (position - origin[axis]) / dir[axis];
	2569	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
	2570	extp = origin + dir * tdist;
	2571	maxt = tdist;
	2572	}
	2573	else
	2574	{
	2575	// compute intersection with all objects in this leaf
	2576	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	2577	ViewCell *vc = leaf->GetViewCell();
	2578
	2579	if (!vc->Mailed())
[1002]	2580	{
[1012]	2581	vc->Mail();
	2582	// todo: add view cells to ray
[1002]	2583	++ hits;
	2584	}
[1012]	2585	#if 0
[1020]	2586	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
[1012]	2587	#endif
	2588	// get the next node from the stack
[1002]	2589	if (tStack.empty())
	2590	break;
	2591
	2592	entp = extp;
[1012]	2593	mint = maxt;
[1002]	2594
[1012]	2595	LineTraversalData &s = tStack.top();
[1002]	2596	node = s.mNode;
	2597	extp = s.mExitPoint;
[1012]	2598	maxt = s.mMaxT;
[1002]	2599	tStack.pop();
	2600	}
	2601	}
[1012]	2602
[1002]	2603	return hits;
	2604	}
	2605
	2606
[1016]	2607	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
[1002]	2608	{
	2609	if (mRoot == NULL)
	2610	return NULL;
	2611
[1008]	2612	stack<VspNode *> nodeStack;
[1002]	2613	nodeStack.push(mRoot);
	2614
	2615	ViewCellLeaf *viewcell = NULL;
	2616
	2617	while (!nodeStack.empty())
	2618	{
[1008]	2619	VspNode *node = nodeStack.top();
[1002]	2620	nodeStack.pop();
	2621
	2622	if (node->IsLeaf())
	2623	{
[1008]	2624	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
[1002]	2625	break;
	2626	}
	2627	else
	2628	{
[1008]	2629	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	2630
[1002]	2631	// random decision
[1012]	2632	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
[1002]	2633	nodeStack.push(interior->GetBack());
	2634	else
	2635	nodeStack.push(interior->GetFront());
	2636	}
	2637	}
	2638
	2639	if (active)
	2640	return mViewCellsTree->GetActiveViewCell(viewcell);
	2641	else
	2642	return viewcell;
	2643	}
	2644
	2645
[1016]	2646	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
[1002]	2647	{
[1008]	2648	VspNode *node = mRoot;
[1002]	2649
	2650	while (1)
	2651	{
	2652	// early exit
	2653	if (node->TreeValid())
	2654	return true;
	2655
	2656	if (node->IsLeaf())
	2657	return false;
	2658
[1008]	2659	VspInterior in = dynamic_cast<VspInterior >(node);
[1002]	2660
[1012]	2661	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
[1002]	2662	{
	2663	node = in->GetBack();
	2664	}
	2665	else
	2666	{
	2667	node = in->GetFront();
	2668	}
	2669	}
[1012]	2670
[1002]	2671	// should never come here
	2672	return false;
	2673	}
	2674
	2675
[1016]	2676	void VspTree::PropagateUpValidity(VspNode *node)
[1002]	2677	{
	2678	const bool isValid = node->TreeValid();
	2679
	2680	// propagative up invalid flag until only invalid nodes exist over this node
	2681	if (!isValid)
	2682	{
	2683	while (!node->IsRoot() && node->GetParent()->TreeValid())
	2684	{
	2685	node = node->GetParent();
	2686	node->SetTreeValid(false);
	2687	}
	2688	}
	2689	else
	2690	{
	2691	// propagative up valid flag until one of the subtrees is invalid
	2692	while (!node->IsRoot() && !node->TreeValid())
	2693	{
	2694	node = node->GetParent();
[1008]	2695	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2696
	2697	// the parent is valid iff both leaves are valid
	2698	node->SetTreeValid(interior->GetBack()->TreeValid() &&
	2699	interior->GetFront()->TreeValid());
	2700	}
	2701	}
	2702	}
	2703
[1201]	2704
	2705	bool VspTree::Export(OUT_STREAM &stream)
[1002]	2706	{
	2707	ExportNode(mRoot, stream);
	2708
	2709	return true;
	2710	}
	2711
[1006]	2712
[1201]	2713	void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
[1002]	2714	{
	2715	if (node->IsLeaf())
	2716	{
[1008]	2717	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	2718	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
	2719
	2720	int id = -1;
	2721	if (viewCell != mOutOfBoundsCell)
	2722	id = viewCell->GetId();
	2723
	2724	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
	2725	}
	2726	else
[1012]	2727	{
[1008]	2728	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2729
[1012]	2730	AxisAlignedPlane plane = interior->GetPlane();
	2731	stream << "<Interior plane=\"" << plane.mPosition << " "
	2732	<< plane.mAxis << "\">" << endl;
[1002]	2733
	2734	ExportNode(interior->GetBack(), stream);
	2735	ExportNode(interior->GetFront(), stream);
[1012]	2736
[1002]	2737	stream << "</Interior>" << endl;
	2738	}
	2739	}
	2740
[1011]	2741
[1016]	2742	int VspTree::SplitRays(const AxisAlignedPlane &plane,
[1020]	2743	RayInfoContainer &rays,
	2744	RayInfoContainer &frontRays,
	2745	RayInfoContainer &backRays) const
[1011]	2746	{
	2747	int splits = 0;
	2748
	2749	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2750
	2751	for (rit = rays.begin(); rit != rit_end; ++ rit)
	2752	{
	2753	RayInfo bRay = *rit;
	2754
	2755	VssRay *ray = bRay.mRay;
	2756	float t;
	2757
	2758	// get classification and receive new t
[1186]	2759	// test if start point behind or in front of plane
[1047]	2760	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
	2761
[1011]	2762	if (side == 0)
	2763	{
	2764	++ splits;
	2765
	2766	if (ray->HasPosDir(plane.mAxis))
	2767	{
	2768	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2769	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2770	}
	2771	else
	2772	{
	2773	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2774	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2775	}
	2776	}
	2777	else if (side == 1)
	2778	{
	2779	frontRays.push_back(bRay);
	2780	}
	2781	else
	2782	{
	2783	backRays.push_back(bRay);
	2784	}
	2785	}
	2786
	2787	return splits;
	2788	}
	2789
[1012]	2790
[1144]	2791	AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
[1012]	2792	{
	2793	if (!node->GetParent())
[1020]	2794	return mBoundingBox;
[1012]	2795
	2796	if (!node->IsLeaf())
	2797	{
[1016]	2798	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
[1012]	2799	}
	2800
	2801	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
	2802
[1016]	2803	AxisAlignedBox3 box(parent->GetBoundingBox());
[1012]	2804
[1047]	2805	if (parent->GetFront() == node)
	2806	box.SetMin(parent->GetAxis(), parent->GetPosition());
	2807	else
	2808	box.SetMax(parent->GetAxis(), parent->GetPosition());
[1012]	2809
	2810	return box;
	2811	}
	2812
	2813
[1021]	2814	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
	2815	ViewCellContainer &viewCells) const
	2816	{
[1027]	2817	stack<VspNode *> nodeStack;
	2818
[1021]	2819	ViewCell::NewMail();
	2820
	2821	while (!nodeStack.empty())
	2822	{
[1027]	2823	VspNode *node = nodeStack.top();
[1021]	2824	nodeStack.pop();
	2825
[1144]	2826	const AxisAlignedBox3 bbox = GetBoundingBox(node);
[1027]	2827
	2828	if (bbox.Includes(box))
[1021]	2829	{
	2830	// node geometry is contained in box
	2831	CollectViewCells(node, true, viewCells, true);
[1027]	2832	}
	2833	else if (Overlap(bbox, box))
	2834	{
[1021]	2835	if (node->IsLeaf())
	2836	{
	2837	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2838
	2839	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
	2840	{
	2841	leaf->GetViewCell()->Mail();
	2842	viewCells.push_back(leaf->GetViewCell());
	2843	}
	2844	}
	2845	else
	2846	{
[1027]	2847	VspInterior interior = dynamic_cast<VspInterior >(node);
[1021]	2848
[1027]	2849	VspNode *first = interior->GetFront();
	2850	VspNode *second = interior->GetBack();
[1021]	2851
[1027]	2852	nodeStack.push(first);
	2853	nodeStack.push(second);
[1021]	2854	}
[1027]	2855	}
	2856	// default: cull
[1021]	2857	}
	2858
	2859	return (int)viewCells.size();
	2860	}
	2861
	2862
[1121]	2863	void VspTree::CollectDirtyCandidates(VspSplitCandidate *sc,
	2864	vector<SplitCandidate *> &dirtyList)
	2865	{
[1138]	2866	VspTraversalData &tData = sc->mParentData;
	2867	VspLeaf *node = tData.mNode;
[1121]	2868
	2869	KdLeaf::NewMail();
	2870
[1138]	2871	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	2872
	2873	// add all kd nodes seen by the rays
	2874	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
[1121]	2875	{
[1138]	2876	VssRay ray = (rit).mRay;
[1135]	2877
[1138]	2878	KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
	2879
	2880	if (!leaf->Mailed())
[1121]	2881	{
[1138]	2882	leaf->Mail();
	2883	dirtyList.push_back(leaf->mSplitCandidate);
[1121]	2884	}
[1138]	2885
	2886	leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
	2887
	2888	if (!leaf->Mailed())
	2889	{
	2890	leaf->Mail();
	2891	dirtyList.push_back(leaf->mSplitCandidate);
	2892	}
[1121]	2893	}
	2894	}
	2895
	2896
[1176]	2897	void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
	2898	RayInfoContainer &rays)
[1135]	2899	{
	2900	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	2901
	2902	long startTime = GetTime();
	2903
	2904	cout << "storing rays ... ";
	2905
	2906	Intersectable::NewMail();
	2907
	2908	//-- store rays and objects
	2909	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	2910	{
	2911	VssRay ray = rit;
	2912	float minT, maxT;
	2913	static Ray hray;
	2914
	2915	hray.Init(*ray);
	2916
	2917	// TODO: not very efficient to implictly cast between rays types
	2918	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
	2919	{
	2920	float len = ray->Length();
	2921
	2922	if (!len)
	2923	len = Limits::Small;
	2924
	2925	rays.push_back(RayInfo(ray, minT / len, maxT / len));
	2926	}
	2927	}
	2928
	2929	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	2930	}
	2931
	2932
[1186]	2933	void VspTree::GetViewCells(VssRay &ray, ViewCellContainer &viewCells)
[1137]	2934	{
[1186]	2935	mViewCellsManager->ComputeSampleContribution(ray, false, true);
	2936	viewCells = ray.mViewCells;
	2937	ray.mViewCells.clear();
	2938	/*
[1184]	2939	static Ray hray;
	2940	hray.Init(ray);
	2941	//hray.mFlags \|= Ray::CULL_BACKFACES;
	2942	//Ray hray(ray);
	2943
	2944	float tmin = 0, tmax = 1.0;
	2945
	2946	if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
	2947	return;
	2948
	2949	const Vector3 origin = hray.Extrap(tmin);
	2950	const Vector3 termination = hray.Extrap(tmax);
	2951
[1137]	2952	// if no precomputation of view cells
[1186]	2953	CastLineSegment(origin, termination, viewCells);*/
[1137]	2954	}
[1016]	2955
[1027]	2956
[1186]	2957
[1137]	2958	/*******************************************************************/
	2959	/* class OspTree implementation */
	2960	/*******************************************************************/
	2961
	2962
[1022]	2963	OspTree::OspTree():
[1099]	2964	mRoot(NULL),
[1143]	2965	mTimeStamp(1),
	2966	mCopyFromKdTree(false)
[1022]	2967	{
[1143]	2968	ReadEnvironment();
	2969	mSplitCandidates = new vector<SortableEntry>;
	2970	}
	2971
	2972
	2973	OspTree::OspTree(const KdTree &kdTree)
	2974	{
	2975	ReadEnvironment();
	2976
	2977	// copy values from kd tree
	2978	mCopyFromKdTree = true;
	2979	mBoundingBox = kdTree.GetBox();
	2980	mRoot = kdTree.GetRoot();
[1180]	2981
[1178]	2982	mSplitCandidates = new vector<SortableEntry>;
[1143]	2983	}
	2984
	2985
	2986	OspTree::~OspTree()
	2987	{
[1180]	2988	// delete kd intersectables
[1143]	2989	KdIntersectableMap::iterator it, it_end = mKdIntersectables.end();
	2990
	2991	for (it = mKdIntersectables.begin(); it != mKdIntersectables.end(); ++ it)
	2992	{
	2993	DEL_PTR((*it).second);
	2994	}
	2995
[1176]	2996	// if not using kd tree root, delete tree (otherwise mKdTree has to do the job)
[1143]	2997	if (!mCopyFromKdTree)
	2998	DEL_PTR(mRoot);
[1176]	2999
[1178]	3000	DEL_PTR(mSplitCandidates);
[1176]	3001	mSubdivisionStats.close();
[1143]	3002	}
	3003
	3004
	3005	void OspTree::ReadEnvironment()
	3006	{
[1022]	3007	bool randomize = false;
	3008	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
	3009	if (randomize)
	3010	Randomize(); // initialise random generator for heuristics
[1020]	3011
[1022]	3012	//-- termination criteria for autopartition
[1106]	3013	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
	3014	Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
	3015	Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
	3016	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
[1023]	3017
[1106]	3018	Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
	3019
[1022]	3020	//-- max cost ratio for early tree termination
[1106]	3021	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[1022]	3022
[1123]	3023	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio",
	3024	mTermMinGlobalCostRatio);
[1129]	3025
[1022]	3026
	3027	//-- factors for bsp tree split plane heuristics
[1106]	3028	Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
[1022]	3029
	3030	//-- partition criteria
[1106]	3031	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
[1022]	3032
	3033	// if only the driving axis is used for axis aligned split
[1106]	3034	Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
	3035	Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
	3036	Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
[1023]	3037
	3038
[1022]	3039	char subdivisionStatsLog[100];
[1106]	3040	Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
[1022]	3041	mSubdivisionStats.open(subdivisionStatsLog);
	3042
[1106]	3043	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
[1121]	3044	Environment::GetSingleton()->GetFloatValue("OspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
	3045
[1129]	3046
[1022]	3047	//-- debug output
	3048
[1145]	3049	Debug << "***** OSP tree options ****** " << endl;
[1106]	3050
[1022]	3051	Debug << "max depth: " << mTermMaxDepth << endl;
	3052	Debug << "min probabiliy: " << mTermMinProbability << endl;
[1106]	3053	Debug << "min objects: " << mTermMinObjects << endl;
[1022]	3054	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	3055	Debug << "miss tolerance: " << mTermMissTolerance << endl;
[1106]	3056	Debug << "max leaves: " << mTermMaxLeaves << endl;
	3057
[1022]	3058	Debug << "randomize: " << randomize << endl;
	3059
	3060	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	3061	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	3062	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	3063	Debug << "max memory: " << mMaxMemory << endl;
	3064	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	3065	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1023]	3066
[1106]	3067	Debug << "split borders: " << mSplitBorder << endl;
[1121]	3068	Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
[1022]	3069	Debug << endl;
	3070	}
	3071
	3072
[1143]	3073	void OspTree::SplitObjects(KdLeaf *parent,
	3074	const AxisAlignedPlane& splitPlane,
[1020]	3075	const ObjectContainer &objects,
[1106]	3076	ObjectContainer &front,
	3077	ObjectContainer &back)
[1016]	3078	{
[1020]	3079	ObjectContainer::const_iterator oit, oit_end = objects.end();
	3080
	3081	for (oit = objects.begin(); oit != oit_end; ++ oit)
	3082	{
[1135]	3083	Intersectable object = oit;
[1143]	3084
[1176]	3085	// initialise leaf references of objects
[1143]	3086	if (parent->IsRoot())
[1181]	3087	{
[1143]	3088	object->mReferences = 1;
[1181]	3089	}
[1135]	3090
[1143]	3091	// remove parent ref
	3092	-- object->mReferences;
	3093
[1020]	3094	// determine the side of this ray with respect to the plane
[1135]	3095	const AxisAlignedBox3 box = object->GetBox();
[1020]	3096
	3097	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
[1135]	3098	{
	3099	front.push_back(object);
[1143]	3100	++ object->mReferences;
[1135]	3101	}
	3102
[1020]	3103	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
[1135]	3104	{
	3105	back.push_back(object);
[1143]	3106	++ object->mReferences;
[1135]	3107	}
[1020]	3108	}
[1106]	3109
	3110	mOspStats.objectRefs -= (int)objects.size();
[1181]	3111	mOspStats.objectRefs += (int)(back.size() + front.size());
[1016]	3112	}
	3113
	3114
[1106]	3115	KdInterior *OspTree::SubdivideNode(
[1020]	3116	const AxisAlignedPlane &splitPlane,
[1108]	3117	const OspTraversalData &tData,
[1106]	3118	OspTraversalData &frontData,
	3119	OspTraversalData &backData
	3120	)
[1016]	3121	{
[1108]	3122	KdLeaf *leaf = tData.mNode;
	3123
	3124	// two new leaves
[1106]	3125	mOspStats.nodes += 2;
[1016]	3126
[1020]	3127	// add the new nodes to the tree
	3128	KdInterior *node = new KdInterior(leaf->mParent);
	3129
	3130	const int axis = splitPlane.mAxis;
	3131	const float position = splitPlane.mPosition;
	3132
	3133	node->mAxis = axis;
	3134	node->mPosition = position;
[1108]	3135	node->mBox = tData.mBoundingBox;
[1020]	3136
[1108]	3137
	3138	//-- the front and back traversal data is filled with the new values
	3139
	3140	// bounding boxes: split front and back node geometry
	3141	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
	3142	frontData.mBoundingBox, backData.mBoundingBox);
	3143
	3144	frontData.mDepth = backData.mDepth = tData.mDepth + 1;
	3145
[1135]	3146	//-- subdivide rays
	3147	frontData.mRays = new RayInfoContainer();
	3148	backData.mRays = new RayInfoContainer();
[1108]	3149
[1186]	3150	/* SplitRays(splitPlane,
[1135]	3151	*tData.mRays,
	3152	*frontData.mRays,
	3153	*backData.mRays);
[1186]	3154	*/
[1135]	3155
	3156	//-- classify objects
[1184]	3157
[1020]	3158	int objectsBack = 0;
	3159	int objectsFront = 0;
	3160
[1184]	3161	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
[1020]	3162
	3163	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
	3164	{
	3165	// determine the side of this ray with respect to the plane
	3166	const AxisAlignedBox3 box = (*mi)->GetBox();
	3167
[1184]	3168	if (box.Max(axis) >= position)
[1020]	3169	++ objectsFront;
	3170
[1184]	3171	if (box.Min(axis) < position)
[1020]	3172	++ objectsBack;
	3173	}
	3174
[1184]	3175
[1181]	3176	// TODO matt: compute pvs
[1186]	3177	//frontData.mPvs = objectsFront;
	3178	//backData.mPvs = objectsBack;
[1181]	3179
[1184]	3180	//CheckViewCellsPvs(leaf, *tData.mRays);
	3181	RemoveParentViewCellsPvs(leaf, *tData.mRays);
	3182
	3183
[1020]	3184	KdLeaf *back = new KdLeaf(node, objectsBack);
	3185	KdLeaf *front = new KdLeaf(node, objectsFront);
	3186
[1184]	3187
[1106]	3188	/////////////
	3189	//-- create front and back leaf
	3190
	3191	KdInterior *parent = leaf->mParent;
	3192
[1020]	3193	// replace a link from node's parent
[1106]	3194	if (parent)
	3195	{
	3196	parent->ReplaceChildLink(leaf, node);
	3197	node->mParent = parent;
	3198	}
	3199	else // new root
	3200	{
	3201	mRoot = node;
	3202	}
[1020]	3203
	3204	// and setup child links
	3205	node->SetupChildLinks(back, front);
	3206
[1143]	3207	SplitObjects(leaf, splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
[1186]	3208
	3209	FilterRays(front, tData.mRays, frontData.mRays);
	3210	FilterRays(back, tData.mRays, backData.mRays);
[1143]	3211
[1193]	3212	++ mOspStats.splits[splitPlane.mAxis];
[1184]	3213
	3214	//-- eval view cells pvs
	3215
	3216	// remove parent pvs update pvs of left and right leaves
	3217	// Note: It is necessary to update first left and then right pvs.
	3218	// We need to store the view cells seen by each object,
	3219	// but also if the view cells are seen as part of two different
	3220	// kd leaves, which is stored in the pdf component of the pvs entry.
	3221	// Because if an object is part of a view cell more than once,
	3222	// it cannot be removed from the pvs by splitting a kd node where
	3223	// the view cell sees only the other child of the node.
	3224	// This is important during the subdivision
	3225
[1189]	3226	//MailablePvsData::NewMail();
[1184]	3227	UpdateViewCellsPvs(front, *frontData.mRays);
	3228	UpdateViewCellsPvs(back, *backData.mRays);
	3229
	3230	////////////////////////////////////
	3231
	3232
[1143]	3233	ProcessMultipleRefs(front);
	3234	ProcessMultipleRefs(back);
	3235
[1181]	3236	frontData.mNode = front;
[1106]	3237	backData.mNode = back;
	3238
[1181]	3239
	3240	// compute probability, i.e., volume of seen view cells
	3241	frontData.mProbability = EvalViewCellsVolume(front, *frontData.mRays);
	3242	backData.mProbability = EvalViewCellsVolume(back, *backData.mRays);
	3243
	3244
[1020]	3245	//delete leaf;
	3246	return node;
[1016]	3247	}
	3248
	3249
[1020]	3250	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
[1145]	3251	SplitCandidate *splitCandidate,
[1020]	3252	const bool globalCriteriaMet)
[1108]	3253	{
[1145]	3254	OspSplitCandidate sc = dynamic_cast<OspSplitCandidate >(splitCandidate);
	3255	OspTraversalData &tData = sc->mParentData;
	3256
[1020]	3257	KdNode *newNode = tData.mNode;
[1016]	3258
[1020]	3259	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	3260	{
	3261	OspTraversalData tFrontData;
	3262	OspTraversalData tBackData;
[1108]	3263
[1020]	3264	//-- continue subdivision
	3265
	3266	// create new interior node and two leaf node
[1145]	3267	const AxisAlignedPlane splitPlane = sc->mSplitPlane;
[1027]	3268
[1108]	3269	newNode = SubdivideNode(splitPlane,
	3270	tData,
[1106]	3271	tFrontData,
	3272	tBackData);
[1020]	3273
[1145]	3274	const int maxCostMisses = sc->mMaxCostMisses;
[1016]	3275
[1174]	3276	// how often was max cost ratio missed in this branch?
[1020]	3277	tFrontData.mMaxCostMisses = maxCostMisses;
	3278	tBackData.mMaxCostMisses = maxCostMisses;
[1174]	3279
	3280	mTotalCost -= sc->GetRenderCostDecrease();
	3281
	3282	// subdivision statistics
	3283	if (1) EvalSubdivisionStats(*sc);
	3284
[1020]	3285	//-- push the new split candidates on the queue
[1174]	3286
[1099]	3287	OspSplitCandidate *frontCandidate = new OspSplitCandidate(tFrontData);
	3288	OspSplitCandidate *backCandidate = new OspSplitCandidate(tBackData);
[1016]	3289
[1099]	3290	EvalSplitCandidate(*frontCandidate);
	3291	EvalSplitCandidate(*backCandidate);
[1016]	3292
[1099]	3293	tQueue.Push(frontCandidate);
	3294	tQueue.Push(backCandidate);
[1020]	3295
	3296	// delete old leaf node
	3297	DEL_PTR(tData.mNode);
	3298	}
	3299
	3300
	3301	//-- terminate traversal
	3302	if (newNode->IsLeaf())
	3303	{
[1186]	3304	EvaluateLeafStats(tData);
	3305
	3306	const bool mStoreRays= true;
	3307
[1184]	3308	//-- store additional info
	3309	if (mStoreRays)
	3310	{
	3311	KdLeaf leaf = dynamic_cast<KdLeaf >(newNode);
	3312
	3313	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	3314
	3315	for (it = tData.mRays->begin(); it != it_end; ++ it)
	3316	{
	3317	(*it).mRay->Ref();
	3318	leaf->mVssRays.push_back((*it).mRay);
	3319	}
	3320	}
[1020]	3321	}
[1108]	3322
[1020]	3323	//-- cleanup
	3324	tData.Clear();
[1108]	3325
[1020]	3326	return newNode;
	3327	}
[1016]	3328
	3329
[1099]	3330	void OspTree::EvalSplitCandidate(OspSplitCandidate &splitCandidate)
[1020]	3331	{
	3332	float frontProb;
[1089]	3333	float backProb;
[1178]	3334
[1020]	3335	// compute locally best split plane
[1084]	3336	const bool success =
[1184]	3337	SelectSplitPlane(splitCandidate.mParentData,
	3338	splitCandidate.mSplitPlane,
	3339	frontProb,
	3340	backProb);
[1020]	3341
[1145]	3342	float oldRenderCost;
	3343
[1020]	3344	// compute global decrease in render cost
[1145]	3345	const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
	3346	splitCandidate.mParentData,
	3347	oldRenderCost);
	3348
	3349	splitCandidate.SetRenderCostDecrease(renderCostDecr);
	3350
	3351	#if 0
	3352	const float priority = (float)-data.mDepth;
	3353	#else
	3354	// take render cost of node into account
	3355	// otherwise danger of being stuck in a local minimum!!
	3356	const float factor = mRenderCostDecreaseWeight;
	3357	const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
	3358
	3359	#endif
	3360
	3361	// compute global decrease in render cost
[1106]	3362	splitCandidate.SetPriority(priority);
	3363
	3364	splitCandidate.mMaxCostMisses =
[1184]	3365	success ? splitCandidate.mParentData.mMaxCostMisses :
	3366	splitCandidate.mParentData.mMaxCostMisses + 1;
[1016]	3367	}
	3368
	3369
[1021]	3370	bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
	3371	{
	3372	// matt: TODO
[1106]	3373	return (
	3374	//(data.mNode->mObjects.size() < mTermMinObjects) \|\|
	3375	//(data.mProbability <= mTermMinProbability) \|\|
	3376	(data.mDepth >= mTermMaxDepth)
	3377	);
[1021]	3378	}
[1020]	3379
[1021]	3380
	3381	bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
	3382	{
	3383	// matt: TODO
[1106]	3384	return (
	3385	(mOspStats.Leaves() >= mTermMaxLeaves)
	3386	//mOutOfMemory \|\|
	3387	//(mGlobalCostMisses >= mTermGlobalCostMissTolerance)
	3388	);
[1021]	3389	}
	3390
	3391
	3392	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
	3393	{
	3394	// the node became a leaf -> evaluate stats for leafs
[1106]	3395	KdLeaf *leaf = data.mNode;
[1184]	3396
	3397	++ mCreatedLeaves;
[1021]	3398
[1186]	3399	/*if (data.mPvs > mOspStats.maxPvs)
[1021]	3400	{
[1106]	3401	mOspStats.maxPvs = data.mPvs;
[1021]	3402	}
	3403
[1106]	3404	mOspStats.pvs += data.mPvs;
[1021]	3405
[1106]	3406	if (data.mDepth < mOspStats.minDepth)
[1021]	3407	{
[1106]	3408	mOspStats.minDepth = data.mDepth;
[1186]	3409	}*/
[1021]	3410
	3411	if (data.mDepth >= mTermMaxDepth)
	3412	{
[1106]	3413	++ mOspStats.maxDepthNodes;
[1021]	3414	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
	3415	}
	3416
	3417	if (data.mProbability <= mTermMinProbability)
[1106]	3418	++ mOspStats.minProbabilityNodes;
[1021]	3419
	3420	// accumulate depth to compute average depth
[1106]	3421	mOspStats.accumDepth += data.mDepth;
[1184]	3422
	3423	// if ((int)(leaf->mObjects.size()) < mTermMinCost)
	3424	// ++ mOspStats.minCostNodes;
	3425
	3426	if ((int)(leaf->mObjects.size()) > mOspStats.maxObjectRefs)
	3427	mOspStats.maxObjectRefs = (int)leaf->mObjects.size();
[1021]	3428
	3429	#ifdef _DEBUG
	3430	Debug << "BSP stats: "
	3431	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
[1189]	3432	<< "Prob: " << data.mProbability << " (min: " << mTermMinProbability << ")\n";
[1021]	3433	#endif
	3434	}
	3435
	3436
[1135]	3437	float OspTree::EvalLocalCostHeuristics(const OspTraversalData &tData,
[1077]	3438	const AxisAlignedBox3 &box,
	3439	const int axis,
[1084]	3440	float &position,
[1106]	3441	int &objectsFront,
	3442	int &objectsBack)
[1077]	3443	{
[1166]	3444	RayInfoContainer usedRays;
[1179]	3445	int mMaxTests = 500000; // HACK
	3446
	3447	if (mMaxTests < (int)tData.mRays->size())
	3448	{
	3449	GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
	3450	}
	3451	else
	3452	{
[1166]	3453	usedRays = *tData.mRays;
[1179]	3454	}
[1166]	3455
[1084]	3456	// go through the lists, count the number of objects left and right
	3457	// and evaluate the following cost funcion:
	3458	// C = ct_div_ci + (ol + or)/queries
	3459
[1135]	3460	const float minBox = box.Min(axis);
	3461	const float maxBox = box.Max(axis);
[1193]	3462	Debug << "min: " << minBox << " max: " << maxBox << endl;
[1135]	3463
	3464	const float sizeBox = maxBox - minBox;
	3465
	3466	float minBand = minBox + mSplitBorder * (maxBox - minBox);
	3467	float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
	3468
[1193]	3469	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
	3470
[1135]	3471	//-- sort so we can use a sweep
	3472	SortSplitCandidates(tData, axis, minBand, maxBand);
	3473
[1193]	3474	float totalVol = 0;
[1133]	3475	float voll = 0;
	3476	float volr = totalVol;
[1145]	3477
[1189]	3478	ViewCellContainer touchedViewCells;
[1193]	3479
[1189]	3480	const float totalRenderCost = PrepareHeuristics(tData, touchedViewCells);
	3481	float renderCost = totalRenderCost;
	3482
[1166]	3483	/// this is kind of a reverse pvs
	3484	const int totalPvs = (int)tData.mNode->mObjects.size();
[1137]	3485
	3486	int pvsl = 0;
	3487	int pvsr = totalPvs;
[1129]	3488
[1145]	3489	float sum = (float)totalVol * sizeBox;
	3490
[1193]	3491
	3492	Debug << "here82 render cost: " << renderCost / viewSpaceVol << endl;
	3493
[1145]	3494	/////////////////////////////////
	3495
	3496	// note: initialised to take mid split
	3497	// if no good split can be found,
[1137]	3498	position = minBox + 0.5f * sizeBox;
[1077]	3499
	3500	// the relative cost ratio
	3501	float ratio = 99999999.0f;
	3502	bool splitPlaneFound = false;
	3503
[1129]	3504	float volBack = voll;
	3505	float volFront = volr;
[1077]	3506
[1145]	3507	int pvsBack = pvsl;
	3508	int pvsFront = pvsr;
[1137]	3509
[1189]	3510	float minRenderCost = 1e20f;
[1137]	3511
[1178]	3512	debugVol = 0;
	3513
[1189]	3514
[1193]	3515
[1145]	3516	/////////////////////////////
[1178]	3517	// the sweep heuristics
[1084]	3518
[1193]	3519
[1137]	3520	//-- traverse through events and find best split plane
[1178]	3521
[1135]	3522	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
[1193]	3523	//minRenderCost = RandomValue(0,viewSpaceVol);
[1135]	3524
[1137]	3525	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
[1077]	3526	{
[1135]	3527	Intersectable object = (ci).mObject;
	3528
[1145]	3529	EvalHeuristicsContribution(tData.mNode,
	3530	*ci,
[1189]	3531	renderCost,
	3532	touchedViewCells
[1176]	3533	);
[1135]	3534
[1145]	3535	// Note: sufficient to compare size of bounding boxes of front and back side?
[1135]	3536	if (((ci).mPos >= minBand) && ((ci).mPos <= maxBand))
[1077]	3537	{
[1147]	3538	float currentPos;
[1193]	3539	Debug << "here29 : " << minRenderCost / viewSpaceVol << endl;
	3540
[1147]	3541	// HACK: current positition is BETWEEN visibility events
[1193]	3542	if (1 && /((ci).mType == SortableEntry::BOX_INTERSECT) &&*/ ((ci + 1) != ci_end))
[1147]	3543	currentPos = ((ci).mPos + ((ci + 1)).mPos) * 0.5f;
	3544	else
	3545	currentPos = (*ci).mPos;
	3546
[1189]	3547	if (renderCost < minRenderCost)
[1077]	3548	{
	3549	splitPlaneFound = true;
[1189]	3550	minRenderCost = renderCost;
[1147]	3551	position = currentPos;
[1193]	3552	Debug << "pos: " << position << endl;
[1077]	3553	}
	3554	}
	3555	}
[1193]	3556	//splitPlaneFound = true;
[1077]	3557	if (splitPlaneFound)
	3558	{
[1193]	3559	ratio = minRenderCost / totalRenderCost;
[1077]	3560	}
[1178]	3561
[1189]	3562	Debug << "\n§§§§ eval local cost §§§§" << endl
	3563	<< "old rc: " << totalRenderCost / viewSpaceVol << " new rc: " << minRenderCost / viewSpaceVol << endl
	3564	<< "render cost decrease: " << (totalRenderCost - minRenderCost) / viewSpaceVol << endl;
[1077]	3565
	3566	return ratio;
	3567	}
	3568
[1121]	3569
[1135]	3570	void OspTree::SortSplitCandidates(const OspTraversalData &tData,
	3571	const int axis,
	3572	float minBand,
	3573	float maxBand)
	3574
[1077]	3575	{
[1084]	3576	mSplitCandidates->clear();
[1077]	3577
[1135]	3578	RayInfoContainer *rays = tData.mRays;
	3579	KdLeaf *leaf = tData.mNode;
	3580
[1137]	3581	int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size();
[1135]	3582
[1084]	3583	// creates a sorted split candidates array
	3584	if (mSplitCandidates->capacity() > 500000 &&
[1135]	3585	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
[1077]	3586	{
[1135]	3587	delete mSplitCandidates;
	3588	mSplitCandidates = new vector<SortableEntry>;
[1077]	3589	}
	3590
[1084]	3591	mSplitCandidates->reserve(requestedSize);
[1077]	3592
[1135]	3593	float pos;
	3594
[1137]	3595	//-- insert ray queries
	3596	//-- we are intersested only in rays which intersect an object that
	3597	//-- is part of the kd node because they can induce a change in view cell
	3598	//-- volume on the left and the right part.
	3599	//-- Note that they cannot induce a change in pvs size!!
	3600
	3601	RayInfoContainer::const_iterator rit, rit_end = rays->end();
	3602
	3603	for (rit = rays->begin(); rit < rit_end; ++ rit)
[1077]	3604	{
[1137]	3605	VssRay ray = (rit).mRay;
	3606
	3607	const bool positive = ray->HasPosDir(axis);
[1184]	3608
	3609	if (EndPointInsideNode(leaf, *ray, true))
[1137]	3610	{
[1184]	3611	pos = ray->mTermination[axis];
	3612
[1137]	3613	mSplitCandidates->push_back(
	3614	SortableEntry(SortableEntry::BOX_INTERSECT,
	3615	pos,
[1184]	3616	ray->mTerminationObject,
[1137]	3617	ray)
	3618	);
	3619	}
[1077]	3620
[1184]	3621	// if hitpoint with object is inside this node
	3622	if (EndPointInsideNode(leaf, *ray, false))
[1137]	3623	{
[1184]	3624	pos = ray->mOrigin[axis];
	3625
[1137]	3626	mSplitCandidates->push_back(
	3627	SortableEntry(SortableEntry::BOX_INTERSECT,
	3628	pos,
[1184]	3629	ray->mOriginObject,
[1137]	3630	ray)
	3631	);
	3632	}
	3633	}
[1135]	3634
	3635
[1137]	3636	//-- insert object queries
	3637	//-- These queries can induce a change in pvs size.
	3638	//-- Note that they cannot induce a change in view cell volume, as
	3639	//-- there is no ray associated with these events!!
	3640
	3641	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3642
	3643	for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit )
	3644	{
	3645	Intersectable object = oit;
	3646	const AxisAlignedBox3 box = object->GetBox();
	3647
	3648	mSplitCandidates->push_back(
	3649	SortableEntry(SortableEntry::BOX_MIN,
	3650	box.Min(axis),
	3651	object,
	3652	NULL)
	3653	);
	3654
	3655
	3656	mSplitCandidates->push_back(
	3657	SortableEntry(SortableEntry::BOX_MAX,
	3658	box.Max(axis),
	3659	object,
	3660	NULL)
	3661	);
[1077]	3662	}
	3663
[1084]	3664	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
[1077]	3665	}
	3666
	3667
[1137]	3668	const OspTreeStatistics &OspTree::GetStatistics() const
[1077]	3669	{
[1137]	3670	return mOspStats;
[1077]	3671	}
	3672
	3673
[1189]	3674	void OspTree::PrepareHeuristics(const VssRay &ray,
	3675	ViewCellContainer &touchedViewCells)
[1121]	3676	{
[1189]	3677	// collect view cells and set mail + counter
[1137]	3678	ViewCellContainer viewCells;
[1186]	3679	mVspTree->GetViewCells(VssRay(ray), viewCells);
[1145]	3680
[1137]	3681	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	3682
	3683	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	3684	{
	3685	ViewCell vc = (vit);
	3686
	3687	if (!vc->Mailed())
	3688	{
[1189]	3689	vc->Mail(); // set as belonging to front leaf
[1137]	3690	vc->mCounter = 0;
[1189]	3691	touchedViewCells.push_back(vc);
[1137]	3692	}
[1145]	3693
	3694	// view cell volume already added => just increase counter
	3695	++ vc->mCounter;
[1137]	3696	}
[1121]	3697	}
	3698
	3699
[1189]	3700	float OspTree::PrepareHeuristics(const OspTraversalData &tData,
	3701	ViewCellContainer &touchedViewCells)
[1077]	3702	{
[1189]	3703	float renderCost = 0;
[1145]	3704
[1189]	3705	Intersectable::NewMail(3);
	3706	ViewCell::NewMail(3);
	3707	MailablePvsData::NewMail();
[1077]	3708
[1137]	3709	KdLeaf *leaf = tData.mNode;
[1077]	3710
[1137]	3711	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	3712
	3713	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
[1077]	3714	{
[1137]	3715	VssRay ray = (rit).mRay;
[1189]	3716	PrepareHeuristics(*ray, touchedViewCells);
	3717	}
[1137]	3718
[1189]	3719	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1145]	3720
[1189]	3721	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	3722	{
	3723	Intersectable obj = oit;
	3724	obj->Mail(); // set as belonging to front leaf
	3725
	3726	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
[1145]	3727
[1189]	3728	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
[1145]	3729	{
[1189]	3730	ViewCell vc = vit;
	3731	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
	3732
	3733	if (!vdata) // should never happen
	3734	continue;
	3735
	3736	if (!vdata->Mailed())
	3737	{
	3738	vdata->Mail();
	3739	renderCost += vc->GetVolume();
	3740	}
[1145]	3741	}
[1077]	3742	}
	3743
[1189]	3744	Debug << "here32 " << touchedViewCells.size() << endl;
	3745	return renderCost;
[1077]	3746	}
	3747
	3748
[1189]	3749	void OspTree::AddObjectContribution(KdLeaf *leaf,
	3750	Intersectable *obj,
	3751	ViewCellContainer &touchedViewCells,
	3752	float &renderCost)
[1077]	3753	{
[1193]	3754	//Debug << "add contri to obj: " << obj->mMailbox - Intersectable::sMailId << endl;
[1189]	3755	obj->Mail(2); // set as belonging to both leafs
[1176]	3756
[1189]	3757	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	3758
	3759	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
[1077]	3760	{
[1189]	3761	ViewCell vc = vit;
[1193]	3762	//Debug << "here30 vc mail " << vc->mMailbox - ViewCell::sMailId << endl;
[1137]	3763
[1189]	3764	// if obj not previously associated with this view cell => increase render cost
[1193]	3765	if (vc->Mailed(1) && !ViewCellHasMultipleReferences(obj, vc, false))
	3766	{
	3767	//Debug << "add to rendercost: " << vc->GetVolume() / mVspTree->GetBoundingBox().GetVolume() << endl;
[1189]	3768	renderCost += vc->GetVolume();
	3769	}
[1077]	3770	}
[1189]	3771	}
[1121]	3772
[1189]	3773
	3774	void OspTree::SubtractObjectContribution(KdLeaf *leaf,
	3775	Intersectable * obj,
	3776	ViewCellContainer &touchedViewCells,
	3777	float &renderCost)
	3778	{
[1193]	3779	//Debug << "subtract contri from obj: " << obj->mMailbox - Intersectable::sMailId << endl;
[1189]	3780	obj->Mail(1); // set as belonging to back leaf
	3781	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
[1193]	3782
[1189]	3783	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	3784	{
	3785	ViewCell vc = vit;
	3786
[1193]	3787	//Debug << "here6 " << vc->mMailbox - ViewCell::sMailId << endl;
	3788
[1189]	3789	// if obj was previously associated with this view cell but is not now
	3790	// => decrease render cost
[1193]	3791	if (vc->Mailed() && !ViewCellHasMultipleReferences(obj, vc, false))
[1189]	3792	{
[1193]	3793	//Debug << "subtract from rendercost: " << vc->GetVolume() / mVspTree->GetBoundingBox().GetVolume() << endl;
[1189]	3794	renderCost -= vc->GetVolume();
	3795	}
	3796	}
[1077]	3797	}
	3798
	3799
[1189]	3800	void OspTree::EvalRayContribution(KdLeaf *leaf,
	3801	const VssRay &ray,
	3802	float &renderCost)
[1106]	3803	{
[1137]	3804	ViewCellContainer viewCells;
[1106]	3805
[1186]	3806	mVspTree->GetViewCells(VssRay(ray), viewCells);
[1106]	3807
[1193]	3808	// classify view cells and compute volume contri accordingly
	3809	// possible view cell classifications:
	3810	// view cell mailed => view cell can be seen from left child node
	3811	// view cell counter > 0 view cell can be seen from right child node
	3812	// combined: view cell volume belongs to both nodes
[1137]	3813	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1145]	3814
[1137]	3815	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	3816	{
[1189]	3817	EvalViewCellContribution(leaf, *vit, renderCost);
	3818	}
	3819	}
[1137]	3820
[1176]	3821
[1189]	3822	void OspTree::EvalViewCellContribution(KdLeaf *leaf,
	3823	ViewCell *viewCell,
	3824	float &renderCost)
	3825	{
[1193]	3826	//Debug << "**************" << endl;
	3827	//Debug << "vc contri: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " " << viewCell->mMailbox - ViewCell::sMailId << " counter: " << viewCell->mCounter << endl;
	3828
[1189]	3829	const float vol = viewCell->GetVolume();
[1145]	3830
[1189]	3831	if (viewCell->Mailed())
	3832	{
[1193]	3833	viewCell->Mail(2); // view cell can be seen from both nodes
[1178]	3834
[1189]	3835	// we now see view cell from both nodes => add contri
	3836	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3837
	3838	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	3839	{
	3840	Intersectable obj = oit;
	3841
	3842	// was render cost already added?
[1193]	3843	if (!ViewCellHasMultipleReferences(obj, viewCell, false) &&
[1189]	3844	obj->Mailed(1))
	3845	{
[1193]	3846	//Debug << "obj mail 1!! " << vol / mVspTree->GetBoundingBox().GetVolume() << endl;
	3847	renderCost += vol;
[1189]	3848	}
[1137]	3849	}
[1189]	3850	}
[1137]	3851
[1189]	3852	if (-- viewCell->mCounter == 0)
	3853	{
[1193]	3854	viewCell->Mail(1); // view cell can be seen from back node only
[1189]	3855
	3856	//MailablePvsData::NewMail();
	3857	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3858
	3859	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
[1137]	3860	{
[1189]	3861	Intersectable obj = oit;
	3862
	3863	// can render cost be be reduced?
[1193]	3864	if (!ViewCellHasMultipleReferences(obj, viewCell, false) && obj->Mailed())
[1189]	3865	{
[1193]	3866	renderCost -= vol;
[1189]	3867	}
[1137]	3868	}
	3869	}
[1193]	3870	//Debug << "new rc: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " counter2: " << viewCell->mCounter << endl;
	3871	//Debug << "**************"<<endl;
[1106]	3872	}
	3873
	3874
[1189]	3875	void OspTree::EvalHeuristicsContribution(KdLeaf *leaf,
	3876	const SortableEntry &ci,
	3877	float &renderCost,
	3878	ViewCellContainer &touchedViewCells)
	3879	{
	3880	Intersectable *obj = ci.mObject;
	3881	VssRay *ray = ci.mRay;
	3882
	3883	// switch between different types of events
	3884	switch (ci.mType)
	3885	{
	3886	case SortableEntry::BOX_MIN:
	3887	cout << "<";
	3888	AddObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
	3889	break;
	3890
	3891	case SortableEntry::BOX_MAX:
	3892	cout << ">";
	3893	SubtractObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
	3894	break;
	3895
	3896	// compute volume contribution from view cells
	3897	case SortableEntry::BOX_INTERSECT:
	3898	cout << "i";
	3899	// process ray if the hit point with termination / origin object
	3900	// is inside this kd leaf
	3901	EvalRayContribution(leaf, *ray, renderCost);
	3902	break;
	3903
	3904	default:
	3905	cout << "should not come here" << endl;
	3906	break;
	3907	}
	3908
	3909	//cout << "vol left: " << volLeft << " vol right " << volRight << endl;
	3910	}
	3911
	3912
[1137]	3913	void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
[1077]	3914	{
[1137]	3915	mViewCellsManager = vcm;
[1077]	3916	}
	3917
	3918
[1137]	3919	AxisAlignedBox3 OspTree::GetBoundingBox() const
[1077]	3920	{
[1137]	3921	return mBoundingBox;
[1077]	3922	}
	3923
	3924
[1089]	3925	float OspTree::SelectSplitPlane(const OspTraversalData &tData,
[1084]	3926	AxisAlignedPlane &plane,
	3927	float &pFront,
	3928	float &pBack)
	3929	{
	3930	float nPosition[3];
	3931	float nCostRatio[3];
	3932	float nProbFront[3];
	3933	float nProbBack[3];
	3934
	3935	// create bounding box of node geometry
	3936	AxisAlignedBox3 box = tData.mBoundingBox;
	3937
	3938	int sAxis = 0;
	3939	int bestAxis = -1;
	3940
	3941	if (mOnlyDrivingAxis)
	3942	{
	3943	sAxis = box.Size().DrivingAxis();
	3944	}
[1178]	3945
[1084]	3946
[1106]	3947	// -- evaluate split cost for all three axis
[1084]	3948	for (int axis = 0; axis < 3; ++ axis)
	3949	{
	3950	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
	3951	{
[1106]	3952	if (1 \|\| mUseCostHeuristics)
	3953	{
	3954	//-- place split plane using heuristics
	3955	int objectsFront, objectsBack;
[1084]	3956
	3957	nCostRatio[axis] =
[1137]	3958	EvalLocalCostHeuristics(tData,
[1106]	3959	tData.mBoundingBox,
	3960	axis,
	3961	nPosition[axis],
	3962	objectsFront,
	3963	objectsBack);
[1084]	3964	}
[1106]	3965	/* else
[1084]	3966	{
[1106]	3967	//-- split plane position is spatial median
	3968
[1084]	3969	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	3970
	3971	nCostRatio[axis] = EvalLocalSplitCost(tData,
	3972	box,
	3973	axis,
	3974	nPosition[axis],
	3975	nProbFront[axis],
	3976	nProbBack[axis]);
[1106]	3977	}*/
[1084]	3978
	3979	if (bestAxis == -1)
	3980	{
	3981	bestAxis = axis;
	3982	}
	3983	else if (nCostRatio[axis] < nCostRatio[bestAxis])
	3984	{
	3985	bestAxis = axis;
	3986	}
	3987	}
	3988	}
	3989
	3990	//-- assign values
[1106]	3991
[1084]	3992	plane.mAxis = bestAxis;
	3993	// split plane position
	3994	plane.mPosition = nPosition[bestAxis];
	3995
	3996	pFront = nProbFront[bestAxis];
	3997	pBack = nProbBack[bestAxis];
	3998
[1145]	3999	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1084]	4000	return nCostRatio[bestAxis];
	4001	}
	4002
	4003
[1145]	4004	bool OspTree::EndPointInsideNode(KdLeaf *leaf,
	4005	VssRay &ray,
	4006	bool isTermination) const
[1089]	4007	{
[1145]	4008	// test if the leaf where the hitpoint is located is the current leaf
	4009	if (isTermination)
	4010	{
[1184]	4011	return ray.mTerminationObject && (GetLeaf(ray.mTermination, ray.mTerminationNode) == leaf);
[1145]	4012	}
	4013	else
	4014	{
[1189]	4015	return false; // no origin object!
	4016	return ray.mOriginObject && (GetLeaf(ray.mOrigin, ray.mOriginNode) == leaf);
[1145]	4017	}
	4018	}
	4019
	4020
[1174]	4021	void OspTree::EvalSubdivisionStats(const SplitCandidate &sc)
[1145]	4022	{
[1174]	4023	const float costDecr = sc.GetRenderCostDecrease();
[1176]	4024
[1174]	4025	AddSubdivisionStats(mOspStats.Leaves(),
	4026	costDecr,
	4027	mTotalCost
	4028	);
	4029	}
[1145]	4030
	4031
[1174]	4032	void OspTree::AddSubdivisionStats(const int leaves,
	4033	const float renderCostDecr,
	4034	const float totalRenderCost)
[1176]	4035	{
[1174]	4036	mSubdivisionStats
	4037	<< "#Leaves\n" << leaves << endl
	4038	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	4039	<< "#TotalRenderCost\n" << totalRenderCost << endl;
	4040	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
[1145]	4041	}
[1089]	4042
[1145]	4043
	4044	int OspTree::ClassifyRay(VssRay *ray,
	4045	KdLeaf *leaf,
	4046	const AxisAlignedPlane &plane) const
	4047	{
	4048	const bool originInside = EndPointInsideNode(leaf, *ray, false);
	4049	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
	4050
[1189]	4051	const bool originGt = (ray->mOrigin[plane.mAxis] >= plane.mPosition);
	4052	const bool originLt = (ray->mOrigin[plane.mAxis] <= plane.mPosition);
[1145]	4053
[1189]	4054	const bool terminationGt = (ray->mTermination[plane.mAxis] >= plane.mPosition);
	4055	const bool terminationLt = (ray->mTermination[plane.mAxis] <= plane.mPosition);
	4056
[1145]	4057	// add view cell volume to front volume
[1189]	4058	const bool addToFront =
	4059	((originInside && originGt) \|\| (terminationInside && terminationGt));
[1145]	4060
	4061	// add view cell volume to back volume
[1189]	4062	const bool addToBack =
	4063	((originInside && originLt/!originGt/) \|\| (terminationInside && terminationLt/terminationGt/));
[1145]	4064
	4065	// classify ray with respect to the child nodes the view cells contribute
	4066	if (addToFront && addToBack)
	4067	return 0;
	4068	else if (addToBack)
	4069	return -1;
	4070	else if (addToFront)
	4071	return 1;
	4072
	4073	return -2;
	4074	}
	4075
	4076
[1186]	4077	int OspTree::ClassifyRays(const RayInfoContainer &rays,
	4078	KdLeaf *leaf,
	4079	const AxisAlignedPlane &plane,
	4080	RayInfoContainer &frontRays,
	4081	RayInfoContainer &backRays) const
	4082	{
	4083	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4084
	4085	for (rit = rays.begin(); rit < rit_end; ++ rit)
	4086	{
	4087	VssRay ray = (rit).mRay;
	4088
	4089	bool originGt = false;
	4090	bool terminationGt = false;
	4091
	4092	Intersectable *obj = ray->mOriginObject;
	4093
[1189]	4094	if (0 && obj)
[1186]	4095	{
[1189]	4096	originGt = ray->mOrigin[plane.mAxis] >= plane.mPosition;
[1186]	4097	}
	4098
	4099	obj = ray->mTerminationObject;
	4100
	4101	if (obj)
	4102	{
[1189]	4103	terminationGt = ray->mTermination[plane.mAxis] >= plane.mPosition;
[1186]	4104	}
	4105
	4106	// either begin or end point on front side
	4107	const bool addToFront = originGt \|\| terminationGt;
	4108
	4109	// add view cell volume to back volume
	4110	const bool addToBack = !originGt \|\| !terminationGt;
	4111
	4112	// classify ray with respect to the child nodes the view cells contribute
	4113	if (addToFront)
	4114	frontRays.push_back(*rit);
	4115	if (addToBack)
	4116	backRays.push_back(*rit);
	4117	}
	4118
	4119	return 0;
	4120	}
	4121
	4122
[1189]	4123	#if 0
[1186]	4124
[1145]	4125	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	4126	const OspTraversalData &tData,
	4127	float &normalizedOldRenderCost) const
	4128	{
[1089]	4129	float pvsFront = 0;
	4130	float pvsBack = 0;
	4131
	4132	// probability that view point lies in back / front node
[1138]	4133	float pOverall = 0;//data.mProbability; // todo matt§: value ok?
[1089]	4134	float pFront = 0;
	4135	float pBack = 0;
[1176]	4136	float pFrontAndBack = 0;
[1089]	4137
[1145]	4138	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
	4139
[1184]	4140	Intersectable::NewMail(3);
	4141
[1138]	4142	KdLeaf *leaf = tData.mNode;
[1181]	4143	const int totalPvs = (int)leaf->mObjects.size();
	4144
[1186]	4145	RayInfoContainer frontRays, backRays;
	4146	ClassifyRays(*tData.mRays, leaf, candidatePlane, frontRays, backRays);
[1089]	4147
[1186]	4148	ViewCellContainer touchedViewCells;
[1184]	4149
[1145]	4150	// sum up volume seen from the objects of left and right children
	4151	// => the volume is the weight for the render cost equation
	4152	ViewCell::NewMail(3);
[1176]	4153
[1137]	4154	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	4155
	4156	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
	4157	{
	4158	VssRay ray = (rit).mRay;
	4159
[1189]	4160	// add volume to volumes of left and / or right children
	4161	// if one of the ray end points is inside
	4162	const int classification = ClassifyRay(ray, leaf, candidatePlane);
[1145]	4163
[1189]	4164	ViewCellContainer viewCells;
	4165	mVspTree->GetViewCells(*ray, viewCells);
[1138]	4166
[1189]	4167	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1138]	4168
[1189]	4169	// traverse through view cells and classify them according
	4170	// to them being seen from to back / front / front and back node
	4171	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4172	{
	4173	ViewCell vc = vit;
[1176]	4174
[1189]	4175	// if not previously mailed
	4176	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
	4177	{
	4178	touchedViewCells.push_back(vc);
[1137]	4179	}
[1189]	4180
	4181	// classify / mail the view cell
	4182	MailViewCell(vc, classification);
[1137]	4183	}
	4184	}
	4185
[1184]	4186	// evaluate view cells volume contribution
	4187	// with respect to the mail box classification
	4188	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
[1181]	4189
[1184]	4190	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
[1176]	4191	{
	4192	AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
	4193	}
	4194
[1184]	4195	//////////////////////////////////////////////
	4196	//
	4197	// evaluate contribution of objects which are part of other kd nodes
	4198	// which are seen by the same view cell
	4199	// These contributions cannot be reduced by splitting, because
	4200	// the object would still be part of the pvs
[1181]	4201
[1184]	4202	float additionalFrontRenderCost = 0;
	4203	float additionalBackRenderCost = 0;
	4204
[1189]	4205	MailablePvsData::NewMail();
[1184]	4206
[1186]	4207	for (rit = tData.mRays->begin(); rit != tData.mRays->end(); ++ rit)
[1184]	4208	{
	4209	VssRay ray = (rit).mRay;
	4210
	4211	ViewCellContainer viewCells;
	4212	mVspTree->GetViewCells(*ray, viewCells);
	4213
	4214	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	4215
	4216	// traverse through view cells
	4217	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4218	{
	4219	ViewCell viewCell = vit;
	4220
	4221	// for a view cell:
	4222	// if object is also in the kd pvs entries from other kd leaves,
	4223	// render cost cannot be reduced for this view cell
	4224	// => the render cost was falsly reduced, add them again
	4225
[1186]	4226	if (ray->mTerminationObject)
[1184]	4227	{
	4228	Intersectable *obj = ray->mTerminationObject;
	4229
	4230	const bool renderCostWrong =
	4231	ViewCellHasMultipleReferences(obj, viewCell, true);
[1186]	4232
[1184]	4233	// if there is already an entry of this object in the view cell pvs
	4234	if (renderCostWrong)
	4235	{
	4236	// view cell was counted only for front or back => correct tjos
	4237	if (viewCell->Mailed(1) && obj->Mailed())
[1186]	4238	{
[1184]	4239	additionalFrontRenderCost += viewCell->GetVolume();
[1186]	4240	}
[1184]	4241	else if (viewCell->Mailed() && obj->Mailed(1))
[1186]	4242	{
[1184]	4243	additionalBackRenderCost += viewCell->GetVolume();
[1186]	4244	}
[1184]	4245	}
	4246	}
	4247
[1186]	4248	if (ray->mOriginObject)
[1184]	4249	{
	4250	Intersectable *obj = ray->mOriginObject;
	4251
	4252	const bool renderCostWrong =
	4253	ViewCellHasMultipleReferences(obj, viewCell, true);
	4254	// if there is already an entry of this object in the view cell pvs
	4255	if (renderCostWrong)
	4256	{
	4257	if (viewCell->Mailed(1) && obj->Mailed())
[1186]	4258	{
[1184]	4259	additionalFrontRenderCost += viewCell->GetVolume();
[1186]	4260	}
[1184]	4261	else if (viewCell->Mailed() && obj->Mailed(1))
[1186]	4262	{
[1184]	4263	additionalBackRenderCost += viewCell->GetVolume();
[1186]	4264	}
[1184]	4265	}
	4266	}
	4267	}
	4268	}
	4269
	4270	/////////////////////////////
	4271
	4272
[1178]	4273	// these are non-overlapping sets
	4274	pOverall = pFront + pBack + pFrontAndBack;
[1176]	4275
[1181]	4276
[1089]	4277	//-- pvs rendering heuristics
[1181]	4278
[1138]	4279	const float oldRenderCost = pOverall * totalPvs;
[1181]	4280
	4281	// sum up the terms:
	4282	// the view cells seeing
	4283	// a) the left node are weighted by the #left node objects
	4284	// b) the right node are weighted by the #right node objects
	4285	// c) both nodes are weighted by the #parent node objects
[1184]	4286	const float newRenderCost = pvsFront * pFront + pvsBack * pBack + totalPvs * pFrontAndBack
	4287	+ additionalFrontRenderCost + additionalBackRenderCost;
[1089]	4288
[1145]	4289	// normalize volume with view space volume
	4290	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
[1089]	4291
[1176]	4292	Debug << "\n(((( eval render cost decrease ))))" << endl
[1145]	4293	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
[1176]	4294	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
[1181]	4295	<< " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << tData.mProbability / viewSpaceVol << endl
[1145]	4296	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
[1184]	4297	<< "render cost decrease: " << renderCostDecrease << endl
	4298	<< "additional front " << additionalFrontRenderCost / viewSpaceVol
	4299	<< " additional back " << additionalBackRenderCost / viewSpaceVol << endl;
	4300
	4301	if (oldRenderCost < newRenderCost * 0.99)
	4302	Debug <<"error!!"<<endl;
	4303
[1181]	4304	//if ((((pOverall - tData.mProbability) / viewSpaceVol) > 0.00001))
	4305	// Debug << "ERROR!!"<<endl;
[1089]	4306
[1145]	4307	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
	4308
[1181]	4309
[1145]	4310	return renderCostDecrease;
[1089]	4311	}
	4312
[1186]	4313	#else
[1089]	4314
[1186]	4315	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	4316	const OspTraversalData &tData,
	4317	float &normalizedOldRenderCost) const
	4318	{
	4319	float pvsFront = 0;
	4320	float pvsBack = 0;
	4321
	4322	// probability that view point lies in back / front node
	4323	float pOverall = 0;//data.mProbability; // todo matt§: value ok?
	4324	float pFront = 0;
	4325	float pBack = 0;
	4326	float pFrontAndBack = 0;
	4327
	4328	Intersectable::NewMail(3);
	4329	KdLeaf *leaf = tData.mNode;
[1189]	4330
	4331	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
[1186]	4332	const int totalPvs = (int)leaf->mObjects.size();
	4333
	4334	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	4335
	4336	// evaluate reverse pvs and view cell volume on left and right cell
	4337	// note: should I take all leaf objects or rather the objects hit by rays?
	4338	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	4339	{
	4340	int pvsContri = 0;
	4341
	4342	Intersectable obj = oit;
	4343	const AxisAlignedBox3 box = obj->GetBox();
	4344
	4345	// test if box falls in left / right child node
	4346	if (box.Max(candidatePlane.mAxis) >= candidatePlane.mPosition)
	4347	{
	4348	++ pvsFront;
	4349	obj->Mail();
	4350	}
	4351
	4352	if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
	4353	{
	4354	++ pvsBack;
	4355
	4356	if (obj->Mailed())
	4357	obj->Mail(2);
	4358	else
	4359	obj->Mail(1);
	4360	}
	4361	}
	4362
	4363
	4364	ViewCellContainer touchedViewCells;
	4365
	4366	// sum up volume seen from the objects of left and right children
	4367	// => the volume is the weight for the render cost equation
	4368	ViewCell::NewMail(3);
	4369
	4370	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	4371	//map<Intersectable *, ViewCellContainer> objectsMap;
	4372
	4373	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
	4374	{
	4375	VssRay ray = (rit).mRay;
	4376
	4377	// add volume to volumes of left and / or right children
	4378	// if one of the ray end points is inside
	4379	const int classification = ClassifyRay(ray, leaf, candidatePlane);
	4380
	4381	ViewCellContainer viewCells;
	4382	mVspTree->GetViewCells(*ray, viewCells);
	4383
	4384	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	4385
	4386	// traverse through view cells and classify them according
	4387	// to them being seen from to back / front / front and back node
	4388	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4389	{
	4390	ViewCell vc = vit;
	4391
	4392	// if not previously mailed
	4393	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
	4394	{
	4395	touchedViewCells.push_back(vc);
	4396	}
	4397
	4398	// classify / mail the view cell
[1189]	4399	MailViewCell(vc, classification);
[1186]	4400	}
	4401	}
	4402
	4403	// evaluate view cells volume contribution
	4404	// with respect to the mail box classification
	4405	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	4406
	4407	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	4408	{
	4409	AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
	4410	}
	4411
	4412	//////////////////////////////////////////////
	4413	//
	4414	// evaluate contribution of objects which are part of other kd nodes
	4415	// which are seen by the same view cell
	4416	// These contributions cannot be reduced by splitting, because
	4417	// the object would still be part of the pvs
	4418
[1189]	4419	float newRc = 0;
[1186]	4420	float rc = 0;
	4421
[1189]	4422	MailablePvsData::NewMail();
	4423	//ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1186]	4424
	4425	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	4426	{
	4427	Intersectable obj = oit;
	4428	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	4429
	4430	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	4431	{
	4432	ViewCell vc = vit;
[1189]	4433
	4434	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1186]	4435
	4436	if (!vdata)
	4437	{
[1189]	4438	Debug << "here86 error!!"<<endl;
	4439	continue;
	4440	}
[1186]	4441
[1189]	4442	if (!vdata->Mailed())
[1186]	4443	{
	4444	vdata->Mail();
[1189]	4445	rc += vc->GetVolume();
	4446
	4447	if ((vdata->mSumPdf > 1.5) \|\|
	4448	vc->Mailed(2) \|\|
	4449	obj->Mailed(2) \|\|
	4450	(obj->Mailed() && vc->Mailed()) \|\|
	4451	(obj->Mailed(1) && vc->Mailed(1))
	4452	)
	4453	{
	4454	newRc += vc->GetVolume();
	4455	}
[1186]	4456	}
	4457	}
	4458	}
	4459
	4460
	4461	/////////////////////////////
	4462
	4463
	4464	// these are non-overlapping sets
	4465	pOverall = pFront + pBack + pFrontAndBack;
	4466
	4467
	4468	//-- pvs rendering heuristics
	4469
[1189]	4470	const float oldRenderCost = rc;//pOverall * totalPvs;
[1186]	4471
	4472	// sum up the terms:
	4473	// the view cells seeing
	4474	// a) the left node are weighted by the #left node objects
	4475	// b) the right node are weighted by the #right node objects
	4476	// c) both nodes are weighted by the #parent node objects
[1189]	4477	const float newRenderCost = newRc//pvsFront * pFront + pvsBack * pBack + totalPvs * pFrontAndBack
	4478	;// + additionalFrontRenderCost + additionalBackRenderCost;
[1186]	4479
	4480	// normalize volume with view space volume
	4481	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
	4482
	4483	Debug << "\n(((( eval render cost decrease ))))" << endl
	4484	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
	4485	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
	4486	<< " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << tData.mProbability / viewSpaceVol << endl
	4487	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
[1189]	4488	<< "render cost decrease: " << renderCostDecrease << endl;
	4489	//<< "additional front " << additionalFrontRenderCost / viewSpaceVol
	4490	//<< " additional back " << additionalBackRenderCost / viewSpaceVol << endl;
[1186]	4491
	4492	if (oldRenderCost < newRenderCost * 0.99)
	4493	Debug <<"error!!"<<endl;
	4494
	4495	//if ((((pOverall - tData.mProbability) / viewSpaceVol) > 0.00001))
	4496	// Debug << "ERROR!!"<<endl;
	4497
	4498	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
	4499
	4500
	4501	return renderCostDecrease;
	4502	}
	4503	#endif
	4504
[1189]	4505
[1135]	4506	void OspTree::ComputeBoundingBox(const ObjectContainer &objects,
	4507	AxisAlignedBox3 *forcedBoundingBox)
[1089]	4508	{
	4509	if (forcedBoundingBox)
	4510	{
	4511	mBoundingBox = *forcedBoundingBox;
	4512	}
	4513	else // compute vsp tree bounding box
	4514	{
	4515	mBoundingBox.Initialize();
	4516
	4517	ObjectContainer::const_iterator oit, oit_end = objects.end();
	4518
	4519	//-- compute bounding box
	4520	for (oit = objects.begin(); oit != oit_end; ++ oit)
	4521	{
	4522	Intersectable obj = oit;
	4523
	4524	// compute bounding box of view space
	4525	mBoundingBox.Include(obj->GetBox());
	4526	}
	4527	}
	4528	}
	4529
[1135]	4530
[1143]	4531	void OspTree::ProcessMultipleRefs(KdLeaf *leaf) const
[1089]	4532	{
[1143]	4533	// find objects from multiple kd-leaves
	4534	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1089]	4535
[1143]	4536	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
[1122]	4537	{
[1143]	4538	Intersectable object = oit;
	4539
	4540	if (object->mReferences > 1)
[1122]	4541	{
[1143]	4542	leaf->mMultipleObjects.push_back(object);
[1122]	4543	}
[1089]	4544	}
	4545	}
	4546
[1143]	4547
[1106]	4548	void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
	4549	{
	4550	stack<KdNode *> nodeStack;
	4551	nodeStack.push(mRoot);
[1089]	4552
[1106]	4553	while (!nodeStack.empty())
	4554	{
	4555	KdNode *node = nodeStack.top();
	4556	nodeStack.pop();
	4557	if (node->IsLeaf())
	4558	{
	4559	KdLeaf leaf = (KdLeaf )node;
	4560	leaves.push_back(leaf);
	4561	}
	4562	else
	4563	{
	4564	KdInterior interior = (KdInterior )node;
	4565	nodeStack.push(interior->mBack);
	4566	nodeStack.push(interior->mFront);
	4567	}
	4568	}
	4569	}
[1021]	4570
[1072]	4571
[1144]	4572	AxisAlignedBox3 OspTree::GetBoundingBox(KdNode *node) const
[1106]	4573	{
	4574	if (!node->mParent)
	4575	return mBoundingBox;
[1072]	4576
[1106]	4577	if (!node->IsLeaf())
	4578	{
	4579	return (dynamic_cast<KdInterior *>(node))->mBox;
	4580	}
	4581
	4582	KdInterior parent = dynamic_cast<KdInterior >(node->mParent);
	4583
	4584	AxisAlignedBox3 box(parent->mBox);
	4585
	4586	if (parent->mFront == node)
	4587	box.SetMin(parent->mAxis, parent->mPosition);
	4588	else
	4589	box.SetMax(parent->mAxis, parent->mPosition);
	4590
	4591	return box;
	4592	}
	4593
	4594
[1121]	4595	void OspTree::CollectViewCells(KdLeaf *leaf, ViewCellContainer &viewCells)
	4596	{
	4597	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	4598
	4599	ViewCell::NewMail();
	4600
	4601	// loop through all object and collect view cell pvs of this node
	4602	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	4603	{
	4604	Intersectable obj = oit;
	4605
	4606	ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
	4607
	4608	for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
	4609	{
	4610	ViewCell vc = (vit).first;
	4611
	4612	if (!vc->Mailed())
	4613	{
	4614	vc->Mail();
	4615	viewCells.push_back(vc);
	4616	}
	4617	}
	4618	}
	4619	}
	4620
	4621
	4622	void OspTree::CollectDirtyCandidates(OspSplitCandidate *sc,
	4623	vector<SplitCandidate *> &dirtyList)
	4624	{
[1138]	4625	OspTraversalData &tData = sc->mParentData;
	4626	KdLeaf *node = tData.mNode;
	4627
	4628	ViewCell::NewMail();
	4629	ViewCellContainer viewCells;
	4630	ViewCellContainer tmpViewCells;
[1121]	4631
[1138]	4632	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
[1121]	4633
[1138]	4634	// find all view cells associated with the rays, add them to view cells
	4635	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
	4636	{
	4637	VssRay ray = (rit).mRay;
	4638	mVspTree->GetViewCells(*ray, tmpViewCells);
[1121]	4639
[1138]	4640	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
[1121]	4641
[1138]	4642	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
	4643	{
	4644	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
	4645
	4646	if (!vc->Mailed())
	4647	{
	4648	vc->Mail();
	4649	viewCells.push_back(vc);
	4650	}
	4651	}
	4652	}
	4653
	4654
	4655	// split candidates holding this view cells
	4656	// are thrown into dirty list
[1121]	4657	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	4658
	4659	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4660	{
	4661	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
	4662
	4663	VspLeaf *leaf = vc->mLeaf;
	4664	dirtyList.push_back(leaf->GetSplitCandidate());
	4665	}
	4666	}
	4667
	4668
[1135]	4669	KdNode *OspTree::GetRoot() const
	4670	{
	4671	return mRoot;
	4672	}
	4673
	4674
[1133]	4675	KdLeaf OspTree::GetLeaf(const Vector3 &pt, KdNode node) const
	4676	{
[1144]	4677	// start from root of tree
[1133]	4678	if (node == NULL)
[1135]	4679	{
[1133]	4680	node = mRoot;
[1135]	4681	}
[1133]	4682
	4683	stack<KdNode *> nodeStack;
	4684	nodeStack.push(node);
	4685
	4686	KdLeaf *leaf = NULL;
	4687
	4688	while (!nodeStack.empty())
	4689	{
	4690	KdNode *node = nodeStack.top();
	4691	nodeStack.pop();
	4692
	4693	if (node->IsLeaf())
	4694	{
	4695	leaf = dynamic_cast<KdLeaf *>(node);
	4696	}
	4697	else
	4698	{
[1144]	4699	// find point
[1133]	4700	KdInterior interior = dynamic_cast<KdInterior >(node);
	4701
[1144]	4702	if (interior->mPosition > pt[interior->mAxis])
[1135]	4703	{
[1133]	4704	nodeStack.push(interior->mBack);
[1135]	4705	}
[1133]	4706	else
[1135]	4707	{
[1133]	4708	nodeStack.push(interior->mFront);
[1135]	4709	}
[1133]	4710	}
	4711	}
	4712
	4713	return leaf;
	4714	}
	4715
	4716
[1186]	4717	void OspTree::PreprocessRays(KdLeaf *root,
	4718	const VssRayContainer &sampleRays,
[1176]	4719	RayInfoContainer &rays)
[1133]	4720	{
[1121]	4721	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[1186]	4722	RayInfoContainer clippedRays;
[1020]	4723
	4724	long startTime = GetTime();
	4725
	4726	cout << "storing rays ... ";
	4727
	4728	Intersectable::NewMail();
	4729
[1121]	4730	//-- store rays and objects
[1016]	4731	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	4732	{
	4733	VssRay ray = rit;
[1178]	4734
[1016]	4735	float minT, maxT;
[1121]	4736	static Ray hray;
[1016]	4737
	4738	hray.Init(*ray);
[1027]	4739
[1016]	4740	// TODO: not very efficient to implictly cast between rays types
[1135]	4741	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
[1016]	4742	{
	4743	float len = ray->Length();
[1186]	4744	if (!len)
[1016]	4745	len = Limits::Small;
	4746
[1186]	4747	clippedRays.push_back(RayInfo(ray, minT / len, maxT / len));
[1176]	4748
	4749	// HACK: reset nodes for the case we have used object kd tree for
	4750	// tree building.
[1189]	4751	ray->mOriginNode = NULL;
[1176]	4752	ray->mTerminationNode = NULL;
[1016]	4753	}
	4754	}
[1020]	4755
[1186]	4756	FilterRays(root, clippedRays, rays);
	4757
[1027]	4758	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1121]	4759	}
[1020]	4760
[1089]	4761
[1135]	4762
	4763	int OspTree::SplitRays(const AxisAlignedPlane &plane,
	4764	RayInfoContainer &rays,
	4765	RayInfoContainer &frontRays,
	4766	RayInfoContainer &backRays) const
	4767	{
	4768	int splits = 0;
	4769
	4770	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4771
	4772	for (rit = rays.begin(); rit != rit_end; ++ rit)
	4773	{
	4774	RayInfo bRay = *rit;
	4775
	4776	VssRay *ray = bRay.mRay;
	4777	float t;
	4778
	4779	// get classification and receive new t
	4780	//-- test if start point behind or in front of plane
	4781	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
	4782
	4783	if (side == 0)
	4784	{
	4785	++ splits;
	4786
	4787	if (ray->HasPosDir(plane.mAxis))
	4788	{
	4789	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	4790	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	4791	}
	4792	else
	4793	{
	4794	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	4795	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	4796	}
	4797	}
	4798	else if (side == 1)
	4799	{
	4800	frontRays.push_back(bRay);
	4801	}
	4802	else
	4803	{
	4804	backRays.push_back(bRay);
	4805	}
	4806	}
	4807
	4808	return splits;
	4809	}
	4810
	4811
[1186]	4812	int OspTree::FilterRays(KdLeaf *leaf,
	4813	const RayInfoContainer &rays,
	4814	RayInfoContainer &filteredRays)
	4815	{
	4816	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4817
	4818	for (rit = rays.begin(); rit != rit_end; ++ rit)
	4819	{
	4820	VssRay ray = (rit).mRay;
	4821
	4822	// test if intersection point with one of the objects is inside this node
	4823	const bool originInside = EndPointInsideNode(leaf, *ray, false);
	4824	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
	4825
	4826	if (originInside \|\| terminationInside)
	4827	{
	4828	filteredRays.push_back(ray);
	4829	}
	4830	}
	4831
	4832	return 0;
	4833	}
	4834
	4835
[1184]	4836	int OspTree::CheckViewCellsPvs(KdLeaf *leaf,
	4837	const RayInfoContainer &rays) const
	4838	{
	4839	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4840
	4841	Intersectable::NewMail();
	4842	ObjectContainer touchedObjects;
	4843
	4844
	4845	for (rit = rays.begin(); rit < rit_end; ++ rit)
	4846	{
	4847	VssRay ray = (rit).mRay;
	4848
[1189]	4849	if (ray->mTerminationObject)
[1184]	4850	{
	4851	Intersectable *obj = ray->mTerminationObject;
	4852
	4853	if (!obj->Mailed())
	4854	{
	4855	obj->Mail();
	4856	touchedObjects.push_back(obj);
	4857	}
	4858	}
	4859
[1189]	4860	if (ray->mOriginObject)
[1184]	4861	{
	4862	Intersectable *obj = ray->mOriginObject;
	4863
	4864	if (!obj->Mailed())
	4865	{
	4866	obj->Mail();
	4867	touchedObjects.push_back(obj);
	4868	}
	4869	}
	4870	}
	4871	Debug << "here65 " << touchedObjects.size() << endl;
	4872	ObjectContainer::const_iterator it, it_end = touchedObjects.end();
	4873	for (it = touchedObjects.begin(); it != it_end; ++ it)
	4874	{
	4875	Debug << "\nhere94 obj: " << (it) << " size: " << (it)->mViewCellPvs.GetSize() << endl << endl;
	4876	ViewCellPvsMap::const_iterator mit, mit_end = (*it)->mViewCellPvs.mEntries.end();
	4877
	4878	for (mit = (*it)->mViewCellPvs.mEntries.begin(); mit != mit_end; ++ mit)
	4879	{
	4880	Debug << "newsumpdf: " << (*mit).second.mSumPdf << endl;
	4881	}
	4882	}
	4883
	4884	return 0;
	4885	}
	4886
	4887
[1141]	4888	KdIntersectable OspTree::GetOrCreateKdIntersectable(KdNode node)
	4889	{
	4890	// search nodes
[1144]	4891	std::map<KdNode , KdIntersectable >::
	4892	const_iterator it = mKdIntersectables.find(node);
[1135]	4893
[1141]	4894	if (it != mKdIntersectables.end())
	4895	{
	4896	return (*it).second;
	4897	}
[1135]	4898
[1141]	4899	// not in map => create new entry
[1189]	4900	KdIntersectable *kdObj = new KdIntersectable(node);
[1141]	4901	mKdIntersectables[node] = kdObj;
	4902
	4903	return kdObj;
	4904	}
	4905
	4906
[1176]	4907	/*
[1145]	4908	void OspTree::AddViewCellVolume(ViewCell *vc,
	4909	const int cf,
	4910	float &frontVol,
	4911	float &backVol,
	4912	float &totalVol) const
	4913	{
	4914	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
	4915	const float vol = vc->GetVolume();
[1143]	4916
[1145]	4917	// view cell not found yet => new
	4918	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
	4919	{
	4920	totalVol += vol;
	4921	}
	4922
	4923	if (cf >= 0) // front volume
	4924	{
	4925	if (!vc->Mailed() && !vc->Mailed(2))
	4926	{
	4927	frontVol += vol;
	4928
	4929	// already in back volume => in both volumes
	4930	if (vc->Mailed(1))
	4931	vc->Mail(2);
	4932	else
	4933	vc->Mail();
	4934	}
	4935	}
	4936
	4937	if (cf <= 0) // back volume
	4938	{
	4939	if (!vc->Mailed(1) && !vc->Mailed(2))
	4940	{
	4941	backVol += vol;
	4942
	4943	// already in front volume => in both volume
	4944	if (vc->Mailed())
	4945	vc->Mail(2);
	4946	else
	4947	vc->Mail(1);
	4948	}
	4949	}
	4950	}
[1176]	4951	*/
[1184]	4952
	4953
[1176]	4954	void OspTree::MailViewCell(ViewCell *vc, const int cf) const
	4955	{
	4956	if (vc->Mailed(2)) // already classified
	4957	return;
[1145]	4958
[1176]	4959	if (cf >= 0) // front volume
	4960	{
[1189]	4961	// already in back volume => in both volumes
[1176]	4962	if (vc->Mailed(1))
	4963	{
	4964	vc->Mail(2);
	4965	}
	4966	else
	4967	{
	4968	vc->Mail();
	4969	}
	4970	}
[1145]	4971
[1176]	4972	if (cf <= 0) // back volume
	4973	{
	4974	// already in front volume => in both volume
	4975	if (vc->Mailed())
	4976	{
	4977	vc->Mail(2);
	4978	}
	4979	else
	4980	{
	4981	vc->Mail(1);
	4982	}
	4983	}
	4984	}
	4985
	4986
	4987	void OspTree::AddViewCellVolumeContri(ViewCell *vc,
	4988	float &frontVol,
	4989	float &backVol,
	4990	float &frontAndBackVol) const
	4991	{
	4992	if (vc->Mailed())
[1181]	4993	{
[1176]	4994	frontVol += vc->GetVolume();
[1181]	4995	}
[1176]	4996	else if (vc->Mailed(1))
[1181]	4997	{
[1176]	4998	backVol += vc->GetVolume();
[1181]	4999	}
[1176]	5000	else if (vc->Mailed(2))
[1181]	5001	{
[1176]	5002	frontAndBackVol += vc->GetVolume();
[1181]	5003	}
[1176]	5004	}
	5005
	5006
[1184]	5007	float OspTree::EvalViewCellsVolume(KdLeaf *leaf,
	5008	const RayInfoContainer &rays) const
[1180]	5009	{
	5010	float vol = 0;
	5011	ViewCell::NewMail();
[1176]	5012
[1180]	5013	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	5014
	5015	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	5016	{
	5017	VssRay ray = (rit).mRay;
	5018
	5019	ViewCellContainer viewCells;
[1189]	5020	mVspTree->GetViewCells(*ray, viewCells);
[1180]	5021
	5022	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5023
	5024	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5025	{
	5026	ViewCell vc = vit;
	5027
	5028	if (!vc->Mailed())
	5029	{
	5030	vc->Mail();
	5031	vol += vc->GetVolume();
	5032	}
	5033	}
	5034	}
	5035
	5036	return vol;
	5037	}
	5038
	5039
[1184]	5040	bool OspTree::AddViewCellToObjectPvs(Intersectable *obj,
	5041	ViewCell *vc,
	5042	float &contribution,
	5043	bool onlyMailed) const
	5044	{
	5045	contribution = 0; // todo
	5046
[1189]	5047	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1184]	5048
	5049	if (!vdata)
	5050	{
	5051	vdata = obj->mViewCellPvs.AddSample2(vc, 1);
	5052	}
	5053	else if (!onlyMailed \|\| !vdata->Mailed())
	5054	{
	5055	obj->mViewCellPvs.AddSample(vc, 1);
	5056	}
	5057
	5058	vdata->Mail();
	5059
	5060	return true;
	5061	}
	5062
	5063
[1189]	5064	void OspTree::CollectTouchedViewCells(const RayInfoContainer &rays,
	5065	ViewCellContainer &touchedViewCells) const
	5066	{
	5067	ViewCell::NewMail();
	5068
	5069	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	5070
	5071	for (rit = rays.begin(); rit != rit_end; ++ rit)
	5072	{
	5073	VssRay ray = (rit).mRay;
	5074
	5075	ViewCellContainer viewCells;
	5076	mVspTree->GetViewCells(*ray, viewCells);
	5077
	5078	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5079
	5080	// traverse through view cells and classify them according
	5081	// to them being seen from to back / front / front and back node
	5082	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5083	{
	5084	ViewCell vc = vit;
	5085	if (!vc->Mailed())
	5086	{
	5087	vc->Mail();
	5088	touchedViewCells.push_back(vc);
	5089	}
	5090	}
	5091	}
	5092	}
	5093
	5094
[1184]	5095	int OspTree::UpdateViewCellsPvs(KdLeaf *leaf,
	5096	const RayInfoContainer &rays) const
	5097
	5098	{
[1189]	5099	MailablePvsData::NewMail();
	5100
	5101	/*RayInfoContainer::const_iterator rit, rit_end = rays.end();
[1184]	5102
	5103	for (rit = rays.begin(); rit < rit_end; ++ rit)
	5104	{
	5105	VssRay ray = (rit).mRay;
	5106
[1189]	5107	ViewCellContainer viewCells;
	5108	mVspTree->GetViewCells(*ray, viewCells);
[1184]	5109
[1189]	5110	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5111
	5112	// traverse through view cells and classify them according
	5113	// to them being seen from to back / front / front and back node
	5114	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
[1184]	5115	{
[1189]	5116	ViewCell vc = vit;
[1184]	5117
[1189]	5118	Intersectable *obj = ray->mTerminationObject;
	5119	if (obj)
	5120	{
	5121	float contri;
	5122	AddViewCellToObjectPvs(obj, vc, contri, true);
	5123	}
[1184]	5124
[1189]	5125	obj = ray->mOriginObject;
	5126	if (obj)
[1184]	5127	{
[1189]	5128	float contri;
	5129	AddViewCellToObjectPvs(obj, vc, contri, true);
	5130	}
	5131	}
	5132	}*/
	5133
	5134	ViewCellContainer touchedViewCells;
	5135	CollectTouchedViewCells(rays, touchedViewCells);
[1184]	5136
[1189]	5137	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1184]	5138
[1189]	5139	for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
	5140	{
	5141	Intersectable obj = oit;
	5142	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5143
	5144	// traverse through view cells and classify them according
	5145	// to them being seen from to back / front / front and back node
	5146	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5147	{
	5148	ViewCell vc = vit;
	5149	float contri;
	5150	AddViewCellToObjectPvs(obj, vc, contri, true);
[1184]	5151	}
	5152	}
	5153
	5154	return 0;
	5155	}
	5156
	5157
	5158	int OspTree::RemoveParentViewCellsPvs(KdLeaf *leaf,
	5159	const RayInfoContainer &rays
	5160	) const
	5161
	5162	{
[1189]	5163	MailablePvsData::NewMail();
[1184]	5164
[1189]	5165	/*RayInfoContainer::const_iterator rit, rit_end = rays.end();
[1184]	5166	for (rit = rays.begin(); rit < rit_end; ++ rit)
	5167	{
	5168	VssRay ray = (rit).mRay;
	5169
	5170	// test if intersection point with one of the objects is inside this node
[1189]	5171	ViewCellContainer viewCells;
	5172	mVspTree->GetViewCells(*ray, viewCells);
[1184]	5173
[1189]	5174	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5175
	5176	// traverse through view cells and classify them according
	5177	// to them being seen from to back / front / front and back node
	5178	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
[1184]	5179	{
[1189]	5180	ViewCell vc = vit;
	5181	Intersectable *obj = ray->mTerminationObject;
[1184]	5182
[1189]	5183	if (obj)
[1184]	5184	{
[1189]	5185	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1184]	5186
[1189]	5187	if (vdata && !vdata->Mailed())
[1184]	5188	{
[1189]	5189	vdata->Mail();
	5190	obj->mViewCellPvs.RemoveSample(vc, 1);
[1184]	5191	}
[1189]	5192	}
[1184]	5193
[1189]	5194	obj = ray->mOriginObject;
[1184]	5195
[1189]	5196	if (obj)
	5197	{
	5198	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
	5199
	5200	if (vdata && !vdata->Mailed())
	5201	{
	5202	vdata->Mail();
	5203	obj->mViewCellPvs.RemoveSample(vc, 1);
[1184]	5204	}
	5205	}
	5206	}
[1189]	5207	}*/
	5208
	5209	ViewCellContainer touchedViewCells;
	5210	CollectTouchedViewCells(rays, touchedViewCells);
	5211
	5212	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	5213
	5214	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	5215	{
	5216	Intersectable obj = oit;
	5217
	5218	// traverse through view cells and classify them according
	5219	// to them being seen from to back / front / front and back node
	5220	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5221
	5222	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5223	{
	5224	ViewCell vc = vit;
	5225
	5226	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
	5227
	5228	if (vdata && !vdata->Mailed())
	5229	{
	5230	vdata->Mail();
	5231	obj->mViewCellPvs.RemoveSample(vc, 1);
	5232	}
	5233	}
[1184]	5234	}
	5235
	5236	return 0;
	5237	}
	5238
	5239
[1186]	5240	float OspTree::EvalRenderCost(const VssRayContainer &myrays)
[1184]	5241	{
	5242	float rc = 0;
[1186]	5243	float prop = mVspTree->GetBoundingBox().GetVolume();
	5244
[1184]	5245	KdLeafContainer leaves;
	5246	CollectLeaves(leaves);
	5247
[1186]	5248	ViewCellContainer vcleaves;
	5249	mVspTree->CollectViewCells(vcleaves, false);
	5250
	5251
	5252	ViewCellContainer::const_iterator vit, vit_end = vcleaves.end();
	5253
	5254	for (vit = vcleaves.begin(); vit != vit_end; ++ vit)
	5255	{
	5256	ViewCell vc = vit;
	5257	vc->GetPvs().Clear();
	5258	}
	5259
[1184]	5260	KdLeafContainer::const_iterator kit, kit_end = leaves.end();
[1186]	5261
[1189]	5262	MailablePvsData::NewMail();
[1186]	5263
[1184]	5264	for (kit = leaves.begin(); kit != kit_end; ++ kit)
	5265	{
	5266	KdLeaf leaf = kit;
	5267	float newCost = 0;
	5268	float vol = 0;
	5269
	5270	ViewCell::NewMail();
	5271	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	5272	ViewCellContainer touchedViewCells;
	5273
	5274	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	5275	{
	5276	VssRay ray = rit;
	5277
	5278	// test if intersection point with one of the objects is inside this node
	5279	const bool originInside = EndPointInsideNode(leaf, *ray, false);
	5280	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
	5281
	5282	if (originInside \|\| terminationInside)
	5283	{
	5284	ViewCellContainer viewCells;
	5285	mVspTree->GetViewCells(*ray, viewCells);
	5286
	5287	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5288
	5289	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5290	{
	5291	ViewCell vc = vit;
	5292
	5293	// if not previously mailed
	5294	if (!vc->Mailed())
	5295	{
	5296	vc->Mail();
	5297	touchedViewCells.push_back(vc);
	5298	}
	5299
	5300	}
	5301	}
	5302	}
	5303
	5304	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	5305
	5306	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	5307	{
	5308	Intersectable obj = oit;
	5309	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5310
	5311	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5312	{
	5313	ViewCell vc = vit;
[1189]	5314	PvsData *vdata = vc->GetPvs().Find(obj);
[1184]	5315
	5316	if (!vdata)
	5317	{
	5318	vc->GetPvs().AddSample(obj, 1);
	5319	newCost += vc->GetVolume();
[1189]	5320	}
[1186]	5321
[1189]	5322	/* MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1186]	5323
	5324	if (!vdata \|\| !vdata->Mailed())
	5325	{
	5326	newCost += vc->GetVolume();
	5327	if (!vdata)
	5328	vdata = obj->mViewCellPvs.AddSample2(vc, 1);
	5329	vdata->Mail();
[1189]	5330	}*/
[1184]	5331	}
	5332	}
	5333
	5334	rc += newCost;
	5335	}
	5336
	5337	return rc / prop;
	5338	}
	5339
	5340
[1186]	5341	float OspTree::EvalLeafCost(const OspTraversalData &tData)
	5342	{
	5343	KdLeaf *leaf = tData.mNode;
[1135]	5344
[1186]	5345	float rc = 0;
	5346	//float prop = mVspTree->GetBoundingBox().GetVolume();
	5347	//float vol = 0;
	5348	//ViewCell::NewMail();
	5349
	5350	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	5351	ViewCellContainer touchedViewCells;
[1135]	5352
[1186]	5353	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
	5354	{
	5355	VssRay ray = (rit).mRay;
	5356
	5357	// test if intersection point with one of the objects is inside this node
	5358
	5359	ViewCellContainer viewCells;
	5360	mVspTree->GetViewCells(*ray, viewCells);
	5361
	5362	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5363
	5364	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5365	{
	5366	ViewCell vc = vit;
	5367
	5368	// if not previously mailed
	5369	if (!vc->Mailed())
	5370	{
	5371	vc->Mail();
	5372	touchedViewCells.push_back(vc);
	5373	}
	5374	}
	5375	}
	5376
	5377	// clear pvs of involved view cells
	5378	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5379
	5380	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5381	{
	5382	ViewCell vc = vit;
	5383	vc->GetPvs().Clear();
	5384	}
	5385
	5386	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	5387
	5388	//Debug << "here53 " << touchedViewCells.size() << endl;
	5389	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	5390	{
	5391	Intersectable obj = oit;
	5392
	5393	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5394	{
	5395	ViewCell vc = vit;
[1189]	5396	PvsData *vdata = vc->GetPvs().Find(obj);
[1186]	5397
	5398	if (!vdata)
	5399	{
	5400	vc->GetPvs().AddSample(obj, 1);
	5401	rc += vc->GetVolume();
	5402	//prop += vc->GetVolume();
	5403	}
	5404	}
	5405	}
	5406
	5407	return rc;
	5408	}
	5409
	5410
[1201]	5411	bool OspTree::Export(OUT_STREAM &stream)
	5412	{
	5413	ExportNode(mRoot, stream);
[1186]	5414
[1201]	5415	return true;
	5416	}
	5417
	5418
	5419	void OspTree::ExportNode(KdNode *node, OUT_STREAM &stream)
	5420	{
	5421	if (node->IsLeaf())
	5422	{
	5423	KdLeaf leaf = dynamic_cast<KdLeaf >(node);
	5424
	5425	stream << "<Leaf ";
	5426	stream << "objects=\"";
	5427
	5428	//-- export objects in kd leaves
	5429	//if (mExportObjects) ExportObjects(leaf, stream);
	5430
	5431	stream << "\" />" << endl;
	5432	//stream << " </Leaf>" << endl;
	5433	}
	5434	else
	5435	{
	5436	KdInterior interior = dynamic_cast<KdInterior >(node);
	5437
	5438	stream << "<Interior plane=\"" << interior->mPosition << " "
	5439	<< interior->mAxis << "\">" << endl;
	5440
	5441	ExportNode(interior->mBack, stream);
	5442	ExportNode(interior->mFront, stream);
	5443
	5444	stream << "</Interior>" << endl;
	5445	}
	5446	}
	5447
	5448
	5449	struct KdObjectsTraversalData
	5450	{
	5451	KdNode *node;
	5452	ObjectContainer *objects;
	5453	};
	5454
	5455
	5456	void OspTree::InsertObjects(KdNode *node, const ObjectContainer &objects)
	5457	{
	5458	stack<KdObjectsTraversalData> tStack;
	5459
	5460	while (!tStack.empty())
	5461	{
	5462	KdObjectsTraversalData tData = tStack.top();
	5463	tStack.pop();
	5464
	5465	KdNode *node = tData.node;
	5466
	5467	if (node->IsLeaf())
	5468	{
	5469	KdLeaf leaf = dynamic_cast<KdLeaf >(node);
	5470
	5471	ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
	5472
	5473	for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
	5474	{
	5475	leaf->mObjects.push_back(*oit);
	5476	}
	5477	}
	5478	else // interior
	5479	{
	5480	KdObjectsTraversalData frontData, backData;
	5481	KdInterior interior = dynamic_cast<KdInterior >(node);
	5482
	5483	frontData.objects = new ObjectContainer();
	5484	backData.objects = new ObjectContainer();
	5485
	5486	ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
	5487
	5488	for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
	5489	{
	5490	Intersectable object = oit;
	5491
	5492	// determine the side of this ray with respect to the plane
	5493	const AxisAlignedBox3 box = object->GetBox();
	5494
	5495	if (box.Max(interior->mAxis) >= interior->mPosition)
	5496	{
	5497	frontData.objects->push_back(object);
	5498	}
	5499
	5500	if (box.Min(interior->mAxis) < interior->mPosition)
	5501	{
	5502	backData.objects->push_back(object);
	5503	}
	5504	}
	5505
	5506	tStack.push(backData);
	5507	tStack.push(frontData);
	5508	}
	5509
	5510	DEL_PTR(tData.objects);
	5511	}
	5512	}
	5513
	5514
[1186]	5515	/*******************************************************************/
	5516	/* class HierarchyManager implementation */
	5517	/*******************************************************************/
	5518
	5519
[1135]	5520	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
	5521	mVspTree(vspTree), mOspTree(ospTree)
	5522	{
[1137]	5523	// cross references
[1135]	5524	mVspTree.mOspTree = &ospTree;
[1137]	5525	mOspTree.mVspTree = &vspTree;
[1174]	5526
	5527	char subdivisionStatsLog[100];
[1189]	5528	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
	5529	subdivisionStatsLog);
[1174]	5530	mSubdivisionStats.open(subdivisionStatsLog);
[1135]	5531	}
	5532
	5533
	5534	SplitCandidate *HierarchyManager::NextSplitCandidate()
	5535	{
	5536	SplitCandidate *splitCandidate = mTQueue.Top();
	5537	mTQueue.Pop();
	5538
	5539	return splitCandidate;
	5540	}
	5541
	5542
[1145]	5543	VspTree::VspSplitCandidate *HierarchyManager::PrepareVsp(const VssRayContainer &sampleRays,
[1133]	5544	AxisAlignedBox3 *forcedViewSpace,
[1135]	5545	RayInfoContainer &rays)
[1121]	5546	{
[1135]	5547	// store pointer to this tree
	5548	VspTree::VspSplitCandidate::sVspTree = &mVspTree;
	5549	mVspTree.mVspStats.nodes = 1;
	5550
[1142]	5551	// compute view space bounding box
[1143]	5552	mVspTree.ComputeBoundingBox(sampleRays, forcedViewSpace);
[1089]	5553
[1143]	5554	// initialise termination criteria
[1135]	5555	mVspTree.mTermMinProbability *= mBoundingBox.GetVolume();
	5556	mVspTree.mGlobalCostMisses = 0;
[1121]	5557
[1143]	5558	// get clipped rays
[1176]	5559	mVspTree.PreprocessRays(sampleRays, rays);
[1135]	5560
[1181]	5561	const int pvsSize = mVspTree.EvalPvsSize(rays);
[1133]	5562
[1145]	5563	Debug << "pvs size: " << (int)pvsSize << endl;
	5564	Debug << "rays size: " << (int)rays.size() << endl;
[1089]	5565
[1143]	5566	//-- prepare view space partition
	5567
[1089]	5568	// add first candidate for view space partition
[1109]	5569	VspLeaf *leaf = new VspLeaf();
	5570	mVspTree.mRoot = leaf;
[1133]	5571
[1027]	5572	const float prop = mVspTree.mBoundingBox.GetVolume();
	5573
[1089]	5574	// first vsp traversal data
[1109]	5575	VspTree::VspTraversalData vData(leaf,
[1027]	5576	0,
	5577	&rays,
[1089]	5578	pvsSize,
[1027]	5579	prop,
	5580	mVspTree.mBoundingBox);
	5581
[1121]	5582	// create first view cell
[1143]	5583	mVspTree.CreateViewCell(vData, false);
[1121]	5584
[1178]	5585	#if WORK_WITH_VIEWCELL_PVS
	5586
[1121]	5587	// add first view cell to all the objects view cell pvs
	5588	ObjectPvsMap::const_iterator oit,
	5589	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
	5590
	5591
	5592	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
	5593	{
	5594	Intersectable obj = (oit).first;
	5595	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
	5596	}
[1174]	5597	#endif
[1121]	5598
[1027]	5599	// compute first split candidate
[1133]	5600	VspTree::VspSplitCandidate *splitCandidate =
	5601	new VspTree::VspSplitCandidate(vData);
[1099]	5602	mVspTree.EvalSplitCandidate(*splitCandidate);
[1027]	5603
[1174]	5604	mVspTree.mTotalCost = (float)pvsSize;
	5605	mVspTree.EvalSubdivisionStats(*splitCandidate);
	5606
[1133]	5607	return splitCandidate;
[1121]	5608	}
[1027]	5609
[1089]	5610
[1145]	5611	OspTree::OspSplitCandidate * HierarchyManager::PrepareOsp(const VssRayContainer &sampleRays,
[1174]	5612	const ObjectContainer &objects,
	5613	AxisAlignedBox3 *forcedObjectSpace,
	5614	RayInfoContainer &rays)
[1121]	5615	{
[1135]	5616	// store pointer to this tree
	5617	OspTree::OspSplitCandidate::sOspTree = &mOspTree;
	5618	mOspTree.mOspStats.nodes = 1;
	5619
[1144]	5620	// compute bounding box from objects
[1135]	5621	mOspTree.ComputeBoundingBox(objects, forcedObjectSpace);
	5622
	5623	mOspTree.mTermMinProbability *= mBoundingBox.GetVolume();
	5624	mGlobalCostMisses = 0;
	5625
[1179]	5626	// create new root
[1109]	5627	KdLeaf *kdleaf = new KdLeaf(NULL, 0);
	5628	kdleaf->mObjects = objects;
	5629	mOspTree.mRoot = kdleaf;
[1089]	5630
[1186]	5631	// get clipped rays
	5632	mOspTree.PreprocessRays(kdleaf, sampleRays, rays);
	5633
	5634
[1184]	5635	// probabilty is voume of all "seen" view cells
[1189]	5636	#if 1
[1181]	5637	const float prop = mOspTree.EvalViewCellsVolume(kdleaf, rays);
[1184]	5638	#else
	5639	const float prop = mVspTree.GetBoundingBox().GetVolume();
	5640	#endif
[1179]	5641
[1184]	5642	//-- add first candidate for object space partition
[1089]	5643
[1184]	5644	// create osp traversal data
[1109]	5645	OspTree::OspTraversalData oData(kdleaf,
[1089]	5646	0,
[1135]	5647	&rays,
[1189]	5648	0,//(int)objects.size(),
[1089]	5649	prop,
	5650	mOspTree.mBoundingBox);
	5651
	5652
[1184]	5653	// first split candidate
[1121]	5654	OspTree::OspSplitCandidate *oSplitCandidate =
	5655	new OspTree::OspSplitCandidate(oData);
[1144]	5656
[1189]	5657	mOspTree.UpdateViewCellsPvs(kdleaf, rays);
	5658
[1174]	5659	mOspTree.EvalSplitCandidate(*oSplitCandidate);
[1089]	5660
[1184]	5661	mOspTree.mTotalCost = (float)objects.size() * prop /
	5662	mVspTree.GetBoundingBox().GetVolume();
	5663
[1174]	5664	mOspTree.EvalSubdivisionStats(*oSplitCandidate);
	5665
[1133]	5666	return oSplitCandidate;
[1016]	5667	}
	5668
	5669
[1121]	5670	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
	5671	const ObjectContainer &objects,
	5672	AxisAlignedBox3 *forcedViewSpace,
[1135]	5673	RayInfoContainer &viewSpaceRays,
	5674	RayInfoContainer &objectSpaceRays)
[1121]	5675	{
[1135]	5676	SplitCandidate *vsc =
	5677	PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
	5678	mTQueue.Push(vsc);
	5679
	5680	SplitCandidate *osc =
	5681	PrepareOsp(sampleRays, objects, forcedViewSpace, objectSpaceRays);
	5682
	5683	mTQueue.Push(osc);
[1121]	5684	}
	5685
	5686
[1174]	5687	void HierarchyManager::EvalSubdivisionStats(const SplitCandidate &tData)
	5688	{
	5689	const float costDecr = tData.GetRenderCostDecrease();
	5690
	5691	//mTotalCost -= costDecr;
	5692	// mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
	5693
	5694	AddSubdivisionStats(mOspTree.mOspStats.Leaves() + mVspTree.mVspStats.Leaves(),
	5695	costDecr,
	5696	mTotalCost
	5697	);
	5698	}
	5699
	5700
	5701	void HierarchyManager::AddSubdivisionStats(const int splits,
	5702	const float renderCostDecr,
	5703	const float totalRenderCost)
	5704	{
	5705	mSubdivisionStats
	5706	<< "#Splits\n" << splits << endl
	5707	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	5708	<< "#TotalRenderCost\n" << totalRenderCost << endl;
	5709	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
	5710	}
	5711
	5712
[1020]	5713	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
[1016]	5714	{
[1108]	5715	// TODO matt: make virtual by creating superclasss for traveral data
	5716	return candidate->GlobalTerminationCriteriaMet();
[1016]	5717	}
	5718
	5719
[1143]	5720	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
	5721	const ObjectContainer &objects,
	5722	AxisAlignedBox3 *forcedViewSpace)
	5723	{
	5724	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
	5725	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	5726
	5727	// prepare vsp and osp trees for traversal
	5728	PrepareConstruction(sampleRays, objects, forcedViewSpace, viewSpaceRays, objectSpaceRays);
	5729
	5730	mVspTree.mVspStats.Reset();
	5731	mVspTree.mVspStats.Start();
	5732
	5733	cout << "Constructing view space / object space tree ... \n";
	5734	const long startTime = GetTime();
	5735
[1145]	5736	RunConstruction(true);
	5737
	5738	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	5739
	5740	mVspTree.mVspStats.Stop();
	5741	}
	5742
	5743
	5744	bool HierarchyManager::SubdivideSplitCandidate(SplitCandidate *sc)
	5745	{
	5746	const bool globalTerminationCriteriaMet =
	5747	GlobalTerminationCriteriaMet(sc);
	5748
	5749	const bool vspSplit = (sc->Type() == SplitCandidate::VIEW_SPACE);
	5750
	5751	if (vspSplit)
	5752	{
[1174]	5753	VspNode *n = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1145]	5754	}
	5755	else
	5756	{
[1174]	5757	KdNode *n = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1145]	5758	}
[1174]	5759
	5760	return !globalTerminationCriteriaMet;
[1145]	5761	}
	5762
	5763
	5764	void HierarchyManager::RunConstruction(const bool repair)
	5765	{
	5766	int numNodes = 0;
	5767
[1143]	5768	while (!FinishedConstruction())
	5769	{
[1145]	5770	SplitCandidate *splitCandidate = NextSplitCandidate();
	5771
	5772	mTotalCost -= splitCandidate->GetRenderCostDecrease();
[1181]	5773
[1143]	5774	// cost ratio of cost decrease / totalCost
[1145]	5775	const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
[1174]	5776
	5777	if (costRatio < mTermMinGlobalCostRatio)
	5778	++ mGlobalCostMisses;
[1181]	5779
[1184]	5780	/Debug << "\n*********" << endl
[1145]	5781	<< "total cost: " << mTotalCost << " render cost decr: "
	5782	<< splitCandidate->GetRenderCostDecrease()
[1184]	5783	<< " cost ratio: " << costRatio << endl << endl;*/
[1181]	5784
[1168]	5785	//-- subdivide leaf node
[1178]	5786
[1174]	5787	if (SubdivideSplitCandidate(splitCandidate))
	5788	{
[1178]	5789	// subdivision successful
[1174]	5790	EvalSubdivisionStats(*splitCandidate);
	5791
	5792	// reevaluate candidates affected by the split
	5793	// for view space splits, this would be object space splits
	5794	// and other way round
	5795	if (repair)
	5796	RepairQueue();
[1178]	5797
	5798	cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
[1174]	5799	}
[1168]	5800
[1145]	5801	DEL_PTR(splitCandidate);
[1143]	5802	}
	5803	}
	5804
	5805
[1101]	5806	void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
[1106]	5807	const ObjectContainer &objects,
	5808	AxisAlignedBox3 *forcedViewSpace)
[1101]	5809	{
[1178]	5810	// rays clipped in view space and in object space
[1135]	5811	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	5812	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
[1123]	5813
[1145]	5814
[1143]	5815	/////////////////////////////////////////////////////////////
	5816	// view space space partition
	5817	/////////////////////////////////////////////////////////////
	5818
[1176]	5819	#if 0
[1123]	5820	// makes no sense otherwise because only one kd cell available
	5821	// during view space partition
[1141]	5822	const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
	5823	const bool savedStoreMethod = mVspTree.mStoreKdPvs;
	5824
	5825	mVspTree.mUseKdPvsForHeuristics = false;
	5826	mVspTree.mStoreKdPvs = false;
[1176]	5827	#endif
[1123]	5828
[1145]	5829	VspTree::VspSplitCandidate *vsc =
	5830	PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
[1174]	5831
[1145]	5832	// add to queue
	5833	mTQueue.Push(vsc);
[1101]	5834
	5835	long startTime = GetTime();
[1121]	5836	cout << "starting vsp contruction ... " << endl;
[1143]	5837
	5838	mVspTree.mVspStats.Reset();
	5839	mVspTree.mVspStats.Start();
	5840
[1101]	5841	int i = 0;
	5842
[1145]	5843	// all objects can be seen from everywhere
	5844	mTotalCost = (float)vsc->mParentData.mPvs;
[1101]	5845
[1145]	5846	const bool repairQueue = false;
[1101]	5847
[1145]	5848	// process view space candidates
	5849	RunConstruction(repairQueue);
[1101]	5850
[1145]	5851	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	5852	mVspTree.mVspStats.Stop();
[1121]	5853
	5854
[1101]	5855
[1142]	5856	/////////////////////////////////////////////////////////////
[1143]	5857	// object space partition
	5858	/////////////////////////////////////////////////////////////
[1142]	5859
[1189]	5860
[1145]	5861	Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
[1144]	5862	cout << "starting osp contruction ... " << endl;
[1142]	5863
[1184]	5864	// start with one big kd cell - all objects can be seen from everywhere
	5865	// note: only true for view space = object space
	5866
[1145]	5867	// compute first candidate
	5868	OspTree::OspSplitCandidate *osc =
[1135]	5869	PrepareOsp(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
[1101]	5870
[1184]	5871	Debug << "reseting cost, new total cost: " << mTotalCost << endl;
	5872	mTotalCost = mOspTree.mTotalCost;
	5873
[1135]	5874	mTQueue.Push(osc);
	5875
[1145]	5876	mOspTree.mOspStats.Reset();
	5877	mOspTree.mOspStats.Start();
[1135]	5878
[1145]	5879	startTime = GetTime();
[1174]	5880
[1145]	5881	// process object space candidates
	5882	RunConstruction(repairQueue);
	5883
	5884	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1101]	5885
[1145]	5886	mOspTree.mOspStats.Stop();
[1101]	5887
[1186]	5888	float rc = mOspTree.EvalRenderCost(sampleRays);
[1184]	5889
[1189]	5890	Debug << "here47 My render cost evalulation: " << rc << endl;
[1184]	5891
[1176]	5892	#if 0
[1145]	5893	// reset parameters
[1141]	5894	mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
	5895	mVspTree.mStoreKdPvs = savedStoreMethod;
[1176]	5896	#endif
[1101]	5897	}
	5898
	5899
[1142]	5900	void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
	5901	const ObjectContainer &objects,
	5902	AxisAlignedBox3 *forcedViewSpace)
	5903	{
[1145]	5904	// only view space partition
	5905	// object kd tree is taken for osp
	5906
[1143]	5907	mVspTree.mVspStats.Reset();
	5908	mVspTree.mVspStats.Start();
[1142]	5909
[1143]	5910	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	5911
[1142]	5912	SplitCandidate sc = PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
	5913	mTQueue.Push(sc);
	5914
	5915	cout << "starting vsp contruction ... " << endl;
	5916
	5917	long startTime = GetTime();
	5918
[1145]	5919	RunConstruction(false);
[1142]	5920
	5921	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	5922	mVspTree.mVspStats.Stop();
	5923	}
	5924
	5925
[1145]	5926	bool HierarchyManager::FinishedConstruction() const
[1020]	5927	{
[1099]	5928	return mTQueue.Empty();
[1020]	5929	}
	5930
	5931
[1121]	5932	void HierarchyManager::CollectDirtyCandidates(vector<SplitCandidate *> &dirtyList)
	5933	{
	5934	// we have either a object space or view space split
	5935	if (mCurrentCandidate->Type() == SplitCandidate::VIEW_SPACE)
	5936	{
	5937	VspTree::VspSplitCandidate *sc =
	5938	dynamic_cast<VspTree::VspSplitCandidate *>(mCurrentCandidate);
	5939
	5940	mVspTree.CollectDirtyCandidates(sc, dirtyList);
	5941	}
	5942	else // object space split
	5943	{
	5944	OspTree::OspSplitCandidate *sc =
	5945	dynamic_cast<OspTree::OspSplitCandidate *>(mCurrentCandidate);
	5946
	5947	mOspTree.CollectDirtyCandidates(sc, dirtyList);
	5948	}
	5949	}
	5950
	5951
	5952	void HierarchyManager::RepairQueue()
[1093]	5953	{
	5954	// TODO
	5955	// for each update of the view space partition:
	5956	// the candidates from object space partition which
	5957	// have been afected by the view space split (the kd split candidates
	5958	// which saw the view cell which was split) must be reevaluated
	5959	// (maybe not locally, just reinsert them into the queue)
	5960	//
	5961	// vice versa for the view cells
	5962	// for each update of the object space partition
	5963	// reevaluate split candidate for view cells which saw the split kd cell
	5964	//
	5965	// the priority queue update can be solved by implementing a binary heap
	5966	// (explicit data structure, binary tree)
	5967	// *) inserting and removal is efficient
[1099]	5968	// *) search is not efficient => store queue position with each
[1093]	5969	// split candidate
	5970
[1121]	5971	// collect list of "dirty" candidates
	5972	vector<SplitCandidate *> dirtyList;
	5973	CollectDirtyCandidates(dirtyList);
	5974
	5975	//-- reevaluate the dirty list
[1099]	5976	vector<SplitCandidate *>::const_iterator sit, sit_end = dirtyList.end();
[1093]	5977
[1099]	5978	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
[1093]	5979	{
[1099]	5980	SplitCandidate* sc = *sit;
[1093]	5981
[1099]	5982	mTQueue.Erase(sc);
[1093]	5983
[1099]	5984	// reevaluate
	5985	sc->EvalPriority();
[1093]	5986
[1099]	5987	// reinsert
	5988	mTQueue.Push(sc);
	5989	}
[1093]	5990	}
	5991
[1002]	5992	}

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

Download in other formats: