Context Navigation

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

Revision 1733, 58.3 KB checked in by mattausch, 18 years ago (diff)
removed bug from dirtycandidates

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

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

Download in other formats: