Context Navigation

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

Revision 2539, 68.9 KB checked in by mattausch, 17 years ago (diff)
fixed obj loading error

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

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

Download in other formats: