Context Navigation

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

Revision 1233, 146.3 KB checked in by mattausch, 18 years ago (diff)

Rev	Line
[1002]	1	#include <stack>
	2	#include <time.h>
	3	#include <iomanip>
	4
[1010]	5	#include "ViewCell.h"
[1002]	6	#include "Plane3.h"
[1006]	7	#include "VspOspTree.h"
[1002]	8	#include "Mesh.h"
	9	#include "common.h"
	10	#include "Environment.h"
	11	#include "Polygon3.h"
	12	#include "Ray.h"
	13	#include "AxisAlignedBox3.h"
	14	#include "Exporter.h"
	15	#include "Plane3.h"
	16	#include "ViewCellsManager.h"
	17	#include "Beam.h"
[1020]	18	#include "KdTree.h"
[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
[1221]	583	inline 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
[1221]	608	inline 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();
[1233]	2883	dirtyList.push_back(leaf->mSubdivisionCandidate);
[1121]	2884	}
[1138]	2885
	2886	leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
	2887
	2888	if (!leaf->Mailed())
	2889	{
	2890	leaf->Mail();
[1233]	2891	dirtyList.push_back(leaf->mSubdivisionCandidate);
[1138]	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
[1221]	2933	void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
[1137]	2934	{
[1221]	2935	/*mViewCellsManager->ComputeSampleContribution(ray, false, true);
[1186]	2936	viewCells = ray.mViewCells;
	2937	ray.mViewCells.clear();
[1221]	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
[1221]	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
[1221]	3370	inline bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
[1021]	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
[1221]	3381	inline bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
[1021]	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;
[1221]	3539	//Debug << "here29 : " << minRenderCost / viewSpaceVol << endl;
[1193]	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;
[1221]	3679	mVspTree->GetViewCells(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
[1221]	3800	void OspTree::EvalRayContribution(KdLeaf *leaf, const VssRay &ray, float &renderCost)
[1106]	3801	{
[1137]	3802	ViewCellContainer viewCells;
[1106]	3803
[1221]	3804	mVspTree->GetViewCells(ray, viewCells);
[1106]	3805
[1193]	3806	// classify view cells and compute volume contri accordingly
	3807	// possible view cell classifications:
	3808	// view cell mailed => view cell can be seen from left child node
	3809	// view cell counter > 0 view cell can be seen from right child node
	3810	// combined: view cell volume belongs to both nodes
[1137]	3811	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1145]	3812
[1137]	3813	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	3814	{
[1189]	3815	EvalViewCellContribution(leaf, *vit, renderCost);
	3816	}
	3817	}
[1137]	3818
[1176]	3819
[1189]	3820	void OspTree::EvalViewCellContribution(KdLeaf *leaf,
	3821	ViewCell *viewCell,
	3822	float &renderCost)
	3823	{
[1193]	3824	//Debug << "**************" << endl;
	3825	//Debug << "vc contri: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " " << viewCell->mMailbox - ViewCell::sMailId << " counter: " << viewCell->mCounter << endl;
	3826
[1189]	3827	const float vol = viewCell->GetVolume();
[1145]	3828
[1189]	3829	if (viewCell->Mailed())
	3830	{
[1193]	3831	viewCell->Mail(2); // view cell can be seen from both nodes
[1178]	3832
[1189]	3833	// we now see view cell from both nodes => add contri
	3834	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3835
	3836	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	3837	{
	3838	Intersectable obj = oit;
	3839
	3840	// was render cost already added?
[1193]	3841	if (!ViewCellHasMultipleReferences(obj, viewCell, false) &&
[1189]	3842	obj->Mailed(1))
	3843	{
[1193]	3844	//Debug << "obj mail 1!! " << vol / mVspTree->GetBoundingBox().GetVolume() << endl;
	3845	renderCost += vol;
[1189]	3846	}
[1137]	3847	}
[1189]	3848	}
[1137]	3849
[1189]	3850	if (-- viewCell->mCounter == 0)
	3851	{
[1193]	3852	viewCell->Mail(1); // view cell can be seen from back node only
[1189]	3853
	3854	//MailablePvsData::NewMail();
	3855	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	3856
	3857	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
[1137]	3858	{
[1189]	3859	Intersectable obj = oit;
	3860
	3861	// can render cost be be reduced?
[1193]	3862	if (!ViewCellHasMultipleReferences(obj, viewCell, false) && obj->Mailed())
[1189]	3863	{
[1193]	3864	renderCost -= vol;
[1189]	3865	}
[1137]	3866	}
	3867	}
[1193]	3868	//Debug << "new rc: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " counter2: " << viewCell->mCounter << endl;
	3869	//Debug << "**************"<<endl;
[1106]	3870	}
	3871
	3872
[1189]	3873	void OspTree::EvalHeuristicsContribution(KdLeaf *leaf,
	3874	const SortableEntry &ci,
	3875	float &renderCost,
	3876	ViewCellContainer &touchedViewCells)
	3877	{
	3878	Intersectable *obj = ci.mObject;
	3879	VssRay *ray = ci.mRay;
	3880
	3881	// switch between different types of events
	3882	switch (ci.mType)
	3883	{
	3884	case SortableEntry::BOX_MIN:
	3885	cout << "<";
	3886	AddObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
	3887	break;
	3888
	3889	case SortableEntry::BOX_MAX:
	3890	cout << ">";
	3891	SubtractObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
	3892	break;
	3893
	3894	// compute volume contribution from view cells
	3895	case SortableEntry::BOX_INTERSECT:
	3896	cout << "i";
	3897	// process ray if the hit point with termination / origin object
	3898	// is inside this kd leaf
	3899	EvalRayContribution(leaf, *ray, renderCost);
	3900	break;
	3901
	3902	default:
	3903	cout << "should not come here" << endl;
	3904	break;
	3905	}
	3906
	3907	//cout << "vol left: " << volLeft << " vol right " << volRight << endl;
	3908	}
	3909
	3910
[1137]	3911	void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
[1077]	3912	{
[1137]	3913	mViewCellsManager = vcm;
[1077]	3914	}
	3915
	3916
[1137]	3917	AxisAlignedBox3 OspTree::GetBoundingBox() const
[1077]	3918	{
[1137]	3919	return mBoundingBox;
[1077]	3920	}
	3921
	3922
[1089]	3923	float OspTree::SelectSplitPlane(const OspTraversalData &tData,
[1084]	3924	AxisAlignedPlane &plane,
	3925	float &pFront,
	3926	float &pBack)
	3927	{
	3928	float nPosition[3];
	3929	float nCostRatio[3];
	3930	float nProbFront[3];
	3931	float nProbBack[3];
	3932
	3933	// create bounding box of node geometry
	3934	AxisAlignedBox3 box = tData.mBoundingBox;
	3935
	3936	int sAxis = 0;
	3937	int bestAxis = -1;
	3938
	3939	if (mOnlyDrivingAxis)
	3940	{
	3941	sAxis = box.Size().DrivingAxis();
	3942	}
[1178]	3943
[1084]	3944
[1106]	3945	// -- evaluate split cost for all three axis
[1084]	3946	for (int axis = 0; axis < 3; ++ axis)
	3947	{
	3948	if (!mOnlyDrivingAxis \|\| (axis == sAxis))
	3949	{
[1106]	3950	if (1 \|\| mUseCostHeuristics)
	3951	{
	3952	//-- place split plane using heuristics
	3953	int objectsFront, objectsBack;
[1084]	3954
	3955	nCostRatio[axis] =
[1137]	3956	EvalLocalCostHeuristics(tData,
[1106]	3957	tData.mBoundingBox,
	3958	axis,
	3959	nPosition[axis],
	3960	objectsFront,
	3961	objectsBack);
[1084]	3962	}
[1106]	3963	/* else
[1084]	3964	{
[1106]	3965	//-- split plane position is spatial median
	3966
[1084]	3967	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	3968
	3969	nCostRatio[axis] = EvalLocalSplitCost(tData,
	3970	box,
	3971	axis,
	3972	nPosition[axis],
	3973	nProbFront[axis],
	3974	nProbBack[axis]);
[1106]	3975	}*/
[1084]	3976
	3977	if (bestAxis == -1)
	3978	{
	3979	bestAxis = axis;
	3980	}
	3981	else if (nCostRatio[axis] < nCostRatio[bestAxis])
	3982	{
	3983	bestAxis = axis;
	3984	}
	3985	}
	3986	}
	3987
	3988	//-- assign values
[1106]	3989
[1084]	3990	plane.mAxis = bestAxis;
	3991	// split plane position
	3992	plane.mPosition = nPosition[bestAxis];
	3993
[1221]	3994	//pFront = nProbFront[bestAxis];
	3995	//pBack = nProbBack[bestAxis];
[1084]	3996
[1145]	3997	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1084]	3998	return nCostRatio[bestAxis];
	3999	}
	4000
	4001
[1145]	4002	bool OspTree::EndPointInsideNode(KdLeaf *leaf,
	4003	VssRay &ray,
	4004	bool isTermination) const
[1089]	4005	{
[1145]	4006	// test if the leaf where the hitpoint is located is the current leaf
	4007	if (isTermination)
	4008	{
[1184]	4009	return ray.mTerminationObject && (GetLeaf(ray.mTermination, ray.mTerminationNode) == leaf);
[1145]	4010	}
	4011	else
	4012	{
[1189]	4013	return false; // no origin object!
	4014	return ray.mOriginObject && (GetLeaf(ray.mOrigin, ray.mOriginNode) == leaf);
[1145]	4015	}
	4016	}
	4017
	4018
[1174]	4019	void OspTree::EvalSubdivisionStats(const SplitCandidate &sc)
[1145]	4020	{
[1174]	4021	const float costDecr = sc.GetRenderCostDecrease();
[1176]	4022
[1174]	4023	AddSubdivisionStats(mOspStats.Leaves(),
	4024	costDecr,
	4025	mTotalCost
	4026	);
	4027	}
[1145]	4028
	4029
[1174]	4030	void OspTree::AddSubdivisionStats(const int leaves,
	4031	const float renderCostDecr,
	4032	const float totalRenderCost)
[1176]	4033	{
[1174]	4034	mSubdivisionStats
	4035	<< "#Leaves\n" << leaves << endl
	4036	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	4037	<< "#TotalRenderCost\n" << totalRenderCost << endl;
	4038	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
[1145]	4039	}
[1089]	4040
[1145]	4041
	4042	int OspTree::ClassifyRay(VssRay *ray,
	4043	KdLeaf *leaf,
	4044	const AxisAlignedPlane &plane) const
	4045	{
	4046	const bool originInside = EndPointInsideNode(leaf, *ray, false);
	4047	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
	4048
[1189]	4049	const bool originGt = (ray->mOrigin[plane.mAxis] >= plane.mPosition);
	4050	const bool originLt = (ray->mOrigin[plane.mAxis] <= plane.mPosition);
[1145]	4051
[1189]	4052	const bool terminationGt = (ray->mTermination[plane.mAxis] >= plane.mPosition);
	4053	const bool terminationLt = (ray->mTermination[plane.mAxis] <= plane.mPosition);
	4054
[1145]	4055	// add view cell volume to front volume
[1189]	4056	const bool addToFront =
	4057	((originInside && originGt) \|\| (terminationInside && terminationGt));
[1145]	4058
	4059	// add view cell volume to back volume
[1189]	4060	const bool addToBack =
	4061	((originInside && originLt/!originGt/) \|\| (terminationInside && terminationLt/terminationGt/));
[1145]	4062
	4063	// classify ray with respect to the child nodes the view cells contribute
	4064	if (addToFront && addToBack)
	4065	return 0;
	4066	else if (addToBack)
	4067	return -1;
	4068	else if (addToFront)
	4069	return 1;
	4070
	4071	return -2;
	4072	}
	4073
	4074
[1186]	4075	int OspTree::ClassifyRays(const RayInfoContainer &rays,
	4076	KdLeaf *leaf,
	4077	const AxisAlignedPlane &plane,
	4078	RayInfoContainer &frontRays,
	4079	RayInfoContainer &backRays) const
	4080	{
	4081	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4082
	4083	for (rit = rays.begin(); rit < rit_end; ++ rit)
	4084	{
	4085	VssRay ray = (rit).mRay;
	4086
	4087	bool originGt = false;
	4088	bool terminationGt = false;
	4089
	4090	Intersectable *obj = ray->mOriginObject;
	4091
[1189]	4092	if (0 && obj)
[1186]	4093	{
[1189]	4094	originGt = ray->mOrigin[plane.mAxis] >= plane.mPosition;
[1186]	4095	}
	4096
	4097	obj = ray->mTerminationObject;
	4098
	4099	if (obj)
	4100	{
[1189]	4101	terminationGt = ray->mTermination[plane.mAxis] >= plane.mPosition;
[1186]	4102	}
	4103
	4104	// either begin or end point on front side
	4105	const bool addToFront = originGt \|\| terminationGt;
	4106
	4107	// add view cell volume to back volume
	4108	const bool addToBack = !originGt \|\| !terminationGt;
	4109
	4110	// classify ray with respect to the child nodes the view cells contribute
	4111	if (addToFront)
	4112	frontRays.push_back(*rit);
	4113	if (addToBack)
	4114	backRays.push_back(*rit);
	4115	}
	4116
	4117	return 0;
	4118	}
	4119
	4120
[1189]	4121	#if 0
[1186]	4122
[1145]	4123	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	4124	const OspTraversalData &tData,
	4125	float &normalizedOldRenderCost) const
	4126	{
[1089]	4127	float pvsFront = 0;
	4128	float pvsBack = 0;
	4129
	4130	// probability that view point lies in back / front node
[1138]	4131	float pOverall = 0;//data.mProbability; // todo matt§: value ok?
[1089]	4132	float pFront = 0;
	4133	float pBack = 0;
[1176]	4134	float pFrontAndBack = 0;
[1089]	4135
[1145]	4136	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
	4137
[1184]	4138	Intersectable::NewMail(3);
	4139
[1138]	4140	KdLeaf *leaf = tData.mNode;
[1181]	4141	const int totalPvs = (int)leaf->mObjects.size();
	4142
[1186]	4143	RayInfoContainer frontRays, backRays;
	4144	ClassifyRays(*tData.mRays, leaf, candidatePlane, frontRays, backRays);
[1089]	4145
[1186]	4146	ViewCellContainer touchedViewCells;
[1184]	4147
[1145]	4148	// sum up volume seen from the objects of left and right children
	4149	// => the volume is the weight for the render cost equation
	4150	ViewCell::NewMail(3);
[1176]	4151
[1137]	4152	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	4153
	4154	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
	4155	{
	4156	VssRay ray = (rit).mRay;
	4157
[1189]	4158	// add volume to volumes of left and / or right children
	4159	// if one of the ray end points is inside
	4160	const int classification = ClassifyRay(ray, leaf, candidatePlane);
[1145]	4161
[1189]	4162	ViewCellContainer viewCells;
	4163	mVspTree->GetViewCells(*ray, viewCells);
[1138]	4164
[1189]	4165	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
[1138]	4166
[1189]	4167	// traverse through view cells and classify them according
	4168	// to them being seen from to back / front / front and back node
	4169	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4170	{
	4171	ViewCell vc = vit;
[1176]	4172
[1189]	4173	// if not previously mailed
	4174	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
	4175	{
	4176	touchedViewCells.push_back(vc);
[1137]	4177	}
[1189]	4178
	4179	// classify / mail the view cell
	4180	MailViewCell(vc, classification);
[1137]	4181	}
	4182	}
	4183
[1184]	4184	// evaluate view cells volume contribution
	4185	// with respect to the mail box classification
	4186	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
[1181]	4187
[1184]	4188	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
[1176]	4189	{
	4190	AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
	4191	}
	4192
[1184]	4193	//////////////////////////////////////////////
	4194	//
	4195	// evaluate contribution of objects which are part of other kd nodes
	4196	// which are seen by the same view cell
	4197	// These contributions cannot be reduced by splitting, because
	4198	// the object would still be part of the pvs
[1181]	4199
[1184]	4200	float additionalFrontRenderCost = 0;
	4201	float additionalBackRenderCost = 0;
	4202
[1189]	4203	MailablePvsData::NewMail();
[1184]	4204
[1186]	4205	for (rit = tData.mRays->begin(); rit != tData.mRays->end(); ++ rit)
[1184]	4206	{
	4207	VssRay ray = (rit).mRay;
	4208
	4209	ViewCellContainer viewCells;
	4210	mVspTree->GetViewCells(*ray, viewCells);
	4211
	4212	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	4213
	4214	// traverse through view cells
	4215	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4216	{
	4217	ViewCell viewCell = vit;
	4218
	4219	// for a view cell:
	4220	// if object is also in the kd pvs entries from other kd leaves,
	4221	// render cost cannot be reduced for this view cell
	4222	// => the render cost was falsly reduced, add them again
	4223
[1186]	4224	if (ray->mTerminationObject)
[1184]	4225	{
	4226	Intersectable *obj = ray->mTerminationObject;
	4227
	4228	const bool renderCostWrong =
	4229	ViewCellHasMultipleReferences(obj, viewCell, true);
[1186]	4230
[1184]	4231	// if there is already an entry of this object in the view cell pvs
	4232	if (renderCostWrong)
	4233	{
	4234	// view cell was counted only for front or back => correct tjos
	4235	if (viewCell->Mailed(1) && obj->Mailed())
[1186]	4236	{
[1184]	4237	additionalFrontRenderCost += viewCell->GetVolume();
[1186]	4238	}
[1184]	4239	else if (viewCell->Mailed() && obj->Mailed(1))
[1186]	4240	{
[1184]	4241	additionalBackRenderCost += viewCell->GetVolume();
[1186]	4242	}
[1184]	4243	}
	4244	}
	4245
[1186]	4246	if (ray->mOriginObject)
[1184]	4247	{
	4248	Intersectable *obj = ray->mOriginObject;
	4249
	4250	const bool renderCostWrong =
	4251	ViewCellHasMultipleReferences(obj, viewCell, true);
	4252	// if there is already an entry of this object in the view cell pvs
	4253	if (renderCostWrong)
	4254	{
	4255	if (viewCell->Mailed(1) && obj->Mailed())
[1186]	4256	{
[1184]	4257	additionalFrontRenderCost += viewCell->GetVolume();
[1186]	4258	}
[1184]	4259	else if (viewCell->Mailed() && obj->Mailed(1))
[1186]	4260	{
[1184]	4261	additionalBackRenderCost += viewCell->GetVolume();
[1186]	4262	}
[1184]	4263	}
	4264	}
	4265	}
	4266	}
	4267
	4268	/////////////////////////////
	4269
	4270
[1178]	4271	// these are non-overlapping sets
	4272	pOverall = pFront + pBack + pFrontAndBack;
[1176]	4273
[1181]	4274
[1089]	4275	//-- pvs rendering heuristics
[1181]	4276
[1138]	4277	const float oldRenderCost = pOverall * totalPvs;
[1181]	4278
	4279	// sum up the terms:
	4280	// the view cells seeing
	4281	// a) the left node are weighted by the #left node objects
	4282	// b) the right node are weighted by the #right node objects
	4283	// c) both nodes are weighted by the #parent node objects
[1184]	4284	const float newRenderCost = pvsFront * pFront + pvsBack * pBack + totalPvs * pFrontAndBack
	4285	+ additionalFrontRenderCost + additionalBackRenderCost;
[1089]	4286
[1145]	4287	// normalize volume with view space volume
	4288	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
[1089]	4289
[1176]	4290	Debug << "\n(((( eval render cost decrease ))))" << endl
[1145]	4291	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
[1176]	4292	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
[1181]	4293	<< " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << tData.mProbability / viewSpaceVol << endl
[1145]	4294	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
[1184]	4295	<< "render cost decrease: " << renderCostDecrease << endl
	4296	<< "additional front " << additionalFrontRenderCost / viewSpaceVol
	4297	<< " additional back " << additionalBackRenderCost / viewSpaceVol << endl;
	4298
	4299	if (oldRenderCost < newRenderCost * 0.99)
	4300	Debug <<"error!!"<<endl;
	4301
[1181]	4302	//if ((((pOverall - tData.mProbability) / viewSpaceVol) > 0.00001))
	4303	// Debug << "ERROR!!"<<endl;
[1089]	4304
[1145]	4305	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
	4306
[1181]	4307
[1145]	4308	return renderCostDecrease;
[1089]	4309	}
	4310
[1186]	4311	#else
[1089]	4312
[1186]	4313	float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	4314	const OspTraversalData &tData,
	4315	float &normalizedOldRenderCost) const
	4316	{
	4317	float pvsFront = 0;
	4318	float pvsBack = 0;
	4319
	4320	// probability that view point lies in back / front node
	4321	float pOverall = 0;//data.mProbability; // todo matt§: value ok?
	4322	float pFront = 0;
	4323	float pBack = 0;
	4324	float pFrontAndBack = 0;
	4325
	4326	Intersectable::NewMail(3);
	4327	KdLeaf *leaf = tData.mNode;
[1189]	4328
	4329	const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
[1186]	4330	const int totalPvs = (int)leaf->mObjects.size();
	4331
	4332	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	4333
	4334	// evaluate reverse pvs and view cell volume on left and right cell
	4335	// note: should I take all leaf objects or rather the objects hit by rays?
	4336	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	4337	{
	4338	int pvsContri = 0;
	4339
	4340	Intersectable obj = oit;
	4341	const AxisAlignedBox3 box = obj->GetBox();
	4342
	4343	// test if box falls in left / right child node
	4344	if (box.Max(candidatePlane.mAxis) >= candidatePlane.mPosition)
	4345	{
	4346	++ pvsFront;
	4347	obj->Mail();
	4348	}
	4349
	4350	if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
	4351	{
	4352	++ pvsBack;
	4353
	4354	if (obj->Mailed())
	4355	obj->Mail(2);
	4356	else
	4357	obj->Mail(1);
	4358	}
	4359	}
	4360
	4361
	4362	ViewCellContainer touchedViewCells;
	4363
	4364	// sum up volume seen from the objects of left and right children
	4365	// => the volume is the weight for the render cost equation
	4366	ViewCell::NewMail(3);
	4367
	4368	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	4369	//map<Intersectable *, ViewCellContainer> objectsMap;
	4370
	4371	for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
	4372	{
	4373	VssRay ray = (rit).mRay;
	4374
	4375	// add volume to volumes of left and / or right children
	4376	// if one of the ray end points is inside
	4377	const int classification = ClassifyRay(ray, leaf, candidatePlane);
	4378
	4379	ViewCellContainer viewCells;
	4380	mVspTree->GetViewCells(*ray, viewCells);
	4381
	4382	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	4383
	4384	// traverse through view cells and classify them according
	4385	// to them being seen from to back / front / front and back node
	4386	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4387	{
	4388	ViewCell vc = vit;
	4389
	4390	// if not previously mailed
	4391	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
	4392	{
	4393	touchedViewCells.push_back(vc);
	4394	}
	4395
	4396	// classify / mail the view cell
[1189]	4397	MailViewCell(vc, classification);
[1186]	4398	}
	4399	}
	4400
	4401	// evaluate view cells volume contribution
	4402	// with respect to the mail box classification
	4403	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	4404
	4405	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	4406	{
	4407	AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
	4408	}
	4409
	4410	//////////////////////////////////////////////
	4411	//
	4412	// evaluate contribution of objects which are part of other kd nodes
	4413	// which are seen by the same view cell
	4414	// These contributions cannot be reduced by splitting, because
	4415	// the object would still be part of the pvs
	4416
[1189]	4417	float newRc = 0;
[1186]	4418	float rc = 0;
	4419
[1189]	4420	MailablePvsData::NewMail();
	4421	//ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1186]	4422
	4423	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	4424	{
	4425	Intersectable obj = oit;
	4426	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	4427
	4428	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	4429	{
	4430	ViewCell vc = vit;
[1189]	4431
	4432	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1186]	4433
	4434	if (!vdata)
	4435	{
[1189]	4436	Debug << "here86 error!!"<<endl;
	4437	continue;
	4438	}
[1186]	4439
[1189]	4440	if (!vdata->Mailed())
[1186]	4441	{
	4442	vdata->Mail();
[1189]	4443	rc += vc->GetVolume();
	4444
	4445	if ((vdata->mSumPdf > 1.5) \|\|
	4446	vc->Mailed(2) \|\|
	4447	obj->Mailed(2) \|\|
	4448	(obj->Mailed() && vc->Mailed()) \|\|
	4449	(obj->Mailed(1) && vc->Mailed(1))
	4450	)
	4451	{
	4452	newRc += vc->GetVolume();
	4453	}
[1186]	4454	}
	4455	}
	4456	}
	4457
	4458
	4459	/////////////////////////////
	4460
	4461
	4462	// these are non-overlapping sets
	4463	pOverall = pFront + pBack + pFrontAndBack;
	4464
	4465
	4466	//-- pvs rendering heuristics
	4467
[1189]	4468	const float oldRenderCost = rc;//pOverall * totalPvs;
[1186]	4469
	4470	// sum up the terms:
	4471	// the view cells seeing
	4472	// a) the left node are weighted by the #left node objects
	4473	// b) the right node are weighted by the #right node objects
	4474	// c) both nodes are weighted by the #parent node objects
[1189]	4475	const float newRenderCost = newRc//pvsFront * pFront + pvsBack * pBack + totalPvs * pFrontAndBack
	4476	;// + additionalFrontRenderCost + additionalBackRenderCost;
[1186]	4477
	4478	// normalize volume with view space volume
	4479	const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
	4480
	4481	Debug << "\n(((( eval render cost decrease ))))" << endl
	4482	<< "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
	4483	<< "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol
	4484	<< " front and back p " << pFrontAndBack / viewSpaceVol << " p: " << tData.mProbability / viewSpaceVol << endl
	4485	<< "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
[1189]	4486	<< "render cost decrease: " << renderCostDecrease << endl;
	4487	//<< "additional front " << additionalFrontRenderCost / viewSpaceVol
	4488	//<< " additional back " << additionalBackRenderCost / viewSpaceVol << endl;
[1186]	4489
	4490	if (oldRenderCost < newRenderCost * 0.99)
	4491	Debug <<"error!!"<<endl;
	4492
	4493	//if ((((pOverall - tData.mProbability) / viewSpaceVol) > 0.00001))
	4494	// Debug << "ERROR!!"<<endl;
	4495
	4496	normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
	4497
	4498
	4499	return renderCostDecrease;
	4500	}
	4501	#endif
	4502
[1189]	4503
[1135]	4504	void OspTree::ComputeBoundingBox(const ObjectContainer &objects,
	4505	AxisAlignedBox3 *forcedBoundingBox)
[1089]	4506	{
	4507	if (forcedBoundingBox)
	4508	{
	4509	mBoundingBox = *forcedBoundingBox;
	4510	}
	4511	else // compute vsp tree bounding box
	4512	{
	4513	mBoundingBox.Initialize();
	4514
	4515	ObjectContainer::const_iterator oit, oit_end = objects.end();
	4516
	4517	//-- compute bounding box
	4518	for (oit = objects.begin(); oit != oit_end; ++ oit)
	4519	{
	4520	Intersectable obj = oit;
	4521
	4522	// compute bounding box of view space
	4523	mBoundingBox.Include(obj->GetBox());
	4524	}
	4525	}
	4526	}
	4527
[1135]	4528
[1143]	4529	void OspTree::ProcessMultipleRefs(KdLeaf *leaf) const
[1089]	4530	{
[1143]	4531	// find objects from multiple kd-leaves
	4532	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1089]	4533
[1143]	4534	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
[1122]	4535	{
[1143]	4536	Intersectable object = oit;
	4537
	4538	if (object->mReferences > 1)
[1122]	4539	{
[1143]	4540	leaf->mMultipleObjects.push_back(object);
[1122]	4541	}
[1089]	4542	}
	4543	}
	4544
[1143]	4545
[1106]	4546	void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
	4547	{
	4548	stack<KdNode *> nodeStack;
	4549	nodeStack.push(mRoot);
[1089]	4550
[1106]	4551	while (!nodeStack.empty())
	4552	{
	4553	KdNode *node = nodeStack.top();
	4554	nodeStack.pop();
	4555	if (node->IsLeaf())
	4556	{
	4557	KdLeaf leaf = (KdLeaf )node;
	4558	leaves.push_back(leaf);
	4559	}
	4560	else
	4561	{
	4562	KdInterior interior = (KdInterior )node;
	4563	nodeStack.push(interior->mBack);
	4564	nodeStack.push(interior->mFront);
	4565	}
	4566	}
	4567	}
[1021]	4568
[1072]	4569
[1144]	4570	AxisAlignedBox3 OspTree::GetBoundingBox(KdNode *node) const
[1106]	4571	{
	4572	if (!node->mParent)
	4573	return mBoundingBox;
[1072]	4574
[1106]	4575	if (!node->IsLeaf())
	4576	{
	4577	return (dynamic_cast<KdInterior *>(node))->mBox;
	4578	}
	4579
	4580	KdInterior parent = dynamic_cast<KdInterior >(node->mParent);
	4581
	4582	AxisAlignedBox3 box(parent->mBox);
	4583
	4584	if (parent->mFront == node)
	4585	box.SetMin(parent->mAxis, parent->mPosition);
	4586	else
	4587	box.SetMax(parent->mAxis, parent->mPosition);
	4588
	4589	return box;
	4590	}
	4591
	4592
[1121]	4593	void OspTree::CollectViewCells(KdLeaf *leaf, ViewCellContainer &viewCells)
	4594	{
	4595	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	4596
	4597	ViewCell::NewMail();
	4598
	4599	// loop through all object and collect view cell pvs of this node
	4600	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	4601	{
	4602	Intersectable obj = oit;
	4603
	4604	ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
	4605
	4606	for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
	4607	{
	4608	ViewCell vc = (vit).first;
	4609
	4610	if (!vc->Mailed())
	4611	{
	4612	vc->Mail();
	4613	viewCells.push_back(vc);
	4614	}
	4615	}
	4616	}
	4617	}
	4618
	4619
	4620	void OspTree::CollectDirtyCandidates(OspSplitCandidate *sc,
	4621	vector<SplitCandidate *> &dirtyList)
	4622	{
[1138]	4623	OspTraversalData &tData = sc->mParentData;
	4624	KdLeaf *node = tData.mNode;
	4625
	4626	ViewCell::NewMail();
	4627	ViewCellContainer viewCells;
	4628	ViewCellContainer tmpViewCells;
[1121]	4629
[1138]	4630	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
[1121]	4631
[1138]	4632	// find all view cells associated with the rays, add them to view cells
	4633	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
	4634	{
	4635	VssRay ray = (rit).mRay;
	4636	mVspTree->GetViewCells(*ray, tmpViewCells);
[1121]	4637
[1138]	4638	ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
[1121]	4639
[1138]	4640	for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
	4641	{
	4642	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
	4643
	4644	if (!vc->Mailed())
	4645	{
	4646	vc->Mail();
	4647	viewCells.push_back(vc);
	4648	}
	4649	}
	4650	}
	4651
	4652
	4653	// split candidates holding this view cells
	4654	// are thrown into dirty list
[1121]	4655	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	4656
	4657	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	4658	{
	4659	VspViewCell vc = dynamic_cast<VspViewCell >(*vit);
	4660
	4661	VspLeaf *leaf = vc->mLeaf;
	4662	dirtyList.push_back(leaf->GetSplitCandidate());
	4663	}
	4664	}
	4665
	4666
[1135]	4667	KdNode *OspTree::GetRoot() const
	4668	{
	4669	return mRoot;
	4670	}
	4671
	4672
[1133]	4673	KdLeaf OspTree::GetLeaf(const Vector3 &pt, KdNode node) const
	4674	{
[1144]	4675	// start from root of tree
[1133]	4676	if (node == NULL)
[1135]	4677	{
[1133]	4678	node = mRoot;
[1135]	4679	}
[1133]	4680
	4681	stack<KdNode *> nodeStack;
	4682	nodeStack.push(node);
	4683
	4684	KdLeaf *leaf = NULL;
	4685
	4686	while (!nodeStack.empty())
	4687	{
	4688	KdNode *node = nodeStack.top();
	4689	nodeStack.pop();
	4690
	4691	if (node->IsLeaf())
	4692	{
	4693	leaf = dynamic_cast<KdLeaf *>(node);
	4694	}
	4695	else
	4696	{
[1144]	4697	// find point
[1133]	4698	KdInterior interior = dynamic_cast<KdInterior >(node);
	4699
[1144]	4700	if (interior->mPosition > pt[interior->mAxis])
[1135]	4701	{
[1133]	4702	nodeStack.push(interior->mBack);
[1135]	4703	}
[1133]	4704	else
[1135]	4705	{
[1133]	4706	nodeStack.push(interior->mFront);
[1135]	4707	}
[1133]	4708	}
	4709	}
	4710
	4711	return leaf;
	4712	}
	4713
	4714
[1186]	4715	void OspTree::PreprocessRays(KdLeaf *root,
	4716	const VssRayContainer &sampleRays,
[1176]	4717	RayInfoContainer &rays)
[1133]	4718	{
[1121]	4719	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[1186]	4720	RayInfoContainer clippedRays;
[1020]	4721
	4722	long startTime = GetTime();
	4723
	4724	cout << "storing rays ... ";
	4725
	4726	Intersectable::NewMail();
	4727
[1121]	4728	//-- store rays and objects
[1016]	4729	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	4730	{
	4731	VssRay ray = rit;
[1178]	4732
[1016]	4733	float minT, maxT;
[1121]	4734	static Ray hray;
[1016]	4735
	4736	hray.Init(*ray);
[1027]	4737
[1016]	4738	// TODO: not very efficient to implictly cast between rays types
[1135]	4739	if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
[1016]	4740	{
	4741	float len = ray->Length();
[1186]	4742	if (!len)
[1016]	4743	len = Limits::Small;
	4744
[1186]	4745	clippedRays.push_back(RayInfo(ray, minT / len, maxT / len));
[1176]	4746
	4747	// HACK: reset nodes for the case we have used object kd tree for
	4748	// tree building.
[1189]	4749	ray->mOriginNode = NULL;
[1176]	4750	ray->mTerminationNode = NULL;
[1016]	4751	}
	4752	}
[1020]	4753
[1186]	4754	FilterRays(root, clippedRays, rays);
	4755
[1027]	4756	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1121]	4757	}
[1020]	4758
[1089]	4759
[1135]	4760
	4761	int OspTree::SplitRays(const AxisAlignedPlane &plane,
	4762	RayInfoContainer &rays,
	4763	RayInfoContainer &frontRays,
	4764	RayInfoContainer &backRays) const
	4765	{
	4766	int splits = 0;
	4767
	4768	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4769
	4770	for (rit = rays.begin(); rit != rit_end; ++ rit)
	4771	{
	4772	RayInfo bRay = *rit;
	4773
	4774	VssRay *ray = bRay.mRay;
	4775	float t;
	4776
	4777	// get classification and receive new t
	4778	//-- test if start point behind or in front of plane
	4779	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
	4780
	4781	if (side == 0)
	4782	{
	4783	++ splits;
	4784
	4785	if (ray->HasPosDir(plane.mAxis))
	4786	{
	4787	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	4788	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	4789	}
	4790	else
	4791	{
	4792	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	4793	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	4794	}
	4795	}
	4796	else if (side == 1)
	4797	{
	4798	frontRays.push_back(bRay);
	4799	}
	4800	else
	4801	{
	4802	backRays.push_back(bRay);
	4803	}
	4804	}
	4805
	4806	return splits;
	4807	}
	4808
	4809
[1186]	4810	int OspTree::FilterRays(KdLeaf *leaf,
	4811	const RayInfoContainer &rays,
	4812	RayInfoContainer &filteredRays)
	4813	{
	4814	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4815
	4816	for (rit = rays.begin(); rit != rit_end; ++ rit)
	4817	{
	4818	VssRay ray = (rit).mRay;
	4819
	4820	// test if intersection point with one of the objects is inside this node
	4821	const bool originInside = EndPointInsideNode(leaf, *ray, false);
	4822	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
	4823
	4824	if (originInside \|\| terminationInside)
	4825	{
	4826	filteredRays.push_back(ray);
	4827	}
	4828	}
	4829
	4830	return 0;
	4831	}
	4832
	4833
[1184]	4834	int OspTree::CheckViewCellsPvs(KdLeaf *leaf,
	4835	const RayInfoContainer &rays) const
	4836	{
	4837	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	4838
	4839	Intersectable::NewMail();
	4840	ObjectContainer touchedObjects;
	4841
	4842
	4843	for (rit = rays.begin(); rit < rit_end; ++ rit)
	4844	{
	4845	VssRay ray = (rit).mRay;
	4846
[1189]	4847	if (ray->mTerminationObject)
[1184]	4848	{
	4849	Intersectable *obj = ray->mTerminationObject;
	4850
	4851	if (!obj->Mailed())
	4852	{
	4853	obj->Mail();
	4854	touchedObjects.push_back(obj);
	4855	}
	4856	}
	4857
[1189]	4858	if (ray->mOriginObject)
[1184]	4859	{
	4860	Intersectable *obj = ray->mOriginObject;
	4861
	4862	if (!obj->Mailed())
	4863	{
	4864	obj->Mail();
	4865	touchedObjects.push_back(obj);
	4866	}
	4867	}
	4868	}
	4869	Debug << "here65 " << touchedObjects.size() << endl;
	4870	ObjectContainer::const_iterator it, it_end = touchedObjects.end();
	4871	for (it = touchedObjects.begin(); it != it_end; ++ it)
	4872	{
	4873	Debug << "\nhere94 obj: " << (it) << " size: " << (it)->mViewCellPvs.GetSize() << endl << endl;
	4874	ViewCellPvsMap::const_iterator mit, mit_end = (*it)->mViewCellPvs.mEntries.end();
	4875
	4876	for (mit = (*it)->mViewCellPvs.mEntries.begin(); mit != mit_end; ++ mit)
	4877	{
	4878	Debug << "newsumpdf: " << (*mit).second.mSumPdf << endl;
	4879	}
	4880	}
	4881
	4882	return 0;
	4883	}
	4884
	4885
[1141]	4886	KdIntersectable OspTree::GetOrCreateKdIntersectable(KdNode node)
	4887	{
	4888	// search nodes
[1144]	4889	std::map<KdNode , KdIntersectable >::
	4890	const_iterator it = mKdIntersectables.find(node);
[1135]	4891
[1141]	4892	if (it != mKdIntersectables.end())
	4893	{
	4894	return (*it).second;
	4895	}
[1135]	4896
[1141]	4897	// not in map => create new entry
[1189]	4898	KdIntersectable *kdObj = new KdIntersectable(node);
[1141]	4899	mKdIntersectables[node] = kdObj;
	4900
	4901	return kdObj;
	4902	}
	4903
	4904
[1176]	4905	/*
[1145]	4906	void OspTree::AddViewCellVolume(ViewCell *vc,
	4907	const int cf,
	4908	float &frontVol,
	4909	float &backVol,
	4910	float &totalVol) const
	4911	{
	4912	//const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
	4913	const float vol = vc->GetVolume();
[1143]	4914
[1145]	4915	// view cell not found yet => new
	4916	if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
	4917	{
	4918	totalVol += vol;
	4919	}
	4920
	4921	if (cf >= 0) // front volume
	4922	{
	4923	if (!vc->Mailed() && !vc->Mailed(2))
	4924	{
	4925	frontVol += vol;
	4926
	4927	// already in back volume => in both volumes
	4928	if (vc->Mailed(1))
	4929	vc->Mail(2);
	4930	else
	4931	vc->Mail();
	4932	}
	4933	}
	4934
	4935	if (cf <= 0) // back volume
	4936	{
	4937	if (!vc->Mailed(1) && !vc->Mailed(2))
	4938	{
	4939	backVol += vol;
	4940
	4941	// already in front volume => in both volume
	4942	if (vc->Mailed())
	4943	vc->Mail(2);
	4944	else
	4945	vc->Mail(1);
	4946	}
	4947	}
	4948	}
[1176]	4949	*/
[1184]	4950
	4951
[1176]	4952	void OspTree::MailViewCell(ViewCell *vc, const int cf) const
	4953	{
	4954	if (vc->Mailed(2)) // already classified
	4955	return;
[1145]	4956
[1176]	4957	if (cf >= 0) // front volume
	4958	{
[1189]	4959	// already in back volume => in both volumes
[1176]	4960	if (vc->Mailed(1))
	4961	{
	4962	vc->Mail(2);
	4963	}
	4964	else
	4965	{
	4966	vc->Mail();
	4967	}
	4968	}
[1145]	4969
[1176]	4970	if (cf <= 0) // back volume
	4971	{
	4972	// already in front volume => in both volume
	4973	if (vc->Mailed())
	4974	{
	4975	vc->Mail(2);
	4976	}
	4977	else
	4978	{
	4979	vc->Mail(1);
	4980	}
	4981	}
	4982	}
	4983
	4984
	4985	void OspTree::AddViewCellVolumeContri(ViewCell *vc,
	4986	float &frontVol,
	4987	float &backVol,
	4988	float &frontAndBackVol) const
	4989	{
	4990	if (vc->Mailed())
[1181]	4991	{
[1176]	4992	frontVol += vc->GetVolume();
[1181]	4993	}
[1176]	4994	else if (vc->Mailed(1))
[1181]	4995	{
[1176]	4996	backVol += vc->GetVolume();
[1181]	4997	}
[1176]	4998	else if (vc->Mailed(2))
[1181]	4999	{
[1176]	5000	frontAndBackVol += vc->GetVolume();
[1181]	5001	}
[1176]	5002	}
	5003
	5004
[1184]	5005	float OspTree::EvalViewCellsVolume(KdLeaf *leaf,
	5006	const RayInfoContainer &rays) const
[1180]	5007	{
	5008	float vol = 0;
	5009	ViewCell::NewMail();
[1176]	5010
[1180]	5011	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	5012
	5013	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	5014	{
	5015	VssRay ray = (rit).mRay;
	5016
	5017	ViewCellContainer viewCells;
[1189]	5018	mVspTree->GetViewCells(*ray, viewCells);
[1180]	5019
	5020	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5021
	5022	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5023	{
	5024	ViewCell vc = vit;
	5025
	5026	if (!vc->Mailed())
	5027	{
	5028	vc->Mail();
	5029	vol += vc->GetVolume();
	5030	}
	5031	}
	5032	}
	5033
	5034	return vol;
	5035	}
	5036
	5037
[1184]	5038	bool OspTree::AddViewCellToObjectPvs(Intersectable *obj,
	5039	ViewCell *vc,
	5040	float &contribution,
	5041	bool onlyMailed) const
	5042	{
	5043	contribution = 0; // todo
	5044
[1189]	5045	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1184]	5046
	5047	if (!vdata)
	5048	{
	5049	vdata = obj->mViewCellPvs.AddSample2(vc, 1);
	5050	}
	5051	else if (!onlyMailed \|\| !vdata->Mailed())
	5052	{
	5053	obj->mViewCellPvs.AddSample(vc, 1);
	5054	}
	5055
	5056	vdata->Mail();
	5057
	5058	return true;
	5059	}
	5060
	5061
[1189]	5062	void OspTree::CollectTouchedViewCells(const RayInfoContainer &rays,
	5063	ViewCellContainer &touchedViewCells) const
	5064	{
	5065	ViewCell::NewMail();
	5066
	5067	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	5068
	5069	for (rit = rays.begin(); rit != rit_end; ++ rit)
	5070	{
	5071	VssRay ray = (rit).mRay;
	5072
	5073	ViewCellContainer viewCells;
	5074	mVspTree->GetViewCells(*ray, viewCells);
	5075
	5076	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5077
	5078	// traverse through view cells and classify them according
	5079	// to them being seen from to back / front / front and back node
	5080	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5081	{
	5082	ViewCell vc = vit;
	5083	if (!vc->Mailed())
	5084	{
	5085	vc->Mail();
	5086	touchedViewCells.push_back(vc);
	5087	}
	5088	}
	5089	}
	5090	}
	5091
	5092
[1184]	5093	int OspTree::UpdateViewCellsPvs(KdLeaf *leaf,
	5094	const RayInfoContainer &rays) const
	5095
	5096	{
[1189]	5097	MailablePvsData::NewMail();
	5098
	5099	/*RayInfoContainer::const_iterator rit, rit_end = rays.end();
[1184]	5100
	5101	for (rit = rays.begin(); rit < rit_end; ++ rit)
	5102	{
	5103	VssRay ray = (rit).mRay;
	5104
[1189]	5105	ViewCellContainer viewCells;
	5106	mVspTree->GetViewCells(*ray, viewCells);
[1184]	5107
[1189]	5108	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5109
	5110	// traverse through view cells and classify them according
	5111	// to them being seen from to back / front / front and back node
	5112	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
[1184]	5113	{
[1189]	5114	ViewCell vc = vit;
[1184]	5115
[1189]	5116	Intersectable *obj = ray->mTerminationObject;
	5117	if (obj)
	5118	{
	5119	float contri;
	5120	AddViewCellToObjectPvs(obj, vc, contri, true);
	5121	}
[1184]	5122
[1189]	5123	obj = ray->mOriginObject;
	5124	if (obj)
[1184]	5125	{
[1189]	5126	float contri;
	5127	AddViewCellToObjectPvs(obj, vc, contri, true);
	5128	}
	5129	}
	5130	}*/
	5131
	5132	ViewCellContainer touchedViewCells;
	5133	CollectTouchedViewCells(rays, touchedViewCells);
[1184]	5134
[1189]	5135	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
[1184]	5136
[1189]	5137	for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
	5138	{
	5139	Intersectable obj = oit;
	5140	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5141
	5142	// traverse through view cells and classify them according
	5143	// to them being seen from to back / front / front and back node
	5144	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5145	{
	5146	ViewCell vc = vit;
	5147	float contri;
	5148	AddViewCellToObjectPvs(obj, vc, contri, true);
[1184]	5149	}
	5150	}
	5151
	5152	return 0;
	5153	}
	5154
	5155
	5156	int OspTree::RemoveParentViewCellsPvs(KdLeaf *leaf,
	5157	const RayInfoContainer &rays
	5158	) const
	5159
	5160	{
[1189]	5161	MailablePvsData::NewMail();
[1184]	5162
[1189]	5163	/*RayInfoContainer::const_iterator rit, rit_end = rays.end();
[1184]	5164	for (rit = rays.begin(); rit < rit_end; ++ rit)
	5165	{
	5166	VssRay ray = (rit).mRay;
	5167
	5168	// test if intersection point with one of the objects is inside this node
[1189]	5169	ViewCellContainer viewCells;
	5170	mVspTree->GetViewCells(*ray, viewCells);
[1184]	5171
[1189]	5172	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5173
	5174	// traverse through view cells and classify them according
	5175	// to them being seen from to back / front / front and back node
	5176	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
[1184]	5177	{
[1189]	5178	ViewCell vc = vit;
	5179	Intersectable *obj = ray->mTerminationObject;
[1184]	5180
[1189]	5181	if (obj)
[1184]	5182	{
[1189]	5183	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1184]	5184
[1189]	5185	if (vdata && !vdata->Mailed())
[1184]	5186	{
[1189]	5187	vdata->Mail();
	5188	obj->mViewCellPvs.RemoveSample(vc, 1);
[1184]	5189	}
[1189]	5190	}
[1184]	5191
[1189]	5192	obj = ray->mOriginObject;
[1184]	5193
[1189]	5194	if (obj)
	5195	{
	5196	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
	5197
	5198	if (vdata && !vdata->Mailed())
	5199	{
	5200	vdata->Mail();
	5201	obj->mViewCellPvs.RemoveSample(vc, 1);
[1184]	5202	}
	5203	}
	5204	}
[1189]	5205	}*/
	5206
	5207	ViewCellContainer touchedViewCells;
	5208	CollectTouchedViewCells(rays, touchedViewCells);
	5209
	5210	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	5211
	5212	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	5213	{
	5214	Intersectable obj = oit;
	5215
	5216	// traverse through view cells and classify them according
	5217	// to them being seen from to back / front / front and back node
	5218	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5219
	5220	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5221	{
	5222	ViewCell vc = vit;
	5223
	5224	MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
	5225
	5226	if (vdata && !vdata->Mailed())
	5227	{
	5228	vdata->Mail();
	5229	obj->mViewCellPvs.RemoveSample(vc, 1);
	5230	}
	5231	}
[1184]	5232	}
	5233
	5234	return 0;
	5235	}
	5236
	5237
[1186]	5238	float OspTree::EvalRenderCost(const VssRayContainer &myrays)
[1184]	5239	{
	5240	float rc = 0;
[1186]	5241	float prop = mVspTree->GetBoundingBox().GetVolume();
	5242
[1184]	5243	KdLeafContainer leaves;
	5244	CollectLeaves(leaves);
	5245
[1186]	5246	ViewCellContainer vcleaves;
	5247	mVspTree->CollectViewCells(vcleaves, false);
	5248
	5249
	5250	ViewCellContainer::const_iterator vit, vit_end = vcleaves.end();
	5251
	5252	for (vit = vcleaves.begin(); vit != vit_end; ++ vit)
	5253	{
	5254	ViewCell vc = vit;
	5255	vc->GetPvs().Clear();
	5256	}
	5257
[1184]	5258	KdLeafContainer::const_iterator kit, kit_end = leaves.end();
[1186]	5259
[1189]	5260	MailablePvsData::NewMail();
[1186]	5261
[1184]	5262	for (kit = leaves.begin(); kit != kit_end; ++ kit)
	5263	{
	5264	KdLeaf leaf = kit;
	5265	float newCost = 0;
	5266	float vol = 0;
	5267
	5268	ViewCell::NewMail();
	5269	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	5270	ViewCellContainer touchedViewCells;
	5271
	5272	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	5273	{
	5274	VssRay ray = rit;
	5275
	5276	// test if intersection point with one of the objects is inside this node
	5277	const bool originInside = EndPointInsideNode(leaf, *ray, false);
	5278	const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
	5279
	5280	if (originInside \|\| terminationInside)
	5281	{
	5282	ViewCellContainer viewCells;
	5283	mVspTree->GetViewCells(*ray, viewCells);
	5284
	5285	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5286
	5287	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5288	{
	5289	ViewCell vc = vit;
	5290
	5291	// if not previously mailed
	5292	if (!vc->Mailed())
	5293	{
	5294	vc->Mail();
	5295	touchedViewCells.push_back(vc);
	5296	}
	5297
	5298	}
	5299	}
	5300	}
	5301
	5302	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	5303
	5304	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	5305	{
	5306	Intersectable obj = oit;
	5307	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5308
	5309	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5310	{
	5311	ViewCell vc = vit;
[1189]	5312	PvsData *vdata = vc->GetPvs().Find(obj);
[1184]	5313
	5314	if (!vdata)
	5315	{
	5316	vc->GetPvs().AddSample(obj, 1);
	5317	newCost += vc->GetVolume();
[1189]	5318	}
[1186]	5319
[1189]	5320	/* MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
[1186]	5321
	5322	if (!vdata \|\| !vdata->Mailed())
	5323	{
	5324	newCost += vc->GetVolume();
	5325	if (!vdata)
	5326	vdata = obj->mViewCellPvs.AddSample2(vc, 1);
	5327	vdata->Mail();
[1189]	5328	}*/
[1184]	5329	}
	5330	}
	5331
	5332	rc += newCost;
	5333	}
	5334
	5335	return rc / prop;
	5336	}
	5337
	5338
[1186]	5339	float OspTree::EvalLeafCost(const OspTraversalData &tData)
	5340	{
	5341	KdLeaf *leaf = tData.mNode;
[1135]	5342
[1186]	5343	float rc = 0;
	5344	//float prop = mVspTree->GetBoundingBox().GetVolume();
	5345	//float vol = 0;
	5346	//ViewCell::NewMail();
	5347
	5348	RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
	5349	ViewCellContainer touchedViewCells;
[1135]	5350
[1186]	5351	for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
	5352	{
	5353	VssRay ray = (rit).mRay;
	5354
	5355	// test if intersection point with one of the objects is inside this node
	5356
	5357	ViewCellContainer viewCells;
	5358	mVspTree->GetViewCells(*ray, viewCells);
	5359
	5360	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	5361
	5362	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	5363	{
	5364	ViewCell vc = vit;
	5365
	5366	// if not previously mailed
	5367	if (!vc->Mailed())
	5368	{
	5369	vc->Mail();
	5370	touchedViewCells.push_back(vc);
	5371	}
	5372	}
	5373	}
	5374
	5375	// clear pvs of involved view cells
	5376	ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
	5377
	5378	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5379	{
	5380	ViewCell vc = vit;
	5381	vc->GetPvs().Clear();
	5382	}
	5383
	5384	ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
	5385
	5386	//Debug << "here53 " << touchedViewCells.size() << endl;
	5387	for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
	5388	{
	5389	Intersectable obj = oit;
	5390
	5391	for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
	5392	{
	5393	ViewCell vc = vit;
[1189]	5394	PvsData *vdata = vc->GetPvs().Find(obj);
[1186]	5395
	5396	if (!vdata)
	5397	{
	5398	vc->GetPvs().AddSample(obj, 1);
	5399	rc += vc->GetVolume();
	5400	//prop += vc->GetVolume();
	5401	}
	5402	}
	5403	}
	5404
	5405	return rc;
	5406	}
	5407
	5408
[1201]	5409	bool OspTree::Export(OUT_STREAM &stream)
	5410	{
	5411	ExportNode(mRoot, stream);
[1186]	5412
[1201]	5413	return true;
	5414	}
	5415
	5416
	5417	void OspTree::ExportNode(KdNode *node, OUT_STREAM &stream)
	5418	{
	5419	if (node->IsLeaf())
	5420	{
	5421	KdLeaf leaf = dynamic_cast<KdLeaf >(node);
	5422
	5423	stream << "<Leaf ";
	5424	stream << "objects=\"";
	5425
	5426	//-- export objects in kd leaves
	5427	//if (mExportObjects) ExportObjects(leaf, stream);
	5428
	5429	stream << "\" />" << endl;
	5430	//stream << " </Leaf>" << endl;
	5431	}
	5432	else
	5433	{
	5434	KdInterior interior = dynamic_cast<KdInterior >(node);
	5435
	5436	stream << "<Interior plane=\"" << interior->mPosition << " "
	5437	<< interior->mAxis << "\">" << endl;
	5438
	5439	ExportNode(interior->mBack, stream);
	5440	ExportNode(interior->mFront, stream);
	5441
	5442	stream << "</Interior>" << endl;
	5443	}
	5444	}
	5445
	5446
	5447	struct KdObjectsTraversalData
	5448	{
	5449	KdNode *node;
	5450	ObjectContainer *objects;
	5451	};
	5452
	5453
	5454	void OspTree::InsertObjects(KdNode *node, const ObjectContainer &objects)
	5455	{
	5456	stack<KdObjectsTraversalData> tStack;
	5457
	5458	while (!tStack.empty())
	5459	{
	5460	KdObjectsTraversalData tData = tStack.top();
	5461	tStack.pop();
	5462
	5463	KdNode *node = tData.node;
	5464
	5465	if (node->IsLeaf())
	5466	{
	5467	KdLeaf leaf = dynamic_cast<KdLeaf >(node);
	5468
	5469	ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
	5470
	5471	for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
	5472	{
	5473	leaf->mObjects.push_back(*oit);
	5474	}
	5475	}
	5476	else // interior
	5477	{
	5478	KdObjectsTraversalData frontData, backData;
	5479	KdInterior interior = dynamic_cast<KdInterior >(node);
	5480
	5481	frontData.objects = new ObjectContainer();
	5482	backData.objects = new ObjectContainer();
	5483
	5484	ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
	5485
	5486	for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
	5487	{
	5488	Intersectable object = oit;
	5489
	5490	// determine the side of this ray with respect to the plane
	5491	const AxisAlignedBox3 box = object->GetBox();
	5492
	5493	if (box.Max(interior->mAxis) >= interior->mPosition)
	5494	{
	5495	frontData.objects->push_back(object);
	5496	}
	5497
	5498	if (box.Min(interior->mAxis) < interior->mPosition)
	5499	{
	5500	backData.objects->push_back(object);
	5501	}
	5502	}
	5503
	5504	tStack.push(backData);
	5505	tStack.push(frontData);
	5506	}
	5507
	5508	DEL_PTR(tData.objects);
	5509	}
	5510	}
	5511
	5512
[1186]	5513	/*******************************************************************/
	5514	/* class HierarchyManager implementation */
	5515	/*******************************************************************/
	5516
	5517
[1135]	5518	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
	5519	mVspTree(vspTree), mOspTree(ospTree)
	5520	{
[1137]	5521	// cross references
[1135]	5522	mVspTree.mOspTree = &ospTree;
[1137]	5523	mOspTree.mVspTree = &vspTree;
[1174]	5524
	5525	char subdivisionStatsLog[100];
[1189]	5526	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
	5527	subdivisionStatsLog);
[1174]	5528	mSubdivisionStats.open(subdivisionStatsLog);
[1135]	5529	}
	5530
	5531
	5532	SplitCandidate *HierarchyManager::NextSplitCandidate()
	5533	{
	5534	SplitCandidate *splitCandidate = mTQueue.Top();
	5535	mTQueue.Pop();
	5536
	5537	return splitCandidate;
	5538	}
	5539
	5540
[1145]	5541	VspTree::VspSplitCandidate *HierarchyManager::PrepareVsp(const VssRayContainer &sampleRays,
[1133]	5542	AxisAlignedBox3 *forcedViewSpace,
[1135]	5543	RayInfoContainer &rays)
[1121]	5544	{
[1135]	5545	// store pointer to this tree
	5546	VspTree::VspSplitCandidate::sVspTree = &mVspTree;
	5547	mVspTree.mVspStats.nodes = 1;
	5548
[1142]	5549	// compute view space bounding box
[1143]	5550	mVspTree.ComputeBoundingBox(sampleRays, forcedViewSpace);
[1089]	5551
[1143]	5552	// initialise termination criteria
[1135]	5553	mVspTree.mTermMinProbability *= mBoundingBox.GetVolume();
	5554	mVspTree.mGlobalCostMisses = 0;
[1121]	5555
[1143]	5556	// get clipped rays
[1176]	5557	mVspTree.PreprocessRays(sampleRays, rays);
[1135]	5558
[1181]	5559	const int pvsSize = mVspTree.EvalPvsSize(rays);
[1133]	5560
[1145]	5561	Debug << "pvs size: " << (int)pvsSize << endl;
	5562	Debug << "rays size: " << (int)rays.size() << endl;
[1089]	5563
[1143]	5564	//-- prepare view space partition
	5565
[1089]	5566	// add first candidate for view space partition
[1109]	5567	VspLeaf *leaf = new VspLeaf();
	5568	mVspTree.mRoot = leaf;
[1133]	5569
[1027]	5570	const float prop = mVspTree.mBoundingBox.GetVolume();
	5571
[1089]	5572	// first vsp traversal data
[1109]	5573	VspTree::VspTraversalData vData(leaf,
[1027]	5574	0,
	5575	&rays,
[1089]	5576	pvsSize,
[1027]	5577	prop,
	5578	mVspTree.mBoundingBox);
	5579
[1121]	5580	// create first view cell
[1143]	5581	mVspTree.CreateViewCell(vData, false);
[1121]	5582
[1178]	5583	#if WORK_WITH_VIEWCELL_PVS
	5584
[1121]	5585	// add first view cell to all the objects view cell pvs
	5586	ObjectPvsMap::const_iterator oit,
	5587	oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
	5588
	5589
	5590	for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
	5591	{
	5592	Intersectable obj = (oit).first;
	5593	obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
	5594	}
[1174]	5595	#endif
[1121]	5596
[1027]	5597	// compute first split candidate
[1133]	5598	VspTree::VspSplitCandidate *splitCandidate =
	5599	new VspTree::VspSplitCandidate(vData);
[1099]	5600	mVspTree.EvalSplitCandidate(*splitCandidate);
[1027]	5601
[1174]	5602	mVspTree.mTotalCost = (float)pvsSize;
	5603	mVspTree.EvalSubdivisionStats(*splitCandidate);
	5604
[1133]	5605	return splitCandidate;
[1121]	5606	}
[1027]	5607
[1089]	5608
[1145]	5609	OspTree::OspSplitCandidate * HierarchyManager::PrepareOsp(const VssRayContainer &sampleRays,
[1174]	5610	const ObjectContainer &objects,
	5611	AxisAlignedBox3 *forcedObjectSpace,
	5612	RayInfoContainer &rays)
[1121]	5613	{
[1135]	5614	// store pointer to this tree
	5615	OspTree::OspSplitCandidate::sOspTree = &mOspTree;
	5616	mOspTree.mOspStats.nodes = 1;
	5617
[1144]	5618	// compute bounding box from objects
[1135]	5619	mOspTree.ComputeBoundingBox(objects, forcedObjectSpace);
	5620
	5621	mOspTree.mTermMinProbability *= mBoundingBox.GetVolume();
	5622	mGlobalCostMisses = 0;
	5623
[1179]	5624	// create new root
[1109]	5625	KdLeaf *kdleaf = new KdLeaf(NULL, 0);
	5626	kdleaf->mObjects = objects;
	5627	mOspTree.mRoot = kdleaf;
[1089]	5628
[1186]	5629	// get clipped rays
	5630	mOspTree.PreprocessRays(kdleaf, sampleRays, rays);
	5631
	5632
[1184]	5633	// probabilty is voume of all "seen" view cells
[1189]	5634	#if 1
[1181]	5635	const float prop = mOspTree.EvalViewCellsVolume(kdleaf, rays);
[1184]	5636	#else
	5637	const float prop = mVspTree.GetBoundingBox().GetVolume();
	5638	#endif
[1179]	5639
[1184]	5640	//-- add first candidate for object space partition
[1089]	5641
[1184]	5642	// create osp traversal data
[1109]	5643	OspTree::OspTraversalData oData(kdleaf,
[1089]	5644	0,
[1135]	5645	&rays,
[1189]	5646	0,//(int)objects.size(),
[1089]	5647	prop,
	5648	mOspTree.mBoundingBox);
	5649
	5650
[1184]	5651	// first split candidate
[1121]	5652	OspTree::OspSplitCandidate *oSplitCandidate =
	5653	new OspTree::OspSplitCandidate(oData);
[1144]	5654
[1189]	5655	mOspTree.UpdateViewCellsPvs(kdleaf, rays);
	5656
[1174]	5657	mOspTree.EvalSplitCandidate(*oSplitCandidate);
[1089]	5658
[1184]	5659	mOspTree.mTotalCost = (float)objects.size() * prop /
	5660	mVspTree.GetBoundingBox().GetVolume();
	5661
[1174]	5662	mOspTree.EvalSubdivisionStats(*oSplitCandidate);
	5663
[1133]	5664	return oSplitCandidate;
[1016]	5665	}
	5666
	5667
[1121]	5668	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
	5669	const ObjectContainer &objects,
	5670	AxisAlignedBox3 *forcedViewSpace,
[1135]	5671	RayInfoContainer &viewSpaceRays,
	5672	RayInfoContainer &objectSpaceRays)
[1121]	5673	{
[1135]	5674	SplitCandidate *vsc =
	5675	PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
	5676	mTQueue.Push(vsc);
	5677
	5678	SplitCandidate *osc =
	5679	PrepareOsp(sampleRays, objects, forcedViewSpace, objectSpaceRays);
	5680
	5681	mTQueue.Push(osc);
[1121]	5682	}
	5683
	5684
[1174]	5685	void HierarchyManager::EvalSubdivisionStats(const SplitCandidate &tData)
	5686	{
	5687	const float costDecr = tData.GetRenderCostDecrease();
	5688
	5689	//mTotalCost -= costDecr;
	5690	// mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
	5691
	5692	AddSubdivisionStats(mOspTree.mOspStats.Leaves() + mVspTree.mVspStats.Leaves(),
	5693	costDecr,
	5694	mTotalCost
	5695	);
	5696	}
	5697
	5698
	5699	void HierarchyManager::AddSubdivisionStats(const int splits,
	5700	const float renderCostDecr,
	5701	const float totalRenderCost)
	5702	{
	5703	mSubdivisionStats
	5704	<< "#Splits\n" << splits << endl
	5705	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	5706	<< "#TotalRenderCost\n" << totalRenderCost << endl;
	5707	//<< "#AvgRenderCost\n" << avgRenderCost << endl;
	5708	}
	5709
	5710
[1020]	5711	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
[1016]	5712	{
[1108]	5713	// TODO matt: make virtual by creating superclasss for traveral data
	5714	return candidate->GlobalTerminationCriteriaMet();
[1016]	5715	}
	5716
	5717
[1143]	5718	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
	5719	const ObjectContainer &objects,
	5720	AxisAlignedBox3 *forcedViewSpace)
	5721	{
	5722	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
	5723	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	5724
	5725	// prepare vsp and osp trees for traversal
	5726	PrepareConstruction(sampleRays, objects, forcedViewSpace, viewSpaceRays, objectSpaceRays);
	5727
	5728	mVspTree.mVspStats.Reset();
	5729	mVspTree.mVspStats.Start();
	5730
	5731	cout << "Constructing view space / object space tree ... \n";
	5732	const long startTime = GetTime();
	5733
[1145]	5734	RunConstruction(true);
	5735
	5736	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	5737
	5738	mVspTree.mVspStats.Stop();
	5739	}
	5740
	5741
	5742	bool HierarchyManager::SubdivideSplitCandidate(SplitCandidate *sc)
	5743	{
	5744	const bool globalTerminationCriteriaMet =
	5745	GlobalTerminationCriteriaMet(sc);
	5746
	5747	const bool vspSplit = (sc->Type() == SplitCandidate::VIEW_SPACE);
	5748
	5749	if (vspSplit)
	5750	{
[1174]	5751	VspNode *n = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1145]	5752	}
	5753	else
	5754	{
[1174]	5755	KdNode *n = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1145]	5756	}
[1174]	5757
	5758	return !globalTerminationCriteriaMet;
[1145]	5759	}
	5760
	5761
	5762	void HierarchyManager::RunConstruction(const bool repair)
	5763	{
	5764	int numNodes = 0;
	5765
[1143]	5766	while (!FinishedConstruction())
	5767	{
[1145]	5768	SplitCandidate *splitCandidate = NextSplitCandidate();
	5769
	5770	mTotalCost -= splitCandidate->GetRenderCostDecrease();
[1181]	5771
[1143]	5772	// cost ratio of cost decrease / totalCost
[1145]	5773	const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
[1174]	5774
	5775	if (costRatio < mTermMinGlobalCostRatio)
	5776	++ mGlobalCostMisses;
[1181]	5777
[1184]	5778	/Debug << "\n*********" << endl
[1145]	5779	<< "total cost: " << mTotalCost << " render cost decr: "
	5780	<< splitCandidate->GetRenderCostDecrease()
[1184]	5781	<< " cost ratio: " << costRatio << endl << endl;*/
[1181]	5782
[1168]	5783	//-- subdivide leaf node
[1178]	5784
[1174]	5785	if (SubdivideSplitCandidate(splitCandidate))
	5786	{
[1178]	5787	// subdivision successful
[1174]	5788	EvalSubdivisionStats(*splitCandidate);
	5789
	5790	// reevaluate candidates affected by the split
	5791	// for view space splits, this would be object space splits
	5792	// and other way round
	5793	if (repair)
	5794	RepairQueue();
[1178]	5795
	5796	cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
[1174]	5797	}
[1168]	5798
[1145]	5799	DEL_PTR(splitCandidate);
[1143]	5800	}
	5801	}
	5802
	5803
[1101]	5804	void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
[1106]	5805	const ObjectContainer &objects,
	5806	AxisAlignedBox3 *forcedViewSpace)
[1101]	5807	{
[1178]	5808	// rays clipped in view space and in object space
[1135]	5809	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	5810	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
[1123]	5811
[1145]	5812
[1143]	5813	/////////////////////////////////////////////////////////////
	5814	// view space space partition
	5815	/////////////////////////////////////////////////////////////
	5816
[1176]	5817	#if 0
[1123]	5818	// makes no sense otherwise because only one kd cell available
	5819	// during view space partition
[1141]	5820	const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
	5821	const bool savedStoreMethod = mVspTree.mStoreKdPvs;
	5822
	5823	mVspTree.mUseKdPvsForHeuristics = false;
	5824	mVspTree.mStoreKdPvs = false;
[1176]	5825	#endif
[1123]	5826
[1145]	5827	VspTree::VspSplitCandidate *vsc =
	5828	PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays);
[1174]	5829
[1145]	5830	// add to queue
	5831	mTQueue.Push(vsc);
[1101]	5832
	5833	long startTime = GetTime();
[1121]	5834	cout << "starting vsp contruction ... " << endl;
[1143]	5835
	5836	mVspTree.mVspStats.Reset();
	5837	mVspTree.mVspStats.Start();
	5838
[1101]	5839	int i = 0;
	5840
[1145]	5841	// all objects can be seen from everywhere
	5842	mTotalCost = (float)vsc->mParentData.mPvs;
[1101]	5843
[1145]	5844	const bool repairQueue = false;
[1101]	5845
[1145]	5846	// process view space candidates
	5847	RunConstruction(repairQueue);
[1101]	5848
[1145]	5849	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	5850	mVspTree.mVspStats.Stop();
[1121]	5851
	5852
[1101]	5853
[1142]	5854	/////////////////////////////////////////////////////////////
[1143]	5855	// object space partition
	5856	/////////////////////////////////////////////////////////////
[1142]	5857
[1189]	5858
[1145]	5859	Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
[1144]	5860	cout << "starting osp contruction ... " << endl;
[1142]	5861
[1184]	5862	// start with one big kd cell - all objects can be seen from everywhere
	5863	// note: only true for view space = object space
	5864
[1145]	5865	// compute first candidate
	5866	OspTree::OspSplitCandidate *osc =
[1135]	5867	PrepareOsp(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
[1101]	5868
[1184]	5869	Debug << "reseting cost, new total cost: " << mTotalCost << endl;
	5870	mTotalCost = mOspTree.mTotalCost;
	5871
[1135]	5872	mTQueue.Push(osc);
	5873
[1145]	5874	mOspTree.mOspStats.Reset();
	5875	mOspTree.mOspStats.Start();
[1135]	5876
[1145]	5877	startTime = GetTime();
[1174]	5878
[1145]	5879	// process object space candidates
	5880	RunConstruction(repairQueue);
	5881
	5882	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1101]	5883
[1145]	5884	mOspTree.mOspStats.Stop();
[1101]	5885
[1186]	5886	float rc = mOspTree.EvalRenderCost(sampleRays);
[1184]	5887
[1189]	5888	Debug << "here47 My render cost evalulation: " << rc << endl;
[1184]	5889
[1176]	5890	#if 0
[1145]	5891	// reset parameters
[1141]	5892	mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
	5893	mVspTree.mStoreKdPvs = savedStoreMethod;
[1176]	5894	#endif
[1101]	5895	}
	5896
	5897
[1142]	5898	void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
	5899	const ObjectContainer &objects,
	5900	AxisAlignedBox3 *forcedViewSpace)
	5901	{
[1145]	5902	// only view space partition
	5903	// object kd tree is taken for osp
	5904
[1143]	5905	mVspTree.mVspStats.Reset();
	5906	mVspTree.mVspStats.Start();
[1142]	5907
[1143]	5908	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	5909
[1142]	5910	SplitCandidate sc = PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
	5911	mTQueue.Push(sc);
	5912
	5913	cout << "starting vsp contruction ... " << endl;
	5914
	5915	long startTime = GetTime();
	5916
[1145]	5917	RunConstruction(false);
[1142]	5918
	5919	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
	5920	mVspTree.mVspStats.Stop();
	5921	}
	5922
	5923
[1145]	5924	bool HierarchyManager::FinishedConstruction() const
[1020]	5925	{
[1099]	5926	return mTQueue.Empty();
[1020]	5927	}
	5928
	5929
[1121]	5930	void HierarchyManager::CollectDirtyCandidates(vector<SplitCandidate *> &dirtyList)
	5931	{
	5932	// we have either a object space or view space split
	5933	if (mCurrentCandidate->Type() == SplitCandidate::VIEW_SPACE)
	5934	{
	5935	VspTree::VspSplitCandidate *sc =
	5936	dynamic_cast<VspTree::VspSplitCandidate *>(mCurrentCandidate);
	5937
	5938	mVspTree.CollectDirtyCandidates(sc, dirtyList);
	5939	}
	5940	else // object space split
	5941	{
	5942	OspTree::OspSplitCandidate *sc =
	5943	dynamic_cast<OspTree::OspSplitCandidate *>(mCurrentCandidate);
	5944
	5945	mOspTree.CollectDirtyCandidates(sc, dirtyList);
	5946	}
	5947	}
	5948
	5949
	5950	void HierarchyManager::RepairQueue()
[1093]	5951	{
	5952	// TODO
	5953	// for each update of the view space partition:
	5954	// the candidates from object space partition which
	5955	// have been afected by the view space split (the kd split candidates
	5956	// which saw the view cell which was split) must be reevaluated
	5957	// (maybe not locally, just reinsert them into the queue)
	5958	//
	5959	// vice versa for the view cells
	5960	// for each update of the object space partition
	5961	// reevaluate split candidate for view cells which saw the split kd cell
	5962	//
	5963	// the priority queue update can be solved by implementing a binary heap
	5964	// (explicit data structure, binary tree)
	5965	// *) inserting and removal is efficient
[1099]	5966	// *) search is not efficient => store queue position with each
[1093]	5967	// split candidate
	5968
[1121]	5969	// collect list of "dirty" candidates
	5970	vector<SplitCandidate *> dirtyList;
	5971	CollectDirtyCandidates(dirtyList);
	5972
	5973	//-- reevaluate the dirty list
[1233]	5974	vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();
[1093]	5975
[1099]	5976	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
[1093]	5977	{
[1099]	5978	SplitCandidate* sc = *sit;
[1093]	5979
[1099]	5980	mTQueue.Erase(sc);
[1093]	5981
[1099]	5982	// reevaluate
	5983	sc->EvalPriority();
[1093]	5984
[1099]	5985	// reinsert
	5986	mTQueue.Push(sc);
	5987	}
[1093]	5988	}
	5989
[1002]	5990	}

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

Download in other formats: