Context Navigation

HierarchyManager.cpp @ 2705

Revision 2705, 66.2 KB checked in by mattausch, 16 years ago (diff)
enabled view cell visualization

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

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

Context Navigation

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

Download in other formats: