Context Navigation

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

Revision 2093, 67.9 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: