Context Navigation

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

Revision 2575, 68.7 KB checked in by bittner, 17 years ago (diff)
big merge: preparation for havran ray caster, check if everything works

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

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

Download in other formats: