Context Navigation

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

Revision 1883, 153.6 KB checked in by bittner, 18 years ago (diff)
mixture distribution initial coding

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

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

Download in other formats: