Context Navigation

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

Revision 2227, 72.0 KB checked in by mattausch, 17 years ago (diff)
added render cost bound for objects, improved undersampling compensation

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

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

Download in other formats: