Context Navigation

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

Revision 2210, 85.5 KB checked in by mattausch, 17 years ago (diff)
improved performance of osp

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

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

Download in other formats: