Context Navigation

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

Revision 2342, 68.5 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: