Context Navigation

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

Revision 1811, 159.6 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 0
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	int ViewCellsManager::GetMinPvsSize() const
1960	{
1961	return mMinPvsSize;
1962	}
1963
1964
1965
1966	float ViewCellsManager::GetMaxPvsRatio() const
1967	{
1968	return mMaxPvsRatio;
1969	}
1970
1971
1972	float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
1973	const bool addRays,
1974	const bool storeViewCells)
1975	{
1976	ViewCellContainer viewcells;
1977
1978	ray.mPvsContribution = 0;
1979	ray.mRelativePvsContribution = 0.0f;
1980
1981	static Ray hray;
1982	hray.Init(ray);
1983	//hray.mFlags \|= Ray::CULL_BACKFACES;
1984	//Ray hray(ray);
1985
1986	float tmin = 0, tmax = 1.0;
1987
1988	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
1989	return 0;
1990
1991	Vector3 origin = hray.Extrap(tmin);
1992	Vector3 termination = hray.Extrap(tmax);
1993
1994	ViewCell::NewMail();
1995
1996	// if (ray.mPdf!=1.0f)
1997	// cout<<ray.mPdf<<" ";
1998
1999
2000	// traverse the view space subdivision
2001	CastLineSegment(origin, termination, viewcells);
2002
2003	if (storeViewCells)
2004	{ // copy viewcells memory efficiently
2005	ray.mViewCells.reserve(viewcells.size());
2006	ray.mViewCells = viewcells;
2007	}
2008
2009	Intersectable *obj = GetIntersectable(ray, true);
2010
2011	ViewCellContainer::const_iterator it = viewcells.begin();
2012
2013	for (; it != viewcells.end(); ++ it)
2014	{
2015	ViewCell viewcell = it;
2016	// tests if view cell is in valid view space
2017	if (viewcell->GetValid())
2018	{
2019	float contribution;
2020
2021	if (ray.mTerminationObject)
2022	{
2023	if (viewcell->GetPvs().GetSampleContribution(obj,
2024	ray.mPdf,
2025	contribution))
2026	{
2027	++ ray.mPvsContribution;
2028	ray.mRelativePvsContribution += contribution;
2029	}
2030	}
2031
2032	#if SAMPLE_ORIGIN_OBJECTS
2033
2034	// for directional sampling it is important to count only contributions
2035	// made in one direction!!!
2036	// the other contributions of this sample will be counted for the oposite ray!
2037
2038	if (ray.mOriginObject &&
2039	viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
2040	ray.mPdf,
2041	contribution))
2042	{
2043	++ ray.mPvsContribution;
2044	ray.mRelativePvsContribution += contribution;
2045	}
2046	#endif
2047	}
2048	}
2049
2050	// if true, the sampled entities are stored in the pvs
2051	if (addRays)
2052	{
2053	for (it = viewcells.begin(); it != viewcells.end(); ++ it)
2054	{
2055	ViewCell viewcell = it;
2056
2057	if (viewcell->GetValid())
2058	{
2059	// if view point is valid, add new object to the pvs
2060	if (ray.mTerminationObject)
2061	{
2062	viewcell->GetPvs().AddSample(obj, ray.mPdf);
2063	}
2064	#if SAMPLE_ORIGIN_OBJECTS
2065	if (ray.mOriginObject)
2066	{
2067	viewcell->GetPvs().AddSample(ray.mOriginObject, ray.mPdf);
2068	}
2069	#endif
2070	}
2071	}
2072	}
2073
2074	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2075	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2076	}
2077
2078
2079	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
2080	const int maxSize,
2081	VssRayContainer &usedRays,
2082	VssRayContainer *savedRays) const
2083	{
2084	const int limit = min(maxSize, (int)sourceRays.size());
2085	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
2086
2087	VssRayContainer::const_iterator it, it_end = sourceRays.end();
2088	for (it = sourceRays.begin(); it != it_end; ++ it)
2089	{
2090	if (Random(1.0f) < prop)
2091	usedRays.push_back(*it);
2092	else if (savedRays)
2093	savedRays->push_back(*it);
2094	}
2095	}
2096
2097
2098	float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
2099	{
2100	return (float)mViewCellsTree->GetPvsCost(viewCell);
2101	}
2102
2103
2104	float ViewCellsManager::GetAccVcArea()
2105	{
2106	// if already computed
2107	if (mTotalAreaValid)
2108	{
2109	return mTotalArea;
2110	}
2111
2112	mTotalArea = 0;
2113	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2114
2115	for (it = mViewCells.begin(); it != it_end; ++ it)
2116	{
2117	//Debug << "area: " << GetArea(*it);
2118	mTotalArea += GetArea(*it);
2119	}
2120
2121	mTotalAreaValid = true;
2122
2123	return mTotalArea;
2124	}
2125
2126
2127	void ViewCellsManager::PrintStatistics(ostream &s) const
2128	{
2129	s << mCurrentViewCellsStats << endl;
2130	}
2131
2132
2133	void ViewCellsManager::CreateUniqueViewCellIds()
2134	{
2135	if (ViewCellsTreeConstructed())
2136	{
2137	mViewCellsTree->CreateUniqueViewCellsIds();
2138	}
2139	else // no view cells tree, handle view cells "myself"
2140	{
2141	int i = 0;
2142	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2143	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2144	{
2145	if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2146	{
2147	mViewCells[i]->SetId(i ++);
2148	}
2149	}
2150	}
2151	}
2152
2153
2154	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2155	const AxisAlignedBox3 *sceneBox,
2156	const bool colorCode,
2157	const AxisAlignedPlane *clipPlane
2158	) const
2159	{
2160	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2161
2162	for (it = mViewCells.begin(); it != it_end; ++ it)
2163	{
2164	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
2165	{
2166	ExportColor(exporter, *it, colorCode);
2167	ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2168	}
2169	}
2170	}
2171
2172
2173	void ViewCellsManager::CreateViewCellMeshes()
2174	{
2175	// convert to meshes
2176	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2177
2178	for (it = mViewCells.begin(); it != it_end; ++ it)
2179	{
2180	if (!(*it)->GetMesh())
2181	{
2182	CreateMesh(*it);
2183	}
2184	}
2185	}
2186
2187
2188	bool ViewCellsManager::ExportViewCells(const string filename,
2189	const bool exportPvs,
2190	const ObjectContainer &objects)
2191	{
2192	return false;
2193	}
2194
2195
2196	void ViewCellsManager::CollectViewCells(const int n)
2197	{
2198	mNumActiveViewCells = n;
2199	mViewCells.clear();
2200	// implemented in subclasses
2201	CollectViewCells();
2202	}
2203
2204
2205	void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
2206	{
2207	ViewCellContainer leaves;
2208	// sets the pointers to the currently active view cells
2209	mViewCellsTree->CollectLeaves(vc, leaves);
2210
2211	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2212	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2213	{
2214	dynamic_cast<ViewCellLeaf >(lit)->SetActiveViewCell(vc);
2215	}
2216	}
2217
2218
2219	void ViewCellsManager::SetViewCellsActive()
2220	{
2221	// collect leaf view cells and set the pointers to
2222	// the currently active view cells
2223	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2224
2225	for (it = mViewCells.begin(); it != it_end; ++ it)
2226	{
2227	SetViewCellActive(*it);
2228	}
2229	}
2230
2231
2232	int ViewCellsManager::GetMaxFilterSize() const
2233	{
2234	return mMaxFilterSize;
2235	}
2236
2237
2238	static const bool USE_ASCII = true;
2239
2240
2241	bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2242	const ObjectContainer &objects) const
2243	{
2244	ObjectContainer::const_iterator it, it_end = objects.end();
2245
2246	if (USE_ASCII)
2247	{
2248	ofstream boxesOut(filename.c_str());
2249	if (!boxesOut.is_open())
2250	return false;
2251
2252	for (it = objects.begin(); it != it_end; ++ it)
2253	{
2254	MeshInstance mi = dynamic_cast<MeshInstance >(*it);
2255	const AxisAlignedBox3 box = mi->GetBox();
2256
2257	boxesOut << mi->GetId() << " "
2258	<< box.Min().x << " "
2259	<< box.Min().y << " "
2260	<< box.Min().z << " "
2261	<< box.Max().x << " "
2262	<< box.Max().y << " "
2263	<< box.Max().z << endl;
2264	}
2265
2266	boxesOut.close();
2267	}
2268	else
2269	{
2270	ofstream boxesOut(filename.c_str(), ios::binary);
2271
2272	if (!boxesOut.is_open())
2273	return false;
2274
2275	for (it = objects.begin(); it != it_end; ++ it)
2276	{
2277	MeshInstance mi = dynamic_cast<MeshInstance >(*it);
2278	const AxisAlignedBox3 box = mi->GetBox();
2279	Vector3 bmin = box.Min();
2280	Vector3 bmax = box.Max();
2281	int id = mi->GetId();
2282
2283	boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2284	boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2285	boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2286	}
2287
2288	boxesOut.close();
2289	}
2290
2291	return true;
2292	}
2293
2294
2295	bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2296	IndexedBoundingBoxContainer &boxes) const
2297	{
2298	Vector3 bmin, bmax;
2299	int id;
2300
2301	if (USE_ASCII)
2302	{
2303	ifstream boxesIn(filename.c_str());
2304
2305	if (!boxesIn.is_open())
2306	{
2307	cout << "failed to open file " << filename << endl;
2308	return false;
2309	}
2310
2311	string buf;
2312	while (!(getline(boxesIn, buf)).eof())
2313	{
2314	sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2315	&id, &bmin.x, &bmin.y, &bmin.z,
2316	&bmax.x, &bmax.y, &bmax.z);
2317
2318	AxisAlignedBox3 box(bmin, bmax);
2319	// MeshInstance *mi = new MeshInstance();
2320	// HACK: set bounding box to new box
2321	//mi->mBox = box;
2322
2323	boxes.push_back(IndexedBoundingBox(id, box));
2324	}
2325
2326	boxesIn.close();
2327	}
2328	else
2329	{
2330	ifstream boxesIn(filename.c_str(), ios::binary);
2331
2332	if (!boxesIn.is_open())
2333	return false;
2334
2335	while (1)
2336	{
2337	boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2338	boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2339	boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2340
2341	if (boxesIn.eof())
2342	break;
2343
2344
2345	AxisAlignedBox3 box(bmin, bmax);
2346	MeshInstance *mi = new MeshInstance(NULL);
2347
2348	// HACK: set bounding box to new box
2349	//mi->mBox = box;
2350	//boxes.push_back(mi);
2351	boxes.push_back(IndexedBoundingBox(id, box));
2352	}
2353
2354	boxesIn.close();
2355	}
2356
2357	return true;
2358	}
2359
2360
2361	float ViewCellsManager::GetFilterWidth()
2362	{
2363	return mFilterWidth;
2364	}
2365
2366
2367	float ViewCellsManager::GetAbsFilterWidth()
2368	{
2369	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2370	}
2371
2372
2373	void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2374	const float pvsCost,
2375	const int entriesInPvs) const
2376	{
2377	vc->mPvsCost = pvsCost;
2378	vc->mEntriesInPvs = entriesInPvs;
2379
2380	vc->mPvsSizeValid = true;
2381	}
2382
2383
2384	void
2385	ViewCellsManager::ApplyFilter(ViewCell *viewCell,
2386	KdTree *kdTree,
2387	const float viewSpaceFilterSize,
2388	const float spatialFilterSize,
2389	ObjectPvs &pvs
2390	)
2391	{
2392	// extend the pvs of the viewcell by pvs of its neighbors
2393	// and apply spatial filter by including all neighbors of the objects
2394	// in the pvs
2395
2396	// get all viewcells intersecting the viewSpaceFilterBox
2397	// and compute the pvs union
2398
2399	//Vector3 center = viewCell->GetBox().Center();
2400	// Vector3 center = m->mBox.Center();
2401
2402	// AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
2403	// center + Vector3(viewSpaceFilterSize/2));
2404	if (!ViewCellsConstructed())
2405	return;
2406
2407	if (viewSpaceFilterSize >= 0.0f) {
2408
2409	const bool usePrVS = false;
2410
2411	if (!usePrVS) {
2412	AxisAlignedBox3 box = GetViewCellBox(viewCell);
2413	box.Enlarge(Vector3(viewSpaceFilterSize/2));
2414
2415	ViewCellContainer viewCells;
2416	ComputeBoxIntersections(box, viewCells);
2417
2418	// cout<<"box="<<box<<endl;
2419	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
2420
2421	for (; it != it_end; ++ it)
2422	{
2423	ObjectPvs interPvs;
2424	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
2425	ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
2426
2427	pvs = interPvs;
2428	}
2429	} else
2430	{
2431	PrVs prvs;
2432	AxisAlignedBox3 box = GetViewCellBox(viewCell);
2433
2434	// mViewCellsManager->SetMaxFilterSize(1);
2435	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
2436	pvs = prvs.mViewCell->GetPvs();
2437	DeleteLocalMergeTree(prvs.mViewCell);
2438	}
2439	}
2440	else
2441	{
2442	pvs = viewCell->GetPvs();
2443	}
2444
2445	if (spatialFilterSize >=0.0f)
2446	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
2447
2448	}
2449
2450
2451
2452	void
2453	ViewCellsManager::ApplyFilter(KdTree *kdTree,
2454	const float relViewSpaceFilterSize,
2455	const float relSpatialFilterSize
2456	)
2457	{
2458
2459	if (!ViewCellsConstructed())
2460	return;
2461
2462	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2463
2464	ObjectPvs *newPvs;
2465	newPvs = new ObjectPvs[mViewCells.size()];
2466
2467	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
2468	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
2469
2470	int i;
2471	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2472	ApplyFilter(*it,
2473	kdTree,
2474	viewSpaceFilterSize,
2475	spatialFilterSize,
2476	newPvs[i]
2477	);
2478	}
2479
2480	// now replace all pvss
2481	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2482
2483	ObjectPvs &pvs = (*it)->GetPvs();
2484	pvs.Clear();
2485	pvs = newPvs[i];
2486	newPvs[i].Clear();
2487	}
2488
2489	delete [] newPvs;
2490	}
2491
2492
2493	void
2494	ViewCellsManager::ApplySpatialFilter(
2495	KdTree *kdTree,
2496	const float spatialFilterSize,
2497	ObjectPvs &pvs
2498	)
2499	{
2500	// now compute a new Pvs by including also objects intersecting the
2501	// extended boxes of visible objects
2502	Intersectable::NewMail();
2503
2504	ObjectPvsIterator pit = pvs.GetIterator();
2505
2506	while (pit.HasMoreEntries())
2507	{
2508	ObjectPvsEntry entry = pit.Next();
2509
2510	Intersectable *object = entry.mObject;
2511	object->Mail();
2512	}
2513
2514	ObjectPvs nPvs;
2515	int nPvsSize = 0;
2516
2517	ObjectPvsIterator pit2 = pvs.GetIterator();
2518
2519	while (pit2.HasMoreEntries())
2520	{
2521	// now go through the pvs again
2522	ObjectPvsEntry entry = pit2.Next();
2523	Intersectable *object = entry.mObject;
2524
2525	// Vector3 center = object->GetBox().Center();
2526	// AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
2527	// center + Vector3(spatialFilterSize/2));
2528
2529	AxisAlignedBox3 box = object->GetBox();
2530	box.Enlarge(Vector3(spatialFilterSize/2));
2531
2532	ObjectContainer objects;
2533
2534	// $$ warning collect objects takes only unmailed ones!
2535	kdTree->CollectObjects(box, objects);
2536	// cout<<"collected objects="<<objects.size()<<endl;
2537	ObjectContainer::const_iterator noi = objects.begin();
2538	for (; noi != objects.end(); ++ noi)
2539	{
2540	Intersectable o = noi;
2541
2542	// $$ JB warning: pdfs are not correct at this point!
2543	nPvs.AddSample(o, Limits::Small);
2544	nPvsSize ++;
2545	}
2546	}
2547
2548	// cout<<"nPvs size = "<<nPvsSize<<endl;
2549	pvs.MergeInPlace(nPvs);
2550	}
2551
2552
2553	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
2554	const ViewCellContainer &viewCells) const
2555	{
2556	MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
2557	}
2558
2559
2560	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
2561	const ViewCellContainer &viewCells,
2562	const int leftIdx,
2563	const int rightIdx) const
2564	{
2565	if (leftIdx == rightIdx)
2566	{
2567	pvs = viewCells[leftIdx]->GetPvs();
2568	}
2569	else
2570	{
2571	const int midSplit = (leftIdx + rightIdx) / 2;
2572
2573	ObjectPvs leftPvs, rightPvs;
2574	MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
2575	MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);
2576
2577	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
2578	}
2579	}
2580
2581
2582	#if 1
2583	PvsFilterStatistics
2584	ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
2585	const bool useViewSpaceFilter,
2586	const float filterSize,
2587	ObjectPvs &pvs
2588	)
2589	{
2590	cout<<"y";
2591	PvsFilterStatistics stats;
2592
2593	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
2594	Vector3 center = vbox.Center();
2595	// copy the PVS
2596	ObjectPvs basePvs = viewCell->GetPvs();
2597	Intersectable::NewMail();
2598
2599	ObjectPvsIterator pit = basePvs.GetIterator();
2600
2601	#if !USE_KD_PVS
2602	// first mark all object from this pvs
2603	while (pit.HasMoreEntries()) {
2604	ObjectPvsEntry entry = pit.Next();
2605
2606	Intersectable *object = entry.mObject;
2607	object->Mail();
2608	}
2609	#endif
2610
2611	int pvsSize = 0;
2612	int nPvsSize = 0;
2613	float samples = (float)basePvs.GetSamples();
2614
2615	Debug<<"f #s="<<samples<<" pvs size = "<<basePvs.GetSize();
2616	// cout<<"Filter size = "<<filterSize<<endl;
2617	// cout<<"vbox = "<<vbox<<endl;
2618	// cout<<"center = "<<center<<endl;
2619
2620
2621	// Minimal number of local samples to take into account
2622	// the local sampling density.
2623	// The size of the filter is a minimum of the conservative
2624	// local sampling density estimate (#rays intersecting teh viewcell and
2625	// the object)
2626	// and gobal estimate for the view cell
2627	// (total #rays intersecting the viewcell)
2628	#define MIN_LOCAL_SAMPLES 5
2629
2630	float viewCellRadius = 0.5f*Magnitude(vbox.Diagonal());
2631
2632	// now compute the filter box around the current viewCell
2633
2634	if (useViewSpaceFilter) {
2635	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
2636	float radius = viewCellRadius/100.0f;
2637	vbox.Enlarge(radius);
2638	cout<<"vbox = "<<vbox<<endl;
2639	ViewCellContainer viewCells;
2640	ComputeBoxIntersections(vbox, viewCells);
2641
2642	ViewCellContainer::const_iterator it = viewCells.begin(),
2643	it_end = viewCells.end();
2644	int i = 0;
2645	for (i=0; it != it_end; ++ it, ++ i)
2646	if ((*it) != viewCell) {
2647	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
2648	basePvs.MergeInPlace((*it)->GetPvs());
2649	}
2650
2651	// update samples and globalC
2652	samples = (float)pvs.GetSamples();
2653	// cout<<"neighboring viewcells = "<<i-1<<endl;
2654	// cout<<"Samples' = "<<samples<<endl;
2655	}
2656
2657	// Minimal number of samples so that filtering takes place
2658	#define MIN_SAMPLES 100
2659	if (samples > MIN_SAMPLES) {
2660	float globalC = 2.0f*filterSize/sqrt(samples);
2661
2662	pit = basePvs.GetIterator();
2663
2664	ObjectContainer objects;
2665
2666	while (pit.HasMoreEntries())
2667	{
2668	ObjectPvsEntry entry = pit.Next();
2669
2670	Intersectable *object = entry.mObject;
2671	// compute filter size based on the distance and the numebr of samples
2672	AxisAlignedBox3 box = object->GetBox();
2673
2674	float distance = Distance(center, box.Center());
2675	float globalRadius = distance*globalC;
2676
2677	int objectSamples = (int)entry.mData.mSumPdf;
2678	float localRadius = MAX_FLOAT;
2679	if (objectSamples > MIN_LOCAL_SAMPLES)
2680	localRadius = filterSize0.5fMagnitude(box.Diagonal())/
2681	sqrt((float)objectSamples);
2682
2683	// cout<<"lr="<<localRadius<<" gr="<<globalRadius<<endl;
2684
2685	// now compute the filter size
2686	float radius;
2687
2688	if (localRadius < globalRadius) {
2689	radius = localRadius;
2690	stats.mLocalFilterCount++;
2691	} else {
2692	radius = globalRadius;
2693	stats.mGlobalFilterCount++;
2694	}
2695
2696	stats.mAvgFilterRadius += radius;
2697
2698	// cout<<"box = "<<box<<endl;
2699	// cout<<"distance = "<<distance<<endl;
2700	// cout<<"radiues = "<<radius<<endl;
2701
2702	box.Enlarge(Vector3(radius));
2703
2704	objects.clear();
2705	// $$ warning collect objects takes only unmailed ones!
2706	CollectObjects(box, objects);
2707	// cout<<"collected objects="<<objects.size()<<endl;
2708	ObjectContainer::const_iterator noi = objects.begin();
2709	for (; noi != objects.end(); ++ noi) {
2710	Intersectable o = noi;
2711	// $$ JB warning: pdfs are not correct at this point!
2712	pvs.AddSampleDirty(o, Limits::Small);
2713	}
2714	}
2715	stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
2716	}
2717
2718	Debug<<" nPvs size = "<<pvs.GetSize()<<endl;
2719
2720	#if !USE_KD_PVS
2721	// copy the base pvs to the new pvs
2722	pit = basePvs.GetIterator();
2723	while (pit.HasMoreEntries()) {
2724	ObjectPvsEntry entry = pit.Next();
2725	pvs.AddSampleDirty(entry.mObject, entry.mData.mSumPdf);
2726	}
2727	#endif
2728	viewCell->SetFilteredPvsSize(pvs.GetSize());
2729
2730	Intersectable::NewMail();
2731	return stats;
2732	}
2733	#else
2734	PvsFilterStatistics
2735	ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
2736	const bool useViewSpaceFilter,
2737	const float filterSize,
2738	ObjectPvs &pvs
2739	)
2740	{
2741	cout << "x";
2742	PvsFilterStatistics stats;
2743
2744	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
2745	Vector3 center = vbox.Center();
2746	// copy the PVS
2747	ObjectPvs basePvs;// = viewCell->GetPvs();
2748	Intersectable::NewMail();
2749
2750	ObjectPvsIterator pit = viewCell->GetPvs().GetIterator();
2751
2752	#if !USE_KD_PVS
2753	// first mark all object from this pvs
2754	while (pit.HasMoreEntries())
2755	{
2756	ObjectPvsEntry entry = pit.Next();
2757
2758	Intersectable *object = entry.mObject;
2759	object->Mail();
2760	}
2761	#endif
2762
2763	int pvsSize = 0;
2764	int nPvsSize = 0;
2765	float samples = (float)viewCell->GetPvs().GetSamples();
2766
2767	Debug<<"f #s="<<samples<<"pvs size = "<<viewCell->GetPvs().GetSize();
2768	// cout<<"Filter size = "<<filterSize<<endl;
2769	// cout<<"vbox = "<<vbox<<endl;
2770	// cout<<"center = "<<center<<endl;
2771
2772
2773	// Minimal number of local samples to take into account
2774	// the local sampling density.
2775	// The size of the filter is a minimum of the conservative
2776	// local sampling density estimate (#rays intersecting teh viewcell and
2777	// the object)
2778	// and gobal estimate for the view cell
2779	// (total #rays intersecting the viewcell)
2780	#define MIN_LOCAL_SAMPLES 5
2781
2782	float viewCellRadius = 0.5f*Magnitude(vbox.Diagonal());
2783
2784	// now compute the filter box around the current viewCell
2785
2786	if (useViewSpaceFilter)
2787	{
2788	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
2789	float radius = viewCellRadius/100.0f;
2790	vbox.Enlarge(radius);
2791	cout<<"vbox = "<<vbox<<endl;
2792	ViewCellContainer viewCells;
2793	ComputeBoxIntersections(vbox, viewCells);
2794
2795	MergeViewCellsEfficient(basePvs, viewCells);
2796	cout << "basepvs size " << basePvs.GetSize() << endl;
2797	// update samples and globalC
2798	samples = (float)pvs.GetSamples();
2799	// cout<<"neighboring viewcells = "<<i-1<<endl;
2800	// cout<<"Samples' = "<<samples<<endl;
2801	}
2802	else
2803	{
2804	basePvs = viewCell->GetPvs();
2805	}
2806
2807	// Minimal number of samples so that filtering takes place
2808	#define MIN_SAMPLES 100
2809	if (samples > MIN_SAMPLES)
2810	{
2811	float globalC = 2.0f*filterSize/sqrt(samples);
2812
2813	pit = basePvs.GetIterator();
2814
2815	ObjectContainer objects;
2816
2817	while (pit.HasMoreEntries())
2818	{
2819	ObjectPvsEntry entry = pit.Next();
2820
2821	Intersectable *object = entry.mObject;
2822	// compute filter size based on the distance and the numebr of samples
2823	AxisAlignedBox3 box = object->GetBox();
2824
2825	float distance = Distance(center, box.Center());
2826	float globalRadius = distance*globalC;
2827
2828	int objectSamples = (int)entry.mData.mSumPdf;
2829	float localRadius = MAX_FLOAT;
2830
2831	if (objectSamples > MIN_LOCAL_SAMPLES)
2832	{
2833	localRadius = filterSize0.5fMagnitude(box.Diagonal())/
2834	sqrt((float)objectSamples);
2835	}
2836
2837	// cout<<"lr="<<localRadius<<" gr="<<globalRadius<<endl;
2838
2839	// now compute the filter size
2840	float radius;
2841
2842	if (localRadius < globalRadius)
2843	{
2844	radius = localRadius;
2845	stats.mLocalFilterCount++;
2846	}
2847	else
2848	{
2849	radius = globalRadius;
2850	stats.mGlobalFilterCount++;
2851	}
2852
2853	stats.mAvgFilterRadius += radius;
2854
2855	// cout<<"box = "<<box<<endl;
2856	// cout<<"distance = "<<distance<<endl;
2857	// cout<<"radiues = "<<radius<<endl;
2858
2859	box.Enlarge(Vector3(radius));
2860	objects.clear();
2861
2862	// $$ warning collect objects takes only unmailed ones!
2863	CollectObjects(box, objects);
2864
2865	// cout<<"collected objects="<<objects.size()<<endl;
2866	ObjectContainer::const_iterator noi = objects.begin();
2867	for (; noi != objects.end(); ++ noi)
2868	{
2869	Intersectable o = noi;
2870	// $$ JB warning: pdfs are not correct at this point!
2871	pvs.AddSampleDirty(o, Limits::Small);
2872	}
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	{
2885	ObjectPvsEntry entry = pit.Next();
2886	pvs.AddSampleDirty(entry.mObject, entry.mData.mSumPdf);
2887	}
2888	#endif
2889	viewCell->SetFilteredPvsSize(pvs.GetSize());
2890
2891	Intersectable::NewMail();
2892
2893	return stats;
2894	}
2895	#endif
2896
2897
2898
2899	void ViewCellsManager::ExportColor(Exporter *exporter,
2900	ViewCell *vc,
2901	bool colorCode) const
2902	{
2903	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
2904
2905	float importance = 0;
2906	static Material m;
2907	//cout << "color code: " << colorCode << endl;
2908	switch (mColorCode)
2909	{
2910	case 0: // Random
2911	{
2912	if (vcValid)
2913	{
2914	m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
2915	m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
2916	m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
2917	}
2918	else
2919	{
2920	m.mDiffuseColor.r = 0.0f;
2921	m.mDiffuseColor.g = 1.0f;
2922	m.mDiffuseColor.b = 0.0f;
2923	}
2924
2925	exporter->SetForcedMaterial(m);
2926	return;
2927	}
2928
2929	case 1: // pvs
2930	{
2931	if (mCurrentViewCellsStats.maxPvs)
2932	{
2933	importance = (float)mViewCellsTree->GetPvsCost(vc) /
2934	(float)mCurrentViewCellsStats.maxPvs;
2935	}
2936	}
2937	break;
2938	case 2: // merges
2939	{
2940	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
2941	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
2942	}
2943	break;
2944	#if 0
2945	case 3: // merge tree differene
2946	{
2947	importance = (float)GetMaxTreeDiff(vc) /
2948	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
2949
2950	}
2951	break;
2952	#endif
2953	default:
2954	break;
2955	}
2956
2957	// special color code for invalid view cells
2958	m.mDiffuseColor.r = importance;
2959	m.mDiffuseColor.g = vcValid ? 0.0f : 1.0f;
2960	m.mDiffuseColor.b = 1.0f - importance;
2961
2962	//Debug << "importance: " << importance << endl;
2963	exporter->SetForcedMaterial(m);
2964	}
2965
2966
2967	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2968	vector<MergeCandidate> &candidates)
2969	{
2970	// implemented in subclasses
2971	}
2972
2973
2974	void ViewCellsManager::UpdatePvsForEvaluation()
2975	{
2976	ObjectPvs objPvs;
2977	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
2978	}
2979
2980	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
2981	{
2982	// terminate traversal
2983	if (root->IsLeaf())
2984	{
2985	//cout << "updating leaf" << endl;
2986	// we assume that pvs is explicitly stored in leaves
2987	pvs = root->GetPvs();
2988	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
2989	return;
2990	}
2991
2992	////////////////
2993	//-- interior node => propagate pvs up the tree
2994
2995	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
2996
2997	// reset interior pvs
2998	interior->GetPvs().Clear();
2999	// reset recursive pvs
3000	pvs.Clear();
3001
3002	// pvss of child nodes
3003	vector<ObjectPvs> pvsList;
3004	pvsList.resize((int)interior->mChildren.size());
3005
3006	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3007
3008	int i = 0;
3009
3010	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3011	{
3012	//////////////////
3013	//-- recursivly compute child pvss
3014	UpdatePvsForEvaluation(vit, pvsList[i]/objPvs*/);
3015	}
3016
3017	#if 1
3018	Intersectable::NewMail();
3019
3020	//-- faster way of computing pvs:
3021	//-- construct merged pvs by adding
3022	//-- and only those of the next pvs which were not mailed.
3023	//-- note: sumpdf is not correct!!
3024
3025	vector<ObjectPvs>::iterator oit = pvsList.begin();
3026
3027	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3028	{
3029	ObjectPvsIterator pit = (*oit).GetIterator();
3030
3031	// first mark all object from this pvs
3032	while (pit.HasMoreEntries())
3033	{
3034	ObjectPvsEntry entry = pit.Next();
3035
3036	Intersectable *intersect = entry.mObject;
3037
3038	if (!intersect->Mailed())
3039	{
3040	pvs.AddSample(intersect, entry.mData.mSumPdf);
3041	intersect->Mail();
3042	}
3043	}
3044	}
3045
3046	// store pvs in this node
3047	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3048	{
3049	interior->SetPvs(pvs);
3050	}
3051
3052	// set new pvs size
3053	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3054
3055	#else
3056	// really merge cells: slow put sumPdf is correct
3057	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3058	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3059	#endif
3060	}
3061
3062
3063
3064	/*******************************************************************/
3065	/* BspViewCellsManager implementation */
3066	/*******************************************************************/
3067
3068
3069	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
3070	ViewCellsManager(vcTree), mBspTree(bspTree)
3071	{
3072	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3073
3074	mBspTree->SetViewCellsManager(this);
3075	mBspTree->SetViewCellsTree(mViewCellsTree);
3076	}
3077
3078
3079	bool BspViewCellsManager::ViewCellsConstructed() const
3080	{
3081	return mBspTree->GetRoot() != NULL;
3082	}
3083
3084
3085	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
3086	{
3087	return new BspViewCell(mesh);
3088	}
3089
3090
3091	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3092	const VssRayContainer &rays)
3093	{
3094	// if view cells were already constructed, we can finish
3095	if (ViewCellsConstructed())
3096	return 0;
3097
3098	int sampleContributions = 0;
3099
3100	// construct view cells using the collected samples
3101	RayContainer constructionRays;
3102	VssRayContainer savedRays;
3103
3104	// choose a a number of rays based on the ratio of cast rays / requested rays
3105	const int limit = min(mInitialSamples, (int)rays.size());
3106	VssRayContainer::const_iterator it, it_end = rays.end();
3107
3108	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3109
3110	for (it = rays.begin(); it != it_end; ++ it)
3111	{
3112	if (Random(1.0f) < prop)
3113	constructionRays.push_back(new Ray((it)));
3114	else
3115	savedRays.push_back(*it);
3116	}
3117
3118	if (!mUsePredefinedViewCells)
3119	{
3120	// no view cells loaded
3121	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3122	// collect final view cells
3123	mBspTree->CollectViewCells(mViewCells);
3124	}
3125	else
3126	{
3127	// use predefined view cells geometry =>
3128	// contruct bsp hierarchy over them
3129	mBspTree->Construct(mViewCells);
3130	}
3131
3132	// destroy rays created only for construction
3133	CLEAR_CONTAINER(constructionRays);
3134
3135	Debug << mBspTree->GetStatistics() << endl;
3136	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3137
3138	// recast rest of the rays
3139	if (SAMPLE_AFTER_SUBDIVISION)
3140	ComputeSampleContributions(savedRays, true, false);
3141
3142	// real meshes are contructed at this stage
3143	if (0)
3144	{
3145	cout << "finalizing view cells ... ";
3146	FinalizeViewCells(true);
3147	cout << "finished" << endl;
3148	}
3149
3150	return sampleContributions;
3151	}
3152
3153
3154	void BspViewCellsManager::CollectViewCells()
3155	{
3156	if (!ViewCellsTreeConstructed())
3157	{ // view cells tree constructed
3158	mBspTree->CollectViewCells(mViewCells);
3159	}
3160	else
3161	{ // we can use the view cells tree hierarchy to get the right set
3162	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3163	}
3164	}
3165
3166
3167	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3168	{
3169	if (1)
3170	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3171	else
3172	// compute view cell area as subsititute for probability
3173	return GetArea(viewCell) / GetAccVcArea();
3174	}
3175
3176
3177
3178	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3179	const Vector3 &termination,
3180	ViewCellContainer &viewcells)
3181	{
3182	return mBspTree->CastLineSegment(origin, termination, viewcells);
3183	}
3184
3185
3186	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3187	{
3188	// save color code
3189	const int savedColorCode = mColorCode;
3190
3191	Exporter *exporter;
3192
3193	#if 0
3194	// export merged view cells
3195	mColorCode = 0; // use random colors
3196
3197	exporter = Exporter::GetExporter("merged_view_cells.wrl");
3198
3199	cout << "exporting view cells after merge ... ";
3200
3201	if (exporter)
3202	{
3203	if (mExportGeometry)
3204	{
3205	exporter->ExportGeometry(objects);
3206	}
3207
3208	exporter->SetFilled();
3209	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3210
3211	delete exporter;
3212	}
3213	cout << "finished" << endl;
3214	#endif
3215
3216	// export merged view cells using pvs color coding
3217	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3218	cout << "exporting view cells after merge (pvs size) ... ";
3219
3220	if (exporter)
3221	{
3222	if (mExportGeometry)
3223	{
3224	exporter->ExportGeometry(objects);
3225	}
3226
3227	exporter->SetFilled();
3228	mColorCode = 1;
3229
3230	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3231
3232	delete exporter;
3233	}
3234	cout << "finished" << endl;
3235
3236	mColorCode = savedColorCode;
3237	}
3238
3239
3240	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3241	const VssRayContainer &rays)
3242	{
3243	if (!ViewCellsConstructed())
3244	{
3245	Debug << "view cells not constructed" << endl;
3246	return 0;
3247	}
3248
3249	// view cells already finished before post processing step,
3250	// i.e., because they were loaded from disc
3251	if (mViewCellsFinished)
3252	{
3253	FinalizeViewCells(true);
3254	EvaluateViewCellsStats();
3255
3256	return 0;
3257	}
3258
3259	//////////////////
3260	//-- merge leaves of the view cell hierarchy
3261
3262	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3263	long startTime = GetTime();
3264
3265	VssRayContainer postProcessRays;
3266	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3267
3268	if (mMergeViewCells)
3269	{
3270	cout << "constructing visibility based merge tree" << endl;
3271	mViewCellsTree->ConstructMergeTree(rays, objects);
3272	}
3273	else
3274	{
3275	cout << "constructing spatial merge tree" << endl;
3276	ViewCell *root;
3277	// the spatial merge tree is difficult to build for
3278	// this type of construction, as view cells cover several
3279	// leaves => create dummy tree which is only 2 levels deep
3280	if (mUsePredefinedViewCells)
3281	{
3282	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3283	}
3284	else
3285	{
3286	// create spatial merge hierarchy
3287	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3288	}
3289
3290	mViewCellsTree->SetRoot(root);
3291
3292	// recompute pvs in the whole hierarchy
3293	ObjectPvs pvs;
3294	UpdatePvsForEvaluation(root, pvs);
3295	}
3296
3297	cout << "finished" << endl;
3298	cout << "merged view cells in "
3299	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3300
3301	Debug << "Postprocessing: Merged view cells in "
3302	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3303
3304
3305	////////////////////////
3306	//-- visualization and statistics after merge
3307
3308	if (1)
3309	{
3310	char mstats[100];
3311	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3312	mViewCellsTree->ExportStats(mstats);
3313	}
3314
3315	// recompute view cells and stats
3316	ResetViewCells();
3317	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3318
3319	// visualization of the view cells
3320	if (1) ExportMergedViewCells(objects);
3321
3322	// compute final meshes and volume / area
3323	if (1) FinalizeViewCells(true);
3324
3325	return 0;
3326	}
3327
3328
3329	BspViewCellsManager::~BspViewCellsManager()
3330	{
3331	}
3332
3333
3334	int BspViewCellsManager::GetType() const
3335	{
3336	return BSP;
3337	}
3338
3339
3340	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3341	const VssRayContainer &sampleRays)
3342	{
3343	if (!ViewCellsConstructed())
3344	return;
3345
3346	const int savedColorCode = mColorCode;
3347
3348	if (1) // export final view cells
3349	{
3350	mColorCode = 1; // hack color code
3351	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3352
3353	cout << "exporting view cells after merge (pvs size) ... ";
3354
3355	if (exporter)
3356	{
3357	if (mExportGeometry)
3358	{
3359	exporter->ExportGeometry(objects);
3360	}
3361
3362	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3363	delete exporter;
3364	}
3365	cout << "finished" << endl;
3366	}
3367
3368	// reset color code
3369	mColorCode = savedColorCode;
3370
3371
3372	//////////////////
3373	//-- visualization of the BSP splits
3374
3375	bool exportSplits = false;
3376	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3377
3378	if (exportSplits)
3379	{
3380	cout << "exporting splits ... ";
3381	ExportSplits(objects);
3382	cout << "finished" << endl;
3383	}
3384
3385	int leafOut;
3386	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3387	const int raysOut = 100;
3388	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3389	}
3390
3391
3392	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3393	{
3394	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3395
3396	if (exporter)
3397	{
3398	//exporter->SetFilled();
3399	if (mExportGeometry)
3400	{
3401	exporter->ExportGeometry(objects);
3402	}
3403
3404	Material m;
3405	m.mDiffuseColor = RgbColor(1, 0, 0);
3406	exporter->SetForcedMaterial(m);
3407	exporter->SetWireframe();
3408
3409	exporter->ExportBspSplits(*mBspTree, true);
3410
3411	// NOTE: take forced material, else big scenes cannot be viewed
3412	m.mDiffuseColor = RgbColor(0, 1, 0);
3413	exporter->SetForcedMaterial(m);
3414	//exporter->ResetForcedMaterial();
3415
3416	delete exporter;
3417	}
3418	}
3419
3420
3421	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3422	const int maxViewCells,
3423	const bool sortViewCells,
3424	const bool exportPvs,
3425	const bool exportRays,
3426	const int maxRays,
3427	const string prefix,
3428	VssRayContainer *visRays)
3429	{
3430	if (sortViewCells)
3431	{ // sort view cells to visualize the largest view cells
3432	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
3433	}
3434
3435	//////////
3436	//-- some view cells for output
3437
3438	ViewCell::NewMail();
3439	const int limit = min(maxViewCells, (int)mViewCells.size());
3440
3441	for (int i = 0; i < limit; ++ i)
3442	{
3443	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
3444	ViewCell *vc = mViewCells[idx];
3445
3446	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
3447	continue;
3448
3449	vc->Mail();
3450
3451	ObjectPvs pvs;
3452	mViewCellsTree->GetPvs(vc, pvs);
3453
3454	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
3455	Exporter *exporter = Exporter::GetExporter(s);
3456
3457	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetPvsCost(vc) << endl;
3458
3459	if (exportRays)
3460	{
3461	////////////
3462	//-- export rays piercing this view cell
3463
3464	// use rays stored with the view cells
3465	VssRayContainer vcRays, vcRays2, vcRays3;
3466	VssRayContainer collectRays;
3467
3468	// collect initial view cells
3469	ViewCellContainer leaves;
3470	mViewCellsTree->CollectLeaves(vc, leaves);
3471
3472	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3473	for (vit = leaves.begin(); vit != vit_end; ++ vit)
3474	{
3475	// prepare some rays for output
3476	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
3477	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
3478	{
3479	collectRays.push_back(*rit);
3480	}
3481	}
3482
3483	const int raysOut = min((int)collectRays.size(), maxRays);
3484
3485	// prepare some rays for output
3486	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3487	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3488	{
3489	const float p = RandomValue(0.0f, (float)collectRays.size());
3490	if (p < raysOut)
3491	{
3492	if ((*rit)->mFlags & VssRay::BorderSample)
3493	{
3494	vcRays.push_back(*rit);
3495	}
3496	else if ((*rit)->mFlags & VssRay::ReverseSample)
3497	vcRays2.push_back(*rit);
3498	else
3499	vcRays3.push_back(*rit);
3500
3501	}
3502	}
3503
3504	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
3505	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
3506	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
3507	}
3508
3509	////////////////
3510	//-- export view cell geometry
3511
3512	exporter->SetWireframe();
3513
3514	Material m;//= RandomMaterial();
3515	m.mDiffuseColor = RgbColor(0, 1, 0);
3516	exporter->SetForcedMaterial(m);
3517
3518	ExportViewCellGeometry(exporter, vc, NULL, NULL);
3519	exporter->SetFilled();
3520
3521	if (exportPvs)
3522	{
3523	Intersectable::NewMail();
3524	ObjectPvsIterator pit = pvs.GetIterator();
3525
3526	while (pit.HasMoreEntries())
3527	{
3528	ObjectPvsEntry entry = pit.Next();
3529
3530	// output PVS of view cell
3531	Intersectable *intersect = entry.mObject;
3532
3533	if (!intersect->Mailed())
3534	{
3535	intersect->Mail();
3536
3537	m = RandomMaterial();
3538	exporter->SetForcedMaterial(m);
3539	exporter->ExportIntersectable(intersect);
3540	}
3541	}
3542	cout << endl;
3543	}
3544
3545	DEL_PTR(exporter);
3546	cout << "finished" << endl;
3547	}
3548	}
3549
3550
3551	void BspViewCellsManager::TestSubdivision()
3552	{
3553	ViewCellContainer leaves;
3554	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
3555
3556	ViewCellContainer::const_iterator it, it_end = leaves.end();
3557
3558	const float vol = mViewSpaceBox.GetVolume();
3559	float subdivVol = 0;
3560	float newVol = 0;
3561
3562	for (it = leaves.begin(); it != it_end; ++ it)
3563	{
3564	BspNodeGeometry geom;
3565	mBspTree->ConstructGeometry(*it, geom);
3566
3567	const float lVol = geom.GetVolume();
3568	newVol += lVol;
3569	subdivVol += (*it)->GetVolume();
3570
3571	const float thres = 0.9f;
3572	if ((lVol < ((it)->GetVolume() thres)) \|\|
3573	(lVol * thres > ((*it)->GetVolume())))
3574	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
3575	}
3576
3577	Debug << "exact volume: " << vol << endl;
3578	Debug << "subdivision volume: " << subdivVol << endl;
3579	Debug << "new volume: " << newVol << endl;
3580	}
3581
3582
3583	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3584	ViewCell *vc,
3585	const AxisAlignedBox3 *sceneBox,
3586	const AxisAlignedPlane *clipPlane
3587	) const
3588	{
3589	if (clipPlane)
3590	{
3591	const Plane3 plane = clipPlane->GetPlane();
3592
3593	ViewCellContainer leaves;
3594	mViewCellsTree->CollectLeaves(vc, leaves);
3595	ViewCellContainer::const_iterator it, it_end = leaves.end();
3596
3597	for (it = leaves.begin(); it != it_end; ++ it)
3598	{
3599	BspNodeGeometry geom;
3600	BspNodeGeometry front;
3601	BspNodeGeometry back;
3602
3603	mBspTree->ConstructGeometry(*it, geom);
3604
3605	const float eps = 0.0001f;
3606	const int cf = geom.Side(plane, eps);
3607
3608	if (cf == -1)
3609	{
3610	exporter->ExportPolygons(geom.GetPolys());
3611	}
3612	else if (cf == 0)
3613	{
3614	geom.SplitGeometry(front,
3615	back,
3616	plane,
3617	mViewSpaceBox,
3618	eps);
3619
3620	if (back.Valid())
3621	{
3622	exporter->ExportPolygons(back.GetPolys());
3623	}
3624	}
3625	}
3626	}
3627	else
3628	{
3629	// export mesh if available
3630	// TODO: some bug here?
3631	if (1 && vc->GetMesh())
3632	{
3633	exporter->ExportMesh(vc->GetMesh());
3634	}
3635	else
3636	{
3637	BspNodeGeometry geom;
3638	mBspTree->ConstructGeometry(vc, geom);
3639	exporter->ExportPolygons(geom.GetPolys());
3640	}
3641	}
3642	}
3643
3644
3645	void BspViewCellsManager::CreateMesh(ViewCell *vc)
3646	{
3647	// note: should previous mesh be deleted (via mesh manager?)
3648	BspNodeGeometry geom;
3649	mBspTree->ConstructGeometry(vc, geom);
3650
3651	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
3652
3653	IncludeNodeGeomInMesh(geom, *mesh);
3654	vc->SetMesh(mesh);
3655	}
3656
3657
3658	void BspViewCellsManager::Finalize(ViewCell *viewCell,
3659	const bool createMesh)
3660	{
3661	float area = 0;
3662	float volume = 0;
3663
3664	ViewCellContainer leaves;
3665	mViewCellsTree->CollectLeaves(viewCell, leaves);
3666
3667	ViewCellContainer::const_iterator it, it_end = leaves.end();
3668
3669	for (it = leaves.begin(); it != it_end; ++ it)
3670	{
3671	BspNodeGeometry geom;
3672
3673	mBspTree->ConstructGeometry(*it, geom);
3674
3675	const float lVol = geom.GetVolume();
3676	const float lArea = geom.GetArea();
3677
3678	area += lArea;
3679	volume += lVol;
3680
3681	CreateMesh(*it);
3682	}
3683
3684	viewCell->SetVolume(volume);
3685	viewCell->SetArea(area);
3686	}
3687
3688
3689	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
3690	{
3691	if (!ViewCellsConstructed())
3692	{
3693	return NULL;
3694	}
3695	if (!mViewSpaceBox.IsInside(point))
3696	{
3697	return NULL;
3698	}
3699	return mBspTree->GetViewCell(point);
3700	}
3701
3702
3703	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3704	vector<MergeCandidate> &candidates)
3705	{
3706	cout << "collecting merge candidates ... " << endl;
3707
3708	if (mUseRaysForMerge)
3709	{
3710	mBspTree->CollectMergeCandidates(rays, candidates);
3711	}
3712	else
3713	{
3714	vector<BspLeaf *> leaves;
3715	mBspTree->CollectLeaves(leaves);
3716	mBspTree->CollectMergeCandidates(leaves, candidates);
3717	}
3718
3719	cout << "fininshed collecting candidates" << endl;
3720	}
3721
3722
3723
3724	bool BspViewCellsManager::ExportViewCells(const string filename,
3725	const bool exportPvs,
3726	const ObjectContainer &objects)
3727	{
3728	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
3729	{
3730	return false;
3731	}
3732
3733	cout << "exporting view cells to xml ... ";
3734
3735	OUT_STREAM stream(filename.c_str());
3736
3737	// for output we need unique ids for each view cell
3738	CreateUniqueViewCellIds();
3739
3740	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3741	stream << "<VisibilitySolution>" << endl;
3742
3743	if (exportPvs)
3744	{
3745	//////////
3746	//-- export bounding boxes: they are used to identify the objects from the pvs and
3747	//-- assign them to the entities in the rendering engine
3748
3749	stream << "<BoundingBoxes>" << endl;
3750	ObjectContainer::const_iterator oit, oit_end = objects.end();
3751
3752	for (oit = objects.begin(); oit != oit_end; ++ oit)
3753	{
3754	const AxisAlignedBox3 box = (*oit)->GetBox();
3755
3756	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
3757	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
3758	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
3759	}
3760
3761	stream << "</BoundingBoxes>" << endl;
3762	}
3763
3764	///////////
3765	//-- export the view cells and the pvs
3766
3767	const int numViewCells = mCurrentViewCellsStats.viewCells;
3768	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
3769
3770	mViewCellsTree->Export(stream, exportPvs);
3771
3772	stream << "</ViewCells>" << endl;
3773
3774	/////////////
3775	//-- export the view space hierarchy
3776	stream << "<ViewSpaceHierarchy type=\"bsp\""
3777	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3778	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
3779
3780	mBspTree->Export(stream);
3781
3782	// end tags
3783	stream << "</ViewSpaceHierarchy>" << endl;
3784	stream << "</VisibilitySolution>" << endl;
3785
3786	stream.close();
3787	cout << "finished" << endl;
3788
3789	return true;
3790	}
3791
3792
3793	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
3794	{
3795	ViewCellInterior *vcRoot = new ViewCellInterior();
3796
3797	// evaluate merge cost for priority traversal
3798	const float mergeCost = -(float)root->mTimeStamp;
3799	vcRoot->SetMergeCost(mergeCost);
3800
3801	float volume = 0;
3802	vector<BspLeaf *> leaves;
3803	mBspTree->CollectLeaves(leaves);
3804	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
3805	ViewCell::NewMail();
3806
3807	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3808	{
3809	BspLeaf leaf = lit;
3810	ViewCell *vc = leaf->GetViewCell();
3811
3812	if (!vc->Mailed())
3813	{
3814	vc->Mail();
3815	vc->SetMergeCost(0.0f);
3816	vcRoot->SetupChildLink(vc);
3817
3818	volume += vc->GetVolume();
3819	volume += vc->GetVolume();
3820	vcRoot->SetVolume(volume);
3821	}
3822	}
3823
3824	return vcRoot;
3825	}
3826
3827
3828	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
3829	{
3830	// terminate recursion
3831	if (root->IsLeaf())
3832	{
3833	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
3834	leaf->GetViewCell()->SetMergeCost(0.0f);
3835	return leaf->GetViewCell();
3836	}
3837
3838	BspInterior interior = dynamic_cast<BspInterior >(root);
3839	ViewCellInterior *viewCellInterior = new ViewCellInterior();
3840
3841	// evaluate merge cost for priority traversal
3842	const float mergeCost = -(float)root->mTimeStamp;
3843	viewCellInterior->SetMergeCost(mergeCost);
3844
3845	float volume = 0;
3846
3847	BspNode *front = interior->GetFront();
3848	BspNode *back = interior->GetBack();
3849
3850
3851	////////////
3852	//-- recursivly compute child hierarchies
3853
3854	ViewCell *backVc = ConstructSpatialMergeTree(back);
3855	ViewCell *frontVc = ConstructSpatialMergeTree(front);
3856
3857	viewCellInterior->SetupChildLink(backVc);
3858	viewCellInterior->SetupChildLink(frontVc);
3859
3860	volume += backVc->GetVolume();
3861	volume += frontVc->GetVolume();
3862
3863	viewCellInterior->SetVolume(volume);
3864
3865	return viewCellInterior;
3866	}
3867
3868
3869	/************************************************************************/
3870	/* KdViewCellsManager implementation */
3871	/************************************************************************/
3872
3873
3874
3875	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
3876	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
3877	{
3878	}
3879
3880
3881	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
3882	{
3883	// compute view cell area / volume as subsititute for probability
3884	if (0)
3885	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
3886	else
3887	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3888	}
3889
3890
3891
3892
3893	void KdViewCellsManager::CollectViewCells()
3894	{
3895	//mKdTree->CollectViewCells(mViewCells); TODO
3896	}
3897
3898
3899	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3900	const VssRayContainer &rays)
3901	{
3902	// if view cells already constructed
3903	if (ViewCellsConstructed())
3904	return 0;
3905
3906	mKdTree->Construct();
3907
3908	mTotalAreaValid = false;
3909	// create the view cells
3910	mKdTree->CreateAndCollectViewCells(mViewCells);
3911	// cast rays
3912	ComputeSampleContributions(rays, true, false);
3913
3914	EvaluateViewCellsStats();
3915	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3916
3917	return 0;
3918	}
3919
3920
3921	bool KdViewCellsManager::ViewCellsConstructed() const
3922	{
3923	return mKdTree->GetRoot() != NULL;
3924	}
3925
3926
3927	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
3928	const VssRayContainer &rays)
3929	{
3930	return 0;
3931	}
3932
3933
3934	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3935	const int maxViewCells,
3936	const bool sortViewCells,
3937	const bool exportPvs,
3938	const bool exportRays,
3939	const int maxRays,
3940	const string prefix,
3941	VssRayContainer *visRays)
3942	{
3943	// TODO
3944	}
3945
3946
3947	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
3948	const VssRayContainer &sampleRays)
3949	{
3950	if (!ViewCellsConstructed())
3951	return;
3952
3953	// using view cells instead of the kd PVS of objects
3954	const bool useViewCells = true;
3955	bool exportRays = false;
3956
3957	int limit = min(mVisualizationSamples, (int)sampleRays.size());
3958	const int pvsOut = min((int)objects.size(), 10);
3959	VssRayContainer *rays = new VssRayContainer[pvsOut];
3960
3961	if (useViewCells)
3962	{
3963	const int leafOut = 10;
3964
3965	ViewCell::NewMail();
3966
3967	//-- some rays for output
3968	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
3969	Debug << "visualization using " << raysOut << " samples" << endl;
3970
3971	//-- some random view cells and rays for output
3972	vector<KdLeaf *> kdLeaves;
3973
3974	for (int i = 0; i < leafOut; ++ i)
3975	kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
3976
3977	for (int i = 0; i < kdLeaves.size(); ++ i)
3978	{
3979	KdLeaf *leaf = kdLeaves[i];
3980	RayContainer vcRays;
3981
3982	cout << "creating output for view cell " << i << " ... ";
3983	#if 0
3984	// check whether we can add the current ray to the output rays
3985	for (int k = 0; k < raysOut; ++ k)
3986	{
3987	Ray *ray = sampleRays[k];
3988
3989	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
3990	{
3991	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
3992
3993	if (leaf->GetViewCell() == leaf2->GetViewCell())
3994	{
3995	vcRays.push_back(ray);
3996	}
3997	}
3998	}
3999	#endif
4000	Intersectable::NewMail();
4001
4002	ViewCell *vc = leaf->mViewCell;
4003	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4004
4005	Exporter *exporter = Exporter::GetExporter(str);
4006	exporter->SetFilled();
4007
4008	exporter->SetWireframe();
4009	//exporter->SetFilled();
4010
4011	Material m;//= RandomMaterial();
4012	m.mDiffuseColor = RgbColor(1, 1, 0);
4013	exporter->SetForcedMaterial(m);
4014
4015	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4016	exporter->ExportBox(box);
4017
4018	// export rays piercing this view cell
4019	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4020
4021	m.mDiffuseColor = RgbColor(1, 0, 0);
4022	exporter->SetForcedMaterial(m);
4023
4024	// exporter->SetWireframe();
4025	exporter->SetFilled();
4026
4027	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4028
4029	while (pit.HasMoreEntries())
4030	{
4031	ObjectPvsEntry entry = pit.Next();
4032
4033	//-- output PVS of view cell
4034	Intersectable *intersect = entry.mObject;
4035	if (!intersect->Mailed())
4036	{
4037	exporter->ExportIntersectable(intersect);
4038	intersect->Mail();
4039	}
4040	}
4041
4042	DEL_PTR(exporter);
4043	cout << "finished" << endl;
4044	}
4045
4046	DEL_PTR(rays);
4047	}
4048	else // using kd PVS of objects
4049	{
4050	for (int i = 0; i < limit; ++ i)
4051	{
4052	VssRay *ray = sampleRays[i];
4053
4054	// check whether we can add this to the rays
4055	for (int j = 0; j < pvsOut; j++)
4056	{
4057	if (objects[j] == ray->mTerminationObject)
4058	{
4059	rays[j].push_back(ray);
4060	}
4061	}
4062	}
4063
4064	if (exportRays)
4065	{
4066	Exporter *exporter = NULL;
4067	exporter = Exporter::GetExporter("sample-rays.x3d");
4068	exporter->SetWireframe();
4069	exporter->ExportKdTree(*mKdTree);
4070
4071	for (int i = 0; i < pvsOut; i++)
4072	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4073
4074	exporter->SetFilled();
4075	delete exporter;
4076	}
4077
4078	for (int k=0; k < pvsOut; k++)
4079	{
4080	Intersectable *object = objects[k];
4081	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4082
4083	Exporter *exporter = Exporter::GetExporter(str);
4084	exporter->SetWireframe();
4085
4086	// matt: no kd pvs
4087	/*
4088	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4089	Intersectable::NewMail();
4090
4091	// avoid adding the object to the list
4092	object->Mail();
4093	ObjectContainer visibleObjects;
4094
4095	for (; kit != object->mKdPvs.mEntries.end(); i++)
4096	{
4097	KdNode node = (kit).first;
4098	exporter->ExportBox(mKdTree->GetBox(node));
4099
4100	mKdTree->CollectObjects(node, visibleObjects);
4101	}
4102
4103	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4104	exporter->SetFilled();
4105
4106	for (int j = 0; j < visibleObjects.size(); j++)
4107	exporter->ExportIntersectable(visibleObjects[j]);
4108
4109	Material m;
4110	m.mDiffuseColor = RgbColor(1, 0, 0);
4111	exporter->SetForcedMaterial(m);
4112	exporter->ExportIntersectable(object);
4113	*/
4114	delete exporter;
4115	}
4116	}
4117	}
4118
4119
4120	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4121	{
4122	return new KdViewCell(mesh);
4123	}
4124
4125
4126	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4127	ViewCell *vc,
4128	const AxisAlignedBox3 *sceneBox,
4129	const AxisAlignedPlane *clipPlane
4130	) const
4131	{
4132	ViewCellContainer leaves;
4133	mViewCellsTree->CollectLeaves(vc, leaves);
4134	ViewCellContainer::const_iterator it, it_end = leaves.end();
4135
4136	for (it = leaves.begin(); it != it_end; ++ it)
4137	{
4138	KdViewCell kdVc = dynamic_cast<KdViewCell >(*it);
4139	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4140	}
4141	}
4142
4143
4144	int KdViewCellsManager::GetType() const
4145	{
4146	return ViewCellsManager::KD;
4147	}
4148
4149
4150
4151	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4152	{
4153	KdNode *node = leaf;
4154
4155	while (node->mParent && node->mDepth > mKdPvsDepth)
4156	node = node->mParent;
4157
4158	return node;
4159	}
4160
4161	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4162	const Vector3 &termination,
4163	ViewCellContainer &viewcells)
4164	{
4165	return mKdTree->CastLineSegment(origin, termination, viewcells);
4166	}
4167
4168
4169	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4170	{
4171	// TODO
4172	}
4173
4174
4175
4176	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4177	vector<MergeCandidate> &candidates)
4178	{
4179	// TODO
4180	}
4181
4182
4183
4184	/**************************************************************************/
4185	/* VspBspViewCellsManager implementation */
4186	/**************************************************************************/
4187
4188
4189	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4190	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4191	{
4192	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4193	mVspBspTree->SetViewCellsManager(this);
4194	mVspBspTree->mViewCellsTree = mViewCellsTree;
4195	}
4196
4197
4198	VspBspViewCellsManager::~VspBspViewCellsManager()
4199	{
4200	}
4201
4202
4203	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4204	{
4205	if (0 && mVspBspTree->mUseAreaForPvs)
4206	return GetArea(viewCell) / GetAccVcArea();
4207	else
4208	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4209	}
4210
4211
4212	void VspBspViewCellsManager::CollectViewCells()
4213	{
4214	// view cells tree constructed?
4215	if (!ViewCellsTreeConstructed())
4216	{
4217	mVspBspTree->CollectViewCells(mViewCells, false);
4218	}
4219	else
4220	{
4221	// we can use the view cells tree hierarchy to get the right set
4222	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4223	}
4224	}
4225
4226
4227	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4228	vector<MergeCandidate> &candidates)
4229	{
4230	cout << "collecting merge candidates ... " << endl;
4231
4232	if (mUseRaysForMerge)
4233	{
4234	mVspBspTree->CollectMergeCandidates(rays, candidates);
4235	}
4236	else
4237	{
4238	vector<BspLeaf *> leaves;
4239	mVspBspTree->CollectLeaves(leaves);
4240
4241	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4242	}
4243
4244	cout << "fininshed collecting candidates" << endl;
4245	}
4246
4247
4248	bool VspBspViewCellsManager::ViewCellsConstructed() const
4249	{
4250	return mVspBspTree->GetRoot() != NULL;
4251	}
4252
4253
4254	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4255	{
4256	return new BspViewCell(mesh);
4257	}
4258
4259
4260	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4261	const VssRayContainer &rays)
4262	{
4263	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4264
4265	// if view cells were already constructed
4266	if (ViewCellsConstructed())
4267	{
4268	return 0;
4269	}
4270
4271	int sampleContributions = 0;
4272	VssRayContainer sampleRays;
4273
4274	const int limit = min(mInitialSamples, (int)rays.size());
4275
4276	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4277	<< ", actual rays: " << (int)rays.size() << endl;
4278
4279	VssRayContainer savedRays;
4280
4281	if (SAMPLE_AFTER_SUBDIVISION)
4282	{
4283	VssRayContainer constructionRays;
4284
4285	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4286
4287	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4288	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4289
4290	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4291	}
4292	else
4293	{
4294	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4295	mVspBspTree->Construct(rays, &mViewSpaceBox);
4296	}
4297
4298	// collapse invalid regions
4299	cout << "collapsing invalid tree regions ... ";
4300	long startTime = GetTime();
4301
4302	const int collapsedLeaves = mVspBspTree->CollapseTree();
4303	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4304	<< " seconds" << endl;
4305
4306	cout << "finished" << endl;
4307
4308	/////////////////
4309	//-- stats after construction
4310
4311	Debug << mVspBspTree->GetStatistics() << endl;
4312
4313	ResetViewCells();
4314	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4315
4316
4317	//////////////////////
4318	//-- recast the rest of the rays
4319
4320	startTime = GetTime();
4321
4322	cout << "Computing remaining ray contributions ... ";
4323
4324	if (SAMPLE_AFTER_SUBDIVISION)
4325	ComputeSampleContributions(savedRays, true, false);
4326
4327	cout << "finished" << endl;
4328
4329	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4330	<< " secs" << endl;
4331
4332	cout << "construction finished" << endl;
4333
4334	if (0)
4335	{ ////////
4336	//-- real meshes are contructed at this stage
4337
4338	cout << "finalizing view cells ... ";
4339	FinalizeViewCells(true);
4340	cout << "finished" << endl;
4341	}
4342
4343	return sampleContributions;
4344	}
4345
4346
4347	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4348	const ObjectContainer &objects)
4349	{
4350	int vcSize = 0;
4351	int pvsSize = 0;
4352
4353	//-- merge view cells
4354	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4355	long startTime = GetTime();
4356
4357
4358	if (mMergeViewCells)
4359	{
4360	// TODO: should be done BEFORE the ray casting
4361	// compute tree by merging the nodes based on cost heuristics
4362	mViewCellsTree->ConstructMergeTree(rays, objects);
4363	}
4364	else
4365	{
4366	// compute tree by merging the nodes of the spatial hierarchy
4367	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4368	mViewCellsTree->SetRoot(root);
4369
4370	// compute pvs
4371	ObjectPvs pvs;
4372	UpdatePvsForEvaluation(root, pvs);
4373	}
4374
4375	if (1)
4376	{
4377	char mstats[100];
4378	ObjectPvs pvs;
4379
4380	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4381	mViewCellsTree->ExportStats(mstats);
4382	}
4383
4384	cout << "merged view cells in "
4385	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4386
4387	Debug << "Postprocessing: Merged view cells in "
4388	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4389
4390
4391	//////////////////
4392	//-- stats and visualizations
4393
4394	int savedColorCode = mColorCode;
4395
4396	// get currently active view cell set
4397	ResetViewCells();
4398	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4399
4400	if (mShowVisualization) // export merged view cells
4401	{
4402	mColorCode = 0;
4403	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4404
4405	cout << "exporting view cells after merge ... ";
4406
4407	if (exporter)
4408	{
4409	if (0)
4410	exporter->SetWireframe();
4411	else
4412	exporter->SetFilled();
4413
4414	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4415
4416	if (mExportGeometry)
4417	{
4418	Material m;
4419	m.mDiffuseColor = RgbColor(0, 1, 0);
4420	exporter->SetForcedMaterial(m);
4421	exporter->SetFilled();
4422
4423	exporter->ExportGeometry(objects);
4424	}
4425
4426	delete exporter;
4427	}
4428	cout << "finished" << endl;
4429	}
4430
4431	if (mShowVisualization)
4432	{
4433	// use pvs size for color coding
4434	mColorCode = 1;
4435	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
4436
4437	cout << "exporting view cells after merge (pvs size) ... ";
4438
4439	if (exporter)
4440	{
4441	exporter->SetFilled();
4442
4443	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4444
4445	if (mExportGeometry)
4446	{
4447	Material m;
4448	m.mDiffuseColor = RgbColor(0, 1, 0);
4449	exporter->SetForcedMaterial(m);
4450	exporter->SetFilled();
4451
4452	exporter->ExportGeometry(objects);
4453	}
4454
4455	delete exporter;
4456	}
4457	cout << "finished" << endl;
4458	}
4459
4460	mColorCode = savedColorCode;
4461	}
4462
4463
4464	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4465	const ObjectContainer &objects)
4466	{
4467	mRenderer->RenderScene();
4468
4469	SimulationStatistics ss;
4470	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4471	Debug << "render time before refine\n\n" << ss << endl;
4472
4473	const long startTime = GetTime();
4474	cout << "Refining the merged view cells ... ";
4475
4476	// refining the merged view cells
4477	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4478
4479	//-- stats and visualizations
4480	cout << "finished" << endl;
4481	cout << "refined " << refined << " view cells in "
4482	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4483
4484	Debug << "Postprocessing: refined " << refined << " view cells in "
4485	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4486	}
4487
4488
4489	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4490	const VssRayContainer &rays)
4491	{
4492	if (!ViewCellsConstructed())
4493	{
4494	Debug << "postprocess error: no view cells constructed" << endl;
4495	return 0;
4496	}
4497
4498	// view cells already finished before post processing step
4499	// (i.e. because they were loaded)
4500	if (mViewCellsFinished)
4501	{
4502	FinalizeViewCells(true);
4503	EvaluateViewCellsStats();
4504
4505	return 0;
4506	}
4507
4508	// check if new view cells turned invalid
4509	int minPvs, maxPvs;
4510
4511	if (0)
4512	{
4513	minPvs = mMinPvsSize;
4514	maxPvs = mMaxPvsSize;
4515	}
4516	else
4517	{
4518	// problem matt: why did I start here from zero?
4519	minPvs = 0;
4520	maxPvs = mMaxPvsSize;
4521	}
4522
4523	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4524	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4525
4526	SetValidity(minPvs, maxPvs);
4527
4528	// update valid view space according to valid view cells
4529	if (0) mVspBspTree->ValidateTree();
4530
4531	// area has to be recomputed
4532	mTotalAreaValid = false;
4533	VssRayContainer postProcessRays;
4534	GetRaySets(rays, mPostProcessSamples, postProcessRays);
4535
4536	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4537
4538	//////////
4539	//-- merge neighbouring view cells
4540	MergeViewCells(postProcessRays, objects);
4541
4542	// refines the merged view cells
4543	if (0) RefineViewCells(postProcessRays, objects);
4544
4545
4546	///////////
4547	//-- render simulation after merge + refine
4548
4549	cout << "\nview cells partition render time before compress" << endl << endl;;
4550	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4551	SimulationStatistics ss;
4552	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4553	cout << ss << endl;
4554
4555
4556	////////////
4557	//-- compression
4558
4559	if (ViewCellsTreeConstructed() && mCompressViewCells)
4560	{
4561	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4562	Debug << "number of entries before compress: " << pvsEntries << endl;
4563
4564	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
4565
4566	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4567	Debug << "number of entries after compress: " << pvsEntries << endl;
4568	}
4569
4570	// collapse sibling leaves that share the same view cell
4571	if (0) mVspBspTree->CollapseTree();
4572
4573	// recompute view cell list and statistics
4574	ResetViewCells();
4575
4576	// compute final meshes and volume / area
4577	if (1) FinalizeViewCells(true);
4578
4579	return 0;
4580	}
4581
4582
4583	int VspBspViewCellsManager::GetType() const
4584	{
4585	return VSP_BSP;
4586	}
4587
4588
4589	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4590	{
4591	// terminate recursion
4592	if (root->IsLeaf())
4593	{
4594	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
4595	leaf->GetViewCell()->SetMergeCost(0.0f);
4596	return leaf->GetViewCell();
4597	}
4598
4599
4600	BspInterior interior = dynamic_cast<BspInterior >(root);
4601	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4602
4603	// evaluate merge cost for priority traversal
4604	float mergeCost = 1.0f / (float)root->mTimeStamp;
4605	viewCellInterior->SetMergeCost(mergeCost);
4606
4607	float volume = 0;
4608
4609	BspNode *front = interior->GetFront();
4610	BspNode *back = interior->GetBack();
4611
4612
4613	ObjectPvs frontPvs, backPvs;
4614
4615	//-- recursivly compute child hierarchies
4616	ViewCell *backVc = ConstructSpatialMergeTree(back);
4617	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4618
4619
4620	viewCellInterior->SetupChildLink(backVc);
4621	viewCellInterior->SetupChildLink(frontVc);
4622
4623	volume += backVc->GetVolume();
4624	volume += frontVc->GetVolume();
4625
4626	viewCellInterior->SetVolume(volume);
4627
4628	return viewCellInterior;
4629	}
4630
4631
4632	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4633	{
4634	if (!ViewCellsConstructed())
4635	return ViewCellsManager::GetViewPoint(viewPoint);
4636
4637	// TODO: set reasonable limit
4638	const int limit = 20;
4639
4640	for (int i = 0; i < limit; ++ i)
4641	{
4642	viewPoint = mViewSpaceBox.GetRandomPoint();
4643	if (mVspBspTree->ViewPointValid(viewPoint))
4644	{
4645	return true;
4646	}
4647	}
4648
4649	Debug << "failed to find valid view point, taking " << viewPoint << endl;
4650	return false;
4651	}
4652
4653
4654	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4655	{
4656	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4657	// validy update in preprocessor for all managers)
4658	return ViewCellsManager::ViewPointValid(viewPoint);
4659
4660	// return mViewSpaceBox.IsInside(viewPoint) &&
4661	// mVspBspTree->ViewPointValid(viewPoint);
4662	}
4663
4664
4665	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4666	const VssRayContainer &sampleRays)
4667	{
4668	if (!ViewCellsConstructed())
4669	return;
4670
4671	VssRayContainer visRays;
4672	GetRaySets(sampleRays, mVisualizationSamples, visRays);
4673
4674	if (1)
4675	{
4676	//////////////////
4677	//-- export final view cell partition
4678
4679	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4680
4681	if (exporter)
4682	{
4683	cout << "exporting view cells after post process ... ";
4684	if (0)
4685	{ // export view space box
4686	exporter->SetWireframe();
4687	exporter->ExportBox(mViewSpaceBox);
4688	exporter->SetFilled();
4689	}
4690
4691	Material m;
4692	m.mDiffuseColor.r = 0.0f;
4693	m.mDiffuseColor.g = 0.5f;
4694	m.mDiffuseColor.b = 0.5f;
4695
4696	exporter->SetForcedMaterial(m);
4697
4698	if (1 && mExportGeometry)
4699	{
4700	exporter->ExportGeometry(objects);
4701	}
4702
4703	if (0 && mExportRays)
4704	{
4705	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4706	}
4707	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4708
4709	delete exporter;
4710	cout << "finished" << endl;
4711	}
4712	}
4713
4714	////////////////
4715	//-- visualization of the BSP splits
4716
4717	bool exportSplits = false;
4718	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4719
4720	if (exportSplits)
4721	{
4722	cout << "exporting splits ... ";
4723	ExportSplits(objects, visRays);
4724	cout << "finished" << endl;
4725	}
4726
4727	////////
4728	//-- export single view cells
4729
4730	int leafOut;
4731	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4732	const int raysOut = 100;
4733
4734	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
4735	}
4736
4737
4738	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
4739	const VssRayContainer &rays)
4740	{
4741	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4742
4743	if (exporter)
4744	{
4745	Material m;
4746	m.mDiffuseColor = RgbColor(1, 0, 0);
4747	exporter->SetForcedMaterial(m);
4748	exporter->SetWireframe();
4749
4750	exporter->ExportBspSplits(*mVspBspTree, true);
4751
4752	// take forced material, else big scenes cannot be viewed
4753	m.mDiffuseColor = RgbColor(0, 1, 0);
4754	exporter->SetForcedMaterial(m);
4755	exporter->SetFilled();
4756
4757	exporter->ResetForcedMaterial();
4758
4759	// export rays
4760	if (mExportRays)
4761	{
4762	exporter->ExportRays(rays, RgbColor(1, 1, 0));
4763	}
4764
4765	if (mExportGeometry)
4766	{
4767	exporter->ExportGeometry(objects);
4768	}
4769	delete exporter;
4770	}
4771	}
4772
4773
4774	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4775	const int maxViewCells,
4776	const bool sortViewCells,
4777	const bool exportPvs,
4778	const bool exportRays,
4779	const int maxRays,
4780	const string prefix,
4781	VssRayContainer *visRays)
4782	{
4783	if (sortViewCells)
4784	{
4785	// sort view cells to visualize the largest view cells
4786	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4787	}
4788
4789	//////////
4790	//-- some view cells for output
4791
4792	ViewCell::NewMail();
4793	const int limit = min(maxViewCells, (int)mViewCells.size());
4794
4795	for (int i = 0; i < limit; ++ i)
4796	{
4797	cout << "creating output for view cell " << i << " ... ";
4798
4799	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
4800	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
4801
4802	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
4803	continue;
4804
4805	vc->Mail();
4806
4807	ObjectPvs pvs;
4808	mViewCellsTree->GetPvs(vc, pvs);
4809
4810	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
4811	Exporter *exporter = Exporter::GetExporter(s);
4812
4813	const float pvsCost = mViewCellsTree->GetPvsCost(vc);
4814	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
4815
4816	if (exportRays)
4817	{
4818	////////////
4819	//-- export rays piercing this view cell
4820
4821	// take rays stored with the view cells during subdivision
4822	VssRayContainer vcRays;
4823	VssRayContainer collectRays;
4824
4825	// collect initial view cells
4826	ViewCellContainer leaves;
4827	mViewCellsTree->CollectLeaves(vc, leaves);
4828
4829	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4830	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4831	{
4832	BspLeaf vcLeaf = dynamic_cast<BspViewCell >(*vit)->mLeaves[0];
4833	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
4834
4835	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
4836	{
4837	collectRays.push_back(*rit);
4838	}
4839	}
4840
4841	const int raysOut = min((int)collectRays.size(), maxRays);
4842
4843	// prepare some rays for output
4844	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4845	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4846	{
4847	const float p = RandomValue(0.0f, (float)collectRays.size());
4848
4849	if (p < raysOut)
4850	{
4851	vcRays.push_back(*rit);
4852	}
4853	}
4854
4855	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
4856	}
4857
4858	////////////////
4859	//-- export view cell geometry
4860
4861	exporter->SetWireframe();
4862
4863	Material m;//= RandomMaterial();
4864	m.mDiffuseColor = RgbColor(0, 1, 0);
4865	exporter->SetForcedMaterial(m);
4866
4867	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4868	exporter->SetFilled();
4869
4870	if (exportPvs)
4871	{
4872	Intersectable::NewMail();
4873
4874	ObjectPvsIterator pit = pvs.GetIterator();
4875
4876	cout << endl;
4877
4878	// output PVS of view cell
4879	while (pit.HasMoreEntries())
4880	{
4881	ObjectPvsEntry entry = pit.Next();
4882	Intersectable *intersect = entry.mObject;
4883
4884	if (!intersect->Mailed())
4885	{
4886	intersect->Mail();
4887
4888	m = RandomMaterial();
4889	exporter->SetForcedMaterial(m);
4890	exporter->ExportIntersectable(intersect);
4891	}
4892	}
4893	cout << endl;
4894	}
4895
4896	DEL_PTR(exporter);
4897	cout << "finished" << endl;
4898	}
4899	}
4900
4901
4902	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
4903	{
4904	Exporter *exporter = Exporter::GetExporter("filter.x3d");
4905
4906	Vector3 bsize = mViewSpaceBox.Size();
4907	const Vector3 viewPoint(mViewSpaceBox.Center());
4908	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
4909	const Vector3 width = Vector3(w);
4910
4911	PrVs testPrVs;
4912
4913	if (exporter)
4914	{
4915	ViewCellContainer viewCells;
4916
4917	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
4918
4919	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
4920
4921	exporter->SetWireframe();
4922
4923	exporter->SetForcedMaterial(RgbColor(1,1,1));
4924	exporter->ExportBox(tbox);
4925
4926	exporter->SetFilled();
4927
4928	exporter->SetForcedMaterial(RgbColor(0,1,0));
4929	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
4930
4931	//exporter->ResetForcedMaterial();
4932	exporter->SetForcedMaterial(RgbColor(0,0,1));
4933	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
4934
4935	exporter->SetForcedMaterial(RgbColor(1,0,0));
4936	exporter->ExportGeometry(objects);
4937
4938	delete exporter;
4939	}
4940	}
4941
4942
4943	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
4944	ViewCellContainer &viewCells) const
4945	{
4946	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
4947	}
4948
4949
4950	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
4951	const Vector3 &termination,
4952	ViewCellContainer &viewcells)
4953	{
4954	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
4955	}
4956
4957
4958	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
4959	{
4960	int numSamples;
4961
4962	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
4963	cout << "samples" << numSamples << endl;
4964
4965	vector<RenderCostSample> samples;
4966
4967	if (!mPreprocessor->GetRenderer())
4968	return;
4969
4970	//start the view point queries
4971	long startTime = GetTime();
4972	cout << "starting sampling of render cost ... ";
4973
4974	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
4975
4976	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4977
4978
4979	// for each sample:
4980	// find view cells associated with the samples
4981	// store the sample pvs with the pvs associated with the view cell
4982	//
4983	// for each view cell:
4984	// compute difference point sampled pvs - view cell pvs
4985	// export geometry with color coded pvs difference
4986
4987	std::map<ViewCell *, ObjectPvs> sampleMap;
4988
4989	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
4990
4991	for (rit = samples.begin(); rit != rit_end; ++ rit)
4992	{
4993	RenderCostSample sample = *rit;
4994
4995	ViewCell *vc = GetViewCell(sample.mPosition);
4996
4997	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
4998
4999	if (it == sampleMap.end())
5000	{
5001	sampleMap[vc] = sample.mPvs;
5002	}
5003	else
5004	{
5005	(*it).second.MergeInPlace(sample.mPvs);
5006	}
5007	}
5008
5009	// visualize the view cells
5010	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5011
5012	Material m;//= RandomMaterial();
5013
5014	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5015	{
5016	ViewCell vc = (vit).first;
5017
5018	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5019	const int pvsPtSamples = (*vit).second.GetSize();
5020
5021	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5022	m.mDiffuseColor.b = 1.0f;
5023	//exporter->SetForcedMaterial(m);
5024	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5025
5026	/* // counting the pvss
5027	for (rit = samples.begin(); rit != rit_end; ++ rit)
5028	{
5029	RenderCostSample sample = *rit;
5030	ViewCell *vc = GetViewCell(sample.mPosition);
5031
5032	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5033	Mesh *hMesh = CreateMeshFromBox(box);
5034
5035	DEL_PTR(hMesh);
5036	}
5037	*/
5038	}
5039	}
5040
5041
5042	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5043	ViewCell *vc,
5044	const AxisAlignedBox3 *sceneBox,
5045	const AxisAlignedPlane *clipPlane
5046	) const
5047	{
5048	if (clipPlane)
5049	{
5050	const Plane3 plane = clipPlane->GetPlane();
5051
5052	ViewCellContainer leaves;
5053	mViewCellsTree->CollectLeaves(vc, leaves);
5054	ViewCellContainer::const_iterator it, it_end = leaves.end();
5055
5056	for (it = leaves.begin(); it != it_end; ++ it)
5057	{
5058	BspNodeGeometry geom;
5059	BspNodeGeometry front;
5060	BspNodeGeometry back;
5061
5062	mVspBspTree->ConstructGeometry(*it, geom);
5063
5064	const float eps = 0.0001f;
5065	const int cf = geom.Side(plane, eps);
5066
5067	if (cf == -1)
5068	{
5069	exporter->ExportPolygons(geom.GetPolys());
5070	}
5071	else if (cf == 0)
5072	{
5073	geom.SplitGeometry(front,
5074	back,
5075	plane,
5076	mViewSpaceBox,
5077	eps);
5078
5079	if (back.Valid())
5080	{
5081	exporter->ExportPolygons(back.GetPolys());
5082	}
5083	}
5084	}
5085	}
5086	else
5087	{
5088	// export mesh if available
5089	// TODO: some bug here?
5090	if (1 && vc->GetMesh())
5091	{
5092	exporter->ExportMesh(vc->GetMesh());
5093	}
5094	else
5095	{
5096	BspNodeGeometry geom;
5097	mVspBspTree->ConstructGeometry(vc, geom);
5098	exporter->ExportPolygons(geom.GetPolys());
5099	}
5100	}
5101	}
5102
5103
5104	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5105	{
5106	ViewCellContainer leaves;
5107	mViewCellsTree->CollectLeaves(vc, leaves);
5108
5109	int maxDist = 0;
5110
5111	// compute max height difference
5112	for (int i = 0; i < (int)leaves.size(); ++ i)
5113	{
5114	for (int j = 0; j < (int)leaves.size(); ++ j)
5115	{
5116	BspLeaf leaf = dynamic_cast<BspViewCell >(leaves[i])->mLeaves[0];
5117
5118	if (i != j)
5119	{
5120	BspLeaf leaf2 =dynamic_cast<BspViewCell >(leaves[j])->mLeaves[0];
5121	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5122
5123	if (dist > maxDist)
5124	maxDist = dist;
5125	}
5126	}
5127	}
5128
5129	return maxDist;
5130	}
5131
5132
5133	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5134	{
5135	if (!ViewCellsConstructed())
5136	return NULL;
5137
5138	if (!mViewSpaceBox.IsInside(point))
5139	return NULL;
5140
5141	return mVspBspTree->GetViewCell(point, active);
5142	}
5143
5144
5145	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5146	{
5147	BspNodeGeometry geom;
5148	mVspBspTree->ConstructGeometry(vc, geom);
5149
5150	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5151	IncludeNodeGeomInMesh(geom, *mesh);
5152
5153	vc->SetMesh(mesh);
5154	}
5155
5156
5157	int VspBspViewCellsManager::CastBeam(Beam &beam)
5158	{
5159	return mVspBspTree->CastBeam(beam);
5160	}
5161
5162
5163	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5164	const bool createMesh)
5165	{
5166	float area = 0;
5167	float volume = 0;
5168
5169	ViewCellContainer leaves;
5170	mViewCellsTree->CollectLeaves(viewCell, leaves);
5171
5172	ViewCellContainer::const_iterator it, it_end = leaves.end();
5173
5174	for (it = leaves.begin(); it != it_end; ++ it)
5175	{
5176	BspNodeGeometry geom;
5177	mVspBspTree->ConstructGeometry(*it, geom);
5178
5179	const float lVol = geom.GetVolume();
5180	const float lArea = geom.GetArea();
5181
5182	area += lArea;
5183	volume += lVol;
5184
5185	if (createMesh)
5186	CreateMesh(*it);
5187	}
5188
5189	viewCell->SetVolume(volume);
5190	viewCell->SetArea(area);
5191	}
5192
5193
5194	void VspBspViewCellsManager::TestSubdivision()
5195	{
5196	ViewCellContainer leaves;
5197	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5198
5199	ViewCellContainer::const_iterator it, it_end = leaves.end();
5200
5201	const float vol = mViewSpaceBox.GetVolume();
5202	float subdivVol = 0;
5203	float newVol = 0;
5204
5205	for (it = leaves.begin(); it != it_end; ++ it)
5206	{
5207	BspNodeGeometry geom;
5208	mVspBspTree->ConstructGeometry(*it, geom);
5209
5210	const float lVol = geom.GetVolume();
5211
5212	newVol += lVol;
5213	subdivVol += (*it)->GetVolume();
5214
5215	float thres = 0.9f;
5216	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5217	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5218	}
5219
5220	Debug << "exact volume: " << vol << endl;
5221	Debug << "subdivision volume: " << subdivVol << endl;
5222	Debug << "new volume: " << newVol << endl;
5223	}
5224
5225
5226	void VspBspViewCellsManager::PrepareLoadedViewCells()
5227	{
5228	// TODO: do I still need this here?
5229	if (0)
5230	mVspBspTree->RepairViewCellsLeafLists();
5231	}
5232
5233
5234
5235	/**************************************************************************/
5236	/* VspOspViewCellsManager implementation */
5237	/**************************************************************************/
5238
5239
5240	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5241	const string &hierarchyType)
5242	: ViewCellsManager(vcTree)
5243	{
5244	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5245
5246	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5247	mHierarchyManager->SetViewCellsManager(this);
5248	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5249	}
5250
5251
5252	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5253	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5254	{
5255	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5256
5257	mHierarchyManager->SetViewCellsManager(this);
5258	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5259	}
5260
5261
5262	Intersectable *
5263	VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
5264	{
5265	#if USE_KD_PVS
5266	return ViewCellsManager::GetIntersectable(ray, isTermination);
5267	#else
5268	return mHierarchyManager->GetIntersectable(ray, isTermination);
5269	#endif
5270	}
5271
5272
5273	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5274	{
5275	HierarchyManager *hierarchyManager;
5276
5277	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5278	{
5279	Debug << "hierarchy manager: osp" << endl;
5280	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5281	}
5282	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5283	{
5284	Debug << "hierarchy manager: bvh" << endl;
5285	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5286	}
5287	else // only view space partition
5288	{
5289	Debug << "hierarchy manager: obj" << endl;
5290	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5291	}
5292
5293	return hierarchyManager;
5294	}
5295
5296
5297	VspOspViewCellsManager::~VspOspViewCellsManager()
5298	{
5299	DEL_PTR(mHierarchyManager);
5300	}
5301
5302
5303	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5304	{
5305	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5306	}
5307
5308
5309	void VspOspViewCellsManager::CollectViewCells()
5310	{
5311	// view cells tree constructed
5312	if (!ViewCellsTreeConstructed())
5313	{
5314	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5315	}
5316	else
5317	{ // we can use the view cells tree hierarchy to get the right set
5318	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5319	}
5320	}
5321
5322
5323	bool VspOspViewCellsManager::ViewCellsConstructed() const
5324	{
5325	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5326	}
5327
5328
5329	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5330	{
5331	return new VspViewCell(mesh);
5332	}
5333
5334
5335	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5336	const VssRayContainer &rays)
5337	{
5338	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5339
5340	// skip rest if view cells were already constructed
5341	if (ViewCellsConstructed())
5342	return 0;
5343
5344	int sampleContributions = 0;
5345	VssRayContainer sampleRays;
5346
5347	int limit = min (mInitialSamples, (int)rays.size());
5348
5349	VssRayContainer constructionRays;
5350	VssRayContainer savedRays;
5351
5352	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5353	<< ", actual rays: " << (int)rays.size() << endl;
5354
5355	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5356
5357	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5358	Debug << "saved rays: " << (int)savedRays.size() << endl;
5359
5360	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5361
5362	#if TEST_EVALUATION
5363	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5364	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5365	{
5366	storedRays.push_back(new VssRay((tit)));
5367	}
5368	#endif
5369
5370	/////////////////////////
5371	//-- print satistics for subdivision and view cells
5372
5373	Debug << endl << endl << *mHierarchyManager << endl;
5374
5375	ResetViewCells();
5376	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5377
5378	//////////////
5379	//-- recast rest of rays
5380
5381	const long startTime = GetTime();
5382	cout << "Computing remaining ray contributions ... ";
5383
5384	if (SAMPLE_AFTER_SUBDIVISION)
5385	ComputeSampleContributions(savedRays, true, false);
5386
5387	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5388	<< " secs" << endl;
5389
5390	if (0)
5391	{ // real meshes are constructed at this stage
5392	cout << "finalizing view cells ... ";
5393	FinalizeViewCells(true);
5394	cout << "finished" << endl;
5395	}
5396
5397	return sampleContributions;
5398	}
5399
5400
5401	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5402	const VssRayContainer &rays)
5403	{
5404	if (!ViewCellsConstructed())
5405	{
5406	Debug << "postprocess error: no view cells constructed" << endl;
5407	return 0;
5408	}
5409
5410	// if view cells were already constructed before post processing step
5411	// (e.g., because they were loaded), we are finished
5412	if (mViewCellsFinished)
5413	{
5414	FinalizeViewCells(true);
5415	EvaluateViewCellsStats();
5416
5417	return 0;
5418	}
5419
5420	// check if new view cells turned invalid
5421	int minPvs, maxPvs;
5422
5423	if (0)
5424	{
5425	minPvs = mMinPvsSize;
5426	maxPvs = mMaxPvsSize;
5427	}
5428	else
5429	{
5430	// problem matt: why did I start here from zero?
5431	minPvs = 0;
5432	maxPvs = mMaxPvsSize;
5433	}
5434
5435	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5436	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5437
5438	SetValidity(minPvs, maxPvs);
5439
5440
5441	// area is not up to date, has to be recomputed
5442	mTotalAreaValid = false;
5443	VssRayContainer postProcessRays;
5444	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5445
5446	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5447
5448
5449	// compute tree by merging the nodes of the spatial hierarchy
5450	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5451	mViewCellsTree->SetRoot(root);
5452
5453	//////////////////////////
5454	//-- update pvs up to the root of the hierarchy
5455
5456	ObjectPvs pvs;
5457	UpdatePvsForEvaluation(root, pvs);
5458
5459
5460	//////////////////////
5461	//-- render simulation after merge + refine
5462
5463	cout << "\nview cells partition render time before compress" << endl << endl;
5464	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
5465	SimulationStatistics ss;
5466	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5467	cout << ss << endl;
5468
5469
5470	///////////
5471	//-- compression
5472
5473	if (ViewCellsTreeConstructed() && mCompressViewCells)
5474	{
5475	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
5476	Debug << "number of entries before compress: " << pvsEntries << endl;
5477
5478	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
5479
5480	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
5481	Debug << "number of entries after compress: " << pvsEntries << endl;
5482	}
5483
5484	/////////////
5485	//-- some tasks still to do on the view cells:
5486	//-- Compute meshes from view cell geometry, evaluate volume and / or area
5487
5488	if (1) FinalizeViewCells(true);
5489
5490	return 0;
5491	}
5492
5493
5494	int VspOspViewCellsManager::GetType() const
5495	{
5496	return VSP_OSP;
5497	}
5498
5499
5500	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5501	{
5502	// terminate recursion
5503	if (root->IsLeaf())
5504	{
5505	VspLeaf leaf = dynamic_cast<VspLeaf >(root);
5506	leaf->GetViewCell()->SetMergeCost(0.0f);
5507	return leaf->GetViewCell();
5508	}
5509
5510	VspInterior interior = dynamic_cast<VspInterior >(root);
5511	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5512
5513	// evaluate merge cost for priority traversal
5514	const float mergeCost = -(float)root->mTimeStamp;
5515	viewCellInterior->SetMergeCost(mergeCost);
5516
5517	float volume = 0;
5518
5519	VspNode *front = interior->GetFront();
5520	VspNode *back = interior->GetBack();
5521
5522	ObjectPvs frontPvs, backPvs;
5523
5524	/////////
5525	//-- recursivly compute child hierarchies
5526
5527	ViewCell *backVc = ConstructSpatialMergeTree(back);
5528	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5529
5530	viewCellInterior->SetupChildLink(backVc);
5531	viewCellInterior->SetupChildLink(frontVc);
5532
5533	volume += backVc->GetVolume();
5534	volume += frontVc->GetVolume();
5535
5536	viewCellInterior->SetVolume(volume);
5537
5538	return viewCellInterior;
5539	}
5540
5541
5542	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5543	{
5544	if (!ViewCellsConstructed())
5545	return ViewCellsManager::GetViewPoint(viewPoint);
5546
5547	// TODO: set reasonable limit
5548	const int limit = 20;
5549
5550	for (int i = 0; i < limit; ++ i)
5551	{
5552	viewPoint = mViewSpaceBox.GetRandomPoint();
5553
5554	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
5555	{
5556	return true;
5557	}
5558	}
5559
5560	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5561	return false;
5562	}
5563
5564
5565	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5566	ViewCell *vc,
5567	const AxisAlignedBox3 *sceneBox,
5568	const AxisAlignedPlane *clipPlane
5569	) const
5570	{
5571	ViewCellContainer leaves;
5572	mViewCellsTree->CollectLeaves(vc, leaves);
5573	ViewCellContainer::const_iterator it, it_end = leaves.end();
5574
5575	Plane3 plane;
5576	if (clipPlane)
5577	{
5578	// arbitrary plane definition
5579	plane = clipPlane->GetPlane();
5580	}
5581
5582	for (it = leaves.begin(); it != it_end; ++ it)
5583	{
5584	VspViewCell vspVc = dynamic_cast<VspViewCell >(*it);
5585	VspLeaf *l = vspVc->mLeaves[0];
5586
5587	const AxisAlignedBox3 box =
5588	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
5589
5590	if (sceneBox && !Overlap(*sceneBox, box))
5591	continue;
5592
5593	if (clipPlane)
5594	{
5595	if (box.Side(plane) == -1)
5596	{
5597	exporter->ExportBox(box);
5598	}
5599	else if (box.Side(plane) == 0)
5600	{
5601	// intersection
5602	AxisAlignedBox3 fbox, bbox;
5603	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5604	exporter->ExportBox(bbox);
5605	}
5606	}
5607	else
5608	{
5609	exporter->ExportBox(box);
5610	}
5611	}
5612	}
5613
5614
5615	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5616	{
5617	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5618	// validy update in preprocessor for all managers)
5619	return ViewCellsManager::ViewPointValid(viewPoint);
5620
5621	// return mViewSpaceBox.IsInside(viewPoint) &&
5622	// mVspTree->ViewPointValid(viewPoint);
5623	}
5624
5625
5626	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5627	const VssRayContainer &sampleRays)
5628	{
5629	if (!ViewCellsConstructed())
5630	return;
5631
5632	VssRayContainer visRays;
5633	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5634
5635	////////////
5636	//-- export final view cells
5637
5638	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5639
5640	//Vector3 scale(0.9f, 0.9f, 0.9f);
5641	Vector3 scale(1.0f, 1.0f, 1.0f);
5642
5643	if (exporter)
5644	{
5645	if (CLAMP_TO_BOX)
5646	{
5647	exporter->mClampToBox = true;
5648	}
5649
5650	EvaluateViewCellsStats();
5651
5652	const long starttime = GetTime();
5653	cout << "exporting final view cells (after initial construction + post process) ... ";
5654
5655	// matt: hack for clamping scene
5656	AxisAlignedBox3 bbox = mViewSpaceBox;
5657	bbox.Scale(scale);
5658
5659	if (1 && mExportRays)
5660	{
5661	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5662	}
5663
5664	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
5665	CLAMP_TO_BOX ? &bbox : NULL, false);
5666
5667	// hack color code (show pvs size)
5668	const int savedColorCode = mColorCode;
5669	mColorCode = 1; // export pvs
5670
5671	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
5672	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5673
5674	delete exporter;
5675
5676	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5677	mColorCode = savedColorCode;
5678	}
5679
5680	// export final object partition
5681	exporter = Exporter::GetExporter("final_object_partition.wrl");
5682
5683	if (exporter)
5684	{
5685	if (CLAMP_TO_BOX)
5686	{
5687	exporter->mClampToBox = true;
5688	}
5689
5690	const long starttime = GetTime();
5691
5692	// matt: hack for making visualization smaller in size
5693	AxisAlignedBox3 bbox = mHierarchyManager->GetObjectSpaceBox();
5694	bbox.Scale(scale);
5695
5696	cout << "exporting object space hierarchy ... ";
5697	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, CLAMP_TO_BOX ? &bbox : NULL);
5698
5699	delete exporter;
5700	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5701	}
5702
5703	// visualization of the view cells
5704	if (0)
5705	{
5706	ExportMergedViewCells(objects);
5707	}
5708
5709	// export some view cell
5710	int leafOut;
5711	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5712
5713	const bool sortViewCells = false;
5714	const bool exportPvs = true;
5715	const bool exportRays = true;
5716	const int raysOut = 100;
5717
5718	ExportSingleViewCells(objects,
5719	leafOut,
5720	sortViewCells,
5721	exportPvs,
5722	exportRays,
5723	raysOut,
5724	"");
5725	}
5726
5727
5728	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5729	const int maxViewCells,
5730	const bool sortViewCells,
5731	const bool exportPvs,
5732	const bool exportRays,
5733	const int maxRays,
5734	const string prefix,
5735	VssRayContainer *visRays)
5736	{
5737	if (sortViewCells)
5738	{
5739	// sort view cells to visualize the view cells with highest render cost
5740	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5741	}
5742
5743	ViewCell::NewMail();
5744	const int limit = min(maxViewCells, (int)mViewCells.size());
5745
5746	cout << "\nExporting " << limit << " single view cells: " << endl;
5747
5748	for (int i = 0; i < limit; ++ i)
5749	{
5750	cout << "creating output for view cell " << i << " ... ";
5751
5752	// largest view cell pvs first of random view cell
5753	ViewCell *vc = sortViewCells ?
5754	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
5755
5756	if (vc->Mailed()) // already used
5757	continue;
5758
5759	vc->Mail();
5760
5761	ObjectPvs pvs;
5762	mViewCellsTree->GetPvs(vc, pvs);
5763
5764	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5765	Exporter *exporter = Exporter::GetExporter(s);
5766
5767	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;
5768
5769	if (exportPvs)
5770	{
5771	Material m;
5772
5773	Intersectable::NewMail();
5774
5775	ObjectPvsIterator pit = pvs.GetIterator();
5776
5777	// output PVS of view cell
5778	while (pit.HasMoreEntries())
5779	{
5780	ObjectPvsEntry entry = pit.Next();
5781
5782	Intersectable *intersect = entry.mObject;
5783
5784	if (!intersect->Mailed())
5785	{
5786	m = RandomMaterial();
5787	exporter->SetForcedMaterial(m);
5788
5789	exporter->ExportIntersectable(intersect);
5790	intersect->Mail();
5791	}
5792	}
5793	}
5794
5795	if (exportRays)
5796	{
5797	////////////
5798	//-- export the sample rays
5799
5800	// output rays stored with the view cells during subdivision
5801	VssRayContainer vcRays;
5802	VssRayContainer collectRays;
5803
5804	// collect intial view cells
5805	ViewCellContainer leaves;
5806	mViewCellsTree->CollectLeaves(vc, leaves);
5807
5808	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5809
5810	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5811	{
5812	VspLeaf vcLeaf = dynamic_cast<VspViewCell >(*vit)->mLeaves[0];
5813	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5814
5815	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5816	{
5817	collectRays.push_back(*rit);
5818	}
5819	}
5820
5821	const int raysOut = min((int)collectRays.size(), maxRays);
5822
5823	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5824
5825	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5826	{
5827	const float p = RandomValue(0.0f, (float)collectRays.size());
5828
5829	if (p < raysOut)
5830	vcRays.push_back(*rit);
5831	}
5832
5833	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5834	}
5835
5836
5837	/////////////////
5838	//-- export view cell geometry
5839
5840	exporter->SetWireframe();
5841
5842	Material m;
5843	m.mDiffuseColor = RgbColor(0, 1, 0);
5844	exporter->SetForcedMaterial(m);
5845
5846	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5847	exporter->SetFilled();
5848
5849	DEL_PTR(exporter);
5850	cout << "finished" << endl;
5851	}
5852
5853	cout << endl;
5854	}
5855
5856
5857	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5858	ViewCellContainer &viewCells) const
5859	{
5860	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
5861	}
5862
5863
5864	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
5865	const Vector3 &termination,
5866	ViewCellContainer &viewcells)
5867	{
5868	return mHierarchyManager->GetVspTree()->CastLineSegment(origin, termination, viewcells);
5869	}
5870
5871
5872	bool VspOspViewCellsManager::ExportViewCells(const string filename,
5873	const bool exportPvs,
5874	const ObjectContainer &objects)
5875	{
5876	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
5877	return false;
5878
5879	const long starttime = GetTime();
5880	cout << "exporting view cells to xml ... ";
5881
5882	OUT_STREAM stream(filename.c_str());
5883
5884	// for output we need unique ids for each view cell
5885	CreateUniqueViewCellIds();
5886
5887	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
5888	stream << "<VisibilitySolution>" << endl;
5889
5890	if (exportPvs)
5891	{
5892	///////////////
5893	//-- export bounding boxes
5894	//-- The bounding boxes are used to identify
5895	//-- the objects in the rendering engine
5896	mHierarchyManager->ExportBoundingBoxes(stream, objects);
5897	}
5898
5899	//////////////////////////
5900	//-- export the view cells and the pvs
5901
5902	const int numViewCells = mCurrentViewCellsStats.viewCells;
5903
5904	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
5905	mViewCellsTree->Export(stream, exportPvs);
5906	stream << "</ViewCells>" << endl;
5907
5908	//////////////////////
5909	//-- export the view space hierarchy
5910
5911	stream << "<ViewSpaceHierarchy type=\"vsp\""
5912	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
5913	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
5914
5915	mHierarchyManager->GetVspTree()->Export(stream);
5916	stream << "</ViewSpaceHierarchy>" << endl;
5917
5918	//////////////////////
5919	//-- export the object space partition
5920
5921	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
5922
5923	stream << "</VisibilitySolution>" << endl;
5924	stream.close();
5925
5926	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
5927	return true;
5928	}
5929
5930
5931
5932	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
5933	const bool active) const
5934	{
5935	if (!ViewCellsConstructed())
5936	return NULL;
5937
5938	if (!mViewSpaceBox.IsInside(point))
5939	return NULL;
5940
5941	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
5942	}
5943
5944
5945	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
5946	{
5947	// matt: TODO
5948	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5949
5950	ViewCellContainer leaves;
5951	mViewCellsTree->CollectLeaves(vc, leaves);
5952
5953	ViewCellContainer::const_iterator it, it_end = leaves.end();
5954
5955	for (it = leaves.begin(); it != it_end; ++ it)
5956	{
5957	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaves[0];
5958	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5959	IncludeBoxInMesh(box, *mesh);
5960	}
5961
5962	vc->SetMesh(mesh);
5963	}
5964
5965
5966	int VspOspViewCellsManager::CastBeam(Beam &beam)
5967	{
5968	// matt: TODO
5969	return 0;
5970	}
5971
5972
5973	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
5974	{
5975	float area = 0;
5976	float volume = 0;
5977
5978	ViewCellContainer leaves;
5979	mViewCellsTree->CollectLeaves(viewCell, leaves);
5980
5981	ViewCellContainer::const_iterator it, it_end = leaves.end();
5982
5983	for (it = leaves.begin(); it != it_end; ++ it)
5984	{
5985	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaves[0];
5986
5987	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5988
5989	const float lVol = box.GetVolume();
5990	const float lArea = box.SurfaceArea();
5991
5992	area += lArea;
5993	volume += lVol;
5994
5995	CreateMesh(*it);
5996	}
5997
5998	viewCell->SetVolume(volume);
5999	viewCell->SetArea(area);
6000	}
6001
6002
6003	#define PVS_ADD_DIRTY 1
6004	float VspOspViewCellsManager::ComputeSampleContribution(VssRay &ray,
6005	const bool addRays,
6006	const bool storeViewCells)
6007	{
6008	ViewCellContainer viewcells;
6009
6010	ray.mPvsContribution = 0;
6011	ray.mRelativePvsContribution = 0.0f;
6012
6013	static Ray hray;
6014	hray.Init(ray);
6015	//hray.mFlags \|= Ray::CULL_BACKFACES;
6016	//Ray hray(ray);
6017
6018	// if (ray.mPdf!=1.0f)
6019	// cout<<ray.mPdf<<" ";
6020
6021	float tmin = 0, tmax = 1.0;
6022
6023	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
6024	return 0;
6025
6026	Vector3 origin = hray.Extrap(tmin);
6027	Vector3 termination = hray.Extrap(tmax);
6028
6029	ViewCell::NewMail();
6030
6031	// traverse the view space subdivision
6032	CastLineSegment(origin, termination, viewcells);
6033
6034	if (storeViewCells)
6035	{
6036	// copy viewcells memory efficiently
6037	ray.mViewCells.reserve(viewcells.size());
6038	ray.mViewCells = viewcells;
6039	}
6040
6041	ViewCellContainer::const_iterator it = viewcells.begin();
6042
6043	Intersectable *terminationObj = GetIntersectable(ray, true);
6044	Intersectable *originObj = GetIntersectable(ray, false);
6045
6046	for (; it != viewcells.end(); ++ it)
6047	{
6048	ViewCell viewcell = it;
6049
6050	if (viewcell->GetValid())
6051	{ // if ray not outside of view space
6052	float contribution;
6053
6054	if (terminationObj)
6055	{
6056	// todo: maybe not correct for kd node pvs
6057	if (viewcell->GetPvs().GetSampleContribution(
6058	terminationObj, ray.mPdf, contribution))
6059	{
6060	++ ray.mPvsContribution;
6061	}
6062
6063	ray.mRelativePvsContribution += contribution;
6064	}
6065
6066	////////////////
6067	//-- for directional sampling it is important to count
6068	//-- only contributions made in one direction!
6069	//-- the other contributions of this sample will be counted for the opposite ray!
6070
6071	#if SAMPLE_ORIGIN_OBJECTS
6072
6073	if (originObj &&
6074	viewcell->GetPvs().GetSampleContribution(originObj,
6075	ray.mPdf,
6076	contribution))
6077	{
6078	++ ray.mPvsContribution;
6079	ray.mRelativePvsContribution += contribution;
6080	}
6081	#endif
6082	}
6083	}
6084
6085	if (!addRays)
6086	{
6087	return ray.mRelativePvsContribution;
6088	}
6089
6090	// sampled objects are stored in the pvs
6091	for (it = viewcells.begin(); it != viewcells.end(); ++ it)
6092	{
6093	ViewCell viewCell = it;
6094
6095	if (!viewCell->GetValid())
6096	break;
6097
6098	//$$JB hack
6099
6100	#if PVS_ADD_DIRTY
6101	viewCell->GetPvs().AddSampleDirtyCheck(terminationObj, ray.mPdf);
6102	#else
6103	viewCell->GetPvs().AddSample(terminationObj, ray.mPdf);
6104	#endif
6105
6106	#if SAMPLE_ORIGIN_OBJECTS
6107	#if PVS_ADD_DIRTY
6108	viewCell->GetPvs().AddSampleDirtyCheck(originObj, ray.mPdf);
6109	#else
6110	viewCell->GetPvs().AddSample(originObj, ray.mPdf);
6111	#endif
6112	#endif
6113	if (viewCell->GetPvs().RequiresResort())
6114	{
6115	viewCell->GetPvs().Sort();
6116	}
6117	}
6118
6119	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
6120	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
6121	}
6122
6123
6124	void VspOspViewCellsManager::PrepareLoadedViewCells()
6125	{
6126	// TODO
6127	}
6128
6129
6130	ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
6131	ObjectContainer *objects,
6132	const bool finalizeViewCells,
6133	BoundingBoxConverter *bconverter)
6134
6135	{
6136	ViewCellsManager *vm =
6137	ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
6138	#if 0
6139	// insert scene objects in tree
6140	mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);
6141	#endif
6142	return vm;
6143	}
6144
6145	void
6146	VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
6147	{
6148	mHierarchyManager->CollectObjects(box, objects);
6149	}
6150
6151
6152	#if 1
6153
6154	void VspOspViewCellsManager::EvalViewCellPartition()
6155	{
6156	int samplesPerPass;
6157	int numSamples;
6158	int castSamples = 0;
6159	int oldSamples = 0;
6160	int samplesForStats;
6161	char statsPrefix[100];
6162	char suffix[100];
6163	int splitsStepSize;
6164
6165	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6166	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6167	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
6168	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6169	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6170
6171	Debug << "step size: " << splitsStepSize << endl;
6172	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6173	Debug << "view cell evaluation samples: " << numSamples << endl;
6174	Debug << "view cell stats prefix: " << statsPrefix << endl;
6175
6176	cout << "reseting pvs ... ";
6177
6178	// reset pvs and start over from zero
6179	mViewCellsTree->ResetPvs();
6180
6181	cout << "finished" << endl;
6182	cout << "Evaluating view cell partition ... " << endl;
6183
6184	vector<int> evalStrats;
6185
6186	// mix of sampling strategies
6187	if (0)
6188	{
6189	evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
6190	evalStrats.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
6191	evalStrats.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
6192
6193	Debug << "casting volume strategies" << endl;
6194	cout << "casting volume strategies" << endl;
6195	}
6196	else
6197	{
6198	//evalStrats.push_back(SamplingStrategy::VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6199	evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
6200
6201	// ratio 3:1
6202	evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6203	//evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6204	//evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6205
6206	Debug << "casting surface strategies" << endl;
6207	cout << "casting surface strategies" << endl;
6208	}
6209
6210	while (castSamples < numSamples)
6211	{
6212	///////////////
6213	//-- we have to use uniform sampling strategy for construction rays
6214
6215	VssRayContainer evaluationSamples;
6216	const int samplingType = mEvaluationSamplingType;
6217
6218	long startTime = GetTime();
6219
6220	cout << "casting " << samplesPerPass << " samples ... ";
6221	Debug << "casting " << samplesPerPass << " samples ... ";
6222
6223	CastPassSamples(samplesPerPass, evalStrats, evaluationSamples);
6224	//CastPassSamples(samplesPerPass, mStrategies, evaluationSamples);
6225
6226	castSamples += samplesPerPass;
6227
6228	Real timeDiff = TimeDiff(startTime, GetTime());
6229
6230	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6231	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6232
6233	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6234	Debug << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6235
6236	startTime = GetTime();
6237
6238	ComputeSampleContributions(evaluationSamples, true, false);
6239
6240	timeDiff = TimeDiff(startTime, GetTime());
6241	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6242	Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6243
6244	if ((castSamples >= samplesForStats + oldSamples) \|\|
6245	(castSamples >= numSamples))
6246	{
6247	oldSamples += samplesForStats;
6248
6249	///////////
6250	//-- output stats
6251
6252	sprintf(suffix, "-%09d-eval.log", castSamples);
6253	const string filename = string(statsPrefix) + string(suffix);
6254
6255	startTime = GetTime();
6256
6257	cout << "compute new statistics ... " << endl;
6258
6259	ofstream ofstr(filename.c_str());
6260	mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false);
6261
6262	timeDiff = TimeDiff(startTime, GetTime());
6263	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6264	cout << "*************************************" << endl;
6265
6266	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6267
6268	#if 0
6269	//////////////
6270	// filtered stats
6271
6272	sprintf(suffix, "-%09d-eval-filter.log", castSamples);
6273	const string filename2 = string(statsPrefix) + string(suffix);
6274
6275	startTime = GetTime();
6276
6277	cout << "compute new statistics for filtered pvs ... " << endl;
6278
6279	ofstream ofstr2(filename2.c_str());
6280	mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);
6281
6282	timeDiff = TimeDiff(startTime, GetTime());
6283	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6284	cout << "*************************************" << endl;
6285	Debug << "filtered statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6286	#endif
6287
6288	// only for debugging purpose
6289	if (0)
6290	{
6291	ViewCellContainer viewCells;
6292	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);
6293
6294	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
6295	int pvsSize = 0;
6296
6297	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
6298	{
6299	pvsSize += (*vit)->GetPvs().GetSize();
6300	}
6301
6302	cout << "debug entries: " << pvsSize << ", memcost: "
6303	<< (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
6304	}
6305	}
6306
6307	disposeRays(evaluationSamples, NULL);
6308	}
6309
6310	}
6311	#endif
6312
6313
6314
6315	}

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

Download in other formats: