Context Navigation

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

Revision 2619, 180.2 KB checked in by bittner, 16 years ago (diff)
TEST PVS RENDERING ON

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

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

Download in other formats: