Context Navigation

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

Revision 2117, 68.8 KB checked in by mattausch, 17 years ago (diff)
implemented bit pvs (warnin: only worjs for preprocessing)

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

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

Download in other formats: