Context Navigation

ViewCellsManager.cpp @ 2729

Revision 2729, 180.6 KB checked in by mattausch, 16 years ago (diff)
worked on gvs

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

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

Context Navigation

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

Download in other formats: