Context Navigation

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

Revision 1379, 71.3 KB checked in by mattausch, 18 years ago (diff)
fixed sah for objeect partition loader for single triangles also for x3d

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

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

Download in other formats: