Context Navigation

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

Revision 2228, 72.4 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: