Context Navigation

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

Revision 2199, 71.3 KB checked in by mattausch, 18 years ago (diff)
using mutationsamples for evaluation

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

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

Download in other formats: