Context Navigation

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

Revision 1052, 65.8 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
[1052]	779	if (0) leaf->mVssRays.push_back(new VssRay(*ray));
[1002]	780	}
	781	}
	782
	783
[1047]	784	void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
	785	const int axis,
	786	float minBand,
	787	float maxBand)
[1002]	788	{
	789	mSplitCandidates->clear();
	790
	791	int requestedSize = 2 * (int)(rays.size());
[1047]	792
[1002]	793	// creates a sorted split candidates array
	794	if (mSplitCandidates->capacity() > 500000 &&
	795	requestedSize < (int)(mSplitCandidates->capacity() / 10) )
	796	{
	797	delete mSplitCandidates;
	798	mSplitCandidates = new vector<SortableEntry>;
	799	}
	800
	801	mSplitCandidates->reserve(requestedSize);
	802
	803	float pos;
	804
	805	// float values => don't compare with exact values
	806	if (0)
	807	{
	808	minBand += Limits::Small;
	809	maxBand -= Limits::Small;
	810	}
	811
	812	// insert all queries
	813	for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
	814	{
	815	const bool positive = (*ri).mRay->HasPosDir(axis);
	816
	817	pos = (*ri).ExtrapOrigin(axis);
	818	// clamp to min / max band
	819	if (0) ClipValue(pos, minBand, maxBand);
	820
	821	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
	822	pos, (*ri).mRay));
	823
	824	pos = (*ri).ExtrapTermination(axis);
	825	// clamp to min / max band
	826	if (0) ClipValue(pos, minBand, maxBand);
	827
	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
[1027]	836	float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
	837	const AxisAlignedBox3 &box,
	838	const int pvsSize,
	839	const int axis,
	840	float &position)
[1002]	841	{
	842	const float minBox = box.Min(axis);
	843	const float maxBox = box.Max(axis);
	844
	845	const float sizeBox = maxBox - minBox;
	846
	847	const float minBand = minBox + mMinBand * sizeBox;
	848	const float maxBand = minBox + mMaxBand * sizeBox;
	849
	850	SortSplitCandidates(rays, axis, minBand, maxBand);
	851
	852	// go through the lists, count the number of objects left and right
	853	// and evaluate the following cost funcion:
	854	// C = ct_div_ci + (qlrl + qrrr)/queries
	855
	856	int pvsl = 0;
	857	int pvsr = pvsSize;
	858
	859	int pvsBack = pvsl;
	860	int pvsFront = pvsr;
	861
	862	float sum = (float)pvsSize * sizeBox;
	863	float minSum = 1e20f;
	864
	865
[1047]	866	// if no good split can be found, take mid split
[1002]	867	position = minBox + 0.5f * sizeBox;
	868
	869	// the relative cost ratio
	870	float ratio = /Limits::Infinity;/99999999.0f;
	871	bool splitPlaneFound = false;
	872
	873	Intersectable::NewMail();
	874
	875	RayInfoContainer::const_iterator ri, ri_end = rays.end();
	876
	877	// set all object as belonging to the front pvs
	878	for(ri = rays.begin(); ri != ri_end; ++ ri)
	879	{
	880	Intersectable oObject = (ri).mRay->mOriginObject;
	881	Intersectable tObject = (ri).mRay->mTerminationObject;
	882
	883	if (oObject)
	884	{
	885	if (!oObject->Mailed())
	886	{
	887	oObject->Mail();
	888	oObject->mCounter = 1;
	889	}
	890	else
	891	{
	892	++ oObject->mCounter;
	893	}
	894	}
	895	if (tObject)
	896	{
	897	if (!tObject->Mailed())
	898	{
	899	tObject->Mail();
	900	tObject->mCounter = 1;
	901	}
	902	else
	903	{
	904	++ tObject->mCounter;
	905	}
	906	}
	907	}
	908
	909	Intersectable::NewMail();
	910
	911	vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
	912
	913	for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
	914	{
	915	VssRay *ray;
	916	ray = (*ci).ray;
	917
	918	Intersectable *oObject = ray->mOriginObject;
	919	Intersectable *tObject = ray->mTerminationObject;
	920
	921
	922	switch ((*ci).type)
	923	{
	924	case SortableEntry::ERayMin:
	925	{
	926	if (oObject && !oObject->Mailed())
	927	{
	928	oObject->Mail();
	929	++ pvsl;
	930	}
	931	if (tObject && !tObject->Mailed())
	932	{
	933	tObject->Mail();
	934	++ pvsl;
	935	}
	936	break;
	937	}
	938	case SortableEntry::ERayMax:
	939	{
	940	if (oObject)
	941	{
	942	if (-- oObject->mCounter == 0)
	943	-- pvsr;
	944	}
	945
	946	if (tObject)
	947	{
	948	if (-- tObject->mCounter == 0)
	949	-- pvsr;
	950	}
	951
	952	break;
	953	}
	954	}
	955
	956
	957	// Note: sufficient to compare size of bounding boxes of front and back side?
	958	if (((ci).value >= minBand) && ((ci).value <= maxBand))
	959	{
	960	sum = pvsl * ((ci).value - minBox) + pvsr (maxBox - (*ci).value);
	961
	962	//Debug << "pos=" << (*ci).value << "\t pvs=(" << pvsl << "," << pvsr << ")" << endl;
	963	//Debug << "cost= " << sum << endl;
	964
	965	if (sum < minSum)
	966	{
	967	splitPlaneFound = true;
	968
	969	minSum = sum;
	970	position = (*ci).value;
	971
	972	pvsBack = pvsl;
	973	pvsFront = pvsr;
	974	}
	975	}
	976	}
	977
	978
	979	// -- compute cost
[1047]	980
[1002]	981	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	982	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	983
	984	const float pOverall = sizeBox;
	985	const float pBack = position - minBox;
	986	const float pFront = maxBox - position;
[1047]	987
	988	/*const float pOverall = box.GetVolume();
	989
	990	AxisAlignedBox3 bbox;
	991	AxisAlignedBox3 fbox;
	992
	993	box.Split(axis, position, bbox, fbox);
	994
	995	const float pBack = fbox.GetVolume();
	996	const float pFront = bbox.GetVolume();*/
	997
[1002]	998	const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
	999	const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
	1000	const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
	1001
[1047]	1002	const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
[1002]	1003	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1004
	1005	if (splitPlaneFound)
	1006	{
[1047]	1007	ratio = newRenderCost / oldRenderCost;
[1002]	1008	}
	1009	//if (axis != 1)
	1010	//Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1011	// <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
	1012
	1013	return ratio;
	1014	}
	1015
	1016
[1027]	1017	float VspTree::SelectSplitPlane(const VspTraversalData &tData,
	1018	AxisAlignedPlane &plane,
	1019	float &pFront,
	1020	float &pBack)
[1002]	1021	{
	1022	float nPosition[3];
	1023	float nCostRatio[3];
	1024	float nProbFront[3];
	1025	float nProbBack[3];
	1026
	1027	// create bounding box of node geometry
[1006]	1028	AxisAlignedBox3 box = tData.mBoundingBox;
[1002]	1029
	1030	int sAxis = 0;
[1006]	1031	int bestAxis = -1;
[1002]	1032
[1047]	1033	//mOnlyDrivingAxis = true;
	1034
[1002]	1035	// if we use some kind of specialised fixed axis
	1036	const bool useSpecialAxis =
[1023]	1037	mOnlyDrivingAxis \|\| mCirculatingAxis;
[1047]	1038	Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
	1039	if (mCirculatingAxis)
	1040	{
	1041	int parentAxis = 0;
	1042	VspNode *parent = tData.mNode->GetParent();
[1002]	1043
[1047]	1044	if (parent)
	1045	parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
[1027]	1046
	1047	sAxis = (parentAxis + 1) % 3;
[1047]	1048	}
[1002]	1049	else if (mOnlyDrivingAxis)
[1047]	1050	{
[1002]	1051	sAxis = box.Size().DrivingAxis();
[1047]	1052	}
	1053	//sAxis = 2;
	1054	for (int axis = 0; axis < 3; ++ axis)
[1002]	1055	{
	1056	if (!useSpecialAxis \|\| (axis == sAxis))
	1057	{
	1058	//-- place split plane using heuristics
	1059
	1060	if (mUseCostHeuristics)
	1061	{
	1062	nCostRatio[axis] =
[1027]	1063	EvalLocalCostHeuristics(*tData.mRays,
	1064	box,
[1002]	1065	tData.mPvs,
	1066	axis,
	1067	nPosition[axis]);
	1068	}
[1006]	1069	else //-- split plane position is spatial median
[1002]	1070	{
	1071	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
	1072
[1027]	1073	nCostRatio[axis] = EvalLocalSplitCost(tData,
	1074	box,
	1075	axis,
	1076	nPosition[axis],
	1077	nProbFront[axis],
	1078	nProbBack[axis]);
[1002]	1079	}
	1080
[1006]	1081	if (bestAxis == -1)
[1002]	1082	{
[1006]	1083	bestAxis = axis;
[1002]	1084	}
[1006]	1085	else if (nCostRatio[axis] < nCostRatio[bestAxis])
[1002]	1086	{
[1047]	1087	Debug << "old: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1006]	1088	bestAxis = axis;
[1047]	1089
	1090	Debug << "new: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1002]	1091	}
	1092	}
	1093	}
	1094
[1047]	1095
[1002]	1096	//-- assign values
[1047]	1097
[1006]	1098	plane.mAxis = bestAxis;
[1047]	1099	// split plane position
	1100	plane.mPosition = nPosition[bestAxis];
	1101
[1002]	1102	pFront = nProbFront[bestAxis];
	1103	pBack = nProbBack[bestAxis];
	1104
	1105
[1047]	1106	Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
[1002]	1107	return nCostRatio[bestAxis];
	1108	}
	1109
	1110
[1016]	1111	inline void VspTree::GenerateUniqueIdsForPvs()
[1002]	1112	{
	1113	Intersectable::NewMail(); sBackId = Intersectable::sMailId;
	1114	Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
	1115	Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
	1116	}
	1117
	1118
[1016]	1119	float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
	1120	const VspTraversalData &data) const
[1002]	1121	{
[1047]	1122	#if 0
	1123	return (float)-data.mDepth;
[1027]	1124	#endif
[1002]	1125	float pvsFront = 0;
	1126	float pvsBack = 0;
	1127	float totalPvs = 0;
	1128
	1129	// probability that view point lies in back / front node
	1130	float pOverall = data.mProbability;
	1131	float pFront = 0;
	1132	float pBack = 0;
	1133
	1134
	1135	// create unique ids for pvs heuristics
	1136	GenerateUniqueIdsForPvs();
	1137
[1016]	1138	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
[1015]	1139
[1016]	1140	for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
[1002]	1141	{
[1015]	1142	RayInfo rayInf = *rit;
[1002]	1143
	1144	float t;
	1145	VssRay *ray = rayInf.mRay;
[1027]	1146
[1008]	1147	const int cf =
	1148	rayInf.ComputeRayIntersection(candidatePlane.mAxis,
	1149	candidatePlane.mPosition, t);
[1002]	1150
	1151	// find front and back pvs for origing and termination object
	1152	AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
	1153	AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
	1154	}
	1155
[1027]	1156
[1011]	1157	AxisAlignedBox3 frontBox;
	1158	AxisAlignedBox3 backBox;
	1159
	1160	data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
	1161
	1162	pFront = frontBox.GetVolume();
[1006]	1163	pBack = pOverall - pFront;
	1164
	1165
[1020]	1166	//-- pvs rendering heuristics
[1002]	1167	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
	1168	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
	1169
[1020]	1170	//-- only render cost heuristics or combined with standard deviation
	1171	const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
	1172	const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
	1173	const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[1002]	1174
	1175	const float oldRenderCost = pOverall * penaltyOld;
	1176	const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
	1177
	1178	//Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
[1020]	1179	const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
[1002]	1180
[1020]	1181	// take render cost of node into account
	1182	// otherwise danger of being stuck in a local minimum!!
[1027]	1183	const float factor = 0.99f;
	1184
[1020]	1185	const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
[1027]	1186	return factor * renderCostDecrease + (1.0f - factor) * normalizedOldRenderCost;
[1002]	1187	}
	1188
	1189
[1027]	1190	float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
	1191	const AxisAlignedBox3 &box,
	1192	const int axis,
	1193	const float &position,
	1194	float &pFront,
	1195	float &pBack) const
[1002]	1196	{
	1197	float pvsTotal = 0;
	1198	float pvsFront = 0;
	1199	float pvsBack = 0;
	1200
	1201	// create unique ids for pvs heuristics
	1202	GenerateUniqueIdsForPvs();
	1203
	1204	const int pvsSize = data.mPvs;
	1205
	1206	RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
	1207
	1208	// this is the main ray classification loop!
	1209	for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
	1210	{
	1211	// determine the side of this ray with respect to the plane
	1212	float t;
	1213	const int side = (*rit).ComputeRayIntersection(axis, position, t);
	1214
	1215	AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
	1216	AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
	1217	}
	1218
	1219	//-- pvs heuristics
	1220	float pOverall;
	1221
	1222	//-- compute heurstics
[1027]	1223
[1002]	1224	pOverall = data.mProbability;
[1027]	1225	// we take simplified computation for mid split
[1006]	1226	pBack = pFront = pOverall * 0.5f;
	1227
	1228
[1002]	1229	#ifdef _DEBUG
	1230	Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	1231	Debug << pFront << " " << pBack << " " << pOverall << endl;
	1232	#endif
	1233
	1234
	1235	const float newCost = pvsBack * pBack + pvsFront * pFront;
	1236	const float oldCost = (float)pvsSize * pOverall + Limits::Small;
	1237
	1238	return (mCtDivCi + newCost) / oldCost;
	1239	}
	1240
	1241
[1016]	1242	void VspTree::AddObjToPvs(Intersectable *obj,
[1027]	1243	const int cf,
	1244	float &frontPvs,
	1245	float &backPvs,
	1246	float &totalPvs) const
[1002]	1247	{
	1248	if (!obj)
	1249	return;
	1250
	1251	const float renderCost = mViewCellsManager->EvalRenderCost(obj);
	1252
	1253	// new object
	1254	if ((obj->mMailbox != sFrontId) &&
	1255	(obj->mMailbox != sBackId) &&
	1256	(obj->mMailbox != sFrontAndBackId))
	1257	{
	1258	totalPvs += renderCost;
	1259	}
	1260
	1261	// TODO: does this really belong to no pvs?
	1262	//if (cf == Ray::COINCIDENT) return;
	1263
	1264	// object belongs to both PVS
	1265	if (cf >= 0)
	1266	{
	1267	if ((obj->mMailbox != sFrontId) &&
	1268	(obj->mMailbox != sFrontAndBackId))
	1269	{
	1270	frontPvs += renderCost;
	1271
	1272	if (obj->mMailbox == sBackId)
	1273	obj->mMailbox = sFrontAndBackId;
	1274	else
	1275	obj->mMailbox = sFrontId;
	1276	}
	1277	}
	1278
	1279	if (cf <= 0)
	1280	{
	1281	if ((obj->mMailbox != sBackId) &&
	1282	(obj->mMailbox != sFrontAndBackId))
	1283	{
	1284	backPvs += renderCost;
	1285
	1286	if (obj->mMailbox == sFrontId)
	1287	obj->mMailbox = sFrontAndBackId;
	1288	else
	1289	obj->mMailbox = sBackId;
	1290	}
	1291	}
	1292	}
	1293
	1294
[1016]	1295	void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
[1002]	1296	const bool onlyUnmailed,
	1297	const int maxPvsSize) const
	1298	{
[1008]	1299	stack<VspNode *> nodeStack;
[1002]	1300	nodeStack.push(mRoot);
	1301
	1302	while (!nodeStack.empty())
	1303	{
[1008]	1304	VspNode *node = nodeStack.top();
[1002]	1305	nodeStack.pop();
	1306
	1307	if (node->IsLeaf())
	1308	{
	1309	// test if this leaf is in valid view space
[1008]	1310	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1311	if (leaf->TreeValid() &&
	1312	(!onlyUnmailed \|\| !leaf->Mailed()) &&
	1313	((maxPvsSize < 0) \|\| (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
	1314	{
	1315	leaves.push_back(leaf);
	1316	}
	1317	}
	1318	else
	1319	{
[1008]	1320	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1321
	1322	nodeStack.push(interior->GetBack());
	1323	nodeStack.push(interior->GetFront());
	1324	}
	1325	}
	1326	}
	1327
	1328
[1016]	1329	AxisAlignedBox3 VspTree::GetBoundingBox() const
[1002]	1330	{
[1020]	1331	return mBoundingBox;
[1002]	1332	}
	1333
	1334
[1016]	1335	VspNode *VspTree::GetRoot() const
[1002]	1336	{
	1337	return mRoot;
	1338	}
	1339
	1340
[1016]	1341	void VspTree::EvaluateLeafStats(const VspTraversalData &data)
[1002]	1342	{
	1343	// the node became a leaf -> evaluate stats for leafs
[1008]	1344	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
[1002]	1345
	1346
[1008]	1347	if (data.mPvs > mVspStats.maxPvs)
[1002]	1348	{
[1008]	1349	mVspStats.maxPvs = data.mPvs;
[1002]	1350	}
	1351
[1008]	1352	mVspStats.pvs += data.mPvs;
[1002]	1353
[1008]	1354	if (data.mDepth < mVspStats.minDepth)
[1002]	1355	{
[1008]	1356	mVspStats.minDepth = data.mDepth;
[1002]	1357	}
	1358
	1359	if (data.mDepth >= mTermMaxDepth)
	1360	{
[1008]	1361	++ mVspStats.maxDepthNodes;
	1362	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
[1002]	1363	}
	1364
	1365	// accumulate rays to compute rays / leaf
[1008]	1366	mVspStats.accumRays += (int)data.mRays->size();
[1002]	1367
	1368	if (data.mPvs < mTermMinPvs)
[1008]	1369	++ mVspStats.minPvsNodes;
[1002]	1370
	1371	if ((int)data.mRays->size() < mTermMinRays)
[1008]	1372	++ mVspStats.minRaysNodes;
[1002]	1373
	1374	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
[1008]	1375	++ mVspStats.maxRayContribNodes;
[1002]	1376
	1377	if (data.mProbability <= mTermMinProbability)
[1008]	1378	++ mVspStats.minProbabilityNodes;
[1002]	1379
	1380	// accumulate depth to compute average depth
[1008]	1381	mVspStats.accumDepth += data.mDepth;
[1002]	1382
	1383	++ mCreatedViewCells;
	1384
[1027]	1385	//#ifdef _DEBUG
[1002]	1386	Debug << "BSP stats: "
	1387	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	1388	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	1389	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1027]	1390	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
[1002]	1391	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
[1027]	1392	//#endif
[1002]	1393	}
	1394
	1395
[1016]	1396	void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
[1002]	1397	{
	1398	ViewCell::NewMail();
	1399	CollectViewCells(mRoot, onlyValid, viewCells, true);
	1400	}
	1401
	1402
[1016]	1403	void VspTree::CollapseViewCells()
[1002]	1404	{
	1405	// TODO
	1406	#if HAS_TO_BE_REDONE
[1008]	1407	stack<VspNode *> nodeStack;
[1002]	1408
	1409	if (!mRoot)
	1410	return;
	1411
	1412	nodeStack.push(mRoot);
	1413
	1414	while (!nodeStack.empty())
	1415	{
[1008]	1416	VspNode *node = nodeStack.top();
[1002]	1417	nodeStack.pop();
	1418
	1419	if (node->IsLeaf())
	1420	{
[1008]	1421	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1422
	1423	if (!viewCell->GetValid())
	1424	{
[1008]	1425	BspViewCell viewCell = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1426
	1427	ViewCellContainer leaves;
	1428	mViewCellsTree->CollectLeaves(viewCell, leaves);
	1429
	1430	ViewCellContainer::const_iterator it, it_end = leaves.end();
	1431
	1432	for (it = leaves.begin(); it != it_end; ++ it)
	1433	{
[1008]	1434	VspLeaf l = dynamic_cast<BspViewCell >(*it)->mLeaf;
[1002]	1435	l->SetViewCell(GetOrCreateOutOfBoundsCell());
[1008]	1436	++ mVspStats.invalidLeaves;
[1002]	1437	}
	1438
	1439	// add to unbounded view cell
	1440	GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
	1441	DEL_PTR(viewCell);
	1442	}
	1443	}
	1444	else
	1445	{
[1008]	1446	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1447
	1448	nodeStack.push(interior->GetFront());
	1449	nodeStack.push(interior->GetBack());
	1450	}
	1451	}
	1452
[1008]	1453	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	1454	#endif
	1455	}
	1456
	1457
[1016]	1458	void VspTree::CollectRays(VssRayContainer &rays)
[1002]	1459	{
[1008]	1460	vector<VspLeaf *> leaves;
[1002]	1461
[1008]	1462	vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
[1002]	1463
	1464	for (lit = leaves.begin(); lit != lit_end; ++ lit)
	1465	{
[1008]	1466	VspLeaf leaf = lit;
[1002]	1467	VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
	1468
	1469	for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
	1470	rays.push_back(*rit);
	1471	}
	1472	}
	1473
	1474
[1021]	1475	void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
	1476	{
	1477	mViewCellsManager = vcm;
	1478	}
	1479
	1480
[1016]	1481	void VspTree::ValidateTree()
[1002]	1482	{
[1020]	1483	mVspStats.invalidLeaves = 0;
	1484
[1008]	1485	stack<VspNode *> nodeStack;
[1002]	1486
	1487	if (!mRoot)
	1488	return;
	1489
	1490	nodeStack.push(mRoot);
[1020]	1491
[1002]	1492	while (!nodeStack.empty())
	1493	{
[1008]	1494	VspNode *node = nodeStack.top();
[1002]	1495	nodeStack.pop();
	1496
	1497	if (node->IsLeaf())
	1498	{
[1008]	1499	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	1500
	1501	if (!leaf->GetViewCell()->GetValid())
[1008]	1502	++ mVspStats.invalidLeaves;
[1002]	1503
	1504	// validity flags don't match => repair
	1505	if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
	1506	{
	1507	leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
	1508	PropagateUpValidity(leaf);
	1509	}
	1510	}
	1511	else
	1512	{
[1008]	1513	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1514
	1515	nodeStack.push(interior->GetFront());
	1516	nodeStack.push(interior->GetBack());
	1517	}
	1518	}
	1519
[1008]	1520	Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
[1002]	1521	}
	1522
	1523
	1524
[1016]	1525	void VspTree::CollectViewCells(VspNode *root,
[1002]	1526	bool onlyValid,
	1527	ViewCellContainer &viewCells,
	1528	bool onlyUnmailed) const
	1529	{
[1008]	1530	stack<VspNode *> nodeStack;
[1002]	1531
	1532	if (!root)
	1533	return;
	1534
	1535	nodeStack.push(root);
	1536
	1537	while (!nodeStack.empty())
	1538	{
[1008]	1539	VspNode *node = nodeStack.top();
[1002]	1540	nodeStack.pop();
	1541
	1542	if (node->IsLeaf())
	1543	{
	1544	if (!onlyValid \|\| node->TreeValid())
	1545	{
[1008]	1546	ViewCellLeaf leafVc = dynamic_cast<VspLeaf >(node)->GetViewCell();
[1002]	1547
	1548	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
	1549
	1550	if (!onlyUnmailed \|\| !viewCell->Mailed())
	1551	{
	1552	viewCell->Mail();
	1553	viewCells.push_back(viewCell);
	1554	}
	1555	}
	1556	}
	1557	else
	1558	{
[1008]	1559	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1560
	1561	nodeStack.push(interior->GetFront());
	1562	nodeStack.push(interior->GetBack());
	1563	}
	1564	}
	1565	}
	1566
	1567
[1016]	1568	int VspTree::FindNeighbors(VspLeaf *n,
[1020]	1569	vector<VspLeaf *> &neighbors,
	1570	const bool onlyUnmailed) const
[1002]	1571	{
[1012]	1572	stack<VspNode *> nodeStack;
	1573	nodeStack.push(mRoot);
[1002]	1574
[1012]	1575	const AxisAlignedBox3 box = GetBBox(n);
[1002]	1576
	1577	while (!nodeStack.empty())
	1578	{
[1008]	1579	VspNode *node = nodeStack.top();
[1002]	1580	nodeStack.pop();
	1581
	1582	if (node->IsLeaf())
	1583	{
[1012]	1584	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	1585
	1586	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
	1587	neighbors.push_back(leaf);
[1002]	1588	}
	1589	else
	1590	{
[1008]	1591	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	1592
	1593	if (interior->GetPosition() > box.Max(interior->GetAxis()))
	1594	nodeStack.push(interior->GetBack());
	1595	else
	1596	{
	1597	if (interior->GetPosition() < box.Min(interior->GetAxis()))
	1598	nodeStack.push(interior->GetFront());
	1599	else
	1600	{
	1601	// random decision
	1602	nodeStack.push(interior->GetBack());
	1603	nodeStack.push(interior->GetFront());
	1604	}
	1605	}
	1606	}
	1607	}
[1002]	1608
[1012]	1609	return (int)neighbors.size();
	1610	}
[1002]	1611
	1612
[1012]	1613	// Find random neighbor which was not mailed
[1016]	1614	VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
[1012]	1615	{
	1616	stack<VspNode *> nodeStack;
	1617	nodeStack.push(mRoot);
	1618
	1619	int mask = rand();
	1620
	1621	while (!nodeStack.empty())
	1622	{
	1623	VspNode *node = nodeStack.top();
	1624
	1625	nodeStack.pop();
	1626
	1627	if (node->IsLeaf())
	1628	{
	1629	return dynamic_cast<VspLeaf *>(node);
	1630	}
	1631	else
	1632	{
	1633	VspInterior interior = dynamic_cast<VspInterior >(node);
	1634	VspNode *next;
	1635
	1636	if (GetBBox(interior->GetBack()).Side(plane) < 0)
[1027]	1637	{
[1002]	1638	next = interior->GetFront();
[1027]	1639	}
[1012]	1640	else
[1027]	1641	{
[1012]	1642	if (GetBBox(interior->GetFront()).Side(plane) < 0)
[1027]	1643	{
[1002]	1644	next = interior->GetBack();
[1027]	1645	}
[1012]	1646	else
	1647	{
	1648	// random decision
	1649	if (mask & 1)
	1650	next = interior->GetBack();
	1651	else
	1652	next = interior->GetFront();
	1653	mask = mask >> 1;
	1654	}
[1027]	1655	}
	1656
	1657	nodeStack.push(next);
[1002]	1658	}
	1659	}
[1012]	1660
[1002]	1661	return NULL;
	1662	}
	1663
	1664
[1016]	1665	VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
[1002]	1666	{
[1008]	1667	stack<VspNode *> nodeStack;
[1002]	1668
	1669	nodeStack.push(mRoot);
	1670
	1671	int mask = rand();
	1672
	1673	while (!nodeStack.empty())
	1674	{
[1008]	1675	VspNode *node = nodeStack.top();
[1002]	1676	nodeStack.pop();
	1677
	1678	if (node->IsLeaf())
	1679	{
	1680	if ( (!onlyUnmailed \|\| !node->Mailed()) )
[1008]	1681	return dynamic_cast<VspLeaf *>(node);
[1002]	1682	}
	1683	else
	1684	{
[1008]	1685	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	1686
	1687	// random decision
	1688	if (mask & 1)
	1689	nodeStack.push(interior->GetBack());
	1690	else
	1691	nodeStack.push(interior->GetFront());
	1692
	1693	mask = mask >> 1;
	1694	}
	1695	}
	1696
	1697	return NULL;
	1698	}
	1699
	1700
[1016]	1701	int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
[1002]	1702	{
	1703	int pvsSize = 0;
	1704
	1705	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	1706
	1707	Intersectable::NewMail();
	1708
	1709	for (rit = rays.begin(); rit != rays.end(); ++ rit)
	1710	{
	1711	VssRay ray = (rit).mRay;
	1712
	1713	if (ray->mOriginObject)
	1714	{
	1715	if (!ray->mOriginObject->Mailed())
	1716	{
	1717	ray->mOriginObject->Mail();
	1718	++ pvsSize;
	1719	}
	1720	}
	1721	if (ray->mTerminationObject)
	1722	{
	1723	if (!ray->mTerminationObject->Mailed())
	1724	{
	1725	ray->mTerminationObject->Mail();
	1726	++ pvsSize;
	1727	}
	1728	}
	1729	}
	1730
	1731	return pvsSize;
	1732	}
	1733
	1734
[1016]	1735	float VspTree::GetEpsilon() const
[1002]	1736	{
	1737	return mEpsilon;
	1738	}
	1739
	1740
[1016]	1741	int VspTree::CastLineSegment(const Vector3 &origin,
[1027]	1742	const Vector3 &termination,
	1743	ViewCellContainer &viewcells)
[1002]	1744	{
	1745	int hits = 0;
	1746
	1747	float mint = 0.0f, maxt = 1.0f;
[1012]	1748	const Vector3 dir = termination - origin;
[1002]	1749
[1012]	1750	stack<LineTraversalData> tStack;
	1751
[1002]	1752	Intersectable::NewMail();
	1753	ViewCell::NewMail();
	1754
	1755	Vector3 entp = origin;
	1756	Vector3 extp = termination;
	1757
[1008]	1758	VspNode *node = mRoot;
[1012]	1759	VspNode *farChild;
[1002]	1760
[1012]	1761	float position;
	1762	int axis;
	1763
[1002]	1764	while (1)
	1765	{
	1766	if (!node->IsLeaf())
	1767	{
[1008]	1768	VspInterior in = dynamic_cast<VspInterior >(node);
[1012]	1769	position = in->GetPosition();
	1770	axis = in->GetAxis();
[1002]	1771
[1012]	1772	if (entp[axis] <= position)
[1002]	1773	{
[1012]	1774	if (extp[axis] <= position)
	1775	{
[1047]	1776	node = in->GetBack();
[1012]	1777	// cases N1,N2,N3,P5,Z2,Z3
[1002]	1778	continue;
[1012]	1779	} else
	1780	{
	1781	// case N4
[1047]	1782	node = in->GetBack();
	1783	farChild = in->GetFront();
[1012]	1784	}
	1785	}
	1786	else
[1002]	1787	{
[1012]	1788	if (position <= extp[axis])
	1789	{
[1047]	1790	node = in->GetFront();
[1012]	1791	// cases P1,P2,P3,N5,Z1
[1002]	1792	continue;
[1012]	1793	}
	1794	else
	1795	{
[1047]	1796	node = in->GetFront();
	1797	farChild = in->GetBack();
[1012]	1798	// case P4
	1799	}
[1002]	1800	}
	1801
[1012]	1802	// $$ modification 3.5.2004 - hints from Kamil Ghais
	1803	// case N4 or P4
	1804	const float tdist = (position - origin[axis]) / dir[axis];
	1805	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
[1002]	1806
[1012]	1807	extp = origin + dir * tdist;
	1808	maxt = tdist;
	1809	}
[1002]	1810	else
	1811	{
[1012]	1812	// compute intersection with all objects in this leaf
[1008]	1813	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1012]	1814	ViewCell *vc = leaf->GetViewCell();
	1815
	1816	if (!vc->Mailed())
	1817	{
	1818	vc->Mail();
	1819	viewcells.push_back(vc);
	1820	++ hits;
	1821	}
	1822	#if 0
	1823	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
	1824	#endif
	1825	// get the next node from the stack
	1826	if (tStack.empty())
	1827	break;
	1828
	1829	entp = extp;
	1830	mint = maxt;
[1002]	1831
[1012]	1832	LineTraversalData &s = tStack.top();
	1833	node = s.mNode;
	1834	extp = s.mExitPoint;
	1835	maxt = s.mMaxT;
	1836	tStack.pop();
	1837	}
	1838	}
	1839
	1840	return hits;
	1841	}
	1842
	1843
[1016]	1844	int VspTree::CastRay(Ray &ray)
[1012]	1845	{
	1846	int hits = 0;
	1847
	1848	stack<LineTraversalData> tStack;
	1849	const Vector3 dir = ray.GetDir();
	1850
	1851	float maxt, mint;
	1852
[1020]	1853	if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
[1012]	1854	return 0;
	1855
	1856	Intersectable::NewMail();
	1857	ViewCell::NewMail();
	1858
	1859	Vector3 entp = ray.Extrap(mint);
	1860	Vector3 extp = ray.Extrap(maxt);
	1861
	1862	const Vector3 origin = entp;
	1863
	1864	VspNode *node = mRoot;
	1865	VspNode *farChild = NULL;
	1866
	1867	float position;
	1868	int axis;
	1869
	1870	while (1)
	1871	{
	1872	if (!node->IsLeaf())
	1873	{
	1874	VspInterior in = dynamic_cast<VspInterior >(node);
	1875	position = in->GetPosition();
	1876	axis = in->GetAxis();
	1877
	1878	if (entp[axis] <= position)
	1879	{
	1880	if (extp[axis] <= position)
	1881	{
	1882	node = in->GetBack();
	1883	// cases N1,N2,N3,P5,Z2,Z3
	1884	continue;
[1020]	1885	}
	1886	else
[1012]	1887	{
	1888	// case N4
	1889	node = in->GetBack();
	1890	farChild = in->GetFront();
	1891	}
	1892	}
[1002]	1893	else
[1012]	1894	{
	1895	if (position <= extp[axis])
	1896	{
	1897	node = in->GetFront();
	1898	// cases P1,P2,P3,N5,Z1
	1899	continue;
	1900	}
	1901	else
	1902	{
	1903	node = in->GetFront();
	1904	farChild = in->GetBack();
	1905	// case P4
	1906	}
	1907	}
[1002]	1908
[1012]	1909	// $$ modification 3.5.2004 - hints from Kamil Ghais
	1910	// case N4 or P4
	1911	const float tdist = (position - origin[axis]) / dir[axis];
	1912	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
	1913	extp = origin + dir * tdist;
	1914	maxt = tdist;
	1915	}
	1916	else
	1917	{
	1918	// compute intersection with all objects in this leaf
	1919	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
	1920	ViewCell *vc = leaf->GetViewCell();
	1921
	1922	if (!vc->Mailed())
[1002]	1923	{
[1012]	1924	vc->Mail();
	1925	// todo: add view cells to ray
[1002]	1926	++ hits;
	1927	}
[1012]	1928	#if 0
[1020]	1929	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
[1012]	1930	#endif
	1931	// get the next node from the stack
[1002]	1932	if (tStack.empty())
	1933	break;
	1934
	1935	entp = extp;
[1012]	1936	mint = maxt;
[1002]	1937
[1012]	1938	LineTraversalData &s = tStack.top();
[1002]	1939	node = s.mNode;
	1940	extp = s.mExitPoint;
[1012]	1941	maxt = s.mMaxT;
[1002]	1942	tStack.pop();
	1943	}
	1944	}
[1012]	1945
[1002]	1946	return hits;
	1947	}
	1948
	1949
[1016]	1950	ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
[1002]	1951	{
	1952	if (mRoot == NULL)
	1953	return NULL;
	1954
[1008]	1955	stack<VspNode *> nodeStack;
[1002]	1956	nodeStack.push(mRoot);
	1957
	1958	ViewCellLeaf *viewcell = NULL;
	1959
	1960	while (!nodeStack.empty())
	1961	{
[1008]	1962	VspNode *node = nodeStack.top();
[1002]	1963	nodeStack.pop();
	1964
	1965	if (node->IsLeaf())
	1966	{
[1008]	1967	viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
[1002]	1968	break;
	1969	}
	1970	else
	1971	{
[1008]	1972	VspInterior interior = dynamic_cast<VspInterior >(node);
[1012]	1973
[1002]	1974	// random decision
[1012]	1975	if (interior->GetPosition() - point[interior->GetAxis()] < 0)
[1002]	1976	nodeStack.push(interior->GetBack());
	1977	else
	1978	nodeStack.push(interior->GetFront());
	1979	}
	1980	}
	1981
	1982	if (active)
	1983	return mViewCellsTree->GetActiveViewCell(viewcell);
	1984	else
	1985	return viewcell;
	1986	}
	1987
	1988
[1016]	1989	bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
[1002]	1990	{
[1008]	1991	VspNode *node = mRoot;
[1002]	1992
	1993	while (1)
	1994	{
	1995	// early exit
	1996	if (node->TreeValid())
	1997	return true;
	1998
	1999	if (node->IsLeaf())
	2000	return false;
	2001
[1008]	2002	VspInterior in = dynamic_cast<VspInterior >(node);
[1002]	2003
[1012]	2004	if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
[1002]	2005	{
	2006	node = in->GetBack();
	2007	}
	2008	else
	2009	{
	2010	node = in->GetFront();
	2011	}
	2012	}
[1012]	2013
[1002]	2014	// should never come here
	2015	return false;
	2016	}
	2017
	2018
[1016]	2019	void VspTree::PropagateUpValidity(VspNode *node)
[1002]	2020	{
	2021	const bool isValid = node->TreeValid();
	2022
	2023	// propagative up invalid flag until only invalid nodes exist over this node
	2024	if (!isValid)
	2025	{
	2026	while (!node->IsRoot() && node->GetParent()->TreeValid())
	2027	{
	2028	node = node->GetParent();
	2029	node->SetTreeValid(false);
	2030	}
	2031	}
	2032	else
	2033	{
	2034	// propagative up valid flag until one of the subtrees is invalid
	2035	while (!node->IsRoot() && !node->TreeValid())
	2036	{
	2037	node = node->GetParent();
[1008]	2038	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2039
	2040	// the parent is valid iff both leaves are valid
	2041	node->SetTreeValid(interior->GetBack()->TreeValid() &&
	2042	interior->GetFront()->TreeValid());
	2043	}
	2044	}
	2045	}
	2046
	2047	#if ZIPPED_VIEWCELLS
[1016]	2048	bool VspTree::Export(ogzstream &stream)
[1002]	2049	#else
[1016]	2050	bool VspTree::Export(ofstream &stream)
[1002]	2051	#endif
	2052	{
	2053	ExportNode(mRoot, stream);
	2054
	2055	return true;
	2056	}
	2057
[1006]	2058
[1002]	2059	#if ZIPPED_VIEWCELLS
[1016]	2060	void VspTree::ExportNode(VspNode *node, ogzstream &stream)
[1002]	2061	#else
[1016]	2062	void VspTree::ExportNode(VspNode *node, ofstream &stream)
[1002]	2063	#endif
	2064	{
	2065	if (node->IsLeaf())
	2066	{
[1008]	2067	VspLeaf leaf = dynamic_cast<VspLeaf >(node);
[1002]	2068	ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
	2069
	2070	int id = -1;
	2071	if (viewCell != mOutOfBoundsCell)
	2072	id = viewCell->GetId();
	2073
	2074	stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
	2075	}
	2076	else
[1012]	2077	{
[1008]	2078	VspInterior interior = dynamic_cast<VspInterior >(node);
[1002]	2079
[1012]	2080	AxisAlignedPlane plane = interior->GetPlane();
	2081	stream << "<Interior plane=\"" << plane.mPosition << " "
	2082	<< plane.mAxis << "\">" << endl;
[1002]	2083
	2084	ExportNode(interior->GetBack(), stream);
	2085	ExportNode(interior->GetFront(), stream);
[1012]	2086
[1002]	2087	stream << "</Interior>" << endl;
	2088	}
	2089	}
	2090
[1011]	2091
[1016]	2092	int VspTree::SplitRays(const AxisAlignedPlane &plane,
[1020]	2093	RayInfoContainer &rays,
	2094	RayInfoContainer &frontRays,
	2095	RayInfoContainer &backRays) const
[1011]	2096	{
	2097	int splits = 0;
	2098
	2099	RayInfoContainer::const_iterator rit, rit_end = rays.end();
	2100
	2101	for (rit = rays.begin(); rit != rit_end; ++ rit)
	2102	{
	2103	RayInfo bRay = *rit;
	2104
	2105	VssRay *ray = bRay.mRay;
	2106	float t;
	2107
	2108	// get classification and receive new t
	2109	//-- test if start point behind or in front of plane
[1047]	2110	const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
	2111
	2112
[1027]	2113	#if 1
[1011]	2114	if (side == 0)
	2115	{
	2116	++ splits;
	2117
	2118	if (ray->HasPosDir(plane.mAxis))
	2119	{
	2120	backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2121	frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2122	}
	2123	else
	2124	{
	2125	frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
	2126	backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
	2127	}
	2128	}
	2129	else if (side == 1)
	2130	{
	2131	frontRays.push_back(bRay);
	2132	}
	2133	else
	2134	{
	2135	backRays.push_back(bRay);
	2136	}
[1027]	2137	#else
	2138	if (side == 0)
	2139	{
	2140	++ splits;
[1011]	2141
[1027]	2142	if (ray->HasPosDir(plane.mAxis))
	2143	{
	2144	backRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
	2145	frontRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
	2146	}
	2147	else
	2148	{
	2149	frontRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
	2150	backRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
	2151	}
	2152	}
	2153	else if (side == 1)
	2154	{
	2155	backRays.push_back(bRay);
	2156	}
	2157	else
	2158	{
	2159	frontRays.push_back(bRay);
	2160
	2161	}
	2162	#endif
[1011]	2163	}
	2164
	2165	return splits;
	2166	}
	2167
[1012]	2168
[1016]	2169	AxisAlignedBox3 VspTree::GetBBox(VspNode *node) const
[1012]	2170	{
	2171	if (!node->GetParent())
[1020]	2172	return mBoundingBox;
[1012]	2173
	2174	if (!node->IsLeaf())
	2175	{
[1016]	2176	return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();
[1012]	2177	}
	2178
	2179	VspInterior parent = dynamic_cast<VspInterior >(node->GetParent());
	2180
[1016]	2181	AxisAlignedBox3 box(parent->GetBoundingBox());
[1012]	2182
[1047]	2183	if (parent->GetFront() == node)
	2184	box.SetMin(parent->GetAxis(), parent->GetPosition());
	2185	else
	2186	box.SetMax(parent->GetAxis(), parent->GetPosition());
[1012]	2187
	2188	return box;
	2189	}
	2190
	2191
[1020]	2192
[1021]	2193
	2194	int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
	2195	ViewCellContainer &viewCells) const
	2196	{
[1027]	2197	stack<VspNode *> nodeStack;
	2198
[1021]	2199	ViewCell::NewMail();
	2200
	2201	while (!nodeStack.empty())
	2202	{
[1027]	2203	VspNode *node = nodeStack.top();
[1021]	2204	nodeStack.pop();
	2205
[1027]	2206	const AxisAlignedBox3 bbox = GetBBox(node);
	2207
	2208	if (bbox.Includes(box))
[1021]	2209	{
	2210	// node geometry is contained in box
	2211	CollectViewCells(node, true, viewCells, true);
[1027]	2212	}
	2213	else if (Overlap(bbox, box))
	2214	{
[1021]	2215	if (node->IsLeaf())
	2216	{
	2217	BspLeaf leaf = dynamic_cast<BspLeaf >(node);
	2218
	2219	if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
	2220	{
	2221	leaf->GetViewCell()->Mail();
	2222	viewCells.push_back(leaf->GetViewCell());
	2223	}
	2224	}
	2225	else
	2226	{
[1027]	2227	VspInterior interior = dynamic_cast<VspInterior >(node);
[1021]	2228
[1027]	2229	VspNode *first = interior->GetFront();
	2230	VspNode *second = interior->GetBack();
[1021]	2231
[1027]	2232	nodeStack.push(first);
	2233	nodeStack.push(second);
[1021]	2234	}
[1027]	2235	}
	2236	// default: cull
[1021]	2237	}
	2238
	2239	return (int)viewCells.size();
	2240	}
	2241
	2242
	2243
[1016]	2244	/*****************************************************************/
[1021]	2245	/* class OspTree implementation */
[1016]	2246	/*****************************************************************/
	2247
[1027]	2248
[1022]	2249	OspTree::OspTree():
	2250	mRoot(NULL)
	2251	#if TODO
	2252	mOutOfBoundsCell(NULL),
	2253	mStoreRays(false),
	2254	mUseRandomAxis(false),
	2255	mTimeStamp(1)
	2256	#endif
	2257	{
	2258	#if TODO
	2259	bool randomize = false;
	2260	Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
	2261	if (randomize)
	2262	Randomize(); // initialise random generator for heuristics
[1020]	2263
[1022]	2264	//-- termination criteria for autopartition
	2265	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
	2266	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
	2267	Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
	2268	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
	2269	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
[1023]	2270
[1022]	2271	Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
	2272	Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
	2273
	2274	//-- max cost ratio for early tree termination
	2275	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
	2276
	2277	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	2278	Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
	2279
	2280	// HACK//mTermMinPolygons = 25;
	2281
	2282	//-- factors for bsp tree split plane heuristics
	2283	Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
	2284
	2285	//-- partition criteria
	2286	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
	2287
	2288	// if only the driving axis is used for axis aligned split
	2289	Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
	2290
	2291	//Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
	2292	Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
	2293
	2294	Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
	2295	Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
[1023]	2296
	2297
[1022]	2298	char subdivisionStatsLog[100];
	2299	Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
	2300	mSubdivisionStats.open(subdivisionStatsLog);
	2301
	2302	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
	2303	Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
	2304
	2305
	2306	//-- debug output
	2307
	2308	Debug << "***** VSP BSP options ****** " << endl;
	2309	Debug << "max depth: " << mTermMaxDepth << endl;
	2310	Debug << "min PVS: " << mTermMinPvs << endl;
	2311	Debug << "min probabiliy: " << mTermMinProbability << endl;
	2312	Debug << "min rays: " << mTermMinRays << endl;
	2313	Debug << "max ray contri: " << mTermMaxRayContribution << endl;
	2314	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	2315	Debug << "miss tolerance: " << mTermMissTolerance << endl;
	2316	Debug << "max view cells: " << mMaxViewCells << endl;
	2317	Debug << "randomize: " << randomize << endl;
	2318
	2319	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	2320	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
	2321	Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
	2322	Debug << "max memory: " << mMaxMemory << endl;
	2323	Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
	2324	Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[1023]	2325
[1022]	2326	Debug << "circulating axis: " << mCirculatingAxis << endl;
	2327	Debug << "minband: " << mMinBand << endl;
	2328	Debug << "maxband: " << mMaxBand << endl;
	2329
	2330
	2331	mSplitCandidates = new vector<SortableEntry>;
	2332
	2333	Debug << endl;
	2334	#endif
	2335	}
	2336
	2337
	2338
[1020]	2339	void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
	2340	const ObjectContainer &objects,
	2341	ObjectContainer &back,
	2342	ObjectContainer &front)
[1016]	2343	{
[1020]	2344	ObjectContainer::const_iterator oit, oit_end = objects.end();
	2345
	2346	for (oit = objects.begin(); oit != oit_end; ++ oit)
	2347	{
	2348	// determine the side of this ray with respect to the plane
	2349	const AxisAlignedBox3 box = (*oit)->GetBox();
	2350
	2351	if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
	2352	front.push_back(*oit);
	2353
	2354	if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
	2355	back.push_back(*oit);
	2356	#if TODO
	2357	mStat.objectRefs -= (int)objects.size();
	2358	mStat.objectRefs += objectsBack + objectsFront;
	2359	#endif
	2360	}
[1016]	2361	}
	2362
	2363
[1020]	2364	KdInterior OspTree::SubdivideNode(KdLeaf leaf,
	2365	const AxisAlignedPlane &splitPlane,
	2366	const AxisAlignedBox3 &box,
	2367	AxisAlignedBox3 &backBBox,
	2368	AxisAlignedBox3 &frontBBox)
[1016]	2369	{
[1020]	2370	#if TODO
	2371	mSpatialStat.nodes += 2;
	2372	mSpatialStat.splits[axis];
	2373	#endif
[1016]	2374
[1020]	2375	// add the new nodes to the tree
	2376	KdInterior *node = new KdInterior(leaf->mParent);
	2377
	2378	const int axis = splitPlane.mAxis;
	2379	const float position = splitPlane.mPosition;
	2380
	2381	node->mAxis = axis;
	2382	node->mPosition = position;
	2383	node->mBox = box;
	2384
	2385	backBBox = box;
	2386	frontBBox = box;
	2387
	2388	// first count ray sides
	2389	int objectsBack = 0;
	2390	int objectsFront = 0;
	2391
	2392	backBBox.SetMax(axis, position);
	2393	frontBBox.SetMin(axis, position);
	2394
	2395	ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
	2396
	2397	for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
	2398	{
	2399	// determine the side of this ray with respect to the plane
	2400	const AxisAlignedBox3 box = (*mi)->GetBox();
	2401
	2402	if (box.Max(axis) > position)
	2403	++ objectsFront;
	2404
	2405	if (box.Min(axis) < position)
	2406	++ objectsBack;
	2407	}
	2408
	2409	KdLeaf *back = new KdLeaf(node, objectsBack);
	2410	KdLeaf *front = new KdLeaf(node, objectsFront);
	2411
	2412	// replace a link from node's parent
	2413	if (leaf->mParent)
	2414	leaf->mParent->ReplaceChildLink(leaf, node);
	2415
	2416	// and setup child links
	2417	node->SetupChildLinks(back, front);
	2418
	2419	SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
	2420
	2421	//delete leaf;
	2422	return node;
[1016]	2423	}
	2424
	2425
[1020]	2426	KdNode *OspTree::Subdivide(SplitQueue &tQueue,
	2427	OspSplitCandidate &splitCandidate,
	2428	const bool globalCriteriaMet)
[1016]	2429	{
[1020]	2430	OspTraversalData &tData = splitCandidate.mParentData;
[1016]	2431
[1020]	2432	KdNode *newNode = tData.mNode;
[1016]	2433
[1020]	2434	if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
	2435	{
	2436	OspTraversalData tFrontData;
	2437	OspTraversalData tBackData;
[1016]	2438
[1020]	2439	//-- continue subdivision
	2440
	2441	// create new interior node and two leaf node
	2442	const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
[1027]	2443
[1020]	2444	newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode),
	2445	splitPlane,
	2446	tData.mBoundingBox,
	2447	tFrontData.mBoundingBox,
	2448	tBackData.mBoundingBox);
	2449
	2450	const int maxCostMisses = splitCandidate.mMaxCostMisses;
[1016]	2451
[1020]	2452	// how often was max cost ratio missed in this branch?
	2453	tFrontData.mMaxCostMisses = maxCostMisses;
	2454	tBackData.mMaxCostMisses = maxCostMisses;
	2455
	2456	//-- push the new split candidates on the queue
	2457	OspSplitCandidate *frontCandidate = new OspSplitCandidate();
	2458	OspSplitCandidate *backCandidate = new OspSplitCandidate();
[1016]	2459
[1020]	2460	EvalSplitCandidate(tFrontData, *frontCandidate);
	2461	EvalSplitCandidate(tBackData, *backCandidate);
[1016]	2462
[1020]	2463	tQueue.push(frontCandidate);
	2464	tQueue.push(backCandidate);
	2465
	2466	// delete old leaf node
	2467	DEL_PTR(tData.mNode);
	2468	}
	2469
	2470
	2471	//-- terminate traversal
	2472	if (newNode->IsLeaf())
	2473	{
	2474	//KdLeaf leaf = dynamic_cast<KdLeaf >(newNode);
	2475	EvaluateLeafStats(tData);
	2476	}
	2477
	2478	//-- cleanup
	2479	tData.Clear();
[1016]	2480
[1020]	2481	return newNode;
	2482	}
[1016]	2483
	2484
[1020]	2485	void OspTree::EvalSplitCandidate(OspTraversalData &tData,
	2486	OspSplitCandidate &splitData)
	2487	{
	2488	float frontProb;
	2489	float backtProb;
	2490
	2491	KdLeaf leaf = dynamic_cast<KdLeaf >(tData.mNode);
	2492
	2493	// compute locally best split plane
	2494	const bool success = false;
	2495	#if TODO
	2496	SelectPlane(tData, splitData.mSplitPlane,
	2497	frontData.mProbability, backData.mProbability);
	2498
	2499	//TODO
	2500	// compute global decrease in render cost
	2501	splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
	2502	splitData.mParentData = tData;
	2503	splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
[1016]	2504	#endif
	2505	}
	2506
	2507
[1021]	2508	bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
	2509	{
	2510	// matt: TODO
	2511	return true;
	2512	/* (((int)data.mRays->size() <= mTermMinRays) \|\|
	2513	(data.mPvs <= mTermMinPvs) \|\|
	2514	(data.mProbability <= mTermMinProbability) \|\|
	2515	(data.GetAvgRayContribution() > mTermMaxRayContribution) \|\|
	2516	(data.mDepth >= mTermMaxDepth));*/
	2517	}
[1020]	2518
[1021]	2519
	2520	bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
	2521	{
	2522	// matt: TODO
	2523	return true;
	2524	/*(mOutOfMemory \|\|
	2525	(mVspStats.Leaves() >= mMaxViewCells) \|\|
	2526	(mGlobalCostMisses >= mTermGlobalCostMissTolerance));*/
	2527	}
	2528
	2529
	2530	void OspTree::EvaluateLeafStats(const OspTraversalData &data)
	2531	{
	2532	#if TODO
	2533	// the node became a leaf -> evaluate stats for leafs
	2534	VspLeaf leaf = dynamic_cast<VspLeaf >(data.mNode);
	2535
	2536	if (data.mPvs > mVspStats.maxPvs)
	2537	{
	2538	mVspStats.maxPvs = data.mPvs;
	2539	}
	2540
	2541	mVspStats.pvs += data.mPvs;
	2542
	2543	if (data.mDepth < mVspStats.minDepth)
	2544	{
	2545	mVspStats.minDepth = data.mDepth;
	2546	}
	2547
	2548	if (data.mDepth >= mTermMaxDepth)
	2549	{
	2550	++ mVspStats.maxDepthNodes;
	2551	//Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
	2552	}
	2553
	2554	// accumulate rays to compute rays / leaf
	2555	mVspStats.accumRays += (int)data.mRays->size();
	2556
	2557	if (data.mPvs < mTermMinPvs)
	2558	++ mVspStats.minPvsNodes;
	2559
	2560	if ((int)data.mRays->size() < mTermMinRays)
	2561	++ mVspStats.minRaysNodes;
	2562
	2563	if (data.GetAvgRayContribution() > mTermMaxRayContribution)
	2564	++ mVspStats.maxRayContribNodes;
	2565
	2566	if (data.mProbability <= mTermMinProbability)
	2567	++ mVspStats.minProbabilityNodes;
	2568
	2569	// accumulate depth to compute average depth
	2570	mVspStats.accumDepth += data.mDepth;
	2571
	2572	++ mCreatedViewCells;
	2573
	2574	#ifdef _DEBUG
	2575	Debug << "BSP stats: "
	2576	<< "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
	2577	<< "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
	2578	// << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
	2579	<< "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1027]	2580	<< "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
[1021]	2581	<< "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
	2582	#endif
	2583
	2584	#endif
	2585	}
	2586
	2587
	2588	/*********************************************************************/
	2589	/* class HierarchyManager implementation */
	2590	/*********************************************************************/
	2591
[1027]	2592	HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
	2593	mVspTree(vspTree), mOspTree(ospTree)
[1016]	2594	{
[1020]	2595	}
	2596
	2597
	2598	SplitCandidate *HierarchyManager::NextSplitCandidate()
	2599	{
	2600	SplitCandidate *splitCandidate = mTQueue.top();
[1027]	2601	Debug << "priority: " << splitCandidate->GetPriority() << endl;
[1020]	2602	mTQueue.pop();
	2603
	2604	return splitCandidate;
	2605	}
	2606
	2607
	2608	void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
[1027]	2609	const ObjectContainer &objects,
[1020]	2610	AxisAlignedBox3 *forcedViewSpace,
	2611	RayInfoContainer &rays)
	2612	{
[1027]	2613	mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
[1020]	2614
	2615	long startTime = GetTime();
	2616
	2617	cout << "storing rays ... ";
	2618
	2619	Intersectable::NewMail();
	2620
[1027]	2621	VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[1020]	2622
[1016]	2623	//-- store rays
	2624	for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
	2625	{
	2626	VssRay ray = rit;
	2627
	2628	float minT, maxT;
	2629
	2630	static Ray hray;
	2631	hray.Init(*ray);
[1027]	2632
[1016]	2633	// TODO: not very efficient to implictly cast between rays types
[1027]	2634	if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
[1016]	2635	{
	2636	float len = ray->Length();
	2637
	2638	if (!len)
	2639	len = Limits::Small;
	2640
[1020]	2641	rays.push_back(RayInfo(ray, minT / len, maxT / len));
[1016]	2642	}
	2643	}
[1020]	2644
[1027]	2645	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1020]	2646
[1027]	2647	/// add first candidate for view space partition
	2648	mVspTree.mRoot = new VspLeaf();
	2649	const float prop = mVspTree.mBoundingBox.GetVolume();
	2650
	2651	/// first traversal data
	2652	VspTree::VspTraversalData tData(mVspTree.mRoot,
	2653	0,
	2654	&rays,
	2655	(int)objects.size(),
	2656	//mVspTree.ComputePvsSize(rays),
	2657	prop,
	2658	mVspTree.mBoundingBox);
	2659
	2660	// compute first split candidate
	2661	VspTree::VspSplitCandidate *splitCandidate = new VspTree::VspSplitCandidate();
	2662	mVspTree.EvalSplitCandidate(tData, *splitCandidate);
	2663
	2664	mTQueue.push(splitCandidate);
	2665
[1020]	2666	//mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
[1016]	2667	}
	2668
	2669
[1020]	2670	bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
[1016]	2671	{
[1020]	2672	if (candidate->Type() == SplitCandidate::VIEW_SPACE)
	2673	{
	2674	VspTree::VspSplitCandidate *sc =
	2675	dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
	2676
[1027]	2677	return mVspTree.GlobalTerminationCriteriaMet(sc->mParentData);
[1020]	2678	}
	2679
	2680	return true;
[1016]	2681	}
	2682
	2683
[1020]	2684	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
	2685	const ObjectContainer &objects,
	2686	AxisAlignedBox3 *forcedViewSpace)
[1016]	2687	{
[1020]	2688	RayInfoContainer *rays = new RayInfoContainer();
	2689
	2690	// prepare vsp and osp trees for traversal
[1027]	2691	PrepareConstruction(sampleRays, objects, forcedViewSpace, *rays);
[1016]	2692
[1027]	2693	mVspTree.mVspStats.Reset();
	2694	mVspTree.mVspStats.Start();
[1016]	2695
[1020]	2696	cout << "Constructing view space / object space tree ... \n";
[1016]	2697	const long startTime = GetTime();
	2698
	2699	while (!FinishedConstruction())
	2700	{
	2701	SplitCandidate *splitCandidate = NextSplitCandidate();
	2702
[1020]	2703	const bool globalTerminationCriteriaMet =
	2704	GlobalTerminationCriteriaMet(splitCandidate);
	2705
[1027]	2706	Debug << "cost: " << splitCandidate->GetPriority();
	2707
[1016]	2708	// cost ratio of cost decrease / totalCost
	2709	const float costRatio = splitCandidate->GetPriority() / mTotalCost;
	2710	//Debug << "cost ratio: " << costRatio << endl;
	2711
	2712	if (costRatio < mTermMinGlobalCostRatio)
	2713	++ mGlobalCostMisses;
[1027]	2714
[1020]	2715	//-- subdivide leaf node
	2716	//-- either a object space or view space split
[1016]	2717	if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
	2718	{
	2719	VspTree::VspSplitCandidate *sc =
	2720	dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
	2721
[1027]	2722	VspNode r = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
[1016]	2723	}
[1020]	2724	else // object space split
[1016]	2725	{
	2726	#if TODO
[1027]	2727	KdNode *r = mKdtree.Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
[1016]	2728	#endif
	2729	}
[1020]	2730
	2731	DEL_PTR(splitCandidate);
[1016]	2732	}
	2733
[1020]	2734	cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
[1016]	2735
[1027]	2736	mVspTree.mVspStats.Stop();
[1016]	2737	}
	2738
[1020]	2739
	2740	bool HierarchyManager::FinishedConstruction()
	2741	{
	2742	return mTQueue.empty();
	2743	}
	2744
	2745
[1002]	2746	}

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

Download in other formats: