Context Navigation

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

Revision 1911, 65.8 KB checked in by mattausch, 17 years ago (diff)
added support for pvs correction (warning: does not yet compile)

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

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

Download in other formats: