Context Navigation

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

Revision 2543, 68.6 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: