Context Navigation

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

Revision 1877, 153.6 KB checked in by bittner, 18 years ago (diff)
sampling updates

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

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

Download in other formats: