Context Navigation

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

Revision 2237, 72.3 KB checked in by mattausch, 17 years ago (diff)
worked on optimization. warning: not tested yet

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

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

Download in other formats: