Context Navigation

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

Revision 1707, 57.9 KB checked in by mattausch, 18 years ago (diff)
worked on full render cost evaluation warning: some change sin render cost evaluation for pvs which could have bugs

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

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

Download in other formats: