Context Navigation

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

Revision 1580, 28.8 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include <stack>
2	#include <time.h>
3	#include <iomanip>
4
5	#include "ViewCell.h"
6	#include "Plane3.h"
7	#include "HierarchyManager.h"
8	#include "Mesh.h"
9	#include "common.h"
10	#include "Environment.h"
11	#include "Polygon3.h"
12	#include "Ray.h"
13	#include "AxisAlignedBox3.h"
14	#include "Exporter.h"
15	#include "Plane3.h"
16	#include "ViewCellsManager.h"
17	#include "Beam.h"
18	#include "KdTree.h"
19	#include "IntersectableWrapper.h"
20	#include "VspTree.h"
21	#include "OspTree.h"
22	#include "BvHierarchy.h"
23
24
25	namespace GtpVisibilityPreprocessor {
26
27
28	#define USE_FIXEDPOINT_T 0
29
30
31	/*******************************************************************/
32	/* class HierarchyManager implementation */
33	/*******************************************************************/
34
35
36	HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
37	mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
38	mOspTree(NULL),
39	mBvHierarchy(NULL)
40	{
41	switch(mObjectSpaceSubdivisionType)
42	{
43	case KD_BASED_OBJ_SUBDIV:
44	mOspTree = new OspTree();
45	mOspTree->mVspTree = mVspTree;
46	mOspTree->mHierarchyManager = this;
47	break;
48	case BV_BASED_OBJ_SUBDIV:
49	mBvHierarchy = new BvHierarchy();
50	mBvHierarchy->mHierarchyManager = this;
51	break;
52	default:
53	break;
54	}
55
56	// hierarchy manager links view space partition and object space partition
57	mVspTree = new VspTree();
58	mVspTree->mHierarchyManager = this;
59
60	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
61	ParseEnvironment();
62	}
63
64
65	HierarchyManager::HierarchyManager(KdTree *kdTree):
66	mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
67	mBvHierarchy(NULL)
68	{
69	mOspTree = new OspTree(*kdTree);
70	mOspTree->mVspTree = mVspTree;
71
72	mVspTree = new VspTree();
73	mVspTree->mHierarchyManager = this;
74
75	mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
76	ParseEnvironment();
77	}
78
79
80	void HierarchyManager::ParseEnvironment()
81	{
82	Environment::GetSingleton()->GetFloatValue(
83	"Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
84	Environment::GetSingleton()->GetIntValue(
85	"Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
86
87	Environment::GetSingleton()->GetBoolValue(
88	"Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
89
90	Environment::GetSingleton()->GetIntValue(
91	"Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
92
93	Environment::GetSingleton()->GetIntValue(
94	"Hierarchy.Construction.type", mConstructionType);
95
96	Environment::GetSingleton()->GetIntValue(
97	"Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
98
99	Environment::GetSingleton()->GetIntValue(
100	"Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
101
102	Environment::GetSingleton()->GetBoolValue(
103	"Hierarchy.Construction.repairQueue", mRepairQueue);
104
105	Environment::GetSingleton()->GetBoolValue(
106	"Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
107
108	Environment::GetSingleton()->GetIntValue(
109	"Hierarchy.Construction.levels", mNumMultiLevels);
110
111	Debug << "****** Hierachy Manager Parameters *********" << endl;
112	Debug << "max leaves: " << mTermMaxLeaves << endl;
113	Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
114	Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
115	Debug << "construction type: " << mConstructionType << endl;
116	Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
117	Debug << "repair queue: " << mRepairQueue << endl;
118	Debug << "number of multilevels: " << mNumMultiLevels << endl;
119	Debug << endl;
120	}
121
122
123	HierarchyManager::~HierarchyManager()
124	{
125	DEL_PTR(mOspTree);
126	DEL_PTR(mVspTree);
127	DEL_PTR(mBvHierarchy);
128	}
129
130
131	int HierarchyManager::GetObjectSpaceSubdivisionType() const
132	{
133	return mObjectSpaceSubdivisionType;
134	}
135
136
137	int HierarchyManager::GetViewSpaceSubdivisionType() const
138	{
139	return mViewSpaceSubdivisionType;
140	}
141
142
143	void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
144	{
145	mVspTree->SetViewCellsManager(vcm);
146
147	if (mOspTree)
148	{
149	mOspTree->SetViewCellsManager(vcm);
150	}
151	else if (mBvHierarchy)
152	{
153	mBvHierarchy->SetViewCellsManager(vcm);
154	}
155	}
156
157
158	void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
159	{
160	mVspTree->SetViewCellsTree(vcTree);
161	}
162
163
164	VspTree *HierarchyManager::GetVspTree()
165	{
166	return mVspTree;
167	}
168
169	/*
170	AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
171	{
172	return mVspTree->mBoundingBox;
173	}*/
174
175
176	AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
177	{
178	switch (mObjectSpaceSubdivisionType)
179	{
180	case KD_BASED_OBJ_SUBDIV:
181	return mOspTree->mBoundingBox;
182	case BV_BASED_OBJ_SUBDIV:
183	return mBvHierarchy->mBoundingBox;
184	default:
185	// hack: empty box
186	return AxisAlignedBox3();
187	}
188	}
189
190
191	SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
192	{
193	SubdivisionCandidate *splitCandidate = mTQueue.Top();
194	mTQueue.Pop();
195
196	return splitCandidate;
197	}
198
199
200	void HierarchyManager::EvalSubdivisionStats(const float renderCostDecr)
201	{
202	//cout << "pvs entries " << mHierarchyStats.pvsEntries << endl;
203	AddSubdivisionStats(mHierarchyStats.Leaves(),
204	renderCostDecr,
205	mTotalCost,
206	mHierarchyStats.pvsEntries
207	);
208	}
209
210
211	void HierarchyManager::AddSubdivisionStats(const int splits,
212	const float renderCostDecr,
213	const float totalRenderCost,
214	const int pvsEntries)
215	{
216	mSubdivisionStats
217	<< "#Splits\n" << splits << endl
218	<< "#RenderCostDecrease\n" << renderCostDecr << endl
219	<< "#TotalEntriesInPvs\n" << pvsEntries << endl
220	<< "#TotalRenderCost\n" << totalRenderCost << endl;
221	}
222
223
224	bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
225	{
226	const bool terminationCriteriaMet =
227	(0
228	\|\| (mHierarchyStats.Leaves() >= mTermMaxLeaves)
229	\|\| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
230	\|\| (candidate->GlobalTerminationCriteriaMet())
231	);
232
233	if (0 && terminationCriteriaMet)
234	{
235	Debug << "hierarchy global termination criteria met:" << endl;
236	Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
237	Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
238	}
239	return terminationCriteriaMet;
240	}
241
242
243	void HierarchyManager::Construct(const VssRayContainer &sampleRays,
244	const ObjectContainer &objects,
245	AxisAlignedBox3 *forcedViewSpace)
246	{
247	if (mUseMultiLevelConstruction)
248	{
249	ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
250	}
251	else
252	{
253	char subdivisionStatsLog[100];
254	Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
255	subdivisionStatsLog);
256	mSubdivisionStats.open(subdivisionStatsLog);
257
258	ConstructInterleaved(sampleRays, objects, forcedViewSpace);
259	}
260	}
261
262
263	void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
264	const ObjectContainer &objects,
265	AxisAlignedBox3 *forcedViewSpace)
266	{
267	mHierarchyStats.Reset();
268	mHierarchyStats.Start();
269	mHierarchyStats.nodes = 2; // two nodes for view space and object space
270
271	mTotalCost = (float)objects.size();
272	EvalSubdivisionStats(0);
273	Debug << "setting total cost to " << mTotalCost << endl;
274
275	const long startTime = GetTime();
276	cout << "Constructing view space / object space tree ... \n";
277
278	// compute view space bounding box
279	mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
280
281	// use objects for evaluating vsp tree construction in the first levels
282	// of the subdivision
283	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
284	mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
285
286	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
287	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
288
289	// start with view space subdivison: prepare vsp tree for traversal
290	if (StartViewSpaceSubdivision())
291	{
292	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
293	PrepareViewSpaceSubdivision(sampleRays, objects);
294	}
295
296	// start object space subdivision immediately?
297	if (StartObjectSpaceSubdivision())
298	{
299	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
300	PrepareObjectSpaceSubdivision(sampleRays, objects);
301	}
302
303	// process object space candidates
304	RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
305
306	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
307
308	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
309	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
310
311	mHierarchyStats.Stop();
312	mVspTree->mVspStats.Stop();
313	FinishObjectSpaceSubdivision(objects);
314	}
315
316
317	void HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
318	const ObjectContainer &objects)
319	{
320	cout << "\nstarting view space hierarchy construction ... " << endl;
321	// hack: reset global cost misses
322	mHierarchyStats.mGlobalCostMisses = 0;
323
324	RayInfoContainer *viewSpaceRays = new RayInfoContainer();
325	SubdivisionCandidate *vsc =
326	mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
327
328	mTotalCost = mVspTree->mTotalCost;
329	Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
330
331	mTQueue.Push(vsc);
332	}
333
334
335	void HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
336	const ObjectContainer &objects)
337	{
338	mHierarchyStats.mGlobalCostMisses = 0; // hack: reset global cost misses
339
340	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
341	{
342	PrepareOspTree(sampleRays, objects);
343	}
344	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
345	{
346	PrepareBvHierarchy(sampleRays, objects);
347	}
348	}
349
350
351	void HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
352	const ObjectContainer &objects)
353	{
354	const long startTime = GetTime();
355
356	cout << "preparing bv hierarchy construction ... " << endl;
357
358	// compute first candidate
359	SubdivisionCandidate *sc =
360	mBvHierarchy->PrepareConstruction(sampleRays, objects);
361
362	mTotalCost = mBvHierarchy->mTotalCost;
363	Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
364
365	mTQueue.Push(sc);
366	cout << "finished bv hierarchy preparation in "
367	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
368	}
369
370
371	void HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
372	const ObjectContainer &objects)
373	{
374	cout << "starting osp tree construction ... " << endl;
375
376	RayInfoContainer *objectSpaceRays = new RayInfoContainer();
377
378	// start with one big kd cell - all objects can be seen from everywhere
379	// note: only true for view space = object space
380
381	// compute first candidate
382	SubdivisionCandidate *osc =
383	mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
384
385	mTotalCost = mOspTree->mTotalCost;
386	Debug << "\nreseting cost, new total cost: " << mTotalCost << endl;
387
388	mTQueue.Push(osc);
389	}
390
391
392	bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc, const bool repairQueue)
393	{
394	const bool globalTerminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
395	const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
396
397	if (!globalTerminationCriteriaMet)
398	{
399	// cost ratio of cost decrease / totalCost
400	const float costRatio = mCurrentCandidate->GetRenderCostDecrease() / mTotalCost;
401	//Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
402
403	if (costRatio < mTermMinGlobalCostRatio)
404	{
405	++ mHierarchyStats.mGlobalCostMisses;
406	}
407
408	mTotalCost -= mCurrentCandidate->GetRenderCostDecrease();
409	}
410
411	bool success;
412	switch (sc->Type())
413	{
414	case SubdivisionCandidate::VIEW_SPACE:
415	{
416	VspNode *n = mVspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
417	success = !n->IsLeaf(); // local or global termination criteria failed?
418	}
419	break;
420	case SubdivisionCandidate::OBJECT_SPACE:
421	{
422	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
423	{
424	KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
425	// local or global termination criteria failed
426	success = !n->IsLeaf();
427	}
428	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
429	{
430	BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
431	// local or global termination criteria failed
432	success = !n->IsLeaf();
433	}
434	}
435	break;
436	default:
437	break;
438	}
439
440	cout << sc->Type() << " ";
441
442	// update stats
443	mHierarchyStats.nodes += 2;
444
445	const int pvsEntries = sc->GetPvsEntriesIncr();
446	mHierarchyStats.pvsEntries += pvsEntries;
447
448	//cout << "pvs entries: " << pvsEntries << " " << mHierarchyStats.pvsEntries << endl;
449	mHierarchyStats.memory += 0; // TODO
450
451	// subdivision successful
452	EvalSubdivisionStats(sc->GetRenderCostDecrease());
453
454	// reevaluate candidates affected by the split for view space splits,
455	// this would be object space splits and other way round
456	if (repairQueue)
457	{
458	RepairQueue();
459	}
460
461	return true;
462	}
463
464
465	int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
466	{
467	int maxDepth = 0;
468
469	if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
470	{
471	maxDepth = mOspTree->mOspStats.maxDepth;
472	}
473	else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
474	{
475	maxDepth = mBvHierarchy->mBvhStats.maxDepth;
476	}
477
478	return maxDepth;
479	}
480
481
482	bool HierarchyManager::StartObjectSpaceSubdivision() const
483	{
484	// view space construction already started
485	if (ObjectSpaceSubdivisionConstructed())
486	return false;
487
488	// start immediately with object space subdivision?
489	if (mStartWithObjectSpace)
490	return true;
491
492	// is the queue empty again?
493	if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
494	return true;
495
496	// has the depth for subdivision been reached?
497	return
498	((mConstructionType == INTERLEAVED) &&
499	(mMinDepthForObjectSpaceSubdivion <= mVspTree->mVspStats.maxDepth));
500	}
501
502
503	bool HierarchyManager::StartViewSpaceSubdivision() const
504	{
505	// view space construction already started
506	if (ViewSpaceSubdivisionConstructed())
507	return false;
508
509	// start immediately with view space subdivision?
510	if (!mStartWithObjectSpace)
511	return true;
512
513	// is the queue empty again?
514	if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
515	return true;
516
517	// has the depth for subdivision been reached?
518	return
519	((mConstructionType == INTERLEAVED) &&
520	(mMinDepthForViewSpaceSubdivion <= GetObjectSpaceSubdivisionDepth()));
521	}
522
523
524	void HierarchyManager::RunConstruction(const bool repairQueue,
525	const VssRayContainer &sampleRays,
526	const ObjectContainer &objects,
527	AxisAlignedBox3 *forcedViewSpace)
528	{
529	int i = 0;
530	while (!FinishedConstruction())
531	{
532	mCurrentCandidate = NextSubdivisionCandidate();
533
534	///////////////////
535	//-- subdivide leaf node
536
537	ApplySubdivisionCandidate(mCurrentCandidate, repairQueue);
538
539	// we use objects for evaluating vsp tree construction until
540	// a certain depth once a certain depth existiert ...
541	if (StartObjectSpaceSubdivision())
542	{
543	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
544
545	cout << "\nstarting object space subdivision at depth "
546	<< mVspTree->mVspStats.maxDepth << " ("
547	<< mMinDepthForObjectSpaceSubdivion << ") " << endl;
548
549	PrepareObjectSpaceSubdivision(sampleRays, objects);
550
551	cout << "reseting queue ... ";
552	ResetQueue();
553	cout << "finished" << endl;
554	}
555
556	if (StartViewSpaceSubdivision())
557	{
558	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
559
560	cout << "\nstarting view space subdivision at depth "
561	<< GetObjectSpaceSubdivisionDepth() << " ("
562	<< mMinDepthForViewSpaceSubdivion << ") " << endl;
563
564	PrepareViewSpaceSubdivision(sampleRays, objects);
565
566	cout << "reseting queue ... ";
567	ResetQueue();
568	cout << "finished" << endl;
569	}
570
571	DEL_PTR(mCurrentCandidate);
572	}
573	}
574
575
576
577	void HierarchyManager::RunConstruction(const bool repairQueue)
578	{
579	int i = 0;
580	// main loop
581	while (!FinishedConstruction())
582	{
583	mCurrentCandidate = NextSubdivisionCandidate();
584
585	///////
586	//-- subdivide leaf node
587
588	ApplySubdivisionCandidate(mCurrentCandidate, repairQueue);
589	DEL_PTR(mCurrentCandidate);
590	}
591	}
592
593
594	void HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
595	const ObjectContainer &objects)
596	{
597	#if 0
598	DEL_PTR(mBvHierarchy);
599	mBvHierarchy = new BvHierarchy();
600	mBvHierarchy->mHierarchyManager = this;
601
602	PrepareObjectSpaceSubdivision(sampleRays, objects);
603	return;
604	#else
605
606	// no object space subdivision yet
607	if (!ObjectSpaceSubdivisionConstructed())
608	{
609	return PrepareObjectSpaceSubdivision(sampleRays, objects);
610	}
611
612	// object space partition constructed => reconstruct
613	switch (mObjectSpaceSubdivisionType)
614	{
615	case BV_BASED_OBJ_SUBDIV:
616	{
617	cout << "\nreseting bv hierarchy" << endl;
618	Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
619
620	SubdivisionCandidate *firstCandidate =
621	mBvHierarchy->Reset(sampleRays, objects);
622
623	mTQueue.Push(firstCandidate);
624	mTotalCost = mBvHierarchy->mTotalCost;
625
626	mHierarchyStats.nodes = 2;
627	mHierarchyStats.pvsEntries = 0;
628	EvalSubdivisionStats(0);
629	}
630	break;
631
632	case KD_BASED_OBJ_SUBDIV:
633	// TODO
634	break;
635	default:
636	break;
637	}
638	#endif
639	}
640
641
642	void HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
643	const ObjectContainer &objects)
644	{
645	ViewCellsManager *vc = mVspTree->mViewCellsManager;
646
647	DEL_PTR(mVspTree);
648	mVspTree = new VspTree();
649	mVspTree->mHierarchyManager = this;
650	mVspTree->mViewCellsManager = vc;
651
652	PrepareViewSpaceSubdivision(sampleRays, objects);
653
654	mHierarchyStats.nodes = 2;
655	mHierarchyStats.pvsEntries = 0;
656	EvalSubdivisionStats(0);
657
658	}
659
660
661	void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,
662	const ObjectContainer &objects,
663	AxisAlignedBox3 *forcedViewSpace)
664	{
665	mHierarchyStats.Reset();
666	mHierarchyStats.Start();
667	mHierarchyStats.nodes = 2;
668
669	mTotalCost = (float)objects.size();
670	Debug << "setting total cost to " << mTotalCost << endl;
671
672	const long startTime = GetTime();
673	cout << "Constructing view space / object space tree ... \n";
674
675	// compute view space bounding box
676	mVspTree->ComputeBoundingBox(sampleRays, forcedViewSpace);
677
678	// use sah for evaluating osp tree construction
679	// in the first iteration of the subdivision
680
681	mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
682	mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
683
684	mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
685	//mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
686
687	const int limit = mNumMultiLevels;
688	int i = 0;
689
690	// render cost optimization
691	// start with object space partiton
692	// then optimizate view space partition for the current osp
693	// and vice versa until iteration depth is reached.
694	while (1)
695	{
696	char subdivisionStatsLog[100];
697	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
698	mSubdivisionStats.open(subdivisionStatsLog);
699
700	// fsubdivide object space first
701	ResetObjectSpaceSubdivision(sampleRays, objects);
702	// process object space candidates
703	RunConstruction(false);
704
705	// object space subdivision constructed
706	mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
707
708	cout << "iteration " << i << " of " << limit << " finished" << endl;
709
710	mSubdivisionStats.close();
711	if ((i ++) >= limit)
712	break;
713
714	sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
715	mSubdivisionStats.open(subdivisionStatsLog);
716
717	/////////////////
718	// subdivide view space with respect to the objects
719
720	ResetViewSpaceSubdivision(sampleRays, objects);
721	// process view space candidates
722	RunConstruction(false);
723	// view space subdivision constructed
724	mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
725
726	cout << "iteration " << i << " of " << limit << " finished" << endl;
727
728	mSubdivisionStats.close();
729
730	if ((i ++) >= limit)
731	break;
732	}
733
734	cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
735
736	/*#if _DEBUG
737	cout << "view space: " << GetViewSpaceBox() << endl;
738	cout << "object space: " << GetObjectSpaceBox() << endl;
739	#endif*/
740
741	mHierarchyStats.Stop();
742	mVspTree->mVspStats.Stop();
743	FinishObjectSpaceSubdivision(objects);
744	}
745
746
747	bool HierarchyManager::FinishedConstruction() const
748	{
749	return mTQueue.Empty();
750	}
751
752
753	bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
754	{
755	switch (mObjectSpaceSubdivisionType)
756	{
757	case KD_BASED_OBJ_SUBDIV:
758	return mOspTree && mOspTree->GetRoot();
759	case BV_BASED_OBJ_SUBDIV:
760	return mBvHierarchy && mBvHierarchy->GetRoot();
761	default:
762	return false;
763	}
764	}
765
766
767	bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
768	{
769	return mVspTree && mVspTree->GetRoot();
770	}
771
772
773	void HierarchyManager::CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
774	{
775	switch (mObjectSpaceSubdivisionType)
776	{
777	case KD_BASED_OBJ_SUBDIV:
778	{
779	OspTree::OspSubdivisionCandidate *sc =
780	dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
781
782	mOspTree->CollectDirtyCandidates(sc, dirtyList);
783	break;
784	}
785	case BV_BASED_OBJ_SUBDIV:
786	{
787	BvHierarchy::BvhSubdivisionCandidate *sc =
788	dynamic_cast<BvHierarchy::BvhSubdivisionCandidate *>(mCurrentCandidate);
789
790	mBvHierarchy->CollectDirtyCandidates(sc, dirtyList);
791	break;
792	}
793	default:
794	break;
795	}
796	}
797
798
799	void HierarchyManager::CollectViewSpaceDirtyList(SubdivisionCandidateContainer &dirtyList)
800	{
801	VspTree::VspSubdivisionCandidate *sc =
802	dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
803
804	mVspTree->CollectDirtyCandidates(sc, dirtyList);
805	}
806
807
808	void HierarchyManager::CollectDirtyCandidates(SubdivisionCandidateContainer &dirtyList)
809	{
810	// we have either a object space or view space split
811	if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
812	{
813	CollectViewSpaceDirtyList(dirtyList);
814	}
815	else // object space split
816	{
817	CollectObjectSpaceDirtyList(dirtyList);
818	}
819	}
820
821
822	void HierarchyManager::RepairQueue()
823	{
824	// for each update of the view space partition:
825	// the candidates from object space partition which
826	// have been afected by the view space split (the kd split candidates
827	// which saw the view cell which was split) must be reevaluated
828	// (maybe not locally, just reinsert them into the queue)
829	//
830	// vice versa for the view cells
831	// for each update of the object space partition
832	// reevaluate split candidate for view cells which saw the split kd cell
833	//
834	// the priority queue update can be solved by implementing a binary heap
835	// (explicit data structure, binary tree)
836	// *) inserting and removal is efficient
837	// *) search is not efficient => store queue position with each
838	// split candidate
839
840	// collect list of "dirty" candidates
841	const long startTime = GetTime();
842
843	vector<SubdivisionCandidate *> dirtyList;
844	CollectDirtyCandidates(dirtyList);
845	if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
846
847	/////////////////////////////////
848	//-- reevaluate the dirty list
849
850	SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
851
852	for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
853	{
854	SubdivisionCandidate* sc = *sit;
855	const float rcd = sc->GetRenderCostDecrease();
856
857	mTQueue.Erase(sc); // erase from queue
858	sc->EvalPriority(); // reevaluate
859
860	#ifdef _DEBUG
861	Debug << "candidate " << sc << " reevaluated\n"
862	<< "render cost decrease diff " << rcd - sc->GetRenderCostDecrease()
863	<< " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
864	#endif
865	mTQueue.Push(sc); // reinsert
866	cout << ".";
867	}
868
869	long endTime = GetTime();
870	Real timeDiff = TimeDiff(startTime, endTime);
871	mHierarchyStats.repairTime += timeDiff;
872
873	if (1) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
874	}
875
876
877	void HierarchyManager::ResetQueue()
878	{
879	SubdivisionCandidateContainer mCandidateBuffer;
880
881	// remove from queue
882	while (!mTQueue.Empty())
883	{
884	SubdivisionCandidate *candidate = NextSubdivisionCandidate();
885	candidate->EvalPriority(); // reevaluate
886	cout << ".";
887	mCandidateBuffer.push_back(candidate);
888	}
889
890	// put back into queue
891	SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
892	for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
893	{
894	mTQueue.Push(*sit);
895	}
896	}
897
898
899	void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
900	{
901	// the type of the view cells hierarchy
902	switch (mObjectSpaceSubdivisionType)
903	{
904	case KD_BASED_OBJ_SUBDIV:
905	stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
906	mOspTree->Export(stream);
907	stream << endl << "</ObjectSpaceHierarchy>" << endl;
908	break;
909	case BV_BASED_OBJ_SUBDIV:
910	stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
911	mBvHierarchy->Export(stream);
912	stream << endl << "</ObjectSpaceHierarchy>" << endl;
913	break;
914	}
915	}
916
917
918	bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
919	const Vector3 &hitPoint,
920	ViewCell *vc,
921	const float pdf,
922	float &contribution) const
923	{
924	if (!obj) return false;
925
926	switch (mObjectSpaceSubdivisionType)
927	{
928	case NO_OBJ_SUBDIV:
929	{
930	// potentially visible objects
931	return vc->AddPvsSample(obj, pdf, contribution);
932	}
933	case KD_BASED_OBJ_SUBDIV:
934	{
935	// potentially visible kd cells
936	KdLeaf leaf = mOspTree->GetLeaf(hitPoint/ray->mOriginNode*/);
937	return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
938	}
939	case BV_BASED_OBJ_SUBDIV:
940	{
941	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
942	BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
943
944	return vc->AddPvsSample(bvhObj, pdf, contribution);
945	}
946	default:
947	return false;
948	}
949	}
950
951
952	void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
953	{
954	stream << mHierarchyStats << endl;
955	stream << "\nview space:" << endl << endl;
956	stream << mVspTree->GetStatistics() << endl;
957	stream << "\nobject space:" << endl << endl;
958
959	switch (mObjectSpaceSubdivisionType)
960	{
961	case KD_BASED_OBJ_SUBDIV:
962	{
963	stream << mOspTree->GetStatistics() << endl;
964	break;
965	}
966	case BV_BASED_OBJ_SUBDIV:
967	{
968	stream << mBvHierarchy->GetStatistics() << endl;
969	break;
970	}
971	default:
972	break;
973	}
974	}
975
976
977	void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
978	const ObjectContainer &objects,
979	const AxisAlignedBox3 *bbox,
980	const bool exportBounds) const
981	{
982	switch (mObjectSpaceSubdivisionType)
983	{
984	case KD_BASED_OBJ_SUBDIV:
985	{
986	ExportOspTree(exporter, objects);
987	break;
988	}
989	case BV_BASED_OBJ_SUBDIV:
990	{
991	exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
992	break;
993	}
994	default:
995	break;
996	}
997	}
998
999
1000	void HierarchyManager::ExportOspTree(Exporter *exporter,
1001	const ObjectContainer &objects) const
1002	{
1003	if (0) exporter->ExportGeometry(objects);
1004
1005	exporter->SetWireframe();
1006	exporter->ExportOspTree(*mOspTree, 0);
1007	}
1008
1009
1010	Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
1011	const bool isTermination) const
1012	{
1013
1014	Intersectable *obj;
1015	Vector3 pt;
1016	KdNode *node;
1017
1018	ray.GetSampleData(isTermination, pt, &obj, &node);
1019
1020	if (!obj) return NULL;
1021
1022	switch (mObjectSpaceSubdivisionType)
1023	{
1024	case HierarchyManager::KD_BASED_OBJ_SUBDIV:
1025	{
1026	KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
1027	return mOspTree->GetOrCreateKdIntersectable(leaf);
1028	}
1029	case HierarchyManager::BV_BASED_OBJ_SUBDIV:
1030	{
1031	BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
1032	return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
1033	}
1034	default:
1035	return obj;
1036	}
1037	}
1038
1039
1040	void HierarchyStatistics::Print(ostream &app) const
1041	{
1042	app << "=========== Hierarchy statistics ===============\n";
1043
1044	app << setprecision(4);
1045
1046	app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
1047
1048	app << "#N_RTIME ( Repair time [s] )\n" << repairTime * 1e-3f << " \n";
1049
1050	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
1051
1052	app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
1053
1054	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
1055
1056	app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
1057
1058	app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
1059
1060	app << "========== END OF Hierarchy statistics ==========\n";
1061	}
1062
1063
1064	static void RemoveRayRefs(const ObjectContainer &objects)
1065	{
1066	ObjectContainer::const_iterator oit, oit_end = objects.end();
1067	for (oit = objects.begin(); oit != oit_end; ++ oit)
1068	{
1069	(*oit)->mVssRays.clear();
1070	}
1071	}
1072
1073
1074	void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects) const
1075	{
1076	switch (mObjectSpaceSubdivisionType)
1077	{
1078	case KD_BASED_OBJ_SUBDIV:
1079	{
1080	mOspTree->mOspStats.Stop();
1081	break;
1082	}
1083	case BV_BASED_OBJ_SUBDIV:
1084	{
1085	mBvHierarchy->mBvhStats.Stop();
1086	RemoveRayRefs(objects);
1087	break;
1088	}
1089	default:
1090	break;
1091	}
1092	}
1093
1094	}

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

Download in other formats: