Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp @ 2625

Revision 2625, 180.2 KB checked in by mattausch, 16 years ago (diff)
added new view cell deleted other view cell generation stuff (please use generate_viewcells.sh script) added visualizaton method for gvs

Line
1	#include "ViewCellsManager.h"
2	#include "RenderSimulator.h"
3	#include "Mesh.h"
4	#include "Triangle3.h"
5	#include "ViewCell.h"
6	#include "Environment.h"
7	#include "X3dParser.h"
8	#include "ViewCellBsp.h"
9	#include "KdTree.h"
10	#include "HierarchyManager.h"
11	#include "Exporter.h"
12	#include "VspBspTree.h"
13	#include "ViewCellsParser.h"
14	#include "Beam.h"
15	#include "VssPreprocessor.h"
16	#include "RssPreprocessor.h"
17	#include "BoundingBoxConverter.h"
18	#include "GlRenderer.h"
19	#include "ResourceManager.h"
20	#include "IntersectableWrapper.h"
21	#include "VspTree.h"
22	#include "OspTree.h"
23	#include "BvHierarchy.h"
24	#include "SamplingStrategy.h"
25	#include "SceneGraph.h"
26
27	#ifdef USE_PERFTIMER
28	#include "Timer/PerfTimer.h"
29	#endif // USE_PERFTIMER
30
31	#define USE_RAY_LENGTH_AS_CONTRIBUTION 0
32	#define DIST_WEIGHTED_CONTRIBUTION 0
33	#define SUM_RAY_CONTRIBUTIONS 1
34	#define AVG_RAY_CONTRIBUTIONS 0
35	#define CONTRIBUTION_RELATIVE_TO_PVS_SIZE 0
36	#define PVS_ADD_DIRTY 1
37
38
39	#define MYSTATS 1
40
41
42	namespace GtpVisibilityPreprocessor {
43
44
45	#ifdef USE_PERFTIMER
46	PerfTimer viewCellCastTimer;
47	PerfTimer pvsTimer;
48	PerfTimer objTimer;
49	#endif
50
51	// HACK
52	const static bool SAMPLE_AFTER_SUBDIVISION = true;
53	//const static bool CLAMP_TO_BOX = false;
54	const static bool CLAMP_TO_BOX = true;
55
56
57
58	inline static bool ilt(Intersectable obj1, Intersectable obj2)
59	{
60	return obj1->mId < obj2->mId;
61	}
62
63
64	template <typename T> class myless
65	{
66	public:
67	//bool operator() (HierarchyNode v1, HierarchyNode v2) const
68	bool operator() (T v1, T v2) const
69	{
70	return (v1->GetMergeCost() < v2->GetMergeCost());
71	}
72	};
73
74
75
76	struct SortableViewCellEntry {
77
78	SortableViewCellEntry() {}
79	SortableViewCellEntry(const float v, ViewCell *cell):mValue(v), mViewCell(cell) {}
80
81	float mValue;
82	ViewCell *mViewCell;
83
84	friend bool operator<(const SortableViewCellEntry &a, const SortableViewCellEntry &b);
85	};
86
87
88	inline bool
89	operator<(const SortableViewCellEntry &a, const SortableViewCellEntry &b) {
90	return a.mValue < b.mValue;
91	}
92
93	ViewCellsManager::ViewCellsManager(ViewCellsTree *viewCellsTree):
94	mRenderer(NULL),
95	mInitialSamples(0),
96	mConstructionSamples(0),
97	mPostProcessSamples(0),
98	mVisualizationSamples(0),
99	mTotalAreaValid(false),
100	mTotalArea(0.0f),
101	mViewCellsFinished(false),
102	mMaxPvsSize(9999999),
103	mMinPvsSize(0),
104	mMaxPvsRatio(1.0),
105	mViewCellPvsIsUpdated(false),
106	mPreprocessor(NULL),
107	mViewCellsTree(viewCellsTree),
108	mUsePredefinedViewCells(false),
109	mMixtureDistribution(NULL),
110	mEvaluationSamples(0)
111	{
112	mViewSpaceBox.Initialize();
113	ParseEnvironment();
114
115	mViewCellsTree->SetViewCellsManager(this);
116	mSamplesStat.Reset();
117	//mStats.open("mystats.log");
118
119	mRandomViewCellsHandler = new RandomViewCellsHandler(this);
120	}
121
122
123	int ViewCellsManager::CastEvaluationSamples(const int samplesPerPass,
124	VssRayContainer &passSamples)
125	{
126	static int pass = 0;
127	static int totalRays = 0;
128
129	SimpleRayContainer rays;
130	rays.reserve(samplesPerPass);
131	//passSamples.reserve(samplesPerPass * 2);
132
133	long startTime = GetTime();
134
135	cout<<"Progress :"<<totalRays / 1e6f << " M rays, " << (100.0f * totalRays) / (mEvaluationSamples + 1) << "%" << endl;
136
137	//rays.clear();
138	//passSamples.clear();
139
140	mMixtureDistribution->GenerateSamples(samplesPerPass, rays);
141
142	const bool doubleRays = true;
143	const bool pruneInvalidRays = true;
144	mPreprocessor->CastRays(rays, passSamples, doubleRays, pruneInvalidRays);
145
146	mMixtureDistribution->ComputeContributions(passSamples);
147	mMixtureDistribution->UpdateDistributions(passSamples);
148
149	Real time = TimeDiff(startTime, GetTime());
150	PrintPvsStatistics(mStats);
151
152	/*mStats <<
153	"#Pass\n" << pass ++ <<endl<<
154	"#Time\n" << time <<endl<<
155	"#TotalSamples\n" << totalRays << endl;
156	*/
157
158	totalRays += samplesPerPass;
159
160	return (int)passSamples.size();
161	}
162
163
164	ViewCellsManager::~ViewCellsManager()
165	{
166	// HACK: if view cells tree does not
167	// handle view cells, we have to do it here
168	// question: rather create view cells resource manager?
169	if (!ViewCellsTreeConstructed())
170	{
171	CLEAR_CONTAINER(mViewCells);
172	}
173	else
174	{
175	DEL_PTR(mViewCellsTree);
176	}
177
178	DEL_PTR(mMixtureDistribution);
179	DEL_PTR(mRandomViewCellsHandler);
180	}
181
182
183	void ViewCellsManager::ParseEnvironment()
184	{
185	// visualization stuff
186	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
187	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
188	Environment::GetSingleton()->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
189
190	Environment::GetSingleton()->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);
191
192	Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
193	Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
194	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
195
196	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);
197
198	Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
199	Environment::GetSingleton()->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
200
201	Environment::GetSingleton()->GetIntValue("ViewCells.active", mNumActiveViewCells);
202	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
203	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.useClipPlane", mUseClipPlaneForViz);
204	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
205	Environment::GetSingleton()->GetBoolValue("ViewCells.evaluateViewCells", mEvaluateViewCells);
206	Environment::GetSingleton()->GetBoolValue("ViewCells.showVisualization", mShowVisualization);
207	Environment::GetSingleton()->GetIntValue("ViewCells.Filter.maxSize", mMaxFilterSize);
208	Environment::GetSingleton()->GetFloatValue("ViewCells.Filter.width", mFilterWidth);
209
210	Environment::GetSingleton()->GetBoolValue("ViewCells.exportBboxesForPvs", mExportBboxesForPvs);
211	Environment::GetSingleton()->GetBoolValue("ViewCells.exportPvs", mExportPvs);
212
213	Environment::GetSingleton()->GetBoolValue("ViewCells.useKdPvs", mUseKdPvs);
214
215	char buf[100];
216	Environment::GetSingleton()->GetStringValue("ViewCells.samplingType", buf);
217
218	Environment::GetSingleton()->GetFloatValue("ViewCells.triangleWeight", mTriangleWeight);
219	Environment::GetSingleton()->GetFloatValue("ViewCells.objectWeight", mObjectWeight);
220
221	// choose mix of sampling strategies
222	if (0)
223	{
224	mStrategies.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
225	//mStrategies.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
226	}
227	else
228	{
229	mStrategies.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
230	mStrategies.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
231
232	mStrategies.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
233	//mStrategies.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
234	}
235
236	Debug << "casting strategies: ";
237	for (int i = 0; i < (int)mStrategies.size(); ++ i)
238	Debug << mStrategies[i] << " ";
239	Debug << endl;
240
241	// sampling type for view cells construction samples
242	if (strcmp(buf, "object") == 0)
243	{
244	mSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
245	}
246	else if (strcmp(buf, "box") == 0)
247	{
248	mSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
249	}
250	else if (strcmp(buf, "directional") == 0)
251	{
252	mSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
253	}
254	else if (strcmp(buf, "object_directional") == 0)
255	{
256	mSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
257	}
258	else if (strcmp(buf, "reverse_object") == 0)
259	{
260	mSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
261	}
262	/*else if (strcmp(buf, "interior") == 0)
263	{
264	mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
265	}*/
266	else
267	{
268	Debug << "error! wrong sampling type" << endl;
269	exit(0);
270	}
271
272	// sampling type for evaluation samples
273	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf);
274
275	if (strcmp(buf, "object") == 0)
276	{
277	mEvaluationSamplingType = SamplingStrategy::OBJECT_BASED_DISTRIBUTION;
278	}
279	else if (strcmp(buf, "box") == 0)
280	{
281	mEvaluationSamplingType = SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION;
282	}
283	else if (strcmp(buf, "directional") == 0)
284	{
285	mEvaluationSamplingType = SamplingStrategy::DIRECTION_BASED_DISTRIBUTION;
286	}
287	else if (strcmp(buf, "object_directional") == 0)
288	{
289	mEvaluationSamplingType = SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION;
290	}
291	else if (strcmp(buf, "reverse_object") == 0)
292	{
293	mEvaluationSamplingType = SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION;
294	}
295	else
296	{
297	mEvaluationSamplingType = -1;
298	Debug << "error! wrong sampling type" << endl;
299	exit(0);
300	}
301
302
303	/** The color code used during visualization.
304	*/
305	Environment::GetSingleton()->GetStringValue("ViewCells.Visualization.colorCode", buf);
306
307	if (strcmp(buf, "PVS") == 0)
308	mColorCode = 1;
309	else if (strcmp(buf, "MergedLeaves") == 0)
310	mColorCode = 2;
311	else if (strcmp(buf, "MergedTreeDiff") == 0)
312	mColorCode = 3;
313	else
314	mColorCode = 0;
315
316
317	Debug << "********** View Cells Manager options *************" << endl;
318	Debug << "color code: " << mColorCode << endl;
319
320	Debug << "export rays: " << mExportRays << endl;
321	Debug << "export geometry: " << mExportGeometry << endl;
322	Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
323
324	Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
325	Debug << "construction samples: " << mConstructionSamples << endl;
326	Debug << "post process samples: " << mPostProcessSamples << endl;
327	Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
328	Debug << "visualization samples: " << mVisualizationSamples << endl;
329	Debug << "construction samples per pass: " << mSamplesPerPass << endl;
330	Debug << "export to file: " << mExportViewCells << endl;
331
332	Debug << "active view cells: " << mNumActiveViewCells << endl;
333	Debug << "post process compress: " << mCompressViewCells << endl;
334	Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl;
335	Debug << "post process merge: " << mMergeViewCells << endl;
336	Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
337	Debug << "sampling type: " << mSamplingType << endl;
338	Debug << "evaluation sampling type: " << mEvaluationSamplingType << endl;
339	Debug << "show visualization: " << mShowVisualization << endl;
340	Debug << "filter width: " << mFilterWidth << endl;
341	Debug << "sample after subdivision: " << SAMPLE_AFTER_SUBDIVISION << endl;
342
343	Debug << "export bounding boxes: " << mExportBboxesForPvs << endl;
344	Debug << "export pvs for view cells: " << mExportPvs << endl;
345	Debug << "use kd pvs " << mUseKdPvs << endl;
346
347	Debug << "triangle weight: " << mTriangleWeight << endl;
348	Debug << "object weight: " << mObjectWeight << endl;
349
350	Debug << endl;
351	}
352
353
354	ViewCell *ViewCellsManager::GetViewCellById(const int id)
355	{
356	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
357
358	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
359	{
360	if ((*vit)->GetId() == id)
361	return (*vit);
362	}
363	return NULL;
364	}
365
366
367	Intersectable *ViewCellsManager::GetIntersectable(const VssRay &ray,
368	const bool isTermination) const
369	{
370	#if DYNAMIC_OBJECTS_HACK
371
372	#if USE_TRANSFORMED_MESH_INSTANCE_HACK
373	if (ray.mTerminationObject->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
374	return ray.mTerminationObject;
375	#else
376	if (ray.mTerminationObject->Type() == Intersectable::SCENEGRAPHLEAF_INTERSECTABLE)
377	return ray.mTerminationObject;
378	#endif
379
380	#endif
381	if (mUseKdPvs)
382	{
383	KdNode *node = GetPreprocessor()->
384	mKdTree->GetPvsNode(isTermination ? ray.mTermination : ray.mOrigin);
385
386	return GetPreprocessor()->mKdTree->GetOrCreateKdIntersectable(node);
387	}
388	else
389	{
390	return isTermination ? ray.mTerminationObject : ray.mOriginObject;
391	}
392	}
393
394
395	void ViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
396	{
397	GetPreprocessor()->mKdTree->CollectObjects(box, objects);
398	}
399
400
401	AxisAlignedBox3 ViewCellsManager::GetViewCellBox(ViewCell *vc)
402	{
403	Mesh *m = vc->GetMesh();
404
405	if (m)
406	{
407	m->ComputeBoundingBox();
408	return m->mBox;
409	}
410
411	AxisAlignedBox3 box;
412	box.Initialize();
413
414	if (!vc->IsLeaf())
415	{
416	ViewCellInterior vci = (ViewCellInterior ) vc;
417
418	ViewCellContainer::iterator it = vci->mChildren.begin();
419	for (; it != vci->mChildren.end(); ++it)
420	{
421	box.Include(GetViewCellBox(*it));
422	}
423	}
424
425	return box;
426	}
427
428
429	int ViewCellsManager::CastPassSamples(const int samplesPerPass,
430	const vector<int> &strategies,
431	VssRayContainer &passSamples
432	) const
433	{
434	long startTime = GetTime();
435
436	SimpleRayContainer simpleRays;
437
438	simpleRays.reserve(samplesPerPass);
439	// reserve 2 times the size because always creates double rays
440	passSamples.reserve(samplesPerPass * 2);
441
442	// create one third of each type
443	int castRays = 0;
444
445	const int numRaysPerPass = samplesPerPass / (int)strategies.size();
446	vector<int>::const_iterator iit, iit_end = strategies.end();
447
448	for (iit = strategies.begin(); iit != iit_end; ++ iit)
449	{
450	const int stype = *iit;
451	const int newRays =
452	mPreprocessor->GenerateRays(numRaysPerPass, stype, simpleRays);
453
454	cout << "cast " << newRays << " rays of strategy " << stype << endl;
455	castRays += newRays;
456	}
457
458	cout << "generated " << samplesPerPass << " samples in "
459	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
460
461	startTime = GetTime();
462
463	// shoot simple ray and add it to importance samples
464	mPreprocessor->CastRays(simpleRays, passSamples, true);
465
466	cout << "cast " << samplesPerPass << " samples in "
467	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
468
469	return (int)passSamples.size();
470	}
471
472
473	/// helper function which destroys rays or copies them into the output ray container
474	inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
475	{
476	// hack matt
477	return;
478
479	cout << "disposing samples ... ";
480	long startTime = GetTime();
481	int n = (int)rays.size();
482
483	if (outRays)
484	{
485	VssRayContainer::const_iterator it, it_end = rays.end();
486	for (it = rays.begin(); it != it_end; ++ it)
487	{
488	outRays->push_back(*it);
489	}
490	}
491	else
492	{
493	VssRayContainer::const_iterator it, it_end = rays.end();
494	for (it = rays.begin(); it != it_end; ++ it)
495	{
496	if (!(*it)->IsActive())
497	delete (*it);
498	}
499	}
500
501	cout << "finished" << endl;
502	Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
503	}
504
505
506	int ViewCellsManager::Construct(Preprocessor preprocessor, VssRayContainer outRays)
507	{
508	int numSamples = 0;
509
510	SimpleRayContainer simpleRays;
511	VssRayContainer initialSamples;
512
513	// store pointer to preprocessor for further use during construction
514	mPreprocessor = preprocessor;
515
516	// now decode distribution string
517	char mix[1024];
518	Environment::GetSingleton()->GetStringValue("RssPreprocessor.distributions", mix);
519	Debug << "using mixture distributions: " << mix << endl;
520
521	mMixtureDistribution = new MixtureDistribution(*mPreprocessor);
522	mMixtureDistribution->Construct(mix);
523
524	///////////////////////////////////////////////////////
525	//-- Initial sampling for the construction of the view cell hierarchy.
526	//-- We use uniform sampling / box based sampling.
527
528	long startTime = GetTime();
529	cout << "view cell construction: casting " << mInitialSamples << " initial samples ... " << endl;
530
531	// cast initial samples
532
533	// mix of sampling strategies
534	#if 0
535	vector<int>dummy;
536	dummy.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
537	dummy.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
538	dummy.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
539	#endif
540	CastPassSamples(mInitialSamples, mStrategies, initialSamples);
541
542	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
543
544	// construct view cells
545	ConstructSubdivision(preprocessor->mObjects, initialSamples);
546
547	// initial samples count for overall samples ...
548	numSamples += mInitialSamples;
549
550	// rays can be passed or deleted
551	disposeRays(initialSamples, outRays);
552
553	cout << "time needed for initial construction: "
554	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
555
556	Debug << "time needed for initial construction: "
557	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
558
559	// collect view cells and compute statistics
560	ResetViewCells();
561
562
563	///////////////////
564	//-- Initial hierarchy construction finished.
565	//-- We can do some stats and visualization
566
567	if (0)
568	{
569	//-- export initial view cell partition
570	Debug << "\nView cells after initial sampling:\n" << mCurrentViewCellsStats << endl;
571
572	const string filename("viewcells.wrl");
573	Exporter *exporter = Exporter::GetExporter(filename.c_str());
574
575	if (exporter)
576	{
577	cout << "exporting initial view cells (=leaves) to " << filename.c_str() << " ... ";
578
579	if (mExportGeometry)
580	{
581	exporter->ExportGeometry(preprocessor->mObjects);
582	}
583
584	exporter->SetWireframe();
585	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
586
587	delete exporter;
588	cout << "finished" << endl;
589	}
590	}
591
592
593	//////////////////////
594	//-- Cast some more sampling after initial construction.
595	//-- The additional rays can be used to gain
596	//-- some more information before the bottom-up merge
597	//-- note: guided rays could be used for this task
598
599	// time spent after construction of the initial partition
600	startTime = GetTime();
601	const int n = mConstructionSamples; //+initialSamples;
602
603	while (numSamples < n)
604	{
605	cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
606	Debug << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
607
608	VssRayContainer constructionSamples;
609
610	// cast new samples
611	numSamples += CastPassSamples(mSamplesPerPass,
612	mStrategies,
613	constructionSamples);
614
615	cout << "finished" << endl;
616	cout << "computing sample contribution for " << (int)constructionSamples.size() << " samples ... ";
617
618	// computes sample contribution of cast rays
619	if (SAMPLE_AFTER_SUBDIVISION)
620	ComputeSampleContributions(constructionSamples, true, false);
621
622	cout << "finished" << endl;
623
624	disposeRays(constructionSamples, outRays);
625	cout << "total samples: " << numSamples << endl;
626	}
627
628	if (0)
629	{
630	///////////////
631	//-- Get stats after the additional sampling step
632	//-- and before the bottom-up merge step
633
634	EvaluateViewCellsStats();
635	Debug << "\noriginal view cell partition before post process:\n"
636	<< mCurrentViewCellsStats << endl;
637
638	mRenderer->RenderScene();
639	SimulationStatistics ss;
640	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
641
642	Debug << ss << endl;
643	}
644
645	////////////////////
646	//-- post processing of the initial construction
647	//-- We can bottom-up merge the view cells in this step
648	//-- We can additionally cast some post processing sample rays.
649	//-- These rays can be used to store the view cells with the rays
650
651	VssRayContainer postProcessSamples;
652	cout << "casting " << mPostProcessSamples << " post process samples ..." << endl;
653
654	CastPassSamples(mPostProcessSamples, mStrategies, postProcessSamples);
655
656	cout << "finished post process sampling" << endl;
657	cout << "starting post processing and visualization" << endl;
658
659	// store view cells with rays for post processing?
660	const bool storeViewCells = true;
661
662	if (SAMPLE_AFTER_SUBDIVISION)
663	ComputeSampleContributions(postProcessSamples, true, storeViewCells);
664
665	PostProcess(preprocessor->mObjects, postProcessSamples);
666
667	const float secs = TimeDiff(startTime, GetTime()) * 1e-3f;
668	cout << "post processing (=merge) finished in " << secs << " secs" << endl;
669
670	Debug << "post processing time: " << secs << endl;
671	disposeRays(postProcessSamples, outRays);
672
673
674	////////////////
675	//-- Evaluation of the resulting view cell partition.
676	//-- We cast a number of new samples and measure the render cost
677
678	if (mEvaluateViewCells)
679	{
680	EvalViewCellPartition();
681	}
682
683	/////////////////
684	//-- Show some visualizations
685
686	if (mShowVisualization)
687	{
688	///////////////
689	//-- visualization rays, e.g., to show some samples in the scene
690
691	VssRayContainer visSamples;
692	int numSamples = CastPassSamples(mVisualizationSamples,
693	mStrategies,
694	visSamples);
695
696	if (SAMPLE_AFTER_SUBDIVISION)
697	ComputeSampleContributions(visSamples, true, storeViewCells);
698
699	// various visualizations
700	Visualize(preprocessor->mObjects, visSamples);
701
702	disposeRays(visSamples, outRays);
703	}
704
705	// recalculate view cells
706	EvaluateViewCellsStats();
707
708	// compress the final solution
709	if (0) CompressViewCells();
710
711	// write view cells to disc
712	if (mExportViewCells)
713	{
714	char filename[100];
715
716	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
717	ExportViewCells(filename, mExportPvs, mPreprocessor->mObjects);
718	}
719
720	return numSamples;
721	}
722
723
724	AxisAlignedPlane *ViewCellsManager::GetClipPlane()
725	{
726	return mUseClipPlaneForViz ? &mClipPlaneForViz : NULL;
727	}
728
729
730	ViewCellsManager *ViewCellsManager::LoadViewCells(const string &filename,
731	ObjectContainer &pvsObjects,
732	bool finalizeViewCells,
733	BoundingBoxConverter *bconverter)
734
735	{
736	if (!Debug.is_open()) Debug.open("debug.log");
737
738
739	if (strstr(filename.c_str(), ".bn"))
740	{
741	Debug << "binary view cells format detected" << endl;
742
743	return LoadViewCellsBinary(filename,
744	pvsObjects,
745	finalizeViewCells,
746	bconverter);
747	}
748	else
749	{
750	Debug << "xml view cells format detected" << endl;
751
752	// give just an empty container as parameter:
753	// this loading function is used in the engine, thus it
754	// does not need to load the entities the preprocessor works on
755	ObjectContainer preprocessorObjects;
756
757	return LoadViewCells(filename,
758	pvsObjects,
759	preprocessorObjects,
760	finalizeViewCells,
761	bconverter);
762	}
763	}
764
765	void ViewCellsManager::LoadIndexedBoundingBoxesBinary(IN_STREAM &stream, IndexedBoundingBoxContainer &iboxes)
766	{
767	int numBoxes;
768	stream.read(reinterpret_cast<char *>(&numBoxes), sizeof(int));
769
770	iboxes.reserve(numBoxes);
771
772	Vector3 bmin;
773	Vector3 bmax;
774	int id;
775
776	#ifdef USE_PERFTIMER
777	PerfTimer boxTimer;
778
779	boxTimer.Start();
780	boxTimer.Entry();
781	#endif
782	for (int i = 0; i < numBoxes; ++ i)
783	{
784	stream.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
785	stream.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
786	stream.read(reinterpret_cast<char *>(&id), sizeof(int));
787
788	iboxes.push_back(IndexedBoundingBox(id, AxisAlignedBox3(bmin, bmax)));
789	}
790
791
792	#ifdef USE_PERFTIMER
793	boxTimer.Exit();
794
795	Debug << numBoxes << " boxes loaded in " << boxTimer.TotalTime() << " secs" << endl;
796	#endif
797	}
798
799
800	ViewCellsManager *ViewCellsManager::LoadViewCells(const string &filename,
801	ObjectContainer &pvsObjects,
802	ObjectContainer &preprocessorObjects,
803	bool finalizeViewCells,
804	BoundingBoxConverter *bconverter)
805	{
806	ViewCellsParser parser;
807	ViewCellsManager *vm = NULL;
808
809	const long startTime = GetTime();
810	const bool success = parser.ParseViewCellsFile(filename,
811	&vm,
812	pvsObjects,
813	preprocessorObjects,
814	bconverter);
815
816	if (!success)
817	{
818	Debug << "Error: loading view cells failed!" << endl;
819	DEL_PTR(vm);
820
821	return NULL;
822	}
823
824	if (0) //hack: reset function should work, but something is wrong ..
825	{
826	vm->ResetViewCells();
827	}
828	else
829	{
830	ViewCellContainer leaves;
831
832	vm->mViewCells.clear();
833	vm->mViewCellsTree->CollectLeaves(vm->mViewCellsTree->GetRoot(), leaves);
834
835	ViewCellContainer::const_iterator it, it_end = leaves.end();
836
837	for (it = leaves.begin(); it != it_end; ++ it)
838	{
839	vm->mViewCells.push_back(*it);
840	}
841	}
842
843	vm->mViewCellsFinished = true;
844	vm->mMaxPvsSize = (int)pvsObjects.size();
845
846	if (finalizeViewCells)
847	{
848	// do some final computations, e.g.,
849	// create the meshes and compute view cell volumes
850	const bool createMeshes = true;
851	vm->FinalizeViewCells(createMeshes);
852	}
853
854	cout << (int)vm->mViewCells.size() << " view cells loaded in "
855	<< TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
856
857	Debug << (int)vm->mViewCells.size() << " view cells loaded in "
858	<< TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
859
860	return vm;
861	}
862
863
864	bool VspBspViewCellsManager::ExportViewCells(const string filename,
865	const bool exportPvs,
866	const ObjectContainer &objects)
867	{
868	// no view cells constructed yet
869	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
870	return false;
871
872	cout << "exporting view cells to xml ... ";
873
874	OUT_STREAM stream(filename.c_str());
875
876	// we need unique ids for each view cell
877	CreateUniqueViewCellIds();
878
879	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
880	stream << "<VisibilitySolution>" << endl;
881
882	if (exportPvs)
883	{
884	//-- export bounding boxes
885	stream << "<BoundingBoxes>" << endl;
886
887	if (mUseKdPvs)
888	{
889	vector<KdIntersectable *>::iterator kit, kit_end = GetPreprocessor()->mKdTree->mKdIntersectables.end();
890
891	int id = 0;
892	for (kit = GetPreprocessor()->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
893	{
894	Intersectable obj = kit;
895	const AxisAlignedBox3 box = obj->GetBox();
896
897	obj->SetId(id);
898
899	stream << "<BoundingBox" << " id=\"" << id << "\""
900	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
901	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
902	}
903	}
904	else
905	{
906	ObjectContainer::const_iterator oit, oit_end = objects.end();
907
908	for (oit = objects.begin(); oit != oit_end; ++ oit)
909	{
910	const AxisAlignedBox3 box = (*oit)->GetBox();
911
912	////////////
913	//-- the bounding boxes
914
915	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
916	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
917	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
918	}
919	}
920
921	stream << "</BoundingBoxes>" << endl;
922	}
923
924
925	/////////////
926	//-- export the view cells and the pvs
927
928	const int numViewCells = mCurrentViewCellsStats.viewCells;
929	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
930
931	mViewCellsTree->Export(stream, exportPvs);
932
933	stream << "</ViewCells>" << endl;
934
935
936	//////////
937	//-- export the view space hierarchy
938
939	stream << "<ViewSpaceHierarchy type=\"bsp\""
940	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
941	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
942
943	mVspBspTree->Export(stream);
944	stream << "</ViewSpaceHierarchy>" << endl;
945
946	stream << "</VisibilitySolution>" << endl;
947
948	stream.close();
949	cout << "finished" << endl;
950
951	return true;
952	}
953
954
955	void ViewCellsManager::EvalViewCellHistogram(const string filename,
956	const int nViewCells)
957	{
958	std::ofstream outstream;
959	outstream.open(filename.c_str());
960
961	ViewCellContainer viewCells;
962
963	// the collect best viewcells does not work?
964	mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
965
966	float maxRenderCost, minRenderCost;
967
968	// sort by render cost
969	sort(viewCells.begin(), viewCells.end(), SmallerRenderCost);
970
971	minRenderCost = viewCells.front()->GetRenderCost();
972	maxRenderCost = viewCells.back()->GetRenderCost();
973
974	Debug << "histogram min rc: " << minRenderCost << " max rc: " << maxRenderCost << endl;
975
976	int histoIntervals;
977	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
978	const int intervals = min(histoIntervals, (int)viewCells.size());
979
980	int histoMaxVal;
981	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
982	maxRenderCost = min((float)histoMaxVal, maxRenderCost);
983
984
985	const float range = maxRenderCost - minRenderCost;
986	const float stepSize = range / (float)intervals;
987
988	float currentRenderCost = minRenderCost;//(int)ceil(minRenderCost);
989
990	const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
991	const float totalVol = GetViewSpaceBox().GetVolume();
992	//const float totalVol = mViewCellsTree->GetRoot()->GetVolume();
993
994	int j = 0;
995	int i = 0;
996
997	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
998
999	// count for integral
1000	float volSum = 0;
1001	int smallerCostSum = 0;
1002
1003	// note can skip computations for view cells already
1004	// evaluated and delete them from vector ...
1005	while (1)
1006	{
1007	// count for histogram value
1008	float volDif = 0;
1009	int smallerCostDif = 0;
1010
1011	while ((i < (int)viewCells.size()) && (viewCells[i]->GetRenderCost() < currentRenderCost))
1012	{
1013	volSum += viewCells[i]->GetVolume();
1014	volDif += viewCells[i]->GetVolume();
1015
1016	++ i;
1017	++ smallerCostSum;
1018	++ smallerCostDif;
1019	}
1020
1021	if ((i >= (int)viewCells.size()) \|\| (currentRenderCost >= maxRenderCost))
1022	break;
1023
1024	const float rcRatio = currentRenderCost / maxRenderCost;
1025	const float volRatioSum = volSum / totalVol;
1026	const float volRatioDif = volDif / totalVol;
1027
1028	outstream << "#Pass\n" << j ++ << endl;
1029	outstream << "#RenderCostRatio\n" << rcRatio << endl;
1030	outstream << "#WeightedCost\n" << currentRenderCost / totalVol << endl;
1031	outstream << "#ViewCellsDif\n" << smallerCostDif << endl;
1032	outstream << "#ViewCellsSum\n" << smallerCostSum << endl;
1033	outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
1034	outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
1035
1036	// increase current render cost
1037	currentRenderCost += stepSize;
1038	}
1039
1040	outstream.close();
1041	}
1042
1043	void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename,
1044	const int nViewCells)
1045	{
1046	std::ofstream outstream;
1047	outstream.open(filename.c_str());
1048
1049	ViewCellContainer viewCells;
1050
1051	#ifdef USE_BIT_PVS
1052	cout << "objects size: " << (int)ObjectPvsIterator::sObjects.size() << endl;
1053	cout << "pvs size: " << ObjectPvs::sPvsSize << endl;
1054	#endif
1055
1056	// $$ JB hack - the collect best viewcells does not work?
1057	#if 0
1058	mViewCellsTree->CollectBestViewCellSet(viewCells, nViewCells);
1059	#else
1060	viewCells = mViewCells;
1061	#endif
1062
1063	ViewCellContainer::iterator it = viewCells.begin(), it_end = viewCells.end();
1064
1065	for (; it != it_end; ++it)
1066	{
1067	(*it)->UpdatePvsCost();
1068	}
1069
1070	float maxPvs, maxVal, minVal;
1071
1072	// sort by pvs size
1073	sort(viewCells.begin(), viewCells.end(), SmallerPvs);
1074
1075	maxPvs = viewCells.back()->GetTrianglesInPvs();
1076	minVal = 0;
1077
1078	// hack: normalize pvs size
1079	int histoMaxVal;
1080	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
1081	maxVal = max((float)histoMaxVal, maxPvs);
1082
1083	Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal
1084	<< " real maxpvs " << maxPvs << endl;
1085
1086	int histoIntervals;
1087	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
1088	const int intervals = min(histoIntervals, (int)viewCells.size());
1089
1090	const float range = maxVal - minVal;
1091	int stepSize = (int)(range / intervals);
1092
1093	// set step size to avoid endless loop
1094	if (!stepSize) stepSize = 1;
1095
1096	Debug << "intervals " << histoIntervals << endl;
1097	Debug << "stepsize: " << stepSize << endl;
1098	cout << "intervals " << histoIntervals << endl;
1099	cout << "stepsize: " << stepSize << endl;
1100
1101	const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
1102	const float totalVol = GetViewSpaceBox().GetVolume();
1103
1104	float currentPvs = minVal;
1105
1106	int i = 0;
1107	int j = 0;
1108	float volSum = 0;
1109	int smallerSum = 0;
1110
1111	it = viewCells.begin();
1112
1113	for (int j = 0; j < intervals; ++ j)
1114	{
1115	float volDif = 0;
1116	int smallerDif = 0;
1117
1118	while ((i < (int)viewCells.size()) &&
1119	(viewCells[i]->GetTrianglesInPvs() < currentPvs))
1120	{
1121	volDif += viewCells[i]->GetVolume();
1122	volSum += viewCells[i]->GetVolume();
1123
1124	++ i;
1125	++ smallerDif;
1126	++ smallerSum;
1127	}
1128
1129	const float volRatioDif = volDif / totalVol;
1130	const float volRatioSum = volSum / totalVol;
1131
1132	outstream << "#Pass\n" << j << endl;
1133	outstream << "#Pvs\n" << currentPvs << endl;
1134	outstream << "#ViewCellsDif\n" << smallerDif << endl;
1135	outstream << "#ViewCellsSum\n" << smallerSum << endl;
1136	outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
1137	outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
1138
1139	//-- increase current pvs size to define next interval
1140	currentPvs += stepSize;
1141	}
1142
1143	outstream.close();
1144	}
1145
1146
1147	void ViewCellsManager::EvalViewCellHistogramForPvsSize(const string filename,
1148	ViewCellContainer &viewCells)
1149	{
1150	std::ofstream outstream;
1151	outstream.open(filename.c_str());
1152
1153	float maxPvs, maxVal, minVal;
1154
1155	// sort by pvs size
1156	sort(viewCells.begin(), viewCells.end(), SmallerPvs);
1157
1158	maxPvs = viewCells.back()->GetTrianglesInPvs();
1159	minVal = 0;
1160
1161	// hack: normalize pvs size
1162	int histoMaxVal;
1163	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.maxValue", histoMaxVal);
1164	maxVal = max((float)histoMaxVal, maxPvs);
1165
1166	Debug << "histogram minpvssize: " << minVal << " maxpvssize: " << maxVal
1167	<< " real maxpvs " << maxPvs << endl;
1168
1169	int histoIntervals;
1170	Environment::GetSingleton()->GetIntValue("Preprocessor.histogram.intervals", histoIntervals);
1171	const int intervals = min(histoIntervals, (int)viewCells.size());
1172
1173	const float range = maxVal - minVal;
1174	int stepSize = (int)(range / intervals);
1175
1176	// set step size to avoid endless loop
1177	if (!stepSize) stepSize = 1;
1178
1179	Debug << "intervals " << histoIntervals << endl;
1180	Debug << "stepsize: " << stepSize << endl;
1181	cout << "intervals " << histoIntervals << endl;
1182	cout << "stepsize: " << stepSize << endl;
1183
1184	const float totalRenderCost = mViewCellsTree->GetRoot()->GetRenderCost();
1185	const float totalVol = GetViewSpaceBox().GetVolume();
1186
1187	float currentPvs = minVal;
1188
1189	int i = 0;
1190	int j = 0;
1191	float volSum = 0;
1192	int smallerSum = 0;
1193
1194	//ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
1195
1196	for (int j = 0; j < intervals; ++ j)
1197	{
1198	float volDif = 0;
1199	int smallerDif = 0;
1200
1201	while ((i < (int)viewCells.size()) &&
1202	(viewCells[i]->GetTrianglesInPvs() < currentPvs))
1203	{
1204	volDif += viewCells[i]->GetVolume();
1205	volSum += viewCells[i]->GetVolume();
1206
1207	++ i;
1208	++ smallerDif;
1209	++ smallerSum;
1210	}
1211
1212	// if (0 && (i < (int)viewCells.size()))
1213	// Debug << "new pvs cost increase: " << mViewCellsTree->GetTrianglesInPvs(viewCells[i])
1214	// << " " << currentPvs << endl;
1215
1216	const float volRatioDif = volDif / totalVol;
1217	const float volRatioSum = volSum / totalVol;
1218
1219	outstream << "#Pass\n" << j << endl;
1220	outstream << "#Pvs\n" << currentPvs << endl;
1221	outstream << "#ViewCellsDif\n" << smallerDif << endl;
1222	outstream << "#ViewCellsSum\n" << smallerSum << endl;
1223	outstream << "#VolumeDif\n" << volRatioDif << endl << endl;
1224	outstream << "#VolumeSum\n" << volRatioSum << endl << endl;
1225
1226	//-- increase current pvs size to define next interval
1227	currentPvs += stepSize;
1228	}
1229
1230	outstream.close();
1231	}
1232
1233
1234	bool ViewCellsManager::GetExportPvs() const
1235	{
1236	return mExportPvs;
1237	}
1238
1239
1240	void ViewCellsManager::ResetPvs()
1241	{
1242	if (ViewCellsTreeConstructed())
1243	{
1244	mViewCellsTree->ResetPvs();
1245	}
1246	else
1247	{
1248	cout << "view cells tree not constructed" << endl;
1249	}
1250	}
1251
1252
1253	void ViewCellsManager::ExportStats(const string &fileName)
1254	{
1255	mViewCellsTree->ExportStats(fileName);
1256	}
1257
1258
1259	void ViewCellsManager::EvalViewCellPartition()
1260	{
1261	int samplesPerPass;
1262	int numSamples;
1263	int castSamples = 0;
1264	char str[64];
1265	int oldSamples = 0;
1266
1267	int samplesForStats;
1268
1269	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
1270	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
1271	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
1272
1273	char statsPrefix[100];
1274	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
1275
1276	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
1277	Debug << "view cell evaluation samples: " << numSamples << endl;
1278	Debug << "view cell stats prefix: " << statsPrefix << endl;
1279
1280	cout << "reseting pvs ... ";
1281
1282	const bool startFromZero = true;
1283
1284	// reset pvs and start over from zero
1285	if (startFromZero)
1286	{
1287	mViewCellsTree->ResetPvs();
1288	}
1289	else // start from current sampless
1290	{
1291	// statistics before casting more samples
1292	cout << "compute new statistics ... ";
1293	sprintf(str, "-%09d-eval.log", castSamples);
1294	string fName = string(statsPrefix) + string(str);
1295
1296	mViewCellsTree->ExportStats(fName);
1297	cout << "finished" << endl;
1298	}
1299
1300	cout << "finished" << endl;
1301	cout << "Evaluating view cell partition ... " << endl;
1302
1303	while (castSamples < numSamples)
1304	{
1305	///////////////
1306	//-- we have to use uniform sampling strategy for construction rays
1307
1308	VssRayContainer evaluationSamples;
1309	const int samplingType = mEvaluationSamplingType;
1310
1311	long startTime = GetTime();
1312
1313	cout << "casting " << samplesPerPass << " samples ... ";
1314	Debug << "casting " << samplesPerPass << " samples ... ";
1315
1316	CastPassSamples(samplesPerPass, mStrategies, evaluationSamples);
1317
1318	castSamples += samplesPerPass;
1319
1320	Real timeDiff = TimeDiff(startTime, GetTime());
1321
1322	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
1323	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
1324
1325	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
1326	Debug << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
1327
1328	startTime = GetTime();
1329
1330	ComputeSampleContributions(evaluationSamples, true, false);
1331
1332	timeDiff = TimeDiff(startTime, GetTime());
1333	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
1334	Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
1335
1336	if ((castSamples >= samplesForStats + oldSamples) \|\| (castSamples >= numSamples))
1337	{
1338	oldSamples += samplesForStats;
1339
1340	///////////
1341	//-- output stats
1342
1343	sprintf(str, "-%09d-eval.log", castSamples);
1344	string fileName = string(statsPrefix) + string(str);
1345
1346	///////////////
1347	//-- propagate pvs or pvs size information
1348
1349	startTime = GetTime();
1350	ObjectPvs pvs;
1351
1352	cout << "updating pvs for evaluation ... " << endl;
1353
1354	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);
1355
1356	timeDiff = TimeDiff(startTime, GetTime());
1357	cout << "finished updating the pvs in " << timeDiff * 1e-3 << " secs" << endl;
1358	Debug << "pvs evaluated in " << timeDiff * 1e-3 << " secs" << endl;
1359
1360	startTime = GetTime();
1361	cout << "compute new statistics ... " << endl;
1362
1363	ExportStats(fileName);
1364
1365	timeDiff = TimeDiff(startTime, GetTime());
1366	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
1367	Debug << "statistis computed in " << timeDiff * 1e-3 << " secs" << endl;
1368	}
1369
1370	disposeRays(evaluationSamples, NULL);
1371	}
1372
1373
1374	////////////
1375	//-- histogram
1376
1377	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
1378	bool useHisto;
1379	int histoStepSize;
1380
1381	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
1382	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
1383
1384	if (useHisto)
1385	{
1386	// evaluate view cells in a histogram
1387	char s[64];
1388
1389	for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
1390	{
1391	string filename;
1392
1393	cout << "computing histogram for " << pass << " view cells" << endl;
1394	#if 0
1395	//-- evaluate histogram for render cost
1396	sprintf(s, "-%09d-histo.log", pass);
1397	filename = string(statsPrefix) + string(s);
1398
1399	EvalViewCellHistogram(filename, pass);
1400
1401	#endif
1402	//////////////////////////////////////////
1403	//-- evaluate histogram for pvs size
1404
1405	cout << "computing pvs histogram for " << pass << " view cells" << endl;
1406
1407	sprintf(s, "-%09d-histo-pvs.log", pass);
1408	filename = string(statsPrefix) + string(s);
1409
1410	EvalViewCellHistogram(filename, pass);
1411	// EvalViewCellHistogramForPvsSize(filename, pass);
1412	}
1413	}
1414	}
1415
1416
1417	inline float EvalMergeCost(ViewCell root, ViewCell candidate)
1418	{
1419	return root->GetPvs().GetPvsHomogenity(candidate->GetPvs());
1420	}
1421
1422
1423	/// Returns index of the best view cells of the neighborhood
1424	static int GetBestViewCellIdx(ViewCell *root, const ViewCellContainer &neighborhood)
1425	{
1426	int bestViewCellIdx = 0;
1427
1428	float mergeCost = Limits::Infinity;
1429	int i = 0;
1430
1431	ViewCellContainer::const_iterator vit, vit_end = neighborhood.end();
1432
1433	for (vit = neighborhood.begin(); vit != vit_end; ++ vit, ++ i)
1434	{
1435	const float mc = EvalMergeCost(root, *vit);
1436
1437	if (mc < mergeCost)
1438	{
1439	mergeCost = mc;
1440	bestViewCellIdx = i;
1441	}
1442	}
1443
1444	return bestViewCellIdx;
1445	}
1446
1447
1448	void ViewCellsManager::SetMaxFilterSize(const int size)
1449	{
1450	mMaxFilterSize = size;
1451	}
1452
1453
1454	float ViewCellsManager::ComputeRenderCost(const int tri, const int obj) //const
1455	{
1456	return max((float)tri * mTriangleWeight, (float)obj * mObjectWeight);
1457	}
1458
1459
1460	ViewCell ViewCellsManager::ConstructLocalMergeTree(ViewCell currentViewCell,
1461	const ViewCellContainer &viewCells)
1462	{
1463	ViewCell *root = currentViewCell;
1464	ViewCellContainer neighborhood = viewCells;
1465
1466	ViewCellContainer::const_iterator it, it_end = neighborhood.end();
1467
1468	const int n = min(mMaxFilterSize, (int)neighborhood.size());
1469
1470	/////////////////
1471	//-- use priority queue to merge leaf pairs
1472
1473	for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
1474	{
1475	const int bestViewCellIdx = GetBestViewCellIdx(root, neighborhood);
1476
1477	ViewCell *bestViewCell = neighborhood[bestViewCellIdx];
1478
1479	// remove from vector
1480	swap(neighborhood[bestViewCellIdx], neighborhood.back());
1481	neighborhood.pop_back();
1482
1483	if (!bestViewCell \|\| !root)
1484	cout << "warning!!" << endl;
1485
1486	// create new root of the hierarchy
1487	root = MergeViewCells(root, bestViewCell);
1488	}
1489
1490	return root;
1491	}
1492
1493
1494
1495	ViewCell * ViewCellsManager::ConstructLocalMergeTree2(ViewCell *currentViewCell,
1496	const ViewCellContainer &viewCells)
1497	{
1498
1499	vector<SortableViewCellEntry> neighborhood(viewCells.size());
1500	int i, j;
1501	for (i = 0, j = 0; i < viewCells.size(); i++) {
1502	if (viewCells[i] != currentViewCell)
1503	neighborhood[j++] = SortableViewCellEntry(
1504	EvalMergeCost(currentViewCell, viewCells[i]),
1505	viewCells[i]);
1506	}
1507	neighborhood.resize(j);
1508
1509	sort(neighborhood.begin(), neighborhood.end());
1510
1511	ViewCell *root = currentViewCell;
1512
1513	vector<SortableViewCellEntry>::const_iterator it, it_end = neighborhood.end();
1514
1515	const int n = min(mMaxFilterSize, (int)neighborhood.size());
1516	//-- use priority queue to merge leaf pairs
1517
1518	//cout << "neighborhood: " << neighborhood.size() << endl;
1519	for (int nMergedViewCells = 0; nMergedViewCells < n; ++ nMergedViewCells)
1520	{
1521	ViewCell *bestViewCell = neighborhood[nMergedViewCells].mViewCell;
1522	//cout <<nMergedViewCells<<":"<<"homogenity=" <<neighborhood[nMergedViewCells].mValue<<endl;
1523	// create new root of the hierarchy
1524	root = MergeViewCells(root, bestViewCell);
1525	// set negative cost so that this view cell gets deleted
1526	root->SetMergeCost(-1.0f);
1527	}
1528
1529	return root;
1530	}
1531
1532	void
1533	ViewCellsManager::DeleteLocalMergeTree(ViewCell *vc
1534	) const
1535	{
1536	if (!vc->IsLeaf() && vc->GetMergeCost() < 0.0f)
1537	{
1538	ViewCellInterior vci = (ViewCellInterior ) vc;
1539	ViewCellContainer::const_iterator it, it_end = vci->mChildren.end();
1540
1541	for (it = vci->mChildren.begin(); it != it_end; ++ it)
1542	DeleteLocalMergeTree(*it);
1543
1544	vci->mChildren.clear();
1545
1546	delete vci;
1547	}
1548	}
1549
1550
1551	bool ViewCellsManager::CheckValidity(ViewCell *vc,
1552	int minPvsSize,
1553	int maxPvsSize) const
1554	{
1555
1556	const float pvsCost = vc->GetPvs().EvalPvsCost();
1557
1558	if ((pvsCost > maxPvsSize) \|\| (pvsCost < minPvsSize))
1559	{
1560	cout << "err: " << pvsCost << " " << minPvsSize << " " << maxPvsSize << endl;
1561	return false;
1562	}
1563
1564	return true;
1565	}
1566
1567
1568	int ViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
1569	ViewCellContainer &viewCells) const
1570	{
1571	return 0;
1572	};
1573
1574
1575	AxisAlignedBox3 ViewCellsManager::GetFilterBBox(const Vector3 &viewPoint,
1576	const float width) const
1577	{
1578	float w = Magnitude(mViewSpaceBox.Size())*width;
1579	Vector3 min = viewPoint - w * 0.5f;
1580	Vector3 max = viewPoint + w * 0.5f;
1581
1582	return AxisAlignedBox3(min, max);
1583	}
1584
1585
1586	void ViewCellsManager::GetPrVS(const Vector3 &viewPoint,
1587	PrVs &prvs,
1588	const float filterWidth)
1589	{
1590	ViewCell *currentViewCell = GetViewCell(viewPoint);
1591
1592	if (mMaxFilterSize < 1) {
1593	prvs.mViewCell = currentViewCell;
1594	return;
1595	}
1596
1597	const AxisAlignedBox3 box = GetFilterBBox(viewPoint, filterWidth);
1598
1599	if (currentViewCell)
1600	{
1601	ViewCellContainer viewCells;
1602	ComputeBoxIntersections(box, viewCells);
1603
1604	ViewCell *root = ConstructLocalMergeTree2(currentViewCell, viewCells);
1605	prvs.mViewCell = root;
1606
1607	}
1608	else
1609	{
1610	prvs.mViewCell = NULL;
1611	//prvs.mPvs = root->GetPvs();
1612	}
1613	}
1614
1615
1616	bool ViewCellsManager::ViewCellsTreeConstructed() const
1617	{
1618	return (mViewCellsTree && mViewCellsTree->GetRoot());
1619	}
1620
1621
1622	void ViewCellsManager::SetValidity(ViewCell *vc,
1623	int minPvs,
1624	int maxPvs) const
1625	{
1626	vc->SetValid(CheckValidity(vc, minPvs, maxPvs));
1627	}
1628
1629
1630	void
1631	ViewCellsManager::SetValidity(
1632	int minPvsSize,
1633	int maxPvsSize) const
1634	{
1635	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1636
1637
1638	for (it = mViewCells.begin(); it != it_end; ++ it)
1639	{
1640	SetValidity(*it, minPvsSize, maxPvsSize);
1641	}
1642	}
1643
1644	void
1645	ViewCellsManager::SetValidityPercentage(
1646	const float minValid,
1647	const float maxValid
1648	)
1649	{
1650	ObjectPvs dummyPvs;
1651	// update pvs sizes
1652	for (int i = 0; i < (int)mViewCells.size(); ++ i) {
1653	UpdatePvsForEvaluation(mViewCells[i], dummyPvs);
1654	}
1655
1656	sort(mViewCells.begin(), mViewCells.end(), SmallerPvs);
1657
1658	int start = (int)(mViewCells.size() * minValid);
1659	int end = (int)(mViewCells.size() * maxValid);
1660
1661	for (int i = 0; i < (int)mViewCells.size(); ++ i)
1662	{
1663	// cout<<"pvs:"<<mViewCells[i]->GetCachedPvsCost()<<endl;
1664	mViewCells[i]->SetValid(i >= start && i <= end);
1665	}
1666	}
1667
1668
1669	int ViewCellsManager::CountValidViewcells() const
1670	{
1671	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1672	int valid = 0;
1673
1674	for (it = mViewCells.begin(); it != it_end; ++ it)
1675	{
1676	if ((*it)->GetValid())
1677	++ valid;
1678	}
1679
1680	return valid;
1681	}
1682
1683
1684	bool ViewCellsManager::LoadViewCellsGeometry(const string filename,
1685	const bool extrudeBaseTriangles)
1686	{
1687	/// we use predefined view cells from now on
1688	mUsePredefinedViewCells = true;
1689	X3dParser parser;
1690
1691	if (extrudeBaseTriangles)
1692	{
1693	Environment::GetSingleton()->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
1694	const bool success = parser.ParseFile(filename, *this);
1695
1696	if (!success)
1697	return false;
1698	}
1699	else
1700	{
1701	// hack: use standard mesh loading
1702	// create temporary scene graph for loading the view cells geometry
1703	// note: delete the meshes as they are created two times for transformed mesh instances.
1704	SceneGraphLeaf *root = new SceneGraphLeaf();
1705	const bool success = parser.ParseFile(filename, root, true);
1706
1707	if (!success)
1708	{
1709	DEL_PTR(root);
1710	return false;
1711	}
1712
1713	ObjectContainer::const_iterator oit, oit_end = root->mGeometry.end();
1714
1715	for (oit = root->mGeometry.begin(); oit != oit_end; ++ oit)
1716	{
1717	Mesh *mesh;
1718	if ((*oit)->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
1719	{
1720	TransformedMeshInstance mit = static_cast<TransformedMeshInstance >(*oit);
1721	mesh = MeshManager::GetSingleton()->CreateResource();
1722	mit->GetTransformedMesh(*mesh);
1723	}
1724	else if ((*oit)->Type() == Intersectable::MESH_INSTANCE)
1725	{
1726	MeshInstance mit = static_cast<MeshInstance >(*oit);
1727	mesh = mit->GetMesh();
1728	}
1729	mesh->ComputeBoundingBox();
1730	mViewCells.push_back(GenerateViewCell(mesh));
1731	}
1732
1733	DEL_PTR(root);
1734	}
1735
1736	// set view space box to bounding box of the view cells
1737	AxisAlignedBox3 bbox;
1738	bbox.Initialize();
1739	ViewCellContainer::iterator it = mViewCells.begin(), it_end = mViewCells.end();
1740
1741	for (; it != it_end; ++ it)
1742	{
1743	bbox.Include((*it)->GetMesh()->mBox);
1744	}
1745
1746	SetViewSpaceBox(bbox);
1747	cout << "view space box: " << bbox << endl;
1748	cout << "generated " << (int)mViewCells.size() << " view cells using the geometry " << filename << endl;
1749
1750	return true;
1751	}
1752
1753
1754	bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
1755	{
1756	viewPoint = mViewSpaceBox.GetRandomPoint();
1757	return true;
1758	}
1759
1760	bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint, const Vector3 &params) const
1761	{
1762	viewPoint = mViewSpaceBox.GetRandomPoint(params);
1763	return true;
1764	}
1765
1766
1767	float ViewCellsManager::GetViewSpaceVolume()
1768	{
1769	return mViewSpaceBox.GetVolume() * (2.0f * sqr((float)M_PI));
1770	}
1771
1772
1773	bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
1774	{
1775	if (!ViewCellsConstructed())
1776	{
1777	return mViewSpaceBox.IsInside(viewPoint);
1778	}
1779	else
1780	{
1781	if (!mViewSpaceBox.IsInside(viewPoint))
1782	return false;
1783
1784	ViewCell *viewcell = GetViewCell(viewPoint);
1785
1786	if (!viewcell \|\| !viewcell->GetValid())
1787	return false;
1788	}
1789
1790	return true;
1791	}
1792
1793
1794	float
1795	ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
1796	const bool addContributions,
1797	const bool storeViewCells,
1798	const bool useHitObjects)
1799	{
1800	float sum = 0.0f;
1801
1802	VssRayContainer::const_iterator it, it_end = rays.end();
1803
1804	for (it = rays.begin(); it != it_end; ++ it)
1805	{
1806	if (!ViewCellsConstructed())
1807	{
1808	// view cells not constructed yet =>
1809	// just take the lenghts of the rays as contributions
1810	if ((*it)->mTerminationObject)
1811	{
1812	sum += (*it)->Length();
1813	}
1814	}
1815	else
1816	{
1817	sum += ComputeSampleContribution((it), addContributions, storeViewCells, useHitObjects);
1818	}
1819	}
1820
1821	#ifdef USE_PERFTIMER
1822	cout << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
1823	Debug << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
1824
1825	cout << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
1826	Debug << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
1827	#endif
1828	return sum;
1829	}
1830
1831
1832	void ViewCellsManager::EvaluateViewCellsStats()
1833	{
1834	mCurrentViewCellsStats.Reset();
1835	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1836
1837	for (it = mViewCells.begin(); it != it_end; ++ it)
1838	{
1839	mViewCellsTree->UpdateViewCellsStats(*it, mCurrentViewCellsStats);
1840	}
1841	}
1842
1843
1844	void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
1845	float &expectedRenderCost,
1846	float &deviation,
1847	float &variance,
1848	float &totalCost,
1849	float &avgRenderCost)
1850	{
1851	////////////
1852	//-- compute expected value
1853
1854	totalRenderCost = 0;
1855	totalCost = 0;
1856
1857	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1858
1859	for (it = mViewCells.begin(); it != it_end; ++ it)
1860	{
1861	ViewCell vc = it;
1862	totalRenderCost += vc->GetPvs().EvalPvsCost() * vc->GetVolume();
1863	totalCost += (int)vc->GetPvs().EvalPvsCost();
1864	}
1865
1866	// normalize with view space box
1867	totalRenderCost /= mViewSpaceBox.GetVolume();
1868	expectedRenderCost = totalRenderCost / (float)mViewCells.size();
1869	avgRenderCost = totalCost / (float)mViewCells.size();
1870
1871
1872	///////////
1873	//-- compute standard defiation
1874
1875	variance = 0;
1876	deviation = 0;
1877
1878	for (it = mViewCells.begin(); it != it_end; ++ it)
1879	{
1880	ViewCell vc = it;
1881
1882	float renderCost = vc->GetPvs().EvalPvsCost() * vc->GetVolume();
1883	float dev;
1884
1885	if (1)
1886	dev = fabs(avgRenderCost - (float)vc->GetPvs().EvalPvsCost());
1887	else
1888	dev = fabs(expectedRenderCost - renderCost);
1889
1890	deviation += dev;
1891	variance += dev * dev;
1892	}
1893
1894	variance /= (float)mViewCells.size();
1895	deviation /= (float)mViewCells.size();
1896	}
1897
1898
1899	float ViewCellsManager::GetArea(ViewCell *viewCell) const
1900	{
1901	return viewCell->GetArea();
1902	}
1903
1904
1905	float ViewCellsManager::GetVolume(ViewCell *viewCell) const
1906	{
1907	return viewCell->GetVolume();
1908	}
1909
1910
1911	void ViewCellsManager::CompressViewCells()
1912	{
1913	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
1914	return;
1915
1916	////////////
1917	//-- compression
1918
1919	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
1920
1921	cout << "number of entries before compress: " << pvsEntries << endl;
1922	Debug << "number of entries before compress: " << pvsEntries << endl;
1923
1924	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
1925
1926	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
1927
1928	Debug << "number of entries after compress: " << pvsEntries << endl;
1929	cout << "number of entries after compress: " << pvsEntries << endl;
1930	}
1931
1932
1933	ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
1934	const float height) const
1935	{
1936	// one mesh per view cell
1937	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
1938	//ootl::hash_map<int, Intersectable *> hmap(-2, NULL);
1939	////////////
1940	//-- construct prism
1941
1942	// bottom
1943	mesh->mFaces.push_back(new Face(2,1,0));
1944	// top
1945	mesh->mFaces.push_back(new Face(3,4,5));
1946	// sides
1947	mesh->mFaces.push_back(new Face(1, 4, 3, 0));
1948	mesh->mFaces.push_back(new Face(2, 5, 4, 1));
1949	mesh->mFaces.push_back(new Face(3, 5, 2, 0));
1950
1951
1952	/////////////
1953	//-- extrude new vertices for top of prism
1954
1955	const Vector3 triNorm = baseTri.GetNormal();
1956	Triangle3 topTri;
1957
1958	// add base vertices and calculate top vertices
1959	for (int i = 0; i < 3; ++ i)
1960	{
1961	mesh->mVertices.push_back(baseTri.mVertices[i]);
1962	}
1963
1964	// add top vertices
1965	for (int i = 0; i < 3; ++ i)
1966	{
1967	mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
1968	}
1969
1970	// do we have to preprocess this mesh (we don't want to trace view cells!)?
1971	mesh->ComputeBoundingBox();
1972
1973	return GenerateViewCell(mesh);
1974	}
1975
1976
1977	void ViewCellsManager::FinalizeViewCells(const bool createMesh)
1978	{
1979	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1980
1981	// volume and area of the view cells are recomputed
1982	// a view cell mesh is created
1983	for (it = mViewCells.begin(); it != it_end; ++ it)
1984	{
1985	Finalize(*it, createMesh);
1986	}
1987
1988	mViewCellsTree->AssignRandomColors();
1989
1990	mTotalAreaValid = false;
1991	}
1992
1993
1994	void ViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
1995	{
1996	// implemented in subclasses
1997	}
1998
1999
2000	/** fast way of merging 2 view cells.
2001	*/
2002	ViewCellInterior ViewCellsManager::MergeViewCells(ViewCell left, ViewCell *right) const
2003	{
2004	// generate parent view cell
2005	ViewCellInterior *vc = new ViewCellInterior();
2006
2007	vc->GetPvs().Clear();
2008	ObjectPvs::Merge(vc->GetPvs(), left->GetPvs(), right->GetPvs());
2009
2010	// set only links to child (not from child to parent, maybe not wished!!)
2011	vc->mChildren.push_back(left);
2012	vc->mChildren.push_back(right);
2013
2014	// update pvs size
2015	UpdateScalarPvsSize(vc, vc->GetPvs().EvalPvsCost(), vc->GetPvs().GetSize());
2016
2017	return vc;
2018	}
2019
2020
2021	ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
2022	{
2023	ViewCellInterior *vc = new ViewCellInterior();
2024	ViewCellContainer::const_iterator it, it_end = children.end();
2025
2026	for (it = children.begin(); it != it_end; ++ it)
2027	{
2028	vc->GetPvs().MergeInPlace((*it)->GetPvs());
2029
2030	vc->mChildren.push_back(*it);
2031	}
2032
2033	return vc;
2034	}
2035
2036
2037	void ViewCellsManager::SetRenderer(Renderer *renderer)
2038	{
2039	mRenderer = renderer;
2040	}
2041
2042
2043	ViewCellsTree *ViewCellsManager::GetViewCellsTree()
2044	{
2045	return mViewCellsTree;
2046	}
2047
2048
2049	void ViewCellsManager::SetVisualizationSamples(const int visSamples)
2050	{
2051	mVisualizationSamples = visSamples;
2052	}
2053
2054
2055	void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
2056	{
2057	mConstructionSamples = constructionSamples;
2058	}
2059
2060
2061	void ViewCellsManager::SetInitialSamples(const int initialSamples)
2062	{
2063	mInitialSamples = initialSamples;
2064	}
2065
2066
2067	void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
2068	{
2069	mPostProcessSamples = postProcessSamples;
2070	}
2071
2072
2073	int ViewCellsManager::GetVisualizationSamples() const
2074	{
2075	return mVisualizationSamples;
2076	}
2077
2078
2079	int ViewCellsManager::GetConstructionSamples() const
2080	{
2081	return mConstructionSamples;
2082	}
2083
2084
2085	int ViewCellsManager::GetPostProcessSamples() const
2086	{
2087	return mPostProcessSamples;
2088	}
2089
2090
2091	void ViewCellsManager::UpdatePvs()
2092	{
2093	if (mViewCellPvsIsUpdated \|\| !ViewCellsTreeConstructed())
2094	return;
2095
2096	mViewCellPvsIsUpdated = true;
2097
2098	ViewCellContainer leaves;
2099	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
2100
2101	ViewCellContainer::const_iterator it, it_end = leaves.end();
2102
2103	for (it = leaves.begin(); it != it_end; ++ it)
2104	{
2105	mViewCellsTree->PropagatePvs(*it);
2106	}
2107	}
2108
2109
2110	void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
2111	{
2112	// update pvs of view cells tree if necessary
2113	if (0) UpdatePvs();
2114
2115	ViewCellContainer::const_iterator it = mViewCells.begin();
2116
2117	stat.viewcells = 0;
2118	stat.minPvs = 100000000;
2119	stat.maxPvs = 0;
2120	stat.avgPvs = 0.0f;
2121	stat.avgPvsEntries = 0.0f;
2122	stat.avgFilteredPvs = 0.0f;
2123	stat.avgFilteredPvsEntries = 0.0f;
2124	stat.avgFilterContribution = 0.0f;
2125	stat.avgFilterRadius = 0;
2126	stat.avgFilterRatio = 0;
2127	stat.avgRelPvsIncrease = 0.0f;
2128	stat.devRelPvsIncrease = 0.0f;
2129	stat.renderCost = 0.0f;
2130	stat.mem = 0.0f;
2131
2132	if (mPerViewCellStat.size() != mViewCells.size()) {
2133	// reset the pvs size array after the first call to this routine
2134	mPerViewCellStat.resize(mViewCells.size());
2135	for (int i=0; i < mPerViewCellStat.size(); i++) {
2136	mPerViewCellStat[i].pvsSize = 0.0f;
2137	mPerViewCellStat[i].relPvsIncrease = 0.0f;
2138	}
2139	}
2140	int i;
2141	bool evaluateFilter;
2142	Environment::GetSingleton()->GetBoolValue("Preprocessor.evaluateFilter", evaluateFilter);
2143
2144	const float vol = mViewSpaceBox.GetVolume();
2145
2146	for (i = 0; it != mViewCells.end(); ++ it, ++ i)
2147	{
2148	ViewCell viewcell = it;
2149	if (viewcell->GetValid()) {
2150	const float pvsCost = mViewCellsTree->GetTrianglesInPvs(viewcell);
2151	const float renderCost = pvsCost * viewcell->GetVolume() / vol;
2152
2153	if (pvsCost < stat.minPvs)
2154	stat.minPvs = pvsCost;
2155	if (pvsCost > stat.maxPvs)
2156	stat.maxPvs = pvsCost;
2157
2158	stat.avgPvs += pvsCost;
2159	stat.renderCost += renderCost;
2160
2161	const float pvsEntries = (float)mViewCellsTree->GetPvsEntries(viewcell);
2162	stat.avgPvsEntries += pvsEntries;
2163
2164	if (mPerViewCellStat[i].pvsSize > 0.0f)
2165	mPerViewCellStat[i].relPvsIncrease = (pvsCost - mPerViewCellStat[i].pvsSize) / mPerViewCellStat[i].pvsSize;
2166
2167	stat.avgRelPvsIncrease += mPerViewCellStat[i].relPvsIncrease;
2168
2169	// update the pvs size
2170	mPerViewCellStat[i].pvsSize = pvsCost;
2171
2172
2173	if (evaluateFilter)
2174	{
2175	ObjectPvs filteredPvs;
2176
2177	PvsFilterStatistics fstat = ApplyFilter2(viewcell, false, mFilterWidth, filteredPvs);
2178
2179	const float filteredCost = filteredPvs.EvalPvsCost();
2180
2181	stat.avgFilteredPvs += filteredCost;
2182	stat.avgFilteredPvsEntries += filteredPvs.GetSize();
2183
2184	stat.avgFilterContribution += filteredCost - pvsCost;
2185
2186	stat.avgFilterRadius += fstat.mAvgFilterRadius;
2187	int sum = fstat.mGlobalFilterCount + fstat.mLocalFilterCount;
2188	if (sum) {
2189	stat.avgFilterRatio += fstat.mLocalFilterCount /
2190	(float) sum;
2191	}
2192
2193	} else {
2194	stat.avgFilteredPvs += pvsCost;
2195	stat.avgFilterContribution += 0;
2196	}
2197
2198	++ stat.viewcells;
2199	}
2200	}
2201
2202
2203
2204	if (stat.viewcells) {
2205	stat.mem = (float)(ObjectPvs::GetEntrySizeByte() * stat.avgPvsEntries + stat.viewcells * 16) / float(1024 * 1024);
2206
2207	stat.avgPvs/=stat.viewcells;
2208	stat.avgPvsEntries/=stat.viewcells;
2209	stat.avgFilteredPvsEntries/=stat.viewcells;
2210	stat.avgFilteredPvs/=stat.viewcells;
2211	stat.avgFilterContribution/=stat.viewcells;
2212	stat.avgFilterRadius/=stat.viewcells;
2213	stat.avgFilterRatio/=stat.viewcells;
2214	stat.avgRelPvsIncrease/=stat.viewcells;
2215	stat.renderCostRatio=stat.renderCost / stat.mem;
2216
2217	// evaluate std deviation of relPvsIncrease
2218	float sum=0.0f;
2219	for (i=0; i < stat.viewcells; i++) {
2220	sum += sqr(mPerViewCellStat[i].relPvsIncrease - stat.avgRelPvsIncrease);
2221	}
2222	stat.devRelPvsIncrease = sqrt(sum/stat.viewcells);
2223	}
2224
2225	}
2226
2227
2228	void ViewCellsManager::PrintPvsStatistics(ostream &s)
2229	{
2230	s<<"############# Viewcell PVS STAT ##################\n";
2231	PvsStatistics pvsStat;
2232	GetPvsStatistics(pvsStat);
2233	s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
2234	s<<"#AVG_ENTRIES_PVS\n"<<pvsStat.avgPvsEntries<<endl;
2235	s<<"#RENDERCOST\n"<<pvsStat.renderCost<<endl;
2236	s<<"#AVG_FILTERED_PVS\n"<<pvsStat.avgFilteredPvs<<endl;
2237	s<<"#AVG_FILTERED_ENTRIES_PVS\n"<<pvsStat.avgFilteredPvsEntries<<endl;
2238	s<<"#AVG_FILTER_CONTRIBUTION\n"<<pvsStat.avgFilterContribution<<endl;
2239	s<<"#AVG_FILTER_RADIUS\n"<<pvsStat.avgFilterRadius<<endl;
2240	s<<"#AVG_FILTER_RATIO\n"<<pvsStat.avgFilterRatio<<endl;
2241	s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
2242	s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
2243	s<<"#AVG_REL_PVS_INCREASE\n"<<pvsStat.avgRelPvsIncrease<<endl;
2244	s<<"#DEV_REL_PVS_INCREASE\n"<<pvsStat.devRelPvsIncrease<<endl;
2245	s<<"#MEMORY\n"<<pvsStat.mem<<endl;
2246	s<<"#RATIO\n"<<pvsStat.renderCost / (pvsStat.mem + Limits::Small)<<endl;
2247	s<<"#CONTRIBUTING_RAYS\n"<<mSamplesStat.mContributingRays<<endl;
2248
2249	if (mSamplesStat.mRays) {
2250	s<<"#AVG_VIEWCELLS_PER_RAY\n"<<mSamplesStat.mViewCells/(float)mSamplesStat.mRays<<endl;
2251	s<<"#AVG_RAY_LENGTHS\n"<<mSamplesStat.mRayLengths << endl;
2252
2253	} else {
2254	s<<"#AVG_VIEWCELLS_PER_RAY\n 1 \n";
2255	s<<"#AVG_RAY_LENGTHS\n 1 \n";
2256	}
2257	mSamplesStat.Reset();
2258	}
2259
2260
2261	int ViewCellsManager::CastBeam(Beam &beam)
2262	{
2263	return 0;
2264	}
2265
2266
2267	ViewCellContainer &ViewCellsManager::GetViewCells()
2268	{
2269	return mViewCells;
2270	}
2271
2272
2273	void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
2274	{
2275	mViewSpaceBox = box;
2276
2277	// hack: create clip plane relative to new view space box
2278	CreateClipPlane();
2279	// the total area of the view space has changed
2280	mTotalAreaValid = false;
2281	}
2282
2283
2284	void ViewCellsManager::CreateClipPlane()
2285	{
2286	int axis = 0;
2287	float pos;
2288	bool orientation;
2289	Vector3 absPos;
2290
2291	Environment::GetSingleton()->GetFloatValue("ViewCells.Visualization.clipPlanePos", pos);
2292	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.clipPlaneAxis", axis);
2293
2294	if (axis < 0)
2295	{
2296	axis = -axis;
2297	orientation = false;
2298	absPos = mViewSpaceBox.Max() - mViewSpaceBox.Size() * pos;
2299	}
2300	else
2301	{
2302	orientation = true;
2303	absPos = mViewSpaceBox.Min() + mViewSpaceBox.Size() * pos;
2304	}
2305
2306	mClipPlaneForViz = AxisAlignedPlane(axis, absPos[axis]);
2307	mClipPlaneForViz.mOrientation = orientation;
2308	}
2309
2310
2311	AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
2312	{
2313	return mViewSpaceBox;
2314	}
2315
2316
2317	void ViewCellsManager::ResetViewCells()
2318	{
2319	// recollect view cells
2320	mViewCells.clear();
2321	CollectViewCells();
2322
2323	// stats are computed once more
2324	EvaluateViewCellsStats();
2325
2326	// has to be recomputed
2327	mTotalAreaValid = false;
2328	}
2329
2330
2331	int ViewCellsManager::GetMaxPvsSize() const
2332	{
2333	return mMaxPvsSize;
2334	}
2335
2336
2337	int ViewCellsManager::GetMinPvsSize() const
2338	{
2339	return mMinPvsSize;
2340	}
2341
2342
2343
2344	float ViewCellsManager::GetMaxPvsRatio() const
2345	{
2346	return mMaxPvsRatio;
2347	}
2348
2349
2350	inline static void AddSampleToPvs(ObjectPvs &pvs,
2351	Intersectable *obj,
2352	const float pdf)
2353	{
2354	#if PVS_ADD_DIRTY
2355	pvs.AddSampleDirtyCheck(obj, pdf);
2356
2357	if (pvs.RequiresResort())
2358	{
2359	pvs.SimpleSort();
2360	}
2361	#else
2362	pvs.AddSample(obj, pdf);
2363	#endif
2364	}
2365
2366
2367	void ViewCellsManager::SortViewCellPvs()
2368	{
2369	ViewCellContainer::iterator it, it_end = mViewCells.end();
2370
2371	for (it = mViewCells.begin(); it != it_end; ++ it)
2372	{
2373	ObjectPvs &pvs = (*it)->GetPvs();
2374	if (pvs.RequiresResortLog())
2375	pvs.SimpleSort();
2376	}
2377	}
2378
2379
2380	void ViewCellsManager::UpdateStatsForViewCell(ViewCell vc, Intersectable obj)
2381	{
2382	KdIntersectable kdObj = static_cast<KdIntersectable >(obj);
2383
2384	const AxisAlignedBox3 box = kdObj->GetBox();
2385	const float dist = Distance(vc->GetBox().Center(), box.Center());
2386
2387	float f;
2388
2389	const float radius = box.Radius();
2390	const float fullRadius = max(0.2f * mViewSpaceBox.Radius(), radius);
2391
2392	const float minVal = 0.01f;
2393	const float maxVal = 1.0f;
2394
2395	if (dist <= radius)
2396	f = maxVal;
2397	else if (dist >= fullRadius)
2398	f = minVal;
2399	else // linear blending
2400	{
2401	f = minVal * (dist - radius) / (fullRadius - radius) +
2402	maxVal * (fullRadius - radius - dist) / (fullRadius - radius);
2403	}
2404
2405	//cout << "x " << radius << " " << dist << " " << fullRadius << " " << f << " " << f * f << endl;
2406
2407	const int numTriangles = kdObj->ComputeNumTriangles();
2408	#ifndef USE_BIT_PVS
2409	vc->GetPvs().mStats.mDistanceWeightedTriangles += f * numTriangles;
2410	vc->GetPvs().mStats.mDistanceWeightedPvs += f ;
2411	vc->GetPvs().mStats.mWeightedTriangles += numTriangles;
2412	#endif
2413	}
2414
2415
2416	bool ViewCellsManager::ComputeViewCellContribution(ViewCell *viewCell,
2417	VssRay &ray,
2418	Intersectable *obj,
2419	const Vector3 &pt,
2420	bool addSamplesToPvs)
2421	{
2422	// check if we are outside of view space
2423	// $$JB tmp commented to speedup up computations
2424	#if 0
2425	if (!obj \|\| !viewCell->GetValid())
2426	return false;
2427	#endif
2428
2429	// if ray not outside of view space
2430	float relContribution = 0.0f;
2431	float absContribution = 0.0f;
2432	bool hasAbsContribution;
2433
2434	// todo: maybe not correct for kd node pvs
2435	if (addSamplesToPvs)
2436	{
2437	//if (obj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)cout << "here12 " << endl;
2438
2439	hasAbsContribution = viewCell->GetPvs().AddSampleDirtyCheck(obj, ray.mPdf);
2440	//hasAbsContribution = viewCell->GetPvs().AddSample(obj,ray.mPdf);
2441
2442	if (hasAbsContribution)
2443	{
2444	UpdateStatsForViewCell(viewCell, obj);
2445	}
2446	}
2447	else
2448	{
2449	hasAbsContribution =
2450	viewCell->GetPvs().GetSampleContribution(obj, ray.mPdf, relContribution);
2451	}
2452
2453	// $$ clear the relative contribution as it is currently not correct anyway
2454	// relContribution = 0.0f;
2455
2456	if (hasAbsContribution)
2457	{
2458	++ ray.mPvsContribution;
2459	absContribution = relContribution = 1.0f;
2460
2461	if (viewCell->GetPvs().RequiresResort())
2462	viewCell->GetPvs().SimpleSort();
2463
2464	#if CONTRIBUTION_RELATIVE_TO_PVS_SIZE
2465	relContribution /= viewcell->GetPvs().GetSize();
2466	#endif
2467
2468	#if DIST_WEIGHTED_CONTRIBUTION
2469	// recalculate the contribution - weight the 1.0f contribution by the sqr distance to the
2470	// object-> a new contribution in the proximity of the viewcell has a larger weight!
2471	relContribution /=
2472	SqrDistance(GetViewCellBox(viewcell).Center(), ray.mTermination);
2473
2474	#endif
2475	}
2476
2477	#if SUM_RAY_CONTRIBUTIONS \|\| AVG_RAY_CONTRIBUTIONS
2478	ray.mRelativePvsContribution += relContribution;
2479	#else
2480	// recalculate relative contribution - use max of Rel Contribution
2481	if (ray.mRelativePvsContribution < relContribution)
2482	ray.mRelativePvsContribution = relContribution;
2483	#endif
2484
2485	return hasAbsContribution;
2486	}
2487
2488
2489	int ViewCellsManager::GetNumViewCells() const
2490	{
2491	return (int)mViewCells.size();
2492	}
2493
2494
2495	void
2496	ViewCellsManager::DeterminePvsObjects(VssRayContainer &rays,
2497	bool useHitObjects)
2498	{
2499	if (!useHitObjects)
2500	{
2501	// store higher order object (e.g., bvh node) instead of object itself
2502	VssRayContainer::const_iterator it, it_end = rays.end();
2503
2504	for (it = rays.begin(); it != it_end; ++ it)
2505	{
2506	VssRay vssRay = it;
2507
2508	// set only the termination object
2509	vssRay->mTerminationObject = GetIntersectable(*vssRay, true);
2510
2511	if (vssRay->mTerminationObject->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
2512	cout << "r";
2513
2514	#if 0
2515	if (vssRay->mTerminationObject == NULL)
2516	cerr<<"Error in DeterminePvsObjects - termination object maps to NULL!"<<endl;
2517	#endif
2518	}
2519	}
2520	}
2521
2522
2523	float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2524	const bool addRays,
2525	ViewCell *currentViewCell,
2526	const bool useHitObjects)
2527	{
2528	ray.mPvsContribution = 0;
2529	ray.mRelativePvsContribution = 0.0f;
2530
2531	if (!ray.mTerminationObject)
2532	return 0.0f;
2533
2534	// optain pvs entry (can be different from hit object)
2535	Intersectable *terminationObj;
2536
2537	terminationObj = ray.mTerminationObject;
2538	//cout << "rayd: " << ray.GetDir() << " ";
2539	ComputeViewCellContribution(currentViewCell,
2540	ray,
2541	terminationObj,
2542	ray.mTermination,
2543	addRays);
2544
2545	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2546	float c = 0.0f;
2547	if (terminationObj)
2548	c = ray.Length();
2549
2550	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2551	return c;
2552	#else
2553	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2554	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2555	#endif
2556	}
2557
2558
2559	float
2560	ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2561	bool addRays,
2562	bool storeViewCells,
2563	bool useHitObjects)
2564	{
2565	ray.mPvsContribution = 0;
2566	ray.mRelativePvsContribution = 0.0f;
2567
2568	++ mSamplesStat.mRays;
2569
2570	#if MYSTATS
2571	mSamplesStat.mRayLengths += ray.Length();
2572	#endif
2573	if (!ray.mTerminationObject)
2574	return 0.0f;
2575
2576	static Ray hray;
2577	hray.Init(ray);
2578
2579	float tmin = 0, tmax = 1.0;
2580
2581	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2582	{
2583	// cerr<<"ray outside view space box\n";
2584	return 0;
2585	}
2586
2587	Vector3 origin = hray.Extrap(tmin);
2588	Vector3 termination = hray.Extrap(tmax);
2589
2590	ViewCell::NewMail();
2591
2592	static ViewCellContainer viewCells;
2593	static VssRay *lastVssRay = NULL;
2594
2595	// check if last ray was not same ray with reverse direction
2596	if (1)
2597	// tmp matt: don't use when origin objects are not accounted for, currently the second ray is lost!!
2598	// $$JB: reenabled again - should use the same viewcells for the next ray ray if
2599	// it goes in the oposite direction
2600	// if (!lastVssRay \|\|
2601	// !(ray.mOrigin == lastVssRay->mTermination) \|\|
2602	// !(ray.mTermination == lastVssRay->mOrigin))
2603	{
2604	#ifdef USE_PERFTIMER
2605	viewCellCastTimer.Entry();
2606	#endif
2607	viewCells.clear();
2608
2609	// traverse the view space subdivision
2610	CastLineSegment(origin, termination, viewCells);
2611	lastVssRay = &ray;
2612	#ifdef USE_PERFTIMER
2613	viewCellCastTimer.Exit();
2614	#endif
2615	}
2616
2617	mSamplesStat.mViewCells += (int)viewCells.size();
2618
2619	if (storeViewCells)
2620	{
2621	// cerr << "Store viewcells should not be used in the test!" << endl;
2622	// copy viewcells memory efficiently
2623	#if VSS_STORE_VIEWCELLS
2624	ray.mViewCells.reserve(viewCells.size());
2625	ray.mViewCells = viewCells;
2626	#else
2627	cerr << "Vss store viewcells not supported." << endl;
2628	exit(1);
2629	#endif
2630	}
2631
2632	Intersectable *terminationObj;
2633
2634	#ifdef USE_PERFTIMER
2635	// objTimer.Entry();
2636	#endif
2637	// obtain pvs entry (can be different from hit object)
2638	terminationObj = ray.mTerminationObject;
2639
2640	#ifdef USE_PERFTIMER
2641	// objTimer.Exit();
2642	pvsTimer.Entry();
2643	#endif
2644	//if (terminationObj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
2645	// cout << "found tmi: " << Intersectable::GetTypeName(terminationObj) << " " << viewCells.size() << endl;
2646	bool contri = false;
2647	ViewCellContainer::const_iterator it = viewCells.begin();
2648	//cout << "rayd: " << ray.GetDir() << " ";
2649	for (; it != viewCells.end(); ++ it)
2650	{
2651	if (ComputeViewCellContribution(*it,
2652	ray,
2653	terminationObj,
2654	ray.mTermination,
2655	addRays))
2656	{
2657	contri = true;
2658	}
2659
2660	(*it)->IncNumPiercingRays();
2661
2662	}
2663
2664	#if MYSTATS
2665	if (contri)
2666	{
2667	if (rand() < (RAND_MAX / 10))
2668	// cout << "rayd: " /<< ray.GetOrigin() << " " << ray.GetTermination() << " "/ << Normalize(ray.GetDir()) << " " << endl;
2669	mVizBuffer.AddRay(&ray);
2670	}
2671	#endif
2672	#ifdef USE_PERFTIMER
2673	pvsTimer.Exit();
2674	#endif
2675
2676	mSamplesStat.mPvsContributions += ray.mPvsContribution;
2677	if (ray.mPvsContribution)
2678	++ mSamplesStat.mContributingRays;
2679
2680	#if AVG_RAY_CONTRIBUTIONS
2681	ray.mRelativePvsContribution /= (float)viewCells.size();
2682	#endif
2683
2684	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2685	float c = 0.0f;
2686	if (terminationObj)
2687	c = ray.Length();
2688	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2689	return c;
2690	#else
2691	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2692	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2693	#endif
2694	}
2695
2696
2697	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
2698	const int maxSize,
2699	VssRayContainer &usedRays,
2700	VssRayContainer *savedRays) const
2701	{
2702	const int limit = min(maxSize, (int)sourceRays.size());
2703	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
2704
2705	VssRayContainer::const_iterator it, it_end = sourceRays.end();
2706	for (it = sourceRays.begin(); it != it_end; ++ it)
2707	{
2708	if (Random(1.0f) < prop)
2709	usedRays.push_back(*it);
2710	else if (savedRays)
2711	savedRays->push_back(*it);
2712	}
2713	}
2714
2715
2716	float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
2717	{
2718	return (float)mViewCellsTree->GetTrianglesInPvs(viewCell);
2719	}
2720
2721
2722	float ViewCellsManager::GetAccVcArea()
2723	{
2724	// if already computed
2725	if (mTotalAreaValid)
2726	{
2727	return mTotalArea;
2728	}
2729
2730	mTotalArea = 0;
2731	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2732
2733	for (it = mViewCells.begin(); it != it_end; ++ it)
2734	{
2735	//Debug << "area: " << GetArea(*it);
2736	mTotalArea += GetArea(*it);
2737	}
2738
2739	mTotalAreaValid = true;
2740
2741	return mTotalArea;
2742	}
2743
2744
2745	void ViewCellsManager::PrintStatistics(ostream &s) const
2746	{
2747	s << mCurrentViewCellsStats << endl;
2748	}
2749
2750
2751	void ViewCellsManager::CreateUniqueViewCellIds()
2752	{
2753	if (ViewCellsTreeConstructed())
2754	{
2755	mViewCellsTree->CreateUniqueViewCellsIds();
2756	}
2757	else // no view cells tree, handle view cells "myself"
2758	{
2759	int i = 0;
2760	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2761	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2762	{
2763	if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2764	{
2765	mViewCells[i]->SetId(i ++);
2766	}
2767	}
2768	}
2769	}
2770
2771
2772	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2773	const AxisAlignedBox3 *sceneBox,
2774	const bool colorCode,
2775	const AxisAlignedPlane *clipPlane
2776	) const
2777	{
2778	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2779
2780	for (it = mViewCells.begin(); it != it_end; ++ it)
2781	{
2782	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
2783	{
2784	ExportColor(exporter, *it, colorCode);
2785	ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2786	}
2787	}
2788	}
2789
2790
2791	void ViewCellsManager::CreateViewCellMeshes()
2792	{
2793	// convert to meshes
2794	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2795
2796	for (it = mViewCells.begin(); it != it_end; ++ it)
2797	{
2798	if (!(*it)->GetMesh())
2799	{
2800	CreateMesh(*it);
2801	}
2802	}
2803	}
2804
2805
2806	bool ViewCellsManager::ExportViewCells(const string filename,
2807	const bool exportPvs,
2808	const ObjectContainer &objects)
2809	{
2810	return false;
2811	}
2812
2813
2814	void ViewCellsManager::CollectViewCells(const int n)
2815	{
2816	mNumActiveViewCells = n;
2817	mViewCells.clear();
2818	// implemented in subclasses
2819	CollectViewCells();
2820	}
2821
2822
2823	void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
2824	{
2825	ViewCellContainer leaves;
2826	// sets the pointers to the currently active view cells
2827	mViewCellsTree->CollectLeaves(vc, leaves);
2828
2829	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2830	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2831	{
2832	static_cast<ViewCellLeaf >(lit)->SetActiveViewCell(vc);
2833	}
2834	}
2835
2836
2837	void ViewCellsManager::SetViewCellsActive()
2838	{
2839	// collect leaf view cells and set the pointers to
2840	// the currently active view cells
2841	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2842
2843	for (it = mViewCells.begin(); it != it_end; ++ it)
2844	{
2845	SetViewCellActive(*it);
2846	}
2847	}
2848
2849
2850	int ViewCellsManager::GetMaxFilterSize() const
2851	{
2852	return mMaxFilterSize;
2853	}
2854
2855
2856	static const bool USE_ASCII = true;
2857
2858
2859	bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2860	const ObjectContainer &objects) const
2861	{
2862	ObjectContainer::const_iterator it, it_end = objects.end();
2863
2864	if (USE_ASCII)
2865	{
2866	ofstream boxesOut(filename.c_str());
2867	if (!boxesOut.is_open())
2868	return false;
2869
2870	for (it = objects.begin(); it != it_end; ++ it)
2871	{
2872	MeshInstance mi = static_cast<MeshInstance >(*it);
2873	const AxisAlignedBox3 box = mi->GetBox();
2874
2875	boxesOut << mi->GetId() << " "
2876	<< box.Min().x << " "
2877	<< box.Min().y << " "
2878	<< box.Min().z << " "
2879	<< box.Max().x << " "
2880	<< box.Max().y << " "
2881	<< box.Max().z << endl;
2882	}
2883
2884	boxesOut.close();
2885	}
2886	else
2887	{
2888	ofstream boxesOut(filename.c_str(), ios::binary);
2889
2890	if (!boxesOut.is_open())
2891	return false;
2892
2893	for (it = objects.begin(); it != it_end; ++ it)
2894	{
2895	MeshInstance mi = static_cast<MeshInstance >(*it);
2896	const AxisAlignedBox3 box = mi->GetBox();
2897
2898	Vector3 bmin = box.Min();
2899	Vector3 bmax = box.Max();
2900
2901	int id = mi->GetId();
2902
2903	boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2904	boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2905	boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2906	}
2907
2908	boxesOut.close();
2909	}
2910
2911	return true;
2912	}
2913
2914
2915	bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2916	IndexedBoundingBoxContainer &boxes) const
2917	{
2918	Vector3 bmin, bmax;
2919	int id;
2920
2921	if (USE_ASCII)
2922	{
2923	ifstream boxesIn(filename.c_str());
2924
2925	if (!boxesIn.is_open())
2926	{
2927	cout << "failed to open file " << filename << endl;
2928	return false;
2929	}
2930
2931	string buf;
2932	while (!(getline(boxesIn, buf)).eof())
2933	{
2934	sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2935	&id, &bmin.x, &bmin.y, &bmin.z,
2936	&bmax.x, &bmax.y, &bmax.z);
2937
2938	AxisAlignedBox3 box(bmin, bmax);
2939	// MeshInstance *mi = new MeshInstance();
2940	// HACK: set bounding box to new box
2941	//mi->mBox = box;
2942
2943	boxes.push_back(IndexedBoundingBox(id, box));
2944	}
2945
2946	boxesIn.close();
2947	}
2948	else
2949	{
2950	ifstream boxesIn(filename.c_str(), ios::binary);
2951
2952	if (!boxesIn.is_open())
2953	return false;
2954
2955	while (1)
2956	{
2957	boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2958	boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2959	boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2960
2961	if (boxesIn.eof())
2962	break;
2963
2964	AxisAlignedBox3 box(bmin, bmax);
2965	MeshInstance *mi = new MeshInstance(NULL);
2966
2967	boxes.push_back(IndexedBoundingBox(id, box));
2968	}
2969
2970	boxesIn.close();
2971	}
2972
2973	return true;
2974	}
2975
2976
2977	float ViewCellsManager::GetFilterWidth()
2978	{
2979	return mFilterWidth;
2980	}
2981
2982
2983	float ViewCellsManager::GetAbsFilterWidth()
2984	{
2985	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2986	}
2987
2988
2989	void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2990	const float pvsCost,
2991	const int entriesInPvs) const
2992	{
2993	vc->mPvsCost = pvsCost;
2994	vc->mEntriesInPvs = entriesInPvs;
2995
2996	vc->mPvsSizeValid = true;
2997	}
2998
2999
3000	void ViewCellsManager::UpdateScalarPvsCost(ViewCell *vc, const float pvsCost) const
3001	{
3002	vc->mPvsCost = pvsCost;
3003	}
3004
3005
3006	void
3007	ViewCellsManager::ApplyFilter(ViewCell *viewCell,
3008	KdTree *kdTree,
3009	const float viewSpaceFilterSize,
3010	const float spatialFilterSize,
3011	ObjectPvs &pvs
3012	)
3013	{
3014	// extend the pvs of the viewcell by pvs of its neighbors
3015	// and apply spatial filter by including all neighbors of the objects
3016	// in the pvs
3017
3018	// get all viewcells intersecting the viewSpaceFilterBox
3019	// and compute the pvs union
3020
3021	//Vector3 center = viewCell->GetBox().Center();
3022	// Vector3 center = m->mBox.Center();
3023
3024	// AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
3025	// center + Vector3(viewSpaceFilterSize/2));
3026	if (!ViewCellsConstructed())
3027	return;
3028
3029	if (viewSpaceFilterSize >= 0.0f)
3030	{
3031	const bool usePrVS = false;
3032
3033	if (!usePrVS)
3034	{
3035	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3036	box.Enlarge(Vector3(viewSpaceFilterSize/2));
3037
3038	ViewCellContainer viewCells;
3039	ComputeBoxIntersections(box, viewCells);
3040
3041	// cout<<"box="<<box<<endl;
3042	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3043
3044	for (; it != it_end; ++ it)
3045	{
3046	ObjectPvs interPvs;
3047	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3048	ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
3049
3050	pvs = interPvs;
3051	}
3052	}
3053	else
3054	{
3055	PrVs prvs;
3056	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3057
3058	// mViewCellsManager->SetMaxFilterSize(1);
3059	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
3060	pvs = prvs.mViewCell->GetPvs();
3061	DeleteLocalMergeTree(prvs.mViewCell);
3062	}
3063	}
3064	else
3065	{
3066	pvs = viewCell->GetPvs();
3067	}
3068
3069	if (spatialFilterSize >=0.0f)
3070	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
3071
3072	}
3073
3074
3075
3076	void
3077	ViewCellsManager::ApplyFilter(KdTree *kdTree,
3078	const float relViewSpaceFilterSize,
3079	const float relSpatialFilterSize
3080	)
3081	{
3082
3083	if (!ViewCellsConstructed())
3084	return;
3085
3086	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3087
3088	ObjectPvs *newPvs;
3089	newPvs = new ObjectPvs[mViewCells.size()];
3090
3091	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
3092	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
3093
3094	int i;
3095	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3096	ApplyFilter(*it,
3097	kdTree,
3098	viewSpaceFilterSize,
3099	spatialFilterSize,
3100	newPvs[i]
3101	);
3102	}
3103
3104	// now replace all pvss
3105	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3106
3107	ObjectPvs &pvs = (*it)->GetPvs();
3108	pvs.Clear();
3109	pvs = newPvs[i];
3110	newPvs[i].Clear();
3111	}
3112
3113	delete [] newPvs;
3114	}
3115
3116
3117	void
3118	ViewCellsManager::ApplySpatialFilter(
3119	KdTree *kdTree,
3120	const float spatialFilterSize,
3121	ObjectPvs &pvs
3122	)
3123	{
3124	// now compute a new Pvs by including also objects intersecting the
3125	// extended boxes of visible objects
3126	Intersectable::NewMail();
3127
3128	ObjectPvsIterator pit = pvs.GetIterator();
3129
3130	while (pit.HasMoreEntries())
3131	pit.Next()->Mail();
3132
3133	ObjectPvs nPvs;
3134	int nPvsSize = 0;
3135
3136	ObjectPvsIterator pit2 = pvs.GetIterator();
3137
3138	while (pit2.HasMoreEntries())
3139	{
3140	// now go through the pvs again
3141	Intersectable *object = pit2.Next();
3142
3143	// Vector3 center = object->GetBox().Center();
3144	// AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
3145	// center + Vector3(spatialFilterSize/2));
3146
3147	AxisAlignedBox3 box = object->GetBox();
3148	box.Enlarge(Vector3(spatialFilterSize/2));
3149
3150	ObjectContainer objects;
3151
3152	// $$ warning collect objects takes only unmailed ones!
3153	kdTree->CollectObjects(box, objects);
3154	// cout<<"collected objects="<<objects.size()<<endl;
3155	ObjectContainer::const_iterator noi = objects.begin();
3156	for (; noi != objects.end(); ++ noi)
3157	{
3158	Intersectable o = noi;
3159	cout<<"w";
3160	// $$ JB warning: pdfs are not correct at this point!
3161	nPvs.AddSample(o, Limits::Small);
3162	nPvsSize ++;
3163	}
3164	}
3165
3166	// cout<<"nPvs size = "<<nPvsSize<<endl;
3167	pvs.MergeInPlace(nPvs);
3168	}
3169
3170
3171	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3172	const ViewCellContainer &viewCells) const
3173	{
3174	MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
3175	}
3176
3177
3178	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3179	const ViewCellContainer &viewCells,
3180	int leftIdx,
3181	int rightIdx) const
3182	{
3183	if (leftIdx == rightIdx)
3184	{
3185	pvs = viewCells[leftIdx]->GetPvs();
3186	}
3187	else
3188	{
3189	const int midSplit = (leftIdx + rightIdx) / 2;
3190
3191	ObjectPvs leftPvs, rightPvs;
3192	MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
3193	MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);
3194
3195	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
3196	}
3197	}
3198
3199
3200	PvsFilterStatistics
3201	ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
3202	const bool useViewSpaceFilter,
3203	const float filterSize,
3204	ObjectPvs &pvs,
3205	vector<AxisAlignedBox3> *filteredBoxes,
3206	const bool onlyNewObjects
3207	)
3208	{
3209	pvs.Reserve(viewCell->GetFilteredPvsSize());
3210
3211	PvsFilterStatistics stats;
3212
3213	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
3214	const Vector3 center = vbox.Center();
3215
3216	// copy the PVS
3217	if (!mUseKdPvs)
3218	Intersectable::NewMail();
3219	else
3220	KdNode::NewMail();
3221
3222	ObjectPvs basePvs = viewCell->GetPvs();
3223	ObjectPvsIterator pit = basePvs.GetIterator();
3224
3225	if (!mUseKdPvs)
3226	{
3227	// first mark all objects from this pvs
3228	while (pit.HasMoreEntries())
3229	pit.Next()->Mail();
3230	}
3231
3232	int pvsSize = 0;
3233	int nPvsSize = 0;
3234
3235	//Debug<<"f #s="<<samples<<" pvs size = "<<basePvs.GetSize();
3236	// cout<<"Filter size = "<<filterSize<<endl;
3237	// cout<<"vbox = "<<vbox<<endl;
3238	// cout<<"center = "<<center<<endl;
3239
3240
3241	// Minimal number of local samples to take into account
3242	// the local sampling density.
3243	// The size of the filter is a minimum of the conservative
3244	// local sampling density estimate (#rays intersecting teh viewcell and
3245	// the object)
3246	// and gobal estimate for the view cell
3247	// (total #rays intersecting the viewcell)
3248	const int minLocalSamples = 2;
3249	const float viewCellRadius = 0.5f * Magnitude(vbox.Diagonal());
3250
3251	float samples = (float)basePvs.GetSamples();
3252
3253
3254	//////////
3255	//-- now compute the filter box around the current viewCell
3256
3257	if (useViewSpaceFilter)
3258	{
3259	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
3260	float radius = viewCellRadius / 100.0f;
3261	vbox.Enlarge(radius);
3262	cout<<"vbox = "<<vbox<<endl;
3263
3264	ViewCellContainer viewCells;
3265	ComputeBoxIntersections(vbox, viewCells);
3266
3267	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3268
3269	for (int i = 0; it != it_end; ++ it, ++ i)
3270	{
3271	if ((*it) != viewCell)
3272	{
3273	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3274	basePvs.MergeInPlace((*it)->GetPvs());
3275	}
3276
3277	// update samples and globalC
3278	samples = (float)pvs.GetSamples();
3279	// cout<<"neighboring viewcells = "<<i-1<<endl;
3280	// cout<<"Samples' = "<<samples<<endl;
3281	}
3282	}
3283
3284	// Minimal number of samples so that filtering takes place
3285	const float MIN_SAMPLES = 50;
3286
3287	if (samples > MIN_SAMPLES)
3288	{
3289	float globalC = 2.0f * filterSize / sqrt(samples);
3290
3291	ObjectContainer objects;
3292	PvsData pvsData;
3293
3294	pit = basePvs.GetIterator();
3295
3296	if (onlyNewObjects) {
3297	while (pit.HasMoreEntries()) {
3298	// mail all objects from the original not to include them in the
3299	// resulting pvs
3300	Intersectable *obj = pit.Next(pvsData);
3301	obj->Mail();
3302	}
3303	pit = basePvs.GetIterator();
3304	}
3305
3306	while (pit.HasMoreEntries())
3307	{
3308	Intersectable *object = pit.Next(pvsData);
3309
3310	// compute filter size based on the distance and the numebr of samples
3311	AxisAlignedBox3 box = object->GetBox();
3312
3313	float distance = Distance(center, box.Center());
3314	float globalRadius = distance*globalC;
3315
3316	int objectSamples = (int)pvsData.mSumPdf;
3317	float localRadius = MAX_FLOAT;
3318
3319	localRadius = filterSize0.5fMagnitude(box.Diagonal())/
3320	sqrt((float)objectSamples);
3321
3322	// cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;
3323
3324	// now compute the filter size
3325	float radius;
3326
3327	#if 0
3328	if (objectSamples <= 1)
3329	{
3330	if (localRadius > globalRadius)
3331	{
3332	radius = 0.5flRadius;
3333	stats.mLocalFilterCount++;
3334	}
3335	else
3336	{
3337	radius = globalRadius;
3338	stats.mGlobalFilterCount++;
3339	}
3340	}
3341	else
3342	{
3343	radius = localRadius;
3344	stats.mLocalFilterCount++;
3345	}
3346	#else
3347
3348	// radius = 0.5fglobalRadius + 0.5flocalRadius;
3349	radius = Min(globalRadius, localRadius);
3350
3351	if (localRadius > globalRadius)
3352	++ stats.mLocalFilterCount;
3353	else
3354	++ stats.mGlobalFilterCount;
3355	#endif
3356
3357	stats.mAvgFilterRadius += radius;
3358
3359	// cout<<"box = "<<box<<endl;
3360	// cout<<"distance = "<<distance<<endl;
3361	// cout<<"radiues = "<<radius<<endl;
3362
3363	box.Enlarge(Vector3(radius));
3364
3365	if (filteredBoxes)
3366	filteredBoxes->push_back(box);
3367
3368	objects.clear();
3369
3370	// $$ warning collect objects takes only unmailed ones!
3371	if (mUseKdPvs) {
3372	GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
3373	//GetPreprocessor()->mKdTree->CollectSmallKdObjects(box, objects, 0.1f);
3374
3375	} else
3376	CollectObjects(box, objects);
3377
3378	// cout<<"collected objects="<<objects.size()<<endl;
3379	ObjectContainer::const_iterator noi = objects.begin();
3380	for (; noi != objects.end(); ++ noi)
3381	{
3382	Intersectable o = noi;
3383
3384	// $$ JB warning: pdfs are not correct at this point!
3385	pvs.AddSampleDirty(o, Limits::Small);
3386	}
3387	}
3388
3389	stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
3390	}
3391
3392	//Debug << " nPvs size = " << pvs.GetSize() << endl;
3393
3394	if (!mUseKdPvs && !onlyNewObjects)
3395	{
3396	PvsData pvsData;
3397
3398	// copy the base pvs to the new pvs
3399	pit = basePvs.GetIterator();
3400	while (pit.HasMoreEntries())
3401	{
3402	Intersectable *obj = pit.Next(pvsData);
3403	pvs.AddSampleDirty(obj, pvsData.mSumPdf);
3404	}
3405	}
3406
3407	pvs.SimpleSort();
3408	viewCell->SetFilteredPvsSize(pvs.GetSize());
3409
3410	// warning: not thread-safe!
3411	if (!mUseKdPvs)
3412	Intersectable::NewMail();
3413
3414	return stats;
3415	}
3416
3417
3418
3419	void ViewCellsManager::ExportColor(Exporter *exporter,
3420	ViewCell *vc,
3421	int colorCode) const
3422	{
3423	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3424
3425	float importance = 0;
3426	static Material m;
3427	//cout << "color code: " << colorCode << endl;
3428
3429	switch (colorCode)
3430	{
3431	case 0: // Random
3432	{
3433	if (vcValid)
3434	{
3435	m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
3436	m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
3437	m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
3438	}
3439	else
3440	{
3441	m.mDiffuseColor.r = 0.0f;
3442	m.mDiffuseColor.g = 1.0f;
3443	m.mDiffuseColor.b = 0.0f;
3444	}
3445
3446	exporter->SetForcedMaterial(m);
3447	return;
3448	}
3449
3450	case 1: // pvs
3451	{
3452	if (mCurrentViewCellsStats.maxPvs)
3453	{
3454	importance = //(float)mViewCellsTree->GetTrianglesInPvs(vc) / 700;
3455	(float)mCurrentViewCellsStats.maxPvs;
3456	}
3457	}
3458	break;
3459	case 2: // merges
3460	{
3461	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
3462	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3463	}
3464	break;
3465	default:
3466	break;
3467	}
3468
3469	// special color code for invalid view cells
3470	m.mDiffuseColor.r = importance;
3471	m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
3472	m.mDiffuseColor.g = 1.0f - importance;
3473
3474	//Debug << "importance: " << importance << endl;
3475	exporter->SetForcedMaterial(m);
3476	}
3477
3478
3479	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3480	vector<MergeCandidate> &candidates)
3481	{
3482	// implemented in subclasses
3483	}
3484
3485
3486	void ViewCellsManager::UpdatePvsForEvaluation()
3487	{
3488	ObjectPvs objPvs;
3489	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
3490	}
3491
3492
3493	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
3494	{
3495	// terminate traversal
3496	if (root->IsLeaf())
3497	{
3498	// we assume that pvs is explicitly stored in leaves
3499	pvs = root->GetPvs();
3500	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
3501
3502	return;
3503	}
3504
3505	////////////////
3506	//-- interior node => propagate pvs up the tree
3507
3508	ViewCellInterior interior = static_cast<ViewCellInterior >(root);
3509
3510	// reset interior pvs
3511	interior->GetPvs().Clear();
3512
3513	// reset recursive pvs
3514	pvs.Clear();
3515
3516	// pvss of child nodes
3517	vector<ObjectPvs> pvsList;
3518	pvsList.resize((int)interior->mChildren.size());
3519
3520	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3521
3522	int i = 0;
3523
3524	////////
3525	//-- recursivly compute child pvss
3526
3527	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3528	{
3529	UpdatePvsForEvaluation(*vit, pvsList[i]);
3530	}
3531
3532	#if 1
3533	Intersectable::NewMail();
3534
3535
3536	///////////
3537	//-- merge pvss
3538
3539	PvsData pvsData;
3540
3541	vector<ObjectPvs>::iterator oit = pvsList.begin();
3542
3543	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3544	{
3545	ObjectPvsIterator pit = (*oit).GetIterator();
3546
3547	// add pvss to new pvs: use mailing to avoid adding entries two times.
3548	while (pit.HasMoreEntries())
3549	{
3550	Intersectable *intersect = pit.Next(pvsData);
3551
3552	if (!intersect->Mailed())
3553	{
3554	intersect->Mail();
3555	pvs.AddSampleDirty(intersect, pvsData.mSumPdf);
3556	}
3557	}
3558	}
3559
3560	// store pvs in this node
3561	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3562	{
3563	interior->SetPvs(pvs);
3564	}
3565
3566	// set new pvs size
3567	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3568
3569	#else
3570	// really merge cells: slow but sumPdf is correct
3571	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3572	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3573	#endif
3574	}
3575
3576
3577
3578	/*******************************************************************/
3579	/* BspViewCellsManager implementation */
3580	/*******************************************************************/
3581
3582
3583	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
3584	ViewCellsManager(vcTree), mBspTree(bspTree)
3585	{
3586	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3587
3588	mBspTree->SetViewCellsManager(this);
3589	mBspTree->SetViewCellsTree(mViewCellsTree);
3590	}
3591
3592
3593	bool BspViewCellsManager::ViewCellsConstructed() const
3594	{
3595	return mBspTree->GetRoot() != NULL;
3596	}
3597
3598
3599	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
3600	{
3601	return new BspViewCell(mesh);
3602	}
3603
3604
3605	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3606	const VssRayContainer &rays)
3607	{
3608	// if view cells were already constructed, we can finish
3609	if (ViewCellsConstructed())
3610	return 0;
3611
3612	int sampleContributions = 0;
3613
3614	// construct view cells using the collected samples
3615	RayContainer constructionRays;
3616	VssRayContainer savedRays;
3617
3618	// choose a a number of rays based on the ratio of cast rays / requested rays
3619	const int limit = min(mInitialSamples, (int)rays.size());
3620	VssRayContainer::const_iterator it, it_end = rays.end();
3621
3622	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3623
3624	for (it = rays.begin(); it != it_end; ++ it)
3625	{
3626	if (Random(1.0f) < prop)
3627	constructionRays.push_back(new Ray((it)));
3628	else
3629	savedRays.push_back(*it);
3630	}
3631
3632	if (!mUsePredefinedViewCells)
3633	{
3634	// no view cells loaded
3635	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3636	// collect final view cells
3637	mBspTree->CollectViewCells(mViewCells);
3638	}
3639	else
3640	{
3641	// use predefined view cells geometry =>
3642	// contruct bsp hierarchy over them
3643	mBspTree->Construct(mViewCells);
3644	}
3645
3646	// destroy rays created only for construction
3647	CLEAR_CONTAINER(constructionRays);
3648
3649	Debug << mBspTree->GetStatistics() << endl;
3650	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3651
3652	// recast rest of the rays
3653	if (SAMPLE_AFTER_SUBDIVISION)
3654	ComputeSampleContributions(savedRays, true, false);
3655
3656	// real meshes are contructed at this stage
3657	if (0)
3658	{
3659	cout << "finalizing view cells ... ";
3660	FinalizeViewCells(true);
3661	cout << "finished" << endl;
3662	}
3663
3664	return sampleContributions;
3665	}
3666
3667
3668	void BspViewCellsManager::CollectViewCells()
3669	{
3670	if (!ViewCellsTreeConstructed())
3671	{ // view cells tree constructed
3672	mBspTree->CollectViewCells(mViewCells);
3673	}
3674	else
3675	{ // we can use the view cells tree hierarchy to get the right set
3676	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3677	}
3678	}
3679
3680
3681	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3682	{
3683	if (1)
3684	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3685	else
3686	// compute view cell area as subsititute for probability
3687	return GetArea(viewCell) / GetAccVcArea();
3688	}
3689
3690
3691
3692	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3693	const Vector3 &termination,
3694	ViewCellContainer &viewcells)
3695	{
3696	return mBspTree->CastLineSegment(origin, termination, viewcells);
3697	}
3698
3699
3700	bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
3701	const Vector3 &termination,
3702	ViewCell *viewCell)
3703	{
3704	return false;
3705	}
3706
3707
3708	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3709	{
3710	// save color code
3711	const int savedColorCode = mColorCode;
3712
3713	Exporter *exporter;
3714
3715	// export merged view cells using pvs color coding
3716	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3717	cout << "exporting view cells after merge (pvs size) ... ";
3718
3719	if (exporter)
3720	{
3721	if (mExportGeometry)
3722	{
3723	exporter->ExportGeometry(objects);
3724	}
3725
3726	exporter->SetFilled();
3727	mColorCode = 1;
3728
3729	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3730
3731	delete exporter;
3732	}
3733	cout << "finished" << endl;
3734
3735	mColorCode = savedColorCode;
3736	}
3737
3738
3739	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3740	const VssRayContainer &rays)
3741	{
3742	if (!ViewCellsConstructed())
3743	{
3744	Debug << "view cells not constructed" << endl;
3745	return 0;
3746	}
3747
3748	// view cells already finished before post processing step,
3749	// i.e., because they were loaded from disc
3750	if (mViewCellsFinished)
3751	{
3752	FinalizeViewCells(true);
3753	EvaluateViewCellsStats();
3754
3755	return 0;
3756	}
3757
3758	//////////////////
3759	//-- merge leaves of the view cell hierarchy
3760
3761	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3762	long startTime = GetTime();
3763
3764	VssRayContainer postProcessRays;
3765	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3766
3767	if (mMergeViewCells)
3768	{
3769	cout << "constructing visibility based merge tree" << endl;
3770	mViewCellsTree->ConstructMergeTree(rays, objects);
3771	}
3772	else
3773	{
3774	cout << "constructing spatial merge tree" << endl;
3775	ViewCell *root;
3776	// the spatial merge tree is difficult to build for
3777	// this type of construction, as view cells cover several
3778	// leaves => create dummy tree which is only 2 levels deep
3779	if (mUsePredefinedViewCells)
3780	{
3781	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3782	}
3783	else
3784	{
3785	// create spatial merge hierarchy
3786	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3787	}
3788
3789	mViewCellsTree->SetRoot(root);
3790
3791	// recompute pvs in the whole hierarchy
3792	ObjectPvs pvs;
3793	UpdatePvsForEvaluation(root, pvs);
3794	}
3795
3796	cout << "finished" << endl;
3797	cout << "merged view cells in "
3798	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3799
3800	Debug << "Postprocessing: Merged view cells in "
3801	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3802
3803
3804	////////////////////////
3805	//-- visualization and statistics after merge
3806
3807	if (1)
3808	{
3809	char mstats[100];
3810	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3811	mViewCellsTree->ExportStats(mstats);
3812	}
3813
3814	// recompute view cells and stats
3815	ResetViewCells();
3816	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3817
3818	// visualization of the view cells
3819	if (1) ExportMergedViewCells(objects);
3820
3821	// compute final meshes and volume / area
3822	if (1) FinalizeViewCells(true);
3823
3824	return 0;
3825	}
3826
3827
3828	BspViewCellsManager::~BspViewCellsManager()
3829	{
3830	}
3831
3832
3833	int BspViewCellsManager::GetType() const
3834	{
3835	return BSP;
3836	}
3837
3838
3839	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3840	const VssRayContainer &sampleRays)
3841	{
3842	if (!ViewCellsConstructed())
3843	return;
3844
3845	const int savedColorCode = mColorCode;
3846
3847	if (1) // export final view cells
3848	{
3849	mColorCode = 1; // 0 = pvs, 1 = random
3850	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3851
3852	cout << "exporting view cells after merge (pvs size) ... ";
3853
3854	if (exporter)
3855	{
3856	if (mExportGeometry)
3857	{
3858	exporter->ExportGeometry(objects);
3859	}
3860
3861	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3862	delete exporter;
3863	}
3864	cout << "finished" << endl;
3865	}
3866
3867	// reset color code
3868	mColorCode = savedColorCode;
3869
3870
3871	//////////////////
3872	//-- visualization of the BSP splits
3873
3874	bool exportSplits = false;
3875	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3876
3877	if (exportSplits)
3878	{
3879	cout << "exporting splits ... ";
3880	ExportSplits(objects);
3881	cout << "finished" << endl;
3882	}
3883
3884	int leafOut;
3885	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3886	const int raysOut = 100;
3887	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3888	}
3889
3890
3891	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3892	{
3893	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3894
3895	if (exporter)
3896	{
3897	//exporter->SetFilled();
3898	if (mExportGeometry)
3899	{
3900	exporter->ExportGeometry(objects);
3901	}
3902
3903	Material m;
3904	m.mDiffuseColor = RgbColor(1, 0, 0);
3905	exporter->SetForcedMaterial(m);
3906	exporter->SetWireframe();
3907
3908	exporter->ExportBspSplits(*mBspTree, true);
3909
3910	// NOTE: take forced material, else big scenes cannot be viewed
3911	m.mDiffuseColor = RgbColor(0, 1, 0);
3912	exporter->SetForcedMaterial(m);
3913	//exporter->ResetForcedMaterial();
3914
3915	delete exporter;
3916	}
3917	}
3918
3919
3920	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3921	const int maxViewCells,
3922	const bool sortViewCells,
3923	const bool exportPvs,
3924	const bool exportRays,
3925	const int maxRays,
3926	const string &prefix,
3927	VssRayContainer *visRays)
3928	{
3929	if (sortViewCells)
3930	{ // sort view cells to visualize the largest view cells
3931	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
3932	}
3933
3934	//////////
3935	//-- export visualizations of some view cells
3936
3937	ViewCell::NewMail();
3938	const int limit = min(maxViewCells, (int)mViewCells.size());
3939
3940	for (int i = 0; i < limit; ++ i)
3941	{
3942	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
3943	ViewCell *vc = mViewCells[idx];
3944
3945	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
3946	continue;
3947
3948	vc->Mail();
3949
3950	ObjectPvs pvs;
3951	mViewCellsTree->GetPvs(vc, pvs);
3952
3953	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
3954	Exporter *exporter = Exporter::GetExporter(s);
3955
3956	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetTrianglesInPvs(vc) << endl;
3957
3958	if (exportRays)
3959	{
3960	////////////
3961	//-- export rays piercing this view cell
3962
3963	// use rays stored with the view cells
3964	VssRayContainer vcRays, vcRays2, vcRays3;
3965	VssRayContainer collectRays;
3966
3967	// collect initial view cells
3968	ViewCellContainer leaves;
3969	mViewCellsTree->CollectLeaves(vc, leaves);
3970
3971	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3972	for (vit = leaves.begin(); vit != vit_end; ++ vit)
3973	{
3974	// prepare some rays for visualization
3975	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
3976	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
3977	{
3978	collectRays.push_back(*rit);
3979	}
3980	}
3981
3982	const int raysOut = min((int)collectRays.size(), maxRays);
3983
3984	// prepare some rays for visualization
3985	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3986	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3987	{
3988	const float p = RandomValue(0.0f, (float)collectRays.size());
3989	if (p < raysOut)
3990	{
3991	if ((*rit)->mFlags & VssRay::BorderSample)
3992	{
3993	vcRays.push_back(*rit);
3994	}
3995	else if ((*rit)->mFlags & VssRay::ReverseSample)
3996	{
3997	vcRays2.push_back(*rit);
3998	}
3999	else
4000	{
4001	vcRays3.push_back(*rit);
4002	}
4003	}
4004	}
4005
4006	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
4007	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
4008	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
4009	}
4010
4011	////////////////
4012	//-- export view cell geometry
4013
4014	exporter->SetWireframe();
4015
4016	Material m;//= RandomMaterial();
4017	m.mDiffuseColor = RgbColor(0, 1, 0);
4018	exporter->SetForcedMaterial(m);
4019
4020	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4021	exporter->SetFilled();
4022
4023	if (exportPvs)
4024	{
4025	Intersectable::NewMail();
4026	ObjectPvsIterator pit = pvs.GetIterator();
4027
4028	while (pit.HasMoreEntries())
4029	{
4030	Intersectable *intersect = pit.Next();
4031
4032	// output PVS of view cell
4033	if (!intersect->Mailed())
4034	{
4035	intersect->Mail();
4036
4037	m = RandomMaterial();
4038	exporter->SetForcedMaterial(m);
4039	exporter->ExportIntersectable(intersect);
4040	}
4041	}
4042	cout << endl;
4043	}
4044
4045	DEL_PTR(exporter);
4046	cout << "finished" << endl;
4047	}
4048	}
4049
4050
4051	void BspViewCellsManager::TestSubdivision()
4052	{
4053	ViewCellContainer leaves;
4054	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4055
4056	ViewCellContainer::const_iterator it, it_end = leaves.end();
4057
4058	const float vol = mViewSpaceBox.GetVolume();
4059	float subdivVol = 0;
4060	float newVol = 0;
4061
4062	for (it = leaves.begin(); it != it_end; ++ it)
4063	{
4064	BspNodeGeometry geom;
4065	mBspTree->ConstructGeometry(*it, geom);
4066
4067	const float lVol = geom.GetVolume();
4068	newVol += lVol;
4069	subdivVol += (*it)->GetVolume();
4070
4071	const float thres = 0.9f;
4072	if ((lVol < ((it)->GetVolume() thres)) \|\|
4073	(lVol * thres > ((*it)->GetVolume())))
4074	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4075	}
4076
4077	Debug << "exact volume: " << vol << endl;
4078	Debug << "subdivision volume: " << subdivVol << endl;
4079	Debug << "new volume: " << newVol << endl;
4080	}
4081
4082
4083	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4084	ViewCell *vc,
4085	const AxisAlignedBox3 *sceneBox,
4086	const AxisAlignedPlane *clipPlane
4087	) const
4088	{
4089	if (clipPlane)
4090	{
4091	const Plane3 plane = clipPlane->GetPlane();
4092
4093	ViewCellContainer leaves;
4094	mViewCellsTree->CollectLeaves(vc, leaves);
4095	ViewCellContainer::const_iterator it, it_end = leaves.end();
4096
4097	for (it = leaves.begin(); it != it_end; ++ it)
4098	{
4099	BspNodeGeometry geom;
4100	BspNodeGeometry front;
4101	BspNodeGeometry back;
4102
4103	mBspTree->ConstructGeometry(*it, geom);
4104
4105	const float eps = 0.0001f;
4106	const int cf = geom.Side(plane, eps);
4107
4108	if (cf == -1)
4109	{
4110	exporter->ExportPolygons(geom.GetPolys());
4111	}
4112	else if (cf == 0)
4113	{
4114	geom.SplitGeometry(front,
4115	back,
4116	plane,
4117	mViewSpaceBox,
4118	eps);
4119
4120	if (back.Valid())
4121	{
4122	exporter->ExportPolygons(back.GetPolys());
4123	}
4124	}
4125	}
4126	}
4127	else
4128	{
4129	// export mesh if available
4130	// TODO: some bug here?
4131	if (1 && vc->GetMesh())
4132	{
4133	exporter->ExportMesh(vc->GetMesh());
4134	}
4135	else
4136	{
4137	BspNodeGeometry geom;
4138	mBspTree->ConstructGeometry(vc, geom);
4139	exporter->ExportPolygons(geom.GetPolys());
4140	}
4141	}
4142	}
4143
4144
4145	void BspViewCellsManager::CreateMesh(ViewCell *vc)
4146	{
4147	// note: should previous mesh be deleted (via mesh manager?)
4148	BspNodeGeometry geom;
4149	mBspTree->ConstructGeometry(vc, geom);
4150
4151	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4152
4153	IncludeNodeGeomInMesh(geom, *mesh);
4154	mesh->ComputeBoundingBox();
4155
4156	vc->SetMesh(mesh);
4157	}
4158
4159
4160	void BspViewCellsManager::Finalize(ViewCell *viewCell,
4161	const bool createMesh)
4162	{
4163	float area = 0;
4164	float volume = 0;
4165
4166	ViewCellContainer leaves;
4167	mViewCellsTree->CollectLeaves(viewCell, leaves);
4168
4169	ViewCellContainer::const_iterator it, it_end = leaves.end();
4170
4171	for (it = leaves.begin(); it != it_end; ++ it)
4172	{
4173	BspNodeGeometry geom;
4174
4175	mBspTree->ConstructGeometry(*it, geom);
4176
4177	const float lVol = geom.GetVolume();
4178	const float lArea = geom.GetArea();
4179
4180	area += lArea;
4181	volume += lVol;
4182
4183	CreateMesh(*it);
4184	}
4185
4186	viewCell->SetVolume(volume);
4187	viewCell->SetArea(area);
4188	}
4189
4190
4191	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4192	{
4193	if (!ViewCellsConstructed())
4194	{
4195	return NULL;
4196	}
4197	if (!mViewSpaceBox.IsInside(point))
4198	{
4199	return NULL;
4200	}
4201	return mBspTree->GetViewCell(point);
4202	}
4203
4204
4205	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4206	vector<MergeCandidate> &candidates)
4207	{
4208	cout << "collecting merge candidates ... " << endl;
4209
4210	if (mUseRaysForMerge)
4211	{
4212	mBspTree->CollectMergeCandidates(rays, candidates);
4213	}
4214	else
4215	{
4216	vector<BspLeaf *> leaves;
4217	mBspTree->CollectLeaves(leaves);
4218	mBspTree->CollectMergeCandidates(leaves, candidates);
4219	}
4220
4221	cout << "fininshed collecting candidates" << endl;
4222	}
4223
4224
4225
4226	bool BspViewCellsManager::ExportViewCells(const string filename,
4227	const bool exportPvs,
4228	const ObjectContainer &objects)
4229	{
4230	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
4231	{
4232	return false;
4233	}
4234
4235	cout << "exporting view cells to xml ... ";
4236
4237	OUT_STREAM stream(filename.c_str());
4238
4239	// we need unique ids for each view cell
4240	CreateUniqueViewCellIds();
4241
4242	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
4243	stream << "<VisibilitySolution>" << endl;
4244
4245	if (exportPvs)
4246	{
4247	//////////
4248	//-- export bounding boxes: they are used to identify the objects from the pvs and
4249	//-- assign them to the entities in the rendering engine
4250
4251	stream << "<BoundingBoxes>" << endl;
4252	ObjectContainer::const_iterator oit, oit_end = objects.end();
4253
4254	for (oit = objects.begin(); oit != oit_end; ++ oit)
4255	{
4256	const AxisAlignedBox3 box = (*oit)->GetBox();
4257
4258	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
4259	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
4260	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
4261	}
4262
4263	stream << "</BoundingBoxes>" << endl;
4264	}
4265
4266	///////////
4267	//-- export the view cells and the pvs
4268
4269	const int numViewCells = mCurrentViewCellsStats.viewCells;
4270	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
4271
4272	mViewCellsTree->Export(stream, exportPvs);
4273
4274	stream << "</ViewCells>" << endl;
4275
4276	/////////////
4277	//-- export the view space hierarchy
4278	stream << "<ViewSpaceHierarchy type=\"bsp\""
4279	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
4280	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
4281
4282	mBspTree->Export(stream);
4283
4284	// end tags
4285	stream << "</ViewSpaceHierarchy>" << endl;
4286	stream << "</VisibilitySolution>" << endl;
4287
4288	stream.close();
4289	cout << "finished" << endl;
4290
4291	return true;
4292	}
4293
4294
4295	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
4296	{
4297	ViewCellInterior *vcRoot = new ViewCellInterior();
4298
4299	// evaluate merge cost for priority traversal
4300	const float mergeCost = -(float)root->mTimeStamp;
4301	vcRoot->SetMergeCost(mergeCost);
4302
4303	float volume = 0;
4304	vector<BspLeaf *> leaves;
4305	mBspTree->CollectLeaves(leaves);
4306	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
4307	ViewCell::NewMail();
4308
4309	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4310	{
4311	BspLeaf leaf = lit;
4312	ViewCell *vc = leaf->GetViewCell();
4313
4314	if (!vc->Mailed())
4315	{
4316	vc->Mail();
4317	vc->SetMergeCost(0.0f);
4318	vcRoot->SetupChildLink(vc);
4319
4320	volume += vc->GetVolume();
4321	volume += vc->GetVolume();
4322	vcRoot->SetVolume(volume);
4323	}
4324	}
4325
4326	return vcRoot;
4327	}
4328
4329
4330	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4331	{
4332	// terminate recursion
4333	if (root->IsLeaf())
4334	{
4335	BspLeaf leaf = static_cast<BspLeaf >(root);
4336	leaf->GetViewCell()->SetMergeCost(0.0f);
4337	return leaf->GetViewCell();
4338	}
4339
4340	BspInterior interior = static_cast<BspInterior >(root);
4341	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4342
4343	// evaluate merge cost for priority traversal
4344	const float mergeCost = -(float)root->mTimeStamp;
4345	viewCellInterior->SetMergeCost(mergeCost);
4346
4347	float volume = 0;
4348
4349	BspNode *front = interior->GetFront();
4350	BspNode *back = interior->GetBack();
4351
4352
4353	////////////
4354	//-- recursivly compute child hierarchies
4355
4356	ViewCell *backVc = ConstructSpatialMergeTree(back);
4357	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4358
4359	viewCellInterior->SetupChildLink(backVc);
4360	viewCellInterior->SetupChildLink(frontVc);
4361
4362	volume += backVc->GetVolume();
4363	volume += frontVc->GetVolume();
4364
4365	viewCellInterior->SetVolume(volume);
4366
4367	return viewCellInterior;
4368	}
4369
4370
4371	/************************************************************************/
4372	/* KdViewCellsManager implementation */
4373	/************************************************************************/
4374
4375
4376
4377	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
4378	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
4379	{
4380	}
4381
4382
4383	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
4384	{
4385	// compute view cell area / volume as subsititute for probability
4386	if (0)
4387	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
4388	else
4389	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
4390	}
4391
4392
4393
4394
4395	void KdViewCellsManager::CollectViewCells()
4396	{
4397	//mKdTree->CollectViewCells(mViewCells); TODO
4398	}
4399
4400
4401	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4402	const VssRayContainer &rays)
4403	{
4404	// if view cells already constructed
4405	if (ViewCellsConstructed())
4406	return 0;
4407
4408	mKdTree->Construct();
4409
4410	mTotalAreaValid = false;
4411	// create the view cells
4412	mKdTree->CreateAndCollectViewCells(mViewCells);
4413	// cast rays
4414	ComputeSampleContributions(rays, true, false);
4415
4416	EvaluateViewCellsStats();
4417	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4418
4419	return 0;
4420	}
4421
4422
4423	bool KdViewCellsManager::ViewCellsConstructed() const
4424	{
4425	return mKdTree->GetRoot() != NULL;
4426	}
4427
4428
4429	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
4430	const VssRayContainer &rays)
4431	{
4432	return 0;
4433	}
4434
4435
4436	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4437	const int maxViewCells,
4438	const bool sortViewCells,
4439	const bool exportPvs,
4440	const bool exportRays,
4441	const int maxRays,
4442	const string &prefix,
4443	VssRayContainer *visRays)
4444	{
4445	// TODO
4446	}
4447
4448
4449	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
4450	const VssRayContainer &sampleRays)
4451	{
4452	if (!ViewCellsConstructed())
4453	return;
4454
4455	// using view cells instead of the kd PVS of objects
4456	const bool useViewCells = true;
4457	bool exportRays = false;
4458
4459	int limit = min(mVisualizationSamples, (int)sampleRays.size());
4460	const int pvsOut = min((int)objects.size(), 10);
4461	VssRayContainer *rays = new VssRayContainer[pvsOut];
4462
4463	if (useViewCells)
4464	{
4465	const int leafOut = 10;
4466
4467	ViewCell::NewMail();
4468
4469	//-- some rays for visualization
4470	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4471	Debug << "visualization using " << raysOut << " samples" << endl;
4472
4473	//-- some random view cells and rays for visualization
4474	vector<KdLeaf *> kdLeaves;
4475
4476	for (int i = 0; i < leafOut; ++ i)
4477	kdLeaves.push_back(static_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4478
4479	for (int i = 0; i < kdLeaves.size(); ++ i)
4480	{
4481	KdLeaf *leaf = kdLeaves[i];
4482	RayContainer vcRays;
4483
4484	cout << "creating output for view cell " << i << " ... ";
4485	#if 0
4486	// check whether we can add the current ray to the output rays
4487	for (int k = 0; k < raysOut; ++ k)
4488	{
4489	Ray *ray = sampleRays[k];
4490
4491	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4492	{
4493	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4494
4495	if (leaf->GetViewCell() == leaf2->GetViewCell())
4496	{
4497	vcRays.push_back(ray);
4498	}
4499	}
4500	}
4501	#endif
4502	Intersectable::NewMail();
4503
4504	ViewCell *vc = leaf->mViewCell;
4505	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4506
4507	Exporter *exporter = Exporter::GetExporter(str);
4508	exporter->SetFilled();
4509
4510	exporter->SetWireframe();
4511	//exporter->SetFilled();
4512
4513	Material m;//= RandomMaterial();
4514	m.mDiffuseColor = RgbColor(1, 1, 0);
4515	exporter->SetForcedMaterial(m);
4516
4517	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4518	exporter->ExportBox(box);
4519
4520	// export rays piercing this view cell
4521	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4522
4523	m.mDiffuseColor = RgbColor(1, 0, 0);
4524	exporter->SetForcedMaterial(m);
4525
4526	// exporter->SetWireframe();
4527	exporter->SetFilled();
4528
4529	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4530
4531	while (pit.HasMoreEntries())
4532	{
4533	//-- output PVS of view cell
4534	Intersectable *intersect = pit.Next();
4535
4536	if (!intersect->Mailed())
4537	{
4538	exporter->ExportIntersectable(intersect);
4539	intersect->Mail();
4540	}
4541	}
4542
4543	DEL_PTR(exporter);
4544	cout << "finished" << endl;
4545	}
4546
4547	DEL_PTR(rays);
4548	}
4549	else // using kd PVS of objects
4550	{
4551	for (int i = 0; i < limit; ++ i)
4552	{
4553	VssRay *ray = sampleRays[i];
4554
4555	// check whether we can add this to the rays
4556	for (int j = 0; j < pvsOut; j++)
4557	{
4558	if (objects[j] == ray->mTerminationObject)
4559	{
4560	rays[j].push_back(ray);
4561	}
4562	}
4563	}
4564
4565	if (exportRays)
4566	{
4567	Exporter *exporter = NULL;
4568	exporter = Exporter::GetExporter("sample-rays.x3d");
4569	exporter->SetWireframe();
4570	exporter->ExportKdTree(*mKdTree);
4571
4572	for (int i = 0; i < pvsOut; i++)
4573	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4574
4575	exporter->SetFilled();
4576	delete exporter;
4577	}
4578
4579	for (int k=0; k < pvsOut; k++)
4580	{
4581	Intersectable *object = objects[k];
4582	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4583
4584	Exporter *exporter = Exporter::GetExporter(str);
4585	exporter->SetWireframe();
4586
4587	// matt: we do not use kd pvs
4588	#if 0
4589	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4590	Intersectable::NewMail();
4591
4592	// avoid adding the object to the list
4593	object->Mail();
4594	ObjectContainer visibleObjects;
4595
4596	for (; kit != object->mKdPvs.mEntries.end(); i++)
4597	{
4598	KdNode node = (kit).first;
4599	exporter->ExportBox(mKdTree->GetBox(node));
4600
4601	mKdTree->CollectObjects(node, visibleObjects);
4602	}
4603
4604	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4605	exporter->SetFilled();
4606
4607	for (int j = 0; j < visibleObjects.size(); j++)
4608	exporter->ExportIntersectable(visibleObjects[j]);
4609
4610	Material m;
4611	m.mDiffuseColor = RgbColor(1, 0, 0);
4612	exporter->SetForcedMaterial(m);
4613	exporter->ExportIntersectable(object);
4614	#endif
4615	delete exporter;
4616	}
4617	}
4618	}
4619
4620
4621	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4622	{
4623	return new KdViewCell(mesh);
4624	}
4625
4626
4627	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4628	ViewCell *vc,
4629	const AxisAlignedBox3 *sceneBox,
4630	const AxisAlignedPlane *clipPlane
4631	) const
4632	{
4633	ViewCellContainer leaves;
4634	mViewCellsTree->CollectLeaves(vc, leaves);
4635	ViewCellContainer::const_iterator it, it_end = leaves.end();
4636
4637	for (it = leaves.begin(); it != it_end; ++ it)
4638	{
4639	KdViewCell kdVc = static_cast<KdViewCell >(*it);
4640	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4641	}
4642	}
4643
4644
4645	int KdViewCellsManager::GetType() const
4646	{
4647	return ViewCellsManager::KD;
4648	}
4649
4650
4651
4652	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4653	{
4654	KdNode *node = leaf;
4655
4656	while (node->mParent && node->mDepth > mKdPvsDepth)
4657	node = node->mParent;
4658
4659	return node;
4660	}
4661
4662	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4663	const Vector3 &termination,
4664	ViewCellContainer &viewcells)
4665	{
4666	return mKdTree->CastLineSegment(origin, termination, viewcells);
4667	}
4668
4669
4670	bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
4671	const Vector3 &termination,
4672	ViewCell *viewCell)
4673	{
4674	return false;
4675	}
4676
4677
4678	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4679	{
4680	// TODO
4681	}
4682
4683
4684
4685	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4686	vector<MergeCandidate> &candidates)
4687	{
4688	// TODO
4689	}
4690
4691
4692
4693	/**************************************************************************/
4694	/* VspBspViewCellsManager implementation */
4695	/**************************************************************************/
4696
4697
4698	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4699	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4700	{
4701	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4702	mVspBspTree->SetViewCellsManager(this);
4703	mVspBspTree->mViewCellsTree = mViewCellsTree;
4704	}
4705
4706
4707	VspBspViewCellsManager::~VspBspViewCellsManager()
4708	{
4709	}
4710
4711
4712	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4713	{
4714	if (0 && mVspBspTree->mUseAreaForPvs)
4715	return GetArea(viewCell) / GetAccVcArea();
4716	else
4717	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4718	}
4719
4720
4721	void VspBspViewCellsManager::CollectViewCells()
4722	{
4723	// view cells tree constructed?
4724	if (!ViewCellsTreeConstructed())
4725	{
4726	mVspBspTree->CollectViewCells(mViewCells, false);
4727	}
4728	else
4729	{
4730	// we can use the view cells tree hierarchy to get the right set
4731	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4732	}
4733	}
4734
4735
4736	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4737	vector<MergeCandidate> &candidates)
4738	{
4739	cout << "collecting merge candidates ... " << endl;
4740
4741	if (mUseRaysForMerge)
4742	{
4743	mVspBspTree->CollectMergeCandidates(rays, candidates);
4744	}
4745	else
4746	{
4747	vector<BspLeaf *> leaves;
4748	mVspBspTree->CollectLeaves(leaves);
4749
4750	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4751	}
4752
4753	cout << "fininshed collecting candidates" << endl;
4754	}
4755
4756
4757	bool VspBspViewCellsManager::ViewCellsConstructed() const
4758	{
4759	return mVspBspTree->GetRoot() != NULL;
4760	}
4761
4762
4763	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4764	{
4765	return new BspViewCell(mesh);
4766	}
4767
4768
4769	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4770	const VssRayContainer &rays)
4771	{
4772	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4773
4774	// if view cells were already constructed
4775	if (ViewCellsConstructed())
4776	{
4777	return 0;
4778	}
4779
4780	int sampleContributions = 0;
4781	VssRayContainer sampleRays;
4782
4783	const int limit = min(mInitialSamples, (int)rays.size());
4784
4785	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4786	<< ", actual rays: " << (int)rays.size() << endl;
4787
4788	VssRayContainer savedRays;
4789
4790	if (SAMPLE_AFTER_SUBDIVISION)
4791	{
4792	VssRayContainer constructionRays;
4793
4794	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4795
4796	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4797	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4798
4799	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4800	}
4801	else
4802	{
4803	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4804	mVspBspTree->Construct(rays, &mViewSpaceBox);
4805	}
4806
4807	// collapse invalid regions
4808	cout << "collapsing invalid tree regions ... ";
4809	long startTime = GetTime();
4810
4811	const int collapsedLeaves = mVspBspTree->CollapseTree();
4812	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4813	<< " seconds" << endl;
4814
4815	cout << "finished" << endl;
4816
4817	/////////////////
4818	//-- stats after construction
4819
4820	Debug << mVspBspTree->GetStatistics() << endl;
4821
4822	ResetViewCells();
4823	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4824
4825
4826	//////////////////////
4827	//-- recast the rest of the rays
4828
4829	startTime = GetTime();
4830
4831	cout << "Computing remaining ray contributions ... ";
4832
4833	if (SAMPLE_AFTER_SUBDIVISION)
4834	ComputeSampleContributions(savedRays, true, false);
4835
4836	cout << "finished" << endl;
4837
4838	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4839	<< " secs" << endl;
4840
4841	cout << "construction finished" << endl;
4842
4843	if (0)
4844	{ ////////
4845	//-- real meshes are contructed at this stage
4846
4847	cout << "finalizing view cells ... ";
4848	FinalizeViewCells(true);
4849	cout << "finished" << endl;
4850	}
4851
4852	return sampleContributions;
4853	}
4854
4855
4856	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4857	const ObjectContainer &objects)
4858	{
4859	int vcSize = 0;
4860	int pvsSize = 0;
4861
4862	//-- merge view cells
4863	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4864	long startTime = GetTime();
4865
4866
4867	if (mMergeViewCells)
4868	{
4869	// TODO: should be done BEFORE the ray casting
4870	// compute tree by merging the nodes based on cost heuristics
4871	mViewCellsTree->ConstructMergeTree(rays, objects);
4872	}
4873	else
4874	{
4875	// compute tree by merging the nodes of the spatial hierarchy
4876	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4877	mViewCellsTree->SetRoot(root);
4878
4879	// compute pvs
4880	ObjectPvs pvs;
4881	UpdatePvsForEvaluation(root, pvs);
4882	}
4883
4884	if (1)
4885	{
4886	char mstats[100];
4887	ObjectPvs pvs;
4888
4889	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4890	mViewCellsTree->ExportStats(mstats);
4891	}
4892
4893	cout << "merged view cells in "
4894	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4895
4896	Debug << "Postprocessing: Merged view cells in "
4897	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4898
4899
4900	//////////////////
4901	//-- stats and visualizations
4902
4903	int savedColorCode = mColorCode;
4904
4905	// get currently active view cell set
4906	ResetViewCells();
4907	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4908
4909	if (mShowVisualization) // export merged view cells
4910	{
4911	mColorCode = 0;
4912	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4913
4914	cout << "exporting view cells after merge ... ";
4915
4916	if (exporter)
4917	{
4918	if (0)
4919	exporter->SetWireframe();
4920	else
4921	exporter->SetFilled();
4922
4923	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4924
4925	if (mExportGeometry)
4926	{
4927	Material m;
4928	m.mDiffuseColor = RgbColor(0, 1, 0);
4929	exporter->SetForcedMaterial(m);
4930	exporter->SetFilled();
4931
4932	exporter->ExportGeometry(objects);
4933	}
4934
4935	delete exporter;
4936	}
4937	cout << "finished" << endl;
4938	}
4939
4940	mColorCode = savedColorCode;
4941	}
4942
4943
4944	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4945	const ObjectContainer &objects)
4946	{
4947	mRenderer->RenderScene();
4948
4949	SimulationStatistics ss;
4950	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4951	Debug << "render time before refine\n\n" << ss << endl;
4952
4953	const long startTime = GetTime();
4954	cout << "Refining the merged view cells ... ";
4955
4956	// refining the merged view cells
4957	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4958
4959	//-- stats and visualizations
4960	cout << "finished" << endl;
4961	cout << "refined " << refined << " view cells in "
4962	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4963
4964	Debug << "Postprocessing: refined " << refined << " view cells in "
4965	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4966	}
4967
4968
4969	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4970	const VssRayContainer &rays)
4971	{
4972	if (!ViewCellsConstructed())
4973	{
4974	Debug << "postprocess error: no view cells constructed" << endl;
4975	return 0;
4976	}
4977
4978	// view cells already finished before post processing step
4979	// (i.e. because they were loaded)
4980	if (mViewCellsFinished)
4981	{
4982	FinalizeViewCells(true);
4983	EvaluateViewCellsStats();
4984
4985	return 0;
4986	}
4987
4988	// check if new view cells turned invalid
4989	int minPvs, maxPvs;
4990
4991	if (0)
4992	{
4993	minPvs = mMinPvsSize;
4994	maxPvs = mMaxPvsSize;
4995	}
4996	else
4997	{
4998	// problem matt: why did I start here from zero?
4999	minPvs = 0;
5000	maxPvs = mMaxPvsSize;
5001	}
5002
5003	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5004	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5005
5006	SetValidity(minPvs, maxPvs);
5007
5008	// update valid view space according to valid view cells
5009	if (0) mVspBspTree->ValidateTree();
5010
5011	// area has to be recomputed
5012	mTotalAreaValid = false;
5013	VssRayContainer postProcessRays;
5014	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5015
5016	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5017
5018	//////////
5019	//-- merge neighbouring view cells
5020	MergeViewCells(postProcessRays, objects);
5021
5022	// refines the merged view cells
5023	if (0) RefineViewCells(postProcessRays, objects);
5024
5025
5026	///////////
5027	//-- render simulation after merge + refine
5028
5029	cout << "\nview cells partition render time before compress" << endl << endl;;
5030	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5031	SimulationStatistics ss;
5032	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5033	cout << ss << endl;
5034
5035	if (0) CompressViewCells();
5036
5037	// collapse sibling leaves that share the same view cell
5038	if (0) mVspBspTree->CollapseTree();
5039
5040	// recompute view cell list and statistics
5041	ResetViewCells();
5042
5043	// compute final meshes and volume / area
5044	if (1) FinalizeViewCells(true);
5045
5046	return 0;
5047	}
5048
5049
5050	int VspBspViewCellsManager::GetType() const
5051	{
5052	return VSP_BSP;
5053	}
5054
5055
5056	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
5057	{
5058	// terminate recursion
5059	if (root->IsLeaf())
5060	{
5061	BspLeaf leaf = static_cast<BspLeaf >(root);
5062	leaf->GetViewCell()->SetMergeCost(0.0f);
5063	return leaf->GetViewCell();
5064	}
5065
5066
5067	BspInterior interior = static_cast<BspInterior >(root);
5068	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5069
5070	// evaluate merge cost for priority traversal
5071	float mergeCost = 1.0f / (float)root->mTimeStamp;
5072	viewCellInterior->SetMergeCost(mergeCost);
5073
5074	float volume = 0;
5075
5076	BspNode *front = interior->GetFront();
5077	BspNode *back = interior->GetBack();
5078
5079
5080	ObjectPvs frontPvs, backPvs;
5081
5082	//-- recursivly compute child hierarchies
5083	ViewCell *backVc = ConstructSpatialMergeTree(back);
5084	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5085
5086
5087	viewCellInterior->SetupChildLink(backVc);
5088	viewCellInterior->SetupChildLink(frontVc);
5089
5090	volume += backVc->GetVolume();
5091	volume += frontVc->GetVolume();
5092
5093	viewCellInterior->SetVolume(volume);
5094
5095	return viewCellInterior;
5096	}
5097
5098
5099	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5100	{
5101	if (!ViewCellsConstructed())
5102	return ViewCellsManager::GetViewPoint(viewPoint);
5103
5104	// TODO: set reasonable limit
5105	const int limit = 20;
5106
5107	for (int i = 0; i < limit; ++ i)
5108	{
5109	viewPoint = mViewSpaceBox.GetRandomPoint();
5110	if (mVspBspTree->ViewPointValid(viewPoint))
5111	{
5112	return true;
5113	}
5114	}
5115
5116	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5117	return false;
5118	}
5119
5120
5121	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5122	{
5123	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5124	// validy update in preprocessor for all managers)
5125	return ViewCellsManager::ViewPointValid(viewPoint);
5126
5127	// return mViewSpaceBox.IsInside(viewPoint) &&
5128	// mVspBspTree->ViewPointValid(viewPoint);
5129	}
5130
5131
5132	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
5133	const VssRayContainer &sampleRays)
5134	{
5135	if (!ViewCellsConstructed())
5136	return;
5137
5138	VssRayContainer visRays;
5139	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5140
5141	if (1)
5142	{
5143	//////////////////
5144	//-- export final view cell partition
5145
5146	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5147
5148	if (exporter)
5149	{
5150	cout << "exporting view cells after post process ... ";
5151
5152	if (0)
5153	{ // export view space box
5154	exporter->SetWireframe();
5155	exporter->ExportBox(mViewSpaceBox);
5156	exporter->SetFilled();
5157	}
5158
5159	Material m;
5160	m.mDiffuseColor.r = 0.0f;
5161	m.mDiffuseColor.g = 0.5f;
5162	m.mDiffuseColor.b = 0.5f;
5163
5164	exporter->SetForcedMaterial(m);
5165
5166	if (1 && mExportGeometry)
5167	{
5168	exporter->ExportGeometry(objects);
5169	}
5170
5171	if (0 && mExportRays)
5172	{
5173	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
5174	}
5175	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5176
5177	delete exporter;
5178	cout << "finished" << endl;
5179	}
5180	}
5181
5182	////////////////
5183	//-- visualization of the BSP splits
5184
5185	bool exportSplits = false;
5186	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
5187
5188	if (exportSplits)
5189	{
5190	cout << "exporting splits ... ";
5191	ExportSplits(objects, visRays);
5192	cout << "finished" << endl;
5193	}
5194
5195	////////
5196	//-- export single view cells
5197
5198	int leafOut;
5199	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5200	const int raysOut = 100;
5201
5202	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5203	}
5204
5205
5206	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
5207	const VssRayContainer &rays)
5208	{
5209	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
5210
5211	if (exporter)
5212	{
5213	Material m;
5214	m.mDiffuseColor = RgbColor(1, 0, 0);
5215	exporter->SetForcedMaterial(m);
5216	exporter->SetWireframe();
5217
5218	exporter->ExportBspSplits(*mVspBspTree, true);
5219
5220	// take forced material, else big scenes cannot be viewed
5221	m.mDiffuseColor = RgbColor(0, 1, 0);
5222	exporter->SetForcedMaterial(m);
5223	exporter->SetFilled();
5224
5225	exporter->ResetForcedMaterial();
5226
5227	// export rays
5228	if (mExportRays)
5229	{
5230	exporter->ExportRays(rays, RgbColor(1, 1, 0));
5231	}
5232
5233	if (mExportGeometry)
5234	{
5235	exporter->ExportGeometry(objects);
5236	}
5237	delete exporter;
5238	}
5239	}
5240
5241
5242	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5243	const int maxViewCells,
5244	const bool sortViewCells,
5245	const bool exportPvs,
5246	const bool exportRays,
5247	const int maxRays,
5248	const string &prefix,
5249	VssRayContainer *visRays)
5250	{
5251	if (sortViewCells)
5252	{
5253	// sort view cells to visualize the largest view cells
5254	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
5255	}
5256
5257	//////////
5258	//-- export some view cells for visualization
5259
5260	ViewCell::NewMail();
5261	const int limit = min(maxViewCells, (int)mViewCells.size());
5262
5263	for (int i = 0; i < limit; ++ i)
5264	{
5265	cout << "creating output for view cell " << i << " ... ";
5266
5267	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
5268	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
5269
5270	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
5271	continue;
5272
5273	vc->Mail();
5274
5275	ObjectPvs pvs;
5276	mViewCellsTree->GetPvs(vc, pvs);
5277
5278	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5279	Exporter *exporter = Exporter::GetExporter(s);
5280
5281	const float pvsCost = mViewCellsTree->GetTrianglesInPvs(vc);
5282	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
5283
5284	if (exportRays)
5285	{
5286	////////////
5287	//-- export rays piercing this view cell
5288
5289	// take rays stored with the view cells during subdivision
5290	VssRayContainer vcRays;
5291	VssRayContainer collectRays;
5292
5293	// collect initial view cells
5294	ViewCellContainer leaves;
5295	mViewCellsTree->CollectLeaves(vc, leaves);
5296
5297	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5298	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5299	{
5300	BspLeaf vcLeaf = static_cast<BspViewCell >(*vit)->mLeaves[0];
5301	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5302
5303	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5304	{
5305	collectRays.push_back(*rit);
5306	}
5307	}
5308
5309	const int raysOut = min((int)collectRays.size(), maxRays);
5310
5311	// prepare some rays for visualization
5312	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5313	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5314	{
5315	const float p = RandomValue(0.0f, (float)collectRays.size());
5316
5317	if (p < raysOut)
5318	{
5319	vcRays.push_back(*rit);
5320	}
5321	}
5322
5323	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5324	}
5325
5326	////////////////
5327	//-- export view cell geometry
5328
5329	exporter->SetWireframe();
5330
5331	Material m;//= RandomMaterial();
5332	m.mDiffuseColor = RgbColor(0, 1, 0);
5333	exporter->SetForcedMaterial(m);
5334
5335	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5336	exporter->SetFilled();
5337
5338	if (exportPvs)
5339	{
5340	Intersectable::NewMail();
5341	ObjectPvsIterator pit = pvs.GetIterator();
5342
5343	cout << endl;
5344
5345	// output PVS of view cell
5346	while (pit.HasMoreEntries())
5347	{
5348	Intersectable *intersect = pit.Next();
5349
5350	if (!intersect->Mailed())
5351	{
5352	intersect->Mail();
5353
5354	m = RandomMaterial();
5355	exporter->SetForcedMaterial(m);
5356	exporter->ExportIntersectable(intersect);
5357	}
5358	}
5359	cout << endl;
5360	}
5361
5362	DEL_PTR(exporter);
5363	cout << "finished" << endl;
5364	}
5365	}
5366
5367
5368	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
5369	{
5370	Exporter *exporter = Exporter::GetExporter("filter.x3d");
5371
5372	Vector3 bsize = mViewSpaceBox.Size();
5373	const Vector3 viewPoint(mViewSpaceBox.Center());
5374	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
5375	const Vector3 width = Vector3(w);
5376
5377	PrVs testPrVs;
5378
5379	if (exporter)
5380	{
5381	ViewCellContainer viewCells;
5382
5383	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
5384
5385	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
5386
5387	exporter->SetWireframe();
5388
5389	exporter->SetForcedMaterial(RgbColor(1,1,1));
5390	exporter->ExportBox(tbox);
5391
5392	exporter->SetFilled();
5393
5394	exporter->SetForcedMaterial(RgbColor(0,1,0));
5395	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
5396
5397	//exporter->ResetForcedMaterial();
5398	exporter->SetForcedMaterial(RgbColor(0,0,1));
5399	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
5400
5401	exporter->SetForcedMaterial(RgbColor(1,0,0));
5402	exporter->ExportGeometry(objects);
5403
5404	delete exporter;
5405	}
5406	}
5407
5408
5409	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5410	ViewCellContainer &viewCells) const
5411	{
5412	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
5413	}
5414
5415
5416	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
5417	const Vector3 &termination,
5418	ViewCellContainer &viewcells)
5419	{
5420	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
5421	}
5422
5423
5424	bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
5425	const Vector3 &termination,
5426	ViewCell *viewCell)
5427	{
5428	return false;
5429	}
5430
5431
5432	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
5433	{
5434	int numSamples;
5435
5436	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
5437	cout << "samples" << numSamples << endl;
5438
5439	vector<RenderCostSample> samples;
5440
5441	if (!mPreprocessor->GetRenderer())
5442	return;
5443
5444	//start the view point queries
5445	long startTime = GetTime();
5446	cout << "starting sampling of render cost ... ";
5447
5448	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
5449
5450	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
5451
5452
5453	// for each sample:
5454	// find view cells associated with the samples
5455	// store the sample pvs with the pvs associated with the view cell
5456	//
5457	// for each view cell:
5458	// compute difference point sampled pvs - view cell pvs
5459	// export geometry with color coded pvs difference
5460
5461	std::map<ViewCell *, ObjectPvs> sampleMap;
5462
5463	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5464
5465	for (rit = samples.begin(); rit != rit_end; ++ rit)
5466	{
5467	RenderCostSample sample = *rit;
5468
5469	ViewCell *vc = GetViewCell(sample.mPosition);
5470
5471	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5472
5473	if (it == sampleMap.end())
5474	{
5475	sampleMap[vc] = sample.mPvs;
5476	}
5477	else
5478	{
5479	(*it).second.MergeInPlace(sample.mPvs);
5480	}
5481	}
5482
5483	// visualize the view cells
5484	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5485
5486	Material m;//= RandomMaterial();
5487
5488	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5489	{
5490	ViewCell vc = (vit).first;
5491
5492	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5493	const int pvsPtSamples = (*vit).second.GetSize();
5494
5495	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5496	m.mDiffuseColor.b = 1.0f;
5497	//exporter->SetForcedMaterial(m);
5498	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5499
5500	/* // counting the pvss
5501	for (rit = samples.begin(); rit != rit_end; ++ rit)
5502	{
5503	RenderCostSample sample = *rit;
5504	ViewCell *vc = GetViewCell(sample.mPosition);
5505
5506	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5507	Mesh *hMesh = CreateMeshFromBox(box);
5508
5509	DEL_PTR(hMesh);
5510	}
5511	*/
5512	}
5513	}
5514
5515
5516	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5517	ViewCell *vc,
5518	const AxisAlignedBox3 *sceneBox,
5519	const AxisAlignedPlane *clipPlane
5520	) const
5521	{
5522	if (clipPlane)
5523	{
5524	const Plane3 plane = clipPlane->GetPlane();
5525
5526	ViewCellContainer leaves;
5527	mViewCellsTree->CollectLeaves(vc, leaves);
5528	ViewCellContainer::const_iterator it, it_end = leaves.end();
5529
5530	for (it = leaves.begin(); it != it_end; ++ it)
5531	{
5532	BspNodeGeometry geom;
5533	BspNodeGeometry front;
5534	BspNodeGeometry back;
5535
5536	mVspBspTree->ConstructGeometry(*it, geom);
5537
5538	const float eps = 0.0001f;
5539	const int cf = geom.Side(plane, eps);
5540
5541	if (cf == -1)
5542	{
5543	exporter->ExportPolygons(geom.GetPolys());
5544	}
5545	else if (cf == 0)
5546	{
5547	geom.SplitGeometry(front,
5548	back,
5549	plane,
5550	mViewSpaceBox,
5551	eps);
5552
5553	if (back.Valid())
5554	{
5555	exporter->ExportPolygons(back.GetPolys());
5556	}
5557	}
5558	}
5559	}
5560	else
5561	{
5562	// export mesh if available
5563	// TODO: some bug here?
5564	if (1 && vc->GetMesh())
5565	{
5566	exporter->ExportMesh(vc->GetMesh());
5567	}
5568	else
5569	{
5570	BspNodeGeometry geom;
5571	mVspBspTree->ConstructGeometry(vc, geom);
5572	exporter->ExportPolygons(geom.GetPolys());
5573	}
5574	}
5575	}
5576
5577
5578	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5579	{
5580	ViewCellContainer leaves;
5581	mViewCellsTree->CollectLeaves(vc, leaves);
5582
5583	int maxDist = 0;
5584
5585	// compute max height difference
5586	for (int i = 0; i < (int)leaves.size(); ++ i)
5587	{
5588	for (int j = 0; j < (int)leaves.size(); ++ j)
5589	{
5590	BspLeaf leaf = static_cast<BspViewCell >(leaves[i])->mLeaves[0];
5591
5592	if (i != j)
5593	{
5594	BspLeaf leaf2 =static_cast<BspViewCell >(leaves[j])->mLeaves[0];
5595	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5596
5597	if (dist > maxDist)
5598	maxDist = dist;
5599	}
5600	}
5601	}
5602
5603	return maxDist;
5604	}
5605
5606
5607	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5608	{
5609	if (!ViewCellsConstructed())
5610	return NULL;
5611
5612	if (!mViewSpaceBox.IsInside(point))
5613	return NULL;
5614
5615	return mVspBspTree->GetViewCell(point, active);
5616	}
5617
5618
5619	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5620	{
5621	BspNodeGeometry geom;
5622	mVspBspTree->ConstructGeometry(vc, geom);
5623
5624	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5625
5626	IncludeNodeGeomInMesh(geom, *mesh);
5627	mesh->ComputeBoundingBox();
5628
5629	vc->SetMesh(mesh);
5630	}
5631
5632
5633	int VspBspViewCellsManager::CastBeam(Beam &beam)
5634	{
5635	return mVspBspTree->CastBeam(beam);
5636	}
5637
5638
5639	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5640	const bool createMesh)
5641	{
5642	float area = 0;
5643	float volume = 0;
5644
5645	ViewCellContainer leaves;
5646	mViewCellsTree->CollectLeaves(viewCell, leaves);
5647
5648	ViewCellContainer::const_iterator it, it_end = leaves.end();
5649
5650	for (it = leaves.begin(); it != it_end; ++ it)
5651	{
5652	BspNodeGeometry geom;
5653	mVspBspTree->ConstructGeometry(*it, geom);
5654
5655	const float lVol = geom.GetVolume();
5656	const float lArea = geom.GetArea();
5657
5658	area += lArea;
5659	volume += lVol;
5660
5661	if (createMesh)
5662	CreateMesh(*it);
5663	}
5664
5665	viewCell->SetVolume(volume);
5666	viewCell->SetArea(area);
5667	}
5668
5669
5670	void VspBspViewCellsManager::TestSubdivision()
5671	{
5672	ViewCellContainer leaves;
5673	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5674
5675	ViewCellContainer::const_iterator it, it_end = leaves.end();
5676
5677	const float vol = mViewSpaceBox.GetVolume();
5678	float subdivVol = 0;
5679	float newVol = 0;
5680
5681	for (it = leaves.begin(); it != it_end; ++ it)
5682	{
5683	BspNodeGeometry geom;
5684	mVspBspTree->ConstructGeometry(*it, geom);
5685
5686	const float lVol = geom.GetVolume();
5687
5688	newVol += lVol;
5689	subdivVol += (*it)->GetVolume();
5690
5691	float thres = 0.9f;
5692	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5693	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5694	}
5695
5696	Debug << "exact volume: " << vol << endl;
5697	Debug << "subdivision volume: " << subdivVol << endl;
5698	Debug << "new volume: " << newVol << endl;
5699	}
5700
5701
5702	void VspBspViewCellsManager::PrepareLoadedViewCells()
5703	{
5704	// TODO: do I still need this here?
5705	if (0) mVspBspTree->RepairViewCellsLeafLists();
5706	}
5707
5708
5709
5710	/************************************************************************/
5711	/* VspOspViewCellsManager implementation */
5712	/************************************************************************/
5713
5714
5715	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5716	const string &hierarchyType)
5717	: ViewCellsManager(vcTree)
5718	{
5719	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5720	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5721
5722	Debug << "compressing objects: " << mCompressObjects << endl;
5723	cout << "compressing objects: " << mCompressObjects << endl;
5724
5725	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5726
5727	mHierarchyManager->SetViewCellsManager(this);
5728	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5729	}
5730
5731
5732	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5733	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5734	{
5735	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5736	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5737
5738	Debug << "compressing objects: " << mCompressObjects << endl;
5739	cout << "compressing objects: " << mCompressObjects << endl;
5740
5741	mHierarchyManager->SetViewCellsManager(this);
5742	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5743	}
5744
5745
5746	Intersectable *VspOspViewCellsManager::GetIntersectable(const VssRay &ray,
5747	const bool isTermination) const
5748	{
5749	if (mUseKdPvs)
5750	return ViewCellsManager::GetIntersectable(ray, isTermination);
5751	else
5752	return mHierarchyManager->GetIntersectable(ray, isTermination);
5753	}
5754
5755
5756	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5757	{
5758	HierarchyManager *hierarchyManager;
5759
5760	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5761	{
5762	Debug << "hierarchy manager: osp" << endl;
5763	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5764	}
5765	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5766	{
5767	Debug << "hierarchy manager: bvh" << endl;
5768	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5769	}
5770	else // only view space partition
5771	{
5772	Debug << "hierarchy manager: obj" << endl;
5773	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5774	}
5775
5776	return hierarchyManager;
5777	}
5778
5779
5780	VspOspViewCellsManager::~VspOspViewCellsManager()
5781	{
5782	DEL_PTR(mHierarchyManager);
5783	}
5784
5785
5786	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5787	{
5788	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5789	}
5790
5791
5792	void VspOspViewCellsManager::CollectViewCells()
5793	{
5794	// view cells tree constructed
5795	if (!ViewCellsTreeConstructed())
5796	{
5797	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5798	}
5799	else
5800	{ // we can use the view cells tree hierarchy to get the right set
5801	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5802	}
5803	}
5804
5805
5806	bool VspOspViewCellsManager::ViewCellsConstructed() const
5807	{
5808	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5809	}
5810
5811
5812	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5813	{
5814	return new VspViewCell(mesh);
5815	}
5816
5817
5818	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5819	const VssRayContainer &rays)
5820	{
5821	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5822
5823	// skip rest if view cells were already constructed
5824	if (ViewCellsConstructed())
5825	return 0;
5826
5827	int sampleContributions = 0;
5828	VssRayContainer sampleRays;
5829
5830	int limit = min (mInitialSamples, (int)rays.size());
5831
5832	VssRayContainer constructionRays;
5833	VssRayContainer savedRays;
5834
5835	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5836	<< ", actual rays: " << (int)rays.size() << endl;
5837
5838	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5839
5840	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5841	Debug << "saved rays: " << (int)savedRays.size() << endl;
5842
5843	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5844
5845	#if TEST_EVALUATION
5846	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5847	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5848	{
5849	storedRays.push_back(new VssRay((tit)));
5850	}
5851	#endif
5852
5853	/////////////////////////
5854	//-- print satistics for subdivision and view cells
5855
5856	Debug << endl << endl << *mHierarchyManager << endl;
5857
5858	ResetViewCells();
5859	//Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5860
5861	//////////////
5862	//-- recast rest of rays
5863
5864	const long startTime = GetTime();
5865	cout << "Computing remaining ray contributions ... ";
5866
5867	if (SAMPLE_AFTER_SUBDIVISION)
5868	ComputeSampleContributions(savedRays, true, false);
5869
5870	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5871	<< " secs" << endl;
5872
5873	if (0)
5874	{
5875	// real meshes are constructed at this stage
5876	cout << "finalizing view cells ... ";
5877	FinalizeViewCells(true);
5878	cout << "finished" << endl;
5879	}
5880
5881	return sampleContributions;
5882	}
5883
5884
5885	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5886	const VssRayContainer &rays)
5887	{
5888	if (!ViewCellsConstructed())
5889	{
5890	Debug << "post process error: no view cells constructed" << endl;
5891	return 0;
5892	}
5893
5894	// if view cells were already constructed before post processing step
5895	// (e.g., because they were loaded), we are finished
5896	if (mViewCellsFinished)
5897	{
5898	FinalizeViewCells(true);
5899	EvaluateViewCellsStats();
5900
5901	return 0;
5902	}
5903
5904	// check if new view cells turned invalid
5905	int minPvs, maxPvs;
5906
5907	if (0)
5908	{
5909	minPvs = mMinPvsSize;
5910	maxPvs = mMaxPvsSize;
5911	}
5912	else
5913	{
5914	// problem matt: why did I start here from zero?
5915	minPvs = 0;
5916	maxPvs = mMaxPvsSize;
5917	}
5918
5919	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5920	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5921
5922	SetValidity(minPvs, maxPvs);
5923
5924
5925	// area is not up to date, has to be recomputed
5926	mTotalAreaValid = false;
5927	VssRayContainer postProcessRays;
5928	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5929
5930	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5931
5932
5933	// compute tree by merging the nodes of the spatial hierarchy
5934	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5935	mViewCellsTree->SetRoot(root);
5936
5937	//////////////////////////
5938	//-- update pvs up to the root of the hierarchy
5939
5940	ObjectPvs pvs;
5941	UpdatePvsForEvaluation(root, pvs);
5942
5943
5944	//////////////////////
5945	//-- render simulation after merge + refine
5946
5947	cout << "\nview cells partition render time before compress" << endl << endl;
5948	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5949	SimulationStatistics ss;
5950	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5951	cout << ss << endl;
5952
5953
5954	mHierarchyManager->CreateUniqueObjectIds();
5955
5956	///////////
5957	//-- compression
5958
5959	if (0) CompressViewCells();
5960
5961	/////////////
5962	//-- some tasks still to do on the view cells:
5963	//-- Compute meshes from view cell geometry, evaluate volume and / or area
5964
5965	if (1) FinalizeViewCells(true);
5966
5967	return 0;
5968	}
5969
5970
5971	int VspOspViewCellsManager::GetType() const
5972	{
5973	return VSP_OSP;
5974	}
5975
5976
5977	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5978	{
5979	// terminate recursion
5980	if (root->IsLeaf())
5981	{
5982	VspLeaf leaf = static_cast<VspLeaf >(root);
5983	leaf->GetViewCell()->SetMergeCost(0.0f);
5984	return leaf->GetViewCell();
5985	}
5986
5987	VspInterior interior = static_cast<VspInterior >(root);
5988	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5989
5990	// evaluate merge cost for priority traversal
5991	const float mergeCost = -(float)root->mTimeStamp;
5992	viewCellInterior->SetMergeCost(mergeCost);
5993
5994	float volume = 0;
5995
5996	VspNode *front = interior->GetFront();
5997	VspNode *back = interior->GetBack();
5998
5999	ObjectPvs frontPvs, backPvs;
6000
6001	/////////
6002	//-- recursivly compute child hierarchies
6003
6004	ViewCell *backVc = ConstructSpatialMergeTree(back);
6005	ViewCell *frontVc = ConstructSpatialMergeTree(front);
6006
6007	viewCellInterior->SetupChildLink(backVc);
6008	viewCellInterior->SetupChildLink(frontVc);
6009
6010	volume += backVc->GetVolume();
6011	volume += frontVc->GetVolume();
6012
6013	viewCellInterior->SetVolume(volume);
6014
6015	return viewCellInterior;
6016	}
6017
6018
6019	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
6020	{
6021	if (!ViewCellsConstructed())
6022	return ViewCellsManager::GetViewPoint(viewPoint);
6023
6024	// TODO: set reasonable limit
6025	const int limit = 20;
6026
6027	for (int i = 0; i < limit; ++ i)
6028	{
6029	viewPoint = mViewSpaceBox.GetRandomPoint();
6030
6031	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
6032	{
6033	return true;
6034	}
6035	}
6036
6037	Debug << "failed to find valid view point, taking " << viewPoint << endl;
6038	return false;
6039	}
6040
6041
6042	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
6043	ViewCell *vc,
6044	const AxisAlignedBox3 *sceneBox,
6045	const AxisAlignedPlane *clipPlane
6046	) const
6047	{
6048	Plane3 plane;
6049	if (clipPlane)
6050	{
6051	// arbitrary plane definition
6052	plane = clipPlane->GetPlane();
6053	}
6054
6055	ViewCellContainer leaves;
6056	mViewCellsTree->CollectLeaves(vc, leaves);
6057
6058	ViewCellContainer::const_iterator it, it_end = leaves.end();
6059
6060	for (it = leaves.begin(); it != it_end; ++ it)
6061	{
6062	VspViewCell vspVc = static_cast<VspViewCell >(*it);
6063	VspLeaf *l = vspVc->mLeaves[0];
6064
6065	const AxisAlignedBox3 box =
6066	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
6067
6068	if (sceneBox && !Overlap(*sceneBox, box))
6069	continue;
6070
6071	if (clipPlane)
6072	{
6073	if (box.Side(plane) == -1)
6074	{
6075	exporter->ExportBox(box);
6076	}
6077	else if (box.Side(plane) == 0)
6078	{
6079	// intersection
6080	AxisAlignedBox3 fbox, bbox;
6081	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
6082	exporter->ExportBox(bbox);
6083	}
6084	}
6085	else
6086	{
6087	exporter->ExportBox(box);
6088	}
6089	}
6090	}
6091
6092
6093	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
6094	{
6095	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
6096	// validy update in preprocessor for all managers)
6097	return ViewCellsManager::ViewPointValid(viewPoint);
6098
6099	// return mViewSpaceBox.IsInside(viewPoint) &&
6100	// mVspTree->ViewPointValid(viewPoint);
6101	}
6102
6103
6104	float VspOspViewCellsManager::UpdateObjectCosts()
6105	{
6106	float maxRenderCost = 0;
6107
6108	cout << "updating object pvs cost ... ";
6109	const long startTime = GetTime();
6110
6111	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
6112
6113	Intersectable::NewMail();
6114
6115	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
6116
6117	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
6118	{
6119	ViewCell vc = vit;
6120
6121	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
6122
6123	// output PVS of view cell
6124	while (pit.HasMoreEntries())
6125	{
6126	Intersectable *obj = pit.Next();
6127
6128	BvhNode node = static_cast<BvhNode >(obj);
6129
6130	// hack!!
6131	if (!node->IsLeaf())
6132	{
6133	cout << "error, can only process leaves" << endl;
6134	return 0;
6135	}
6136
6137	if (!node->Mailed())
6138	{
6139	node->Mail();
6140	node->mRenderCost = 0;
6141	}
6142
6143	const float rc = (float)((BvhLeaf *)node)->mObjects.size();
6144
6145	node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
6146
6147	if (node->mRenderCost > maxRenderCost)
6148	maxRenderCost = node->mRenderCost;
6149	}
6150	}
6151
6152	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
6153
6154	return maxRenderCost;
6155	}
6156
6157
6158	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
6159	const VssRayContainer &sampleRays)
6160	{
6161	if (!ViewCellsConstructed())
6162	return;
6163
6164	VssRayContainer visRays;
6165	GetRaySets(sampleRays, mVisualizationSamples, visRays);
6166
6167	////////////
6168	//-- export final view cells
6169
6170	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
6171
6172	Vector3 scale(0.9f, 0.9f, 0.9f);
6173	//Vector3 scale(1.0f, 1.0f, 1.0f);
6174
6175	if (exporter)
6176	{
6177	// clamp to a scene boudning box
6178	if (CLAMP_TO_BOX)
6179	exporter->mClampToBox = true;
6180
6181	const long starttime = GetTime();
6182	cout << "exporting final view cells (after initial construction + post process) ... " << endl;
6183
6184	// matt: hack for clamping scene
6185	AxisAlignedBox3 bbox = mViewSpaceBox;
6186	bbox.Scale(scale);
6187
6188	if (1 && mExportRays)
6189	{
6190	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
6191	}
6192
6193	// hack color code
6194	const int savedColorCode = mColorCode;
6195
6196	EvaluateViewCellsStats();
6197	const int colorCode = 0;
6198
6199	const float maxRenderCost = -1;//UpdateObjectCosts();
6200	const bool exportBounds = false;
6201
6202	//cout << "maxRenderCost: " << maxRenderCost << endl;
6203	if (1)
6204	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
6205	objects,
6206	CLAMP_TO_BOX ? &bbox : NULL,
6207	maxRenderCost,
6208	exportBounds);
6209
6210	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6211	ExportViewCellsForViz(exporter, NULL, colorCode, GetClipPlane());
6212
6213	delete exporter;
6214
6215	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6216	}
6217
6218	if (1)
6219	{
6220	exporter = Exporter::GetExporter("final_object_partition.wrl");
6221
6222	if (exporter)
6223	{
6224	if (CLAMP_TO_BOX)
6225	{
6226	exporter->mClampToBox = true;
6227	}
6228
6229	const long starttime = GetTime();
6230	cout << "exporting final objects (after initial construction + post process) ... ";
6231
6232	// matt: hack for clamping scene
6233	AxisAlignedBox3 bbox = mViewSpaceBox;
6234	bbox.Scale(scale);
6235
6236	// hack color code (show pvs size)
6237	const int savedColorCode = mColorCode;
6238
6239	EvaluateViewCellsStats();
6240	mColorCode = 1; // 0 = random, 1 = export pvs
6241
6242	// don't visualize render cost
6243	const float maxRenderCost = -1;
6244	//const bool exportBounds = true;
6245	const bool exportBounds = false;
6246
6247	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
6248	objects,
6249	CLAMP_TO_BOX ? &bbox : NULL,
6250	maxRenderCost,
6251	exportBounds);
6252
6253
6254	delete exporter;
6255
6256	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6257	mColorCode = savedColorCode;
6258	}
6259	}
6260
6261	// export some view cells
6262	int leafOut;
6263	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
6264
6265	const bool sortViewCells = false;
6266	const bool exportPvs = true;
6267	const bool exportRays = true;
6268	const int raysOut = 100;
6269
6270	ExportSingleViewCells(objects,
6271	leafOut,
6272	sortViewCells,
6273	exportPvs,
6274	exportRays,
6275	raysOut,
6276	"");
6277	}
6278
6279
6280	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
6281	const int maxViewCells,
6282	const bool sortViewCells,
6283	const bool exportPvs,
6284	const bool exportRays,
6285	const int maxRays,
6286	const string &prefix,
6287	VssRayContainer *visRays)
6288	{
6289	if (sortViewCells)
6290	{
6291	// sort view cells to visualize the view cells with highest render cost
6292	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
6293	}
6294
6295	ViewCell::NewMail();
6296	const int limit = min(maxViewCells, (int)mViewCells.size());
6297
6298	cout << "\nExporting " << limit << " single view cells: " << endl;
6299
6300	for (int i = 0; i < limit; ++ i)
6301	{
6302	cout << "creating output for view cell " << i << " ... ";
6303
6304	// largest view cell pvs first of random view cell
6305	ViewCell *vc = sortViewCells ?
6306	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
6307
6308	if (vc->Mailed()) // view cell already processed
6309	continue;
6310
6311	vc->Mail();
6312
6313	ObjectPvs pvs;
6314	mViewCellsTree->GetPvs(vc, pvs);
6315
6316	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
6317	Exporter *exporter = Exporter::GetExporter(s);
6318
6319	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetTrianglesInPvs(vc) << endl;
6320
6321	if (exportPvs)
6322	{
6323	Material m;
6324	Intersectable::NewMail();
6325
6326	ObjectPvsIterator pit = pvs.GetIterator();
6327
6328	// output PVS of view cell
6329	while (pit.HasMoreEntries())
6330	{
6331	Intersectable *intersect = pit.Next();
6332
6333	if (!intersect->Mailed())
6334	{
6335	m = RandomMaterial();
6336	exporter->SetForcedMaterial(m);
6337
6338	exporter->ExportIntersectable(intersect);
6339	intersect->Mail();
6340	}
6341	}
6342	}
6343
6344	if (exportRays)
6345	{
6346	////////////
6347	//-- export the sample rays
6348
6349	// output rays stored with the view cells during subdivision
6350	VssRayContainer vcRays;
6351	VssRayContainer collectRays;
6352
6353	// collect intial view cells
6354	ViewCellContainer leaves;
6355	mViewCellsTree->CollectLeaves(vc, leaves);
6356
6357	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
6358
6359	for (vit = leaves.begin(); vit != vit_end; ++ vit)
6360	{
6361	VspLeaf vcLeaf = static_cast<VspViewCell >(*vit)->mLeaves[0];
6362	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
6363
6364	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
6365	{
6366	collectRays.push_back(*rit);
6367	}
6368	}
6369
6370	const int raysOut = min((int)collectRays.size(), maxRays);
6371
6372	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
6373
6374	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
6375	{
6376	const float p = RandomValue(0.0f, (float)collectRays.size());
6377
6378	if (p < raysOut)
6379	vcRays.push_back(*rit);
6380	}
6381
6382	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
6383	}
6384
6385
6386	/////////////////
6387	//-- export view cell geometry
6388
6389	exporter->SetWireframe();
6390
6391	Material m;
6392	m.mDiffuseColor = RgbColor(0, 1, 0);
6393	exporter->SetForcedMaterial(m);
6394
6395	ExportViewCellGeometry(exporter, vc, NULL, NULL);
6396	exporter->SetFilled();
6397
6398	DEL_PTR(exporter);
6399	cout << "finished" << endl;
6400	}
6401
6402	cout << endl;
6403	}
6404
6405
6406	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
6407	ViewCellContainer &viewCells) const
6408	{
6409	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
6410	}
6411
6412
6413	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
6414	const Vector3 &termination,
6415	ViewCellContainer &viewcells)
6416	{
6417	return mHierarchyManager->CastLineSegment(origin, termination, viewcells);
6418	}
6419
6420
6421	bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
6422	const Vector3 &termination,
6423	ViewCell *viewCell)
6424	{
6425	return false;
6426	}
6427
6428
6429	bool VspOspViewCellsManager::ExportViewCells(const string filename,
6430	const bool exportPvs,
6431	const ObjectContainer &objects)
6432	{
6433	// no view cells were computed
6434	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6435	return false;
6436
6437	if (strstr(filename.c_str(), ".bn"))
6438	{
6439	return ExportViewCellsBinary(filename, exportPvs, objects);
6440	}
6441
6442	//cout << "exporting binary" << endl; string fname("test.vc"); return ExportViewCellsBinary(fname, exportPvs, objects);
6443
6444	const long starttime = GetTime();
6445	cout << "exporting view cells to xml ... ";
6446
6447	OUT_STREAM stream(filename.c_str());
6448
6449	// we need unique ids for each view cell
6450	CreateUniqueViewCellIds();
6451
6452	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6453	stream << "<VisibilitySolution>" << endl;
6454
6455	if (exportPvs)
6456	{
6457	///////////////
6458	//-- export bounding boxes
6459	//-- we need the boxes to identify objects in the target engine
6460
6461	if (mUseKdPvs)
6462	{
6463	stream << "<BoundingBoxes>" << endl;
6464
6465	int id = 0;
6466	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
6467
6468	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
6469	{
6470	Intersectable obj = (kit);
6471	const AxisAlignedBox3 box = obj->GetBox();
6472
6473	// set kd node id
6474	obj->SetId(id);
6475
6476	stream << "<BoundingBox" << " id=\"" << id << "\""
6477	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
6478	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
6479	}
6480
6481	stream << "</BoundingBoxes>" << endl;
6482	}
6483	else
6484	{
6485	mHierarchyManager->ExportBoundingBoxes(stream, objects);
6486	}
6487	}
6488
6489
6490	//////////////////////////
6491	//-- export the view cells and the pvs
6492
6493	const int numViewCells = mCurrentViewCellsStats.viewCells;
6494
6495	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6496	mViewCellsTree->Export(stream, exportPvs);
6497	stream << "</ViewCells>" << endl;
6498
6499
6500	/////////////////
6501	//-- export the view space hierarchy
6502
6503	stream << "<ViewSpaceHierarchy type=\"vsp\""
6504	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6505	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6506
6507	mHierarchyManager->GetVspTree()->Export(stream);
6508	stream << "</ViewSpaceHierarchy>" << endl;
6509
6510	/////////////////
6511	//-- export the object space hierarchy
6512
6513	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6514
6515	stream << "</VisibilitySolution>" << endl;
6516	stream.close();
6517
6518	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6519	return true;
6520	}
6521
6522
6523	bool VspOspViewCellsManager::ExportViewCellsBinary(const string filename,
6524	const bool exportPvs,
6525	const ObjectContainer &objects)
6526	{
6527	// no view cells constructed yet
6528	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6529	return false;
6530
6531	const long starttime = GetTime();
6532	cout << "exporting view cells to binary format ... ";
6533
6534	OUT_STREAM stream(filename.c_str());
6535
6536	// we need unique ids for each view cell
6537	CreateUniqueViewCellIds();
6538
6539	int numBoxes = mPreprocessor->mKdTree->mKdIntersectables.size();
6540	stream.write(reinterpret_cast<char *>(&numBoxes), sizeof(int));
6541
6542
6543	///////////////
6544	//-- export bounding boxes
6545
6546	// we use bounding box intersection to identify pvs objects in the target engine
6547	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
6548
6549	int id = 0;
6550
6551	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
6552	{
6553	Intersectable obj = (kit);
6554	// set the kd node id to identify the kd node as a pvs entry
6555	obj->SetId(id);
6556
6557	const AxisAlignedBox3 &box = obj->GetBox();
6558	Vector3 bmin = box.Min();
6559	Vector3 bmax = box.Max();
6560
6561	stream.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
6562	stream.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
6563	stream.write(reinterpret_cast<char *>(&id), sizeof(int));
6564	}
6565
6566	cout << "written " << numBoxes << " kd nodes" << endl;
6567
6568	///////////////
6569	//-- export the view cells and the pvs
6570
6571	int numViewCells = mViewCells.size();
6572	stream.write(reinterpret_cast<char *>(&numViewCells), sizeof(int));
6573
6574	Vector3 vmin = mViewSpaceBox.Min();
6575	Vector3 vmax = mViewSpaceBox.Max();
6576
6577	stream.write(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
6578	stream.write(reinterpret_cast<char *>(&vmax), sizeof(Vector3));
6579
6580
6581	//////////
6582	//-- export binary view cells
6583
6584	mViewCellsTree->ExportBinary(stream);
6585
6586
6587	/////////
6588	//-- export the view space hierarchy
6589
6590	mHierarchyManager->GetVspTree()->ExportBinary(stream);
6591
6592
6593	////////
6594	//-- export the object space hierarchy
6595
6596	//mHierarchyManager->ExportObjectSpaceHierarchyBinary();
6597
6598	stream.close();
6599
6600	//mHierarchyManager->GetVspTree()->TestOutput("output.txt");
6601
6602	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6603	return true;
6604	}
6605
6606
6607	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6608	const bool active) const
6609	{
6610	if (!ViewCellsConstructed())
6611	return NULL;
6612
6613	if (!mViewSpaceBox.IsInside(point))
6614	return NULL;
6615
6616	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6617	}
6618
6619
6620	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6621	{
6622	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6623
6624	ViewCellContainer leaves;
6625	mViewCellsTree->CollectLeaves(vc, leaves);
6626
6627	ViewCellContainer::const_iterator it, it_end = leaves.end();
6628
6629	for (it = leaves.begin(); it != it_end; ++ it)
6630	{
6631	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6632	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6633	IncludeBoxInMesh(box, *mesh);
6634	}
6635
6636	mesh->ComputeBoundingBox();
6637
6638	vc->SetMesh(mesh);
6639	}
6640
6641
6642	int VspOspViewCellsManager::CastBeam(Beam &beam)
6643	{
6644	// matt: TODO
6645	return 0;
6646	}
6647
6648
6649	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6650	{
6651	float area = 0;
6652	float volume = 0;
6653
6654	ViewCellContainer leaves;
6655	mViewCellsTree->CollectLeaves(viewCell, leaves);
6656
6657	ViewCellContainer::const_iterator it, it_end = leaves.end();
6658
6659	for (it = leaves.begin(); it != it_end; ++ it)
6660	{
6661	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6662
6663	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6664
6665	const float lVol = box.GetVolume();
6666	const float lArea = box.SurfaceArea();
6667
6668	area += lArea;
6669	volume += lVol;
6670
6671	CreateMesh(*it);
6672	}
6673
6674	viewCell->SetVolume(volume);
6675	viewCell->SetArea(area);
6676	}
6677
6678
6679	void VspOspViewCellsManager::PrepareLoadedViewCells()
6680	{
6681	// TODO
6682	}
6683
6684
6685	void VspOspViewCellsManager::PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6686	{
6687	const float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6688
6689	float fullmem = mem +
6690	(hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6691	hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6692
6693	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6694	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6695	}
6696
6697
6698	void VspOspViewCellsManager::CompressViewCells()
6699	{
6700	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6701	return;
6702
6703
6704	////////////
6705	//-- compression
6706
6707	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6708
6709	cout << "before compression: " << endl;
6710	Debug << "before compression: " << endl;
6711
6712	PrintCompressionStats(mHierarchyManager, pvsEntries);
6713
6714	if (mCompressObjects)
6715	{
6716	cout << "compressing in the objects: " << endl;
6717	Debug << "compressing in the objects: " << endl;
6718
6719	pvsEntries = mHierarchyManager->CompressObjectSpace();
6720	}
6721	else
6722	{
6723	cout << "compressing in the view space: " << endl;
6724	Debug << "compressing in the view space: " << endl;
6725
6726	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6727	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6728	}
6729
6730	PrintCompressionStats(mHierarchyManager, pvsEntries);
6731	}
6732
6733
6734	void VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box,
6735	ObjectContainer &objects)
6736	{
6737	mHierarchyManager->CollectObjects(box, objects);
6738	}
6739
6740
6741	void VspOspViewCellsManager::EvalViewCellPartition()
6742	{
6743	int samplesPerPass;
6744	int castSamples = 0;
6745	int oldSamples = 0;
6746	int samplesForStats;
6747	char statsPrefix[100];
6748	char suffix[100];
6749	int splitsStepSize;
6750
6751	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6752	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6753	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", mEvaluationSamples);
6754	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6755	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6756
6757	bool useHisto;
6758	int histoMem;
6759
6760	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6761	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6762
6763	Debug << "step size: " << splitsStepSize << endl;
6764	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6765	Debug << "view cell evaluation samples: " << mEvaluationSamples << endl;
6766	Debug << "view cell stats prefix: " << statsPrefix << endl;
6767
6768	cout << "reseting pvs ... ";
6769
6770	// reset pvs and start over from zero
6771	mViewCellsTree->ResetPvs();
6772
6773	cout << "finished" << endl;
6774	cout << "Evaluating view cell partition ... " << endl;
6775
6776	int pass = 0;
6777
6778	while (castSamples < mEvaluationSamples)
6779	{
6780	///////////////
6781	//-- we have to use uniform sampling strategy for construction rays
6782
6783	VssRayContainer evaluationSamples;
6784	const int samplingType = mEvaluationSamplingType;
6785
6786	long startTime = GetTime();
6787	Real timeDiff;
6788
6789	cout << "casting " << samplesPerPass << " samples ... ";
6790	Debug << "casting " << samplesPerPass << " samples ... ";
6791
6792	// use mixed distributions
6793	CastEvaluationSamples(samplesPerPass, evaluationSamples);
6794
6795	timeDiff = TimeDiff(startTime, GetTime());
6796	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6797	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6798
6799	// don't computed sample contributions
6800	// because already accounted for inside the mixture distribution!
6801
6802	castSamples += samplesPerPass;
6803
6804	if ((castSamples >= samplesForStats + oldSamples) \|\|
6805	(castSamples >= mEvaluationSamples))
6806	{
6807	oldSamples += samplesForStats;
6808
6809	///////////
6810	//-- output stats
6811
6812	sprintf(suffix, "-%09d-eval.log", castSamples);
6813	const string filename = string(statsPrefix) + string(suffix);
6814
6815	startTime = GetTime();
6816
6817	cout << "compute new statistics ... " << endl;
6818
6819	ofstream ofstr(filename.c_str());
6820	mHierarchyManager->EvaluateSubdivision(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6821
6822	timeDiff = TimeDiff(startTime, GetTime());
6823	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6824	cout << "*************************************" << endl;
6825
6826	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6827
6828	++ pass;
6829	}
6830
6831	disposeRays(evaluationSamples, NULL);
6832	}
6833
6834	////////////
6835	//-- histogram
6836
6837	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
6838	int histoStepSize;
6839
6840	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6841	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
6842
6843	if (useHisto)
6844	{
6845	// evaluate view cells in a histogram
6846	char str[64];
6847
6848	// hack: just show final view cells
6849	const int pass = (int)mViewCells.size();
6850
6851	//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
6852
6853	string filename;
6854
6855	cout << "computing histogram for " << pass << " view cells" << endl;
6856
6857	///////////////////
6858	//-- evaluate histogram for pvs size
6859
6860	cout << "computing pvs histogram for " << pass << " view cells" << endl;
6861
6862	sprintf(str, "-%09d-histo-pvs2.log", pass);
6863	filename = string(statsPrefix) + string(str);
6864
6865	EvalViewCellHistogramForPvsSize(filename, pass);
6866	}
6867	}
6868
6869
6870	void VspOspViewCellsManager::FinalizeViewCells(const bool createMesh)
6871	{
6872	ViewCellsManager::FinalizeViewCells(createMesh);
6873
6874	if (mHierarchyManager->mUseTraversalTree)
6875	{ // create a traversal tree for optimal view cell casting
6876	mHierarchyManager->CreateTraversalTree();
6877	}
6878	}
6879
6880
6881	#if TEST_PACKETS
6882
6883	float VspOspViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
6884	const bool addContributions,
6885	const bool storeViewCells,
6886	const bool useHitObjects)
6887	{
6888	if (!ViewCellsConstructed())
6889	return 0;
6890
6891	float sum = 0.0f;
6892	VssRayContainer::const_iterator it, it_end = rays.end();
6893
6894	VssRayContainer tmpRays;
6895
6896	for (it = rays.begin(); it != it_end; ++ it)
6897	{
6898	sum += ComputeSampleContribution((it), addContributions, storeViewCells, useHitObjects);
6899
6900	tmpRays.push_back(new VssRay((it)));
6901
6902	if (tmpRays.size() == 4)
6903	{
6904	// cast packets of 4 rays
6905	RayPacket packet(tmpRays);
6906	mHierarchyManager->CastLineSegment(packet);
6907
6908	for (int i = 0; i < 4; ++ i)
6909	{
6910	ComputeSampleContribution(*tmpRays[i], addContributions, true, useHitObjects);
6911	// compare results
6912	cout << "ray " << i << ": " << (int)tmpRays[i]->mViewCells.size() << " "
6913	<< (int)packet.mViewCells[i].size() << endl;
6914	}
6915
6916	CLEAR_CONTAINER(tmpRays);
6917	}
6918	}
6919
6920	CLEAR_CONTAINER(tmpRays);
6921
6922	#ifdef USE_PERFTIMER
6923	cout << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
6924	Debug << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
6925	cout << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
6926	Debug << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
6927	#endif
6928
6929	return sum;
6930	}
6931
6932	#endif
6933
6934
6935	ViewCellsManager *
6936	ViewCellsManager::LoadViewCellsBinary(const string &filename,
6937	ObjectContainer &pvsObjects,
6938	bool finalizeViewCells,
6939	BoundingBoxConverter *bconverter)
6940	{
6941	IN_STREAM stream(filename.c_str());
6942
6943	if (!stream.is_open())
6944	{
6945	Debug << "View cells loading failed: could not open file" << endl;
6946	return NULL;
6947	}
6948
6949	Debug << "loading boxes" << endl;
6950
6951	const long startTime = GetTime();
6952
6953	// load all the bounding boxes
6954	IndexedBoundingBoxContainer iboxes;
6955	ViewCellsManager::LoadIndexedBoundingBoxesBinary(stream, iboxes);
6956
6957	pvsObjects.reserve(iboxes.size());
6958
6959	if (bconverter)
6960	{
6961	// associate object ids with bounding boxes
6962	bconverter->IdentifyObjects(iboxes, pvsObjects);
6963	}
6964
6965
6966	ObjectContainer pvsLookup;
6967	pvsLookup.resize(iboxes.size());
6968
6969	for (size_t i = 0; i < pvsLookup.size(); ++ i)
6970	{
6971	pvsLookup[i] = NULL;
6972	}
6973
6974	for (size_t i = 0; i < pvsObjects.size(); ++ i)
6975	{
6976	pvsLookup[pvsObjects[i]->GetId()] = pvsObjects[i];
6977	}
6978
6979
6980	/////////////
6981	//-- load the view cells
6982
6983	int numViewCells;
6984	stream.read(reinterpret_cast<char *>(&numViewCells), sizeof(int));
6985
6986	Debug << "loading " << numViewCells << " view cells " << endl;
6987
6988	Vector3 vmin, vmax;
6989
6990	stream.read(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
6991	stream.read(reinterpret_cast<char *>(&vmax), sizeof(Vector3));
6992
6993	AxisAlignedBox3 viewSpaceBox(vmin, vmax);
6994
6995	Debug << "view space box: " << viewSpaceBox << endl;
6996
6997	ViewCellsTree *vcTree = new ViewCellsTree();
6998
6999	if (!vcTree->ImportBinary(stream, pvsLookup))
7000	{
7001	Debug << "Error: loading view cells tree failed!" << endl;
7002	delete vcTree;
7003
7004	return NULL;
7005	}
7006
7007	Debug << "loading the view space partition tree" << endl;
7008	VspTree *vspTree = new VspTree(viewSpaceBox);
7009
7010	if (!vspTree->ImportBinary(stream))
7011	{
7012	Debug << "Error: loading vsp tree failed!" << endl;
7013	delete vcTree; delete vspTree;
7014
7015	return NULL;
7016	}
7017
7018
7019	HierarchyManager * hm =
7020	new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
7021
7022	hm->SetVspTree(vspTree);
7023
7024
7025	/////////
7026	//-- create view cells manager
7027
7028	VspOspViewCellsManager *vm = new VspOspViewCellsManager(vcTree, hm);
7029
7030
7031	//////////////
7032	//-- do some more preparation
7033
7034	vm->mViewSpaceBox = viewSpaceBox;
7035	vm->mViewCells.clear();
7036
7037	ViewCellContainer viewCells;
7038	vcTree->CollectLeaves(vcTree->GetRoot(), viewCells);
7039
7040	ViewCellContainer::const_iterator cit, cit_end = viewCells.end();
7041
7042	for (cit = viewCells.begin(); cit != cit_end; ++ cit)
7043	{
7044	vm->mViewCells.push_back(*cit);
7045	}
7046
7047
7048	//////////////
7049	//-- associate view cells with vsp leaves
7050
7051	vector<VspLeaf *> vspLeaves;
7052	vspTree->CollectLeaves(vspLeaves);
7053
7054	vector<VspLeaf *>::const_iterator vit, vit_end = vspLeaves.end();
7055	cit = viewCells.begin();
7056
7057	for (vit = vspLeaves.begin(); vit != vit_end; ++ vit, ++ cit)
7058	{
7059	VspLeaf leaf = vit;
7060	VspViewCell vc = static_cast<VspViewCell >(*cit);
7061
7062	leaf->SetViewCell(vc);
7063	vc->mLeaves.push_back(leaf);
7064	}
7065
7066
7067	/*for (cit = viewCells.begin(); cit != cit_end; ++ cit)
7068	{
7069	Debug << "pvssize: " << (*cit)->GetPvs().GetSize();
7070	}*/
7071
7072
7073	vm->mViewCellsFinished = true;
7074	vm->mMaxPvsSize = (int)pvsObjects.size();
7075
7076	if (finalizeViewCells)
7077	{
7078	// create the meshes and compute view cell volumes
7079	const bool createMeshes = true;
7080	vm->FinalizeViewCells(createMeshes);
7081	}
7082
7083	Debug << (int)vm->mViewCells.size() << " view cells loaded in "
7084	<< TimeDiff(startTime, GetTime()) * 1e-6f << " secs" << endl;
7085
7086	//vspTree->TestOutput("input.txt");
7087
7088	return vm;
7089	}
7090
7091
7092	ViewCellPointsList *ViewCellsManager::GetViewCellPointsList()
7093	{
7094	return mRandomViewCellsHandler->GetViewCellPointsList();
7095	}
7096
7097
7098	bool ViewCellsManager::ExportRandomViewCells(const string &filename)
7099	{
7100	// export ten view cells with 100 random view points inside each
7101	const int numViewCells = 100;
7102	const int numViewPoints = 10;
7103
7104	//cout << "exporting random view cells" << endl;
7105	return mRandomViewCellsHandler->ExportRandomViewCells(filename);
7106	}
7107
7108
7109	bool ViewCellsManager::ImportViewCellsList(const string &filename)
7110	{
7111	return mRandomViewCellsHandler->ImportViewCellsList(filename);
7112	}
7113
7114
7115	}

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

Download in other formats: