Context Navigation

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

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

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

Download in other formats: