Context Navigation

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

Revision 1912, 65.9 KB checked in by mattausch, 17 years ago (diff)

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	return childPvs;
746
747	// assume pvs not sampled sufficiently => take total pvs
748	if (avgRayContri > mMaxAvgRayContri)
749	return totalPvs;
750
751	const float alpha = (mMaxAvgRayContri - avgRayContri) /
752	(mMaxAvgRayContri - mMinAvgRayContri);
753
754	cout << "here41 **************** " << alpha << " " << childPvs << " " << totalPvs << endl;
755
756	const float beta = (1.0f - alpha) * (totalPvs + childPvs) / totalPvs;
757
758	return childPvs + beta;
759	}
760
761
762	bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
763	SplitQueue &splitQueue,
764	const bool repairQueue)
765	{
766	const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
767	const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
768
769	if (sc->IsDirty())
770	cerr << "Error: Should never come here!" << endl;
771
772	if (!success) // split was not taken
773	{
774	cout << "x";
775	return false;
776	}
777
778	//cout << "priority: " << sc->GetPriority() << " rc decr: " << sc->GetRenderCostDecrease() << " \| ";
779	///////////////
780	//-- split was successful => update stats and queue
781
782	// cost ratio of cost decrease / totalCost
783	const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
784	//cout << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
785
786	if (costRatio < mTermMinGlobalCostRatio)
787	{
788	++ mHierarchyStats.mGlobalCostMisses;
789	}
790
791	cout << sc->Type() << " ";
792
793	/////////////
794	// update stats
795
796	mHierarchyStats.mNodes += 2;
797	mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
798
799	const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
800	mHierarchyStats.mPvsEntries += pvsEntriesIncr;
801	//cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
802
803	// memory size in byte
804	float mem = (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
805
806	// high avg ray contri, the result is influenced by undersampling
807	// => decrease priority
808	if (0 && USE_AVGRAYCONTRI && (sc->GetAvgRayContribution() > mMaxAvgRayContri))
809	{
810	const float factor = 1.0f + sc->GetAvgRayContribution() - mMaxAvgRayContri;
811	cout << "h " << factor << endl;
812
813	mem *= factor;
814	}
815
816	mHierarchyStats.mMemory += mem;
817	mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
818
819	mPriority = sc->GetPriority();
820
821	//////////
822	// show current memory
823
824	static float memoryCount = 0;
825
826	if (mHierarchyStats.mMemory > memoryCount)
827	{
828	memoryCount += 100000;
829	cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
830	<< " MB, steps: " << mHierarchyStats.Leaves() << endl;
831	}
832
833	// output stats
834	EvalSubdivisionStats();
835
836	if (repairQueue)
837	{
838	// reevaluate candidates affected by the split for view space splits,
839	// this would be object space splits and other way round
840	vector<SubdivisionCandidate *> dirtyList;
841	sc->CollectDirtyCandidates(dirtyList, false);
842
843	RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
844	}
845
846	return true;
847	}
848
849
850	int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
851	{
852	int maxDepth = 0;
853
854	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
855	{
856	maxDepth = mOspTree->mOspStats.maxDepth;
857	}
858	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
859	{
860	maxDepth = mBvHierarchy->mBvhStats.maxDepth;
861	}
862
863	return maxDepth;
864	}
865
866
867	int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
868	{
869	int maxLeaves= 0;
870
871	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
872	{
873	maxLeaves = mOspTree->mOspStats.Leaves();
874	}
875	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
876	{
877	maxLeaves = mBvHierarchy->mBvhStats.Leaves();
878	}
879
880	return maxLeaves;
881	}
882
883
884	int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
885	{
886	int maxLeaves = 0;
887
888	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
889	{
890	maxLeaves = mOspTree->mOspStats.nodes;
891	}
892	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
893	{
894	maxLeaves = mBvHierarchy->mBvhStats.nodes;
895	}
896
897	return maxLeaves;
898	}
899
900	bool HierarchyManager::StartObjectSpaceSubdivision() const
901	{
902	// view space construction already started
903	if (ObjectSpaceSubdivisionConstructed())
904	return false;
905
906	// start immediately with object space subdivision?
907	if (mStartWithObjectSpace)
908	return true;
909
910	// is the queue empty again?
911	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
912	return true;
913
914	// has the depth for subdivision been reached?
915	return
916	((mConstructionType == INTERLEAVED) &&
917	(mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
918	}
919
920
921	bool HierarchyManager::StartViewSpaceSubdivision() const
922	{
923	// view space construction already started
924	if (ViewSpaceSubdivisionConstructed())
925	return false;
926
927	// start immediately with view space subdivision?
928	if (!mStartWithObjectSpace)
929	return true;
930
931	// is the queue empty again?
932	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
933	return true;
934
935	// has the depth for subdivision been reached?
936	return
937	((mConstructionType == INTERLEAVED) &&
938	(mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
939	}
940
941
942	void HierarchyManager::RunConstruction(const bool repairQueue,
943	const VssRayContainer &sampleRays,
944	const ObjectContainer &objects,
945	AxisAlignedBox3 *forcedViewSpace)
946	{
947	while (!FinishedConstruction())
948	{
949	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
950
951	///////////////////
952	//-- subdivide leaf node
953
954	ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
955
956	// we use objects for evaluating vsp tree construction until
957	// a certain depth once a certain depth existiert ...
958	if (StartObjectSpaceSubdivision())
959	{
960	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
961
962	cout << "\nstarting object space subdivision after "
963	<< mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") steps, mem="
964	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
965
966	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
967
968	cout << "reseting queue ... ";
969	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
970	cout << "finished" << endl;
971	}
972
973	if (StartViewSpaceSubdivision())
974	{
975	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
976
977	cout << "\nstarting view space subdivision at "
978	<< GetObjectSpaceSubdivisionLeaves() << " ("
979	<< mMinStepsOfSameType << ") , mem="
980	<< mHierarchyStats.mMemory / float(1024 * 1024) << " MB" << endl;
981
982	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
983
984	cout << "reseting queue ... ";
985	ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
986	cout << "finished" << endl;
987	}
988
989	DEL_PTR(sc);
990	}
991	}
992
993
994	void HierarchyManager::RunConstruction(const bool repairQueue)
995	{
996	// main loop
997	while (!FinishedConstruction())
998	{
999	SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
1000
1001	////////
1002	//-- subdivide leaf node of either type
1003
1004	ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
1005
1006	DEL_PTR(sc);
1007	}
1008	}
1009
1010
1011	int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
1012	SubdivisionCandidateContainer &dirtyCandidates,
1013	SubdivisionCandidate *oldCandidate,
1014	const int minSteps,
1015	const int maxSteps)
1016	{
1017	if (minSteps >= maxSteps)
1018	cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
1019
1020	int steps = 0;
1021	SubdivisionCandidate::NewMail();
1022
1023	// main loop
1024	while (!splitQueue.Empty())
1025	{
1026	const float priority = splitQueue.Top()->GetPriority();
1027	const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
1028
1029	// minimum slope reached
1030	if ((steps >= maxSteps) \|\| ((priority < threshold) && !(steps < minSteps)))
1031	{
1032	cout << "\nbreaking on " << priority << " smaller than " << threshold << endl;
1033	break;
1034	}
1035
1036	////////
1037	//-- subdivide leaf node of either type
1038
1039	SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
1040
1041	const bool repairQueue = false;
1042	const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
1043
1044	if (success)
1045	{
1046	sc->CollectDirtyCandidates(dirtyCandidates, true);
1047	++ steps;
1048	}
1049
1050	DEL_PTR(sc);
1051	}
1052
1053	return steps;
1054	}
1055
1056
1057	void HierarchyManager::ResetObjectSpaceSubdivision(SplitQueue &tQueue,
1058	const VssRayContainer &sampleRays,
1059	const ObjectContainer &objects)
1060	{
1061	SubdivisionCandidate *firstCandidate;
1062
1063	// object space partition constructed => reconstruct
1064	switch (mObjectSpaceSubdivisionType)
1065	{
1066	case BV_BASED_OBJ_SUBDIV:
1067	{
1068	cout << "\nreseting bv hierarchy" << endl;
1069	Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
1070
1071	// rather use this: remove previous nodes and add the two new ones
1072	//mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
1073	mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
1074
1075	// create root
1076	mBvHierarchy->Initialise(objects);
1077
1078	mBvHierarchy->Reset(tQueue, sampleRays, objects);
1079
1080	mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
1081
1082	//mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
1083	mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
1084
1085	mHierarchyStats.mMemory =
1086	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1087
1088	mHierarchyStats.mRenderCostDecrease = 0;
1089
1090	// evaluate stats before first subdivision
1091	EvalSubdivisionStats();
1092	cout << "finished bv hierarchy preparation" << endl;
1093	}
1094	break;
1095
1096	case KD_BASED_OBJ_SUBDIV:
1097	// TODO
1098	default:
1099	break;
1100	}
1101	}
1102
1103
1104	void HierarchyManager::ResetViewSpaceSubdivision(SplitQueue &tQueue,
1105	const VssRayContainer &sampleRays,
1106	const ObjectContainer &objects,
1107	AxisAlignedBox3 *forcedViewSpace)
1108	{
1109	ViewCellsManager *vm = mVspTree->mViewCellsManager;
1110
1111	// HACK: rather not destroy vsp tree
1112	DEL_PTR(mVspTree);
1113	mVspTree = new VspTree();
1114
1115	mVspTree->mHierarchyManager = this;
1116	mVspTree->mViewCellsManager = vm;
1117
1118	mVspTree->Initialise(sampleRays, forcedViewSpace);
1119
1120	//////////
1121	//-- reset stats
1122	mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();
1123	//-mVspTree->mVspStats.nodes + 1;
1124
1125	PrepareViewSpaceSubdivision(mTQueue, sampleRays, objects);
1126
1127	mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
1128	mHierarchyStats.mRenderCostDecrease = 0;
1129
1130	mHierarchyStats.mMemory =
1131	(float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
1132
1133	// evaluate new stats before first subdivsiion
1134	EvalSubdivisionStats();
1135	}
1136
1137
1138	void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,
1139	const ObjectContainer &objects,
1140	AxisAlignedBox3 *forcedViewSpace)
1141	{
1142	mHierarchyStats.Reset();
1143	mHierarchyStats.Start();
1144	mHierarchyStats.mNodes = 2;
1145
1146	mHierarchyStats.mTotalCost = (float)objects.size();
1147	Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
1148
1149	const long startTime = GetTime();
1150	cout << "Constructing view space / object space tree ... \n";
1151
1152	// initialise view / object space
1153	mVspTree->Initialise(sampleRays, forcedViewSpace);
1154	InitialiseObjectSpaceSubdivision(objects);
1155
1156	// use sah for evaluating osp tree construction
1157	// in the first iteration of the subdivision
1158
1159	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
1160	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
1161
1162	PrepareObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1163
1164	//////////////////////////
1165
1166
1167	const int limit = mNumMultiLevels;
1168	int i = 0;
1169
1170	// This method subdivides view space / object space
1171	// in order to converge to some optimal cost for this partition
1172	// start with object space partiton
1173	// then optimizate view space partition for the current osp
1174	// and vice versa until iteration depth is reached.
1175	while (1)
1176	{
1177	char subdivisionStatsLog[100];
1178	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1179	mSubdivisionStats.open(subdivisionStatsLog);
1180
1181	// subdivide object space first
1182	ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1183
1184	// process object space candidates
1185	RunConstruction(false);
1186
1187	// object space subdivision constructed
1188	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
1189
1190	cout << "iteration " << i << " of " << limit << " finished" << endl;
1191	mSubdivisionStats.close();
1192
1193	if ((i ++) >= limit)
1194	break;
1195
1196	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
1197	mSubdivisionStats.open(subdivisionStatsLog);
1198
1199
1200	/////////////////
1201	// subdivide view space with respect to the objects
1202
1203	ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
1204
1205	// view space subdivision constructed
1206	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
1207
1208	// process view space candidates
1209	RunConstruction(false);
1210
1211	cout << "iteration " << i << " of " << limit << " finished" << endl;
1212	mSubdivisionStats.close();
1213
1214	if ((i ++) >= limit)
1215	break;
1216	}
1217
1218	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1219
1220	mHierarchyStats.Stop();
1221	mVspTree->mVspStats.Stop();
1222	FinishObjectSpaceSubdivision(objects);
1223	}
1224
1225
1226	void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,
1227	const ObjectContainer &objects,
1228	AxisAlignedBox3 *forcedViewSpace)
1229	{
1230	const long startTime = GetTime();
1231	const int limit = mNumMultiLevels;
1232
1233	// open up new subdivision
1234	mSubdivisionStats.close();
1235
1236	int steps = 0;
1237
1238	int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
1239	int maxObjectSpaceLeaves;
1240
1241	// set the number of leaves 'evaluated' from the previous methods
1242	// we go for the same numbers, but we try to optimize both subdivisions
1243	switch (mObjectSpaceSubdivisionType)
1244	{
1245	case BV_BASED_OBJ_SUBDIV:
1246	maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
1247	break;
1248	case KD_BASED_OBJ_SUBDIV:
1249	maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
1250	default:
1251	maxObjectSpaceLeaves = 0;
1252	break;
1253	}
1254
1255	// This method subdivides view space / object space
1256	// in order to converge to some optimal cost for this partition
1257	// start with object space partiton
1258	// then optimizate view space partition for the current osp
1259	// and vice versa until iteration depth is reached.
1260	while (1)
1261	{
1262	char subdivisionStatsLog[100];
1263	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1264	mSubdivisionStats.open(subdivisionStatsLog);
1265
1266	// subdivide object space first
1267	ResetObjectSpaceSubdivision(mTQueue, sampleRays, objects);
1268
1269	// set the number of leaves 'evaluated' from the previous methods
1270	// we go for the same numbers, but we try to optimize both subdivisions
1271	mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
1272
1273	// process object space candidates
1274	RunConstruction(false);
1275
1276	cout << "iteration " << steps << " of " << limit << " finished" << endl;
1277	mSubdivisionStats.close();
1278
1279	if ((++ steps) >= limit)
1280	break;
1281
1282	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
1283	mSubdivisionStats.open(subdivisionStatsLog);
1284
1285	/////////////////
1286	// subdivide view space with respect to the objects
1287
1288	ResetViewSpaceSubdivision(mTQueue, sampleRays, objects, forcedViewSpace);
1289
1290	mVspTree->mMaxViewCells = maxViewSpaceLeaves;
1291
1292	// process view space candidates
1293	RunConstruction(false);
1294
1295	cout << "iteration " << steps << " of " << limit << " finished" << endl;
1296	mSubdivisionStats.close();
1297
1298	if ((++ steps) >= limit)
1299	break;
1300	}
1301
1302	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1303
1304	mHierarchyStats.Stop();
1305	mVspTree->mVspStats.Stop();
1306	FinishObjectSpaceSubdivision(objects);
1307	}
1308
1309
1310
1311	bool HierarchyManager::FinishedConstruction() const
1312	{
1313	return mTQueue.Empty();
1314	}
1315
1316
1317	bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
1318	{
1319	/*switch (mObjectSpaceSubdivisionType)
1320	{
1321	case KD_BASED_OBJ_SUBDIV:
1322	return mOspTree && mOspTree->GetRoot();
1323	case BV_BASED_OBJ_SUBDIV:
1324	return mBvHierarchy && mBvHierarchy->GetRoot();
1325	default:
1326	return false;
1327	}*/
1328	return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
1329	}
1330
1331
1332	bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
1333	{
1334	return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
1335	//return mVspTree && mVspTree->GetRoot();
1336	}
1337
1338
1339	void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
1340	SubdivisionCandidateContainer &dirtyList)
1341	{
1342	SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
1343	SubdivisionCandidate::NewMail();
1344
1345	for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
1346	{
1347	(*sit)->CollectDirtyCandidates(dirtyList, true);
1348	}
1349	}
1350
1351
1352	int HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
1353	SplitQueue &splitQueue,
1354	const bool recomputeSplitPlaneOnRepair)
1355	{
1356	// for each update of the view space partition:
1357	// the candidates from object space partition which
1358	// have been afected by the view space split (the kd split candidates
1359	// which saw the view cell which was split) must be reevaluated
1360	// (maybe not locally, just reinsert them into the queue)
1361	//
1362	// vice versa for the view cells
1363	// for each update of the object space partition
1364	// reevaluate split candidate for view cells which saw the split kd cell
1365	//
1366	// the priority queue update can be solved by implementing a binary heap
1367	// (explicit data structure, binary tree)
1368	// *) inserting and removal is efficient
1369	// *) search is not efficient => store queue position with each
1370	// split candidate
1371
1372	int repaired = 0;
1373
1374	// collect list of "dirty" candidates
1375	const long startTime = GetTime();
1376	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
1377
1378	const float prop = (float)mMaxRepairs / (float)dirtyList.size();
1379
1380	///////////////////////////
1381	//-- reevaluate the dirty list
1382
1383	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
1384
1385	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
1386	{
1387	// only repair a certain number of candidates
1388	if ((mMaxRepairs < (int)dirtyList.size()) && (Random(1.0f) >= prop))
1389	continue;
1390
1391	SubdivisionCandidate* sc = *sit;
1392	const float rcd = sc->GetRenderCostDecrease();
1393
1394	// erase from queue
1395	splitQueue.Erase(sc);
1396	// reevaluate candidate
1397	sc->EvalCandidate(recomputeSplitPlaneOnRepair);
1398	// reinsert
1399	splitQueue.Push(sc);
1400
1401	++ repaired;
1402	cout << ".";
1403
1404	#ifdef GTP_DEBUG
1405	Debug << "candidate " << sc << " reevaluated\n"
1406	<< "render cost decrease diff " << rcd - sc->GetRenderCostDecrease()
1407	<< " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
1408	#endif
1409	}
1410
1411	const long endTime = GetTime();
1412	const Real timeDiff = TimeDiff(startTime, endTime);
1413
1414	mHierarchyStats.mRepairTime += timeDiff;
1415
1416	return repaired;
1417	}
1418
1419
1420	void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
1421	{
1422	SubdivisionCandidateContainer mCandidateBuffer;
1423
1424	// remove from queue
1425	while (!splitQueue.Empty())
1426	{
1427	SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
1428
1429	// reevaluate local split plane and priority
1430	candidate->EvalCandidate(recomputeSplitPlane);
1431	cout << ".";
1432	mCandidateBuffer.push_back(candidate);
1433	}
1434
1435	// put back into queue
1436	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
1437	for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
1438	{
1439	splitQueue.Push(*sit);
1440	}
1441	}
1442
1443
1444	void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
1445	{
1446	// the type of the view cells hierarchy
1447	switch (mObjectSpaceSubdivisionType)
1448	{
1449	case KD_BASED_OBJ_SUBDIV:
1450	stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
1451	mOspTree->Export(stream);
1452	stream << endl << "</ObjectSpaceHierarchy>" << endl;
1453	break;
1454	case BV_BASED_OBJ_SUBDIV:
1455	stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
1456	mBvHierarchy->Export(stream);
1457	stream << endl << "</ObjectSpaceHierarchy>" << endl;
1458	break;
1459	}
1460	}
1461
1462
1463	void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
1464	{
1465	stream << mHierarchyStats << endl;
1466	stream << "\nview space:" << endl << endl;
1467	stream << mVspTree->GetStatistics() << endl;
1468	stream << "\nobject space:" << endl << endl;
1469
1470	switch (mObjectSpaceSubdivisionType)
1471	{
1472	case KD_BASED_OBJ_SUBDIV:
1473	{
1474	stream << mOspTree->GetStatistics() << endl;
1475	break;
1476	}
1477	case BV_BASED_OBJ_SUBDIV:
1478	{
1479	stream << mBvHierarchy->GetStatistics() << endl;
1480	break;
1481	}
1482	default:
1483	break;
1484	}
1485	}
1486
1487
1488	void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
1489	const ObjectContainer &objects,
1490	AxisAlignedBox3 *bbox,
1491	const bool exportBounds) const
1492	{
1493	switch (mObjectSpaceSubdivisionType)
1494	{
1495	case KD_BASED_OBJ_SUBDIV:
1496	{
1497	ExportOspTree(exporter, objects);
1498	break;
1499	}
1500	case BV_BASED_OBJ_SUBDIV:
1501	{
1502	exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
1503	break;
1504	}
1505	default:
1506	break;
1507	}
1508	}
1509
1510
1511	void HierarchyManager::ExportOspTree(Exporter *exporter,
1512	const ObjectContainer &objects) const
1513	{
1514	if (0) exporter->ExportGeometry(objects);
1515
1516	exporter->SetWireframe();
1517	exporter->ExportOspTree(*mOspTree, 0);
1518	}
1519
1520
1521	Intersectable HierarchyManager::GetIntersectable(Intersectable obj,
1522	const Vector3 &point) const
1523	{
1524
1525	if (!obj)
1526	return NULL;
1527
1528	switch (mObjectSpaceSubdivisionType)
1529	{
1530	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1531	{
1532	KdLeaf *leaf = mOspTree->GetLeaf(point, NULL);
1533	return mOspTree->GetOrCreateKdIntersectable(leaf);
1534	}
1535	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1536	{
1537	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1538	return leaf;
1539	}
1540	default:
1541	return obj;
1542	}
1543	}
1544
1545	Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1546	const bool isTermination) const
1547	{
1548	Intersectable *obj = NULL;
1549	Vector3 pt;
1550	KdNode *node;
1551
1552	ray.GetSampleData(isTermination, pt, &obj, &node);
1553
1554	if (!obj)
1555	return NULL;
1556
1557	switch (mObjectSpaceSubdivisionType)
1558	{
1559	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1560	{
1561	KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1562	return mOspTree->GetOrCreateKdIntersectable(leaf);
1563	}
1564	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1565	{
1566	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1567	return leaf;
1568	}
1569	default:
1570	break;
1571	}
1572
1573	return obj;
1574	}
1575
1576
1577	void HierarchyStatistics::Print(ostream &app) const
1578	{
1579	app << "=========== Hierarchy statistics ===============\n";
1580
1581	app << setprecision(4);
1582
1583	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
1584
1585	app << "#N_RTIME ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1586
1587	app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1588
1589	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1590
1591	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1592
1593	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1594
1595	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1596
1597	app << "========== END OF Hierarchy statistics ==========\n";
1598	}
1599
1600
1601	static void RemoveRayRefs(const ObjectContainer &objects)
1602	{
1603	ObjectContainer::const_iterator oit, oit_end = objects.end();
1604	for (oit = objects.begin(); oit != oit_end; ++ oit)
1605	{
1606	(*oit)->DelRayRefs();
1607	}
1608	}
1609
1610
1611	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1612	const bool removeRayRefs) const
1613	{
1614	switch (mObjectSpaceSubdivisionType)
1615	{
1616	case KD_BASED_OBJ_SUBDIV:
1617	{
1618	mOspTree->mOspStats.Stop();
1619	break;
1620	}
1621	case BV_BASED_OBJ_SUBDIV:
1622	{
1623	mBvHierarchy->mBvhStats.Stop();
1624	if (removeRayRefs)
1625	RemoveRayRefs(objects);
1626	break;
1627	}
1628	default:
1629	break;
1630	}
1631	}
1632
1633
1634	void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1635	{
1636	stream << "<BoundingBoxes>" << endl;
1637
1638	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1639	{
1640	KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1641
1642	int id = 0;
1643	for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1644	{
1645	Intersectable obj = (kit).second;
1646	const AxisAlignedBox3 box = obj->GetBox();
1647
1648	obj->SetId(id);
1649
1650	stream << "<BoundingBox" << " id=\"" << id << "\""
1651	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1652	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1653	}
1654	}
1655	else
1656	{
1657	ObjectContainer::const_iterator oit, oit_end = objects.end();
1658
1659	for (oit = objects.begin(); oit != oit_end; ++ oit)
1660	{
1661	const AxisAlignedBox3 box = (*oit)->GetBox();
1662
1663	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1664	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1665	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1666	}
1667	}
1668
1669	stream << "</BoundingBoxes>" << endl;
1670	}
1671
1672
1673	class HierarchyNodeWrapper;
1674
1675
1676	template <typename T> class myless
1677	{
1678	public:
1679	bool operator() (T v1, T v2) const
1680	{
1681	return (v1->GetMergeCost() < v2->GetMergeCost());
1682	}
1683	};
1684
1685
1686	typedef priority_queue<HierarchyNodeWrapper , vector<HierarchyNodeWrapper >,
1687	myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
1688
1689	class HierarchyNodeWrapper
1690	{
1691	public:
1692	enum {VSP_NODE, BVH_NODE, VIEW_CELL};
1693
1694	virtual float GetMergeCost() const = 0;
1695	virtual int Type() const = 0;
1696	virtual bool IsLeaf() const = 0;
1697
1698	virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
1699	};
1700
1701
1702	class VspNodeWrapper: public HierarchyNodeWrapper
1703	{
1704	public:
1705	VspNodeWrapper(VspNode *node): mNode(node) {}
1706
1707	int Type() const { return VSP_NODE; }
1708
1709	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
1710
1711	bool IsLeaf() const { return mNode->IsLeaf(); }
1712
1713	void PushChildren(HierarchyNodeQueue &tQueue)
1714	{
1715	if (!mNode->IsLeaf())
1716	{
1717	VspInterior interior = dynamic_cast<VspInterior >(mNode);
1718
1719	tQueue.push(new VspNodeWrapper(interior->GetFront()));
1720	tQueue.push(new VspNodeWrapper(interior->GetBack()));
1721	}
1722	}
1723
1724	VspNode *mNode;
1725	};
1726
1727
1728	class BvhNodeWrapper: public HierarchyNodeWrapper
1729	{
1730	public:
1731	BvhNodeWrapper(BvhNode *node): mNode(node) {}
1732
1733	int Type() const { return BVH_NODE; }
1734
1735	float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };
1736
1737	bool IsLeaf() const { return mNode->IsLeaf(); }
1738
1739	void PushChildren(HierarchyNodeQueue &tQueue)
1740	{
1741	if (!mNode->IsLeaf())
1742	{
1743	BvhInterior interior = dynamic_cast<BvhInterior >(mNode);
1744
1745	tQueue.push(new BvhNodeWrapper(interior->GetFront()));
1746	tQueue.push(new BvhNodeWrapper(interior->GetBack()));
1747	}
1748	}
1749
1750	BvhNode *mNode;
1751	};
1752
1753
1754	class ViewCellWrapper: public HierarchyNodeWrapper
1755	{
1756	public:
1757
1758	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
1759
1760	int Type() const { return VIEW_CELL; }
1761
1762	float GetMergeCost() const { return mViewCell->GetMergeCost(); };
1763
1764	bool IsLeaf() const { return mViewCell->IsLeaf(); }
1765
1766	void PushChildren(HierarchyNodeQueue &tQueue)
1767	{
1768	if (!mViewCell->IsLeaf())
1769	{
1770	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(mViewCell);
1771
1772	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1773
1774	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1775	{
1776	tQueue.push(new ViewCellWrapper(*it));
1777	}
1778	}
1779	}
1780
1781	ViewCell *mViewCell;
1782	};
1783
1784
1785	void HierarchyManager::CollectBestSet(const int maxSplits,
1786	const float maxMemoryCost,
1787	ViewCellContainer &viewCells,
1788	vector<BvhNode *> &bvhNodes)
1789	{
1790	HierarchyNodeQueue tqueue;
1791	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
1792	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
1793	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
1794
1795	float memCost = 0;
1796
1797	while (!tqueue.empty())
1798	{
1799	HierarchyNodeWrapper *nodeWrapper = tqueue.top();
1800	tqueue.pop();
1801	//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
1802	// save the view cells if it is a leaf or if enough view cells have already been traversed
1803	// because of the priority queue, this will be the optimal set of v
1804	if (nodeWrapper->IsLeaf() \|\|
1805	((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) \|\|
1806	(memCost > maxMemoryCost)
1807	)
1808	{
1809	if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
1810	{
1811	//cout << "1";
1812	ViewCellWrapper viewCellWrapper = dynamic_cast<ViewCellWrapper >(nodeWrapper);
1813	viewCells.push_back(viewCellWrapper->mViewCell);
1814	}
1815	else
1816	{
1817	//cout << "0";
1818	BvhNodeWrapper bvhNodeWrapper = dynamic_cast<BvhNodeWrapper >(nodeWrapper);
1819	bvhNodes.push_back(bvhNodeWrapper->mNode);
1820	}
1821	}
1822	else
1823	{
1824	nodeWrapper->PushChildren(tqueue);
1825	}
1826
1827	delete nodeWrapper;
1828	}
1829	}
1830
1831
1832	void HierarchyManager::ComputePvs(const ObjectPvs &pvs,
1833	float &rc,
1834	int &pvsEntries)
1835	{
1836	BvhNode::NewMail();
1837
1838	ObjectPvsIterator pit = pvs.GetIterator();
1839
1840	while (pit.HasMoreEntries())
1841	{
1842	const ObjectPvsEntry &entry = pit.Next();
1843
1844	if (entry.mObject->Type() != Intersectable::BVH_INTERSECTABLE)
1845	cout << "error " << entry.mObject->Type() << endl;
1846
1847	BvhNode intersect = dynamic_cast<BvhNode >(entry.mObject);
1848	BvhNode *activeNode;
1849
1850	// hack for choosing which node to account for
1851	if (intersect->IsLeaf())
1852	{
1853	activeNode =
1854	dynamic_cast<BvhLeaf *>(intersect)->GetActiveNode();
1855	}
1856	else
1857	{
1858	activeNode = intersect;
1859	}
1860
1861	if (!activeNode->Mailed())
1862	{
1863	activeNode->Mail();
1864
1865	#if STUPID_METHOD
1866
1867	ObjectContainer objects;
1868	activeNode->CollectObjects(objects);
1869	rc += mBvHierarchy->EvalAbsCost(objects);
1870	#else
1871	rc += mBvHierarchy->GetRenderCostIncrementially(activeNode);
1872	#endif
1873	++ pvsEntries;
1874	}
1875	}
1876	}
1877
1878
1879	void HierarchyManager::GetPvsEfficiently(ViewCell *viewCell, ObjectPvs &pvs) const
1880	{
1881	////////////////
1882	//-- pvs is not stored with the interiors => reconstruct
1883
1884	// add pvs from leaves
1885	stack<ViewCell *> tstack;
1886	tstack.push(viewCell);
1887
1888	Intersectable::NewMail();
1889
1890	while (!tstack.empty())
1891	{
1892	ViewCell *vc = tstack.top();
1893	tstack.pop();
1894
1895	// add newly found pvs to merged pvs: break here even for interior
1896	if (!vc->GetPvs().Empty())
1897	{
1898	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1899
1900	while (pit.HasMoreEntries())
1901	{
1902	const ObjectPvsEntry &entry = pit.Next();
1903
1904	Intersectable *object = entry.mObject;
1905	if (!object->Mailed())
1906	{
1907	object->Mail();
1908	pvs.AddSampleDirty(object, 1.0f);
1909	}
1910	}
1911	}
1912	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1913	{
1914	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1915	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1916
1917	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1918	{
1919	tstack.push(*it);
1920	}
1921	}
1922	}
1923	}
1924
1925
1926	// TODO matt: implement this function for different storing methods
1927	void HierarchyManager::GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const
1928	{
1929	////////////////
1930	//-- pvs is not stored with the interiors => reconstruct
1931
1932	// add pvs from leaves
1933	stack<ViewCell *> tstack;
1934	tstack.push(vc);
1935
1936	while (!tstack.empty())
1937	{
1938	vc = tstack.top();
1939	tstack.pop();
1940
1941	// add newly found pvs to merged pvs: break here even for interior
1942	if (!vc->GetPvs().Empty())
1943	{
1944	//if (vc->IsLeaf()) cout << " l " << pvs.GetSize();
1945	//else cout << " i " << pvs.GetSize();
1946	pvs.MergeInPlace(vc->GetPvs());
1947	}
1948	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1949	{
1950	//cout <<" t";
1951	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1952	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1953
1954	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1955	{
1956	tstack.push(*it);
1957	}
1958	}
1959	else cout <<"k";
1960	}
1961	}
1962
1963
1964	// TODO matt: implement this function for different storing methods
1965	void HierarchyManager::PullUpPvsIncrementally(ViewCell *viewCell) const
1966	{
1967	////////////////
1968	//-- pvs is not stored with the interiors => reconstruct
1969
1970	// early exit: pvs is already pulled up to this view cell
1971	if (!viewCell->GetPvs().Empty())
1972	return;
1973
1974	// add pvs from leaves
1975	stack<ViewCell *> tstack;
1976	tstack.push(viewCell);
1977
1978	ViewCell *vc = viewCell;
1979
1980	while (!tstack.empty())
1981	{
1982	vc = tstack.top();
1983	tstack.pop();
1984
1985	// add newly found pvs to merged pvs: break here even for interior
1986	if (!vc->GetPvs().Empty())
1987	{
1988	viewCell->GetPvs().MergeInPlace(vc->GetPvs());
1989	}
1990	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1991	{
1992	//cout <<" t";
1993	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1994	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1995
1996	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1997	{
1998	tstack.push(*it);
1999	}
2000	}
2001	}
2002	}
2003
2004
2005
2006	// TODO matt: implement this function for different storing methods
2007	void HierarchyManager::GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const
2008	{
2009	////////////////
2010	//-- pvs is not stored with the interiors => reconstruct
2011	if (vc->IsLeaf() \|\| !vc->GetPvs().Empty())
2012	{
2013	pvs = vc->GetPvs();
2014	}
2015	else
2016	{
2017	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2018	#if 0
2019	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2020	const int childPvsSize = (int)interior->mChildren.size();
2021	vector<ObjectPvs> childPvs;
2022	childPvs.resize((int)interior->mChildren.size());
2023
2024	int i = 0;
2025	for (it = interior->mChildren.begin(); it != it_end; ++ it, ++ i)
2026	{
2027	GetPvsRecursive(*it, childPvs[i]);
2028	pvs.MergeInPlace(childPvs[i]);
2029	}
2030	#else
2031
2032	ObjectPvs leftPvs, rightPvs;
2033
2034	GetPvsRecursive(interior->mChildren[0], leftPvs);
2035	GetPvsRecursive(interior->mChildren[1], rightPvs);
2036
2037	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2038	#endif
2039	}
2040	}
2041
2042
2043	int HierarchyManager::ExtractStatistics(const int maxSplits,
2044	const float maxMemoryCost,
2045	float &renderCost,
2046	float &memory,
2047	int &pvsEntries,
2048	int &viewSpaceSplits,
2049	int &objectSpaceSplits,
2050	const bool useFilter)
2051	{
2052	ViewCellContainer viewCells;
2053	vector<BvhNode *> bvhNodes;
2054
2055	// collect best set of view cells for this #splits
2056	CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
2057	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
2058
2059	// set new nodes to be active
2060	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
2061	{
2062	mBvHierarchy->SetActive(*bit);
2063	}
2064
2065	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2066
2067	pvsEntries = 0;
2068	renderCost = 0.0f;
2069
2070	ViewCell::NewMail();
2071
2072	//cout << "\nviewcells: " << viewCells.size() << endl;
2073	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2074	{
2075	ViewCell vc = vit;
2076	float rc = 0;
2077
2078	#if STUPID_METHOD
2079	ObjectPvs pvs;
2080	GetPvsIncrementially(vc, pvs);
2081	vc->SetPvs(pvs);
2082
2083	#else
2084
2085	ObjectPvs pvs;
2086
2087	if (vc->GetPvs().Empty())
2088	{
2089	// warning: uses mailing, pvs not sorted!!
2090	GetPvsEfficiently(vc, pvs);
2091	//GetPvsRecursive(vc, pvs);
2092	vc->SetPvs(pvs);
2093	//cout << "q";
2094	}
2095	//else cout << "t";
2096	#endif
2097
2098	vc->Mail();
2099
2100	if (useFilter)
2101	{
2102	const long startT = GetTime();
2103	ObjectPvs filteredPvs;
2104	mVspTree->mViewCellsManager->ApplyFilter2(vc, false, 1.0f, filteredPvs);
2105	const long endT = GetTime();
2106
2107	//cout << "filter computed in " << TimeDiff(startT, endT) * 1e-3f << " secs" << endl;
2108	ComputePvs(filteredPvs, rc, pvsEntries);
2109	}
2110	else
2111	{
2112	ComputePvs(vc->GetPvs(), rc, pvsEntries);
2113	}
2114
2115	rc *= vc->GetVolume();
2116	renderCost += rc;
2117	}
2118
2119	renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
2120	memory = pvsEntries * ObjectPvs::GetEntrySize();
2121
2122	viewSpaceSplits = (int)viewCells.size();
2123	objectSpaceSplits = (int)bvhNodes.size();
2124	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
2125
2126	// delete old "base" view cells if they are not leaves
2127	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2128
2129	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2130	{
2131	if (!(oit)->Mailed() && !(oit)->IsLeaf())
2132	{
2133	(*oit)->GetPvs().Clear();
2134	}
2135	}
2136
2137	// store current level
2138	mOldViewCells = viewCells;
2139
2140	return (int)(viewCells.size() + bvhNodes.size());
2141	}
2142
2143
2144	void HierarchyManager::ExportStats(ofstream &stats,
2145	SplitQueue &tQueue,
2146	const ObjectContainer &objects)
2147	{
2148	HierarchySubdivisionStats subStats;
2149	subStats.Reset();
2150
2151	/////////////
2152	//-- initial situation
2153
2154	subStats.mNumSplits = 0;
2155	subStats.mTotalRenderCost = (float)objects.size();
2156	subStats.mEntriesInPvs = 1;
2157	subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
2158	subStats.mFullMemory = subStats.mMemoryCost;
2159	subStats.mViewSpaceSplits = 0;
2160	subStats.mObjectSpaceSplits = 0;
2161	subStats.mRenderCostDecrease = 0;
2162	subStats.Print(stats);
2163
2164	cout << "exporting vsposp stats ... " << endl;
2165
2166	//-- go through tree in the order of render cost decrease
2167	//-- which is the same order as the view cells were merged
2168	//-- or the reverse order of subdivision for subdivision-only
2169	//-- view cell hierarchies.
2170
2171	while (!tQueue.Empty())
2172	{
2173	SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
2174	bool isLeaf;
2175	int timeStamp;
2176	float rcDecr;
2177	int entriesIncr;
2178
2179	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2180	{
2181	timeStamp = (int)-nextCandidate->GetPriority();
2182
2183	VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
2184	VspNode oldNode = (VspNode )nextCandidate->mEvaluationHack;
2185
2186	isLeaf = newNode->IsLeaf();
2187	//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2188	//entriesIncr = oldNode->mPvsEntriesIncr;
2189	}
2190	else
2191	{
2192	timeStamp = (int)-nextCandidate->GetPriority();
2193
2194	BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
2195	BvhNode oldNode = (BvhNode )nextCandidate->mEvaluationHack;
2196
2197	isLeaf = newNode->IsLeaf();
2198	//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2199	//entriesIncr = oldNode->mPvsEntriesIncr;
2200	}
2201
2202	if (!isLeaf)
2203	{
2204	subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
2205	//subStats.mEntriesInPvs += entriesIncr;
2206
2207	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2208	{
2209	++ subStats.mViewSpaceSplits;
2210	cout << "v";
2211	//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2212	}
2213	else
2214	{
2215	++ subStats.mObjectSpaceSplits;
2216	cout << "o";
2217	//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2218	}
2219
2220	++ subStats.mNumSplits;
2221
2222	if ((subStats.mNumSplits % 500) == 499)
2223	cout << subStats.mNumSplits << " steps taken" << endl;
2224
2225	subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
2226	subStats.mFullMemory = subStats.mMemoryCost;
2227
2228	subStats.Print(stats);
2229
2230	}
2231
2232	DEL_PTR(nextCandidate);
2233	}
2234
2235	stats.close();
2236	}
2237
2238
2239	void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
2240	const ObjectContainer &objects,
2241	const string &filename)
2242	{
2243	#if 0
2244	VspTree *oldVspTree = mVspTree;
2245	ViewCellsManager *vm = mVspTree->mViewCellsManager;
2246	BvHierarchy *oldHierarchy = mBvHierarchy;
2247
2248	mBvHierarchy = new BvHierarchy();
2249	mBvHierarchy->mHierarchyManager = this;
2250	mBvHierarchy->mViewCellsManager = vm;
2251
2252	mVspTree = new VspTree();
2253	mVspTree->mHierarchyManager = this;
2254	mVspTree->mViewCellsManager = vm;
2255
2256	// create first nodes
2257	mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
2258	InitialiseObjectSpaceSubdivision(objects);
2259
2260	const long startTime = GetTime();
2261	cout << "Constructing evaluation hierarchies ... \n";
2262
2263	ofstream stats;
2264	stats.open(filename.c_str());
2265	SplitQueue tQueue;
2266
2267	BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
2268	VspNode *oldVspRoot = oldVspTree->GetRoot();
2269
2270	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
2271
2272	SubdivisionCandidate firstVsp = mVspTree->PrepareConstruction(sampleRays, viewSpaceRays);
2273	tQueue.Push(firstVsp);
2274
2275	mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
2276
2277	firstVsp->mEvaluationHack = oldVspRoot;
2278	firstBvh->mEvaluationHack = oldBvhRoot;
2279
2280	firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
2281	firstBvh->SetPriority((float)-oldBvhRoot->GetTimeStamp());
2282
2283	ExportStats(stats, tQueue, objects);
2284
2285	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2286	RemoveRayRefs(objects);
2287
2288	// view cells needed only for evaluation
2289	ViewCellContainer viewCells;
2290	mVspTree->CollectViewCells(viewCells, false);
2291
2292	// helper trees can be destroyed
2293	DEL_PTR(mVspTree);
2294	DEL_PTR(mBvHierarchy);
2295
2296	CLEAR_CONTAINER(viewCells);
2297
2298	// reset hierarchies
2299	mVspTree = oldVspTree;
2300	mBvHierarchy = oldHierarchy;
2301
2302	// reinstall old bv refs
2303	vector<BvhLeaf *> leaves;
2304	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
2305	vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
2306
2307	for (bit = leaves.begin(); bit != bit_end; ++ bit)
2308	{
2309	mBvHierarchy->AssociateObjectsWithLeaf(*bit);
2310	}
2311	#endif
2312	}
2313
2314
2315	void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
2316	const int splitsStepSize,
2317	const bool useFilter)
2318	{
2319	vector<HierarchySubdivisionStats> subStatsContainer;
2320
2321	int splits = (1 + (mHierarchyStats.Leaves() - 1) / splitsStepSize) * splitsStepSize;
2322	cout << "splits: " << splits << endl;
2323
2324	while (1)
2325	{
2326	HierarchySubdivisionStats subStats;
2327	subStats.mNumSplits = ExtractStatistics(splits,
2328	99999.0,
2329	subStats.mTotalRenderCost,
2330	subStats.mMemoryCost,
2331	subStats.mEntriesInPvs,
2332	subStats.mViewSpaceSplits,
2333	subStats.mObjectSpaceSplits,
2334	useFilter);
2335
2336
2337	const float objectSpaceHierarchyMem = float(
2338	subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
2339	//+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
2340	//+sizeof(BvHierarchy)
2341	) / float(1024 * 1024);
2342
2343
2344	const float viewSpaceHierarchyMem = float(
2345	subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
2346	//+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
2347	+ sizeof(ObjectPvs)
2348	//+ sizeof(VspTree)
2349	) / float(1024 * 1024);
2350
2351	subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
2352
2353	subStatsContainer.push_back(subStats);
2354
2355	if (splits == 0)
2356	{
2357	break;
2358	}
2359	splits -= splitsStepSize;
2360
2361	cout << "splits: " << subStats.mNumSplits << " ";
2362	}
2363
2364	vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();
2365
2366	for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
2367	{
2368	(*hit).Print(splitsStats);
2369	}
2370
2371	// delete old "base" view cells: only pvss in the leaves are allowed
2372	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2373	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2374	{
2375	if (!(*oit)->IsLeaf())
2376	{
2377	(*oit)->GetPvs().Clear();
2378	}
2379	}
2380
2381	mOldViewCells.clear();
2382
2383	// reset active nodes
2384	vector<BvhLeaf *> bvhLeaves;
2385
2386	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);
2387
2388	vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();
2389
2390	for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
2391	{
2392	(bit)->SetActiveNode(bit);
2393	}
2394
2395	cout << endl;
2396	}
2397
2398
2399	void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2400	{
2401	mBvHierarchy->CollectObjects(box, objects);
2402	}
2403
2404
2405	int HierarchyManager::CompressObjectSpace()
2406	{
2407	//mBvHierarchy->Compress();
2408	return mVspTree->CompressObjects();
2409	}
2410
2411
2412	void HierarchyManager::CreateUniqueObjectIds()
2413	{
2414	mBvHierarchy->CreateUniqueObjectIds();
2415	}
2416
2417
2418	}

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

Download in other formats: