Context Navigation

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

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

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

Download in other formats: