Context Navigation

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

Revision 1902, 155.7 KB checked in by mattausch, 18 years ago (diff)
added kd pvs as option to view cells manager to avoid errors when updating the svn from jiri

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

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

Download in other formats: