Context Navigation

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

Revision 2543, 68.6 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: