Context Navigation

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

Revision 2187, 70.8 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: