Context Navigation

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

Revision 2199, 71.3 KB checked in by mattausch, 17 years ago (diff)
using mutationsamples for evaluation

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

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

Download in other formats: