Context Navigation

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

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

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

Download in other formats: