Context Navigation

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

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

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

Download in other formats: