Context Navigation

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

Revision 1727, 58.6 KB checked in by mattausch, 18 years ago (diff)
implemented several accelleration svhemes for the gradient method

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"
[1237]	24
	25
	26	namespace GtpVisibilityPreprocessor {
	27
	28
	29	#define USE_FIXEDPOINT_T 0
	30
	31
	32	/*******************************************************************/
	33	/* class HierarchyManager implementation */
	34	/*******************************************************************/
	35
	36
[1421]	37	HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
[1308]	38	mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
[1279]	39	mOspTree(NULL),
	40	mBvHierarchy(NULL)
[1237]	41	{
[1308]	42	switch(mObjectSpaceSubdivisionType)
[1279]	43	{
	44	case KD_BASED_OBJ_SUBDIV:
	45	mOspTree = new OspTree();
	46	mOspTree->mVspTree = mVspTree;
[1379]	47	mOspTree->mHierarchyManager = this;
[1279]	48	break;
	49	case BV_BASED_OBJ_SUBDIV:
	50	mBvHierarchy = new BvHierarchy();
[1379]	51	mBvHierarchy->mHierarchyManager = this;
[1279]	52	break;
	53	default:
	54	break;
	55	}
	56
[1379]	57	// hierarchy manager links view space partition and object space partition
[1421]	58	mVspTree = new VspTree();
[1379]	59	mVspTree->mHierarchyManager = this;
	60
[1580]	61	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
[1288]	62	ParseEnvironment();
[1237]	63	}
	64
	65
[1421]	66	HierarchyManager::HierarchyManager(KdTree *kdTree):
[1308]	67	mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
[1279]	68	mBvHierarchy(NULL)
	69	{
	70	mOspTree = new OspTree(*kdTree);
	71	mOspTree->mVspTree = mVspTree;
	72
[1421]	73	mVspTree = new VspTree();
[1379]	74	mVspTree->mHierarchyManager = this;
[1279]	75
[1580]	76	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
[1288]	77	ParseEnvironment();
	78	}
	79
	80
[1723]	81	void HierarchySubdivisionStats::Print(ostream &app) const
	82	{
	83	app << "#Pass\n" << 0 << endl
	84	<< "#Splits\n" << mNumSplits << endl
	85	<< "#TotalRenderCost\n" << mTotalRenderCost << endl
	86	<< "#TotalEntriesInPvs\n" << mEntriesInPvs << endl
	87	<< "#Memory\n" << mMemoryCost << endl
	88	<< "#StepsView\n" << mViewSpaceSplits << endl
	89	<< "#StepsObject\n" << mObjectSpaceSplits << endl
	90	<< "#VspOspRatio\n" << VspOspRatio() << endl
	91	<< "#FullMem\n" << mFullMemory << endl
	92	<< "#RenderCostDecrease\n" << mRenderCostDecrease << endl
	93	<< "#FpsPerMb\n" << FpsPerMb() << endl
	94	<< endl;
	95	}
	96
	97
[1288]	98	void HierarchyManager::ParseEnvironment()
	99	{
	100	Environment::GetSingleton()->GetFloatValue(
	101	"Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
	102	Environment::GetSingleton()->GetIntValue(
	103	"Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
	104
[1370]	105	Environment::GetSingleton()->GetBoolValue(
	106	"Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
	107
[1293]	108	Environment::GetSingleton()->GetIntValue(
[1294]	109	"Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
	110
	111	Environment::GetSingleton()->GetIntValue(
[1293]	112	"Hierarchy.Construction.type", mConstructionType);
	113
[1311]	114	Environment::GetSingleton()->GetIntValue(
	115	"Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
[1370]	116
	117	Environment::GetSingleton()->GetIntValue(
	118	"Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
[1311]	119
[1314]	120	Environment::GetSingleton()->GetBoolValue(
	121	"Hierarchy.Construction.repairQueue", mRepairQueue);
	122
[1449]	123	Environment::GetSingleton()->GetBoolValue(
[1564]	124	"Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
[1449]	125
[1580]	126	Environment::GetSingleton()->GetIntValue(
	127	"Hierarchy.Construction.levels", mNumMultiLevels);
	128
[1640]	129	Environment::GetSingleton()->GetIntValue(
	130	"Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
	131
[1684]	132	Environment::GetSingleton()->GetIntValue(
	133	"Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);
	134
[1624]	135	char subdivisionStatsLog[100];
	136	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
	137	mSubdivisionStats.open(subdivisionStatsLog);
	138
[1633]	139	Environment::GetSingleton()->GetBoolValue(
	140	"Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
[1624]	141
[1662]	142	Environment::GetSingleton()->GetBoolValue(
	143	"Hierarchy.Construction.considerMemory", mConsiderMemory);
	144
[1673]	145	Environment::GetSingleton()->GetBoolValue(
	146	"Hierarchy.Construction.considerMemory2", mConsiderMemory2);
	147
[1649]	148	Environment::GetSingleton()->GetFloatValue(
	149	"Hierarchy.Termination.maxMemory", mTermMaxMemory);
	150
[1727]	151	Environment::GetSingleton()->GetIntValue(
	152	"Hierarchy.Construction.maxRepairs", mMaxRepairs);
	153
[1684]	154	if (1 && mConsiderMemory2)
	155	{
	156	mMemoryConst = (float)(sizeof(VspLeaf ) + sizeof (VspViewCell ));
	157	}
	158	else
	159	{
	160	Environment::GetSingleton()->GetFloatValue(
	161	"Hierarchy.Termination.memoryConst", mMemoryConst);
	162	}
[1666]	163
[1662]	164	// compare to bytes
[1653]	165	mTermMaxMemory = (1024.0f 1024.0f);
	166
[1705]	167	Debug << "****** Hierarchy Manager Options *********" << endl;
[1294]	168	Debug << "max leaves: " << mTermMaxLeaves << endl;
[1288]	169	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
	170	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
[1314]	171	Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
	172	Debug << "repair queue: " << mRepairQueue << endl;
[1580]	173	Debug << "number of multilevels: " << mNumMultiLevels << endl;
[1633]	174	Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
[1640]	175	Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
[1649]	176	Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
[1673]	177	Debug << "consider memory: " << mConsiderMemory << endl;
	178	Debug << "consider memory2: " << mConsiderMemory << endl;
[1666]	179	Debug << "mem const: " << mMemoryConst << endl;
[1684]	180	Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
	181	Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
[1727]	182	Debug << "max repairs: " << mMaxRepairs << endl;
[1632]	183
	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
	281	return splitCandidate;
	282	}
	283
	284
[1624]	285	void HierarchyManager::EvalSubdivisionStats()
[1237]	286	{
[1649]	287	// question: should I also add the mem usage of the hierarchies?
[1723]	288	const float objectSpaceMem = GetObjectSpaceMemUsage();
	289	const float viewSpaceMem = mVspTree->GetMemUsage();
	290
	291	HierarchySubdivisionStats stats;
	292	stats.mNumSplits = mHierarchyStats.Leaves();
	293	stats.mTotalRenderCost = mHierarchyStats.mTotalCost;
	294	stats.mEntriesInPvs = mHierarchyStats.mPvsEntries;
	295	stats.mMemoryCost = mHierarchyStats.mMemory / float(1024 * 1024);
	296	stats.mFullMemory = mHierarchyStats.mMemory / float(1024 * 1024)
	297	+ objectSpaceMem + viewSpaceMem;
	298	stats.mViewSpaceSplits = mVspTree->mVspStats.Leaves();
	299	stats.mObjectSpaceSplits = GetObjectSpaceSubdivisionLeaves();
[1640]	300
[1723]	301	stats.Print(mSubdivisionStats);
[1237]	302	}
	303
	304
	305	void HierarchyManager::AddSubdivisionStats(const int splits,
	306	const float renderCostDecr,
[1576]	307	const float totalRenderCost,
[1625]	308	const int pvsEntries,
[1640]	309	const float memory,
[1654]	310	const float renderCostPerStorage,
	311	const float vspOspRatio)
[1237]	312	{
[1308]	313	mSubdivisionStats
[1237]	314	<< "#Splits\n" << splits << endl
	315	<< "#RenderCostDecrease\n" << renderCostDecr << endl
[1577]	316	<< "#TotalEntriesInPvs\n" << pvsEntries << endl
[1625]	317	<< "#TotalRenderCost\n" << totalRenderCost << endl
	318	<< "#Memory\n" << memory << endl
[1660]	319	<< "#FpsPerMb\n" << renderCostPerStorage << endl
[1723]	320	<< "#VspOspRatio\n" << vspOspRatio << endl
	321	<< endl;
[1237]	322	}
	323
	324
	325	bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
	326	{
[1421]	327	const bool terminationCriteriaMet =
	328	(0
[1294]	329	\|\| (mHierarchyStats.Leaves() >= mTermMaxLeaves)
[1649]	330	\|\| (mHierarchyStats.mMemory >= mTermMaxMemory)
	331	\|\| candidate->GlobalTerminationCriteriaMet()
	332	//\|\| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
[1633]	333	//\|\| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
[1288]	334	);
[1421]	335
[1715]	336	#if GTP_DEBUG
[1610]	337	if (terminationCriteriaMet)
[1421]	338	{
	339	Debug << "hierarchy global termination criteria met:" << endl;
	340	Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
[1449]	341	Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
[1649]	342	Debug << "memory: " << mHierarchyStats.mMemory << " " << mTermMaxMemory << endl;
[1421]	343	}
[1653]	344	#endif
[1610]	345
[1421]	346	return terminationCriteriaMet;
[1237]	347	}
	348
	349
	350	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
[1311]	351	const ObjectContainer &objects,
	352	AxisAlignedBox3 *forcedViewSpace)
[1237]	353	{
[1679]	354	mTimeStamp = 1;
	355
[1627]	356	switch (mConstructionType)
[1449]	357	{
[1627]	358	case MULTILEVEL:
[1449]	359	ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
[1627]	360	break;
	361	case INTERLEAVED:
	362	case SEQUENTIAL:
[1624]	363	ConstructInterleaved(sampleRays, objects, forcedViewSpace);
[1627]	364	break;
	365	case GRADIENT:
	366	ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
	367	break;
	368	default:
	369	break;
[1624]	370	}
[1642]	371
	372	// hack: should be different parameter name
	373	if (mUseMultiLevelConstruction)
	374	{
	375	cout << "starting optimizing multilevel ... " << endl;
	376	// try to optimize on the above hierarchy
	377	OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
	378
	379	cout << "finished" << endl;
	380	}
[1624]	381	}
	382
	383
[1686]	384	void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
[1626]	385	const ObjectContainer &objects,
	386	AxisAlignedBox3 *forcedViewSpace)
[1624]	387	{
	388	mHierarchyStats.Reset();
	389	mHierarchyStats.Start();
[1625]	390
[1624]	391	mHierarchyStats.mNodes = 2;
[1640]	392
	393	// create first nodes
	394	mVspTree->Initialise(sampleRays, forcedViewSpace);
	395	InitialiseObjectSpaceSubdivision(objects);
	396
	397	// hack: assume that object space can be seen from view space
[1677]	398	mHierarchyStats.mTotalCost = mInitialRenderCost = (float)objects.size();
[1667]	399	// only one entry for start
[1640]	400	mHierarchyStats.mPvsEntries = 1;
[1667]	401	mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
[1640]	402
	403	EvalSubdivisionStats();
[1624]	404	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
	405
	406	const long startTime = GetTime();
	407	cout << "Constructing view space / object space tree ... \n";
	408
[1633]	409	SplitQueue objectSpaceQueue;
	410	SplitQueue viewSpaceQueue;
	411
[1696]	412	int vspSteps = 0, ospSteps = 0;
[1684]	413
[1624]	414	// use sah for evaluating osp tree construction
	415	// in the first iteration of the subdivision
	416	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	417	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
[1662]	418	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
[1624]	419
[1632]	420	// number of initial splits
[1640]	421	const int minSteps = mMinStepsOfSameType;
[1684]	422	const int maxSteps = mMaxStepsOfSameType;
[1625]	423
[1727]	424	SubdivisionCandidate *osc =
	425	PrepareObjectSpaceSubdivision(sampleRays, objects);
[1633]	426	objectSpaceQueue.Push(osc);
	427
	428	/////////////////////////
	429	// calulcate initial object space splits
	430
[1684]	431	SubdivisionCandidateContainer dirtyList;
[1633]	432
	433	// subdivide object space first
	434	// for first round, use sah splits. Once view space partition
	435	// has started, use render cost heuristics instead
[1727]	436	ospSteps = RunConstruction(objectSpaceQueue,
	437	dirtyList,
	438	NULL,
	439	minSteps,
	440	maxSteps);
	441
[1640]	442	cout << "\n" << ospSteps << " object space partition steps taken" << endl;
[1633]	443
[1640]	444	// create view space
[1667]	445	SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
[1684]	446	viewSpaceQueue.Push(vsc);
[1633]	447
[1684]	448	dirtyList.clear();
	449
[1642]	450	// view space subdivision started
[1633]	451	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	452
[1684]	453	if (1)
	454	{
	455	// rather also start with 100 view space splits to avoid initial bias.
	456	vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
	457	cout << "\n" << vspSteps << " view space partition steps taken" << endl;
	458
	459	/// Repair split queue
	460	cout << "repairing queue ... " << endl;
	461	RepairQueue(dirtyList, objectSpaceQueue, true);
	462	cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
[1633]	463
[1684]	464	dirtyList.clear();
	465	}
	466	else
	467	{
	468	// the priorities were calculated for driving sah.
	469	// => recalculate "real" priorities taking visibility into
	470	// account so we can compare to view space splits
	471	ResetQueue(objectSpaceQueue, false);
	472	}
	473
[1624]	474	// This method subdivides view space / object space
	475	// in order to converge to some optimal cost for this partition
	476	// start with object space partiton
	477	// then optimizate view space partition for the current osp
	478	// and vice versa until iteration depth is reached.
[1696]	479
[1684]	480	bool lastSplitWasOsp = true;
	481
[1633]	482	while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
[1624]	483	{
[1662]	484	// decide upon next split type
[1727]	485	if (viewSpaceQueue.Top()->IsDirty())
	486	viewSpaceQueue.Top()->EvalCandidate();
	487
	488	if (objectSpaceQueue.Top()->IsDirty())
	489	objectSpaceQueue.Top()->EvalCandidate();
	490
[1701]	491	const float vspPriority = viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
	492	const float ospPriority = objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
[1662]	493
[1640]	494	cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
	495
[1633]	496	// should view or object space be subdivided further?
[1684]	497	if (ospPriority >= vspPriority)
	498	//if (!lastSplitWasOsp)
[1633]	499	{
[1679]	500	lastSplitWasOsp = true;
[1673]	501	cout << "osp" << endl;
[1684]	502
[1633]	503	// dirtied view space candidates
	504	SubdivisionCandidateContainer dirtyVspList;
[1624]	505
[1727]	506	// subdivide object space first for first round,
	507	// use sah splits. Once view space partition
[1633]	508	// has started, use render cost heuristics instead
[1727]	509	const int ospSteps = RunConstruction(objectSpaceQueue,
	510	dirtyVspList,
	511	viewSpaceQueue.Top(),
	512	minSteps,
	513	maxSteps);
[1624]	514
[1640]	515	cout << "\n" << ospSteps << " object space partition steps taken" << endl;
[1684]	516	Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
	517
[1640]	518	/// Repair split queue, i.e., affected view space candidates
[1633]	519	cout << "repairing queue ... " << endl;
	520	RepairQueue(dirtyVspList, viewSpaceQueue, true);
[1727]	521
[1640]	522	cout << "\nrepaired " << (int)dirtyVspList.size() << " candidates" << endl;
[1633]	523	}
	524	else
	525	{
[1679]	526	lastSplitWasOsp = false;
[1673]	527	cout << "vsp" << endl;
	528
[1633]	529	/////////////////
	530	// subdivide view space with respect to the objects
[1625]	531
[1684]	532	// dirtied object space candidates
[1633]	533	SubdivisionCandidateContainer dirtyOspList;
[1624]	534
[1633]	535	// process view space candidates
[1727]	536	const int vspSteps = RunConstruction(viewSpaceQueue,
	537	dirtyOspList,
	538	objectSpaceQueue.Top(),
	539	minSteps,
	540	maxSteps);
[1624]	541
[1640]	542	cout << "\n" << vspSteps << " view space partition steps taken" << endl;
[1684]	543	Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
[1625]	544
[1633]	545	// view space subdivision constructed
	546	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
[1624]	547
[1633]	548	/// Repair split queue
	549	cout << "repairing queue ... " << endl;
	550	RepairQueue(dirtyOspList, objectSpaceQueue, true);
[1727]	551
[1640]	552	cout << "repaired " << (int)dirtyOspList.size() << " candidates" << endl;
[1633]	553	}
[1449]	554	}
[1633]	555
[1624]	556	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	557
	558	mHierarchyStats.Stop();
	559	mVspTree->mVspStats.Stop();
[1625]	560
[1649]	561	FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
[1449]	562	}
	563
	564
	565	void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
	566	const ObjectContainer &objects,
	567	AxisAlignedBox3 *forcedViewSpace)
	568	{
[1308]	569	mHierarchyStats.Reset();
	570	mHierarchyStats.Start();
[1664]	571
	572	// two nodes for view space and object space
	573	mHierarchyStats.mNodes = 2;
[1640]	574	mHierarchyStats.mPvsEntries = 1;
[1667]	575	mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
[1640]	576	mHierarchyStats.mTotalCost = (float)objects.size();
[1449]	577
[1624]	578	mHierarchyStats.mRenderCostDecrease = 0;
[1237]	579
[1624]	580	EvalSubdivisionStats();
	581	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
	582
[1311]	583	const long startTime = GetTime();
[1308]	584	cout << "Constructing view space / object space tree ... \n";
[1237]	585
[1640]	586	// create only roots
	587	mVspTree->Initialise(sampleRays, forcedViewSpace);
	588	InitialiseObjectSpaceSubdivision(objects);
[1379]	589
[1633]	590	// use objects for evaluating vsp tree construction in the
	591	// first levels of the subdivision
[1323]	592	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
	593	mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
	594
[1370]	595	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	596	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
	597
[1632]	598	// start view space subdivison immediately?
[1329]	599	if (StartViewSpaceSubdivision())
	600	{
[1624]	601	// prepare vsp tree for traversal
[1640]	602	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	603	SubdivisionCandidate *vspSc =
	604	PrepareViewSpaceSubdivision(sampleRays, objects);
	605
[1632]	606	mTQueue.Push(vspSc);
[1329]	607	}
	608
[1323]	609	// start object space subdivision immediately?
	610	if (StartObjectSpaceSubdivision())
	611	{
	612	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
[1632]	613	SubdivisionCandidate *ospSc =
	614	PrepareObjectSpaceSubdivision(sampleRays, objects);
	615	mTQueue.Push(ospSc);
[1323]	616	}
[1632]	617
[1624]	618	// begin subdivision
[1667]	619	RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
[1308]	620
[1418]	621	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1370]	622
[1548]	623	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
	624	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	625
[1313]	626	mHierarchyStats.Stop();
[1259]	627	mVspTree->mVspStats.Stop();
[1649]	628
	629	FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
[1237]	630	}
	631
	632
[1625]	633	SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
	634	const ObjectContainer &objects)
[1311]	635	{
[1632]	636	cout << "\npreparing view space hierarchy construction ... " << endl;
[1625]	637
[1580]	638	// hack: reset global cost misses
[1548]	639	mHierarchyStats.mGlobalCostMisses = 0;
[1625]	640
[1311]	641	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	642	SubdivisionCandidate *vsc =
[1379]	643	mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
[1311]	644
[1661]	645	/////////
	646	//-- new stats
	647
[1624]	648	mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
[1662]	649
[1624]	650	cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
[1421]	651
[1625]	652	return vsc;
[1311]	653	}
	654
	655
[1640]	656	float HierarchyManager::GetObjectSpaceMemUsage() const
	657	{
	658	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	659	{
	660	// TODO;
	661	}
	662	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	663	{
	664	return mBvHierarchy->GetMemUsage();
	665	}
	666
	667	return -1;
	668	}
	669
	670	void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
	671	{
	672	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	673	{
	674	// TODO;
	675	}
	676	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	677	{
	678	mBvHierarchy->Initialise(objects);
	679	}
	680	}
	681
	682
[1625]	683	SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
	684	const ObjectContainer &objects)
[1308]	685	{
[1625]	686	// hack: reset global cost misses
	687	mHierarchyStats.mGlobalCostMisses = 0;
[1522]	688
[1308]	689	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	690	{
[1625]	691	return PrepareOspTree(sampleRays, objects);
[1308]	692	}
	693	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	694	{
[1625]	695	return PrepareBvHierarchy(sampleRays, objects);
[1308]	696	}
[1625]	697
	698	return NULL;
[1308]	699	}
[1294]	700
[1308]	701
[1625]	702	SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
	703	const ObjectContainer &objects)
[1294]	704	{
[1421]	705	const long startTime = GetTime();
	706
	707	cout << "preparing bv hierarchy construction ... " << endl;
[1548]	708
[1294]	709	// compute first candidate
	710	SubdivisionCandidate *sc =
	711	mBvHierarchy->PrepareConstruction(sampleRays, objects);
	712
[1624]	713	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
	714	Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
[1294]	715
[1548]	716	cout << "finished bv hierarchy preparation in "
	717	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1625]	718
	719	return sc;
[1294]	720	}
	721
	722
[1625]	723	SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
	724	const ObjectContainer &objects)
[1294]	725	{
[1370]	726	cout << "starting osp tree construction ... " << endl;
	727
[1294]	728	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
	729
	730	// start with one big kd cell - all objects can be seen from everywhere
	731	// note: only true for view space = object space
	732
	733	// compute first candidate
	734	SubdivisionCandidate *osc =
	735	mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
	736
[1624]	737	mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
[1625]	738	Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
[1294]	739
[1625]	740	return osc;
[1294]	741	}
	742
	743
[1624]	744	bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
[1625]	745	SplitQueue &splitQueue,
[1624]	746	const bool repairQueue)
[1237]	747	{
[1624]	748	const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
[1633]	749	const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
[1444]	750
[1610]	751	if (!success) // split was not taken
	752	{
	753	return false;
	754	}
	755
	756	///////////////
[1624]	757	//-- split was successful => update stats and queue
[1610]	758
	759	// cost ratio of cost decrease / totalCost
[1624]	760	const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
[1610]	761	//Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
	762
	763	if (costRatio < mTermMinGlobalCostRatio)
	764	{
	765	++ mHierarchyStats.mGlobalCostMisses;
	766	}
	767
[1580]	768	cout << sc->Type() << " ";
	769
[1640]	770	/////////////
[1580]	771	// update stats
[1640]	772
[1624]	773	mHierarchyStats.mNodes += 2;
[1640]	774	mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
	775
	776	const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
	777	mHierarchyStats.mPvsEntries += pvsEntriesIncr;
	778	//cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
	779
	780	// memory size in byte
[1676]	781	mHierarchyStats.mMemory += (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
[1624]	782	mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
	783
[1654]	784	static float memoryCount = 0;
	785
	786	if (mHierarchyStats.mMemory > memoryCount)
	787	{
	788	memoryCount += 100000;
[1684]	789	cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
	790	<< " MB, steps: " << mHierarchyStats.Leaves() << endl;
[1654]	791	}
	792
[1640]	793	// output stats
[1624]	794	EvalSubdivisionStats();
[1580]	795
	796	if (repairQueue)
[1624]	797	{
	798	// reevaluate candidates affected by the split for view space splits,
	799	// this would be object space splits and other way round
[1625]	800	vector<SubdivisionCandidate *> dirtyList;
[1633]	801	sc->CollectDirtyCandidates(dirtyList, false);
[1624]	802
[1633]	803	RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
[1580]	804	}
	805
[1416]	806	return true;
[1237]	807	}
	808
	809
[1370]	810	int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
	811	{
	812	int maxDepth = 0;
	813
	814	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	815	{
	816	maxDepth = mOspTree->mOspStats.maxDepth;
	817	}
	818	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	819	{
	820	maxDepth = mBvHierarchy->mBvhStats.maxDepth;
	821	}
	822
	823	return maxDepth;
	824	}
	825
	826
[1640]	827	int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
	828	{
	829	int maxLeaves= 0;
	830
	831	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	832	{
	833	maxLeaves = mOspTree->mOspStats.Leaves();
	834	}
	835	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	836	{
	837	maxLeaves = mBvHierarchy->mBvhStats.Leaves();
	838	}
	839
	840	return maxLeaves;
	841	}
	842
	843
[1663]	844	int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
	845	{
	846	int maxLeaves = 0;
	847
	848	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	849	{
	850	maxLeaves = mOspTree->mOspStats.nodes;
	851	}
	852	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
	853	{
	854	maxLeaves = mBvHierarchy->mBvhStats.nodes;
	855	}
	856
	857	return maxLeaves;
	858	}
	859
[1308]	860	bool HierarchyManager::StartObjectSpaceSubdivision() const
[1237]	861	{
[1370]	862	// view space construction already started
	863	if (ObjectSpaceSubdivisionConstructed())
	864	return false;
	865
	866	// start immediately with object space subdivision?
	867	if (mStartWithObjectSpace)
	868	return true;
	869
	870	// is the queue empty again?
	871	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
	872	return true;
	873
	874	// has the depth for subdivision been reached?
	875	return
	876	((mConstructionType == INTERLEAVED) &&
[1640]	877	(mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
[1308]	878	}
	879
	880
[1329]	881	bool HierarchyManager::StartViewSpaceSubdivision() const
	882	{
[1370]	883	// view space construction already started
	884	if (ViewSpaceSubdivisionConstructed())
	885	return false;
	886
	887	// start immediately with view space subdivision?
	888	if (!mStartWithObjectSpace)
	889	return true;
	890
	891	// is the queue empty again?
	892	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
	893	return true;
	894
	895	// has the depth for subdivision been reached?
	896	return
	897	((mConstructionType == INTERLEAVED) &&
[1640]	898	(mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
[1329]	899	}
	900
	901
[1449]	902	void HierarchyManager::RunConstruction(const bool repairQueue,
	903	const VssRayContainer &sampleRays,
[1311]	904	const ObjectContainer &objects,
[1640]	905	AxisAlignedBox3 *forcedViewSpace)
[1308]	906	{
[1313]	907	while (!FinishedConstruction())
	908	{
[1625]	909	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
[1632]	910
[1415]	911	///////////////////
[1237]	912	//-- subdivide leaf node
[1415]	913
[1625]	914	ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
[1580]	915
[1313]	916	// we use objects for evaluating vsp tree construction until
[1415]	917	// a certain depth once a certain depth existiert ...
[1313]	918	if (StartObjectSpaceSubdivision())
	919	{
[1323]	920	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
[1314]	921
[1640]	922	cout << "\nstarting object space subdivision after "
[1723]	923	<< mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem="
	924	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
[1329]	925
[1632]	926	SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
[1640]	927
[1313]	928	cout << "reseting queue ... ";
[1640]	929	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
[1313]	930	cout << "finished" << endl;
[1640]	931
	932	mTQueue.Push(ospSc);
[1313]	933	}
	934
[1329]	935	if (StartViewSpaceSubdivision())
	936	{
	937	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	938
[1723]	939	cout << "\nstarting view space subdivision at "
[1640]	940	<< GetObjectSpaceSubdivisionLeaves() << " ("
[1723]	941	<< mMinStepsOfSameType << ") , mem="
	942	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
[1329]	943
[1640]	944	SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
[1329]	945
	946	cout << "reseting queue ... ";
[1640]	947	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
[1329]	948	cout << "finished" << endl;
[1640]	949
	950	// push view space candidate
	951	mTQueue.Push(vspSc);
[1329]	952	}
	953
[1624]	954	DEL_PTR(sc);
[1237]	955	}
	956	}
	957
	958
[1449]	959	void HierarchyManager::RunConstruction(const bool repairQueue)
	960	{
[1580]	961	// main loop
[1449]	962	while (!FinishedConstruction())
	963	{
[1625]	964	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
[1649]	965
[1624]	966	////////
	967	//-- subdivide leaf node of either type
[1642]	968	ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
	969
[1624]	970	DEL_PTR(sc);
[1449]	971	}
	972	}
	973
	974
[1625]	975	int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
[1633]	976	SubdivisionCandidateContainer &dirtyCandidates,
[1667]	977	SubdivisionCandidate *oldCandidate,
[1676]	978	const int minSteps,
	979	const int maxSteps)
[1624]	980	{
[1676]	981	if (minSteps >= maxSteps)
	982	cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
	983
[1625]	984	int steps = 0;
[1633]	985	SubdivisionCandidate::NewMail();
[1625]	986
[1624]	987	// main loop
[1634]	988	while (!splitQueue.Empty())
[1624]	989	{
[1727]	990	// reevaluate current candidate
	991	if (splitQueue.Top()->IsDirty())
	992	splitQueue.Top()->EvalCandidate();
	993
[1701]	994	const float priority = splitQueue.Top()->GetPriority();
[1686]	995	const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
[1679]	996
[1701]	997	// minimum slope reached
	998	if ((steps >= maxSteps) \|\| ((priority < threshold) && !(steps < minSteps)))
	999	{
	1000	cout << "\n**************** breaking on " << priority << " smaller than " << threshold << endl;
	1001	break;
	1002	}
	1003
[1624]	1004	////////
	1005	//-- subdivide leaf node of either type
	1006
[1727]	1007	SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
	1008
[1625]	1009	const bool repairQueue = false;
[1633]	1010	const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
[1625]	1011
[1632]	1012	if (success)
	1013	{
[1697]	1014	sc->CollectDirtyCandidates(dirtyCandidates, true);
[1633]	1015	++ steps;
[1632]	1016	}
[1696]	1017
	1018	DEL_PTR(sc);
[1624]	1019	}
[1625]	1020
	1021	return steps;
[1624]	1022	}
	1023
	1024
[1625]	1025	SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
	1026	const ObjectContainer &objects)
[1580]	1027	{
[1632]	1028	SubdivisionCandidate *firstCandidate;
[1625]	1029
[1580]	1030	// object space partition constructed => reconstruct
[1557]	1031	switch (mObjectSpaceSubdivisionType)
	1032	{
	1033	case BV_BASED_OBJ_SUBDIV:
[1580]	1034	{
	1035	cout << "\nreseting bv hierarchy" << endl;
	1036	Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
[1663]	1037
	1038	// rather use this: remove previous nodes and add the two new ones
	1039	//mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
	1040	mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
[1649]	1041
[1663]	1042	// create root
[1642]	1043	mBvHierarchy->Initialise(objects);
[1649]	1044
[1632]	1045	firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
[1649]	1046
[1625]	1047	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
[1663]	1048
[1662]	1049	//mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
[1649]	1050	mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
[1663]	1051
[1667]	1052	mHierarchyStats.mMemory =
	1053	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
[1642]	1054
[1662]	1055	mHierarchyStats.mRenderCostDecrease = 0;
	1056
[1625]	1057	// evaluate stats before first subdivision
	1058	EvalSubdivisionStats();
[1649]	1059	cout << "finished bv hierarchy preparation" << endl;
[1580]	1060	}
[1548]	1061	break;
[1557]	1062
[1548]	1063	case KD_BASED_OBJ_SUBDIV:
	1064	// TODO
	1065	default:
[1632]	1066	firstCandidate = NULL;
[1548]	1067	break;
	1068	}
[1633]	1069
[1625]	1070	return firstCandidate;
[1449]	1071	}
	1072
	1073
[1625]	1074	SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
[1642]	1075	const ObjectContainer &objects,
	1076	AxisAlignedBox3 *forcedViewSpace)
[1557]	1077	{
[1649]	1078	ViewCellsManager *vm = mVspTree->mViewCellsManager;
[1557]	1079
[1624]	1080	// HACK: rather not destroy vsp tree
[1580]	1081	DEL_PTR(mVspTree);
	1082	mVspTree = new VspTree();
[1649]	1083
[1580]	1084	mVspTree->mHierarchyManager = this;
[1649]	1085	mVspTree->mViewCellsManager = vm;
[1580]	1086
[1642]	1087	mVspTree->Initialise(sampleRays, forcedViewSpace);
[1580]	1088
[1662]	1089	//-- reset stats
[1663]	1090	mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
[1662]	1091
	1092	SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
	1093
	1094	mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
[1661]	1095	mHierarchyStats.mRenderCostDecrease = 0;
	1096
[1667]	1097	mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
[1662]	1098
[1640]	1099	// evaluate new stats before first subdivsiion
[1624]	1100	EvalSubdivisionStats();
[1625]	1101
	1102	return vsc;
[1557]	1103	}
	1104
	1105
[1449]	1106	void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,
	1107	const ObjectContainer &objects,
	1108	AxisAlignedBox3 *forcedViewSpace)
	1109	{
	1110	mHierarchyStats.Reset();
	1111	mHierarchyStats.Start();
[1624]	1112	mHierarchyStats.mNodes = 2;
[1449]	1113
[1624]	1114	mHierarchyStats.mTotalCost = (float)objects.size();
	1115	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
[1449]	1116
	1117	const long startTime = GetTime();
	1118	cout << "Constructing view space / object space tree ... \n";
	1119
[1640]	1120	// initialise view / object space
	1121	mVspTree->Initialise(sampleRays, forcedViewSpace);
	1122	InitialiseObjectSpaceSubdivision(objects);
[1449]	1123
[1580]	1124	// use sah for evaluating osp tree construction
	1125	// in the first iteration of the subdivision
[1642]	1126
[1449]	1127	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
	1128	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
[1640]	1129
[1642]	1130	SubdivisionCandidate *osc =
	1131	PrepareObjectSpaceSubdivision(sampleRays, objects);
	1132	mTQueue.Push(osc);
[1640]	1133
[1649]	1134	//////////////////////////
[1642]	1135
	1136
[1640]	1137	const int limit = mNumMultiLevels;
	1138	int i = 0;
	1139
	1140	// This method subdivides view space / object space
	1141	// in order to converge to some optimal cost for this partition
	1142	// start with object space partiton
	1143	// then optimizate view space partition for the current osp
	1144	// and vice versa until iteration depth is reached.
	1145	while (1)
	1146	{
	1147	char subdivisionStatsLog[100];
	1148	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
	1149	mSubdivisionStats.open(subdivisionStatsLog);
	1150
	1151	// subdivide object space first
[1642]	1152	osc = ResetObjectSpaceSubdivision(sampleRays, objects);
	1153	mTQueue.Push(osc);
[1640]	1154
	1155	// process object space candidates
	1156	RunConstruction(false);
	1157
	1158	// object space subdivision constructed
	1159	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
	1160
	1161	cout << "iteration " << i << " of " << limit << " finished" << endl;
	1162	mSubdivisionStats.close();
	1163
	1164	if ((i ++) >= limit)
	1165	break;
	1166
	1167	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
	1168	mSubdivisionStats.open(subdivisionStatsLog);
	1169
[1649]	1170
[1640]	1171	/////////////////
	1172	// subdivide view space with respect to the objects
	1173
[1649]	1174	SubdivisionCandidate *vspVc =
	1175	ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
[1640]	1176	mTQueue.Push(vspVc);
	1177
	1178	// view space subdivision constructed
	1179	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
	1180
	1181	// process view space candidates
	1182	RunConstruction(false);
	1183
	1184	cout << "iteration " << i << " of " << limit << " finished" << endl;
	1185	mSubdivisionStats.close();
	1186
	1187	if ((i ++) >= limit)
	1188	break;
	1189	}
[1635]	1190
[1640]	1191	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
[1580]	1192
[1640]	1193	mHierarchyStats.Stop();
	1194	mVspTree->mVspStats.Stop();
	1195	FinishObjectSpaceSubdivision(objects);
	1196	}
	1197
	1198
	1199	void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,
	1200	const ObjectContainer &objects,
	1201	AxisAlignedBox3 *forcedViewSpace)
	1202	{
[1649]	1203	const long startTime = GetTime();
	1204	const int limit = mNumMultiLevels;
	1205
	1206	// open up new subdivision
	1207	mSubdivisionStats.close();
	1208
	1209	int steps = 0;
	1210
	1211	int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
	1212	int maxObjectSpaceLeaves;
	1213
[1642]	1214	// set the number of leaves 'evaluated' from the previous methods
[1649]	1215	// we go for the same numbers, but we try to optimize both subdivisions
[1642]	1216	switch (mObjectSpaceSubdivisionType)
	1217	{
	1218	case BV_BASED_OBJ_SUBDIV:
[1649]	1219	maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
[1642]	1220	break;
	1221	case KD_BASED_OBJ_SUBDIV:
[1649]	1222	maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
[1642]	1223	default:
[1649]	1224	maxObjectSpaceLeaves = 0;
[1642]	1225	break;
	1226	}
[1640]	1227
[1624]	1228	// This method subdivides view space / object space
	1229	// in order to converge to some optimal cost for this partition
[1557]	1230	// start with object space partiton
	1231	// then optimizate view space partition for the current osp
	1232	// and vice versa until iteration depth is reached.
	1233	while (1)
[1548]	1234	{
[1580]	1235	char subdivisionStatsLog[100];
[1642]	1236	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
[1580]	1237	mSubdivisionStats.open(subdivisionStatsLog);
	1238
[1624]	1239	// subdivide object space first
[1643]	1240	SubdivisionCandidate *ospVc =
	1241	ResetObjectSpaceSubdivision(sampleRays, objects);
[1649]	1242
	1243	// set the number of leaves 'evaluated' from the previous methods
	1244	// we go for the same numbers, but we try to optimize both subdivisions
	1245	mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
[1642]	1246	mTQueue.Push(ospVc);
[1624]	1247
[1548]	1248	// process object space candidates
	1249	RunConstruction(false);
[1449]	1250
[1642]	1251	cout << "iteration " << steps << " of " << limit << " finished" << endl;
[1580]	1252	mSubdivisionStats.close();
[1635]	1253
[1642]	1254	if ((++ steps) >= limit)
[1557]	1255	break;
	1256
[1642]	1257	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
[1580]	1258	mSubdivisionStats.open(subdivisionStatsLog);
	1259
[1557]	1260	/////////////////
[1580]	1261	// subdivide view space with respect to the objects
	1262
[1643]	1263	SubdivisionCandidate *vspVc =
	1264	ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
[1649]	1265
	1266	mVspTree->mMaxViewCells = maxViewSpaceLeaves;
[1640]	1267	mTQueue.Push(vspVc);
[1624]	1268
[1548]	1269	// process view space candidates
	1270	RunConstruction(false);
[1624]	1271
[1642]	1272	cout << "iteration " << steps << " of " << limit << " finished" << endl;
[1580]	1273	mSubdivisionStats.close();
	1274
[1642]	1275	if ((++ steps) >= limit)
[1557]	1276	break;
[1548]	1277	}
	1278
[1449]	1279	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	1280
	1281	mHierarchyStats.Stop();
	1282	mVspTree->mVspStats.Stop();
	1283	FinishObjectSpaceSubdivision(objects);
	1284	}
	1285
	1286
[1640]	1287
[1237]	1288	bool HierarchyManager::FinishedConstruction() const
	1289	{
	1290	return mTQueue.Empty();
	1291	}
	1292
	1293
[1313]	1294	bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
[1311]	1295	{
[1642]	1296	/*switch (mObjectSpaceSubdivisionType)
[1311]	1297	{
	1298	case KD_BASED_OBJ_SUBDIV:
	1299	return mOspTree && mOspTree->GetRoot();
	1300	case BV_BASED_OBJ_SUBDIV:
[1344]	1301	return mBvHierarchy && mBvHierarchy->GetRoot();
[1311]	1302	default:
[1580]	1303	return false;
[1642]	1304	}*/
	1305	return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
[1311]	1306	}
	1307
	1308
[1329]	1309	bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
	1310	{
[1635]	1311	return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
	1312	//return mVspTree && mVspTree->GetRoot();
[1329]	1313	}
	1314
	1315
[1625]	1316	void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
	1317	SubdivisionCandidateContainer &dirtyList)
[1237]	1318	{
[1625]	1319	SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
[1633]	1320	SubdivisionCandidate::NewMail();
[1625]	1321
	1322	for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
	1323	{
[1633]	1324	(*sit)->CollectDirtyCandidates(dirtyList, true);
[1625]	1325	}
	1326	}
	1327
	1328
[1633]	1329	void HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
	1330	SplitQueue &splitQueue,
	1331	const bool recomputeSplitPlaneOnRepair)
[1625]	1332	{
[1237]	1333	// for each update of the view space partition:
	1334	// the candidates from object space partition which
	1335	// have been afected by the view space split (the kd split candidates
	1336	// which saw the view cell which was split) must be reevaluated
	1337	// (maybe not locally, just reinsert them into the queue)
	1338	//
	1339	// vice versa for the view cells
	1340	// for each update of the object space partition
	1341	// reevaluate split candidate for view cells which saw the split kd cell
	1342	//
	1343	// the priority queue update can be solved by implementing a binary heap
	1344	// (explicit data structure, binary tree)
	1345	// *) inserting and removal is efficient
	1346	// *) search is not efficient => store queue position with each
	1347	// split candidate
	1348
	1349	// collect list of "dirty" candidates
[1580]	1350	const long startTime = GetTime();
[1625]	1351	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
[1624]	1352
[1727]	1353	const float prop = (float)mMaxRepairs / (float)dirtyList.size();
	1354
[1684]	1355	///////////////////////////
[1305]	1356	//-- reevaluate the dirty list
[1415]	1357
[1313]	1358	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
[1302]	1359
[1237]	1360	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
	1361	{
[1727]	1362	// only repair a certain number of candidates
	1363	if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
	1364	continue;
	1365
[1237]	1366	SubdivisionCandidate* sc = *sit;
[1305]	1367	const float rcd = sc->GetRenderCostDecrease();
[1302]	1368
[1667]	1369	// erase from queue
	1370	splitQueue.Erase(sc);
	1371	// reevaluate candidate
	1372	sc->EvalCandidate(recomputeSplitPlaneOnRepair);
	1373	// reinsert
	1374	splitQueue.Push(sc);
	1375
	1376	cout << ".";
	1377
[1715]	1378	#ifdef GTP_DEBUG
[1305]	1379	Debug << "candidate " << sc << " reevaluated\n"
	1380	<< "render cost decrease diff " << rcd - sc->GetRenderCostDecrease()
[1580]	1381	<< " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
	1382	#endif
[1237]	1383	}
[1313]	1384
[1625]	1385	const long endTime = GetTime();
	1386	const Real timeDiff = TimeDiff(startTime, endTime);
	1387
[1624]	1388	mHierarchyStats.mRepairTime += timeDiff;
[1313]	1389
[1633]	1390	if (0) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
[1237]	1391	}
	1392
[1259]	1393
[1640]	1394	void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
[1313]	1395	{
	1396	SubdivisionCandidateContainer mCandidateBuffer;
	1397
	1398	// remove from queue
[1640]	1399	while (!splitQueue.Empty())
[1313]	1400	{
[1640]	1401	SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
[1625]	1402	// reevaluate local split plane and priority
[1667]	1403	candidate->EvalCandidate(recomputeSplitPlane);
[1313]	1404	cout << ".";
	1405	mCandidateBuffer.push_back(candidate);
	1406	}
	1407
	1408	// put back into queue
	1409	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
	1410	for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
[1580]	1411	{
[1640]	1412	splitQueue.Push(*sit);
[1313]	1413	}
	1414	}
	1415
	1416
[1279]	1417	void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
	1418	{
	1419	// the type of the view cells hierarchy
[1308]	1420	switch (mObjectSpaceSubdivisionType)
[1279]	1421	{
	1422	case KD_BASED_OBJ_SUBDIV:
	1423	stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
	1424	mOspTree->Export(stream);
	1425	stream << endl << "</ObjectSpaceHierarchy>" << endl;
[1305]	1426	break;
[1279]	1427	case BV_BASED_OBJ_SUBDIV:
	1428	stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
	1429	mBvHierarchy->Export(stream);
	1430	stream << endl << "</ObjectSpaceHierarchy>" << endl;
	1431	break;
	1432	}
	1433	}
	1434
	1435
	1436	bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
	1437	const Vector3 &hitPoint,
	1438	ViewCell *vc,
	1439	const float pdf,
	1440	float &contribution) const
	1441	{
	1442	if (!obj) return false;
	1443
[1308]	1444	switch (mObjectSpaceSubdivisionType)
[1279]	1445	{
	1446	case NO_OBJ_SUBDIV:
[1486]	1447	{
	1448	// potentially visible objects
	1449	return vc->AddPvsSample(obj, pdf, contribution);
	1450	}
[1279]	1451	case KD_BASED_OBJ_SUBDIV:
	1452	{
	1453	// potentially visible kd cells
	1454	KdLeaf leaf = mOspTree->GetLeaf(hitPoint/ray->mOriginNode*/);
	1455	return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
	1456	}
	1457	case BV_BASED_OBJ_SUBDIV:
	1458	{
	1459	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
[1370]	1460	BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
	1461
	1462	return vc->AddPvsSample(bvhObj, pdf, contribution);
[1279]	1463	}
	1464	default:
	1465	return false;
	1466	}
	1467	}
	1468
	1469
[1421]	1470	void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
[1279]	1471	{
[1313]	1472	stream << mHierarchyStats << endl;
	1473	stream << "\nview space:" << endl << endl;
	1474	stream << mVspTree->GetStatistics() << endl;
	1475	stream << "\nobject space:" << endl << endl;
[1370]	1476
[1308]	1477	switch (mObjectSpaceSubdivisionType)
[1279]	1478	{
	1479	case KD_BASED_OBJ_SUBDIV:
	1480	{
[1313]	1481	stream << mOspTree->GetStatistics() << endl;
[1279]	1482	break;
	1483	}
	1484	case BV_BASED_OBJ_SUBDIV:
	1485	{
[1313]	1486	stream << mBvHierarchy->GetStatistics() << endl;
[1279]	1487	break;
	1488	}
	1489	default:
	1490	break;
	1491	}
	1492	}
	1493
	1494
[1287]	1495	void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
[1416]	1496	const ObjectContainer &objects,
[1418]	1497	const AxisAlignedBox3 *bbox,
	1498	const bool exportBounds) const
[1279]	1499	{
[1308]	1500	switch (mObjectSpaceSubdivisionType)
[1286]	1501	{
	1502	case KD_BASED_OBJ_SUBDIV:
[1279]	1503	{
[1287]	1504	ExportOspTree(exporter, objects);
[1286]	1505	break;
	1506	}
	1507	case BV_BASED_OBJ_SUBDIV:
	1508	{
[1418]	1509	exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
[1286]	1510	break;
	1511	}
	1512	default:
	1513	break;
	1514	}
	1515	}
[1279]	1516
[1286]	1517
[1287]	1518	void HierarchyManager::ExportOspTree(Exporter *exporter,
	1519	const ObjectContainer &objects) const
[1286]	1520	{
[1287]	1521	if (0) exporter->ExportGeometry(objects);
[1279]	1522
[1287]	1523	exporter->SetWireframe();
	1524	exporter->ExportOspTree(*mOspTree, 0);
[1286]	1525	}
	1526
	1527
[1418]	1528	Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
	1529	const bool isTermination) const
	1530	{
	1531
	1532	Intersectable *obj;
	1533	Vector3 pt;
	1534	KdNode *node;
	1535
	1536	ray.GetSampleData(isTermination, pt, &obj, &node);
	1537
	1538	if (!obj) return NULL;
	1539
	1540	switch (mObjectSpaceSubdivisionType)
	1541	{
	1542	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
	1543	{
	1544	KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
	1545	return mOspTree->GetOrCreateKdIntersectable(leaf);
	1546	}
	1547	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
	1548	{
	1549	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
	1550	return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
	1551	}
	1552	default:
	1553	return obj;
	1554	}
	1555	}
	1556
	1557
[1313]	1558	void HierarchyStatistics::Print(ostream &app) const
	1559	{
	1560	app << "=========== Hierarchy statistics ===============\n";
	1561
	1562	app << setprecision(4);
	1563
	1564	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
	1565
[1624]	1566	app << "#N_RTIME ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
[1313]	1567
[1624]	1568	app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
[1313]	1569
	1570	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
	1571
	1572	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
	1573
[1624]	1574	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
[1449]	1575
	1576	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
[1313]	1577
	1578	app << "========== END OF Hierarchy statistics ==========\n";
	1579	}
	1580
	1581
[1418]	1582	static void RemoveRayRefs(const ObjectContainer &objects)
[1370]	1583	{
[1418]	1584	ObjectContainer::const_iterator oit, oit_end = objects.end();
	1585	for (oit = objects.begin(); oit != oit_end; ++ oit)
	1586	{
[1696]	1587	(*oit)->DelRayRefs();
[1418]	1588	}
	1589	}
	1590
	1591
[1679]	1592	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
	1593	const bool removeRayRefs) const
[1418]	1594	{
[1370]	1595	switch (mObjectSpaceSubdivisionType)
	1596	{
	1597	case KD_BASED_OBJ_SUBDIV:
	1598	{
	1599	mOspTree->mOspStats.Stop();
	1600	break;
	1601	}
	1602	case BV_BASED_OBJ_SUBDIV:
	1603	{
	1604	mBvHierarchy->mBvhStats.Stop();
[1649]	1605	if (removeRayRefs)
	1606	RemoveRayRefs(objects);
[1370]	1607	break;
	1608	}
	1609	default:
	1610	break;
	1611	}
	1612	}
	1613
[1614]	1614
	1615	void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
	1616	{
	1617	stream << "<BoundingBoxes>" << endl;
	1618
	1619	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
	1620	{
	1621	KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
	1622
	1623	int id = 0;
	1624	for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
	1625	{
	1626	Intersectable obj = (kit).second;
	1627	const AxisAlignedBox3 box = obj->GetBox();
	1628
	1629	obj->SetId(id);
	1630
	1631	stream << "<BoundingBox" << " id=\"" << id << "\""
	1632	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	1633	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
	1634	}
	1635	}
	1636	else
	1637	{
	1638	ObjectContainer::const_iterator oit, oit_end = objects.end();
	1639
	1640	for (oit = objects.begin(); oit != oit_end; ++ oit)
	1641	{
	1642	const AxisAlignedBox3 box = (*oit)->GetBox();
	1643
	1644	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
	1645	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
	1646	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
	1647	}
	1648	}
	1649
	1650	stream << "</BoundingBoxes>" << endl;
	1651	}
	1652
[1680]	1653
[1706]	1654	class HierarchyNodeWrapper;
	1655
	1656
	1657	template <typename T> class myless
	1658	{
	1659	public:
	1660	bool operator() (T v1, T v2) const
	1661	{
	1662	return (v1->GetMergeCost() < v2->GetMergeCost());
	1663	}
	1664	};
	1665
[1709]	1666
[1706]	1667	typedef priority_queue<HierarchyNodeWrapper , vector<HierarchyNodeWrapper >,
	1668	myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
	1669
	1670	class HierarchyNodeWrapper
	1671	{
	1672	public:
[1707]	1673	enum {VSP_NODE, BVH_NODE, VIEW_CELL};
[1706]	1674
	1675	virtual float GetMergeCost() const = 0;
	1676	virtual int Type() const = 0;
	1677	virtual bool IsLeaf() const = 0;
	1678
	1679	virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
	1680	};
	1681
	1682
	1683	class VspNodeWrapper: public HierarchyNodeWrapper
	1684	{
	1685	public:
	1686	VspNodeWrapper(VspNode *node): mNode(node) {}
	1687
	1688	int Type() const { return VSP_NODE; }
	1689
	1690	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
	1691
	1692	bool IsLeaf() const { return mNode->IsLeaf(); }
	1693
	1694	void PushChildren(HierarchyNodeQueue &tQueue)
	1695	{
	1696	if (!mNode->IsLeaf())
	1697	{
	1698	VspInterior interior = dynamic_cast<VspInterior >(mNode);
	1699
	1700	tQueue.push(new VspNodeWrapper(interior->GetFront()));
	1701	tQueue.push(new VspNodeWrapper(interior->GetBack()));
	1702	}
	1703	}
	1704
	1705	VspNode *mNode;
	1706	};
	1707
	1708
	1709	class BvhNodeWrapper: public HierarchyNodeWrapper
	1710	{
	1711	public:
	1712	BvhNodeWrapper(BvhNode *node): mNode(node) {}
[1686]	1713
[1706]	1714	int Type() const { return BVH_NODE; }
	1715
	1716	float GetMergeCost() const { return (float)-mNode->mTimeStamp; };
	1717
	1718	bool IsLeaf() const { return mNode->IsLeaf(); }
	1719
	1720	void PushChildren(HierarchyNodeQueue &tQueue)
	1721	{
	1722	if (!mNode->IsLeaf())
	1723	{
	1724	BvhInterior interior = dynamic_cast<BvhInterior >(mNode);
	1725
	1726	tQueue.push(new BvhNodeWrapper(interior->GetFront()));
	1727	tQueue.push(new BvhNodeWrapper(interior->GetBack()));
	1728	}
	1729	}
	1730
	1731	BvhNode *mNode;
	1732	};
	1733
	1734
[1707]	1735	class ViewCellWrapper: public HierarchyNodeWrapper
	1736	{
	1737	public:
	1738
	1739	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
	1740
	1741	int Type() const { return VIEW_CELL; }
	1742
	1743	float GetMergeCost() const { return mViewCell->GetMergeCost(); };
	1744
	1745	bool IsLeaf() const { return mViewCell->IsLeaf(); }
	1746
	1747	void PushChildren(HierarchyNodeQueue &tQueue)
	1748	{
	1749	if (!mViewCell->IsLeaf())
	1750	{
	1751	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(mViewCell);
	1752
	1753	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
	1754
	1755	for (it = interior->mChildren.begin(); it != it_end; ++ it)
	1756	{
	1757	tQueue.push(new ViewCellWrapper(*it));
	1758	}
	1759	}
	1760	}
	1761
	1762	ViewCell *mViewCell;
	1763	};
	1764
	1765
[1706]	1766	void HierarchyManager::CollectBestSet(const int maxSplits,
	1767	const float maxMemoryCost,
[1707]	1768	ViewCellContainer &viewCells,
[1706]	1769	vector<BvhNode *> &bvhNodes)
	1770	{
	1771	HierarchyNodeQueue tqueue;
[1707]	1772	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
	1773	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
[1706]	1774	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
	1775
	1776	float memCost = 0;
	1777
	1778	while (!tqueue.empty())
	1779	{
	1780	HierarchyNodeWrapper *nodeWrapper = tqueue.top();
	1781	tqueue.pop();
[1713]	1782	//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
[1706]	1783	// save the view cells if it is a leaf or if enough view cells have already been traversed
	1784	// because of the priority queue, this will be the optimal set of v
	1785	if (nodeWrapper->IsLeaf() \|\|
[1707]	1786	((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) \|\|
[1706]	1787	(memCost > maxMemoryCost)
	1788	)
	1789	{
[1713]	1790	if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
[1706]	1791	{
[1713]	1792	//cout << "1";
[1707]	1793	ViewCellWrapper viewCellWrapper = dynamic_cast<ViewCellWrapper >(nodeWrapper);
	1794	viewCells.push_back(viewCellWrapper->mViewCell);
[1706]	1795	}
	1796	else
	1797	{
[1713]	1798	//cout << "0";
[1706]	1799	BvhNodeWrapper bvhNodeWrapper = dynamic_cast<BvhNodeWrapper >(nodeWrapper);
	1800	bvhNodes.push_back(bvhNodeWrapper->mNode);
	1801	}
	1802	}
	1803	else
	1804	{
	1805	nodeWrapper->PushChildren(tqueue);
	1806	}
	1807
	1808	delete nodeWrapper;
	1809	}
	1810	}
	1811
	1812
[1713]	1813	int HierarchyManager::ExtractStatistics(const int maxSplits,
	1814	const float maxMemoryCost,
	1815	float &renderCost,
	1816	float &memory,
[1718]	1817	int &pvsEntries,
	1818	int &viewSpaceSplits,
	1819	int &objectSpaceSplits)
[1706]	1820	{
[1707]	1821	ViewCellContainer viewCells;
	1822	vector<BvhNode *> bvhNodes;
	1823
[1709]	1824	// collect best set of view cells for this #splits
[1707]	1825	CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
[1713]	1826	//cout << "here5 " << bvhNodes.size() << endl;
[1707]	1827	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
	1828
[1713]	1829	// set new nodes to be active
[1707]	1830	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
	1831	{
	1832	mBvHierarchy->SetActive(*bit);
	1833	}
	1834
	1835	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
	1836
[1713]	1837	pvsEntries = 0;
	1838	renderCost = 0.0f;
[1707]	1839
[1713]	1840	//BvhNode::NewMail();
	1841	//int dummy = 0;
[1707]	1842	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
	1843	{
[1713]	1844	float rc = 0;
[1707]	1845	ViewCell vc = vit;
	1846	ObjectPvs pvs;
	1847	mVspTree->mViewCellsTree->GetPvs(vc, pvs);
[1713]	1848	//dummy+=pvs.GetSize();
[1707]	1849	BvhNode::NewMail();
	1850
	1851	// hack: should not be done here
	1852	ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
	1853
	1854	for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
	1855	{
	1856	BvhIntersectable intersect = dynamic_cast<BvhIntersectable >((*oit).first);
[1713]	1857
[1707]	1858	BvhLeaf *leaf = intersect->GetItem();
	1859	BvhNode *activeNode = leaf->GetActiveNode();
	1860
	1861	if (!activeNode->Mailed())
	1862	{
	1863	activeNode->Mail();
	1864
[1713]	1865	ObjectContainer objects;
	1866	activeNode->CollectObjects(objects);
	1867
	1868	++ pvsEntries;
	1869	rc += mBvHierarchy->EvalAbsCost(objects);
	1870	//cout << " pvs: " << mBvHierarchy->EvalAbsCost(leaf->mObjects);
[1707]	1871	}
	1872	}
[1713]	1873
	1874	rc *= vc->GetVolume();
	1875	renderCost += rc;
[1707]	1876	}
	1877
[1713]	1878	renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
	1879
	1880	memory = pvsEntries * ObjectPvs::GetEntrySize();
[1718]	1881
	1882	viewSpaceSplits = (int)viewCells.size();
	1883	objectSpaceSplits = (int)bvhNodes.size();
	1884
[1713]	1885	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
	1886
	1887	return viewCells.size() + bvhNodes.size();
[1709]	1888	}
[1706]	1889
	1890
[1709]	1891	void HierarchyManager::ExportStats(ofstream &stats,
	1892	SplitQueue &tQueue,
	1893	const ObjectContainer &objects)
	1894	{
[1723]	1895	HierarchySubdivisionStats subStats;
	1896	subStats.Reset();
[1706]	1897
	1898	/////////////
[1723]	1899	//-- initial situation
[1706]	1900
[1723]	1901	subStats.mNumSplits = 0;
	1902	subStats.mTotalRenderCost = (float)objects.size();
	1903	subStats.mEntriesInPvs = 1;
	1904	subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
	1905	subStats.mFullMemory = subStats.mMemoryCost;
	1906	subStats.mViewSpaceSplits = 0;
	1907	subStats.mObjectSpaceSplits = 0;
	1908
	1909	subStats.Print(stats);
[1706]	1910
[1723]	1911	cout << "exporting vsposp stats ... " << endl;
	1912
[1706]	1913	//-- go through tree in the order of render cost decrease
	1914	//-- which is the same order as the view cells were merged
	1915	//-- or the reverse order of subdivision for subdivision-only
	1916	//-- view cell hierarchies.
[1709]	1917
	1918	while (!tQueue.Empty())
[1706]	1919	{
[1709]	1920	SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
	1921	bool isLeaf;
	1922	int timeStamp;
	1923	float rcDecr;
	1924	int entriesIncr;
[1706]	1925
[1709]	1926	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
	1927	{
	1928	timeStamp = (int)-nextCandidate->GetPriority();
[1706]	1929
[1709]	1930	VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
	1931	VspNode oldNode = (VspNode )nextCandidate->mEvaluationHack;
	1932
	1933	isLeaf = newNode->IsLeaf();
[1723]	1934	subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
[1709]	1935	entriesIncr = oldNode->mPvsEntriesIncr;
	1936	}
	1937	else
	1938	{
	1939	timeStamp = (int)-nextCandidate->GetPriority();
	1940
	1941	BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
	1942	BvhNode oldNode = (BvhNode )nextCandidate->mEvaluationHack;
	1943
	1944	isLeaf = newNode->IsLeaf();
[1723]	1945	subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
[1709]	1946	entriesIncr = oldNode->mPvsEntriesIncr;
	1947	}
	1948
	1949	if (!isLeaf)
	1950	{
[1723]	1951	subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
	1952	subStats.mEntriesInPvs += entriesIncr;
	1953
[1709]	1954	// if (rcDecr <= 0)
[1718]	1955	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
	1956	{
[1723]	1957	++ subStats.mViewSpaceSplits;
[1709]	1958	cout << "v";//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
[1718]	1959	}
[1709]	1960	else
[1718]	1961	{
[1723]	1962	++ subStats.mObjectSpaceSplits;
[1709]	1963	cout << "o";//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
[1718]	1964	}
[1706]	1965
[1723]	1966	++ subStats.mNumSplits;
[1706]	1967
[1723]	1968	if ((subStats.mNumSplits % 500) == 499)
	1969	cout << subStats.mNumSplits << " steps taken" << endl;
[1718]	1970
[1723]	1971	subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
	1972	subStats.mFullMemory = subStats.mMemoryCost;
	1973
	1974	subStats.Print(stats);
	1975
[1709]	1976	}
[1706]	1977
[1709]	1978	DEL_PTR(nextCandidate);
	1979	}
[1706]	1980
[1709]	1981	stats.close();
	1982	}
[1706]	1983
	1984
[1709]	1985	void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
	1986	const ObjectContainer &objects,
	1987	const string &filename)
	1988	{
	1989	VspTree *oldVspTree = mVspTree;
	1990	ViewCellsManager *vm = mVspTree->mViewCellsManager;
	1991	BvHierarchy *oldHierarchy = mBvHierarchy;
[1706]	1992
[1709]	1993	mBvHierarchy = new BvHierarchy();
	1994	mBvHierarchy->mHierarchyManager = this;
	1995	mBvHierarchy->mViewCellsManager = vm;
[1706]	1996
[1709]	1997	mVspTree = new VspTree();
	1998	mVspTree->mHierarchyManager = this;
	1999	mVspTree->mViewCellsManager = vm;
[1706]	2000
[1709]	2001	// create first nodes
	2002	mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
	2003	InitialiseObjectSpaceSubdivision(objects);
[1706]	2004
[1709]	2005	const long startTime = GetTime();
	2006	cout << "Constructing evaluation hierarchies ... \n";
	2007
	2008	ofstream stats;
	2009	stats.open(filename.c_str());
	2010	SplitQueue tQueue;
[1706]	2011
[1709]	2012	BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
	2013	VspNode *oldVspRoot = oldVspTree->GetRoot();
[1706]	2014
[1709]	2015	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
	2016
	2017	SubdivisionCandidate firstVsp = mVspTree->PrepareConstruction(sampleRays, viewSpaceRays);
	2018	SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);
	2019
	2020	firstVsp->mEvaluationHack = oldVspRoot;
	2021	firstBvh->mEvaluationHack = oldBvhRoot;
	2022
	2023	firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
	2024	firstBvh->SetPriority((float)-oldBvhRoot->mTimeStamp);
	2025
	2026	tQueue.Push(firstVsp);
	2027	tQueue.Push(firstBvh);
	2028
	2029	ExportStats(stats, tQueue, objects);
	2030
	2031	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
	2032	RemoveRayRefs(objects);
	2033
	2034	// view cells needed only for evaluation
	2035	ViewCellContainer viewCells;
	2036	mVspTree->CollectViewCells(viewCells, false);
	2037
	2038	// helper trees can be destroyed
	2039	DEL_PTR(mVspTree);
	2040	DEL_PTR(mBvHierarchy);
	2041
	2042	CLEAR_CONTAINER(viewCells);
	2043
	2044	// reset hierarchies
	2045	mVspTree = oldVspTree;
	2046	mBvHierarchy = oldHierarchy;
	2047
	2048	// reinstall old bv refs
	2049	vector<BvhLeaf *> leaves;
	2050	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
	2051	vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
	2052
	2053	for (bit = leaves.begin(); bit != bit_end; ++ bit)
	2054	{
	2055	mBvHierarchy->AssociateObjectsWithLeaf(*bit);
[1706]	2056	}
[1709]	2057	}
[1706]	2058
[1709]	2059
	2060	void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
[1713]	2061	const int splitsStepSize)
[1709]	2062	{
[1723]	2063	HierarchySubdivisionStats subStats;
	2064
[1709]	2065	int splits = 0;
	2066
	2067	while (1)
	2068	{
[1723]	2069	subStats.mNumSplits = ExtractStatistics(splits,
[1718]	2070	99999.0,
[1723]	2071	subStats.mTotalRenderCost,
	2072	subStats.mMemoryCost,
	2073	subStats.mEntriesInPvs,
	2074	subStats.mViewSpaceSplits,
	2075	subStats.mObjectSpaceSplits);
	2076
[1713]	2077
[1723]	2078	const float objectSpaceHierarchyMem = float(
	2079	subStats.mObjectSpaceSplits * sizeof(BvhLeaf *) +
	2080	(subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior *) +
	2081	sizeof(BvHierarchy)
	2082	) / float(1024 * 1024);
[1718]	2083
[1723]	2084
	2085	const float viewSpaceHierarchyMem = float(
	2086	subStats.mViewSpaceSplits * sizeof(VspLeaf *) +
	2087	(subStats.mViewSpaceSplits - 1) * sizeof(VspInterior *) +
	2088	sizeof(VspTree)
	2089	) / float(1024 * 1024);
	2090
	2091	subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
	2092
	2093	subStats.Print(splitsStats);
	2094
[1710]	2095	splits += splitsStepSize;
[1709]	2096
[1723]	2097	if (subStats.mNumSplits == mHierarchyStats.Leaves())
[1709]	2098	break;
	2099	}
[1706]	2100	}
[1709]	2101
[1718]	2102
	2103	void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
	2104	{
[1719]	2105	mBvHierarchy->CollectObjects(box, objects);
[1715]	2106	}
[1718]	2107
	2108	}

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

Download in other formats: