Context Navigation

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

Revision 2353, 68.6 KB checked in by mattausch, 18 years ago (diff)
cleaned up project files

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	static void RemoveRayRefs(const ObjectContainer &objects)
1753	{
1754	ObjectContainer::const_iterator oit, oit_end = objects.end();
1755	for (oit = objects.begin(); oit != oit_end; ++ oit)
1756	{
1757	(*oit)->DelRayRefs();
1758	}
1759	}
1760
1761
1762	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1763	const bool removeRayRefs) const
1764	{
1765	switch (mObjectSpaceSubdivisionType)
1766	{
1767	case KD_BASED_OBJ_SUBDIV:
1768	{
1769	mOspTree->mOspStats.Stop();
1770	break;
1771	}
1772	case BV_BASED_OBJ_SUBDIV:
1773	{
1774	mBvHierarchy->mBvhStats.Stop();
1775	if (removeRayRefs)
1776	RemoveRayRefs(objects);
1777	break;
1778	}
1779	default:
1780	break;
1781	}
1782	}
1783
1784
1785	void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1786	{
1787	stream << "<BoundingBoxes>" << endl;
1788
1789	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1790	{
1791	KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1792
1793	int id = 0;
1794	for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1795	{
1796	Intersectable obj = (kit).second;
1797	const AxisAlignedBox3 box = obj->GetBox();
1798
1799	obj->SetId(id);
1800
1801	stream << "<BoundingBox" << " id=\"" << id << "\""
1802	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1803	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1804	}
1805	}
1806	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
1807	{
1808	// export bounding boxes
1809	vector<BvhNode *> nodes;
1810
1811	// hack: should also expect interior nodes
1812	mBvHierarchy->CollectNodes(mBvHierarchy->GetRoot(), nodes);
1813
1814	vector<BvhNode *>::const_iterator oit, oit_end = nodes.end();
1815
1816	for (oit = nodes.begin(); oit != oit_end; ++ oit)
1817	{
1818	const AxisAlignedBox3 box = (*oit)->GetBox();
1819	const int id = (*oit)->GetId();
1820
1821	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1822	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1823	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1824	}
1825	}
1826	else
1827	{
1828	ObjectContainer::const_iterator oit, oit_end = objects.end();
1829
1830	for (oit = objects.begin(); oit != oit_end; ++ oit)
1831	{
1832	const AxisAlignedBox3 box = (*oit)->GetBox();
1833
1834	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1835	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1836	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1837	}
1838	}
1839
1840	stream << "</BoundingBoxes>" << endl;
1841	}
1842
1843
1844	class HierarchyNodeWrapper;
1845
1846
1847	template <typename T> class myless
1848	{
1849	public:
1850	bool operator() (T v1, T v2) const
1851	{
1852	return (v1->GetMergeCost() < v2->GetMergeCost());
1853	}
1854	};
1855
1856
1857	typedef priority_queue<HierarchyNodeWrapper , vector<HierarchyNodeWrapper >,
1858	myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
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 VspNodeWrapper: public HierarchyNodeWrapper
1874	{
1875	public:
1876	VspNodeWrapper(VspNode *node): mNode(node) {}
1877
1878	int Type() const { return VSP_NODE; }
1879
1880	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
1881
1882	bool IsLeaf() const { return mNode->IsLeaf(); }
1883
1884	void PushChildren(HierarchyNodeQueue &tQueue)
1885	{
1886	if (!mNode->IsLeaf())
1887	{
1888	VspInterior interior = static_cast<VspInterior >(mNode);
1889
1890	tQueue.push(new VspNodeWrapper(interior->GetFront()));
1891	tQueue.push(new VspNodeWrapper(interior->GetBack()));
1892	}
1893	}
1894
1895	VspNode *mNode;
1896	};
1897
1898
1899	class BvhNodeWrapper: public HierarchyNodeWrapper
1900	{
1901	public:
1902	BvhNodeWrapper(BvhNode *node): mNode(node) {}
1903
1904	int Type() const { return BVH_NODE; }
1905
1906	float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };
1907
1908	bool IsLeaf() const { return mNode->IsLeaf(); }
1909
1910	void PushChildren(HierarchyNodeQueue &tQueue)
1911	{
1912	if (!mNode->IsLeaf())
1913	{
1914	BvhInterior interior = static_cast<BvhInterior >(mNode);
1915
1916	tQueue.push(new BvhNodeWrapper(interior->GetFront()));
1917	tQueue.push(new BvhNodeWrapper(interior->GetBack()));
1918	}
1919	}
1920
1921	BvhNode *mNode;
1922	};
1923
1924
1925	class ViewCellWrapper: public HierarchyNodeWrapper
1926	{
1927	public:
1928
1929	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
1930
1931	int Type() const { return VIEW_CELL; }
1932
1933	float GetMergeCost() const { return mViewCell->GetMergeCost(); };
1934
1935	bool IsLeaf() const { return mViewCell->IsLeaf(); }
1936
1937	void PushChildren(HierarchyNodeQueue &tQueue)
1938	{
1939	if (!mViewCell->IsLeaf())
1940	{
1941	ViewCellInterior interior = static_cast<ViewCellInterior >(mViewCell);
1942
1943	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1944
1945	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1946	{
1947	tQueue.push(new ViewCellWrapper(*it));
1948	}
1949	}
1950	}
1951
1952	ViewCell *mViewCell;
1953	};
1954
1955
1956	void HierarchyManager::CollectBestSet(const int maxSplits,
1957	const float maxMemoryCost,
1958	ViewCellContainer &viewCells,
1959	vector<BvhNode *> &bvhNodes)
1960	{
1961	HierarchyNodeQueue tqueue;
1962	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
1963	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
1964	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
1965
1966	float memCost = 0;
1967
1968	while (!tqueue.empty())
1969	{
1970	HierarchyNodeWrapper *nodeWrapper = tqueue.top();
1971	tqueue.pop();
1972	//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
1973	// save the view cells if it is a leaf or if enough view cells have already been traversed
1974	// because of the priority queue, this will be the optimal set of view cells
1975	if (nodeWrapper->IsLeaf() \|\|
1976	((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) \|\|
1977	(memCost > maxMemoryCost)
1978	)
1979	{
1980	if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
1981	{
1982	//cout << "1";
1983	ViewCellWrapper viewCellWrapper = static_cast<ViewCellWrapper >(nodeWrapper);
1984	viewCells.push_back(viewCellWrapper->mViewCell);
1985	}
1986	else
1987	{
1988	//cout << "0";
1989	BvhNodeWrapper bvhNodeWrapper = static_cast<BvhNodeWrapper >(nodeWrapper);
1990	bvhNodes.push_back(bvhNodeWrapper->mNode);
1991	}
1992	}
1993	else
1994	{
1995	nodeWrapper->PushChildren(tqueue);
1996	}
1997
1998	delete nodeWrapper;
1999	}
2000	}
2001
2002
2003	void HierarchyManager::ComputePvs(const ObjectPvs &pvs,
2004	float &triangles,
2005	int &pvsEntries)
2006	{
2007	BvhNode::NewMail();
2008
2009	ObjectPvsIterator pit = pvs.GetIterator();
2010
2011	while (pit.HasMoreEntries())
2012	{
2013	Intersectable *obj = pit.Next();
2014
2015	if (obj->Type() != Intersectable::BVH_INTERSECTABLE)
2016	{
2017	cout << "error: wrong object type detected: " << obj->Type() << endl;
2018	exit(0);
2019	}
2020
2021	BvhNode intersect = static_cast<BvhNode >(obj);
2022	BvhNode *activeNode;
2023
2024	// hack for choosing which node to account for
2025	if (intersect->IsLeaf())
2026	{
2027	activeNode =
2028	static_cast<BvhLeaf *>(intersect)->GetActiveNode();
2029	}
2030	else
2031	{
2032	activeNode = intersect;
2033	}
2034
2035	if (!activeNode->Mailed())
2036	{
2037	activeNode->Mail();
2038
2039	#if STUPID_METHOD
2040
2041	ObjectContainer objects;
2042	activeNode->CollectObjects(objects);
2043	triangles += (float)objects.size();
2044	#else
2045	triangles += mBvHierarchy->GetTriangleSizeIncrementially(activeNode);
2046	#endif
2047	++ pvsEntries;
2048	}
2049	}
2050	}
2051
2052
2053	void HierarchyManager::GetPvsEfficiently(ViewCell *viewCell, ObjectPvs &pvs) const
2054	{
2055	////////////////
2056	//-- pvs is not stored with the interiors => reconstruct
2057
2058	// add pvs from leaves
2059	stack<ViewCell *> tstack;
2060	tstack.push(viewCell);
2061
2062	Intersectable::NewMail();
2063
2064	while (!tstack.empty())
2065	{
2066	ViewCell *vc = tstack.top();
2067	tstack.pop();
2068
2069	// add newly found pvs to merged pvs: break here even for interior
2070	if (!vc->GetPvs().Empty())
2071	{
2072	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
2073
2074	while (pit.HasMoreEntries())
2075	{
2076	Intersectable *object = pit.Next();
2077
2078	if (!object->Mailed())
2079	{
2080	object->Mail();
2081	pvs.AddSampleDirty(object, 1.0f);
2082	}
2083	}
2084	}
2085	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2086	{
2087	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2088	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2089
2090	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2091	{
2092	tstack.push(*it);
2093	}
2094	}
2095	}
2096	}
2097
2098
2099	// TODO matt: implement this function for different storing methods
2100	void HierarchyManager::GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const
2101	{
2102	////////////////
2103	//-- pvs is not stored with the interiors => reconstruct
2104
2105	// add pvs from leaves
2106	stack<ViewCell *> tstack;
2107	tstack.push(vc);
2108
2109	while (!tstack.empty())
2110	{
2111	vc = tstack.top();
2112	tstack.pop();
2113
2114	// add newly found pvs to merged pvs: break here even for interior
2115	if (!vc->GetPvs().Empty())
2116	{
2117	pvs.MergeInPlace(vc->GetPvs());
2118	}
2119	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2120	{
2121	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2122	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2123
2124	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2125	{
2126	tstack.push(*it);
2127	}
2128	}
2129	}
2130	}
2131
2132
2133	// TODO matt: implement this function for different storing methods
2134	void HierarchyManager::PullUpPvsIncrementally(ViewCell *viewCell) const
2135	{
2136	////////////////
2137	//-- pvs is not stored with the interiors => reconstruct
2138
2139	// early exit: pvs is already pulled up to this view cell
2140	if (!viewCell->GetPvs().Empty())
2141	return;
2142
2143	// add pvs from leaves
2144	stack<ViewCell *> tstack;
2145	tstack.push(viewCell);
2146
2147	ViewCell *vc = viewCell;
2148
2149	while (!tstack.empty())
2150	{
2151	vc = tstack.top();
2152	tstack.pop();
2153
2154	// add newly found pvs to merged pvs: break here even for interior
2155	if (!vc->GetPvs().Empty())
2156	{
2157	viewCell->GetPvs().MergeInPlace(vc->GetPvs());
2158	}
2159	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2160	{
2161	//cout <<" t";
2162	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2163	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2164
2165	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2166	{
2167	tstack.push(*it);
2168	}
2169	}
2170	}
2171	}
2172
2173
2174
2175	// TODO matt: implement this function for different storing methods
2176	void HierarchyManager::GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const
2177	{
2178	////////////////
2179	//-- pvs is not stored with the interiors => reconstruct
2180	if (vc->IsLeaf() \|\| !vc->GetPvs().Empty())
2181	{
2182	pvs = vc->GetPvs();
2183	}
2184	else
2185	{
2186	ViewCellInterior interior = static_cast<ViewCellInterior >(vc);
2187	#if 0
2188	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2189	const int childPvsSize = (int)interior->mChildren.size();
2190	vector<ObjectPvs> childPvs;
2191	childPvs.resize((int)interior->mChildren.size());
2192
2193	int i = 0;
2194	for (it = interior->mChildren.begin(); it != it_end; ++ it, ++ i)
2195	{
2196	GetPvsRecursive(*it, childPvs[i]);
2197	pvs.MergeInPlace(childPvs[i]);
2198	}
2199	#else
2200
2201	ObjectPvs leftPvs, rightPvs;
2202
2203	GetPvsRecursive(interior->mChildren[0], leftPvs);
2204	GetPvsRecursive(interior->mChildren[1], rightPvs);
2205
2206	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2207	#endif
2208	}
2209	}
2210
2211
2212	int HierarchyManager::ExtractStatistics(const int maxSplits,
2213	const float maxMemoryCost,
2214	float &renderCost,
2215	float &memory,
2216	int &pvsEntries,
2217	int &viewSpaceSplits,
2218	int &objectSpaceSplits,
2219	const bool useFilter,
2220	const bool useHisto,
2221	const int histoMem,
2222	const int pass,
2223	bool &histoUsed)
2224	{
2225	ViewCellContainer viewCells;
2226	vector<BvhNode *> bvhNodes;
2227
2228	// collect best set of view cells for this #splits
2229	CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
2230	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
2231
2232	// set new nodes to be active
2233	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
2234	{
2235	mBvHierarchy->SetActive(*bit);
2236	}
2237
2238	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2239
2240	pvsEntries = 0;
2241	renderCost = 0.0f;
2242
2243	ViewCell::NewMail();
2244
2245	//cout << "\nviewcells: " << viewCells.size() << endl;
2246	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2247	{
2248	ViewCell vc = vit;
2249
2250	#if STUPID_METHOD
2251	ObjectPvs pvs;
2252	GetPvsIncrementially(vc, pvs);
2253	vc->SetPvs(pvs);
2254
2255	#else
2256
2257	ObjectPvs pvs;
2258
2259	if (vc->GetPvs().Empty())
2260	{
2261	// warning: uses mailing, pvs not sorted!!
2262	GetPvsEfficiently(vc, pvs);
2263	//GetPvsRecursive(vc, pvs);
2264	vc->SetPvs(pvs);
2265	}
2266	#endif
2267
2268	vc->Mail();
2269
2270	float triangles = 0;
2271	int entries = 0;
2272
2273	if (useFilter)
2274	{
2275	const long startT = GetTime();
2276
2277	ObjectPvs filteredPvs;
2278	GetViewCellsManager()->ApplyFilter2(vc, false, 1.0f, filteredPvs);
2279
2280	const long endT = GetTime();
2281
2282	//cout << "filter computed in " << TimeDiff(startT, endT) * 1e-3f << " secs" << endl;
2283
2284	ComputePvs(filteredPvs, triangles, entries);
2285	}
2286	else
2287	{
2288	ComputePvs(vc->GetPvs(), triangles, entries);
2289	vc->SetTrianglesInPvs(triangles);
2290	}
2291
2292	const float rc = GetViewCellsManager()->ComputeRenderCost((int)triangles, entries) * vc->GetVolume();
2293
2294	renderCost += rc;
2295	pvsEntries += entries;
2296	}
2297
2298	renderCost /= GetViewCellsManager()->GetViewSpaceBox().GetVolume();
2299	memory = pvsEntries * ObjectPvs::GetEntrySize();
2300
2301	viewSpaceSplits = (int)viewCells.size();
2302	objectSpaceSplits = (int)bvhNodes.size();
2303
2304	////////////////////////
2305	//-- evaluate histogram for pvs size
2306
2307	if (useHisto && (memory <= (float)histoMem))
2308	{
2309	char str[100];
2310	char statsPrefix[100];
2311	//int histoStepSize;
2312
2313	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
2314
2315	cout << "computing pvs histogram for " << histoMem << " memory" << endl;
2316	Debug << "computing pvs histogram for " << histoMem << " memory" << endl;
2317
2318	sprintf(str, "-%05d-%05d-histo-pvs.log", pass, histoMem);
2319	const string filename = string(statsPrefix) + string(str);
2320
2321	GetViewCellsManager()->EvalViewCellHistogramForPvsSize(filename, viewCells);
2322
2323	histoUsed = true;
2324	}
2325
2326	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
2327
2328	// delete old "base" view cells if they are not leaves
2329	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2330
2331	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2332	{
2333	if (!(oit)->Mailed() && !(oit)->IsLeaf())
2334	{
2335	(*oit)->GetPvs().Clear();
2336	}
2337	}
2338
2339	// store current level
2340	mOldViewCells = viewCells;
2341
2342	return (int)(viewCells.size() + bvhNodes.size());
2343	}
2344
2345
2346
2347	void HierarchyManager::EvaluateSubdivision(ofstream &splitsStats,
2348	const int splitsStepSize,
2349	const bool useFilter,
2350	const bool useHisto,
2351	const int histoMem,
2352	const int pass)
2353	{
2354	vector<HierarchySubdivisionStats> subStatsContainer;
2355
2356	int splits = (1 + (mHierarchyStats.Leaves() - 1) / splitsStepSize) * splitsStepSize;
2357	cout << "splits: " << splits << endl;
2358
2359	bool histoUsed = false;
2360
2361	while (1)
2362	{
2363	HierarchySubdivisionStats subStats;
2364	subStats.mNumSplits = ExtractStatistics(splits,
2365	99999.0,
2366	subStats.mTotalRenderCost,
2367	subStats.mMemoryCost,
2368	subStats.mEntriesInPvs,
2369	subStats.mViewSpaceSplits,
2370	subStats.mObjectSpaceSplits,
2371	useFilter,
2372	useHisto && !histoUsed,
2373	histoMem,
2374	pass,
2375	histoUsed);
2376
2377
2378	const float objectSpaceHierarchyMem = float(
2379	subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
2380	//+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
2381	//+sizeof(BvHierarchy)
2382	) / float(1024 * 1024);
2383
2384
2385	const float viewSpaceHierarchyMem = float(
2386	subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
2387	//+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
2388	+ sizeof(ObjectPvs)
2389	//+ sizeof(VspTree)
2390	) / float(1024 * 1024);
2391
2392	subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
2393
2394	subStatsContainer.push_back(subStats);
2395
2396	if (splits == 0)
2397	{
2398	break;
2399	}
2400	splits -= splitsStepSize;
2401
2402	cout << "splits: " << subStats.mNumSplits << " ";
2403	}
2404
2405	vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();
2406
2407	for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
2408	{
2409	(*hit).Print(splitsStats);
2410	}
2411
2412	// delete old "base" view cells: only pvss in the leaves are allowed
2413	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2414
2415	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2416	{
2417	if (!(*oit)->IsLeaf())
2418	{
2419	(*oit)->GetPvs().Clear();
2420	}
2421	}
2422
2423	mOldViewCells.clear();
2424
2425	// reset active nodes
2426	vector<BvhLeaf *> bvhLeaves;
2427
2428	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);
2429
2430	vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();
2431
2432	for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
2433	{
2434	(bit)->SetActiveNode(bit);
2435	}
2436
2437	cout << endl;
2438	}
2439
2440
2441	void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2442	{
2443	mBvHierarchy->CollectObjects(box, objects);
2444	}
2445
2446
2447	int HierarchyManager::CompressObjectSpace()
2448	{
2449	//mBvHierarchy->Compress();
2450	return mVspTree->CompressObjects();
2451	}
2452
2453
2454	void HierarchyManager::CreateUniqueObjectIds()
2455	{
2456	mBvHierarchy->CreateUniqueObjectIds();
2457	}
2458
2459
2460	void HierarchyManager::CreateTraversalTree()
2461	{
2462	int mind, maxd;
2463	mVspTree->EvalMinMaxDepth(mind, maxd);
2464
2465	cout << "old tree balance: " << mind << " " << maxd << endl;
2466	mTraversalTree = new TraversalTree;
2467
2468	ViewCellContainer viewCells;
2469	mVspTree->CollectViewCells(viewCells, false);
2470
2471	const long startTime = GetTime();
2472
2473	cout << "building traversal tree ... " << endl;
2474
2475	mTraversalTree->Construct(viewCells);
2476
2477	cout << "finished traversal tree construction in " << TimeDiff(startTime, GetTime()) * 1e-3
2478	<< " secs " << endl;
2479
2480	Debug << "* TraversalTree Stats *" << endl;
2481	Debug << mTraversalTree->GetStatistics() << endl;
2482
2483	if (1)
2484	{
2485	Exporter *exporter = Exporter::GetExporter("traversal.wrl");
2486	exporter->ExportTraversalTree(*mTraversalTree, true);
2487	delete exporter;
2488	}
2489	}
2490
2491
2492	int HierarchyManager::CastLineSegment(const Vector3 &origin,
2493	const Vector3 &termination,
2494	ViewCellContainer &viewcells,
2495	const bool useMailboxing)
2496	{
2497	if (!mTraversalTree)
2498	{
2499	return mVspTree->CastLineSegment(origin, termination, viewcells, useMailboxing);
2500	}
2501	else
2502	{
2503	return mTraversalTree->CastLineSegment(origin, termination, viewcells, useMailboxing);
2504	}
2505	}
2506
2507
2508	ViewCellsManager *HierarchyManager::GetViewCellsManager()
2509	{
2510	return mVspTree->mViewCellsManager;
2511	}
2512
2513
2514	int HierarchyManager::CastLineSegment(RayPacket &packet)
2515	{
2516	return mVspTree->TraverseRayPacket(packet, true);
2517	}
2518
2519
2520	}

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

Download in other formats: