Context Navigation

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

Revision 1933, 67.2 KB checked in by mattausch, 18 years ago (diff)
worked on gvs reverse sampling (still in debug state)

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

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

Download in other formats: