Context Navigation

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

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

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

Download in other formats: