Context Navigation

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

Revision 1370, 71.1 KB checked in by mattausch, 18 years ago (diff)
debugged global sorting, worked on object-viewspace subdivision

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

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

Download in other formats: