Context Navigation

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

Revision 1915, 82.6 KB checked in by mattausch, 18 years ago (diff)
implemented pvs correction (debug version)

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

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

Download in other formats: