Context Navigation

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

Revision 1920, 67.3 KB checked in by mattausch, 18 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	{
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 float maxRenderCost,
1502	const bool exportBounds) const
1503	{
1504	switch (mObjectSpaceSubdivisionType)
1505	{
1506	case KD_BASED_OBJ_SUBDIV:
1507	{
1508	ExportOspTree(exporter, objects);
1509	break;
1510	}
1511	case BV_BASED_OBJ_SUBDIV:
1512	{
1513	exporter->ExportBvHierarchy(*mBvHierarchy, maxRenderCost, bbox, exportBounds);
1514	break;
1515	}
1516	default:
1517	break;
1518	}
1519	}
1520
1521
1522	void HierarchyManager::ExportOspTree(Exporter *exporter,
1523	const ObjectContainer &objects) const
1524	{
1525	if (0) exporter->ExportGeometry(objects);
1526
1527	exporter->SetWireframe();
1528	exporter->ExportOspTree(*mOspTree, 0);
1529	}
1530
1531
1532	Intersectable HierarchyManager::GetIntersectable(Intersectable obj,
1533	const Vector3 &point) const
1534	{
1535
1536	if (!obj)
1537	return NULL;
1538
1539	switch (mObjectSpaceSubdivisionType)
1540	{
1541	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1542	{
1543	KdLeaf *leaf = mOspTree->GetLeaf(point, NULL);
1544	return mOspTree->GetOrCreateKdIntersectable(leaf);
1545	}
1546	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1547	{
1548	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1549	return leaf;
1550	}
1551	default:
1552	return obj;
1553	}
1554	}
1555
1556	Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1557	const bool isTermination) const
1558	{
1559	Intersectable *obj = NULL;
1560	Vector3 pt;
1561	KdNode *node;
1562
1563	ray.GetSampleData(isTermination, pt, &obj, &node);
1564
1565	if (!obj)
1566	return NULL;
1567
1568	switch (mObjectSpaceSubdivisionType)
1569	{
1570	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1571	{
1572	KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1573	return mOspTree->GetOrCreateKdIntersectable(leaf);
1574	}
1575	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1576	{
1577	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1578	return leaf;
1579	}
1580	default:
1581	break;
1582	}
1583
1584	return obj;
1585	}
1586
1587
1588	void HierarchyStatistics::Print(ostream &app) const
1589	{
1590	app << "=========== Hierarchy statistics ===============\n";
1591
1592	app << setprecision(4);
1593
1594	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
1595
1596	app << "#N_RTIME ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
1597
1598	app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
1599
1600	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1601
1602	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1603
1604	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
1605
1606	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1607
1608	app << "========== END OF Hierarchy statistics ==========\n";
1609	}
1610
1611
1612	static void RemoveRayRefs(const ObjectContainer &objects)
1613	{
1614	ObjectContainer::const_iterator oit, oit_end = objects.end();
1615	for (oit = objects.begin(); oit != oit_end; ++ oit)
1616	{
1617	(*oit)->DelRayRefs();
1618	}
1619	}
1620
1621
1622	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
1623	const bool removeRayRefs) const
1624	{
1625	switch (mObjectSpaceSubdivisionType)
1626	{
1627	case KD_BASED_OBJ_SUBDIV:
1628	{
1629	mOspTree->mOspStats.Stop();
1630	break;
1631	}
1632	case BV_BASED_OBJ_SUBDIV:
1633	{
1634	mBvHierarchy->mBvhStats.Stop();
1635	if (removeRayRefs)
1636	RemoveRayRefs(objects);
1637	break;
1638	}
1639	default:
1640	break;
1641	}
1642	}
1643
1644
1645	void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
1646	{
1647	stream << "<BoundingBoxes>" << endl;
1648
1649	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
1650	{
1651	KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
1652
1653	int id = 0;
1654	for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
1655	{
1656	Intersectable obj = (kit).second;
1657	const AxisAlignedBox3 box = obj->GetBox();
1658
1659	obj->SetId(id);
1660
1661	stream << "<BoundingBox" << " id=\"" << id << "\""
1662	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1663	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1664	}
1665	}
1666	else
1667	{
1668	ObjectContainer::const_iterator oit, oit_end = objects.end();
1669
1670	for (oit = objects.begin(); oit != oit_end; ++ oit)
1671	{
1672	const AxisAlignedBox3 box = (*oit)->GetBox();
1673
1674	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
1675	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
1676	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
1677	}
1678	}
1679
1680	stream << "</BoundingBoxes>" << endl;
1681	}
1682
1683
1684	class HierarchyNodeWrapper;
1685
1686
1687	template <typename T> class myless
1688	{
1689	public:
1690	bool operator() (T v1, T v2) const
1691	{
1692	return (v1->GetMergeCost() < v2->GetMergeCost());
1693	}
1694	};
1695
1696
1697	typedef priority_queue<HierarchyNodeWrapper , vector<HierarchyNodeWrapper >,
1698	myless<vector<HierarchyNodeWrapper *>::value_type> > HierarchyNodeQueue;
1699
1700	class HierarchyNodeWrapper
1701	{
1702	public:
1703	enum {VSP_NODE, BVH_NODE, VIEW_CELL};
1704
1705	virtual float GetMergeCost() const = 0;
1706	virtual int Type() const = 0;
1707	virtual bool IsLeaf() const = 0;
1708
1709	virtual void PushChildren(HierarchyNodeQueue &tQueue) = 0;
1710	};
1711
1712
1713	class VspNodeWrapper: public HierarchyNodeWrapper
1714	{
1715	public:
1716	VspNodeWrapper(VspNode *node): mNode(node) {}
1717
1718	int Type() const { return VSP_NODE; }
1719
1720	float GetMergeCost() const { return (float) -mNode->mTimeStamp; };
1721
1722	bool IsLeaf() const { return mNode->IsLeaf(); }
1723
1724	void PushChildren(HierarchyNodeQueue &tQueue)
1725	{
1726	if (!mNode->IsLeaf())
1727	{
1728	VspInterior interior = dynamic_cast<VspInterior >(mNode);
1729
1730	tQueue.push(new VspNodeWrapper(interior->GetFront()));
1731	tQueue.push(new VspNodeWrapper(interior->GetBack()));
1732	}
1733	}
1734
1735	VspNode *mNode;
1736	};
1737
1738
1739	class BvhNodeWrapper: public HierarchyNodeWrapper
1740	{
1741	public:
1742	BvhNodeWrapper(BvhNode *node): mNode(node) {}
1743
1744	int Type() const { return BVH_NODE; }
1745
1746	float GetMergeCost() const { return (float)-mNode->GetTimeStamp(); };
1747
1748	bool IsLeaf() const { return mNode->IsLeaf(); }
1749
1750	void PushChildren(HierarchyNodeQueue &tQueue)
1751	{
1752	if (!mNode->IsLeaf())
1753	{
1754	BvhInterior interior = dynamic_cast<BvhInterior >(mNode);
1755
1756	tQueue.push(new BvhNodeWrapper(interior->GetFront()));
1757	tQueue.push(new BvhNodeWrapper(interior->GetBack()));
1758	}
1759	}
1760
1761	BvhNode *mNode;
1762	};
1763
1764
1765	class ViewCellWrapper: public HierarchyNodeWrapper
1766	{
1767	public:
1768
1769	ViewCellWrapper(ViewCell *vc): mViewCell(vc) {}
1770
1771	int Type() const { return VIEW_CELL; }
1772
1773	float GetMergeCost() const { return mViewCell->GetMergeCost(); };
1774
1775	bool IsLeaf() const { return mViewCell->IsLeaf(); }
1776
1777	void PushChildren(HierarchyNodeQueue &tQueue)
1778	{
1779	if (!mViewCell->IsLeaf())
1780	{
1781	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(mViewCell);
1782
1783	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1784
1785	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1786	{
1787	tQueue.push(new ViewCellWrapper(*it));
1788	}
1789	}
1790	}
1791
1792	ViewCell *mViewCell;
1793	};
1794
1795
1796	void HierarchyManager::CollectBestSet(const int maxSplits,
1797	const float maxMemoryCost,
1798	ViewCellContainer &viewCells,
1799	vector<BvhNode *> &bvhNodes)
1800	{
1801	HierarchyNodeQueue tqueue;
1802	//tqueue.push(new VspNodeWrapper(mVspTree->GetRoot()));
1803	tqueue.push(new ViewCellWrapper(mVspTree->mViewCellsTree->GetRoot()));
1804	tqueue.push(new BvhNodeWrapper(mBvHierarchy->GetRoot()));
1805
1806	float memCost = 0;
1807
1808	while (!tqueue.empty())
1809	{
1810	HierarchyNodeWrapper *nodeWrapper = tqueue.top();
1811	tqueue.pop();
1812	//cout << "priority: " << nodeWrapper->GetMergeCost() << endl;
1813	// save the view cells if it is a leaf or if enough view cells have already been traversed
1814	// because of the priority queue, this will be the optimal set of v
1815	if (nodeWrapper->IsLeaf() \|\|
1816	((viewCells.size() + bvhNodes.size() + tqueue.size() + 1) >= maxSplits) \|\|
1817	(memCost > maxMemoryCost)
1818	)
1819	{
1820	if (nodeWrapper->Type() == HierarchyNodeWrapper::VIEW_CELL)
1821	{
1822	//cout << "1";
1823	ViewCellWrapper viewCellWrapper = dynamic_cast<ViewCellWrapper >(nodeWrapper);
1824	viewCells.push_back(viewCellWrapper->mViewCell);
1825	}
1826	else
1827	{
1828	//cout << "0";
1829	BvhNodeWrapper bvhNodeWrapper = dynamic_cast<BvhNodeWrapper >(nodeWrapper);
1830	bvhNodes.push_back(bvhNodeWrapper->mNode);
1831	}
1832	}
1833	else
1834	{
1835	nodeWrapper->PushChildren(tqueue);
1836	}
1837
1838	delete nodeWrapper;
1839	}
1840	}
1841
1842
1843	void HierarchyManager::ComputePvs(const ObjectPvs &pvs,
1844	float &rc,
1845	int &pvsEntries)
1846	{
1847	BvhNode::NewMail();
1848
1849	ObjectPvsIterator pit = pvs.GetIterator();
1850
1851	while (pit.HasMoreEntries())
1852	{
1853	const ObjectPvsEntry &entry = pit.Next();
1854
1855	if (entry.mObject->Type() != Intersectable::BVH_INTERSECTABLE)
1856	cout << "error " << entry.mObject->Type() << endl;
1857
1858	BvhNode intersect = dynamic_cast<BvhNode >(entry.mObject);
1859	BvhNode *activeNode;
1860
1861	// hack for choosing which node to account for
1862	if (intersect->IsLeaf())
1863	{
1864	activeNode =
1865	dynamic_cast<BvhLeaf *>(intersect)->GetActiveNode();
1866	}
1867	else
1868	{
1869	activeNode = intersect;
1870	}
1871
1872	if (!activeNode->Mailed())
1873	{
1874	activeNode->Mail();
1875
1876	#if STUPID_METHOD
1877
1878	ObjectContainer objects;
1879	activeNode->CollectObjects(objects);
1880	rc += mBvHierarchy->EvalAbsCost(objects);
1881	#else
1882	rc += mBvHierarchy->GetRenderCostIncrementially(activeNode);
1883	#endif
1884	++ pvsEntries;
1885	}
1886	}
1887	}
1888
1889
1890	void HierarchyManager::GetPvsEfficiently(ViewCell *viewCell, ObjectPvs &pvs) const
1891	{
1892	////////////////
1893	//-- pvs is not stored with the interiors => reconstruct
1894
1895	// add pvs from leaves
1896	stack<ViewCell *> tstack;
1897	tstack.push(viewCell);
1898
1899	Intersectable::NewMail();
1900
1901	while (!tstack.empty())
1902	{
1903	ViewCell *vc = tstack.top();
1904	tstack.pop();
1905
1906	// add newly found pvs to merged pvs: break here even for interior
1907	if (!vc->GetPvs().Empty())
1908	{
1909	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1910
1911	while (pit.HasMoreEntries())
1912	{
1913	const ObjectPvsEntry &entry = pit.Next();
1914
1915	Intersectable *object = entry.mObject;
1916	if (!object->Mailed())
1917	{
1918	object->Mail();
1919	pvs.AddSampleDirty(object, 1.0f);
1920	}
1921	}
1922	}
1923	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1924	{
1925	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1926	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1927
1928	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1929	{
1930	tstack.push(*it);
1931	}
1932	}
1933	}
1934	}
1935
1936
1937	// TODO matt: implement this function for different storing methods
1938	void HierarchyManager::GetPvsIncrementially(ViewCell *vc, ObjectPvs &pvs) const
1939	{
1940	////////////////
1941	//-- pvs is not stored with the interiors => reconstruct
1942
1943	// add pvs from leaves
1944	stack<ViewCell *> tstack;
1945	tstack.push(vc);
1946
1947	while (!tstack.empty())
1948	{
1949	vc = tstack.top();
1950	tstack.pop();
1951
1952	// add newly found pvs to merged pvs: break here even for interior
1953	if (!vc->GetPvs().Empty())
1954	{
1955	//if (vc->IsLeaf()) cout << " l " << pvs.GetSize();
1956	//else cout << " i " << pvs.GetSize();
1957	pvs.MergeInPlace(vc->GetPvs());
1958	}
1959	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
1960	{
1961	//cout <<" t";
1962	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1963	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1964
1965	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1966	{
1967	tstack.push(*it);
1968	}
1969	}
1970	else cout <<"k";
1971	}
1972	}
1973
1974
1975	// TODO matt: implement this function for different storing methods
1976	void HierarchyManager::PullUpPvsIncrementally(ViewCell *viewCell) const
1977	{
1978	////////////////
1979	//-- pvs is not stored with the interiors => reconstruct
1980
1981	// early exit: pvs is already pulled up to this view cell
1982	if (!viewCell->GetPvs().Empty())
1983	return;
1984
1985	// add pvs from leaves
1986	stack<ViewCell *> tstack;
1987	tstack.push(viewCell);
1988
1989	ViewCell *vc = viewCell;
1990
1991	while (!tstack.empty())
1992	{
1993	vc = tstack.top();
1994	tstack.pop();
1995
1996	// add newly found pvs to merged pvs: break here even for interior
1997	if (!vc->GetPvs().Empty())
1998	{
1999	viewCell->GetPvs().MergeInPlace(vc->GetPvs());
2000	}
2001	else if (!vc->IsLeaf()) // interior cells: go down to leaf level
2002	{
2003	//cout <<" t";
2004	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2005	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2006
2007	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2008	{
2009	tstack.push(*it);
2010	}
2011	}
2012	}
2013	}
2014
2015
2016
2017	// TODO matt: implement this function for different storing methods
2018	void HierarchyManager::GetPvsRecursive(ViewCell *vc, ObjectPvs &pvs) const
2019	{
2020	////////////////
2021	//-- pvs is not stored with the interiors => reconstruct
2022	if (vc->IsLeaf() \|\| !vc->GetPvs().Empty())
2023	{
2024	pvs = vc->GetPvs();
2025	}
2026	else
2027	{
2028	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2029	#if 0
2030	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2031	const int childPvsSize = (int)interior->mChildren.size();
2032	vector<ObjectPvs> childPvs;
2033	childPvs.resize((int)interior->mChildren.size());
2034
2035	int i = 0;
2036	for (it = interior->mChildren.begin(); it != it_end; ++ it, ++ i)
2037	{
2038	GetPvsRecursive(*it, childPvs[i]);
2039	pvs.MergeInPlace(childPvs[i]);
2040	}
2041	#else
2042
2043	ObjectPvs leftPvs, rightPvs;
2044
2045	GetPvsRecursive(interior->mChildren[0], leftPvs);
2046	GetPvsRecursive(interior->mChildren[1], rightPvs);
2047
2048	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2049	#endif
2050	}
2051	}
2052
2053
2054	int HierarchyManager::ExtractStatistics(const int maxSplits,
2055	const float maxMemoryCost,
2056	float &renderCost,
2057	float &memory,
2058	int &pvsEntries,
2059	int &viewSpaceSplits,
2060	int &objectSpaceSplits,
2061	const bool useFilter,
2062	const bool useHisto,
2063	const int histoMem,
2064	const int pass,
2065	bool &histoUsed)
2066	{
2067	ViewCellContainer viewCells;
2068	vector<BvhNode *> bvhNodes;
2069
2070	// collect best set of view cells for this #splits
2071	CollectBestSet(maxSplits, maxMemoryCost, viewCells, bvhNodes);
2072	vector<BvhNode *>::const_iterator bit, bit_end = bvhNodes.end();
2073
2074	// set new nodes to be active
2075	for (bit = bvhNodes.begin(); bit != bit_end; ++ bit)
2076	{
2077	mBvHierarchy->SetActive(*bit);
2078	}
2079
2080	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2081
2082	pvsEntries = 0;
2083	renderCost = 0.0f;
2084
2085	ViewCell::NewMail();
2086
2087	//cout << "\nviewcells: " << viewCells.size() << endl;
2088	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2089	{
2090	ViewCell vc = vit;
2091	float rc = 0;
2092
2093	#if STUPID_METHOD
2094	ObjectPvs pvs;
2095	GetPvsIncrementially(vc, pvs);
2096	vc->SetPvs(pvs);
2097
2098	#else
2099
2100	ObjectPvs pvs;
2101
2102	if (vc->GetPvs().Empty())
2103	{
2104	// warning: uses mailing, pvs not sorted!!
2105	GetPvsEfficiently(vc, pvs);
2106	//GetPvsRecursive(vc, pvs);
2107	vc->SetPvs(pvs);
2108	//cout << "q";
2109	}
2110	//else cout << "t";
2111	#endif
2112
2113	vc->Mail();
2114
2115	if (useFilter)
2116	{
2117	const long startT = GetTime();
2118	ObjectPvs filteredPvs;
2119	mVspTree->mViewCellsManager->ApplyFilter2(vc, false, 1.0f, filteredPvs);
2120	const long endT = GetTime();
2121
2122	//cout << "filter computed in " << TimeDiff(startT, endT) * 1e-3f << " secs" << endl;
2123	ComputePvs(filteredPvs, rc, pvsEntries);
2124	}
2125	else
2126	{
2127	ComputePvs(vc->GetPvs(), rc, pvsEntries);
2128	vc->SetPvsCost(rc);
2129	}
2130
2131	rc *= vc->GetVolume();
2132	renderCost += rc;
2133	}
2134
2135	renderCost /= mVspTree->mViewCellsManager->GetViewSpaceBox().GetVolume();
2136	memory = pvsEntries * ObjectPvs::GetEntrySize();
2137
2138	viewSpaceSplits = (int)viewCells.size();
2139	objectSpaceSplits = (int)bvhNodes.size();
2140
2141	////////////////////////
2142	//-- evaluate histogram for pvs size
2143
2144	if (useHisto && (memory <= (float)histoMem))
2145	{
2146	char str[100];
2147	char statsPrefix[100];
2148	int histoStepSize;
2149
2150	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
2151
2152	cout << "computing pvs histogram for " << histoMem << " memory" << endl;
2153	Debug << "computing pvs histogram for " << histoMem << " memory" << endl;
2154
2155	sprintf(str, "-%05d-%05d-histo-pvs.log", pass, histoMem);
2156	const string filename = string(statsPrefix) + string(str);
2157
2158	mVspTree->mViewCellsManager->EvalViewCellHistogramForPvsSize(filename, viewCells);
2159
2160	histoUsed = true;
2161	}
2162
2163	//cout << "viewCells: " << (int)viewCells.size() << " nodes: " << (int)bvhNodes.size() << " rc: " << renderCost << " entries: " << pvsEntries << endl;
2164
2165	// delete old "base" view cells if they are not leaves
2166	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2167
2168	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2169	{
2170	if (!(oit)->Mailed() && !(oit)->IsLeaf())
2171	{
2172	(*oit)->GetPvs().Clear();
2173	}
2174	}
2175
2176	// store current level
2177	mOldViewCells = viewCells;
2178
2179	return (int)(viewCells.size() + bvhNodes.size());
2180	}
2181
2182
2183	void HierarchyManager::ExportStats(ofstream &stats,
2184	SplitQueue &tQueue,
2185	const ObjectContainer &objects)
2186	{
2187	HierarchySubdivisionStats subStats;
2188	subStats.Reset();
2189
2190	/////////////
2191	//-- initial situation
2192
2193	subStats.mNumSplits = 0;
2194	subStats.mTotalRenderCost = (float)objects.size();
2195	subStats.mEntriesInPvs = 1;
2196	subStats.mMemoryCost = (float)ObjectPvs::GetEntrySize();
2197	subStats.mFullMemory = subStats.mMemoryCost;
2198	subStats.mViewSpaceSplits = 0;
2199	subStats.mObjectSpaceSplits = 0;
2200	subStats.mRenderCostDecrease = 0;
2201	subStats.Print(stats);
2202
2203	cout << "exporting vsposp stats ... " << endl;
2204
2205	//-- go through tree in the order of render cost decrease
2206	//-- which is the same order as the view cells were merged
2207	//-- or the reverse order of subdivision for subdivision-only
2208	//-- view cell hierarchies.
2209
2210	while (!tQueue.Empty())
2211	{
2212	SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
2213	bool isLeaf;
2214	int timeStamp;
2215	float rcDecr;
2216	int entriesIncr;
2217
2218	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2219	{
2220	timeStamp = (int)-nextCandidate->GetPriority();
2221
2222	VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
2223	VspNode oldNode = (VspNode )nextCandidate->mEvaluationHack;
2224
2225	isLeaf = newNode->IsLeaf();
2226	//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2227	//entriesIncr = oldNode->mPvsEntriesIncr;
2228	}
2229	else
2230	{
2231	timeStamp = (int)-nextCandidate->GetPriority();
2232
2233	BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
2234	BvhNode oldNode = (BvhNode )nextCandidate->mEvaluationHack;
2235
2236	isLeaf = newNode->IsLeaf();
2237	//subStats.mRenderCostDecrease = oldNode->mRenderCostDecr;
2238	//entriesIncr = oldNode->mPvsEntriesIncr;
2239	}
2240
2241	if (!isLeaf)
2242	{
2243	subStats.mTotalRenderCost -= subStats.mRenderCostDecrease;
2244	//subStats.mEntriesInPvs += entriesIncr;
2245
2246	if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
2247	{
2248	++ subStats.mViewSpaceSplits;
2249	cout << "v";
2250	//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2251	}
2252	else
2253	{
2254	++ subStats.mObjectSpaceSplits;
2255	cout << "o";
2256	//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
2257	}
2258
2259	++ subStats.mNumSplits;
2260
2261	if ((subStats.mNumSplits % 500) == 499)
2262	cout << subStats.mNumSplits << " steps taken" << endl;
2263
2264	subStats.mMemoryCost = (float)subStats.mEntriesInPvs * (float)ObjectPvs::GetEntrySize();
2265	subStats.mFullMemory = subStats.mMemoryCost;
2266
2267	subStats.Print(stats);
2268
2269	}
2270
2271	DEL_PTR(nextCandidate);
2272	}
2273
2274	stats.close();
2275	}
2276
2277
2278	void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
2279	const ObjectContainer &objects,
2280	const string &filename)
2281	{
2282	#if 0
2283	VspTree *oldVspTree = mVspTree;
2284	ViewCellsManager *vm = mVspTree->mViewCellsManager;
2285	BvHierarchy *oldHierarchy = mBvHierarchy;
2286
2287	mBvHierarchy = new BvHierarchy();
2288	mBvHierarchy->mHierarchyManager = this;
2289	mBvHierarchy->mViewCellsManager = vm;
2290
2291	mVspTree = new VspTree();
2292	mVspTree->mHierarchyManager = this;
2293	mVspTree->mViewCellsManager = vm;
2294
2295	// create first nodes
2296	mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
2297	InitialiseObjectSpaceSubdivision(objects);
2298
2299	const long startTime = GetTime();
2300	cout << "Constructing evaluation hierarchies ... \n";
2301
2302	ofstream stats;
2303	stats.open(filename.c_str());
2304	SplitQueue tQueue;
2305
2306	BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
2307	VspNode *oldVspRoot = oldVspTree->GetRoot();
2308
2309	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
2310
2311	SubdivisionCandidate firstVsp = mVspTree->PrepareConstruction(sampleRays, viewSpaceRays);
2312	tQueue.Push(firstVsp);
2313
2314	mBvHierarchy->PrepareConstruction(tQueue, sampleRays, objects);
2315
2316	firstVsp->mEvaluationHack = oldVspRoot;
2317	firstBvh->mEvaluationHack = oldBvhRoot;
2318
2319	firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
2320	firstBvh->SetPriority((float)-oldBvhRoot->GetTimeStamp());
2321
2322	ExportStats(stats, tQueue, objects);
2323
2324	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2325	RemoveRayRefs(objects);
2326
2327	// view cells needed only for evaluation
2328	ViewCellContainer viewCells;
2329	mVspTree->CollectViewCells(viewCells, false);
2330
2331	// helper trees can be destroyed
2332	DEL_PTR(mVspTree);
2333	DEL_PTR(mBvHierarchy);
2334
2335	CLEAR_CONTAINER(viewCells);
2336
2337	// reset hierarchies
2338	mVspTree = oldVspTree;
2339	mBvHierarchy = oldHierarchy;
2340
2341	// reinstall old bv refs
2342	vector<BvhLeaf *> leaves;
2343	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), leaves);
2344	vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
2345
2346	for (bit = leaves.begin(); bit != bit_end; ++ bit)
2347	{
2348	mBvHierarchy->AssociateObjectsWithLeaf(*bit);
2349	}
2350	#endif
2351	}
2352
2353
2354	void HierarchyManager::EvaluateSubdivision2(ofstream &splitsStats,
2355	const int splitsStepSize,
2356	const bool useFilter,
2357	const bool useHisto,
2358	const int histoMem,
2359	const int pass)
2360	{
2361	vector<HierarchySubdivisionStats> subStatsContainer;
2362
2363	int splits = (1 + (mHierarchyStats.Leaves() - 1) / splitsStepSize) * splitsStepSize;
2364	cout << "splits: " << splits << endl;
2365
2366	bool histoUsed = false;
2367
2368	while (1)
2369	{
2370	HierarchySubdivisionStats subStats;
2371	subStats.mNumSplits = ExtractStatistics(splits,
2372	99999.0,
2373	subStats.mTotalRenderCost,
2374	subStats.mMemoryCost,
2375	subStats.mEntriesInPvs,
2376	subStats.mViewSpaceSplits,
2377	subStats.mObjectSpaceSplits,
2378	useFilter,
2379	useHisto && !histoUsed,
2380	histoMem,
2381	pass,
2382	histoUsed);
2383
2384
2385	const float objectSpaceHierarchyMem = float(
2386	subStats.mObjectSpaceSplits * mBvHierarchy->mMemoryConst//sizeof(ObjectContainer)
2387	//+ (subStats.mObjectSpaceSplits - 1) * sizeof(BvhInterior)
2388	//+sizeof(BvHierarchy)
2389	) / float(1024 * 1024);
2390
2391
2392	const float viewSpaceHierarchyMem = float(
2393	subStats.mViewSpaceSplits * mVspTree->mMemoryConst//sizeof(ObjectPvs)
2394	//+ (subStats.mViewSpaceSplits - 1) * sizeof(VspInterior)
2395	+ sizeof(ObjectPvs)
2396	//+ sizeof(VspTree)
2397	) / float(1024 * 1024);
2398
2399	subStats.mFullMemory = subStats.mMemoryCost + objectSpaceHierarchyMem + viewSpaceHierarchyMem;
2400
2401	subStatsContainer.push_back(subStats);
2402
2403	if (splits == 0)
2404	{
2405	break;
2406	}
2407	splits -= splitsStepSize;
2408
2409	cout << "splits: " << subStats.mNumSplits << " ";
2410	}
2411
2412	vector<HierarchySubdivisionStats>::const_reverse_iterator hit, hit_end = subStatsContainer.rend();
2413
2414	for (hit = subStatsContainer.rbegin(); hit != hit_end; ++ hit)
2415	{
2416	(*hit).Print(splitsStats);
2417	}
2418
2419	// delete old "base" view cells: only pvss in the leaves are allowed
2420	ViewCellContainer::const_iterator oit, oit_end = mOldViewCells.end();
2421	for (oit = mOldViewCells.begin(); oit != oit_end; ++ oit)
2422	{
2423	if (!(*oit)->IsLeaf())
2424	{
2425	(*oit)->GetPvs().Clear();
2426	}
2427	}
2428
2429	mOldViewCells.clear();
2430
2431	// reset active nodes
2432	vector<BvhLeaf *> bvhLeaves;
2433
2434	mBvHierarchy->CollectLeaves(mBvHierarchy->GetRoot(), bvhLeaves);
2435
2436	vector<BvhLeaf *>::const_iterator bit, bit_end = bvhLeaves.end();
2437
2438	for (bit = bvhLeaves.begin(); bit != bit_end; ++ bit)
2439	{
2440	(bit)->SetActiveNode(bit);
2441	}
2442
2443	cout << endl;
2444	}
2445
2446
2447	void HierarchyManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
2448	{
2449	mBvHierarchy->CollectObjects(box, objects);
2450	}
2451
2452
2453	int HierarchyManager::CompressObjectSpace()
2454	{
2455	//mBvHierarchy->Compress();
2456	return mVspTree->CompressObjects();
2457	}
2458
2459
2460	void HierarchyManager::CreateUniqueObjectIds()
2461	{
2462	mBvHierarchy->CreateUniqueObjectIds();
2463	}
2464
2465
2466	}

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

Download in other formats: