Context Navigation

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

Revision 1842, 64.4 KB checked in by mattausch, 18 years ago (diff)
fixed compress

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

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

Download in other formats: