Context Navigation

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

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

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

Download in other formats: