Context Navigation

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

Revision 1778, 154.2 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: