Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp @ 2353

Revision 2353, 68.6 KB checked in by mattausch, 18 years ago (diff)
cleaned up project files

Rev	Line
[1237]	1	#include <stack>
	2	#include <time.h>
	3	#include <iomanip>
	4
	5	#include "ViewCell.h"
	6	#include "Plane3.h"
	7	#include "HierarchyManager.h"
	8	#include "Mesh.h"
	9	#include "common.h"
	10	#include "Environment.h"
	11	#include "Polygon3.h"
	12	#include "Ray.h"
	13	#include "AxisAlignedBox3.h"
	14	#include "Exporter.h"
	15	#include "Plane3.h"
	16	#include "ViewCellsManager.h"
	17	#include "Beam.h"
	18	#include "KdTree.h"
[1315]	19	#include "IntersectableWrapper.h"
[1237]	20	#include "VspTree.h"
	21	#include "OspTree.h"
[1259]	22	#include "BvHierarchy.h"
[1707]	23	#include "ViewCell.h"
[2094]	24	#include "TraversalTree.h"
[1237]	25
	26
	27	namespace GtpVisibilityPreprocessor {
	28
	29
	30	#define USE_FIXEDPOINT_T 0
[1786]	31	#define STUPID_METHOD 0
[1237]	32
[1895]	33
	34
[1237]	35	/*******************************************************************/
	36	/* class HierarchyManager implementation */
	37	/*******************************************************************/
	38
	39
[1421]	40	HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
[1308]	41	mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
[1279]	42	mOspTree(NULL),
[2094]	43	mBvHierarchy(NULL),
	44	mTraversalTree(NULL)
[1237]	45	{
[1308]	46	switch(mObjectSpaceSubdivisionType)
[1279]	47	{
	48	case KD_BASED_OBJ_SUBDIV:
	49	mOspTree = new OspTree();
	50	mOspTree->mVspTree = mVspTree;
[1379]	51	mOspTree->mHierarchyManager = this;
[1279]	52	break;
	53	case BV_BASED_OBJ_SUBDIV:
	54	mBvHierarchy = new BvHierarchy();
[1379]	55	mBvHierarchy->mHierarchyManager = this;
[1279]	56	break;
	57	default:
	58	break;
	59	}
	60
[1379]	61	// hierarchy manager links view space partition and object space partition
[1421]	62	mVspTree = new VspTree();
[1379]	63	mVspTree->mHierarchyManager = this;
	64
[1580]	65	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
[1288]	66	ParseEnvironment();
[1237]	67	}
	68
	69
[1421]	70	HierarchyManager::HierarchyManager(KdTree *kdTree):
[1308]	71	mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
[1279]	72	mBvHierarchy(NULL)
	73	{
	74	mOspTree = new OspTree(*kdTree);
	75	mOspTree->mVspTree = mVspTree;
	76
[1421]	77	mVspTree = new VspTree();
[1379]	78	mVspTree->mHierarchyManager = this;
[1279]	79
[1580]	80	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
[1288]	81	ParseEnvironment();
	82	}
	83
	84
[1723]	85	void HierarchySubdivisionStats::Print(ostream &app) const
	86	{
	87	app << "#Pass\n" << 0 << endl
	88	<< "#Splits\n" << mNumSplits << endl
	89	<< "#TotalRenderCost\n" << mTotalRenderCost << endl
	90	<< "#TotalEntriesInPvs\n" << mEntriesInPvs << endl
	91	<< "#Memory\n" << mMemoryCost << endl
	92	<< "#StepsView\n" << mViewSpaceSplits << endl
	93	<< "#StepsObject\n" << mObjectSpaceSplits << endl
	94	<< "#VspOspRatio\n" << VspOspRatio() << endl
	95	<< "#FullMem\n" << mFullMemory << endl
	96	<< "#RenderCostDecrease\n" << mRenderCostDecrease << endl
[1744]	97	<< "#Priority\n" << mPriority << endl
[1723]	98	<< "#FpsPerMb\n" << FpsPerMb() << endl
	99	<< endl;
	100	}
	101
	102
[1288]	103	void HierarchyManager::ParseEnvironment()
	104	{
	105	Environment::GetSingleton()->GetFloatValue(
	106	"Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
[2228]	107
	108	Environment::GetSingleton()->GetFloatValue("Hierarchy.minRenderCost", mMinRenderCost);
	109
[1288]	110	Environment::GetSingleton()->GetIntValue(
	111	"Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
	112
[1370]	113	Environment::GetSingleton()->GetBoolValue(
	114	"Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
	115
[1293]	116	Environment::GetSingleton()->GetIntValue(
[1294]	117	"Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
	118
	119	Environment::GetSingleton()->GetIntValue(
[1293]	120	"Hierarchy.Construction.type", mConstructionType);
	121
[1311]	122	Environment::GetSingleton()->GetIntValue(
	123	"Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
[1370]	124
	125	Environment::GetSingleton()->GetIntValue(
	126	"Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
[1311]	127
[1314]	128	Environment::GetSingleton()->GetBoolValue(
	129	"Hierarchy.Construction.repairQueue", mRepairQueue);
	130
[1449]	131	Environment::GetSingleton()->GetBoolValue(
[1564]	132	"Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
[1449]	133
[1580]	134	Environment::GetSingleton()->GetIntValue(
	135	"Hierarchy.Construction.levels", mNumMultiLevels);
	136
[1640]	137	Environment::GetSingleton()->GetIntValue(
	138	"Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
	139
[1684]	140	Environment::GetSingleton()->GetIntValue(
	141	"Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);
	142
[1624]	143	char subdivisionStatsLog[100];
	144	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
	145	mSubdivisionStats.open(subdivisionStatsLog);
	146
[1633]	147	Environment::GetSingleton()->GetBoolValue(
	148	"Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
[1624]	149
[1662]	150	Environment::GetSingleton()->GetBoolValue(
	151	"Hierarchy.Construction.considerMemory", mConsiderMemory);
	152
[1649]	153	Environment::GetSingleton()->GetFloatValue(
	154	"Hierarchy.Termination.maxMemory", mTermMaxMemory);
	155
[1727]	156	Environment::GetSingleton()->GetIntValue(
	157	"Hierarchy.Construction.maxRepairs", mMaxRepairs);
[1736]	158
[1895]	159	Environment::GetSingleton()->GetFloatValue(
[2227]	160	"Hierarchy.Construction.maxAvgRaysPerObject", mMaxAvgRaysPerObject);
[1895]	161
[1912]	162	Environment::GetSingleton()->GetFloatValue(
[2227]	163	"Hierarchy.Construction.minAvgRaysPerObject", mMinAvgRaysPerObject);
[1912]	164
[2130]	165	Environment::GetSingleton()->GetBoolValue(
	166	"Hierarchy.useTraversalTree", mUseTraversalTree);
	167
[1705]	168	Debug << "****** Hierarchy Manager Options *********" << endl;
[1294]	169	Debug << "max leaves: " << mTermMaxLeaves << endl;
[1288]	170	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	171	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
[1314]	172	Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
	173	Debug << "repair queue: " << mRepairQueue << endl;
[1580]	174	Debug << "number of multilevels: " << mNumMultiLevels << endl;
[1633]	175	Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
[1640]	176	Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
[1649]	177	Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
[1673]	178	Debug << "consider memory: " << mConsiderMemory << endl;
[1684]	179	Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
	180	Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
[1727]	181	Debug << "max repairs: " << mMaxRepairs << endl;
[2227]	182	Debug << "max avg rays per object: " << mMaxAvgRaysPerObject << endl;
	183	Debug << "mín avg rays per object: " << mMinAvgRaysPerObject << endl;
[2228]	184	Debug << "mín render cost: " << mMinRenderCost << endl;
[1632]	185
[2199]	186	// for comparing it with byte - value
	187	mTermMaxMemory = (1024.0f 1024.0f);
[1895]	188
[1632]	189	switch (mConstructionType)
	190	{
	191	case 0:
	192	Debug << "construction type: sequential" << endl;
	193	break;
	194	case 1:
	195	Debug << "construction type: interleaved" << endl;
	196	break;
	197	case 2:
	198	Debug << "construction type: gradient" << endl;
	199	break;
	200	case 3:
	201	Debug << "construction type: multilevel" << endl;
	202	break;
	203	default:
	204	Debug << "construction type " << mConstructionType << " unknown" << endl;
	205	break;
	206	}
	207
[1625]	208	//Debug << "min render cost " << mMinRenderCostDecrease << endl;
[1449]	209	Debug << endl;
[1279]	210	}
	211
	212
	213	HierarchyManager::~HierarchyManager()
	214	{
	215	DEL_PTR(mOspTree);
[1421]	216	DEL_PTR(mVspTree);
[1279]	217	DEL_PTR(mBvHierarchy);
	218	}
	219
	220
[1370]	221	int HierarchyManager::GetObjectSpaceSubdivisionType() const
	222	{
	223	return mObjectSpaceSubdivisionType;
	224	}
	225
	226
	227	int HierarchyManager::GetViewSpaceSubdivisionType() const
	228	{
	229	return mViewSpaceSubdivisionType;
	230	}
	231
	232
[1279]	233	void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
	234	{
	235	mVspTree->SetViewCellsManager(vcm);
	236
	237	if (mOspTree)
[1576]	238	{
[1279]	239	mOspTree->SetViewCellsManager(vcm);
[1576]	240	}
[1416]	241	else if (mBvHierarchy)
[1576]	242	{
[1279]	243	mBvHierarchy->SetViewCellsManager(vcm);
[1576]	244	}
[1279]	245	}
	246
	247
	248	void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
	249	{
	250	mVspTree->SetViewCellsTree(vcTree);
	251	}
	252
	253
[1379]	254	VspTree *HierarchyManager::GetVspTree()
	255	{
	256	return mVspTree;
	257	}
	258
[1563]	259	/*
[1379]	260	AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
	261	{
	262	return mVspTree->mBoundingBox;
[1563]	263	}*/
[1379]	264
	265
[1416]	266	AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
	267	{
	268	switch (mObjectSpaceSubdivisionType)
	269	{
	270	case KD_BASED_OBJ_SUBDIV:
	271	return mOspTree->mBoundingBox;
	272	case BV_BASED_OBJ_SUBDIV:
	273	return mBvHierarchy->mBoundingBox;
	274	default:
[1576]	275	// hack: empty box
[1416]	276	return AxisAlignedBox3();
	277	}
	278	}
	279
	280
[1625]	281	SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
[1237]	282	{
[1625]	283	SubdivisionCandidate *splitCandidate = splitQueue.Top();
	284	splitQueue.Pop();
[1237]	285
[1733]	286	// split was not reevaluated before => do it now
[2353]	287	// matt: for new evaluation method, we cannot be sure if the candidate is dirty,
	288	// so ALWAYS reevaluate
	289	if (1 \|\| splitCandidate->IsDirty())
[2198]	290	{
[1733]	291	splitCandidate->EvalCandidate();
[2198]	292	}
[1733]	293
[1237]	294	return splitCandidate;
	295	}
	296
	297
[1830]	298	float HierarchyManager::EvalFullMem() const
	299	{
	300	// question: should I also add the mem usage of the hierarchies?
	301	const float objectSpaceMem = 16;//GetObjectSpaceMemUsage();
	302	const float viewSpaceMem = 16;//mVspTree->GetMemUsage();
	303	// HACK: the same value is used for view and object space
	304	return mHierarchyStats.mMemory + mHierarchyStats.Leaves() * objectSpaceMem;
	305	}
	306
	307
[2332]	308	void HierarchyManager::PrintSubdivisionStats()
[1237]	309	{
[1830]	310
[1723]	311	HierarchySubdivisionStats stats;
[1744]	312
[1723]	313	stats.mNumSplits = mHierarchyStats.Leaves();
	314	stats.mTotalRenderCost = mHierarchyStats.mTotalCost;
	315	stats.mEntriesInPvs = mHierarchyStats.mPvsEntries;
	316	stats.mMemoryCost = mHierarchyStats.mMemory / float(1024 * 1024);
[1830]	317	stats.mFullMemory = EvalFullMem() / float(1024 * 1024);
[1723]	318	stats.mViewSpaceSplits = mVspTree->mVspStats.Leaves();
	319	stats.mObjectSpaceSplits = GetObjectSpaceSubdivisionLeaves();
[1744]	320	stats.mRenderCostDecrease = mHierarchyStats.mRenderCostDecrease;
	321	stats.mPriority = mPriority;
	322
[1723]	323	stats.Print(mSubdivisionStats);
[1237]	324	}
	325
	326
	327	void HierarchyManager::AddSubdivisionStats(const int splits,
	328	const float renderCostDecr,
[1576]	329	const float totalRenderCost,
[1625]	330	const int pvsEntries,
[1640]	331	const float memory,
[1654]	332	const float renderCostPerStorage,
	333	const float vspOspRatio)
[1237]	334	{
[1308]	335	mSubdivisionStats
[1237]	336	<< "#Splits\n" << splits << endl
	337	<< "#RenderCostDecrease\n" << renderCostDecr << endl
[1577]	338	<< "#TotalEntriesInPvs\n" << pvsEntries << endl
[1625]	339	<< "#TotalRenderCost\n" << totalRenderCost << endl
	340	<< "#Memory\n" << memory << endl
[1660]	341	<< "#FpsPerMb\n" << renderCostPerStorage << endl
[1723]	342	<< "#VspOspRatio\n" << vspOspRatio << endl
	343	<< endl;
[1237]	344	}
	345
	346
	347	bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
	348	{
[1421]	349	const bool terminationCriteriaMet =
	350	(0
[1294]	351	\|\| (mHierarchyStats.Leaves() >= mTermMaxLeaves)
[1830]	352	//\|\| (mHierarchyStats.mMemory >= mTermMaxMemory)
	353	\|\| (EvalFullMem() >= mTermMaxMemory)
[1649]	354	\|\| candidate->GlobalTerminationCriteriaMet()
	355	//\|\| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
[1633]	356	//\|\| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
[1288]	357	);
[1421]	358
[1715]	359	#if GTP_DEBUG
[1610]	360	if (terminationCriteriaMet)
[1421]	361	{
	362	Debug << "hierarchy global termination criteria met:" << endl;
	363	Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
[1449]	364	Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
[1649]	365	Debug << "memory: " << mHierarchyStats.mMemory << " " << mTermMaxMemory << endl;
[1830]	366	Debug << "full memory: " << EvalFullMem() << " " << mTermMaxMemory << endl;
[1421]	367	}
[1653]	368	#endif
[1610]	369
[1421]	370	return terminationCriteriaMet;
[1237]	371	}
	372
	373
	374	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
[1311]	375	const ObjectContainer &objects,
	376	AxisAlignedBox3 *forcedViewSpace)
[1237]	377	{
[1679]	378	mTimeStamp = 1;
	379
[1627]	380	switch (mConstructionType)
[1449]	381	{
[1627]	382	case MULTILEVEL:
[1449]	383	ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
[1627]	384	break;
	385	case INTERLEAVED:
	386	case SEQUENTIAL:
[1624]	387	ConstructInterleaved(sampleRays, objects, forcedViewSpace);
[2206]	388	PrintTimings(true);
[1627]	389	break;
	390	case GRADIENT:
	391	ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
[2206]	392	PrintTimings(true);
[1627]	393	break;
	394	default:
	395	break;
[1624]	396	}
[1642]	397
[2124]	398	// hack
[1642]	399	if (mUseMultiLevelConstruction)
	400	{
	401	cout << "starting optimizing multilevel ... " << endl;
[2124]	402	// try to optimize the hierarchy from above
[1642]	403	OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
	404
	405	cout << "finished" << endl;
	406	}
[2093]	407
	408	if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	409	{
	410	mBvHierarchy->SetUniqueNodeIds();
	411	}
[2094]	412
[2124]	413	// create a traversal tree which is optimized for view cell casting
[2130]	414	if (mUseTraversalTree)
[2124]	415	{
	416	CreateTraversalTree();
	417	}
[1624]	418	}
	419
	420
[2187]	421	void HierarchyManager::PrintTimings(const bool lastSplitWasOsp)
	422	{
[2198]	423	double sortTime, evalTime, nodeTime, splitTime, subdTime, planeTime, collectTime, viewCellsTime;
[2187]	424
[2199]	425	sortTime = mBvHierarchy->mSortTimer.TotalTime();
[2187]	426	evalTime = mBvHierarchy->mEvalTimer.TotalTime();
	427	nodeTime = mBvHierarchy->mNodeTimer.TotalTime();
	428	splitTime = mBvHierarchy->mSplitTimer.TotalTime();
	429	subdTime = mBvHierarchy->mSubdivTimer.TotalTime();
[2198]	430	planeTime = mBvHierarchy->mPlaneTimer.TotalTime();
	431	collectTime = mBvHierarchy->mCollectTimer.TotalTime();
[2187]	432
	433	cout << "bvh times"
	434	<< " sort : " << sortTime
	435	<< " eval : " << evalTime
	436	<< " node : " << nodeTime
	437	<< " split: " << splitTime
[2198]	438	<< " subd : " << subdTime
	439	<< " plane: " << planeTime
	440	<< " colct: " << collectTime
	441	<< endl;
[2187]	442
	443	Debug << "bvh times"
	444	<< " sort : " << sortTime
	445	<< " eval : " << evalTime
	446	<< " node : " << nodeTime
	447	<< " split: " << splitTime
[2198]	448	<< " subd : " << subdTime
	449	<< " plane: " << planeTime
	450	<< " colct: " << collectTime
	451	<< endl;
[2187]	452
	453	sortTime = mVspTree->mSortTimer.TotalTime();
	454	evalTime = mVspTree->mEvalTimer.TotalTime();
	455	nodeTime = mVspTree->mNodeTimer.TotalTime();
	456	splitTime = mVspTree->mSplitTimer.TotalTime();
	457	subdTime = mVspTree->mSubdivTimer.TotalTime();
[2198]	458	planeTime = mVspTree->mPlaneTimer.TotalTime();
	459	viewCellsTime = mVspTree->mViewCellsTimer.TotalTime();
[2187]	460
	461	cout << "vsp times"
	462	<< " sort : " << sortTime
	463	<< " eval : " << evalTime
	464	<< " node : " << nodeTime
	465	<< " split: " << splitTime
[2198]	466	<< " subd : " << subdTime
	467	<< " plane: " << planeTime
	468	<< " viewc: " << viewCellsTime
	469	<< endl;
[2187]	470
	471	Debug << "vsp times"
[2198]	472	<< " sort : " << sortTime
	473	<< " eval : " << evalTime
	474	<< " node : " << nodeTime
	475	<< " split: " << splitTime
	476	<< " subd : " << subdTime
	477	<< " plane: " << planeTime
	478	<< " viewc: " << viewCellsTime
	479	<< endl;
	480
[2187]	481	cout << endl;
	482	Debug << endl;
	483	}
	484
	485
[1686]	486	void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
[1626]	487	const ObjectContainer &objects,
	488	AxisAlignedBox3 *forcedViewSpace)
[1624]	489	{
	490	mHierarchyStats.Reset();
	491	mHierarchyStats.Start();
[1625]	492
[1624]	493	mHierarchyStats.mNodes = 2;
[1640]	494
	495	// create first nodes
[2332]	496	mVspTree->Initialise(sampleRays, forcedViewSpace, objects);
[1640]	497	InitialiseObjectSpaceSubdivision(objects);
	498
	499	// hack: assume that object space can be seen from view space
[2332]	500	mHierarchyStats.mTotalCost = mInitialRenderCost = GetViewCellsManager()->ComputeRenderCost(objects.size(), 1);
	501
[1667]	502	// only one entry for start
[1640]	503	mHierarchyStats.mPvsEntries = 1;
[1667]	504	mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
[1640]	505
[2332]	506	PrintSubdivisionStats();
[1624]	507	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
	508
	509	const long startTime = GetTime();
	510	cout << "Constructing view space / object space tree ... \n";
	511
[1633]	512	SplitQueue objectSpaceQueue;
	513	SplitQueue viewSpaceQueue;
	514
[1696]	515	int vspSteps = 0, ospSteps = 0;
[1684]	516
[1624]	517	// use sah for evaluating osp tree construction
	518	// in the first iteration of the subdivision
	519	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	520	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
[1662]	521	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
[1624]	522
[1632]	523	// number of initial splits
[1640]	524	const int minSteps = mMinStepsOfSameType;
[1684]	525	const int maxSteps = mMaxStepsOfSameType;
[1625]	526
[1779]	527	PrepareObjectSpaceSubdivision(objectSpaceQueue, sampleRays, objects);
	528
[1633]	529	/////////////////////////
	530	// calulcate initial object space splits
	531
[1684]	532	SubdivisionCandidateContainer dirtyList;
[1633]	533
	534	// subdivide object space first
	535	// for first round, use sah splits. Once view space partition
	536	// has started, use render cost heuristics instead
[1727]	537	ospSteps = RunConstruction(objectSpaceQueue,
	538	dirtyList,
	539	NULL,
	540	minSteps,
	541	maxSteps);
	542
[1640]	543	cout << "\n" << ospSteps << " object space partition steps taken" << endl;
[1633]	544
[2206]	545	//PrintTimings(true);
[2199]	546
	547	///////////////
	548	//-- create view space
[2237]	549
[1779]	550	PrepareViewSpaceSubdivision(viewSpaceQueue, sampleRays, objects);
[1633]	551
[1684]	552	dirtyList.clear();
[1642]	553	// view space subdivision started
[1633]	554	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	555
[1684]	556	if (1)
	557	{
	558	// rather also start with 100 view space splits to avoid initial bias.
	559	vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
	560	cout << "\n" << vspSteps << " view space partition steps taken" << endl;
	561
	562	/// Repair split queue
[2342]	563	cout << "repairing object space queue ... " << endl;
[1684]	564	RepairQueue(dirtyList, objectSpaceQueue, true);
	565	cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
[1633]	566
[1684]	567	dirtyList.clear();
[2342]	568
	569	/// also repair some candidates from view space queue
	570	/*cout << "repairing view space queue ... " << endl;
	571	CollectRandomCandidates(dirtyList);
	572	RepairQueue(dirtyList, viewSpaceQueue, true);
	573	cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
	574	dirtyList.clear();*/
[2206]	575	//PrintTimings(false);
[1684]	576	}
	577	else
	578	{
	579	// the priorities were calculated for driving sah.
	580	// => recalculate "real" priorities taking visibility into
	581	// account so we can compare to view space splits
	582	ResetQueue(objectSpaceQueue, false);
	583	}
	584
[1624]	585	// This method subdivides view space / object space
	586	// in order to converge to some optimal cost for this partition
	587	// start with object space partiton
	588	// then optimizate view space partition for the current osp
	589	// and vice versa until iteration depth is reached.
[1696]	590
[1684]	591	bool lastSplitWasOsp = true;
	592
[1633]	593	while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
[1624]	594	{
[1662]	595	// decide upon next split type
[1784]	596	const float vspPriority =
	597	viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
	598	const float ospPriority =
	599	objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
[1662]	600
[1640]	601	cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
	602
[1633]	603	// should view or object space be subdivided further?
[1684]	604	if (ospPriority >= vspPriority)
	605	//if (!lastSplitWasOsp)
[1633]	606	{
[2187]	607	/////////////////
	608	// subdivide object space with respect to the objects
	609
[1679]	610	lastSplitWasOsp = true;
[1673]	611	cout << "osp" << endl;
[1684]	612
[1633]	613	// dirtied view space candidates
	614	SubdivisionCandidateContainer dirtyVspList;
[1624]	615
[1727]	616	// subdivide object space first for first round,
	617	// use sah splits. Once view space partition
[1633]	618	// has started, use render cost heuristics instead
[1727]	619	const int ospSteps = RunConstruction(objectSpaceQueue,
	620	dirtyVspList,
	621	viewSpaceQueue.Top(),
	622	minSteps,
	623	maxSteps);
[1624]	624
[1640]	625	cout << "\n" << ospSteps << " object space partition steps taken" << endl;
[1684]	626	Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
	627
[1640]	628	/// Repair split queue, i.e., affected view space candidates
[1633]	629	cout << "repairing queue ... " << endl;
[1736]	630	const int repaired = RepairQueue(dirtyVspList, viewSpaceQueue, true);
[1727]	631
[1784]	632	cout << "\nrepaired " << repaired << " candidates from "
	633	<< (int)dirtyVspList.size() << " dirtied candidates" << endl;
[1633]	634	}
	635	else
	636	{
	637	/////////////////
	638	// subdivide view space with respect to the objects
[1625]	639
[2187]	640	lastSplitWasOsp = false;
	641	cout << "vsp" << endl;
	642
[1684]	643	// dirtied object space candidates
[1633]	644	SubdivisionCandidateContainer dirtyOspList;
[1624]	645
[1633]	646	// process view space candidates
[1727]	647	const int vspSteps = RunConstruction(viewSpaceQueue,
	648	dirtyOspList,
	649	objectSpaceQueue.Top(),
	650	minSteps,
	651	maxSteps);
[1624]	652
[1640]	653	cout << "\n" << vspSteps << " view space partition steps taken" << endl;
[1684]	654	Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
[1625]	655
[1633]	656	// view space subdivision constructed
	657	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
[1624]	658
[1633]	659	/// Repair split queue
	660	cout << "repairing queue ... " << endl;
[1736]	661	const int repaired = RepairQueue(dirtyOspList, objectSpaceQueue, true);
[1727]	662
[1784]	663	cout << "\nrepaired " << repaired << " candidates from "
	664	<< (int)dirtyOspList.size() << " dirtied candidates" << endl;
[1633]	665	}
[2187]	666
[2206]	667	//PrintTimings(lastSplitWasOsp);
[1449]	668	}
[1633]	669
[1624]	670	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	671
	672	mHierarchyStats.Stop();
	673	mVspTree->mVspStats.Stop();
[1625]	674
[1649]	675	FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
[1449]	676	}
	677
	678
	679	void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
	680	const ObjectContainer &objects,
	681	AxisAlignedBox3 *forcedViewSpace)
	682	{
[1308]	683	mHierarchyStats.Reset();
	684	mHierarchyStats.Start();
[1664]	685
	686	// two nodes for view space and object space
	687	mHierarchyStats.mNodes = 2;
[1640]	688	mHierarchyStats.mPvsEntries = 1;
[1667]	689	mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
[2332]	690	mHierarchyStats.mTotalCost = GetViewCellsManager()->ComputeRenderCost(objects.size(), 1);
[1449]	691
[1624]	692	mHierarchyStats.mRenderCostDecrease = 0;
[1237]	693
[2332]	694	PrintSubdivisionStats();
[1624]	695	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
	696
[1311]	697	const long startTime = GetTime();
[1308]	698	cout << "Constructing view space / object space tree ... \n";
[1237]	699
[1640]	700	// create only roots
[2332]	701	mVspTree->Initialise(sampleRays, forcedViewSpace, objects);
[1640]	702	InitialiseObjectSpaceSubdivision(objects);
[1379]	703
[1633]	704	// use objects for evaluating vsp tree construction in the
	705	// first levels of the subdivision
[1323]	706	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
	707	mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
	708
[1370]	709	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	710	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
	711
[1632]	712	// start view space subdivison immediately?
[1329]	713	if (StartViewSpaceSubdivision())
	714	{
[1624]	715	// prepare vsp tree for traversal
[1640]	716	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
[1779]	717	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
[1329]	718	}
	719
[1323]	720	// start object space subdivision immediately?
	721	if (StartObjectSpaceSubdivision())
	722	{
	723	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
[1779]	724	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
[1323]	725	}
[1784]	726
[1624]	727	// begin subdivision
[1667]	728	RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
[1308]	729
[1418]	730	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1370]	731
[1548]	732	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
	733	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	734
[1313]	735	mHierarchyStats.Stop();
[1259]	736	mVspTree->mVspStats.Stop();
[1649]	737
	738	FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
[1237]	739	}
	740
	741
[1779]	742	void HierarchyManager::PrepareViewSpaceSubdivision(SplitQueue &tQueue,
	743	const VssRayContainer &sampleRays,
	744	const ObjectContainer &objects)
[1311]	745	{
[1632]	746	cout << "\npreparing view space hierarchy construction ... " << endl;
[1625]	747
[1580]	748	// hack: reset global cost misses
[1548]	749	mHierarchyStats.mGlobalCostMisses = 0;
[1625]	750
[1311]	751	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
[1779]	752	mVspTree->PrepareConstruction(tQueue, sampleRays, *viewSpaceRays);
[1311]	753
[2332]	754	if (0)
	755	{
[2342]	756	/////////
	757	//-- new render cost
	758
[2332]	759	mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
	760	cout << "\nreseting cost for vsp construction, new total cost: " << mHierarchyStats.mTotalCost << endl;
	761	}
[1311]	762	}
	763
	764
[1640]	765	float HierarchyManager::GetObjectSpaceMemUsage() const
	766	{
	767	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	768	{
	769	// TODO;
	770	}
	771	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	772	{
	773	return mBvHierarchy->GetMemUsage();
	774	}
	775
	776	return -1;
	777	}
	778
[1844]	779
[1640]	780	void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
	781	{
	782	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	783	{
	784	// TODO;
	785	}
	786	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	787	{
	788	mBvHierarchy->Initialise(objects);
	789	}
	790	}
	791
	792
[1779]	793	void HierarchyManager::PrepareObjectSpaceSubdivision(SplitQueue &tQueue,
	794	const VssRayContainer &sampleRays,
	795	const ObjectContainer &objects)
[1308]	796	{
[1625]	797	// hack: reset global cost misses
	798	mHierarchyStats.mGlobalCostMisses = 0;
[1522]	799
[1308]	800	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	801	{
[1779]	802	return PrepareOspTree(tQueue, sampleRays, objects);
[1308]	803	}
	804	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	805	{
[1779]	806	return PrepareBvHierarchy(tQueue, sampleRays, objects);
[1308]	807	}
	808	}
[1294]	809
[1308]	810
[1779]	811	void HierarchyManager::PrepareBvHierarchy(SplitQueue &tQueue,
	812	const VssRayContainer &sampleRays,
	813	const ObjectContainer &objects)
[1294]	814	{
[1421]	815	const long startTime = GetTime();
	816
	817	cout << "preparing bv hierarchy construction ... " << endl;
[1548]	818
[1294]	819	// compute first candidate
[1779]	820	mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
[1294]	821
[1624]	822	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
	823	Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
[1294]	824
[1548]	825	cout << "finished bv hierarchy preparation in "
	826	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1294]	827	}
	828
	829
[1779]	830	void HierarchyManager::PrepareOspTree(SplitQueue &tQueue,
	831	const VssRayContainer &sampleRays,
	832	const ObjectContainer &objects)
[1294]	833	{
[1370]	834	cout << "starting osp tree construction ... " << endl;
	835
[1294]	836	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
	837
	838	// start with one big kd cell - all objects can be seen from everywhere
	839	// note: only true for view space = object space
	840
	841	// compute first candidate
[1779]	842	mOspTree->PrepareConstruction(tQueue, sampleRays, objects, *objectSpaceRays);
[1294]	843
[1624]	844	mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
[1625]	845	Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
[1294]	846	}
	847
	848
[1912]	849	float HierarchyManager::EvalCorrectedPvs(const float childPvs,
	850	const float totalPvs,
[2227]	851	const float avgRaysPerObjects) const
[1911]	852	{
[2228]	853	// don't correct pvss
	854	if (mMaxAvgRaysPerObject <= mMinAvgRaysPerObject)
	855	{
	856	return childPvs;
	857	}
	858
[1912]	859	// assume pvs sampled sufficiently => take child pvs
[2231]	860	if (avgRaysPerObjects >= mMaxAvgRaysPerObject)
[1913]	861	{
[1912]	862	return childPvs;
[1913]	863	}
[2228]	864
	865	// assume pvs not sampled sufficiently => pvs equal to parent pvs
	866	// we should not subdivide further from this point
	867	if (avgRaysPerObjects <= mMinAvgRaysPerObject)
[1913]	868	{
[2232]	869	//cout << "t ";// << avgRaysPerObjects << " ";
[1912]	870	return totalPvs;
[1913]	871	}
[1911]	872
[2228]	873	///////////
	874	//-- blend pvss
	875
[2227]	876	const float alpha = (mMaxAvgRaysPerObject - avgRaysPerObjects) /
	877	(mMaxAvgRaysPerObject - mMinAvgRaysPerObject);
[1911]	878
[2227]	879	/// rays per object == max threshold => alpha == 0 => newPvs is childPvs
	880	/// rays per object == min threshold => alpha == 1 => newPvs is totalPvs
	881
	882	const float beta = alpha * (totalPvs - childPvs);
[1915]	883	#if 1
	884	const float newPvs = childPvs + beta;
	885	#else
	886	const float newPvs = alpha * childPvs + (1.0f - alpha) * totalPvs;
	887	#endif
[2233]	888	//cout << "b ";
[1916]	889	//cout << "alpha " << alpha << " beta: " << beta << " child: " << childPvs << " parent: " << totalPvs << endl;
[1913]	890
[2233]	891	if (0 &&
	892	((newPvs < childPvs - Limits::Small) \|\| (newPvs > totalPvs + Limits::Small)))
	893	cout << "w: " << newPvs << " < child (" << childPvs << ") or > parent (" << totalPvs << ")" << endl;
[2227]	894
[1913]	895	return newPvs;
[1911]	896	}
	897
	898
[1624]	899	bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
[1625]	900	SplitQueue &splitQueue,
[2224]	901	//const bool repairQueue,
	902	SubdivisionCandidateContainer &dirtyList)
[1237]	903	{
[1624]	904	const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
[2224]	905	const bool success = sc->Apply(splitQueue, terminationCriteriaMet, dirtyList);
[1444]	906
[1744]	907	if (sc->IsDirty())
[1745]	908	cerr << "Error: Should never come here!" << endl;
[1744]	909
[1610]	910	if (!success) // split was not taken
	911	{
[2232]	912	//cout << "x";
[1610]	913	return false;
	914	}
	915
[2198]	916
[1610]	917	///////////////
[1624]	918	//-- split was successful => update stats and queue
[1610]	919
	920	// cost ratio of cost decrease / totalCost
[1624]	921	const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
[1744]	922	//cout << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
[1610]	923
	924	if (costRatio < mTermMinGlobalCostRatio)
	925	{
	926	++ mHierarchyStats.mGlobalCostMisses;
	927	}
	928
[1640]	929	/////////////
[1580]	930	// update stats
[1640]	931
[1624]	932	mHierarchyStats.mNodes += 2;
[1640]	933	mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
	934
	935	const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
	936	mHierarchyStats.mPvsEntries += pvsEntriesIncr;
[2198]	937	//cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.mPvsEntries << endl;
[1640]	938
	939	// memory size in byte
[1895]	940	float mem = (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
	941
[2227]	942	#if USE_AVGRAYCONTRI
[1895]	943	// high avg ray contri, the result is influenced by undersampling
	944	// => decrease priority
[2227]	945
	946	if (sc->GetAvgRayContribution() > mMaxAvgRayContri)
[1895]	947	{
	948	const float factor = 1.0f + sc->GetAvgRayContribution() - mMaxAvgRayContri;
[1899]	949	cout << "h " << factor << endl;
[1895]	950
	951	mem *= factor;
	952	}
[2227]	953	#endif
	954
[1895]	955	mHierarchyStats.mMemory += mem;
[1624]	956	mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
[1744]	957
	958	mPriority = sc->GetPriority();
[1624]	959
[2228]	960	cout << sc->Type() << " ";
	961
[1895]	962	//////////
	963	// show current memory
	964
[1654]	965	static float memoryCount = 0;
	966
	967	if (mHierarchyStats.mMemory > memoryCount)
	968	{
	969	memoryCount += 100000;
[1684]	970	cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
	971	<< " MB, steps: " << mHierarchyStats.Leaves() << endl;
[1654]	972	}
	973
[1640]	974	// output stats
[2332]	975	PrintSubdivisionStats();
[1624]	976
[1416]	977	return true;
[1237]	978	}
	979
	980
[1370]	981	int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
	982	{
	983	int maxDepth = 0;
	984
	985	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	986	{
	987	maxDepth = mOspTree->mOspStats.maxDepth;
	988	}
	989	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	990	{
	991	maxDepth = mBvHierarchy->mBvhStats.maxDepth;
	992	}
	993
	994	return maxDepth;
	995	}
	996
	997
[1640]	998	int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
	999	{
	1000	int maxLeaves= 0;
	1001
	1002	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	1003	{
	1004	maxLeaves = mOspTree->mOspStats.Leaves();
	1005	}
	1006	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	1007	{
	1008	maxLeaves = mBvHierarchy->mBvhStats.Leaves();
	1009	}
	1010
	1011	return maxLeaves;
	1012	}
	1013
	1014
[1663]	1015	int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
	1016	{
	1017	int maxLeaves = 0;
	1018
	1019	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	1020	{
	1021	maxLeaves = mOspTree->mOspStats.nodes;
	1022	}
	1023	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	1024	{
	1025	maxLeaves = mBvHierarchy->mBvhStats.nodes;
	1026	}
	1027
	1028	return maxLeaves;
	1029	}
	1030
[1308]	1031	bool HierarchyManager::StartObjectSpaceSubdivision() const
[1237]	1032	{
[1370]	1033	// view space construction already started
	1034	if (ObjectSpaceSubdivisionConstructed())
	1035	return false;
	1036
	1037	// start immediately with object space subdivision?
	1038	if (mStartWithObjectSpace)
	1039	return true;
	1040
	1041	// is the queue empty again?
	1042	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
	1043	return true;
	1044
	1045	// has the depth for subdivision been reached?
	1046	return
	1047	((mConstructionType == INTERLEAVED) &&
[1640]	1048	(mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
[1308]	1049	}
	1050
	1051
[1329]	1052	bool HierarchyManager::StartViewSpaceSubdivision() const
	1053	{
[1370]	1054	// view space construction already started
	1055	if (ViewSpaceSubdivisionConstructed())
	1056	return false;
	1057
	1058	// start immediately with view space subdivision?
	1059	if (!mStartWithObjectSpace)
	1060	return true;
	1061
	1062	// is the queue empty again?
	1063	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
	1064	return true;
	1065
	1066	// has the depth for subdivision been reached?
	1067	return
	1068	((mConstructionType == INTERLEAVED) &&
[1640]	1069	(mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
[1329]	1070	}
	1071
	1072
[1449]	1073	void HierarchyManager::RunConstruction(const bool repairQueue,
	1074	const VssRayContainer &sampleRays,
[1311]	1075	const ObjectContainer &objects,
[1640]	1076	AxisAlignedBox3 *forcedViewSpace)
[1308]	1077	{
[2224]	1078	SubdivisionCandidate::NewMail();
	1079
[1313]	1080	while (!FinishedConstruction())
	1081	{
[1625]	1082	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
[1632]	1083
[1415]	1084	///////////////////
[1237]	1085	//-- subdivide leaf node
[1415]	1086
[2224]	1087	SubdivisionCandidateContainer dirtyList;
	1088
	1089	ApplySubdivisionCandidate(sc, mTQueue, dirtyList);
[1580]	1090
[2224]	1091	if (repairQueue)
	1092	{
	1093	// reevaluate candidates affected by the split for view space splits,
	1094	// this would be object space splits and other way round
	1095	RepairQueue(dirtyList, mTQueue, mRecomputeSplitPlaneOnRepair);
	1096	}
	1097
[1313]	1098	// we use objects for evaluating vsp tree construction until
[1415]	1099	// a certain depth once a certain depth existiert ...
[1313]	1100	if (StartObjectSpaceSubdivision())
	1101	{
[1323]	1102	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
[1314]	1103
[1640]	1104	cout << "\nstarting object space subdivision after "
[1723]	1105	<< mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem="
	1106	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
[1329]	1107
[1779]	1108	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
[1640]	1109
[1313]	1110	cout << "reseting queue ... ";
[1640]	1111	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
[1313]	1112	cout << "finished" << endl;
	1113	}
	1114
[1329]	1115	if (StartViewSpaceSubdivision())
	1116	{
	1117	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	1118
[1723]	1119	cout << "\nstarting view space subdivision at "
[1640]	1120	<< GetObjectSpaceSubdivisionLeaves() << " ("
[1723]	1121	<< mMinStepsOfSameType << ") , mem="
	1122	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
[1329]	1123
[1779]	1124	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
[1329]	1125
	1126	cout << "reseting queue ... ";
[1640]	1127	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
[1329]	1128	cout << "finished" << endl;
	1129	}
	1130
[1624]	1131	DEL_PTR(sc);
[1237]	1132	}
	1133	}
	1134
	1135
[1449]	1136	void HierarchyManager::RunConstruction(const bool repairQueue)
	1137	{
[1580]	1138	// main loop
[1449]	1139	while (!FinishedConstruction())
	1140	{
[1625]	1141	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
[1649]	1142
[1624]	1143	////////
	1144	//-- subdivide leaf node of either type
[1904]	1145
[2224]	1146	SubdivisionCandidateContainer dirtyList;
	1147	ApplySubdivisionCandidate(sc, mTQueue, dirtyList);
[1642]	1148
[2224]	1149	if (repairQueue)
	1150	{
	1151	RepairQueue(dirtyList, mTQueue, mRecomputeSplitPlaneOnRepair);
	1152	}
	1153
[1624]	1154	DEL_PTR(sc);
[1449]	1155	}
	1156	}
	1157
	1158
[1625]	1159	int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
[1633]	1160	SubdivisionCandidateContainer &dirtyCandidates,
[1667]	1161	SubdivisionCandidate *oldCandidate,
[1676]	1162	const int minSteps,
	1163	const int maxSteps)
[1624]	1164	{
[1676]	1165	if (minSteps >= maxSteps)
	1166	cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
	1167
[1625]	1168	int steps = 0;
[1633]	1169	SubdivisionCandidate::NewMail();
[1625]	1170
[1624]	1171	// main loop
[1634]	1172	while (!splitQueue.Empty())
[1624]	1173	{
[1701]	1174	const float priority = splitQueue.Top()->GetPriority();
[1686]	1175	const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
[1679]	1176
[1701]	1177	// minimum slope reached
	1178	if ((steps >= maxSteps) \|\| ((priority < threshold) && !(steps < minSteps)))
	1179	{
[1745]	1180	cout << "\nbreaking on " << priority << " smaller than " << threshold << endl;
[1701]	1181	break;
	1182	}
	1183
[1624]	1184	////////
	1185	//-- subdivide leaf node of either type
	1186
[1727]	1187	SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
[2227]	1188
[2224]	1189	const bool success = ApplySubdivisionCandidate(sc, splitQueue, dirtyCandidates);
[1625]	1190
[1632]	1191	if (success)
	1192	{
[2224]	1193	//sc->CollectDirtyCandidates(dirtyCandidates, true);
[2228]	1194	//if (steps % 10 == 0) cout << sc->Type() << " ";
[2227]	1195
[1633]	1196	++ steps;
[1632]	1197	}
[1696]	1198
	1199	DEL_PTR(sc);
[1624]	1200	}
[1625]	1201
	1202	return steps;
[1624]	1203	}
	1204
	1205
[1779]	1206	void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue,
	1207	const VssRayContainer &sampleRays,
	1208	const ObjectContainer &objects)
[1580]	1209	{
	1210	// object space partition constructed => reconstruct
[1557]	1211	switch (mObjectSpaceSubdivisionType)
	1212	{
	1213	case BV_BASED_OBJ_SUBDIV:
[1580]	1214	{
	1215	cout << "\nreseting bv hierarchy" << endl;
	1216	Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
[1663]	1217
	1218	// rather use this: remove previous nodes and add the two new ones
	1219	//mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
	1220	mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
[1649]	1221
[1663]	1222	// create root
[1642]	1223	mBvHierarchy->Initialise(objects);
[1649]	1224
[1779]	1225	mBvHierarchy->Reset(tQueue, sampleRays, objects);
[1649]	1226
[1625]	1227	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
[1663]	1228
[1662]	1229	//mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
[1649]	1230	mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
[1663]	1231
[1667]	1232	mHierarchyStats.mMemory =
	1233	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
[1642]	1234
[1662]	1235	mHierarchyStats.mRenderCostDecrease = 0;
	1236
[1625]	1237	// evaluate stats before first subdivision
[2332]	1238	PrintSubdivisionStats();
[1649]	1239	cout << "finished bv hierarchy preparation" << endl;
[1580]	1240	}
[1548]	1241	break;
[1557]	1242
[1548]	1243	case KD_BASED_OBJ_SUBDIV:
	1244	// TODO
	1245	default:
	1246	break;
	1247	}
[1449]	1248	}
	1249
	1250
[1779]	1251	void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue,
	1252	const VssRayContainer &sampleRays,
	1253	const ObjectContainer &objects,
	1254	AxisAlignedBox3 *forcedViewSpace)
[1557]	1255	{
[2332]	1256	ViewCellsManager *vm = GetViewCellsManager();
[1557]	1257
[1624]	1258	// HACK: rather not destroy vsp tree
[1580]	1259	DEL_PTR(mVspTree);
	1260	mVspTree = new VspTree();
[1649]	1261
[1580]	1262	mVspTree->mHierarchyManager = this;
[1649]	1263	mVspTree->mViewCellsManager = vm;
[1580]	1264
[2332]	1265	mVspTree->Initialise(sampleRays, forcedViewSpace, objects);
[1580]	1266
[2332]	1267
[1779]	1268	//////////
[1662]	1269	//-- reset stats
[2332]	1270
[1779]	1271	mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();
	1272	//-mVspTree->mVspStats.nodes + 1;
[1662]	1273
[1779]	1274	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
[1662]	1275
	1276	mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
[1661]	1277	mHierarchyStats.mRenderCostDecrease = 0;
	1278
[1779]	1279	mHierarchyStats.mMemory =
	1280	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
[1662]	1281
[1640]	1282	// evaluate new stats before first subdivsiion
[2332]	1283	PrintSubdivisionStats();
[1557]	1284	}
	1285
	1286
[1449]	1287	void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,
	1288	const ObjectContainer &objects,
	1289	AxisAlignedBox3 *forcedViewSpace)
	1290	{
	1291	mHierarchyStats.Reset();
	1292	mHierarchyStats.Start();
[1624]	1293	mHierarchyStats.mNodes = 2;
[1449]	1294
[2332]	1295	mHierarchyStats.mTotalCost = GetViewCellsManager()->ComputeRenderCost(objects.size(), 1);
[1624]	1296	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
[1449]	1297
	1298	const long startTime = GetTime();
	1299	cout << "Constructing view space / object space tree ... \n";
	1300
[1640]	1301	// initialise view / object space
[2332]	1302	mVspTree->Initialise(sampleRays, forcedViewSpace, objects);
[1640]	1303	InitialiseObjectSpaceSubdivision(objects);
[1449]	1304
[1580]	1305	// use sah for evaluating osp tree construction
	1306	// in the first iteration of the subdivision
[1642]	1307
[1449]	1308	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	1309	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
[1640]	1310
[1779]	1311	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
[1640]	1312
[1649]	1313	//////////////////////////
[1642]	1314
	1315
[1640]	1316	const int limit = mNumMultiLevels;
	1317	int i = 0;
	1318
	1319	// This method subdivides view space / object space
	1320	// in order to converge to some optimal cost for this partition
	1321	// start with object space partiton
	1322	// then optimizate view space partition for the current osp
	1323	// and vice versa until iteration depth is reached.
	1324	while (1)
	1325	{
	1326	char subdivisionStatsLog[100];
	1327	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
	1328	mSubdivisionStats.open(subdivisionStatsLog);
	1329
	1330	// subdivide object space first
[1779]	1331	ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
[1640]	1332
	1333	// process object space candidates
	1334	RunConstruction(false);
	1335
	1336	// object space subdivision constructed
	1337	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
	1338
	1339	cout << "iteration " << i << " of " << limit << " finished" << endl;
	1340	mSubdivisionStats.close();
	1341
	1342	if ((i ++) >= limit)
	1343	break;
	1344
	1345	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
	1346	mSubdivisionStats.open(subdivisionStatsLog);
	1347
[1649]	1348
[1640]	1349	/////////////////
	1350	// subdivide view space with respect to the objects
	1351
[1779]	1352	ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
	1353
[1640]	1354	// view space subdivision constructed
	1355	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	1356
	1357	// process view space candidates
	1358	RunConstruction(false);
	1359
	1360	cout << "iteration " << i << " of " << limit << " finished" << endl;
	1361	mSubdivisionStats.close();
	1362
	1363	if ((i ++) >= limit)
	1364	break;
	1365	}
[1635]	1366
[1640]	1367	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1580]	1368
[1640]	1369	mHierarchyStats.Stop();
	1370	mVspTree->mVspStats.Stop();
	1371	FinishObjectSpaceSubdivision(objects);
	1372	}
	1373
	1374
	1375	void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,
	1376	const ObjectContainer &objects,
	1377	AxisAlignedBox3 *forcedViewSpace)
	1378	{
[1649]	1379	const long startTime = GetTime();
	1380	const int limit = mNumMultiLevels;
	1381
	1382	// open up new subdivision
	1383	mSubdivisionStats.close();
	1384
	1385	int steps = 0;
	1386
	1387	int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
	1388	int maxObjectSpaceLeaves;
	1389
[1642]	1390	// set the number of leaves 'evaluated' from the previous methods
[1649]	1391	// we go for the same numbers, but we try to optimize both subdivisions
[1642]	1392	switch (mObjectSpaceSubdivisionType)
	1393	{
	1394	case BV_BASED_OBJ_SUBDIV:
[1649]	1395	maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
[1642]	1396	break;
	1397	case KD_BASED_OBJ_SUBDIV:
[1649]	1398	maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
[1642]	1399	default:
[1649]	1400	maxObjectSpaceLeaves = 0;
[1642]	1401	break;
	1402	}
[1640]	1403
[1624]	1404	// This method subdivides view space / object space
	1405	// in order to converge to some optimal cost for this partition
[1557]	1406	// start with object space partiton
	1407	// then optimizate view space partition for the current osp
	1408	// and vice versa until iteration depth is reached.
	1409	while (1)
[1548]	1410	{
[1580]	1411	char subdivisionStatsLog[100];
[1642]	1412	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
[1580]	1413	mSubdivisionStats.open(subdivisionStatsLog);
	1414
[1624]	1415	// subdivide object space first
[1779]	1416	ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
[1649]	1417
	1418	// set the number of leaves 'evaluated' from the previous methods
	1419	// we go for the same numbers, but we try to optimize both subdivisions
	1420	mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
[1624]	1421
[1548]	1422	// process object space candidates
	1423	RunConstruction(false);
[1449]	1424
[1642]	1425	cout << "iteration " << steps << " of " << limit << " finished" << endl;
[1580]	1426	mSubdivisionStats.close();
[1635]	1427
[1642]	1428	if ((++ steps) >= limit)
[1557]	1429	break;
	1430
[1642]	1431	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
[1580]	1432	mSubdivisionStats.open(subdivisionStatsLog);
	1433
[1557]	1434	/////////////////
[1580]	1435	// subdivide view space with respect to the objects
	1436
[1779]	1437	ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
[1649]	1438
	1439	mVspTree->mMaxViewCells = maxViewSpaceLeaves;
[1624]	1440
[1548]	1441	// process view space candidates
	1442	RunConstruction(false);
[1624]	1443
[1642]	1444	cout << "iteration " << steps << " of " << limit << " finished" << endl;
[1580]	1445	mSubdivisionStats.close();
	1446
[1642]	1447	if ((++ steps) >= limit)
[1557]	1448	break;
[1548]	1449	}
	1450
[1449]	1451	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	1452
	1453	mHierarchyStats.Stop();
	1454	mVspTree->mVspStats.Stop();
	1455	FinishObjectSpaceSubdivision(objects);
	1456	}
	1457
	1458
[1640]	1459
[1237]	1460	bool HierarchyManager::FinishedConstruction() const
	1461	{
	1462	return mTQueue.Empty();
	1463	}
	1464
	1465
[1313]	1466	bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
[1311]	1467	{
[1642]	1468	/*switch (mObjectSpaceSubdivisionType)
[1311]	1469	{
	1470	case KD_BASED_OBJ_SUBDIV:
	1471	return mOspTree && mOspTree->GetRoot();
	1472	case BV_BASED_OBJ_SUBDIV:
[1344]	1473	return mBvHierarchy && mBvHierarchy->GetRoot();
[1311]	1474	default:
[1580]	1475	return false;
[1642]	1476	}*/
	1477	return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
[1311]	1478	}
	1479
	1480
[1329]	1481	bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
	1482	{
[1635]	1483	return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
	1484	//return mVspTree && mVspTree->GetRoot();
[1329]	1485	}
	1486
	1487
[1625]	1488	void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
	1489	SubdivisionCandidateContainer &dirtyList)
[1237]	1490	{
[1625]	1491	SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
[1633]	1492	SubdivisionCandidate::NewMail();
[1625]	1493
	1494	for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
	1495	{
[1633]	1496	(*sit)->CollectDirtyCandidates(dirtyList, true);
[1625]	1497	}
	1498	}
	1499
	1500
[1736]	1501	int HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
	1502	SplitQueue &splitQueue,
	1503	const bool recomputeSplitPlaneOnRepair)
[1625]	1504	{
[1237]	1505	// for each update of the view space partition:
	1506	// the candidates from object space partition which
	1507	// have been afected by the view space split (the kd split candidates
	1508	// which saw the view cell which was split) must be reevaluated
	1509	// (maybe not locally, just reinsert them into the queue)
	1510	//
	1511	// vice versa for the view cells
	1512	// for each update of the object space partition
	1513	// reevaluate split candidate for view cells which saw the split kd cell
	1514	//
	1515	// the priority queue update can be solved by implementing a binary heap
	1516	// (explicit data structure, binary tree)
	1517	// *) inserting and removal is efficient
	1518	// *) search is not efficient => store queue position with each
	1519	// split candidate
	1520
[1736]	1521	int repaired = 0;
	1522
[1237]	1523	// collect list of "dirty" candidates
[1580]	1524	const long startTime = GetTime();
[1625]	1525	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
[1624]	1526
[1727]	1527	const float prop = (float)mMaxRepairs / (float)dirtyList.size();
	1528
[1684]	1529	///////////////////////////
[1305]	1530	//-- reevaluate the dirty list
[1415]	1531
[1313]	1532	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
[1302]	1533
[2227]	1534	int i = 0;
	1535	for (sit = dirtyList.begin(); sit != sit_end; ++ sit, ++ i)
[1237]	1536	{
[1727]	1537	// only repair a certain number of candidates
	1538	if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
	1539	continue;
	1540
[1237]	1541	SubdivisionCandidate* sc = *sit;
[1305]	1542	const float rcd = sc->GetRenderCostDecrease();
[1302]	1543
[1667]	1544	// erase from queue
	1545	splitQueue.Erase(sc);
	1546	// reevaluate candidate
	1547	sc->EvalCandidate(recomputeSplitPlaneOnRepair);
	1548	// reinsert
	1549	splitQueue.Push(sc);
[1736]	1550
	1551	++ repaired;
[2227]	1552	//if (i % 10 == 0)
	1553	cout << ".";
[1667]	1554
[1715]	1555	#ifdef GTP_DEBUG
[1305]	1556	Debug << "candidate " << sc << " reevaluated\n"
	1557	<< "render cost decrease diff " << rcd - sc->GetRenderCostDecrease()
[1580]	1558	<< " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
	1559	#endif
[1237]	1560	}
[1313]	1561
[1625]	1562	const long endTime = GetTime();
	1563	const Real timeDiff = TimeDiff(startTime, endTime);
	1564
[1624]	1565	mHierarchyStats.mRepairTime += timeDiff;
[1313]	1566
[1736]	1567	return repaired;
[1237]	1568	}
	1569
[1259]	1570
[1640]	1571	void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
[1313]	1572	{
	1573	SubdivisionCandidateContainer mCandidateBuffer;
	1574
	1575	// remove from queue
[1640]	1576	while (!splitQueue.Empty())
[1313]	1577	{
[1640]	1578	SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
[1744]	1579
	1580	// reevaluate local split plane and priority
[1667]	1581	candidate->EvalCandidate(recomputeSplitPlane);
[1313]	1582	cout << ".";
	1583	mCandidateBuffer.push_back(candidate);
	1584	}
	1585
	1586	// put back into queue
	1587	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
	1588	for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
[1580]	1589	{
[1640]	1590	splitQueue.Push(*sit);
[1313]	1591	}
	1592	}
	1593
	1594
[1279]	1595	void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
	1596	{
	1597	// the type of the view cells hierarchy
[1308]	1598	switch (mObjectSpaceSubdivisionType)
[1279]	1599	{
	1600	case KD_BASED_OBJ_SUBDIV:
	1601	stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
	1602	mOspTree->Export(stream);
	1603	stream << endl << "</ObjectSpaceHierarchy>" << endl;
[1305]	1604	break;
[1279]	1605	case BV_BASED_OBJ_SUBDIV:
	1606	stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
	1607	mBvHierarchy->Export(stream);
	1608	stream << endl << "</ObjectSpaceHierarchy>" << endl;
	1609	break;
	1610	}
	1611	}
	1612
	1613
[1421]	1614	void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
[1279]	1615	{
[1313]	1616	stream << mHierarchyStats << endl;
	1617	stream << "\nview space:" << endl << endl;
	1618	stream << mVspTree->GetStatistics() << endl;
	1619	stream << "\nobject space:" << endl << endl;
[1370]	1620
[1308]	1621	switch (mObjectSpaceSubdivisionType)
[1279]	1622	{
	1623	case KD_BASED_OBJ_SUBDIV:
	1624	{
[1313]	1625	stream << mOspTree->GetStatistics() << endl;
[1279]	1626	break;
	1627	}
	1628	case BV_BASED_OBJ_SUBDIV:
	1629	{
[1313]	1630	stream << mBvHierarchy->GetStatistics() << endl;
[1279]	1631	break;
	1632	}
	1633	default:
	1634	break;
	1635	}
	1636	}
	1637
	1638
[1287]	1639	void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
[1416]	1640	const ObjectContainer &objects,
[1764]	1641	AxisAlignedBox3 *bbox,
[1920]	1642	const float maxRenderCost,
[1418]	1643	const bool exportBounds) const
[1279]	1644	{
[1308]	1645	switch (mObjectSpaceSubdivisionType)
[1286]	1646	{
	1647	case KD_BASED_OBJ_SUBDIV:
[1279]	1648	{
[1287]	1649	ExportOspTree(exporter, objects);
[1286]	1650	break;
	1651	}
	1652	case BV_BASED_OBJ_SUBDIV:
	1653	{
[1920]	1654	exporter->ExportBvHierarchy(*mBvHierarchy, maxRenderCost, bbox, exportBounds);
[1286]	1655	break;
	1656	}
	1657	default:
	1658	break;
	1659	}
	1660	}
[1279]	1661
[1286]	1662
[1287]	1663	void HierarchyManager::ExportOspTree(Exporter *exporter,
	1664	const ObjectContainer &objects) const
[1286]	1665	{
[1287]	1666	if (0) exporter->ExportGeometry(objects);
[1279]	1667
[1287]	1668	exporter->SetWireframe();
	1669	exporter->ExportOspTree(*mOspTree, 0);
[1286]	1670	}
	1671
	1672
[1743]	1673	Intersectable HierarchyManager::GetIntersectable(Intersectable obj,
	1674	const Vector3 &point) const
	1675	{
[1758]	1676
[2233]	1677	if (!obj) return NULL;
[1758]	1678
	1679	switch (mObjectSpaceSubdivisionType)
[1743]	1680	{
	1681	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
[1758]	1682	{
	1683	KdLeaf *leaf = mOspTree->GetLeaf(point, NULL);
	1684	return mOspTree->GetOrCreateKdIntersectable(leaf);
	1685	}
[1743]	1686	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
[1758]	1687	{
	1688	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
	1689	return leaf;
	1690	}
[1743]	1691	default:
[1758]	1692	return obj;
[1743]	1693	}
	1694	}
	1695
[2233]	1696
[1418]	1697	Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
	1698	const bool isTermination) const
	1699	{
[1758]	1700	Intersectable *obj = NULL;
[1418]	1701	Vector3 pt;
	1702	KdNode *node;
	1703
	1704	ray.GetSampleData(isTermination, pt, &obj, &node);
[1758]	1705
[2233]	1706	if (!obj) return NULL;
[1418]	1707
	1708	switch (mObjectSpaceSubdivisionType)
	1709	{
	1710	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
	1711	{
[1758]	1712	KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
[1418]	1713	return mOspTree->GetOrCreateKdIntersectable(leaf);
	1714	}
	1715	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
	1716	{
	1717	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
[1758]	1718	return leaf;
[1418]	1719	}
	1720	default:
[1758]	1721	break;
[1418]	1722	}
[1764]	1723
[1743]	1724	return obj;
[1418]	1725	}
	1726
	1727
[1313]	1728	void HierarchyStatistics::Print(ostream &app) const
	1729	{
	1730	app << "=========== Hierarchy statistics ===============\n";
	1731
	1732	app << setprecision(4);
	1733
	1734	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
	1735
[1624]	1736	app << "#N_RTIME ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
[1313]	1737
[1624]	1738	app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
[1313]	1739
	1740	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	1741
	1742	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	1743
[1624]	1744	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
[1449]	1745
	1746	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
[1313]	1747
	1748	app << "========== END OF Hierarchy statistics ==========\n";
	1749	}
	1750
	1751
[1418]	1752	static void RemoveRayRefs(const ObjectContainer &objects)
[1370]	1753	{
[1418]	1754	ObjectContainer::const_iterator oit, oit_end = objects.end();
	1755	for (oit = objects.begin(); oit != oit_end; ++ oit)
	1756	{
[1696]	1757	(*oit)->DelRayRefs();
[1418]	1758	}
	1759	}
	1760
	1761
[1679]	1762	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
	1763	const bool removeRayRefs) const
[1418]	1764	{
[1370]	1765	switch (mObjectSpaceSubdivisionType)
	1766	{
	1767	case KD_BASED_OBJ_SUBDIV:
	1768	{
	1769	mOspTree->mOspStats.Stop();
	1770	break;
	1771	}
	1772	case BV_BASED_OBJ_SUBDIV:
	1773	{
	1774	mBvHierarchy->mBvhStats.Stop();
[1649]	1775	if (removeRayRefs)
	1776	RemoveRayRefs(objects);
[1370]	1777	break;
	1778	}
	1779	default:
	1780	break;
	1781	}
	1782	}
	1783
[1614]	1784
	1785	void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
	1786	{
	1787	stream << "<BoundingBoxes>" << endl;
	1788
	1789	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	1790	{
	1791	KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
	1792
	1793	int id = 0;
	1794	for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
	1795	{
	1796	Intersectable obj = (kit).second;
	1797	const AxisAlignedBox3 box = obj->GetBox();
	1798
	1799	obj->SetId(id);
	1800
	1801	stream << "<BoundingBox" << " id=\"" << id << "\""
	1802	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	1803	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
	1804	}
	1805	}
[2093]	1806	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	1807	{
	1808	// export bounding boxes
	1809	vector<BvhNode *> nodes;
	1810
	1811	// hack: should also expect interior nodes
	1812	mBvHierarchy->CollectNodes(mBvHierarchy->GetRoot(), nodes);
	1813
	1814	vector<BvhNode *>::const_iterator oit, oit_end = nodes.end();
	1815
	1816	for (oit = nodes.begin(); oit != oit_end; ++ oit)
	1817	{
	1818	const AxisAlignedBox3 box = (*oit)->GetBox();
	1819	const int id = (*oit)->GetId();
	1820
	1821	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
	1822	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	1823	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
	1824	}
	1825	}
[1614]	1826	else
	1827	{
	1828	ObjectContainer::const_iterator oit, oit_end = objects.end();
	1829
	1830	for (oit = objects.begin(); oit != oit_end; ++ oit)
	1831	{
	1832	const AxisAlignedBox3 box = (*oit)->GetBox();
	1833
	1834	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
	1835	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	1836	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
	1837	}
	1838	}
	1839
	1840	stream << "</BoundingBoxes>" << endl;
	1841	}
	1842
[1680]	1843
[1706]	1844	class HierarchyNodeWrapper;
	1845
	1846
	1847	template <typename T> class myless
	1848	{
	1849	public:
	1850	bool operator() (T v1, T v2) const
	1851	{
	1852	return (v1->GetMergeCost() < v2->GetMergeCost());
	1853	}
	1854	};
	1855
[1709]	1856
[1706]	1857	typedef priority_queue<HierarchyNodeWrapper , vector<HierarchyNodeWrapper >,
	1858	myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
	1859
	1860	class HierarchyNodeWrapper
	1861	{
	1862	public:
[1707]	1863	enum {VSP_NODE, BVH_NODE, VIEW_CELL};
[1706]	1864
	1865	virtual float GetMergeCost() const = 0;
	1866	virtual int Type() const = 0;
	1867	virtual bool IsLeaf() const = 0;
	1868
	1869	virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
	1870	};
	1871
	1872
	1873	class VspNodeWrapper: public HierarchyNodeWrapper
	1874	{
	1875	public:
	1876	VspNodeWrapper(VspNode *node): mNode(node) {}
	1877
	1878	int Type() const { return VSP_NODE; }
	1879
	1880	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
	1881
	1882	bool IsLeaf() const { return mNode->IsLeaf(); }
	1883
	1884	void PushChildren(HierarchyNodeQueue &tQueue)
	1885	{
	1886	if (!mNode->IsLeaf())
	1887	{
[2017]	1888	VspInterior interior = static_cast<VspInterior >(mNode);
[1706]	1889
	1890	tQueue.push(new VspNodeWrapper(interior->GetFront()));
	1891	tQueue.push(new VspNodeWrapper(interior->GetBack()));
	1892	}
	1893	}
	1894
	1895	VspNode *mNode;
	1896	};
	1897
	1898
	1899	class BvhNodeWrapper: public HierarchyNodeWrapper
	1900	{
	1901	public:
	1902	BvhNodeWrapper(BvhNode *node): mNode(node) {}
[1686]	1903
[1706]	1904	int Type() const { return BVH_NODE; }
	1905
[1763]	1906	float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };
[1706]	1907
	1908	bool IsLeaf() const { return mNode->IsLeaf(); }
	1909
	1910	void PushChildren(HierarchyNodeQueue &tQueue)
	1911	{
	1912	if (!mNode->IsLeaf())
	1913	{
[2017]	1914	BvhInterior interior = static_cast<BvhInterior >(mNode);
[1706]	1915
	1916	tQueue.push(new BvhNodeWrapper(interior->GetFront()));
	1917	tQueue.push(new BvhNodeWrapper(interior->GetBack()));
	1918	}
	1919	}
	1920
	1921	BvhNode *mNode;
	1922	};
	1923
	1924
[1707]	1925	class ViewCellWrapper: public HierarchyNodeWrapper
	1926	{
	1927	public:
	1928
	1929	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
	1930
	1931	int Type() const { return VIEW_CELL; }
	1932
	1933	float GetMergeCost() const { return mViewCell->GetMergeCost(); };
	1934
	1935	bool IsLeaf() const { return mViewCell->IsLeaf(); }
	1936
	1937	void PushChildren(HierarchyNodeQueue &tQueue)
	1938	{
	1939	if (!mViewCell->IsLeaf())
	1940	{
[2017]	1941	ViewCellInterior interior = static_cast<ViewCellInterior >(mViewCell);
[1707]	1942
	1943	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
	1944
	1945	for (it = interior->mChildren.begin(); it != it_end; ++ it)
	1946	{
	1947	tQueue.push(new ViewCellWrapper(*it));
	1948	}
	1949	}
	1950	}
	1951
	1952	ViewCell *mViewCell;
	1953	};
	1954
	1955
[1706]	1956	void HierarchyManager::CollectBestSet(const int maxSplits,
	1957	const float maxMemoryCost,
[1707]	1958	ViewCellContainer &viewCells,
[1706]	1959	vector<BvhNode *> &bvhNodes)
	1960	{
	1961	HierarchyNodeQueue tqueue;
[1707]	1962	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
	1963	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
[1706]	1964	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
	1965
	1966	float memCost = 0;
	1967
	1968	while (!tqueue.empty())
	1969	{
	1970	HierarchyNodeWrapper *nodeWrapper = tqueue.top();
	1971	tqueue.pop();
[1713]	1972	//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
[1706]	1973	// save the view cells if it is a leaf or if enough view cells have already been traversed
[2187]	1974	// because of the priority queue, this will be the optimal set of view cells
[1706]	1975	if (nodeWrapper->IsLeaf() \|\|
[1707]	1976	((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) \|\|
[1706]	1977	(memCost > maxMemoryCost)
	1978	)
	1979	{
[1713]	1980	if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
[1706]	1981	{
[1713]	1982	//cout << "1";
[2017]	1983	ViewCellWrapper viewCellWrapper = static_cast<ViewCellWrapper >(nodeWrapper);
[1707]	1984	viewCells.push_back(viewCellWrapper->mViewCell);
[1706]	1985	}
	1986	else
	1987	{
[1713]	1988	//cout << "0";
[2017]	1989	BvhNodeWrapper bvhNodeWrapper = static_cast<BvhNodeWrapper >(nodeWrapper);
[1706]	1990	bvhNodes.push_back(bvhNodeWrapper->mNode);
	1991	}
	1992	}
	1993	else
	1994	{
	1995	nodeWrapper->PushChildren(tqueue);
	1996	}
	1997
	1998	delete nodeWrapper;
	1999	}
	2000	}
	2001
	2002
[1842]	2003	void HierarchyManager::ComputePvs(const ObjectPvs &pvs,
[2332]	2004	float &triangles,
[1842]	2005	int &pvsEntries)
[1745]	2006	{
	2007	BvhNode::NewMail();
	2008
	2009	ObjectPvsIterator pit = pvs.GetIterator();
	2010
	2011	while (pit.HasMoreEntries())
	2012	{
[2117]	2013	Intersectable *obj = pit.Next();
[1745]	2014
[2117]	2015	if (obj->Type() != Intersectable::BVH_INTERSECTABLE)
[2187]	2016	{
	2017	cout << "error: wrong object type detected: " << obj->Type() << endl;
	2018	exit(0);
	2019	}
[1842]	2020
[2117]	2021	BvhNode intersect = static_cast<BvhNode >(obj);
[1758]	2022	BvhNode *activeNode;
[1745]	2023
[1758]	2024	// hack for choosing which node to account for
	2025	if (intersect->IsLeaf())
[1786]	2026	{
[1842]	2027	activeNode =
[2017]	2028	static_cast<BvhLeaf *>(intersect)->GetActiveNode();
[1786]	2029	}
[1758]	2030	else
[1786]	2031	{
[1758]	2032	activeNode = intersect;
[1786]	2033	}
[1745]	2034
	2035	if (!activeNode->Mailed())
	2036	{
	2037	activeNode->Mail();
	2038
[1786]	2039	#if STUPID_METHOD
	2040
[1745]	2041	ObjectContainer objects;
[1786]	2042	activeNode->CollectObjects(objects);
[2332]	2043	triangles += (float)objects.size();
[1786]	2044	#else
[2332]	2045	triangles += mBvHierarchy->GetTriangleSizeIncrementially(activeNode);
[1786]	2046	#endif
[1745]	2047	++ pvsEntries;
	2048	}
	2049	}
	2050	}
	2051
	2052
[1787]	2053	void HierarchyManager::GetPvsEfficiently(ViewCell *viewCell, ObjectPvs &pvs) const
	2054	{
	2055	////////////////
	2056	//-- pvs is not stored with the interiors => reconstruct
	2057
	2058	// add pvs from leaves
	2059	stack<ViewCell *> tstack;
	2060	tstack.push(viewCell);
	2061
	2062	Intersectable::NewMail();
	2063
	2064	while (!tstack.empty())
	2065	{
	2066	ViewCell *vc = tstack.top();
	2067	tstack.pop();
	2068
	2069	// add newly found pvs to merged pvs: break here even for interior
	2070	if (!vc->GetPvs().Empty())
	2071	{
	2072	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
	2073
	2074	while (pit.HasMoreEntries())
	2075	{
[2117]	2076	Intersectable *object = pit.Next();
[1787]	2077
	2078	if (!object->Mailed())
	2079	{
	2080	object->Mail();
	2081	pvs.AddSampleDirty(object, 1.0f);
	2082	}
	2083	}
	2084	}
	2085	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
	2086	{
[2017]	2087	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
[1787]	2088	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
	2089
	2090	for (it = interior->mChildren.begin(); it != it_end; ++ it)
	2091	{
	2092	tstack.push(*it);
	2093	}
	2094	}
	2095	}
	2096	}
	2097
	2098
[1750]	2099	// TODO matt: implement this function for different storing methods
[1787]	2100	void HierarchyManager::GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const
[1750]	2101	{
	2102	////////////////
	2103	//-- pvs is not stored with the interiors => reconstruct
	2104
	2105	// add pvs from leaves
	2106	stack<ViewCell *> tstack;
	2107	tstack.push(vc);
	2108
	2109	while (!tstack.empty())
	2110	{
	2111	vc = tstack.top();
	2112	tstack.pop();
	2113
	2114	// add newly found pvs to merged pvs: break here even for interior
	2115	if (!vc->GetPvs().Empty())
	2116	{
	2117	pvs.MergeInPlace(vc->GetPvs());
	2118	}
	2119	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
	2120	{
[2017]	2121	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
[1750]	2122	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
	2123
	2124	for (it = interior->mChildren.begin(); it != it_end; ++ it)
	2125	{
	2126	tstack.push(*it);
	2127	}
	2128	}
	2129	}
	2130	}
	2131
[1786]	2132
	2133	// TODO matt: implement this function for different storing methods
	2134	void HierarchyManager::PullUpPvsIncrementally(ViewCell *viewCell) const
	2135	{
	2136	////////////////
	2137	//-- pvs is not stored with the interiors => reconstruct
	2138
	2139	// early exit: pvs is already pulled up to this view cell
	2140	if (!viewCell->GetPvs().Empty())
	2141	return;
	2142
	2143	// add pvs from leaves
	2144	stack<ViewCell *> tstack;
	2145	tstack.push(viewCell);
	2146
	2147	ViewCell *vc = viewCell;
	2148
	2149	while (!tstack.empty())
	2150	{
	2151	vc = tstack.top();
	2152	tstack.pop();
	2153
	2154	// add newly found pvs to merged pvs: break here even for interior
	2155	if (!vc->GetPvs().Empty())
	2156	{
[1787]	2157	viewCell->GetPvs().MergeInPlace(vc->GetPvs());
[1786]	2158	}
	2159	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
	2160	{
	2161	//cout <<" t";
[2017]	2162	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
[1786]	2163	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
	2164
	2165	for (it = interior->mChildren.begin(); it != it_end; ++ it)
	2166	{
	2167	tstack.push(*it);
	2168	}
	2169	}
	2170	}
	2171	}
	2172
	2173
	2174
	2175	// TODO matt: implement this function for different storing methods
	2176	void HierarchyManager::GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const
	2177	{
	2178	////////////////
	2179	//-- pvs is not stored with the interiors => reconstruct
	2180	if (vc->IsLeaf() \|\| !vc->GetPvs().Empty())
	2181	{
	2182	pvs = vc->GetPvs();
	2183	}
	2184	else
	2185	{
[2017]	2186	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
[1786]	2187	#if 0
	2188	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
	2189	const int childPvsSize = (int)interior->mChildren.size();
	2190	vector<ObjectPvs> childPvs;
	2191	childPvs.resize((int)interior->mChildren.size());
	2192
	2193	int i = 0;
	2194	for (it = interior->mChildren.begin(); it != it_end; ++ it, ++ i)
	2195	{
	2196	GetPvsRecursive(*it, childPvs[i]);
	2197	pvs.MergeInPlace(childPvs[i]);
	2198	}
	2199	#else
	2200
	2201	ObjectPvs leftPvs, rightPvs;
	2202
	2203	GetPvsRecursive(interior->mChildren[0], leftPvs);
	2204	GetPvsRecursive(interior->mChildren[1], rightPvs);
	2205
	2206	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
	2207	#endif
	2208	}
	2209	}
	2210
	2211
[1713]	2212	int HierarchyManager::ExtractStatistics(const int maxSplits,
	2213	const float maxMemoryCost,
	2214	float &renderCost,
	2215	float &memory,
[1718]	2216	int &pvsEntries,
	2217	int &viewSpaceSplits,
[1745]	2218	int &objectSpaceSplits,
[1919]	2219	const bool useFilter,
	2220	const bool useHisto,
	2221	const int histoMem,
	2222	const int pass,
	2223	bool &histoUsed)
[1706]	2224	{
[1707]	2225	ViewCellContainer viewCells;
	2226	vector<BvhNode *> bvhNodes;
	2227
[1709]	2228	// collect best set of view cells for this #splits
[1707]	2229	CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
	2230	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
	2231
[1713]	2232	// set new nodes to be active
[1707]	2233	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
	2234	{
	2235	mBvHierarchy->SetActive(*bit);
	2236	}
	2237
	2238	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	2239
[1713]	2240	pvsEntries = 0;
	2241	renderCost = 0.0f;
[1707]	2242
[1750]	2243	ViewCell::NewMail();
	2244
[1787]	2245	//cout << "\nviewcells: " << viewCells.size() << endl;
[1707]	2246	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	2247	{
	2248	ViewCell vc = vit;
[2332]	2249
[1786]	2250	#if STUPID_METHOD
	2251	ObjectPvs pvs;
[1787]	2252	GetPvsIncrementially(vc, pvs);
[1750]	2253	vc->SetPvs(pvs);
[1787]	2254
[1786]	2255	#else
[1787]	2256
[1786]	2257	ObjectPvs pvs;
[1789]	2258
[1787]	2259	if (vc->GetPvs().Empty())
	2260	{
[1789]	2261	// warning: uses mailing, pvs not sorted!!
[1787]	2262	GetPvsEfficiently(vc, pvs);
[1789]	2263	//GetPvsRecursive(vc, pvs);
[1787]	2264	vc->SetPvs(pvs);
	2265	}
[1786]	2266	#endif
[1750]	2267
	2268	vc->Mail();
	2269
[2332]	2270	float triangles = 0;
	2271	int entries = 0;
	2272
[1745]	2273	if (useFilter)
[1707]	2274	{
[1786]	2275	const long startT = GetTime();
[2332]	2276
[1745]	2277	ObjectPvs filteredPvs;
[2332]	2278	GetViewCellsManager()->ApplyFilter2(vc, false, 1.0f, filteredPvs);
	2279
[1786]	2280	const long endT = GetTime();
	2281
[1787]	2282	//cout << "filter computed in " << TimeDiff(startT, endT) * 1e-3f << " secs" << endl;
[2332]	2283
	2284	ComputePvs(filteredPvs, triangles, entries);
[1707]	2285	}
[1745]	2286	else
	2287	{
[2332]	2288	ComputePvs(vc->GetPvs(), triangles, entries);
[2342]	2289	vc->SetTrianglesInPvs(triangles);
[1749]	2290	}
[1713]	2291
[2332]	2292	const float rc = GetViewCellsManager()->ComputeRenderCost((int)triangles, entries) * vc->GetVolume();
	2293
[1713]	2294	renderCost += rc;
[2332]	2295	pvsEntries += entries;
[1707]	2296	}
	2297
[2332]	2298	renderCost /= GetViewCellsManager()->GetViewSpaceBox().GetVolume();
[1713]	2299	memory = pvsEntries * ObjectPvs::GetEntrySize();
[1718]	2300
	2301	viewSpaceSplits = (int)viewCells.size();
	2302	objectSpaceSplits = (int)bvhNodes.size();
[1919]	2303
	2304	////////////////////////
	2305	//-- evaluate histogram for pvs size
	2306
	2307	if (useHisto && (memory <= (float)histoMem))
	2308	{
	2309	char str[100];
	2310	char statsPrefix[100];
[1933]	2311	//int histoStepSize;
[1919]	2312
	2313	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
	2314
	2315	cout << "computing pvs histogram for " << histoMem << " memory" << endl;
	2316	Debug << "computing pvs histogram for " << histoMem << " memory" << endl;
	2317
	2318	sprintf(str, "-%05d-%05d-histo-pvs.log", pass, histoMem);
	2319	const string filename = string(statsPrefix) + string(str);
	2320
[2332]	2321	GetViewCellsManager()->EvalViewCellHistogramForPvsSize(filename, viewCells);
[1919]	2322
	2323	histoUsed = true;
	2324	}
	2325
[1713]	2326	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
	2327
[1750]	2328	// delete old "base" view cells if they are not leaves
	2329	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
	2330
	2331	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
	2332	{
	2333	if (!(oit)->Mailed() && !(oit)->IsLeaf())
	2334	{
	2335	(*oit)->GetPvs().Clear();
	2336	}
	2337	}
	2338
[1786]	2339	// store current level
[1750]	2340	mOldViewCells = viewCells;
	2341
[1764]	2342	return (int)(viewCells.size() + bvhNodes.size());
[1709]	2343	}
[1706]	2344
	2345
	2346
[2332]	2347	void HierarchyManager::EvaluateSubdivision(ofstream &splitsStats,
	2348	const int splitsStepSize,
	2349	const bool useFilter,
	2350	const bool useHisto,
	2351	const int histoMem,
	2352	const int pass)
[1709]	2353	{
[1750]	2354	vector<HierarchySubdivisionStats> subStatsContainer;
[1709]	2355
[1786]	2356	int splits = (1 + (mHierarchyStats.Leaves() - 1) / splitsStepSize) * splitsStepSize;
[1750]	2357	cout << "splits: " << splits << endl;
	2358
[1919]	2359	bool histoUsed = false;
	2360
[1709]	2361	while (1)
	2362	{
[1750]	2363	HierarchySubdivisionStats subStats;
[1723]	2364	subStats.mNumSplits = ExtractStatistics(splits,
[1718]	2365	99999.0,
[1723]	2366	subStats.mTotalRenderCost,
	2367	subStats.mMemoryCost,
	2368	subStats.mEntriesInPvs,
	2369	subStats.mViewSpaceSplits,
[1745]	2370	subStats.mObjectSpaceSplits,
[1919]	2371	useFilter,
	2372	useHisto && !histoUsed,
	2373	histoMem,
	2374	pass,
	2375	histoUsed);
[1723]	2376
[1713]	2377
[1723]	2378	const float objectSpaceHierarchyMem = float(
[1760]	2379	subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
[1732]	2380	//+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
	2381	//+sizeof(BvHierarchy)
[1723]	2382	) / float(1024 * 1024);
[1718]	2383
[1723]	2384
	2385	const float viewSpaceHierarchyMem = float(
[1760]	2386	subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
[1732]	2387	//+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
	2388	+ sizeof(ObjectPvs)
	2389	//+ sizeof(VspTree)
[1723]	2390	) / float(1024 * 1024);
	2391
	2392	subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
	2393
[1750]	2394	subStatsContainer.push_back(subStats);
	2395
	2396	if (splits == 0)
[1786]	2397	{
[1709]	2398	break;
[1786]	2399	}
[1750]	2400	splits -= splitsStepSize;
	2401
[1786]	2402	cout << "splits: " << subStats.mNumSplits << " ";
[1709]	2403	}
[1745]	2404
[1750]	2405	vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();
	2406
	2407	for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
	2408	{
	2409	(*hit).Print(splitsStats);
	2410	}
	2411
	2412	// delete old "base" view cells: only pvss in the leaves are allowed
	2413	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
[2210]	2414
[1750]	2415	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
	2416	{
	2417	if (!(*oit)->IsLeaf())
	2418	{
	2419	(*oit)->GetPvs().Clear();
	2420	}
	2421	}
	2422
	2423	mOldViewCells.clear();
	2424
[1763]	2425	// reset active nodes
	2426	vector<BvhLeaf *> bvhLeaves;
	2427
	2428	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);
	2429
	2430	vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();
	2431
	2432	for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
	2433	{
	2434	(bit)->SetActiveNode(bit);
	2435	}
	2436
[1732]	2437	cout << endl;
[1706]	2438	}
[1709]	2439
[1718]	2440
	2441	void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
	2442	{
[1719]	2443	mBvHierarchy->CollectObjects(box, objects);
[1715]	2444	}
[1718]	2445
[1843]	2446
[1845]	2447	int HierarchyManager::CompressObjectSpace()
[1844]	2448	{
	2449	//mBvHierarchy->Compress();
[1845]	2450	return mVspTree->CompressObjects();
	2451	}
[1844]	2452
[1845]	2453
[1843]	2454	void HierarchyManager::CreateUniqueObjectIds()
	2455	{
	2456	mBvHierarchy->CreateUniqueObjectIds();
[1718]	2457	}
[1843]	2458
	2459
[2073]	2460	void HierarchyManager::CreateTraversalTree()
	2461	{
[2170]	2462	int mind, maxd;
	2463	mVspTree->EvalMinMaxDepth(mind, maxd);
	2464
	2465	cout << "old tree balance: " << mind << " " << maxd << endl;
[2094]	2466	mTraversalTree = new TraversalTree;
	2467
	2468	ViewCellContainer viewCells;
[2124]	2469	mVspTree->CollectViewCells(viewCells, false);
[2094]	2470
[2124]	2471	const long startTime = GetTime();
[2094]	2472
	2473	cout << "building traversal tree ... " << endl;
	2474
[2124]	2475	mTraversalTree->Construct(viewCells);
[2094]	2476
[2124]	2477	cout << "finished traversal tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3
[2094]	2478	<< " secs " << endl;
[2124]	2479
	2480	Debug << "* TraversalTree Stats *" << endl;
	2481	Debug << mTraversalTree->GetStatistics() << endl;
	2482
	2483	if (1)
	2484	{
	2485	Exporter *exporter = Exporter::GetExporter("traversal.wrl");
	2486	exporter->ExportTraversalTree(*mTraversalTree, true);
	2487	delete exporter;
	2488	}
[1843]	2489	}
[2073]	2490
	2491
[2094]	2492	int HierarchyManager::CastLineSegment(const Vector3 &origin,
	2493	const Vector3 &termination,
	2494	ViewCellContainer &viewcells,
	2495	const bool useMailboxing)
	2496	{
	2497	if (!mTraversalTree)
[2124]	2498	{
[2332]	2499	return mVspTree->CastLineSegment(origin, termination, viewcells, useMailboxing);
[2124]	2500	}
[2094]	2501	else
[2124]	2502	{
[2332]	2503	return mTraversalTree->CastLineSegment(origin, termination, viewcells, useMailboxing);
[2124]	2504	}
[2073]	2505	}
[2094]	2506
	2507
[2332]	2508	ViewCellsManager *HierarchyManager::GetViewCellsManager()
	2509	{
	2510	return mVspTree->mViewCellsManager;
[2094]	2511	}
[2332]	2512
[2353]	2513
[2342]	2514	int HierarchyManager::CastLineSegment(RayPacket &packet)
	2515	{
	2516	return mVspTree->TraverseRayPacket(packet, true);
	2517	}
[2332]	2518
[2342]	2519
[2332]	2520	}

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

Download in other formats: