Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp @ 2015

Revision 2015, 84.0 KB checked in by bittner, 17 years ago (diff)
pvs efficiency tuning

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

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

Download in other formats: