Context Navigation

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

Revision 1919, 67.2 KB checked in by mattausch, 17 years ago (diff)
added mechanism for histogram on certain MB in hierarchymanager no more bug in undersampling estimation added sampling strategy to spatial box based (also for eval) added testing scripts

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

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

Download in other formats: