Context Navigation

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

Revision 1750, 61.3 KB checked in by mattausch, 18 years ago (diff)
improved evaluation speed

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

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

Download in other formats: