Context Navigation

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

Revision 1189, 143.1 KB checked in by mattausch, 18 years ago (diff)
changed osp partition to something taking mult references into account

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

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

Download in other formats: