Context Navigation

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

Revision 1449, 71.3 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: