Context Navigation

HierarchyManager.cpp @ 2705

Revision 2705, 66.2 KB checked in by mattausch, 17 years ago (diff)
enabled view cell visualization

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

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

Context Navigation

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

Download in other formats: