Context Navigation

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

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

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

Download in other formats: