Context Navigation

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

Revision 2237, 72.3 KB checked in by mattausch, 18 years ago (diff)
worked on optimization. warning: not tested yet

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

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

Download in other formats: