Context Navigation

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

Revision 1919, 82.6 KB checked in by mattausch, 18 years ago (diff)
added mechanism for histogram on certain MB in hierarchymanager no more bug in undersampling estimation added sampling strategy to spatial box based (also for eval) added testing scripts

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

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

Download in other formats: