Context Navigation

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

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

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

Download in other formats: