Context Navigation

VspTree.cpp @ 2588

Revision 2588, 89.2 KB checked in by bittner, 17 years ago (diff)
sceneBox bugfix

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

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

Context Navigation

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

Download in other formats: