Context Navigation

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

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

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

Download in other formats: