Context Navigation

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

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

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

Download in other formats: