Context Navigation

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

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

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

Download in other formats: