Context Navigation

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

Revision 1977, 84.5 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: