Context Navigation

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

Revision 2210, 71.3 KB checked in by mattausch, 17 years ago (diff)
improved performance of osp

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	// assume pvs not sampled sufficiently => take total pvs
840	if (avgRayContri >= mMaxAvgRayContri)
841	{
842	return totalPvs;
843	}
844
845	const float alpha = (mMaxAvgRayContri - avgRayContri) /
846	(mMaxAvgRayContri - mMinAvgRayContri);
847
848	const float beta = (1.0f - alpha) * (totalPvs - childPvs);
849	#if 1
850	const float newPvs = childPvs + beta;
851	#else
852	const float newPvs = alpha * childPvs + (1.0f - alpha) * totalPvs;
853	#endif
854
855	//cout << "alpha " << alpha << " beta: " << beta << " child: " << childPvs << " parent: " << totalPvs << endl;
856
857	if ((newPvs < childPvs - Limits::Small) \|\| (newPvs > totalPvs + Limits::Small))
858	cout << "Error!! " << newPvs << endl;
859	return newPvs;
860	}
861
862
863	bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
864	SplitQueue &splitQueue,
865	const bool repairQueue)
866	{
867	const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
868	const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
869
870	if (sc->IsDirty())
871	cerr << "Error: Should never come here!" << endl;
872
873	if (!success) // split was not taken
874	{
875	cout << "x";
876	return false;
877	}
878
879
880	///////////////
881	//-- split was successful => update stats and queue
882
883	// cost ratio of cost decrease / totalCost
884	const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
885	//cout << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
886
887	if (costRatio < mTermMinGlobalCostRatio)
888	{
889	++ mHierarchyStats.mGlobalCostMisses;
890	}
891
892	cout << sc->Type() << " ";
893
894	/////////////
895	// update stats
896
897	mHierarchyStats.mNodes += 2;
898	mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
899
900	const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
901	mHierarchyStats.mPvsEntries += pvsEntriesIncr;
902	//cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.mPvsEntries << endl;
903
904	// memory size in byte
905	float mem = (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
906
907	// high avg ray contri, the result is influenced by undersampling
908	// => decrease priority
909	if (0 && USE_AVGRAYCONTRI && (sc->GetAvgRayContribution() > mMaxAvgRayContri))
910	{
911	const float factor = 1.0f + sc->GetAvgRayContribution() - mMaxAvgRayContri;
912	cout << "h " << factor << endl;
913
914	mem *= factor;
915	}
916
917	mHierarchyStats.mMemory += mem;
918	mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
919
920	mPriority = sc->GetPriority();
921
922	//////////
923	// show current memory
924
925	static float memoryCount = 0;
926
927	if (mHierarchyStats.mMemory > memoryCount)
928	{
929	memoryCount += 100000;
930	cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
931	<< " MB, steps: " << mHierarchyStats.Leaves() << endl;
932	}
933
934	// output stats
935	EvalSubdivisionStats();
936
937	if (repairQueue)
938	{
939	// reevaluate candidates affected by the split for view space splits,
940	// this would be object space splits and other way round
941	vector<SubdivisionCandidate *> dirtyList;
942	sc->CollectDirtyCandidates(dirtyList, false);
943
944	RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
945	}
946
947	return true;
948	}
949
950
951	int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
952	{
953	int maxDepth = 0;
954
955	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
956	{
957	maxDepth = mOspTree->mOspStats.maxDepth;
958	}
959	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
960	{
961	maxDepth = mBvHierarchy->mBvhStats.maxDepth;
962	}
963
964	return maxDepth;
965	}
966
967
968	int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
969	{
970	int maxLeaves= 0;
971
972	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
973	{
974	maxLeaves = mOspTree->mOspStats.Leaves();
975	}
976	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
977	{
978	maxLeaves = mBvHierarchy->mBvhStats.Leaves();
979	}
980
981	return maxLeaves;
982	}
983
984
985	int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
986	{
987	int maxLeaves = 0;
988
989	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
990	{
991	maxLeaves = mOspTree->mOspStats.nodes;
992	}
993	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
994	{
995	maxLeaves = mBvHierarchy->mBvhStats.nodes;
996	}
997
998	return maxLeaves;
999	}
1000
1001	bool HierarchyManager::StartObjectSpaceSubdivision() const
1002	{
1003	// view space construction already started
1004	if (ObjectSpaceSubdivisionConstructed())
1005	return false;
1006
1007	// start immediately with object space subdivision?
1008	if (mStartWithObjectSpace)
1009	return true;
1010
1011	// is the queue empty again?
1012	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
1013	return true;
1014
1015	// has the depth for subdivision been reached?
1016	return
1017	((mConstructionType == INTERLEAVED) &&
1018	(mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
1019	}
1020
1021
1022	bool HierarchyManager::StartViewSpaceSubdivision() const
1023	{
1024	// view space construction already started
1025	if (ViewSpaceSubdivisionConstructed())
1026	return false;
1027
1028	// start immediately with view space subdivision?
1029	if (!mStartWithObjectSpace)
1030	return true;
1031
1032	// is the queue empty again?
1033	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
1034	return true;
1035
1036	// has the depth for subdivision been reached?
1037	return
1038	((mConstructionType == INTERLEAVED) &&
1039	(mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
1040	}
1041
1042
1043	void HierarchyManager::RunConstruction(const bool repairQueue,
1044	const VssRayContainer &sampleRays,
1045	const ObjectContainer &objects,
1046	AxisAlignedBox3 *forcedViewSpace)
1047	{
1048	while (!FinishedConstruction())
1049	{
1050	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
1051
1052	///////////////////
1053	//-- subdivide leaf node
1054
1055	ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
1056
1057	// we use objects for evaluating vsp tree construction until
1058	// a certain depth once a certain depth existiert ...
1059	if (StartObjectSpaceSubdivision())
1060	{
1061	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1062
1063	cout << "\nstarting object space subdivision after "
1064	<< mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem="
1065	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
1066
1067	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1068
1069	cout << "reseting queue ... ";
1070	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
1071	cout << "finished" << endl;
1072	}
1073
1074	if (StartViewSpaceSubdivision())
1075	{
1076	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1077
1078	cout << "\nstarting view space subdivision at "
1079	<< GetObjectSpaceSubdivisionLeaves() << " ("
1080	<< mMinStepsOfSameType << ") , mem="
1081	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
1082
1083	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
1084
1085	cout << "reseting queue ... ";
1086	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
1087	cout << "finished" << endl;
1088	}
1089
1090	DEL_PTR(sc);
1091	}
1092	}
1093
1094
1095	void HierarchyManager::RunConstruction(const bool repairQueue)
1096	{
1097	// main loop
1098	while (!FinishedConstruction())
1099	{
1100	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
1101
1102	////////
1103	//-- subdivide leaf node of either type
1104
1105	ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
1106
1107	DEL_PTR(sc);
1108	}
1109	}
1110
1111
1112	int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
1113	SubdivisionCandidateContainer &dirtyCandidates,
1114	SubdivisionCandidate *oldCandidate,
1115	const int minSteps,
1116	const int maxSteps)
1117	{
1118	if (minSteps >= maxSteps)
1119	cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
1120
1121	int steps = 0;
1122	SubdivisionCandidate::NewMail();
1123
1124	// main loop
1125	while (!splitQueue.Empty())
1126	{
1127	const float priority = splitQueue.Top()->GetPriority();
1128	const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
1129
1130	// minimum slope reached
1131	if ((steps >= maxSteps) \|\| ((priority < threshold) && !(steps < minSteps)))
1132	{
1133	cout << "\nbreaking on " << priority << " smaller than " << threshold << endl;
1134	break;
1135	}
1136
1137	////////
1138	//-- subdivide leaf node of either type
1139
1140	SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
1141
1142	const bool repairQueue = false;
1143	const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
1144
1145	if (success)
1146	{
1147	sc->CollectDirtyCandidates(dirtyCandidates, true);
1148	++ steps;
1149	}
1150
1151	DEL_PTR(sc);
1152	}
1153
1154	return steps;
1155	}
1156
1157
1158	void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue,
1159	const VssRayContainer &sampleRays,
1160	const ObjectContainer &objects)
1161	{
1162	// object space partition constructed => reconstruct
1163	switch (mObjectSpaceSubdivisionType)
1164	{
1165	case BV_BASED_OBJ_SUBDIV:
1166	{
1167	cout << "\nreseting bv hierarchy" << endl;
1168	Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
1169
1170	// rather use this: remove previous nodes and add the two new ones
1171	//mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
1172	mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
1173
1174	// create root
1175	mBvHierarchy->Initialise(objects);
1176
1177	mBvHierarchy->Reset(tQueue, sampleRays, objects);
1178
1179	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
1180
1181	//mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
1182	mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
1183
1184	mHierarchyStats.mMemory =
1185	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1186
1187	mHierarchyStats.mRenderCostDecrease = 0;
1188
1189	// evaluate stats before first subdivision
1190	EvalSubdivisionStats();
1191	cout << "finished bv hierarchy preparation" << endl;
1192	}
1193	break;
1194
1195	case KD_BASED_OBJ_SUBDIV:
1196	// TODO
1197	default:
1198	break;
1199	}
1200	}
1201
1202
1203	void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue,
1204	const VssRayContainer &sampleRays,
1205	const ObjectContainer &objects,
1206	AxisAlignedBox3 *forcedViewSpace)
1207	{
1208	ViewCellsManager *vm = mVspTree->mViewCellsManager;
1209
1210	// HACK: rather not destroy vsp tree
1211	DEL_PTR(mVspTree);
1212	mVspTree = new VspTree();
1213
1214	mVspTree->mHierarchyManager = this;
1215	mVspTree->mViewCellsManager = vm;
1216
1217	mVspTree->Initialise(sampleRays, forcedViewSpace);
1218
1219	//////////
1220	//-- reset stats
1221	mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();
1222	//-mVspTree->mVspStats.nodes + 1;
1223
1224	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
1225
1226	mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
1227	mHierarchyStats.mRenderCostDecrease = 0;
1228
1229	mHierarchyStats.mMemory =
1230	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1231
1232	// evaluate new stats before first subdivsiion
1233	EvalSubdivisionStats();
1234	}
1235
1236
1237	void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,
1238	const ObjectContainer &objects,
1239	AxisAlignedBox3 *forcedViewSpace)
1240	{
1241	mHierarchyStats.Reset();
1242	mHierarchyStats.Start();
1243	mHierarchyStats.mNodes = 2;
1244
1245	mHierarchyStats.mTotalCost = (float)objects.size();
1246	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
1247
1248	const long startTime = GetTime();
1249	cout << "Constructing view space / object space tree ... \n";
1250
1251	// initialise view / object space
1252	mVspTree->Initialise(sampleRays, forcedViewSpace);
1253	InitialiseObjectSpaceSubdivision(objects);
1254
1255	// use sah for evaluating osp tree construction
1256	// in the first iteration of the subdivision
1257
1258	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
1259	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
1260
1261	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1262
1263	//////////////////////////
1264
1265
1266	const int limit = mNumMultiLevels;
1267	int i = 0;
1268
1269	// This method subdivides view space / object space
1270	// in order to converge to some optimal cost for this partition
1271	// start with object space partiton
1272	// then optimizate view space partition for the current osp
1273	// and vice versa until iteration depth is reached.
1274	while (1)
1275	{
1276	char subdivisionStatsLog[100];
1277	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1278	mSubdivisionStats.open(subdivisionStatsLog);
1279
1280	// subdivide object space first
1281	ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1282
1283	// process object space candidates
1284	RunConstruction(false);
1285
1286	// object space subdivision constructed
1287	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1288
1289	cout << "iteration " << i << " of " << limit << " finished" << endl;
1290	mSubdivisionStats.close();
1291
1292	if ((i ++) >= limit)
1293	break;
1294
1295	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1296	mSubdivisionStats.open(subdivisionStatsLog);
1297
1298
1299	/////////////////
1300	// subdivide view space with respect to the objects
1301
1302	ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
1303
1304	// view space subdivision constructed
1305	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1306
1307	// process view space candidates
1308	RunConstruction(false);
1309
1310	cout << "iteration " << i << " of " << limit << " finished" << endl;
1311	mSubdivisionStats.close();
1312
1313	if ((i ++) >= limit)
1314	break;
1315	}
1316
1317	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1318
1319	mHierarchyStats.Stop();
1320	mVspTree->mVspStats.Stop();
1321	FinishObjectSpaceSubdivision(objects);
1322	}
1323
1324
1325	void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,
1326	const ObjectContainer &objects,
1327	AxisAlignedBox3 *forcedViewSpace)
1328	{
1329	const long startTime = GetTime();
1330	const int limit = mNumMultiLevels;
1331
1332	// open up new subdivision
1333	mSubdivisionStats.close();
1334
1335	int steps = 0;
1336
1337	int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
1338	int maxObjectSpaceLeaves;
1339
1340	// set the number of leaves 'evaluated' from the previous methods
1341	// we go for the same numbers, but we try to optimize both subdivisions
1342	switch (mObjectSpaceSubdivisionType)
1343	{
1344	case BV_BASED_OBJ_SUBDIV:
1345	maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
1346	break;
1347	case KD_BASED_OBJ_SUBDIV:
1348	maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
1349	default:
1350	maxObjectSpaceLeaves = 0;
1351	break;
1352	}
1353
1354	// This method subdivides view space / object space
1355	// in order to converge to some optimal cost for this partition
1356	// start with object space partiton
1357	// then optimizate view space partition for the current osp
1358	// and vice versa until iteration depth is reached.
1359	while (1)
1360	{
1361	char subdivisionStatsLog[100];
1362	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1363	mSubdivisionStats.open(subdivisionStatsLog);
1364
1365	// subdivide object space first
1366	ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1367
1368	// set the number of leaves 'evaluated' from the previous methods
1369	// we go for the same numbers, but we try to optimize both subdivisions
1370	mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
1371
1372	// process object space candidates
1373	RunConstruction(false);
1374
1375	cout << "iteration " << steps << " of " << limit << " finished" << endl;
1376	mSubdivisionStats.close();
1377
1378	if ((++ steps) >= limit)
1379	break;
1380
1381	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1382	mSubdivisionStats.open(subdivisionStatsLog);
1383
1384	/////////////////
1385	// subdivide view space with respect to the objects
1386
1387	ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
1388
1389	mVspTree->mMaxViewCells = maxViewSpaceLeaves;
1390
1391	// process view space candidates
1392	RunConstruction(false);
1393
1394	cout << "iteration " << steps << " of " << limit << " finished" << endl;
1395	mSubdivisionStats.close();
1396
1397	if ((++ steps) >= limit)
1398	break;
1399	}
1400
1401	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1402
1403	mHierarchyStats.Stop();
1404	mVspTree->mVspStats.Stop();
1405	FinishObjectSpaceSubdivision(objects);
1406	}
1407
1408
1409
1410	bool HierarchyManager::FinishedConstruction() const
1411	{
1412	return mTQueue.Empty();
1413	}
1414
1415
1416	bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
1417	{
1418	/*switch (mObjectSpaceSubdivisionType)
1419	{
1420	case KD_BASED_OBJ_SUBDIV:
1421	return mOspTree && mOspTree->GetRoot();
1422	case BV_BASED_OBJ_SUBDIV:
1423	return mBvHierarchy && mBvHierarchy->GetRoot();
1424	default:
1425	return false;
1426	}*/
1427	return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
1428	}
1429
1430
1431	bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
1432	{
1433	return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
1434	//return mVspTree && mVspTree->GetRoot();
1435	}
1436
1437
1438	void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1439	SubdivisionCandidateContainer &dirtyList)
1440	{
1441	SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1442	SubdivisionCandidate::NewMail();
1443
1444	for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1445	{
1446	(*sit)->CollectDirtyCandidates(dirtyList, true);
1447	}
1448	}
1449
1450
1451	int HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1452	SplitQueue &splitQueue,
1453	const bool recomputeSplitPlaneOnRepair)
1454	{
1455	// for each update of the view space partition:
1456	// the candidates from object space partition which
1457	// have been afected by the view space split (the kd split candidates
1458	// which saw the view cell which was split) must be reevaluated
1459	// (maybe not locally, just reinsert them into the queue)
1460	//
1461	// vice versa for the view cells
1462	// for each update of the object space partition
1463	// reevaluate split candidate for view cells which saw the split kd cell
1464	//
1465	// the priority queue update can be solved by implementing a binary heap
1466	// (explicit data structure, binary tree)
1467	// *) inserting and removal is efficient
1468	// *) search is not efficient => store queue position with each
1469	// split candidate
1470
1471	int repaired = 0;
1472
1473	// collect list of "dirty" candidates
1474	const long startTime = GetTime();
1475	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1476
1477	const float prop = (float)mMaxRepairs / (float)dirtyList.size();
1478
1479	///////////////////////////
1480	//-- reevaluate the dirty list
1481
1482	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1483
1484	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1485	{
1486	// only repair a certain number of candidates
1487	if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
1488	continue;
1489
1490	SubdivisionCandidate* sc = *sit;
1491	const float rcd = sc->GetRenderCostDecrease();
1492
1493	// erase from queue
1494	splitQueue.Erase(sc);
1495	// reevaluate candidate
1496	sc->EvalCandidate(recomputeSplitPlaneOnRepair);
1497	// reinsert
1498	splitQueue.Push(sc);
1499
1500	++ repaired;
1501	cout << ".";
1502
1503	#ifdef GTP_DEBUG
1504	Debug << "candidate " << sc << " reevaluated\n"
1505	<< "render cost decrease diff " << rcd - sc->GetRenderCostDecrease()
1506	<< " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1507	#endif
1508	}
1509
1510	const long endTime = GetTime();
1511	const Real timeDiff = TimeDiff(startTime, endTime);
1512
1513	mHierarchyStats.mRepairTime += timeDiff;
1514
1515	return repaired;
1516	}
1517
1518
1519	void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
1520	{
1521	SubdivisionCandidateContainer mCandidateBuffer;
1522
1523	// remove from queue
1524	while (!splitQueue.Empty())
1525	{
1526	SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
1527
1528	// reevaluate local split plane and priority
1529	candidate->EvalCandidate(recomputeSplitPlane);
1530	cout << ".";
1531	mCandidateBuffer.push_back(candidate);
1532	}
1533
1534	// put back into queue
1535	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1536	for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1537	{
1538	splitQueue.Push(*sit);
1539	}
1540	}
1541
1542
1543	void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1544	{
1545	// the type of the view cells hierarchy
1546	switch (mObjectSpaceSubdivisionType)
1547	{
1548	case KD_BASED_OBJ_SUBDIV:
1549	stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1550	mOspTree->Export(stream);
1551	stream << endl << "</ObjectSpaceHierarchy>" << endl;
1552	break;
1553	case BV_BASED_OBJ_SUBDIV:
1554	stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1555	mBvHierarchy->Export(stream);
1556	stream << endl << "</ObjectSpaceHierarchy>" << endl;
1557	break;
1558	}
1559	}
1560
1561
1562	void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1563	{
1564	stream << mHierarchyStats << endl;
1565	stream << "\nview space:" << endl << endl;
1566	stream << mVspTree->GetStatistics() << endl;
1567	stream << "\nobject space:" << endl << endl;
1568
1569	switch (mObjectSpaceSubdivisionType)
1570	{
1571	case KD_BASED_OBJ_SUBDIV:
1572	{
1573	stream << mOspTree->GetStatistics() << endl;
1574	break;
1575	}
1576	case BV_BASED_OBJ_SUBDIV:
1577	{
1578	stream << mBvHierarchy->GetStatistics() << endl;
1579	break;
1580	}
1581	default:
1582	break;
1583	}
1584	}
1585
1586
1587	void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1588	const ObjectContainer &objects,
1589	AxisAlignedBox3 *bbox,
1590	const float maxRenderCost,
1591	const bool exportBounds) const
1592	{
1593	switch (mObjectSpaceSubdivisionType)
1594	{
1595	case KD_BASED_OBJ_SUBDIV:
1596	{
1597	ExportOspTree(exporter, objects);
1598	break;
1599	}
1600	case BV_BASED_OBJ_SUBDIV:
1601	{
1602	exporter->ExportBvHierarchy(*mBvHierarchy, maxRenderCost, bbox, exportBounds);
1603	break;
1604	}
1605	default:
1606	break;
1607	}
1608	}
1609
1610
1611	void HierarchyManager::ExportOspTree(Exporter *exporter,
1612	const ObjectContainer &objects) const
1613	{
1614	if (0) exporter->ExportGeometry(objects);
1615
1616	exporter->SetWireframe();
1617	exporter->ExportOspTree(*mOspTree, 0);
1618	}
1619
1620
1621	Intersectable HierarchyManager::GetIntersectable(Intersectable obj,
1622	const Vector3 &point) const
1623	{
1624
1625	if (!obj)
1626	return NULL;
1627
1628	switch (mObjectSpaceSubdivisionType)
1629	{
1630	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1631	{
1632	KdLeaf *leaf = mOspTree->GetLeaf(point, NULL);
1633	return mOspTree->GetOrCreateKdIntersectable(leaf);
1634	}
1635	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1636	{
1637	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1638	return leaf;
1639	}
1640	default:
1641	return obj;
1642	}
1643	}
1644
1645	Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1646	const bool isTermination) const
1647	{
1648	Intersectable *obj = NULL;
1649	Vector3 pt;
1650	KdNode *node;
1651
1652	ray.GetSampleData(isTermination, pt, &obj, &node);
1653
1654	if (!obj)
1655	return NULL;
1656
1657	switch (mObjectSpaceSubdivisionType)
1658	{
1659	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1660	{
1661	KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1662	return mOspTree->GetOrCreateKdIntersectable(leaf);
1663	}
1664	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1665	{
1666	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1667	return leaf;
1668	}
1669	default:
1670	break;
1671	}
1672
1673	return obj;
1674	}
1675
1676
1677	void HierarchyStatistics::Print(ostream &app) const
1678	{
1679	app << "=========== Hierarchy statistics ===============\n";
1680
1681	app << setprecision(4);
1682
1683	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
1684
1685	app << "#N_RTIME ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1686
1687	app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1688
1689	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1690
1691	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1692
1693	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1694
1695	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1696
1697	app << "========== END OF Hierarchy statistics ==========\n";
1698	}
1699
1700
1701	static void RemoveRayRefs(const ObjectContainer &objects)
1702	{
1703	ObjectContainer::const_iterator oit, oit_end = objects.end();
1704	for (oit = objects.begin(); oit != oit_end; ++ oit)
1705	{
1706	(*oit)->DelRayRefs();
1707	}
1708	}
1709
1710
1711	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1712	const bool removeRayRefs) const
1713	{
1714	switch (mObjectSpaceSubdivisionType)
1715	{
1716	case KD_BASED_OBJ_SUBDIV:
1717	{
1718	mOspTree->mOspStats.Stop();
1719	break;
1720	}
1721	case BV_BASED_OBJ_SUBDIV:
1722	{
1723	mBvHierarchy->mBvhStats.Stop();
1724	if (removeRayRefs)
1725	RemoveRayRefs(objects);
1726	break;
1727	}
1728	default:
1729	break;
1730	}
1731	}
1732
1733
1734	void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1735	{
1736	stream << "<BoundingBoxes>" << endl;
1737
1738	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1739	{
1740	KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1741
1742	int id = 0;
1743	for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1744	{
1745	Intersectable obj = (kit).second;
1746	const AxisAlignedBox3 box = obj->GetBox();
1747
1748	obj->SetId(id);
1749
1750	stream << "<BoundingBox" << " id=\"" << id << "\""
1751	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1752	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1753	}
1754	}
1755	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
1756	{
1757	// export bounding boxes
1758	vector<BvhNode *> nodes;
1759
1760	// hack: should also expect interior nodes
1761	mBvHierarchy->CollectNodes(mBvHierarchy->GetRoot(), nodes);
1762
1763	vector<BvhNode *>::const_iterator oit, oit_end = nodes.end();
1764
1765	for (oit = nodes.begin(); oit != oit_end; ++ oit)
1766	{
1767	const AxisAlignedBox3 box = (*oit)->GetBox();
1768	const int id = (*oit)->GetId();
1769
1770	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1771	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1772	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1773	}
1774	}
1775	else
1776	{
1777	ObjectContainer::const_iterator oit, oit_end = objects.end();
1778
1779	for (oit = objects.begin(); oit != oit_end; ++ oit)
1780	{
1781	const AxisAlignedBox3 box = (*oit)->GetBox();
1782
1783	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1784	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1785	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1786	}
1787	}
1788
1789	stream << "</BoundingBoxes>" << endl;
1790	}
1791
1792
1793	class HierarchyNodeWrapper;
1794
1795
1796	template <typename T> class myless
1797	{
1798	public:
1799	bool operator() (T v1, T v2) const
1800	{
1801	return (v1->GetMergeCost() < v2->GetMergeCost());
1802	}
1803	};
1804
1805
1806	typedef priority_queue<HierarchyNodeWrapper , vector<HierarchyNodeWrapper >,
1807	myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
1808
1809	class HierarchyNodeWrapper
1810	{
1811	public:
1812	enum {VSP_NODE, BVH_NODE, VIEW_CELL};
1813
1814	virtual float GetMergeCost() const = 0;
1815	virtual int Type() const = 0;
1816	virtual bool IsLeaf() const = 0;
1817
1818	virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
1819	};
1820
1821
1822	class VspNodeWrapper: public HierarchyNodeWrapper
1823	{
1824	public:
1825	VspNodeWrapper(VspNode *node): mNode(node) {}
1826
1827	int Type() const { return VSP_NODE; }
1828
1829	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
1830
1831	bool IsLeaf() const { return mNode->IsLeaf(); }
1832
1833	void PushChildren(HierarchyNodeQueue &tQueue)
1834	{
1835	if (!mNode->IsLeaf())
1836	{
1837	VspInterior interior = static_cast<VspInterior >(mNode);
1838
1839	tQueue.push(new VspNodeWrapper(interior->GetFront()));
1840	tQueue.push(new VspNodeWrapper(interior->GetBack()));
1841	}
1842	}
1843
1844	VspNode *mNode;
1845	};
1846
1847
1848	class BvhNodeWrapper: public HierarchyNodeWrapper
1849	{
1850	public:
1851	BvhNodeWrapper(BvhNode *node): mNode(node) {}
1852
1853	int Type() const { return BVH_NODE; }
1854
1855	float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };
1856
1857	bool IsLeaf() const { return mNode->IsLeaf(); }
1858
1859	void PushChildren(HierarchyNodeQueue &tQueue)
1860	{
1861	if (!mNode->IsLeaf())
1862	{
1863	BvhInterior interior = static_cast<BvhInterior >(mNode);
1864
1865	tQueue.push(new BvhNodeWrapper(interior->GetFront()));
1866	tQueue.push(new BvhNodeWrapper(interior->GetBack()));
1867	}
1868	}
1869
1870	BvhNode *mNode;
1871	};
1872
1873
1874	class ViewCellWrapper: public HierarchyNodeWrapper
1875	{
1876	public:
1877
1878	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
1879
1880	int Type() const { return VIEW_CELL; }
1881
1882	float GetMergeCost() const { return mViewCell->GetMergeCost(); };
1883
1884	bool IsLeaf() const { return mViewCell->IsLeaf(); }
1885
1886	void PushChildren(HierarchyNodeQueue &tQueue)
1887	{
1888	if (!mViewCell->IsLeaf())
1889	{
1890	ViewCellInterior interior = static_cast<ViewCellInterior >(mViewCell);
1891
1892	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1893
1894	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1895	{
1896	tQueue.push(new ViewCellWrapper(*it));
1897	}
1898	}
1899	}
1900
1901	ViewCell *mViewCell;
1902	};
1903
1904
1905	void HierarchyManager::CollectBestSet(const int maxSplits,
1906	const float maxMemoryCost,
1907	ViewCellContainer &viewCells,
1908	vector<BvhNode *> &bvhNodes)
1909	{
1910	HierarchyNodeQueue tqueue;
1911	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
1912	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
1913	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
1914
1915	float memCost = 0;
1916
1917	while (!tqueue.empty())
1918	{
1919	HierarchyNodeWrapper *nodeWrapper = tqueue.top();
1920	tqueue.pop();
1921	//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
1922	// save the view cells if it is a leaf or if enough view cells have already been traversed
1923	// because of the priority queue, this will be the optimal set of view cells
1924	if (nodeWrapper->IsLeaf() \|\|
1925	((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) \|\|
1926	(memCost > maxMemoryCost)
1927	)
1928	{
1929	if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
1930	{
1931	//cout << "1";
1932	ViewCellWrapper viewCellWrapper = static_cast<ViewCellWrapper >(nodeWrapper);
1933	viewCells.push_back(viewCellWrapper->mViewCell);
1934	}
1935	else
1936	{
1937	//cout << "0";
1938	BvhNodeWrapper bvhNodeWrapper = static_cast<BvhNodeWrapper >(nodeWrapper);
1939	bvhNodes.push_back(bvhNodeWrapper->mNode);
1940	}
1941	}
1942	else
1943	{
1944	nodeWrapper->PushChildren(tqueue);
1945	}
1946
1947	delete nodeWrapper;
1948	}
1949	}
1950
1951
1952	void HierarchyManager::ComputePvs(const ObjectPvs &pvs,
1953	float &rc,
1954	int &pvsEntries)
1955	{
1956	BvhNode::NewMail();
1957
1958	ObjectPvsIterator pit = pvs.GetIterator();
1959
1960	while (pit.HasMoreEntries())
1961	{
1962	Intersectable *obj = pit.Next();
1963
1964	if (obj->Type() != Intersectable::BVH_INTERSECTABLE)
1965	{
1966	cout << "error: wrong object type detected: " << obj->Type() << endl;
1967	exit(0);
1968	}
1969
1970	BvhNode intersect = static_cast<BvhNode >(obj);
1971	BvhNode *activeNode;
1972
1973	// hack for choosing which node to account for
1974	if (intersect->IsLeaf())
1975	{
1976	activeNode =
1977	static_cast<BvhLeaf *>(intersect)->GetActiveNode();
1978	}
1979	else
1980	{
1981	activeNode = intersect;
1982	}
1983
1984	if (!activeNode->Mailed())
1985	{
1986	activeNode->Mail();
1987
1988	#if STUPID_METHOD
1989
1990	ObjectContainer objects;
1991	activeNode->CollectObjects(objects);
1992	rc += mBvHierarchy->EvalAbsCost(objects);
1993	#else
1994	rc += mBvHierarchy->GetRenderCostIncrementially(activeNode);
1995	#endif
1996	++ pvsEntries;
1997	}
1998	}
1999	}
2000
2001
2002	void HierarchyManager::GetPvsEfficiently(ViewCell *viewCell, ObjectPvs &pvs) const
2003	{
2004	////////////////
2005	//-- pvs is not stored with the interiors => reconstruct
2006
2007	// add pvs from leaves
2008	stack<ViewCell *> tstack;
2009	tstack.push(viewCell);
2010
2011	Intersectable::NewMail();
2012
2013	while (!tstack.empty())
2014	{
2015	ViewCell *vc = tstack.top();
2016	tstack.pop();
2017
2018	// add newly found pvs to merged pvs: break here even for interior
2019	if (!vc->GetPvs().Empty())
2020	{
2021	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
2022
2023	while (pit.HasMoreEntries())
2024	{
2025	Intersectable *object = pit.Next();
2026
2027	if (!object->Mailed())
2028	{
2029	object->Mail();
2030	pvs.AddSampleDirty(object, 1.0f);
2031	}
2032	}
2033	}
2034	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2035	{
2036	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2037	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2038
2039	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2040	{
2041	tstack.push(*it);
2042	}
2043	}
2044	}
2045	}
2046
2047
2048	// TODO matt: implement this function for different storing methods
2049	void HierarchyManager::GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const
2050	{
2051	////////////////
2052	//-- pvs is not stored with the interiors => reconstruct
2053
2054	// add pvs from leaves
2055	stack<ViewCell *> tstack;
2056	tstack.push(vc);
2057
2058	while (!tstack.empty())
2059	{
2060	vc = tstack.top();
2061	tstack.pop();
2062
2063	// add newly found pvs to merged pvs: break here even for interior
2064	if (!vc->GetPvs().Empty())
2065	{
2066	pvs.MergeInPlace(vc->GetPvs());
2067	}
2068	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2069	{
2070	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2071	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2072
2073	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2074	{
2075	tstack.push(*it);
2076	}
2077	}
2078	}
2079	}
2080
2081
2082	// TODO matt: implement this function for different storing methods
2083	void HierarchyManager::PullUpPvsIncrementally(ViewCell *viewCell) const
2084	{
2085	////////////////
2086	//-- pvs is not stored with the interiors => reconstruct
2087
2088	// early exit: pvs is already pulled up to this view cell
2089	if (!viewCell->GetPvs().Empty())
2090	return;
2091
2092	// add pvs from leaves
2093	stack<ViewCell *> tstack;
2094	tstack.push(viewCell);
2095
2096	ViewCell *vc = viewCell;
2097
2098	while (!tstack.empty())
2099	{
2100	vc = tstack.top();
2101	tstack.pop();
2102
2103	// add newly found pvs to merged pvs: break here even for interior
2104	if (!vc->GetPvs().Empty())
2105	{
2106	viewCell->GetPvs().MergeInPlace(vc->GetPvs());
2107	}
2108	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2109	{
2110	//cout <<" t";
2111	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2112	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2113
2114	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2115	{
2116	tstack.push(*it);
2117	}
2118	}
2119	}
2120	}
2121
2122
2123
2124	// TODO matt: implement this function for different storing methods
2125	void HierarchyManager::GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const
2126	{
2127	////////////////
2128	//-- pvs is not stored with the interiors => reconstruct
2129	if (vc->IsLeaf() \|\| !vc->GetPvs().Empty())
2130	{
2131	pvs = vc->GetPvs();
2132	}
2133	else
2134	{
2135	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2136	#if 0
2137	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2138	const int childPvsSize = (int)interior->mChildren.size();
2139	vector<ObjectPvs> childPvs;
2140	childPvs.resize((int)interior->mChildren.size());
2141
2142	int i = 0;
2143	for (it = interior->mChildren.begin(); it != it_end; ++ it, ++ i)
2144	{
2145	GetPvsRecursive(*it, childPvs[i]);
2146	pvs.MergeInPlace(childPvs[i]);
2147	}
2148	#else
2149
2150	ObjectPvs leftPvs, rightPvs;
2151
2152	GetPvsRecursive(interior->mChildren[0], leftPvs);
2153	GetPvsRecursive(interior->mChildren[1], rightPvs);
2154
2155	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2156	#endif
2157	}
2158	}
2159
2160
2161	int HierarchyManager::ExtractStatistics(const int maxSplits,
2162	const float maxMemoryCost,
2163	float &renderCost,
2164	float &memory,
2165	int &pvsEntries,
2166	int &viewSpaceSplits,
2167	int &objectSpaceSplits,
2168	const bool useFilter,
2169	const bool useHisto,
2170	const int histoMem,
2171	const int pass,
2172	bool &histoUsed)
2173	{
2174	ViewCellContainer viewCells;
2175	vector<BvhNode *> bvhNodes;
2176
2177	// collect best set of view cells for this #splits
2178	CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
2179	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
2180
2181	// set new nodes to be active
2182	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
2183	{
2184	mBvHierarchy->SetActive(*bit);
2185	}
2186
2187	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2188
2189	pvsEntries = 0;
2190	renderCost = 0.0f;
2191
2192	ViewCell::NewMail();
2193
2194	//cout << "\nviewcells: " << viewCells.size() << endl;
2195	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2196	{
2197	ViewCell vc = vit;
2198	float rc = 0;
2199
2200	#if STUPID_METHOD
2201	ObjectPvs pvs;
2202	GetPvsIncrementially(vc, pvs);
2203	vc->SetPvs(pvs);
2204
2205	#else
2206
2207	ObjectPvs pvs;
2208
2209	if (vc->GetPvs().Empty())
2210	{
2211	// warning: uses mailing, pvs not sorted!!
2212	GetPvsEfficiently(vc, pvs);
2213	//GetPvsRecursive(vc, pvs);
2214	vc->SetPvs(pvs);
2215	}
2216	#endif
2217
2218	vc->Mail();
2219
2220	if (useFilter)
2221	{
2222	const long startT = GetTime();
2223	ObjectPvs filteredPvs;
2224	mVspTree->mViewCellsManager->ApplyFilter2(vc, false, 1.0f, filteredPvs);
2225	const long endT = GetTime();
2226
2227	//cout << "filter computed in " << TimeDiff(startT, endT) * 1e-3f << " secs" << endl;
2228	ComputePvs(filteredPvs, rc, pvsEntries);
2229	}
2230	else
2231	{
2232	ComputePvs(vc->GetPvs(), rc, pvsEntries);
2233	vc->SetPvsCost(rc);
2234	}
2235
2236	rc *= vc->GetVolume();
2237	renderCost += rc;
2238	}
2239
2240	renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
2241	memory = pvsEntries * ObjectPvs::GetEntrySize();
2242
2243	viewSpaceSplits = (int)viewCells.size();
2244	objectSpaceSplits = (int)bvhNodes.size();
2245
2246	////////////////////////
2247	//-- evaluate histogram for pvs size
2248
2249	if (useHisto && (memory <= (float)histoMem))
2250	{
2251	char str[100];
2252	char statsPrefix[100];
2253	//int histoStepSize;
2254
2255	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
2256
2257	cout << "computing pvs histogram for " << histoMem << " memory" << endl;
2258	Debug << "computing pvs histogram for " << histoMem << " memory" << endl;
2259
2260	sprintf(str, "-%05d-%05d-histo-pvs.log", pass, histoMem);
2261	const string filename = string(statsPrefix) + string(str);
2262
2263	mVspTree->mViewCellsManager->EvalViewCellHistogramForPvsSize(filename, viewCells);
2264
2265	histoUsed = true;
2266	}
2267
2268	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
2269
2270	// delete old "base" view cells if they are not leaves
2271	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2272
2273	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2274	{
2275	if (!(oit)->Mailed() && !(oit)->IsLeaf())
2276	{
2277	(*oit)->GetPvs().Clear();
2278	}
2279	}
2280
2281	// store current level
2282	mOldViewCells = viewCells;
2283
2284	return (int)(viewCells.size() + bvhNodes.size());
2285	}
2286
2287
2288	void HierarchyManager::ExportStats(ofstream &stats,
2289	SplitQueue &tQueue,
2290	const ObjectContainer &objects)
2291	{
2292	HierarchySubdivisionStats subStats;
2293	subStats.Reset();
2294
2295	/////////////
2296	//-- initial situation
2297
2298	subStats.mNumSplits = 0;
2299	subStats.mTotalRenderCost = (float)objects.size();
2300	subStats.mEntriesInPvs = 1;
2301	subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
2302	subStats.mFullMemory = subStats.mMemoryCost;
2303	subStats.mViewSpaceSplits = 0;
2304	subStats.mObjectSpaceSplits = 0;
2305	subStats.mRenderCostDecrease = 0;
2306	subStats.Print(stats);
2307
2308	cout << "exporting vsposp stats ... " << endl;
2309
2310	//-- go through tree in the order of render cost decrease
2311	//-- which is the same order as the view cells were merged
2312	//-- or the reverse order of subdivision for subdivision-only
2313	//-- view cell hierarchies.
2314
2315	while (!tQueue.Empty())
2316	{
2317	SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
2318	bool isLeaf;
2319	int timeStamp;
2320	//float rcDecr;
2321	//int entriesIncr;
2322
2323	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2324	{
2325	timeStamp = (int)-nextCandidate->GetPriority();
2326
2327	VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
2328	VspNode oldNode = (VspNode )nextCandidate->mEvaluationHack;
2329
2330	isLeaf = newNode->IsLeaf();
2331	//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2332	//entriesIncr = oldNode->mPvsEntriesIncr;
2333	}
2334	else
2335	{
2336	timeStamp = (int)-nextCandidate->GetPriority();
2337
2338	BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
2339	BvhNode oldNode = (BvhNode )nextCandidate->mEvaluationHack;
2340
2341	isLeaf = newNode->IsLeaf();
2342	//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2343	//entriesIncr = oldNode->mPvsEntriesIncr;
2344	}
2345
2346	if (!isLeaf)
2347	{
2348	subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
2349	//subStats.mEntriesInPvs += entriesIncr;
2350
2351	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2352	{
2353	++ subStats.mViewSpaceSplits;
2354	cout << "v";
2355	//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2356	}
2357	else
2358	{
2359	++ subStats.mObjectSpaceSplits;
2360	cout << "o";
2361	//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2362	}
2363
2364	++ subStats.mNumSplits;
2365
2366	if ((subStats.mNumSplits % 500) == 499)
2367	cout << subStats.mNumSplits << " steps taken" << endl;
2368
2369	subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
2370	subStats.mFullMemory = subStats.mMemoryCost;
2371
2372	subStats.Print(stats);
2373
2374	}
2375
2376	DEL_PTR(nextCandidate);
2377	}
2378
2379	stats.close();
2380	}
2381
2382
2383	void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
2384	const ObjectContainer &objects,
2385	const string &filename)
2386	{
2387	#if 0
2388	VspTree *oldVspTree = mVspTree;
2389	ViewCellsManager *vm = mVspTree->mViewCellsManager;
2390	BvHierarchy *oldHierarchy = mBvHierarchy;
2391
2392	mBvHierarchy = new BvHierarchy();
2393	mBvHierarchy->mHierarchyManager = this;
2394	mBvHierarchy->mViewCellsManager = vm;
2395
2396	mVspTree = new VspTree();
2397	mVspTree->mHierarchyManager = this;
2398	mVspTree->mViewCellsManager = vm;
2399
2400	// create first nodes
2401	mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
2402	InitialiseObjectSpaceSubdivision(objects);
2403
2404	const long startTime = GetTime();
2405	cout << "Constructing evaluation hierarchies ... \n";
2406
2407	ofstream stats;
2408	stats.open(filename.c_str());
2409	SplitQueue tQueue;
2410
2411	BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
2412	VspNode *oldVspRoot = oldVspTree->GetRoot();
2413
2414	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
2415
2416	SubdivisionCandidate firstVsp = mVspTree->PrepareConstruction(sampleRays, viewSpaceRays);
2417	tQueue.Push(firstVsp);
2418
2419	mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
2420
2421	firstVsp->mEvaluationHack = oldVspRoot;
2422	firstBvh->mEvaluationHack = oldBvhRoot;
2423
2424	firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
2425	firstBvh->SetPriority((float)-oldBvhRoot->GetTimeStamp());
2426
2427	ExportStats(stats, tQueue, objects);
2428
2429	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2430	RemoveRayRefs(objects);
2431
2432	// view cells needed only for evaluation
2433	ViewCellContainer viewCells;
2434	mVspTree->CollectViewCells(viewCells, false);
2435
2436	// helper trees can be destroyed
2437	DEL_PTR(mVspTree);
2438	DEL_PTR(mBvHierarchy);
2439
2440	CLEAR_CONTAINER(viewCells);
2441
2442	// reset hierarchies
2443	mVspTree = oldVspTree;
2444	mBvHierarchy = oldHierarchy;
2445
2446	// reinstall old bv refs
2447	vector<BvhLeaf *> leaves;
2448	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
2449	vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
2450
2451	for (bit = leaves.begin(); bit != bit_end; ++ bit)
2452	{
2453	mBvHierarchy->AssociateObjectsWithLeaf(*bit);
2454	}
2455	#endif
2456	}
2457
2458
2459	void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
2460	const int splitsStepSize,
2461	const bool useFilter,
2462	const bool useHisto,
2463	const int histoMem,
2464	const int pass)
2465	{
2466	vector<HierarchySubdivisionStats> subStatsContainer;
2467
2468	int splits = (1 + (mHierarchyStats.Leaves() - 1) / splitsStepSize) * splitsStepSize;
2469	cout << "splits: " << splits << endl;
2470
2471	bool histoUsed = false;
2472
2473	while (1)
2474	{
2475	HierarchySubdivisionStats subStats;
2476	subStats.mNumSplits = ExtractStatistics(splits,
2477	99999.0,
2478	subStats.mTotalRenderCost,
2479	subStats.mMemoryCost,
2480	subStats.mEntriesInPvs,
2481	subStats.mViewSpaceSplits,
2482	subStats.mObjectSpaceSplits,
2483	useFilter,
2484	useHisto && !histoUsed,
2485	histoMem,
2486	pass,
2487	histoUsed);
2488
2489
2490	const float objectSpaceHierarchyMem = float(
2491	subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
2492	//+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
2493	//+sizeof(BvHierarchy)
2494	) / float(1024 * 1024);
2495
2496
2497	const float viewSpaceHierarchyMem = float(
2498	subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
2499	//+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
2500	+ sizeof(ObjectPvs)
2501	//+ sizeof(VspTree)
2502	) / float(1024 * 1024);
2503
2504	subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
2505
2506	subStatsContainer.push_back(subStats);
2507
2508	if (splits == 0)
2509	{
2510	break;
2511	}
2512	splits -= splitsStepSize;
2513
2514	cout << "splits: " << subStats.mNumSplits << " ";
2515	}
2516
2517	vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();
2518
2519	for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
2520	{
2521	(*hit).Print(splitsStats);
2522	}
2523
2524	// delete old "base" view cells: only pvss in the leaves are allowed
2525	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2526
2527	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2528	{
2529	if (!(*oit)->IsLeaf())
2530	{
2531	(*oit)->GetPvs().Clear();
2532	}
2533	}
2534
2535	mOldViewCells.clear();
2536
2537	// reset active nodes
2538	vector<BvhLeaf *> bvhLeaves;
2539
2540	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);
2541
2542	vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();
2543
2544	for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
2545	{
2546	(bit)->SetActiveNode(bit);
2547	}
2548
2549	cout << endl;
2550	}
2551
2552
2553	void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2554	{
2555	mBvHierarchy->CollectObjects(box, objects);
2556	}
2557
2558
2559	int HierarchyManager::CompressObjectSpace()
2560	{
2561	//mBvHierarchy->Compress();
2562	return mVspTree->CompressObjects();
2563	}
2564
2565
2566	void HierarchyManager::CreateUniqueObjectIds()
2567	{
2568	mBvHierarchy->CreateUniqueObjectIds();
2569	}
2570
2571
2572	void HierarchyManager::CreateTraversalTree()
2573	{
2574	int mind, maxd;
2575	mVspTree->EvalMinMaxDepth(mind, maxd);
2576
2577	cout << "old tree balance: " << mind << " " << maxd << endl;
2578	mTraversalTree = new TraversalTree;
2579
2580	ViewCellContainer viewCells;
2581	mVspTree->CollectViewCells(viewCells, false);
2582
2583	const long startTime = GetTime();
2584
2585	cout << "building traversal tree ... " << endl;
2586
2587	mTraversalTree->Construct(viewCells);
2588
2589	cout << "finished traversal tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3
2590	<< " secs " << endl;
2591
2592	Debug << "* TraversalTree Stats *" << endl;
2593	Debug << mTraversalTree->GetStatistics() << endl;
2594
2595	if (1)
2596	{
2597	Exporter *exporter = Exporter::GetExporter("traversal.wrl");
2598	exporter->ExportTraversalTree(*mTraversalTree, true);
2599	delete exporter;
2600	}
2601	}
2602
2603
2604	int HierarchyManager::CastLineSegment(const Vector3 &origin,
2605	const Vector3 &termination,
2606	ViewCellContainer &viewcells,
2607	const bool useMailboxing)
2608	{
2609	if (!mTraversalTree)
2610	{
2611	return mVspTree->CastLineSegment(origin,termination, viewcells, useMailboxing);
2612	}
2613	else
2614	{
2615	return mTraversalTree->CastLineSegment(origin,termination, viewcells, useMailboxing);
2616	}
2617	}
2618
2619
2620	}

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

Download in other formats: