Context Navigation

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

Revision 1845, 64.6 KB checked in by mattausch, 18 years ago (diff)
improved object pvs

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

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

Download in other formats: