Context Navigation

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

Revision 2353, 86.7 KB checked in by mattausch, 17 years ago (diff)
cleaned up project files

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

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

Download in other formats: