Context Navigation

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

Revision 2542, 93.0 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: