Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp @ 1072

Revision 1072, 76.2 KB checked in by mattausch, 18 years ago (diff)

Rev	Line
[1002]	1	#include <stack>
	2	#include <time.h>
	3	#include <iomanip>
	4
[1010]	5	#include "ViewCell.h"
[1002]	6	#include "Plane3.h"
[1006]	7	#include "VspOspTree.h"
[1002]	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"
[1020]	18	#include "KdTree.h"
[1002]	19
[1020]	20
[1002]	21	namespace GtpVisibilityPreprocessor {
	22
	23	#define USE_FIXEDPOINT_T 0
	24
	25
	26	//-- static members
	27
[1016]	28	int VspTree::sFrontId = 0;
	29	int VspTree::sBackId = 0;
	30	int VspTree::sFrontAndBackId = 0;
[1002]	31
	32
	33
	34	// pvs penalty can be different from pvs size
	35	inline static float EvalPvsPenalty(const int pvs,
	36	const int lower,
	37	const int upper)
	38	{
	39	// clamp to minmax values
	40	if (pvs < lower)
	41	return (float)lower;
	42	if (pvs > upper)
	43	return (float)upper;
	44
	45	return (float)pvs;
	46	}
	47
	48
[1008]	49	int VspNode::sMailId = 1;
[1002]	50
	51
[1021]	52
	53	void VspTreeStatistics::Print(ostream &app) const
	54	{
[1027]	55	app << "===== VspTree statistics ===============\n";
[1021]	56
	57	app << setprecision(4);
	58
	59	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
	60
	61	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
	62
	63	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	64
	65	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	66
	67	app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
	68
	69	app << "#N_SPLITS ( Number of splits in axes x y z)\n";
	70
	71	for (int i = 0; i < 3; ++ i)
	72	app << splits[i] << " ";
	73	app << endl;
	74
	75	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
	76	<< maxDepthNodes * 100 / (double)Leaves() << endl;
	77
	78	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n"
	79	<< minPvsNodes * 100 / (double)Leaves() << endl;
	80
	81	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n"
	82	<< minRaysNodes * 100 / (double)Leaves() << endl;
	83
	84	app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n"
	85	<< maxCostNodes * 100 / (double)Leaves() << endl;
	86
	87	app << "#N_PMINPROBABILITYLEAVES ( Percentage of leaves with mininum probability )\n"
	88	<< minProbabilityNodes * 100 / (double)Leaves() << endl;
	89
	90	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"
	91	<< maxRayContribNodes * 100 / (double)Leaves() << endl;
	92
	93	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
	94
	95	app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
	96
	97	app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
	98
	99	app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
	100
	101	app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
	102	//app << "#N_PVS: " << pvs << endl;
	103
[1027]	104	app << "===== END OF VspTree statistics ==========\n";
[1021]	105	}
	106
	107
[1008]	108	/******************************************************************/
	109	/* class VspNode implementation */
	110	/******************************************************************/
	111
	112
	113	VspNode::VspNode():
	114	mParent(NULL), mTreeValid(true), mTimeStamp(0)
	115	{}
	116
	117
	118	VspNode::VspNode(VspInterior *parent):
	119	mParent(parent), mTreeValid(true)
	120	{}
	121
	122
	123	bool VspNode::IsRoot() const
	124	{
	125	return mParent == NULL;
	126	}
	127
	128
	129	VspInterior *VspNode::GetParent()
	130	{
	131	return mParent;
	132	}
	133
	134
	135	void VspNode::SetParent(VspInterior *parent)
	136	{
	137	mParent = parent;
	138	}
	139
	140
	141	bool VspNode::IsSibling(VspNode *n) const
	142	{
	143	return ((this != n) && mParent &&
	144	(mParent->GetFront() == n) \|\| (mParent->GetBack() == n));
	145	}
	146
	147
	148	int VspNode::GetDepth() const
	149	{
	150	int depth = 0;
	151	VspNode *p = mParent;
	152
	153	while (p)
	154	{
	155	p = p->mParent;
	156	++ depth;
	157	}
	158
	159	return depth;
	160	}
	161
	162
	163	bool VspNode::TreeValid() const
	164	{
	165	return mTreeValid;
	166	}
	167
	168
	169	void VspNode::SetTreeValid(const bool v)
	170	{
	171	mTreeValid = v;
	172	}
	173
	174
	175	/****************************************************************/
	176	/* class VspInterior implementation */
	177	/****************************************************************/
	178
	179
	180	VspInterior::VspInterior(const AxisAlignedPlane &plane):
	181	mPlane(plane), mFront(NULL), mBack(NULL)
	182	{}
	183
[1011]	184
[1008]	185	VspInterior::~VspInterior()
	186	{
	187	DEL_PTR(mFront);
	188	DEL_PTR(mBack);
	189	}
	190
[1011]	191
[1008]	192	bool VspInterior::IsLeaf() const
	193	{
	194	return false;
	195	}
	196
[1011]	197
[1008]	198	VspNode *VspInterior::GetBack()
	199	{
	200	return mBack;
	201	}
	202
[1011]	203
[1008]	204	VspNode *VspInterior::GetFront()
	205	{
	206	return mFront;
	207	}
	208
[1011]	209
[1008]	210	AxisAlignedPlane VspInterior::GetPlane() const
	211	{
	212	return mPlane;
	213	}
	214
[1011]	215
[1012]	216	float VspInterior::GetPosition() const
	217	{
	218	return mPlane.mPosition;
	219	}
	220
	221
	222	int VspInterior::GetAxis() const
	223	{
	224	return mPlane.mAxis;
	225	}
	226
	227
[1008]	228	void VspInterior::ReplaceChildLink(VspNode oldChild, VspNode newChild)
	229	{
	230	if (mBack == oldChild)
	231	mBack = newChild;
	232	else
	233	mFront = newChild;
	234	}
	235
[1011]	236
[1008]	237	void VspInterior::SetupChildLinks(VspNode b, VspNode f)
	238	{
	239	mBack = b;
	240	mFront = f;
	241	}
	242
	243
[1016]	244	AxisAlignedBox3 VspInterior::GetBoundingBox() const
[1012]	245	{
[1016]	246	return mBoundingBox;
[1012]	247	}
	248
	249
[1016]	250	void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
[1012]	251	{
[1016]	252	mBoundingBox = box;
[1012]	253	}
	254
	255
	256	int VspInterior::Type() const
	257	{
	258	return Interior;
	259	}
	260
[1027]	261
	262
[1008]	263	/****************************************************************/
	264	/* class VspLeaf implementation */
	265	/****************************************************************/
	266
	267
	268	VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
	269	{
	270	}
	271
	272
	273	VspLeaf::~VspLeaf()
	274	{
	275	DEL_PTR(mPvs);
	276	}
	277
[1021]	278
[1012]	279	int VspLeaf::Type() const
	280	{
	281	return Leaf;
	282	}
[1008]	283
[1012]	284
[1008]	285	VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
	286	mViewCell(viewCell)
	287	{
	288	}
	289
	290
	291	VspLeaf::VspLeaf(VspInterior *parent):
	292	VspNode(parent), mViewCell(NULL), mPvs(NULL)
	293	{}
	294
	295
	296
	297	VspLeaf::VspLeaf(VspInterior parent, ViewCellLeaf viewCell):
	298	VspNode(parent), mViewCell(viewCell), mPvs(NULL)
	299	{
	300	}
	301
	302	ViewCellLeaf *VspLeaf::GetViewCell() const
	303	{
	304	return mViewCell;
	305	}
	306
	307	void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
	308	{
	309	mViewCell = viewCell;
	310	}
	311
	312
	313	bool VspLeaf::IsLeaf() const
	314	{
	315	return true;
	316	}
	317
	318
[1002]	319	/******************************************************************************/
[1016]	320	/* class VspTree implementation */
[1002]	321	/******************************************************************************/
	322
	323
[1016]	324	VspTree::VspTree():
[1002]	325	mRoot(NULL),
	326	mOutOfBoundsCell(NULL),
	327	mStoreRays(false),
	328	mTimeStamp(1)
	329	{
	330	bool randomize = false;
[1016]	331	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
[1002]	332	if (randomize)
	333	Randomize(); // initialise random generator for heuristics
	334
	335	//-- termination criteria for autopartition
[1016]	336	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
	337	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
	338	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
	339	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
	340	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
[1023]	341
[1016]	342	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
	343	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
[1002]	344
	345	//-- max cost ratio for early tree termination
[1016]	346	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[1002]	347
[1016]	348	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	349	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
[1002]	350
	351	// HACK//mTermMinPolygons = 25;
	352
	353	//-- factors for bsp tree split plane heuristics
[1016]	354	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
[1002]	355
	356	//-- partition criteria
[1016]	357	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
[1002]	358
	359	// if only the driving axis is used for axis aligned split
[1016]	360	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[1002]	361
[1016]	362	//Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
	363	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
[1002]	364
[1016]	365	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
	366	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
[1002]	367
[1023]	368
[1002]	369	char subdivisionStatsLog[100];
[1016]	370	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
[1002]	371	mSubdivisionStats.open(subdivisionStatsLog);
	372
[1016]	373	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
	374	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
[1006]	375
[1002]	376
	377	//-- debug output
	378
	379	Debug << "***** VSP BSP options ****** " << endl;
	380	Debug << "max depth: " << mTermMaxDepth << endl;
	381	Debug << "min PVS: " << mTermMinPvs << endl;
	382	Debug << "min probabiliy: " << mTermMinProbability << endl;
	383	Debug << "min rays: " << mTermMinRays << endl;
	384	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	385	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	386	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	387	Debug << "max view cells: " << mMaxViewCells << endl;
	388	Debug << "randomize: " << randomize << endl;
	389
	390	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	391	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	392	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	393	Debug << "max memory: " << mMaxMemory << endl;
	394	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	395	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1023]	396
[1002]	397	Debug << "circulating axis: " << mCirculatingAxis << endl;
	398	Debug << "minband: " << mMinBand << endl;
	399	Debug << "maxband: " << mMaxBand << endl;
[1006]	400
[1002]	401
	402	mSplitCandidates = new vector<SortableEntry>;
	403
	404	Debug << endl;
	405	}
	406
	407
[1016]	408	VspViewCell *VspTree::GetOutOfBoundsCell()
[1002]	409	{
	410	return mOutOfBoundsCell;
	411	}
	412
	413
[1016]	414	VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
[1002]	415	{
	416	if (!mOutOfBoundsCell)
	417	{
[1008]	418	mOutOfBoundsCell = new VspViewCell();
[1002]	419	mOutOfBoundsCell->SetId(-1);
	420	mOutOfBoundsCell->SetValid(false);
	421	}
	422
	423	return mOutOfBoundsCell;
	424	}
	425
	426
[1016]	427	const VspTreeStatistics &VspTree::GetStatistics() const
[1002]	428	{
[1008]	429	return mVspStats;
[1002]	430	}
	431
	432
[1016]	433	VspTree::~VspTree()
[1002]	434	{
	435	DEL_PTR(mRoot);
	436	DEL_PTR(mSplitCandidates);
	437	}
	438
[1008]	439
[1020]	440	void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
	441	AxisAlignedBox3 *forcedBoundingBox)
[1002]	442	{
[1008]	443	mVspStats.nodes = 1;
[1027]	444
[1002]	445	if (forcedBoundingBox)
[1027]	446	{
[1020]	447	mBoundingBox = *forcedBoundingBox;
[1027]	448	}
	449	else // compute vsp tree bounding box
[1002]	450	{
[1027]	451	mBoundingBox.Initialize();
[1002]	452
[1027]	453	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
	454
	455	//-- compute bounding box
	456	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
[1002]	457	{
[1027]	458	VssRay ray = rit;
	459
	460	// compute bounding box of view space
[1020]	461	mBoundingBox.Include(ray->GetTermination());
	462	mBoundingBox.Include(ray->GetOrigin());
[1002]	463	}
	464
[1027]	465	mTermMinProbability *= mBoundingBox.GetVolume();
	466	mGlobalCostMisses = 0;
	467	}
[1020]	468	}
[1002]	469
	470
[1020]	471	void VspTree::AddSubdivisionStats(const int viewCells,
	472	const float renderCostDecr,
	473	const float splitCandidateCost,
	474	const float totalRenderCost,
[1027]	475	const float avgRenderCost)
[1020]	476	{
	477	mSubdivisionStats
	478	<< "#ViewCells\n" << viewCells << endl
	479	<< "#RenderCostDecrease\n" << renderCostDecr << endl
	480	<< "#SplitCandidateCost\n" << splitCandidateCost << endl
	481	<< "#TotalRenderCost\n" << totalRenderCost << endl
	482	<< "#AvgRenderCost\n" << avgRenderCost << endl;
[1002]	483	}
	484
	485
	486	// TODO: return memory usage in MB
[1016]	487	float VspTree::GetMemUsage() const
[1002]	488	{
	489	return (float)
[1016]	490	(sizeof(VspTree) +
[1008]	491	mVspStats.Leaves() * sizeof(VspLeaf) +
[1010]	492	mCreatedViewCells * sizeof(VspViewCell) +
[1008]	493	mVspStats.pvs * sizeof(ObjectPvsData) +
	494	mVspStats.Interior() * sizeof(VspInterior) +
	495	mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
[1002]	496	}
	497
	498
[1016]	499	bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
[1002]	500	{
	501	return
[1027]	502	#if TODO
[1002]	503	(((int)data.mRays->size() <= mTermMinRays) \|\|
	504	(data.mPvs <= mTermMinPvs) \|\|
	505	(data.mProbability <= mTermMinProbability) \|\|
	506	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
	507	(data.mDepth >= mTermMaxDepth));
[1027]	508	#else
	509	false;
	510	#endif
[1002]	511	}
	512
	513
[1016]	514	bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
[1002]	515	{
	516	return
[1027]	517	#if TODO
[1011]	518	(mOutOfMemory \|\|
	519	(mVspStats.Leaves() >= mMaxViewCells) \|\|
	520	(mGlobalCostMisses >= mTermGlobalCostMissTolerance));
[1027]	521	#else
	522	(mVspStats.Leaves() >= mMaxViewCells) ;
	523	#endif
[1002]	524	}
	525
	526
[1016]	527	VspNode *VspTree::Subdivide(SplitQueue &tQueue,
[1020]	528	VspSplitCandidate &splitCandidate,
	529	const bool globalCriteriaMet)
[1002]	530	{
[1016]	531	VspTraversalData &tData = splitCandidate.mParentData;
[1002]	532
[1008]	533	VspNode *newNode = tData.mNode;
[1002]	534
[1020]	535	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
[1002]	536	{
[1016]	537	VspTraversalData tFrontData;
	538	VspTraversalData tBackData;
[1002]	539
	540	//-- continue subdivision
	541
	542	// create new interior node and two leaf node
[1008]	543	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
[1006]	544	newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
[1002]	545
	546	const int maxCostMisses = splitCandidate.mMaxCostMisses;
	547
	548
	549	// how often was max cost ratio missed in this branch?
	550	tFrontData.mMaxCostMisses = maxCostMisses;
	551	tBackData.mMaxCostMisses = maxCostMisses;
	552
[1020]	553	//-- statistics
[1002]	554	if (1)
	555	{
[1020]	556	const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
	557	const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
	558	const float cData = (float)tData.mPvs * tData.mProbability;
	559
	560	const float costDecr =
	561	(cFront + cBack - cData) / mBoundingBox.GetVolume();
[1002]	562
	563	mTotalCost += costDecr;
	564	mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
	565
[1020]	566	AddSubdivisionStats(mVspStats.Leaves(),
	567	-costDecr,
	568	splitCandidate.GetPriority(),
	569	mTotalCost,
	570	(float)mTotalPvsSize / (float)mVspStats.Leaves());
[1002]	571	}
	572
	573
[1020]	574	//-- push the new split candidates on the queue
	575	VspSplitCandidate *frontCandidate = new VspSplitCandidate();
	576	VspSplitCandidate *backCandidate = new VspSplitCandidate();
[1002]	577
[1020]	578	EvalSplitCandidate(tFrontData, *frontCandidate);
	579	EvalSplitCandidate(tBackData, *backCandidate);
	580
[1002]	581	tQueue.push(frontCandidate);
	582	tQueue.push(backCandidate);
[1020]	583
[1002]	584	// delete old leaf node
	585	DEL_PTR(tData.mNode);
	586	}
	587
	588
	589	//-- terminate traversal and create new view cell
	590	if (newNode->IsLeaf())
	591	{
[1008]	592	VspLeaf leaf = dynamic_cast<VspLeaf >(newNode);
[1020]	593
[1010]	594	VspViewCell *viewCell = new VspViewCell();
[1002]	595	leaf->SetViewCell(viewCell);
	596
	597	//-- update pvs
	598	int conSamp = 0;
	599	float sampCon = 0.0f;
	600	AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
	601
	602	// update scalar pvs size value
	603	mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
	604
[1008]	605	mVspStats.contributingSamples += conSamp;
	606	mVspStats.sampleContributions +=(int) sampCon;
[1002]	607
	608	//-- store additional info
	609	if (mStoreRays)
	610	{
	611	RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
	612	for (it = tData.mRays->begin(); it != it_end; ++ it)
	613	{
	614	(*it).mRay->Ref();
	615	leaf->mVssRays.push_back((*it).mRay);
	616	}
	617	}
[1020]	618
[1002]	619	viewCell->mLeaf = leaf;
	620
[1006]	621	viewCell->SetVolume(tData.mProbability);
[1002]	622	leaf->mProbability = tData.mProbability;
	623
[1020]	624	// finally evaluate stats until this leaf
	625	EvaluateLeafStats(tData);
[1002]	626	}
	627
	628	//-- cleanup
	629	tData.Clear();
[1020]	630
[1002]	631	return newNode;
	632	}
	633
	634
[1016]	635	void VspTree::EvalSplitCandidate(VspTraversalData &tData,
[1027]	636	VspSplitCandidate &splitCandidate)
[1002]	637	{
[1020]	638	float frontProb;
[1027]	639	float backProb;
[1020]	640
[1008]	641	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
[1020]	642
[1002]	643	// compute locally best split plane
[1008]	644	const bool success =
[1027]	645	SelectSplitPlane(tData, splitCandidate.mSplitPlane, frontProb, backProb);
[1008]	646
[1002]	647	// compute global decrease in render cost
[1027]	648	splitCandidate.mPriority = EvalRenderCostDecrease(splitCandidate.mSplitPlane, tData);
	649	splitCandidate.mParentData = tData;
	650	splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
	651
	652	Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
[1002]	653	}
	654
	655
[1016]	656	VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
	657	VspTraversalData &tData,
	658	VspTraversalData &frontData,
	659	VspTraversalData &backData)
[1002]	660	{
[1008]	661	VspLeaf leaf = dynamic_cast<VspLeaf >(tData.mNode);
[1002]	662
	663	//-- the front and back traversal data is filled with the new values
	664	frontData.mDepth = tData.mDepth + 1;
	665	frontData.mRays = new RayInfoContainer();
	666
	667	backData.mDepth = tData.mDepth + 1;
	668	backData.mRays = new RayInfoContainer();
	669
	670	//-- subdivide rays
	671	SplitRays(splitPlane,
	672	*tData.mRays,
	673	*frontData.mRays,
	674	*backData.mRays);
	675
[1027]	676	Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
[1011]	677	//-- compute pvs
[1002]	678	frontData.mPvs = ComputePvsSize(*frontData.mRays);
	679	backData.mPvs = ComputePvsSize(*backData.mRays);
	680
	681	// split front and back node geometry and compute area
[1006]	682	tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
	683	frontData.mBoundingBox, backData.mBoundingBox);
[1002]	684
	685
[1006]	686	frontData.mProbability = frontData.mBoundingBox.GetVolume();
	687	backData.mProbability = tData.mProbability - frontData.mProbability;
[1002]	688
	689
[1006]	690	///////////////////////////////////////////
[1002]	691	// subdivide further
	692
	693	// store maximal and minimal depth
[1008]	694	if (tData.mDepth > mVspStats.maxDepth)
[1002]	695	{
[1008]	696	Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
	697	mVspStats.maxDepth = tData.mDepth;
[1002]	698	}
	699
[1008]	700	mVspStats.nodes += 2;
[1002]	701
	702
[1008]	703	VspInterior *interior = new VspInterior(splitPlane);
[1002]	704
	705	#ifdef _DEBUG
	706	Debug << interior << endl;
	707	#endif
	708
	709
	710	//-- create front and back leaf
	711
[1008]	712	VspInterior *parent = leaf->GetParent();
[1002]	713
	714	// replace a link from node's parent
	715	if (parent)
	716	{
	717	parent->ReplaceChildLink(leaf, interior);
	718	interior->SetParent(parent);
	719	}
	720	else // new root
	721	{
	722	mRoot = interior;
	723	}
	724
	725	// and setup child links
[1008]	726	interior->SetupChildLinks(new VspLeaf(interior), new VspLeaf(interior));
[1016]	727	// add bounding box
	728	interior->SetBoundingBox(tData.mBoundingBox);
[1002]	729
	730	frontData.mNode = interior->GetFront();
	731	backData.mNode = interior->GetBack();
	732
	733	interior->mTimeStamp = mTimeStamp ++;
	734
	735	return interior;
	736	}
	737
	738
[1016]	739	void VspTree::AddToPvs(VspLeaf *leaf,
[1002]	740	const RayInfoContainer &rays,
	741	float &sampleContributions,
	742	int &contributingSamples)
	743	{
	744	sampleContributions = 0;
	745	contributingSamples = 0;
	746
	747	RayInfoContainer::const_iterator it, it_end = rays.end();
	748
	749	ViewCellLeaf *vc = leaf->GetViewCell();
	750
	751	// add contributions from samples to the PVS
	752	for (it = rays.begin(); it != it_end; ++ it)
	753	{
	754	float sc = 0.0f;
	755	VssRay ray = (it).mRay;
	756
	757	bool madeContrib = false;
	758	float contribution;
	759
	760	if (ray->mTerminationObject)
	761	{
	762	if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
	763	madeContrib = true;
	764	sc += contribution;
	765	}
	766
	767	if (ray->mOriginObject)
	768	{
	769	if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
	770	madeContrib = true;
	771	sc += contribution;
	772	}
[1047]	773
	774	sampleContributions += sc;
[1002]	775
[1047]	776	if (madeContrib)
	777	++ contributingSamples;
[1002]	778
[1072]	779	// warning: rays get never deleted!
[1052]	780	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
[1002]	781	}
	782	}
	783
	784
[1047]	785	void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
	786	const int axis,
	787	float minBand,
	788	float maxBand)
[1002]	789	{
	790	mSplitCandidates->clear();
	791
	792	int requestedSize = 2 * (int)(rays.size());
[1047]	793
[1002]	794	// creates a sorted split candidates array
	795	if (mSplitCandidates->capacity() > 500000 &&
	796	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
	797	{
	798	delete mSplitCandidates;
	799	mSplitCandidates = new vector<SortableEntry>;
	800	}
	801
	802	mSplitCandidates->reserve(requestedSize);
	803
	804	float pos;
	805
	806	if (0)
	807	{
[1072]	808	// float values => don't compare with exact values
[1002]	809	minBand += Limits::Small;
	810	maxBand -= Limits::Small;
	811	}
	812
	813	// insert all queries
	814	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
	815	{
	816	const bool positive = (*ri).mRay->HasPosDir(axis);
	817
	818	pos = (*ri).ExtrapOrigin(axis);
	819
[1072]	820	if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
[1002]	821	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
	822	pos, (*ri).mRay));
	823
	824	pos = (*ri).ExtrapTermination(axis);
	825
[1072]	826	if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
	827
[1002]	828	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
	829	pos, (*ri).mRay));
	830	}
	831
	832	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
	833	}
	834
	835
[1072]	836	int VspTree::GetPvsContribution(Intersectable *object) const
	837	{
	838	int pvsContri = 0;
	839
	840	KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
	841
	842	Intersectable::NewMail();
	843
	844	// Search kd leaves this object is attached to
	845	for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	846	{
	847	KdNode l = (kit).first;
	848
	849	// new object found during sweep
	850	// => increase pvs contribution of this kd node
	851	if (!l->Mailed())
	852	{
	853	l->Mail();
	854	++ pvsContri;
	855	}
	856	}
	857
	858	return pvsContri;
	859	}
	860
	861
	862	void VspTree::PrepareHeuristics(const RayInfoContainer &rays)
	863	{
	864	ObjectContainer objects;
	865
	866	// Collect all pvs that can be seen from the view cell
	867	CollectPvs(rays, objects);
	868
	869	// adjust kd node info table
	870	// for each object the entry must be updated
	871	// which belongs to the same kd nodes
	872	ObjectContainer::const_iterator oit, oit_end = objects.end();
	873
	874	for (oit = objects.begin(); oit != oit_end; ++ oit)
	875	{
	876	Intersectable obj = oit;
	877	// TODO
	878	//UpdateKdNodeInfo(obj);
	879	}
	880	}
	881
	882
	883	int VspTree::GetPvsIncr(Intersectable *object, const KdPvsMap &activeNodes)
	884	{
	885	// TODO:
	886	// use kd info table to apply set theory in order to
	887	// sort out dublicate pvs entries due to objects which
	888	// belong to more than one kd leaves.
	889	#if TODO
	890	KdPvsMap::const_iterator kit, kit_end = obj->mKdPvs.mEntries.end();
	891
	892	// Search kd leaves this object is attached to
	893	for (kit = obj->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	894	{
	895	KdNode l = (kit).first;
	896
	897	// new object found during sweep
	898	// => increase pvs contribution of this kd node
	899	if (!l->Mailed())
	900	{
	901	l->Mail();
	902	++ pvsContr;
	903	}
	904	}
	905	#endif
	906	return 0;
	907	}
	908
	909
[1027]	910	float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
	911	const AxisAlignedBox3 &box,
	912	const int pvsSize,
	913	const int axis,
	914	float &position)
[1002]	915	{
	916	const float minBox = box.Min(axis);
	917	const float maxBox = box.Max(axis);
	918
	919	const float sizeBox = maxBox - minBox;
	920
	921	const float minBand = minBox + mMinBand * sizeBox;
	922	const float maxBand = minBox + mMaxBand * sizeBox;
	923
	924	SortSplitCandidates(rays, axis, minBand, maxBand);
	925
	926	// go through the lists, count the number of objects left and right
	927	// and evaluate the following cost funcion:
	928	// C = ct_div_ci + (qlrl + qrrr)/queries
	929
	930	int pvsl = 0;
	931	int pvsr = pvsSize;
	932
	933	int pvsBack = pvsl;
	934	int pvsFront = pvsr;
	935
	936	float sum = (float)pvsSize * sizeBox;
	937	float minSum = 1e20f;
	938
	939
[1047]	940	// if no good split can be found, take mid split
[1002]	941	position = minBox + 0.5f * sizeBox;
	942
	943	// the relative cost ratio
	944	float ratio = /Limits::Infinity;/99999999.0f;
	945	bool splitPlaneFound = false;
	946
	947	Intersectable::NewMail();
	948
	949	RayInfoContainer::const_iterator ri, ri_end = rays.end();
	950
[1072]	951	//-- set all object as belonging to the front pvs
	952
[1002]	953	for(ri = rays.begin(); ri != ri_end; ++ ri)
	954	{
	955	Intersectable oObject = (ri).mRay->mOriginObject;
	956	Intersectable tObject = (ri).mRay->mTerminationObject;
	957
	958	if (oObject)
	959	{
	960	if (!oObject->Mailed())
	961	{
	962	oObject->Mail();
	963	oObject->mCounter = 1;
	964	}
	965	else
	966	{
	967	++ oObject->mCounter;
	968	}
	969	}
	970	if (tObject)
	971	{
	972	if (!tObject->Mailed())
	973	{
	974	tObject->Mail();
	975	tObject->mCounter = 1;
	976	}
	977	else
	978	{
	979	++ tObject->mCounter;
	980	}
	981	}
	982	}
	983
	984	Intersectable::NewMail();
	985
	986	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
	987
	988	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
	989	{
	990	VssRay *ray;
	991	ray = (*ci).ray;
	992
	993	Intersectable *oObject = ray->mOriginObject;
	994	Intersectable *tObject = ray->mTerminationObject;
	995
	996
	997	switch ((*ci).type)
	998	{
	999	case SortableEntry::ERayMin:
	1000	{
	1001	if (oObject && !oObject->Mailed())
	1002	{
	1003	oObject->Mail();
	1004	++ pvsl;
	1005	}
	1006	if (tObject && !tObject->Mailed())
	1007	{
	1008	tObject->Mail();
	1009	++ pvsl;
	1010	}
	1011	break;
	1012	}
	1013	case SortableEntry::ERayMax:
	1014	{
	1015	if (oObject)
	1016	{
	1017	if (-- oObject->mCounter == 0)
	1018	-- pvsr;
	1019	}
	1020
	1021	if (tObject)
	1022	{
	1023	if (-- tObject->mCounter == 0)
	1024	-- pvsr;
	1025	}
	1026
	1027	break;
	1028	}
	1029	}
	1030
	1031
	1032	// Note: sufficient to compare size of bounding boxes of front and back side?
	1033	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	1034	{
	1035	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
	1036
	1037	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl;
	1038	//Debug << "cost= " << sum << endl;
	1039
	1040	if (sum < minSum)
	1041	{
	1042	splitPlaneFound = true;
	1043
	1044	minSum = sum;
	1045	position = (*ci).value;
	1046
	1047	pvsBack = pvsl;
	1048	pvsFront = pvsr;
	1049	}
	1050	}
	1051	}
	1052
	1053
	1054	// -- compute cost
[1047]	1055
[1002]	1056	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1057	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1058
	1059	const float pOverall = sizeBox;
	1060	const float pBack = position - minBox;
	1061	const float pFront = maxBox - position;
[1047]	1062
	1063	/*const float pOverall = box.GetVolume();
	1064
	1065	AxisAlignedBox3 bbox;
	1066	AxisAlignedBox3 fbox;
	1067
	1068	box.Split(axis, position, bbox, fbox);
	1069
	1070	const float pBack = fbox.GetVolume();
	1071	const float pFront = bbox.GetVolume();*/
	1072
[1002]	1073	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	1074	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1075	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1076
[1047]	1077	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
[1002]	1078	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1079
	1080	if (splitPlaneFound)
	1081	{
[1047]	1082	ratio = newRenderCost / oldRenderCost;
[1002]	1083	}
	1084	//if (axis != 1)
	1085	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1086	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
	1087
	1088	return ratio;
	1089	}
	1090
	1091
[1072]	1092	void VspTree::EvalPvsIncr(ObjectMap &multipleObjects,
	1093	KdLeaf *leaf,
	1094	const SortableEntry &ci,
	1095	int &pvsLeft,
	1096	int &pvsRight) const
	1097	{
	1098	int pvsSize = 0;
	1099
	1100	if (ci.type == SortableEntry::ERayMin)
	1101	{
	1102	if (!leaf->Mailed())
	1103	{
	1104	leaf->Mail();
	1105	pvsLeft += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
	1106
	1107	// add duplicates
	1108	ObjectMap::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
	1109
	1110	for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
	1111	{
	1112	const int id = (*oit)->first;
	1113	Intersectable object = (oit)->second;
	1114
	1115	if (multipleObjects[id] != object) // object not previously in pvs
	1116	{
	1117	multipleObjects[id] = object;
	1118	++ pvsLeft;
	1119	}
	1120
	1121	}
	1122	}
	1123	}
	1124	else if (ci.type == SortableEntry::ERayMax)
	1125	{
	1126	if (-- leaf->mCounter == 0)
	1127	pvsRight += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
	1128	}
	1129	}
	1130
	1131
	1132	float VspTree::EvalKdCostHeuristics(const RayInfoContainer &rays,
	1133	const AxisAlignedBox3 &box,
	1134	const int pvsSize,
	1135	const int axis,
	1136	float &position)
	1137	{
	1138	const float minBox = box.Min(axis);
	1139	const float maxBox = box.Max(axis);
	1140
	1141	const float sizeBox = maxBox - minBox;
	1142
	1143	const float minBand = minBox + mMinBand * sizeBox;
	1144	const float maxBand = minBox + mMaxBand * sizeBox;
	1145
	1146	SortSplitCandidates(rays, axis, minBand, maxBand);
	1147
	1148	// go through the lists, count the number of objects left and right
	1149	// and evaluate the following cost funcion:
	1150	// C = ct_div_ci + (qlrl + qrrr)/queries
	1151
	1152	int pvsl = 0;
	1153	int pvsr = pvsSize;
	1154
	1155	int pvsBack = pvsl;
	1156	int pvsFront = pvsr;
	1157
	1158	float sum = (float)pvsSize * sizeBox;
	1159	float minSum = 1e20f;
	1160
	1161
	1162	// if no good split can be found, take mid split
	1163	position = minBox + 0.5f * sizeBox;
	1164
	1165	// the relative cost ratio
	1166	float ratio = /Limits::Infinity;/99999999.0f;
	1167	bool splitPlaneFound = false;
	1168
	1169	Intersectable::NewMail();
	1170	KdNode::NewMail();
	1171
	1172	RayInfoContainer::const_iterator ri, ri_end = rays.end();
	1173
	1174	//-- set all kd nodes as belonging to the front pvs
	1175
	1176	for (ri = rays.begin(); ri != ri_end; ++ ri)
	1177	{
	1178	Intersectable oObject = (ri).mRay->mOriginObject;
	1179
	1180	if (oObject)
	1181	{
	1182	KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
	1183
	1184	for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	1185	{
	1186	KdNode node = (kit).first;
	1187
	1188	if (!node->Mailed())
	1189	{
	1190	node->Mail();
	1191	//node->mCounter = 1;
	1192	}
	1193	else
	1194	{
	1195	//++ node->mCounter;
	1196	}
	1197	}
	1198	}
	1199
	1200	Intersectable tObject = (ri).mRay->mTerminationObject;
	1201
	1202	if (tObject)
	1203	{
	1204	KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
	1205
	1206	for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	1207	{
	1208	KdNode node = (kit).first;
	1209
	1210	if (!node->Mailed())
	1211	{
	1212	node->Mail();
	1213	//node->mCounter = 1;
	1214	}
	1215	else
	1216	{
	1217	//++ node->mCounter;
	1218	}
	1219	}
	1220	}
	1221	}
	1222
	1223	Intersectable::NewMail();
	1224
	1225	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
	1226
	1227	ObjectMap multipleObjectsLeft, multipleObjectsRight;
	1228
	1229
	1230	// -- traverse through visibility events
	1231
	1232	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
	1233	{
	1234	VssRay *ray;
	1235	ray = (*ci).ray;
	1236
	1237	Intersectable *oObject = ray->mOriginObject;
	1238
	1239	KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
	1240
	1241	if (oObject)
	1242	{
	1243	for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	1244	{
	1245	KdLeaf node = dynamic_cast<KdLeaf >((*kit).first);
	1246
	1247	EvalPvsIncr(multipleObjectsLeft, node, *ci, pvsl, pvsr);
	1248	}
	1249	}
	1250
	1251	Intersectable *tObject = ray->mOriginObject;
	1252
	1253	if (tObject)
	1254	{
	1255	for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
	1256	{
	1257	KdLeaf node = dynamic_cast<KdLeaf >((*kit).first);
	1258
	1259	EvalPvsIncr(multipleObjectsRight, node, *ci, pvsl, pvsr);
	1260	}
	1261	}
	1262
	1263
	1264	// Note: sufficient to compare size of bounding boxes of front and back side?
	1265	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	1266	{
	1267	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
	1268
	1269	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl;
	1270	//Debug << "cost= " << sum << endl;
	1271
	1272	if (sum < minSum)
	1273	{
	1274	splitPlaneFound = true;
	1275
	1276	minSum = sum;
	1277	position = (*ci).value;
	1278
	1279	pvsBack = pvsl;
	1280	pvsFront = pvsr;
	1281	}
	1282	}
	1283	}
	1284
	1285
	1286	// -- compute cost
	1287
	1288	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1289	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1290
	1291	const float pOverall = sizeBox;
	1292	const float pBack = position - minBox;
	1293	const float pFront = maxBox - position;
	1294
	1295	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	1296	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1297	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1298
	1299	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
	1300	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1301
	1302	if (splitPlaneFound)
	1303	{
	1304	ratio = newRenderCost / oldRenderCost;
	1305	}
	1306	//if (axis != 1)
	1307	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1308	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
	1309
	1310	return ratio;
	1311	}
	1312
	1313
	1314	#if TODO
	1315
	1316	float VspTree::EvalLocalCostHeuristicsNonIncremential(const RayInfoContainer &rays,
	1317	const AxisAlignedBox3 &box,
	1318	const int pvsSize,
	1319	const int axis,
	1320	float &position)
	1321	{
	1322	const float minBox = box.Min(axis);
	1323	const float maxBox = box.Max(axis);
	1324
	1325	const float sizeBox = maxBox - minBox;
	1326
	1327	const float minBand = minBox + mMinBand * sizeBox;
	1328	const float maxBand = minBox + mMaxBand * sizeBox;
	1329
	1330	SortSplitCandidates(rays, axis, minBand, maxBand);
	1331
	1332	// go through the lists, count the number of objects left and right
	1333	// and evaluate the following cost funcion:
	1334	// C = ct_div_ci + (qlrl + qrrr)/queries
	1335
	1336	int pvsl = 0;
	1337	int pvsr = pvsSize;
	1338
	1339	int pvsBack = pvsl;
	1340	int pvsFront = pvsr;
	1341
	1342	float sum = (float)pvsSize * sizeBox;
	1343	float minSum = 1e20f;
	1344
	1345
	1346	// if no good split can be found, take mid split
	1347	position = minBox + 0.5f * sizeBox;
	1348
	1349	// the relative cost ratio
	1350	float ratio = /Limits::Infinity;/99999999.0f;
	1351	bool splitPlaneFound = false;
	1352
	1353	Intersectable::NewMail();
	1354
	1355	RayInfoContainer::const_iterator ri, ri_end = rays.end();
	1356
	1357	//-- set all object as belonging to the front pvs
	1358
	1359	for(ri = rays.begin(); ri != ri_end; ++ ri)
	1360	{
	1361	// Note: sufficient to compare size of bounding boxes of front and back side?
	1362	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	1363	{
	1364	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
	1365
	1366	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl;
	1367	//Debug << "cost= " << sum << endl;
	1368
	1369	if (sum < minSum)
	1370	{
	1371	splitPlaneFound = true;
	1372
	1373	minSum = sum;
	1374	position = (*ci).value;
	1375
	1376	pvsBack = pvsl;
	1377	pvsFront = pvsr;
	1378	}
	1379	}
	1380	}
	1381
	1382
	1383	// -- compute cost
	1384
	1385	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1386	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1387
	1388	const float pOverall = sizeBox;
	1389	const float pBack = position - minBox;
	1390	const float pFront = maxBox - position;
	1391
	1392
	1393	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	1394	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1395	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1396
	1397	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
	1398	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1399
	1400	if (splitPlaneFound)
	1401	{
	1402	ratio = newRenderCost / oldRenderCost;
	1403	}
	1404	//if (axis != 1)
	1405	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1406	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
	1407
	1408	return ratio;
	1409	}
	1410	#endif
	1411
	1412
[1027]	1413	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
	1414	AxisAlignedPlane &plane,
	1415	float &pFront,
	1416	float &pBack)
[1002]	1417	{
	1418	float nPosition[3];
	1419	float nCostRatio[3];
	1420	float nProbFront[3];
	1421	float nProbBack[3];
	1422
	1423	// create bounding box of node geometry
[1006]	1424	AxisAlignedBox3 box = tData.mBoundingBox;
[1002]	1425
	1426	int sAxis = 0;
[1006]	1427	int bestAxis = -1;
[1002]	1428
[1047]	1429	//mOnlyDrivingAxis = true;
	1430
[1002]	1431	// if we use some kind of specialised fixed axis
	1432	const bool useSpecialAxis =
[1023]	1433	mOnlyDrivingAxis \|\| mCirculatingAxis;
[1047]	1434	Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
	1435	if (mCirculatingAxis)
	1436	{
	1437	int parentAxis = 0;
	1438	VspNode *parent = tData.mNode->GetParent();
[1002]	1439
[1047]	1440	if (parent)
	1441	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
[1027]	1442
	1443	sAxis = (parentAxis + 1) % 3;
[1047]	1444	}
[1002]	1445	else if (mOnlyDrivingAxis)
[1047]	1446	{
[1002]	1447	sAxis = box.Size().DrivingAxis();
[1047]	1448	}
	1449	//sAxis = 2;
	1450	for (int axis = 0; axis < 3; ++ axis)
[1002]	1451	{
	1452	if (!useSpecialAxis \|\| (axis == sAxis))
	1453	{
	1454	//-- place split plane using heuristics
	1455
	1456	if (mUseCostHeuristics)
	1457	{
	1458	nCostRatio[axis] =
[1027]	1459	EvalLocalCostHeuristics(*tData.mRays,
	1460	box,
[1002]	1461	tData.mPvs,
	1462	axis,
	1463	nPosition[axis]);
	1464	}
[1006]	1465	else //-- split plane position is spatial median
[1002]	1466	{
	1467	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	1468
[1027]	1469	nCostRatio[axis] = EvalLocalSplitCost(tData,
	1470	box,
	1471	axis,
	1472	nPosition[axis],
	1473	nProbFront[axis],
	1474	nProbBack[axis]);
[1002]	1475	}
	1476
[1006]	1477	if (bestAxis == -1)
[1002]	1478	{
[1006]	1479	bestAxis = axis;
[1002]	1480	}
[1006]	1481	else if (nCostRatio[axis] < nCostRatio[bestAxis])
[1002]	1482	{
[1047]	1483	Debug << "old: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1006]	1484	bestAxis = axis;
[1047]	1485
	1486	Debug << "new: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1002]	1487	}
	1488	}
	1489	}
	1490
[1047]	1491
[1002]	1492	//-- assign values
[1047]	1493
[1006]	1494	plane.mAxis = bestAxis;
[1047]	1495	// split plane position
	1496	plane.mPosition = nPosition[bestAxis];
	1497
[1002]	1498	pFront = nProbFront[bestAxis];
	1499	pBack = nProbBack[bestAxis];
	1500
	1501
[1047]	1502	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1002]	1503	return nCostRatio[bestAxis];
	1504	}
	1505
	1506
[1016]	1507	inline void VspTree::GenerateUniqueIdsForPvs()
[1002]	1508	{
	1509	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
	1510	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
	1511	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
	1512	}
	1513
	1514
[1016]	1515	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	1516	const VspTraversalData &data) const
[1002]	1517	{
[1047]	1518	#if 0
	1519	return (float)-data.mDepth;
[1027]	1520	#endif
[1002]	1521	float pvsFront = 0;
	1522	float pvsBack = 0;
	1523	float totalPvs = 0;
	1524
	1525	// probability that view point lies in back / front node
	1526	float pOverall = data.mProbability;
	1527	float pFront = 0;
	1528	float pBack = 0;
	1529
	1530
	1531	// create unique ids for pvs heuristics
	1532	GenerateUniqueIdsForPvs();
	1533
[1016]	1534	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
[1015]	1535
[1016]	1536	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
[1002]	1537	{
[1015]	1538	RayInfo rayInf = *rit;
[1002]	1539
	1540	float t;
	1541	VssRay *ray = rayInf.mRay;
[1027]	1542
[1008]	1543	const int cf =
	1544	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
	1545	candidatePlane.mPosition, t);
[1002]	1546
	1547	// find front and back pvs for origing and termination object
	1548	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
	1549	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
	1550	}
	1551
[1027]	1552
[1011]	1553	AxisAlignedBox3 frontBox;
	1554	AxisAlignedBox3 backBox;
	1555
	1556	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
	1557
	1558	pFront = frontBox.GetVolume();
[1006]	1559	pBack = pOverall - pFront;
	1560
	1561
[1020]	1562	//-- pvs rendering heuristics
[1002]	1563	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1564	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1565
[1020]	1566	//-- only render cost heuristics or combined with standard deviation
	1567	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	1568	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	1569	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[1002]	1570
	1571	const float oldRenderCost = pOverall * penaltyOld;
	1572	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1573
	1574	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
[1020]	1575	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
[1002]	1576
[1020]	1577	// take render cost of node into account
	1578	// otherwise danger of being stuck in a local minimum!!
[1027]	1579	const float factor = 0.99f;
	1580
[1020]	1581	const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
[1027]	1582	return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
[1002]	1583	}
	1584
	1585
[1027]	1586	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
	1587	const AxisAlignedBox3 &box,
	1588	const int axis,
	1589	const float &position,
	1590	float &pFront,
	1591	float &pBack) const
[1002]	1592	{
	1593	float pvsTotal = 0;
	1594	float pvsFront = 0;
	1595	float pvsBack = 0;
	1596
	1597	// create unique ids for pvs heuristics
	1598	GenerateUniqueIdsForPvs();
	1599
	1600	const int pvsSize = data.mPvs;
	1601
	1602	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
	1603
	1604	// this is the main ray classification loop!
	1605	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
	1606	{
	1607	// determine the side of this ray with respect to the plane
	1608	float t;
	1609	const int side = (*rit).ComputeRayIntersection(axis, position, t);
	1610
	1611	AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
	1612	AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
	1613	}
	1614
	1615	//-- pvs heuristics
	1616	float pOverall;
	1617
	1618	//-- compute heurstics
[1027]	1619
[1002]	1620	pOverall = data.mProbability;
[1027]	1621	// we take simplified computation for mid split
[1006]	1622	pBack = pFront = pOverall * 0.5f;
	1623
	1624
[1002]	1625	#ifdef _DEBUG
	1626	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	1627	Debug << pFront << " " << pBack << " " << pOverall << endl;
	1628	#endif
	1629
	1630
	1631	const float newCost = pvsBack * pBack + pvsFront * pFront;
	1632	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
	1633
	1634	return (mCtDivCi + newCost) / oldCost;
	1635	}
	1636
	1637
[1016]	1638	void VspTree::AddObjToPvs(Intersectable *obj,
[1027]	1639	const int cf,
	1640	float &frontPvs,
	1641	float &backPvs,
	1642	float &totalPvs) const
[1002]	1643	{
	1644	if (!obj)
	1645	return;
	1646
	1647	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
	1648
	1649	// new object
	1650	if ((obj->mMailbox != sFrontId) &&
	1651	(obj->mMailbox != sBackId) &&
	1652	(obj->mMailbox != sFrontAndBackId))
	1653	{
	1654	totalPvs += renderCost;
	1655	}
	1656
	1657	// TODO: does this really belong to no pvs?
	1658	//if (cf == Ray::COINCIDENT) return;
	1659
	1660	// object belongs to both PVS
	1661	if (cf >= 0)
	1662	{
	1663	if ((obj->mMailbox != sFrontId) &&
	1664	(obj->mMailbox != sFrontAndBackId))
	1665	{
	1666	frontPvs += renderCost;
	1667
	1668	if (obj->mMailbox == sBackId)
	1669	obj->mMailbox = sFrontAndBackId;
	1670	else
	1671	obj->mMailbox = sFrontId;
	1672	}
	1673	}
	1674
	1675	if (cf <= 0)
	1676	{
	1677	if ((obj->mMailbox != sBackId) &&
	1678	(obj->mMailbox != sFrontAndBackId))
	1679	{
	1680	backPvs += renderCost;
	1681
	1682	if (obj->mMailbox == sFrontId)
	1683	obj->mMailbox = sFrontAndBackId;
	1684	else
	1685	obj->mMailbox = sBackId;
	1686	}
	1687	}
	1688	}
	1689
	1690
[1016]	1691	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
[1002]	1692	const bool onlyUnmailed,
	1693	const int maxPvsSize) const
	1694	{
[1008]	1695	stack<VspNode *> nodeStack;
[1002]	1696	nodeStack.push(mRoot);
	1697
	1698	while (!nodeStack.empty())
	1699	{
[1008]	1700	VspNode *node = nodeStack.top();
[1002]	1701	nodeStack.pop();
	1702
	1703	if (node->IsLeaf())
	1704	{
	1705	// test if this leaf is in valid view space
[1008]	1706	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1707	if (leaf->TreeValid() &&
	1708	(!onlyUnmailed \|\| !leaf->Mailed()) &&
	1709	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
	1710	{
	1711	leaves.push_back(leaf);
	1712	}
	1713	}
	1714	else
	1715	{
[1008]	1716	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1717
	1718	nodeStack.push(interior->GetBack());
	1719	nodeStack.push(interior->GetFront());
	1720	}
	1721	}
	1722	}
	1723
	1724
[1016]	1725	AxisAlignedBox3 VspTree::GetBoundingBox() const
[1002]	1726	{
[1020]	1727	return mBoundingBox;
[1002]	1728	}
	1729
	1730
[1016]	1731	VspNode *VspTree::GetRoot() const
[1002]	1732	{
	1733	return mRoot;
	1734	}
	1735
	1736
[1016]	1737	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
[1002]	1738	{
	1739	// the node became a leaf -> evaluate stats for leafs
[1008]	1740	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
[1002]	1741
	1742
[1008]	1743	if (data.mPvs > mVspStats.maxPvs)
[1002]	1744	{
[1008]	1745	mVspStats.maxPvs = data.mPvs;
[1002]	1746	}
	1747
[1008]	1748	mVspStats.pvs += data.mPvs;
[1002]	1749
[1008]	1750	if (data.mDepth < mVspStats.minDepth)
[1002]	1751	{
[1008]	1752	mVspStats.minDepth = data.mDepth;
[1002]	1753	}
	1754
	1755	if (data.mDepth >= mTermMaxDepth)
	1756	{
[1008]	1757	++ mVspStats.maxDepthNodes;
	1758	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
[1002]	1759	}
	1760
	1761	// accumulate rays to compute rays / leaf
[1008]	1762	mVspStats.accumRays += (int)data.mRays->size();
[1002]	1763
	1764	if (data.mPvs < mTermMinPvs)
[1008]	1765	++ mVspStats.minPvsNodes;
[1002]	1766
	1767	if ((int)data.mRays->size() < mTermMinRays)
[1008]	1768	++ mVspStats.minRaysNodes;
[1002]	1769
	1770	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
[1008]	1771	++ mVspStats.maxRayContribNodes;
[1002]	1772
	1773	if (data.mProbability <= mTermMinProbability)
[1008]	1774	++ mVspStats.minProbabilityNodes;
[1002]	1775
	1776	// accumulate depth to compute average depth
[1008]	1777	mVspStats.accumDepth += data.mDepth;
[1002]	1778
	1779	++ mCreatedViewCells;
	1780
[1027]	1781	//#ifdef _DEBUG
[1002]	1782	Debug << "BSP stats: "
	1783	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	1784	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	1785	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1027]	1786	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
[1002]	1787	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
[1027]	1788	//#endif
[1002]	1789	}
	1790
	1791
[1016]	1792	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
[1002]	1793	{
	1794	ViewCell::NewMail();
	1795	CollectViewCells(mRoot, onlyValid, viewCells, true);
	1796	}
	1797
	1798
[1016]	1799	void VspTree::CollapseViewCells()
[1002]	1800	{
	1801	// TODO
	1802	#if HAS_TO_BE_REDONE
[1008]	1803	stack<VspNode *> nodeStack;
[1002]	1804
	1805	if (!mRoot)
	1806	return;
	1807
	1808	nodeStack.push(mRoot);
	1809
	1810	while (!nodeStack.empty())
	1811	{
[1008]	1812	VspNode *node = nodeStack.top();
[1002]	1813	nodeStack.pop();
	1814
	1815	if (node->IsLeaf())
	1816	{
[1008]	1817	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1818
	1819	if (!viewCell->GetValid())
	1820	{
[1008]	1821	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1822
	1823	ViewCellContainer leaves;
	1824	mViewCellsTree->CollectLeaves(viewCell, leaves);
	1825
	1826	ViewCellContainer::const_iterator it, it_end = leaves.end();
	1827
	1828	for (it = leaves.begin(); it != it_end; ++ it)
	1829	{
[1008]	1830	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
[1002]	1831	l->SetViewCell(GetOrCreateOutOfBoundsCell());
[1008]	1832	++ mVspStats.invalidLeaves;
[1002]	1833	}
	1834
	1835	// add to unbounded view cell
	1836	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
	1837	DEL_PTR(viewCell);
	1838	}
	1839	}
	1840	else
	1841	{
[1008]	1842	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1843
	1844	nodeStack.push(interior->GetFront());
	1845	nodeStack.push(interior->GetBack());
	1846	}
	1847	}
	1848
[1008]	1849	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	1850	#endif
	1851	}
	1852
	1853
[1016]	1854	void VspTree::CollectRays(VssRayContainer &rays)
[1002]	1855	{
[1008]	1856	vector<VspLeaf *> leaves;
[1002]	1857
[1008]	1858	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
[1002]	1859
	1860	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	1861	{
[1008]	1862	VspLeaf leaf = lit;
[1002]	1863	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	1864
	1865	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	1866	rays.push_back(*rit);
	1867	}
	1868	}
	1869
	1870
[1021]	1871	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
	1872	{
	1873	mViewCellsManager = vcm;
	1874	}
	1875
	1876
[1016]	1877	void VspTree::ValidateTree()
[1002]	1878	{
[1020]	1879	mVspStats.invalidLeaves = 0;
	1880
[1008]	1881	stack<VspNode *> nodeStack;
[1002]	1882
	1883	if (!mRoot)
	1884	return;
	1885
	1886	nodeStack.push(mRoot);
[1020]	1887
[1002]	1888	while (!nodeStack.empty())
	1889	{
[1008]	1890	VspNode *node = nodeStack.top();
[1002]	1891	nodeStack.pop();
	1892
	1893	if (node->IsLeaf())
	1894	{
[1008]	1895	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1896
	1897	if (!leaf->GetViewCell()->GetValid())
[1008]	1898	++ mVspStats.invalidLeaves;
[1002]	1899
	1900	// validity flags don't match => repair
	1901	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
	1902	{
	1903	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
	1904	PropagateUpValidity(leaf);
	1905	}
	1906	}
	1907	else
	1908	{
[1008]	1909	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1910
	1911	nodeStack.push(interior->GetFront());
	1912	nodeStack.push(interior->GetBack());
	1913	}
	1914	}
	1915
[1008]	1916	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	1917	}
	1918
	1919
	1920
[1016]	1921	void VspTree::CollectViewCells(VspNode *root,
[1002]	1922	bool onlyValid,
	1923	ViewCellContainer &viewCells,
	1924	bool onlyUnmailed) const
	1925	{
[1008]	1926	stack<VspNode *> nodeStack;
[1002]	1927
	1928	if (!root)
	1929	return;
	1930
	1931	nodeStack.push(root);
	1932
	1933	while (!nodeStack.empty())
	1934	{
[1008]	1935	VspNode *node = nodeStack.top();
[1002]	1936	nodeStack.pop();
	1937
	1938	if (node->IsLeaf())
	1939	{
	1940	if (!onlyValid \|\| node->TreeValid())
	1941	{
[1008]	1942	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1943
	1944	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
	1945
	1946	if (!onlyUnmailed \|\| !viewCell->Mailed())
	1947	{
	1948	viewCell->Mail();
	1949	viewCells.push_back(viewCell);
	1950	}
	1951	}
	1952	}
	1953	else
	1954	{
[1008]	1955	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1956
	1957	nodeStack.push(interior->GetFront());
	1958	nodeStack.push(interior->GetBack());
	1959	}
	1960	}
	1961	}
	1962
	1963
[1016]	1964	int VspTree::FindNeighbors(VspLeaf *n,
[1020]	1965	vector<VspLeaf *> &neighbors,
	1966	const bool onlyUnmailed) const
[1002]	1967	{
[1012]	1968	stack<VspNode *> nodeStack;
	1969	nodeStack.push(mRoot);
[1002]	1970
[1012]	1971	const AxisAlignedBox3 box = GetBBox(n);
[1002]	1972
	1973	while (!nodeStack.empty())
	1974	{
[1008]	1975	VspNode *node = nodeStack.top();
[1002]	1976	nodeStack.pop();
	1977
	1978	if (node->IsLeaf())
	1979	{
[1012]	1980	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	1981
	1982	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
	1983	neighbors.push_back(leaf);
[1002]	1984	}
	1985	else
	1986	{
[1008]	1987	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	1988
	1989	if (interior->GetPosition() > box.Max(interior->GetAxis()))
	1990	nodeStack.push(interior->GetBack());
	1991	else
	1992	{
	1993	if (interior->GetPosition() < box.Min(interior->GetAxis()))
	1994	nodeStack.push(interior->GetFront());
	1995	else
	1996	{
	1997	// random decision
	1998	nodeStack.push(interior->GetBack());
	1999	nodeStack.push(interior->GetFront());
	2000	}
	2001	}
	2002	}
	2003	}
[1002]	2004
[1012]	2005	return (int)neighbors.size();
	2006	}
[1002]	2007
	2008
[1012]	2009	// Find random neighbor which was not mailed
[1016]	2010	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
[1012]	2011	{
	2012	stack<VspNode *> nodeStack;
	2013	nodeStack.push(mRoot);
	2014
	2015	int mask = rand();
	2016
	2017	while (!nodeStack.empty())
	2018	{
	2019	VspNode *node = nodeStack.top();
	2020
	2021	nodeStack.pop();
	2022
	2023	if (node->IsLeaf())
	2024	{
	2025	return dynamic_cast<VspLeaf *>(node);
	2026	}
	2027	else
	2028	{
	2029	VspInterior interior = dynamic_cast<VspInterior >(node);
	2030	VspNode *next;
	2031
	2032	if (GetBBox(interior->GetBack()).Side(plane) < 0)
[1027]	2033	{
[1002]	2034	next = interior->GetFront();
[1027]	2035	}
[1012]	2036	else
[1027]	2037	{
[1012]	2038	if (GetBBox(interior->GetFront()).Side(plane) < 0)
[1027]	2039	{
[1002]	2040	next = interior->GetBack();
[1027]	2041	}
[1012]	2042	else
	2043	{
	2044	// random decision
	2045	if (mask & 1)
	2046	next = interior->GetBack();
	2047	else
	2048	next = interior->GetFront();
	2049	mask = mask >> 1;
	2050	}
[1027]	2051	}
	2052
	2053	nodeStack.push(next);
[1002]	2054	}
	2055	}
[1012]	2056
[1002]	2057	return NULL;
	2058	}
	2059
	2060
[1016]	2061	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
[1002]	2062	{
[1008]	2063	stack<VspNode *> nodeStack;
[1002]	2064
	2065	nodeStack.push(mRoot);
	2066
	2067	int mask = rand();
	2068
	2069	while (!nodeStack.empty())
	2070	{
[1008]	2071	VspNode *node = nodeStack.top();
[1002]	2072	nodeStack.pop();
	2073
	2074	if (node->IsLeaf())
	2075	{
	2076	if ( (!onlyUnmailed \|\| !node->Mailed()) )
[1008]	2077	return dynamic_cast<VspLeaf *>(node);
[1002]	2078	}
	2079	else
	2080	{
[1008]	2081	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2082
	2083	// random decision
	2084	if (mask & 1)
	2085	nodeStack.push(interior->GetBack());
	2086	else
	2087	nodeStack.push(interior->GetFront());
	2088
	2089	mask = mask >> 1;
	2090	}
	2091	}
	2092
	2093	return NULL;
	2094	}
	2095
	2096
[1072]	2097	void VspTree::CollectPvs(const RayInfoContainer &rays,
	2098	ObjectContainer &objects) const
	2099	{
	2100	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2101
	2102	Intersectable::NewMail();
	2103
	2104	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2105	{
	2106	VssRay ray = (rit).mRay;
	2107
	2108	Intersectable *object;
	2109	object = ray->mOriginObject;
	2110
	2111	if (object)
	2112	{
	2113	if (!object->Mailed())
	2114	{
	2115	object->Mail();
	2116	objects.push_back(object);
	2117	}
	2118	}
	2119
	2120	object = ray->mTerminationObject;
	2121
	2122	if (object)
	2123	{
	2124	if (!object->Mailed())
	2125	{
	2126	object->Mail();
	2127	objects.push_back(object);
	2128	}
	2129	}
	2130	}
	2131	}
	2132
	2133
[1016]	2134	int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
[1002]	2135	{
	2136	int pvsSize = 0;
	2137
	2138	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2139
	2140	Intersectable::NewMail();
	2141
	2142	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	2143	{
	2144	VssRay ray = (rit).mRay;
	2145
	2146	if (ray->mOriginObject)
	2147	{
	2148	if (!ray->mOriginObject->Mailed())
	2149	{
	2150	ray->mOriginObject->Mail();
	2151	++ pvsSize;
	2152	}
	2153	}
	2154	if (ray->mTerminationObject)
	2155	{
	2156	if (!ray->mTerminationObject->Mailed())
	2157	{
	2158	ray->mTerminationObject->Mail();
	2159	++ pvsSize;
	2160	}
	2161	}
	2162	}
	2163
	2164	return pvsSize;
	2165	}
	2166
	2167
[1016]	2168	float VspTree::GetEpsilon() const
[1002]	2169	{
	2170	return mEpsilon;
	2171	}
	2172
	2173
[1016]	2174	int VspTree::CastLineSegment(const Vector3 &origin,
[1027]	2175	const Vector3 &termination,
	2176	ViewCellContainer &viewcells)
[1002]	2177	{
	2178	int hits = 0;
	2179
	2180	float mint = 0.0f, maxt = 1.0f;
[1012]	2181	const Vector3 dir = termination - origin;
[1002]	2182
[1012]	2183	stack<LineTraversalData> tStack;
	2184
[1002]	2185	Intersectable::NewMail();
	2186	ViewCell::NewMail();
	2187
	2188	Vector3 entp = origin;
	2189	Vector3 extp = termination;
	2190
[1008]	2191	VspNode *node = mRoot;
[1012]	2192	VspNode *farChild;
[1002]	2193
[1012]	2194	float position;
	2195	int axis;
	2196
[1002]	2197	while (1)
	2198	{
	2199	if (!node->IsLeaf())
	2200	{
[1008]	2201	VspInterior in = dynamic_cast<VspInterior >(node);
[1012]	2202	position = in->GetPosition();
	2203	axis = in->GetAxis();
[1002]	2204
[1012]	2205	if (entp[axis] <= position)
[1002]	2206	{
[1012]	2207	if (extp[axis] <= position)
	2208	{
[1047]	2209	node = in->GetBack();
[1012]	2210	// cases N1,N2,N3,P5,Z2,Z3
[1002]	2211	continue;
[1012]	2212	} else
	2213	{
	2214	// case N4
[1047]	2215	node = in->GetBack();
	2216	farChild = in->GetFront();
[1012]	2217	}
	2218	}
	2219	else
[1002]	2220	{
[1012]	2221	if (position <= extp[axis])
	2222	{
[1047]	2223	node = in->GetFront();
[1012]	2224	// cases P1,P2,P3,N5,Z1
[1002]	2225	continue;
[1012]	2226	}
	2227	else
	2228	{
[1047]	2229	node = in->GetFront();
	2230	farChild = in->GetBack();
[1012]	2231	// case P4
	2232	}
[1002]	2233	}
	2234
[1012]	2235	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2236	// case N4 or P4
	2237	const float tdist = (position - origin[axis]) / dir[axis];
	2238	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
[1002]	2239
[1012]	2240	extp = origin + dir * tdist;
	2241	maxt = tdist;
	2242	}
[1002]	2243	else
	2244	{
[1012]	2245	// compute intersection with all objects in this leaf
[1008]	2246	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1012]	2247	ViewCell *vc = leaf->GetViewCell();
	2248
	2249	if (!vc->Mailed())
	2250	{
	2251	vc->Mail();
	2252	viewcells.push_back(vc);
	2253	++ hits;
	2254	}
	2255	#if 0
	2256	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
	2257	#endif
	2258	// get the next node from the stack
	2259	if (tStack.empty())
	2260	break;
	2261
	2262	entp = extp;
	2263	mint = maxt;
[1002]	2264
[1012]	2265	LineTraversalData &s = tStack.top();
	2266	node = s.mNode;
	2267	extp = s.mExitPoint;
	2268	maxt = s.mMaxT;
	2269	tStack.pop();
	2270	}
	2271	}
	2272
	2273	return hits;
	2274	}
	2275
	2276
[1016]	2277	int VspTree::CastRay(Ray &ray)
[1012]	2278	{
	2279	int hits = 0;
	2280
	2281	stack<LineTraversalData> tStack;
	2282	const Vector3 dir = ray.GetDir();
	2283
	2284	float maxt, mint;
	2285
[1020]	2286	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
[1012]	2287	return 0;
	2288
	2289	Intersectable::NewMail();
	2290	ViewCell::NewMail();
	2291
	2292	Vector3 entp = ray.Extrap(mint);
	2293	Vector3 extp = ray.Extrap(maxt);
	2294
	2295	const Vector3 origin = entp;
	2296
	2297	VspNode *node = mRoot;
	2298	VspNode *farChild = NULL;
	2299
	2300	float position;
	2301	int axis;
	2302
	2303	while (1)
	2304	{
	2305	if (!node->IsLeaf())
	2306	{
	2307	VspInterior in = dynamic_cast<VspInterior >(node);
	2308	position = in->GetPosition();
	2309	axis = in->GetAxis();
	2310
	2311	if (entp[axis] <= position)
	2312	{
	2313	if (extp[axis] <= position)
	2314	{
	2315	node = in->GetBack();
	2316	// cases N1,N2,N3,P5,Z2,Z3
	2317	continue;
[1020]	2318	}
	2319	else
[1012]	2320	{
	2321	// case N4
	2322	node = in->GetBack();
	2323	farChild = in->GetFront();
	2324	}
	2325	}
[1002]	2326	else
[1012]	2327	{
	2328	if (position <= extp[axis])
	2329	{
	2330	node = in->GetFront();
	2331	// cases P1,P2,P3,N5,Z1
	2332	continue;
	2333	}
	2334	else
	2335	{
	2336	node = in->GetFront();
	2337	farChild = in->GetBack();
	2338	// case P4
	2339	}
	2340	}
[1002]	2341
[1012]	2342	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2343	// case N4 or P4
	2344	const float tdist = (position - origin[axis]) / dir[axis];
	2345	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
	2346	extp = origin + dir * tdist;
	2347	maxt = tdist;
	2348	}
	2349	else
	2350	{
	2351	// compute intersection with all objects in this leaf
	2352	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	2353	ViewCell *vc = leaf->GetViewCell();
	2354
	2355	if (!vc->Mailed())
[1002]	2356	{
[1012]	2357	vc->Mail();
	2358	// todo: add view cells to ray
[1002]	2359	++ hits;
	2360	}
[1012]	2361	#if 0
[1020]	2362	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
[1012]	2363	#endif
	2364	// get the next node from the stack
[1002]	2365	if (tStack.empty())
	2366	break;
	2367
	2368	entp = extp;
[1012]	2369	mint = maxt;
[1002]	2370
[1012]	2371	LineTraversalData &s = tStack.top();
[1002]	2372	node = s.mNode;
	2373	extp = s.mExitPoint;
[1012]	2374	maxt = s.mMaxT;
[1002]	2375	tStack.pop();
	2376	}
	2377	}
[1012]	2378
[1002]	2379	return hits;
	2380	}
	2381
	2382
[1016]	2383	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
[1002]	2384	{
	2385	if (mRoot == NULL)
	2386	return NULL;
	2387
[1008]	2388	stack<VspNode *> nodeStack;
[1002]	2389	nodeStack.push(mRoot);
	2390
	2391	ViewCellLeaf *viewcell = NULL;
	2392
	2393	while (!nodeStack.empty())
	2394	{
[1008]	2395	VspNode *node = nodeStack.top();
[1002]	2396	nodeStack.pop();
	2397
	2398	if (node->IsLeaf())
	2399	{
[1008]	2400	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
[1002]	2401	break;
	2402	}
	2403	else
	2404	{
[1008]	2405	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	2406
[1002]	2407	// random decision
[1012]	2408	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
[1002]	2409	nodeStack.push(interior->GetBack());
	2410	else
	2411	nodeStack.push(interior->GetFront());
	2412	}
	2413	}
	2414
	2415	if (active)
	2416	return mViewCellsTree->GetActiveViewCell(viewcell);
	2417	else
	2418	return viewcell;
	2419	}
	2420
	2421
[1016]	2422	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
[1002]	2423	{
[1008]	2424	VspNode *node = mRoot;
[1002]	2425
	2426	while (1)
	2427	{
	2428	// early exit
	2429	if (node->TreeValid())
	2430	return true;
	2431
	2432	if (node->IsLeaf())
	2433	return false;
	2434
[1008]	2435	VspInterior in = dynamic_cast<VspInterior >(node);
[1002]	2436
[1012]	2437	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
[1002]	2438	{
	2439	node = in->GetBack();
	2440	}
	2441	else
	2442	{
	2443	node = in->GetFront();
	2444	}
	2445	}
[1012]	2446
[1002]	2447	// should never come here
	2448	return false;
	2449	}
	2450
	2451
[1016]	2452	void VspTree::PropagateUpValidity(VspNode *node)
[1002]	2453	{
	2454	const bool isValid = node->TreeValid();
	2455
	2456	// propagative up invalid flag until only invalid nodes exist over this node
	2457	if (!isValid)
	2458	{
	2459	while (!node->IsRoot() && node->GetParent()->TreeValid())
	2460	{
	2461	node = node->GetParent();
	2462	node->SetTreeValid(false);
	2463	}
	2464	}
	2465	else
	2466	{
	2467	// propagative up valid flag until one of the subtrees is invalid
	2468	while (!node->IsRoot() && !node->TreeValid())
	2469	{
	2470	node = node->GetParent();
[1008]	2471	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2472
	2473	// the parent is valid iff both leaves are valid
	2474	node->SetTreeValid(interior->GetBack()->TreeValid() &&
	2475	interior->GetFront()->TreeValid());
	2476	}
	2477	}
	2478	}
	2479
	2480	#if ZIPPED_VIEWCELLS
[1016]	2481	bool VspTree::Export(ogzstream &stream)
[1002]	2482	#else
[1016]	2483	bool VspTree::Export(ofstream &stream)
[1002]	2484	#endif
	2485	{
	2486	ExportNode(mRoot, stream);
	2487
	2488	return true;
	2489	}
	2490
[1006]	2491
[1002]	2492	#if ZIPPED_VIEWCELLS
[1016]	2493	void VspTree::ExportNode(VspNode *node, ogzstream &stream)
[1002]	2494	#else
[1016]	2495	void VspTree::ExportNode(VspNode *node, ofstream &stream)
[1002]	2496	#endif
	2497	{
	2498	if (node->IsLeaf())
	2499	{
[1008]	2500	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	2501	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
	2502
	2503	int id = -1;
	2504	if (viewCell != mOutOfBoundsCell)
	2505	id = viewCell->GetId();
	2506
	2507	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
	2508	}
	2509	else
[1012]	2510	{
[1008]	2511	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2512
[1012]	2513	AxisAlignedPlane plane = interior->GetPlane();
	2514	stream << "<Interior plane=\"" << plane.mPosition << " "
	2515	<< plane.mAxis << "\">" << endl;
[1002]	2516
	2517	ExportNode(interior->GetBack(), stream);
	2518	ExportNode(interior->GetFront(), stream);
[1012]	2519
[1002]	2520	stream << "</Interior>" << endl;
	2521	}
	2522	}
	2523
[1011]	2524
[1016]	2525	int VspTree::SplitRays(const AxisAlignedPlane &plane,
[1020]	2526	RayInfoContainer &rays,
	2527	RayInfoContainer &frontRays,
	2528	RayInfoContainer &backRays) const
[1011]	2529	{
	2530	int splits = 0;
	2531
	2532	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2533
	2534	for (rit = rays.begin(); rit != rit_end; ++ rit)
	2535	{
	2536	RayInfo bRay = *rit;
	2537
	2538	VssRay *ray = bRay.mRay;
	2539	float t;
	2540
	2541	// get classification and receive new t
	2542	//-- test if start point behind or in front of plane
[1047]	2543	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
	2544
	2545
[1027]	2546	#if 1
[1011]	2547	if (side == 0)
	2548	{
	2549	++ splits;
	2550
	2551	if (ray->HasPosDir(plane.mAxis))
	2552	{
	2553	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2554	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2555	}
	2556	else
	2557	{
	2558	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2559	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2560	}
	2561	}
	2562	else if (side == 1)
	2563	{
	2564	frontRays.push_back(bRay);
	2565	}
	2566	else
	2567	{
	2568	backRays.push_back(bRay);
	2569	}
[1027]	2570	#else
	2571	if (side == 0)
	2572	{
	2573	++ splits;
[1011]	2574
[1027]	2575	if (ray->HasPosDir(plane.mAxis))
	2576	{
	2577	backRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
	2578	frontRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
	2579	}
	2580	else
	2581	{
	2582	frontRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
	2583	backRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
	2584	}
	2585	}
	2586	else if (side == 1)
	2587	{
	2588	backRays.push_back(bRay);
	2589	}
	2590	else
	2591	{
	2592	frontRays.push_back(bRay);
	2593
	2594	}
	2595	#endif
[1011]	2596	}
	2597
	2598	return splits;
	2599	}
	2600
[1012]	2601
[1016]	2602	AxisAlignedBox3 VspTree::GetBBox(VspNode *node) const
[1012]	2603	{
	2604	if (!node->GetParent())
[1020]	2605	return mBoundingBox;
[1012]	2606
	2607	if (!node->IsLeaf())
	2608	{
[1016]	2609	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
[1012]	2610	}
	2611
	2612	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
	2613
[1016]	2614	AxisAlignedBox3 box(parent->GetBoundingBox());
[1012]	2615
[1047]	2616	if (parent->GetFront() == node)
	2617	box.SetMin(parent->GetAxis(), parent->GetPosition());
	2618	else
	2619	box.SetMax(parent->GetAxis(), parent->GetPosition());
[1012]	2620
	2621	return box;
	2622	}
	2623
	2624
[1020]	2625
[1021]	2626
	2627	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
	2628	ViewCellContainer &viewCells) const
	2629	{
[1027]	2630	stack<VspNode *> nodeStack;
	2631
[1021]	2632	ViewCell::NewMail();
	2633
	2634	while (!nodeStack.empty())
	2635	{
[1027]	2636	VspNode *node = nodeStack.top();
[1021]	2637	nodeStack.pop();
	2638
[1027]	2639	const AxisAlignedBox3 bbox = GetBBox(node);
	2640
	2641	if (bbox.Includes(box))
[1021]	2642	{
	2643	// node geometry is contained in box
	2644	CollectViewCells(node, true, viewCells, true);
[1027]	2645	}
	2646	else if (Overlap(bbox, box))
	2647	{
[1021]	2648	if (node->IsLeaf())
	2649	{
	2650	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2651
	2652	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
	2653	{
	2654	leaf->GetViewCell()->Mail();
	2655	viewCells.push_back(leaf->GetViewCell());
	2656	}
	2657	}
	2658	else
	2659	{
[1027]	2660	VspInterior interior = dynamic_cast<VspInterior >(node);
[1021]	2661
[1027]	2662	VspNode *first = interior->GetFront();
	2663	VspNode *second = interior->GetBack();
[1021]	2664
[1027]	2665	nodeStack.push(first);
	2666	nodeStack.push(second);
[1021]	2667	}
[1027]	2668	}
	2669	// default: cull
[1021]	2670	}
	2671
	2672	return (int)viewCells.size();
	2673	}
	2674
	2675
	2676
[1016]	2677	/*****************************************************************/
[1021]	2678	/* class OspTree implementation */
[1016]	2679	/*****************************************************************/
	2680
[1027]	2681
[1022]	2682	OspTree::OspTree():
	2683	mRoot(NULL)
	2684	#if TODO
	2685	mOutOfBoundsCell(NULL),
	2686	mStoreRays(false),
	2687	mUseRandomAxis(false),
	2688	mTimeStamp(1)
	2689	#endif
	2690	{
	2691	#if TODO
	2692	bool randomize = false;
	2693	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
	2694	if (randomize)
	2695	Randomize(); // initialise random generator for heuristics
[1020]	2696
[1022]	2697	//-- termination criteria for autopartition
	2698	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
	2699	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
	2700	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
	2701	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
	2702	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
[1023]	2703
[1022]	2704	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
	2705	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
	2706
	2707	//-- max cost ratio for early tree termination
	2708	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
	2709
	2710	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	2711	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
	2712
	2713	// HACK//mTermMinPolygons = 25;
	2714
	2715	//-- factors for bsp tree split plane heuristics
	2716	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
	2717
	2718	//-- partition criteria
	2719	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
	2720
	2721	// if only the driving axis is used for axis aligned split
	2722	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
	2723
	2724	//Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
	2725	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
	2726
	2727	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
	2728	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
[1023]	2729
	2730
[1022]	2731	char subdivisionStatsLog[100];
	2732	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
	2733	mSubdivisionStats.open(subdivisionStatsLog);
	2734
	2735	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
	2736	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
	2737
	2738
	2739	//-- debug output
	2740
	2741	Debug << "***** VSP BSP options ****** " << endl;
	2742	Debug << "max depth: " << mTermMaxDepth << endl;
	2743	Debug << "min PVS: " << mTermMinPvs << endl;
	2744	Debug << "min probabiliy: " << mTermMinProbability << endl;
	2745	Debug << "min rays: " << mTermMinRays << endl;
	2746	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	2747	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	2748	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	2749	Debug << "max view cells: " << mMaxViewCells << endl;
	2750	Debug << "randomize: " << randomize << endl;
	2751
	2752	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	2753	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	2754	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	2755	Debug << "max memory: " << mMaxMemory << endl;
	2756	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	2757	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1023]	2758
[1022]	2759	Debug << "circulating axis: " << mCirculatingAxis << endl;
	2760	Debug << "minband: " << mMinBand << endl;
	2761	Debug << "maxband: " << mMaxBand << endl;
	2762
	2763
	2764	mSplitCandidates = new vector<SortableEntry>;
	2765
	2766	Debug << endl;
	2767	#endif
	2768	}
	2769
	2770
	2771
[1020]	2772	void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
	2773	const ObjectContainer &objects,
	2774	ObjectContainer &back,
	2775	ObjectContainer &front)
[1016]	2776	{
[1020]	2777	ObjectContainer::const_iterator oit, oit_end = objects.end();
	2778
	2779	for (oit = objects.begin(); oit != oit_end; ++ oit)
	2780	{
	2781	// determine the side of this ray with respect to the plane
	2782	const AxisAlignedBox3 box = (*oit)->GetBox();
	2783
	2784	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
	2785	front.push_back(*oit);
	2786
	2787	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
	2788	back.push_back(*oit);
	2789	#if TODO
	2790	mStat.objectRefs -= (int)objects.size();
	2791	mStat.objectRefs += objectsBack + objectsFront;
	2792	#endif
	2793	}
[1016]	2794	}
	2795
	2796
[1020]	2797	KdInterior OspTree::SubdivideNode(KdLeaf leaf,
	2798	const AxisAlignedPlane &splitPlane,
	2799	const AxisAlignedBox3 &box,
	2800	AxisAlignedBox3 &backBBox,
	2801	AxisAlignedBox3 &frontBBox)
[1016]	2802	{
[1020]	2803	#if TODO
	2804	mSpatialStat.nodes += 2;
	2805	mSpatialStat.splits[axis];
	2806	#endif
[1016]	2807
[1020]	2808	// add the new nodes to the tree
	2809	KdInterior *node = new KdInterior(leaf->mParent);
	2810
	2811	const int axis = splitPlane.mAxis;
	2812	const float position = splitPlane.mPosition;
	2813
	2814	node->mAxis = axis;
	2815	node->mPosition = position;
	2816	node->mBox = box;
	2817
	2818	backBBox = box;
	2819	frontBBox = box;
	2820
	2821	// first count ray sides
	2822	int objectsBack = 0;
	2823	int objectsFront = 0;
	2824
	2825	backBBox.SetMax(axis, position);
	2826	frontBBox.SetMin(axis, position);
	2827
	2828	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
	2829
	2830	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
	2831	{
	2832	// determine the side of this ray with respect to the plane
	2833	const AxisAlignedBox3 box = (*mi)->GetBox();
	2834
	2835	if (box.Max(axis) > position)
	2836	++ objectsFront;
	2837
	2838	if (box.Min(axis) < position)
	2839	++ objectsBack;
	2840	}
	2841
	2842	KdLeaf *back = new KdLeaf(node, objectsBack);
	2843	KdLeaf *front = new KdLeaf(node, objectsFront);
	2844
	2845	// replace a link from node's parent
	2846	if (leaf->mParent)
	2847	leaf->mParent->ReplaceChildLink(leaf, node);
	2848
	2849	// and setup child links
	2850	node->SetupChildLinks(back, front);
	2851
	2852	SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
	2853
	2854	//delete leaf;
	2855	return node;
[1016]	2856	}
	2857
	2858
[1020]	2859	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
	2860	OspSplitCandidate &splitCandidate,
	2861	const bool globalCriteriaMet)
[1016]	2862	{
[1020]	2863	OspTraversalData &tData = splitCandidate.mParentData;
[1016]	2864
[1020]	2865	KdNode *newNode = tData.mNode;
[1016]	2866
[1020]	2867	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	2868	{
	2869	OspTraversalData tFrontData;
	2870	OspTraversalData tBackData;
[1016]	2871
[1020]	2872	//-- continue subdivision
	2873
	2874	// create new interior node and two leaf node
	2875	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
[1027]	2876
[1020]	2877	newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode),
	2878	splitPlane,
	2879	tData.mBoundingBox,
	2880	tFrontData.mBoundingBox,
	2881	tBackData.mBoundingBox);
	2882
	2883	const int maxCostMisses = splitCandidate.mMaxCostMisses;
[1016]	2884
[1020]	2885	// how often was max cost ratio missed in this branch?
	2886	tFrontData.mMaxCostMisses = maxCostMisses;
	2887	tBackData.mMaxCostMisses = maxCostMisses;
	2888
	2889	//-- push the new split candidates on the queue
	2890	OspSplitCandidate *frontCandidate = new OspSplitCandidate();
	2891	OspSplitCandidate *backCandidate = new OspSplitCandidate();
[1016]	2892
[1020]	2893	EvalSplitCandidate(tFrontData, *frontCandidate);
	2894	EvalSplitCandidate(tBackData, *backCandidate);
[1016]	2895
[1020]	2896	tQueue.push(frontCandidate);
	2897	tQueue.push(backCandidate);
	2898
	2899	// delete old leaf node
	2900	DEL_PTR(tData.mNode);
	2901	}
	2902
	2903
	2904	//-- terminate traversal
	2905	if (newNode->IsLeaf())
	2906	{
	2907	//KdLeaf leaf = dynamic_cast<KdLeaf >(newNode);
	2908	EvaluateLeafStats(tData);
	2909	}
	2910
	2911	//-- cleanup
	2912	tData.Clear();
[1016]	2913
[1020]	2914	return newNode;
	2915	}
[1016]	2916
	2917
[1020]	2918	void OspTree::EvalSplitCandidate(OspTraversalData &tData,
	2919	OspSplitCandidate &splitData)
	2920	{
	2921	float frontProb;
	2922	float backtProb;
	2923
	2924	KdLeaf leaf = dynamic_cast<KdLeaf >(tData.mNode);
	2925
	2926	// compute locally best split plane
	2927	const bool success = false;
	2928	#if TODO
	2929	SelectPlane(tData, splitData.mSplitPlane,
	2930	frontData.mProbability, backData.mProbability);
	2931
	2932	//TODO
	2933	// compute global decrease in render cost
	2934	splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
	2935	splitData.mParentData = tData;
	2936	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
[1016]	2937	#endif
	2938	}
	2939
	2940
[1021]	2941	bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
	2942	{
	2943	// matt: TODO
	2944	return true;
	2945	/* (((int)data.mRays->size() <= mTermMinRays) \|\|
	2946	(data.mPvs <= mTermMinPvs) \|\|
	2947	(data.mProbability <= mTermMinProbability) \|\|
	2948	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
	2949	(data.mDepth >= mTermMaxDepth));*/
	2950	}
[1020]	2951
[1021]	2952
	2953	bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
	2954	{
	2955	// matt: TODO
	2956	return true;
	2957	/*(mOutOfMemory \|\|
	2958	(mVspStats.Leaves() >= mMaxViewCells) \|\|
	2959	(mGlobalCostMisses >= mTermGlobalCostMissTolerance));*/
	2960	}
	2961
	2962
	2963	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
	2964	{
	2965	#if TODO
	2966	// the node became a leaf -> evaluate stats for leafs
	2967	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
	2968
	2969	if (data.mPvs > mVspStats.maxPvs)
	2970	{
	2971	mVspStats.maxPvs = data.mPvs;
	2972	}
	2973
	2974	mVspStats.pvs += data.mPvs;
	2975
	2976	if (data.mDepth < mVspStats.minDepth)
	2977	{
	2978	mVspStats.minDepth = data.mDepth;
	2979	}
	2980
	2981	if (data.mDepth >= mTermMaxDepth)
	2982	{
	2983	++ mVspStats.maxDepthNodes;
	2984	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
	2985	}
	2986
	2987	// accumulate rays to compute rays / leaf
	2988	mVspStats.accumRays += (int)data.mRays->size();
	2989
	2990	if (data.mPvs < mTermMinPvs)
	2991	++ mVspStats.minPvsNodes;
	2992
	2993	if ((int)data.mRays->size() < mTermMinRays)
	2994	++ mVspStats.minRaysNodes;
	2995
	2996	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
	2997	++ mVspStats.maxRayContribNodes;
	2998
	2999	if (data.mProbability <= mTermMinProbability)
	3000	++ mVspStats.minProbabilityNodes;
	3001
	3002	// accumulate depth to compute average depth
	3003	mVspStats.accumDepth += data.mDepth;
	3004
	3005	++ mCreatedViewCells;
	3006
	3007	#ifdef _DEBUG
	3008	Debug << "BSP stats: "
	3009	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	3010	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
[1072]	3011	<< "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
[1021]	3012	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1027]	3013	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
[1021]	3014	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
	3015	#endif
	3016
	3017	#endif
	3018	}
	3019
	3020
[1072]	3021
[1021]	3022	/*********************************************************************/
	3023	/* class HierarchyManager implementation */
	3024	/*********************************************************************/
	3025
[1072]	3026
	3027
[1027]	3028	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
	3029	mVspTree(vspTree), mOspTree(ospTree)
[1016]	3030	{
[1020]	3031	}
	3032
	3033
	3034	SplitCandidate *HierarchyManager::NextSplitCandidate()
	3035	{
	3036	SplitCandidate *splitCandidate = mTQueue.top();
[1027]	3037	Debug << "priority: " << splitCandidate->GetPriority() << endl;
[1020]	3038	mTQueue.pop();
	3039
	3040	return splitCandidate;
	3041	}
	3042
	3043
	3044	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
[1027]	3045	const ObjectContainer &objects,
[1020]	3046	AxisAlignedBox3 *forcedViewSpace,
	3047	RayInfoContainer &rays)
	3048	{
[1027]	3049	mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
[1020]	3050
	3051	long startTime = GetTime();
	3052
	3053	cout << "storing rays ... ";
	3054
	3055	Intersectable::NewMail();
	3056
[1027]	3057	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[1020]	3058
[1016]	3059	//-- store rays
	3060	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	3061	{
	3062	VssRay ray = rit;
	3063
	3064	float minT, maxT;
	3065
	3066	static Ray hray;
	3067	hray.Init(*ray);
[1027]	3068
[1016]	3069	// TODO: not very efficient to implictly cast between rays types
[1027]	3070	if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
[1016]	3071	{
	3072	float len = ray->Length();
	3073
	3074	if (!len)
	3075	len = Limits::Small;
	3076
[1020]	3077	rays.push_back(RayInfo(ray, minT / len, maxT / len));
[1016]	3078	}
	3079	}
[1020]	3080
[1027]	3081	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1020]	3082
[1027]	3083	/// add first candidate for view space partition
	3084	mVspTree.mRoot = new VspLeaf();
	3085	const float prop = mVspTree.mBoundingBox.GetVolume();
	3086
	3087	/// first traversal data
	3088	VspTree::VspTraversalData tData(mVspTree.mRoot,
	3089	0,
	3090	&rays,
	3091	(int)objects.size(),
	3092	//mVspTree.ComputePvsSize(rays),
	3093	prop,
	3094	mVspTree.mBoundingBox);
	3095
	3096	// compute first split candidate
	3097	VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate();
	3098	mVspTree.EvalSplitCandidate(tData, *splitCandidate);
	3099
	3100	mTQueue.push(splitCandidate);
	3101
[1020]	3102	//mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
[1016]	3103	}
	3104
	3105
[1020]	3106	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
[1016]	3107	{
[1020]	3108	if (candidate->Type() == SplitCandidate::VIEW_SPACE)
	3109	{
	3110	VspTree::VspSplitCandidate *sc =
	3111	dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
	3112
[1027]	3113	return mVspTree.GlobalTerminationCriteriaMet(sc->mParentData);
[1020]	3114	}
	3115
	3116	return true;
[1016]	3117	}
	3118
	3119
[1020]	3120	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
	3121	const ObjectContainer &objects,
	3122	AxisAlignedBox3 *forcedViewSpace)
[1016]	3123	{
[1020]	3124	RayInfoContainer *rays = new RayInfoContainer();
	3125
	3126	// prepare vsp and osp trees for traversal
[1027]	3127	PrepareConstruction(sampleRays, objects, forcedViewSpace, *rays);
[1016]	3128
[1027]	3129	mVspTree.mVspStats.Reset();
	3130	mVspTree.mVspStats.Start();
[1016]	3131
[1020]	3132	cout << "Constructing view space / object space tree ... \n";
[1016]	3133	const long startTime = GetTime();
	3134
	3135	while (!FinishedConstruction())
	3136	{
	3137	SplitCandidate *splitCandidate = NextSplitCandidate();
	3138
[1020]	3139	const bool globalTerminationCriteriaMet =
	3140	GlobalTerminationCriteriaMet(splitCandidate);
	3141
[1027]	3142	Debug << "cost: " << splitCandidate->GetPriority();
	3143
[1016]	3144	// cost ratio of cost decrease / totalCost
	3145	const float costRatio = splitCandidate->GetPriority() / mTotalCost;
	3146	//Debug << "cost ratio: " << costRatio << endl;
	3147
	3148	if (costRatio < mTermMinGlobalCostRatio)
	3149	++ mGlobalCostMisses;
[1027]	3150
[1020]	3151	//-- subdivide leaf node
	3152	//-- either a object space or view space split
[1016]	3153	if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
	3154	{
	3155	VspTree::VspSplitCandidate *sc =
	3156	dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
	3157
[1027]	3158	VspNode r = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1016]	3159	}
[1020]	3160	else // object space split
[1016]	3161	{
	3162	#if TODO
[1027]	3163	KdNode *r = mKdtree.Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
[1016]	3164	#endif
	3165	}
[1020]	3166
	3167	DEL_PTR(splitCandidate);
[1016]	3168	}
	3169
[1020]	3170	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
[1016]	3171
[1027]	3172	mVspTree.mVspStats.Stop();
[1016]	3173	}
	3174
[1020]	3175
	3176	bool HierarchyManager::FinishedConstruction()
	3177	{
	3178	return mTQueue.empty();
	3179	}
	3180
	3181
[1002]	3182	}

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

Download in other formats: