Context Navigation

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

Revision 1789, 63.9 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: