Context Navigation

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

Revision 2575, 68.7 KB checked in by bittner, 17 years ago (diff)
big merge: preparation for havran ray caster, check if everything works

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

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

Download in other formats: