Context Navigation

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

Revision 1924, 162.5 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include "ViewCellsManager.h"
2	#include "RenderSimulator.h"
3	#include "Mesh.h"
4	#include "Triangle3.h"
5	#include "ViewCell.h"
6	#include "Environment.h"
7	#include "X3dParser.h"
8	#include "ViewCellBsp.h"
9	#include "KdTree.h"
10	#include "HierarchyManager.h"
11	#include "Exporter.h"
12	#include "VspBspTree.h"
13	#include "ViewCellsParser.h"
14	#include "Beam.h"
15	#include "VssPreprocessor.h"
16	#include "RssPreprocessor.h"
17	#include "BoundingBoxConverter.h"
18	#include "GlRenderer.h"
19	#include "ResourceManager.h"
20	#include "IntersectableWrapper.h"
21	#include "VspTree.h"
22	#include "OspTree.h"
23	#include "BvHierarchy.h"
24	#include "SamplingStrategy.h"
25	#include "SceneGraph.h"
26
27
28	// $$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	vcRays.push_back(*rit);
3530	}
3531	else if ((*rit)->mFlags & VssRay::ReverseSample)
3532	vcRays2.push_back(*rit);
3533	else
3534	vcRays3.push_back(*rit);
3535
3536	}
3537	}
3538
3539	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
3540	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
3541	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
3542	}
3543
3544	////////////////
3545	//-- export view cell geometry
3546
3547	exporter->SetWireframe();
3548
3549	Material m;//= RandomMaterial();
3550	m.mDiffuseColor = RgbColor(0, 1, 0);
3551	exporter->SetForcedMaterial(m);
3552
3553	ExportViewCellGeometry(exporter, vc, NULL, NULL);
3554	exporter->SetFilled();
3555
3556	if (exportPvs)
3557	{
3558	Intersectable::NewMail();
3559	ObjectPvsIterator pit = pvs.GetIterator();
3560
3561	while (pit.HasMoreEntries())
3562	{
3563	ObjectPvsEntry entry = pit.Next();
3564
3565	// output PVS of view cell
3566	Intersectable *intersect = entry.mObject;
3567
3568	if (!intersect->Mailed())
3569	{
3570	intersect->Mail();
3571
3572	m = RandomMaterial();
3573	exporter->SetForcedMaterial(m);
3574	exporter->ExportIntersectable(intersect);
3575	}
3576	}
3577	cout << endl;
3578	}
3579
3580	DEL_PTR(exporter);
3581	cout << "finished" << endl;
3582	}
3583	}
3584
3585
3586	void BspViewCellsManager::TestSubdivision()
3587	{
3588	ViewCellContainer leaves;
3589	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
3590
3591	ViewCellContainer::const_iterator it, it_end = leaves.end();
3592
3593	const float vol = mViewSpaceBox.GetVolume();
3594	float subdivVol = 0;
3595	float newVol = 0;
3596
3597	for (it = leaves.begin(); it != it_end; ++ it)
3598	{
3599	BspNodeGeometry geom;
3600	mBspTree->ConstructGeometry(*it, geom);
3601
3602	const float lVol = geom.GetVolume();
3603	newVol += lVol;
3604	subdivVol += (*it)->GetVolume();
3605
3606	const float thres = 0.9f;
3607	if ((lVol < ((it)->GetVolume() thres)) \|\|
3608	(lVol * thres > ((*it)->GetVolume())))
3609	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
3610	}
3611
3612	Debug << "exact volume: " << vol << endl;
3613	Debug << "subdivision volume: " << subdivVol << endl;
3614	Debug << "new volume: " << newVol << endl;
3615	}
3616
3617
3618	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3619	ViewCell *vc,
3620	const AxisAlignedBox3 *sceneBox,
3621	const AxisAlignedPlane *clipPlane
3622	) const
3623	{
3624	if (clipPlane)
3625	{
3626	const Plane3 plane = clipPlane->GetPlane();
3627
3628	ViewCellContainer leaves;
3629	mViewCellsTree->CollectLeaves(vc, leaves);
3630	ViewCellContainer::const_iterator it, it_end = leaves.end();
3631
3632	for (it = leaves.begin(); it != it_end; ++ it)
3633	{
3634	BspNodeGeometry geom;
3635	BspNodeGeometry front;
3636	BspNodeGeometry back;
3637
3638	mBspTree->ConstructGeometry(*it, geom);
3639
3640	const float eps = 0.0001f;
3641	const int cf = geom.Side(plane, eps);
3642
3643	if (cf == -1)
3644	{
3645	exporter->ExportPolygons(geom.GetPolys());
3646	}
3647	else if (cf == 0)
3648	{
3649	geom.SplitGeometry(front,
3650	back,
3651	plane,
3652	mViewSpaceBox,
3653	eps);
3654
3655	if (back.Valid())
3656	{
3657	exporter->ExportPolygons(back.GetPolys());
3658	}
3659	}
3660	}
3661	}
3662	else
3663	{
3664	// export mesh if available
3665	// TODO: some bug here?
3666	if (1 && vc->GetMesh())
3667	{
3668	exporter->ExportMesh(vc->GetMesh());
3669	}
3670	else
3671	{
3672	BspNodeGeometry geom;
3673	mBspTree->ConstructGeometry(vc, geom);
3674	exporter->ExportPolygons(geom.GetPolys());
3675	}
3676	}
3677	}
3678
3679
3680	void BspViewCellsManager::CreateMesh(ViewCell *vc)
3681	{
3682	// note: should previous mesh be deleted (via mesh manager?)
3683	BspNodeGeometry geom;
3684	mBspTree->ConstructGeometry(vc, geom);
3685
3686	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
3687
3688	IncludeNodeGeomInMesh(geom, *mesh);
3689	vc->SetMesh(mesh);
3690	}
3691
3692
3693	void BspViewCellsManager::Finalize(ViewCell *viewCell,
3694	const bool createMesh)
3695	{
3696	float area = 0;
3697	float volume = 0;
3698
3699	ViewCellContainer leaves;
3700	mViewCellsTree->CollectLeaves(viewCell, leaves);
3701
3702	ViewCellContainer::const_iterator it, it_end = leaves.end();
3703
3704	for (it = leaves.begin(); it != it_end; ++ it)
3705	{
3706	BspNodeGeometry geom;
3707
3708	mBspTree->ConstructGeometry(*it, geom);
3709
3710	const float lVol = geom.GetVolume();
3711	const float lArea = geom.GetArea();
3712
3713	area += lArea;
3714	volume += lVol;
3715
3716	CreateMesh(*it);
3717	}
3718
3719	viewCell->SetVolume(volume);
3720	viewCell->SetArea(area);
3721	}
3722
3723
3724	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
3725	{
3726	if (!ViewCellsConstructed())
3727	{
3728	return NULL;
3729	}
3730	if (!mViewSpaceBox.IsInside(point))
3731	{
3732	return NULL;
3733	}
3734	return mBspTree->GetViewCell(point);
3735	}
3736
3737
3738	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3739	vector<MergeCandidate> &candidates)
3740	{
3741	cout << "collecting merge candidates ... " << endl;
3742
3743	if (mUseRaysForMerge)
3744	{
3745	mBspTree->CollectMergeCandidates(rays, candidates);
3746	}
3747	else
3748	{
3749	vector<BspLeaf *> leaves;
3750	mBspTree->CollectLeaves(leaves);
3751	mBspTree->CollectMergeCandidates(leaves, candidates);
3752	}
3753
3754	cout << "fininshed collecting candidates" << endl;
3755	}
3756
3757
3758
3759	bool BspViewCellsManager::ExportViewCells(const string filename,
3760	const bool exportPvs,
3761	const ObjectContainer &objects)
3762	{
3763	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
3764	{
3765	return false;
3766	}
3767
3768	cout << "exporting view cells to xml ... ";
3769
3770	OUT_STREAM stream(filename.c_str());
3771
3772	// for output we need unique ids for each view cell
3773	CreateUniqueViewCellIds();
3774
3775	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3776	stream << "<VisibilitySolution>" << endl;
3777
3778	if (exportPvs)
3779	{
3780	//////////
3781	//-- export bounding boxes: they are used to identify the objects from the pvs and
3782	//-- assign them to the entities in the rendering engine
3783
3784	stream << "<BoundingBoxes>" << endl;
3785	ObjectContainer::const_iterator oit, oit_end = objects.end();
3786
3787	for (oit = objects.begin(); oit != oit_end; ++ oit)
3788	{
3789	const AxisAlignedBox3 box = (*oit)->GetBox();
3790
3791	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
3792	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
3793	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
3794	}
3795
3796	stream << "</BoundingBoxes>" << endl;
3797	}
3798
3799	///////////
3800	//-- export the view cells and the pvs
3801
3802	const int numViewCells = mCurrentViewCellsStats.viewCells;
3803	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
3804
3805	mViewCellsTree->Export(stream, exportPvs);
3806
3807	stream << "</ViewCells>" << endl;
3808
3809	/////////////
3810	//-- export the view space hierarchy
3811	stream << "<ViewSpaceHierarchy type=\"bsp\""
3812	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3813	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
3814
3815	mBspTree->Export(stream);
3816
3817	// end tags
3818	stream << "</ViewSpaceHierarchy>" << endl;
3819	stream << "</VisibilitySolution>" << endl;
3820
3821	stream.close();
3822	cout << "finished" << endl;
3823
3824	return true;
3825	}
3826
3827
3828	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
3829	{
3830	ViewCellInterior *vcRoot = new ViewCellInterior();
3831
3832	// evaluate merge cost for priority traversal
3833	const float mergeCost = -(float)root->mTimeStamp;
3834	vcRoot->SetMergeCost(mergeCost);
3835
3836	float volume = 0;
3837	vector<BspLeaf *> leaves;
3838	mBspTree->CollectLeaves(leaves);
3839	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
3840	ViewCell::NewMail();
3841
3842	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3843	{
3844	BspLeaf leaf = lit;
3845	ViewCell *vc = leaf->GetViewCell();
3846
3847	if (!vc->Mailed())
3848	{
3849	vc->Mail();
3850	vc->SetMergeCost(0.0f);
3851	vcRoot->SetupChildLink(vc);
3852
3853	volume += vc->GetVolume();
3854	volume += vc->GetVolume();
3855	vcRoot->SetVolume(volume);
3856	}
3857	}
3858
3859	return vcRoot;
3860	}
3861
3862
3863	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
3864	{
3865	// terminate recursion
3866	if (root->IsLeaf())
3867	{
3868	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
3869	leaf->GetViewCell()->SetMergeCost(0.0f);
3870	return leaf->GetViewCell();
3871	}
3872
3873	BspInterior interior = dynamic_cast<BspInterior >(root);
3874	ViewCellInterior *viewCellInterior = new ViewCellInterior();
3875
3876	// evaluate merge cost for priority traversal
3877	const float mergeCost = -(float)root->mTimeStamp;
3878	viewCellInterior->SetMergeCost(mergeCost);
3879
3880	float volume = 0;
3881
3882	BspNode *front = interior->GetFront();
3883	BspNode *back = interior->GetBack();
3884
3885
3886	////////////
3887	//-- recursivly compute child hierarchies
3888
3889	ViewCell *backVc = ConstructSpatialMergeTree(back);
3890	ViewCell *frontVc = ConstructSpatialMergeTree(front);
3891
3892	viewCellInterior->SetupChildLink(backVc);
3893	viewCellInterior->SetupChildLink(frontVc);
3894
3895	volume += backVc->GetVolume();
3896	volume += frontVc->GetVolume();
3897
3898	viewCellInterior->SetVolume(volume);
3899
3900	return viewCellInterior;
3901	}
3902
3903
3904	/************************************************************************/
3905	/* KdViewCellsManager implementation */
3906	/************************************************************************/
3907
3908
3909
3910	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
3911	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
3912	{
3913	}
3914
3915
3916	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
3917	{
3918	// compute view cell area / volume as subsititute for probability
3919	if (0)
3920	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
3921	else
3922	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3923	}
3924
3925
3926
3927
3928	void KdViewCellsManager::CollectViewCells()
3929	{
3930	//mKdTree->CollectViewCells(mViewCells); TODO
3931	}
3932
3933
3934	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3935	const VssRayContainer &rays)
3936	{
3937	// if view cells already constructed
3938	if (ViewCellsConstructed())
3939	return 0;
3940
3941	mKdTree->Construct();
3942
3943	mTotalAreaValid = false;
3944	// create the view cells
3945	mKdTree->CreateAndCollectViewCells(mViewCells);
3946	// cast rays
3947	ComputeSampleContributions(rays, true, false);
3948
3949	EvaluateViewCellsStats();
3950	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3951
3952	return 0;
3953	}
3954
3955
3956	bool KdViewCellsManager::ViewCellsConstructed() const
3957	{
3958	return mKdTree->GetRoot() != NULL;
3959	}
3960
3961
3962	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
3963	const VssRayContainer &rays)
3964	{
3965	return 0;
3966	}
3967
3968
3969	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3970	const int maxViewCells,
3971	const bool sortViewCells,
3972	const bool exportPvs,
3973	const bool exportRays,
3974	const int maxRays,
3975	const string prefix,
3976	VssRayContainer *visRays)
3977	{
3978	// TODO
3979	}
3980
3981
3982	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
3983	const VssRayContainer &sampleRays)
3984	{
3985	if (!ViewCellsConstructed())
3986	return;
3987
3988	// using view cells instead of the kd PVS of objects
3989	const bool useViewCells = true;
3990	bool exportRays = false;
3991
3992	int limit = min(mVisualizationSamples, (int)sampleRays.size());
3993	const int pvsOut = min((int)objects.size(), 10);
3994	VssRayContainer *rays = new VssRayContainer[pvsOut];
3995
3996	if (useViewCells)
3997	{
3998	const int leafOut = 10;
3999
4000	ViewCell::NewMail();
4001
4002	//-- some rays for output
4003	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4004	Debug << "visualization using " << raysOut << " samples" << endl;
4005
4006	//-- some random view cells and rays for output
4007	vector<KdLeaf *> kdLeaves;
4008
4009	for (int i = 0; i < leafOut; ++ i)
4010	kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4011
4012	for (int i = 0; i < kdLeaves.size(); ++ i)
4013	{
4014	KdLeaf *leaf = kdLeaves[i];
4015	RayContainer vcRays;
4016
4017	cout << "creating output for view cell " << i << " ... ";
4018	#if 0
4019	// check whether we can add the current ray to the output rays
4020	for (int k = 0; k < raysOut; ++ k)
4021	{
4022	Ray *ray = sampleRays[k];
4023
4024	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4025	{
4026	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4027
4028	if (leaf->GetViewCell() == leaf2->GetViewCell())
4029	{
4030	vcRays.push_back(ray);
4031	}
4032	}
4033	}
4034	#endif
4035	Intersectable::NewMail();
4036
4037	ViewCell *vc = leaf->mViewCell;
4038	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4039
4040	Exporter *exporter = Exporter::GetExporter(str);
4041	exporter->SetFilled();
4042
4043	exporter->SetWireframe();
4044	//exporter->SetFilled();
4045
4046	Material m;//= RandomMaterial();
4047	m.mDiffuseColor = RgbColor(1, 1, 0);
4048	exporter->SetForcedMaterial(m);
4049
4050	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4051	exporter->ExportBox(box);
4052
4053	// export rays piercing this view cell
4054	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4055
4056	m.mDiffuseColor = RgbColor(1, 0, 0);
4057	exporter->SetForcedMaterial(m);
4058
4059	// exporter->SetWireframe();
4060	exporter->SetFilled();
4061
4062	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4063
4064	while (pit.HasMoreEntries())
4065	{
4066	ObjectPvsEntry entry = pit.Next();
4067
4068	//-- output PVS of view cell
4069	Intersectable *intersect = entry.mObject;
4070	if (!intersect->Mailed())
4071	{
4072	exporter->ExportIntersectable(intersect);
4073	intersect->Mail();
4074	}
4075	}
4076
4077	DEL_PTR(exporter);
4078	cout << "finished" << endl;
4079	}
4080
4081	DEL_PTR(rays);
4082	}
4083	else // using kd PVS of objects
4084	{
4085	for (int i = 0; i < limit; ++ i)
4086	{
4087	VssRay *ray = sampleRays[i];
4088
4089	// check whether we can add this to the rays
4090	for (int j = 0; j < pvsOut; j++)
4091	{
4092	if (objects[j] == ray->mTerminationObject)
4093	{
4094	rays[j].push_back(ray);
4095	}
4096	}
4097	}
4098
4099	if (exportRays)
4100	{
4101	Exporter *exporter = NULL;
4102	exporter = Exporter::GetExporter("sample-rays.x3d");
4103	exporter->SetWireframe();
4104	exporter->ExportKdTree(*mKdTree);
4105
4106	for (int i = 0; i < pvsOut; i++)
4107	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4108
4109	exporter->SetFilled();
4110	delete exporter;
4111	}
4112
4113	for (int k=0; k < pvsOut; k++)
4114	{
4115	Intersectable *object = objects[k];
4116	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4117
4118	Exporter *exporter = Exporter::GetExporter(str);
4119	exporter->SetWireframe();
4120
4121	// matt: no kd pvs
4122	/*
4123	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4124	Intersectable::NewMail();
4125
4126	// avoid adding the object to the list
4127	object->Mail();
4128	ObjectContainer visibleObjects;
4129
4130	for (; kit != object->mKdPvs.mEntries.end(); i++)
4131	{
4132	KdNode node = (kit).first;
4133	exporter->ExportBox(mKdTree->GetBox(node));
4134
4135	mKdTree->CollectObjects(node, visibleObjects);
4136	}
4137
4138	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4139	exporter->SetFilled();
4140
4141	for (int j = 0; j < visibleObjects.size(); j++)
4142	exporter->ExportIntersectable(visibleObjects[j]);
4143
4144	Material m;
4145	m.mDiffuseColor = RgbColor(1, 0, 0);
4146	exporter->SetForcedMaterial(m);
4147	exporter->ExportIntersectable(object);
4148	*/
4149	delete exporter;
4150	}
4151	}
4152	}
4153
4154
4155	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4156	{
4157	return new KdViewCell(mesh);
4158	}
4159
4160
4161	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4162	ViewCell *vc,
4163	const AxisAlignedBox3 *sceneBox,
4164	const AxisAlignedPlane *clipPlane
4165	) const
4166	{
4167	ViewCellContainer leaves;
4168	mViewCellsTree->CollectLeaves(vc, leaves);
4169	ViewCellContainer::const_iterator it, it_end = leaves.end();
4170
4171	for (it = leaves.begin(); it != it_end; ++ it)
4172	{
4173	KdViewCell kdVc = dynamic_cast<KdViewCell >(*it);
4174	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4175	}
4176	}
4177
4178
4179	int KdViewCellsManager::GetType() const
4180	{
4181	return ViewCellsManager::KD;
4182	}
4183
4184
4185
4186	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4187	{
4188	KdNode *node = leaf;
4189
4190	while (node->mParent && node->mDepth > mKdPvsDepth)
4191	node = node->mParent;
4192
4193	return node;
4194	}
4195
4196	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4197	const Vector3 &termination,
4198	ViewCellContainer &viewcells)
4199	{
4200	return mKdTree->CastLineSegment(origin, termination, viewcells);
4201	}
4202
4203
4204	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4205	{
4206	// TODO
4207	}
4208
4209
4210
4211	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4212	vector<MergeCandidate> &candidates)
4213	{
4214	// TODO
4215	}
4216
4217
4218
4219	/**************************************************************************/
4220	/* VspBspViewCellsManager implementation */
4221	/**************************************************************************/
4222
4223
4224	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4225	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4226	{
4227	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4228	mVspBspTree->SetViewCellsManager(this);
4229	mVspBspTree->mViewCellsTree = mViewCellsTree;
4230	}
4231
4232
4233	VspBspViewCellsManager::~VspBspViewCellsManager()
4234	{
4235	}
4236
4237
4238	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4239	{
4240	if (0 && mVspBspTree->mUseAreaForPvs)
4241	return GetArea(viewCell) / GetAccVcArea();
4242	else
4243	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4244	}
4245
4246
4247	void VspBspViewCellsManager::CollectViewCells()
4248	{
4249	// view cells tree constructed?
4250	if (!ViewCellsTreeConstructed())
4251	{
4252	mVspBspTree->CollectViewCells(mViewCells, false);
4253	}
4254	else
4255	{
4256	// we can use the view cells tree hierarchy to get the right set
4257	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4258	}
4259	}
4260
4261
4262	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4263	vector<MergeCandidate> &candidates)
4264	{
4265	cout << "collecting merge candidates ... " << endl;
4266
4267	if (mUseRaysForMerge)
4268	{
4269	mVspBspTree->CollectMergeCandidates(rays, candidates);
4270	}
4271	else
4272	{
4273	vector<BspLeaf *> leaves;
4274	mVspBspTree->CollectLeaves(leaves);
4275
4276	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4277	}
4278
4279	cout << "fininshed collecting candidates" << endl;
4280	}
4281
4282
4283	bool VspBspViewCellsManager::ViewCellsConstructed() const
4284	{
4285	return mVspBspTree->GetRoot() != NULL;
4286	}
4287
4288
4289	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4290	{
4291	return new BspViewCell(mesh);
4292	}
4293
4294
4295	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4296	const VssRayContainer &rays)
4297	{
4298	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4299
4300	// if view cells were already constructed
4301	if (ViewCellsConstructed())
4302	{
4303	return 0;
4304	}
4305
4306	int sampleContributions = 0;
4307	VssRayContainer sampleRays;
4308
4309	const int limit = min(mInitialSamples, (int)rays.size());
4310
4311	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4312	<< ", actual rays: " << (int)rays.size() << endl;
4313
4314	VssRayContainer savedRays;
4315
4316	if (SAMPLE_AFTER_SUBDIVISION)
4317	{
4318	VssRayContainer constructionRays;
4319
4320	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4321
4322	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4323	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4324
4325	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4326	}
4327	else
4328	{
4329	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4330	mVspBspTree->Construct(rays, &mViewSpaceBox);
4331	}
4332
4333	// collapse invalid regions
4334	cout << "collapsing invalid tree regions ... ";
4335	long startTime = GetTime();
4336
4337	const int collapsedLeaves = mVspBspTree->CollapseTree();
4338	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4339	<< " seconds" << endl;
4340
4341	cout << "finished" << endl;
4342
4343	/////////////////
4344	//-- stats after construction
4345
4346	Debug << mVspBspTree->GetStatistics() << endl;
4347
4348	ResetViewCells();
4349	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4350
4351
4352	//////////////////////
4353	//-- recast the rest of the rays
4354
4355	startTime = GetTime();
4356
4357	cout << "Computing remaining ray contributions ... ";
4358
4359	if (SAMPLE_AFTER_SUBDIVISION)
4360	ComputeSampleContributions(savedRays, true, false);
4361
4362	cout << "finished" << endl;
4363
4364	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4365	<< " secs" << endl;
4366
4367	cout << "construction finished" << endl;
4368
4369	if (0)
4370	{ ////////
4371	//-- real meshes are contructed at this stage
4372
4373	cout << "finalizing view cells ... ";
4374	FinalizeViewCells(true);
4375	cout << "finished" << endl;
4376	}
4377
4378	return sampleContributions;
4379	}
4380
4381
4382	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4383	const ObjectContainer &objects)
4384	{
4385	int vcSize = 0;
4386	int pvsSize = 0;
4387
4388	//-- merge view cells
4389	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4390	long startTime = GetTime();
4391
4392
4393	if (mMergeViewCells)
4394	{
4395	// TODO: should be done BEFORE the ray casting
4396	// compute tree by merging the nodes based on cost heuristics
4397	mViewCellsTree->ConstructMergeTree(rays, objects);
4398	}
4399	else
4400	{
4401	// compute tree by merging the nodes of the spatial hierarchy
4402	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4403	mViewCellsTree->SetRoot(root);
4404
4405	// compute pvs
4406	ObjectPvs pvs;
4407	UpdatePvsForEvaluation(root, pvs);
4408	}
4409
4410	if (1)
4411	{
4412	char mstats[100];
4413	ObjectPvs pvs;
4414
4415	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4416	mViewCellsTree->ExportStats(mstats);
4417	}
4418
4419	cout << "merged view cells in "
4420	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4421
4422	Debug << "Postprocessing: Merged view cells in "
4423	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4424
4425
4426	//////////////////
4427	//-- stats and visualizations
4428
4429	int savedColorCode = mColorCode;
4430
4431	// get currently active view cell set
4432	ResetViewCells();
4433	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4434
4435	if (mShowVisualization) // export merged view cells
4436	{
4437	mColorCode = 0;
4438	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4439
4440	cout << "exporting view cells after merge ... ";
4441
4442	if (exporter)
4443	{
4444	if (0)
4445	exporter->SetWireframe();
4446	else
4447	exporter->SetFilled();
4448
4449	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4450
4451	if (mExportGeometry)
4452	{
4453	Material m;
4454	m.mDiffuseColor = RgbColor(0, 1, 0);
4455	exporter->SetForcedMaterial(m);
4456	exporter->SetFilled();
4457
4458	exporter->ExportGeometry(objects);
4459	}
4460
4461	delete exporter;
4462	}
4463	cout << "finished" << endl;
4464	}
4465
4466	if (mShowVisualization)
4467	{
4468	// use pvs size for color coding
4469	mColorCode = 1;
4470	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
4471
4472	cout << "exporting view cells after merge (pvs size) ... ";
4473
4474	if (exporter)
4475	{
4476	exporter->SetFilled();
4477
4478	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4479
4480	if (mExportGeometry)
4481	{
4482	Material m;
4483	m.mDiffuseColor = RgbColor(0, 1, 0);
4484	exporter->SetForcedMaterial(m);
4485	exporter->SetFilled();
4486
4487	exporter->ExportGeometry(objects);
4488	}
4489
4490	delete exporter;
4491	}
4492	cout << "finished" << endl;
4493	}
4494
4495	mColorCode = savedColorCode;
4496	}
4497
4498
4499	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4500	const ObjectContainer &objects)
4501	{
4502	mRenderer->RenderScene();
4503
4504	SimulationStatistics ss;
4505	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4506	Debug << "render time before refine\n\n" << ss << endl;
4507
4508	const long startTime = GetTime();
4509	cout << "Refining the merged view cells ... ";
4510
4511	// refining the merged view cells
4512	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4513
4514	//-- stats and visualizations
4515	cout << "finished" << endl;
4516	cout << "refined " << refined << " view cells in "
4517	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4518
4519	Debug << "Postprocessing: refined " << refined << " view cells in "
4520	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4521	}
4522
4523
4524	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4525	const VssRayContainer &rays)
4526	{
4527	if (!ViewCellsConstructed())
4528	{
4529	Debug << "postprocess error: no view cells constructed" << endl;
4530	return 0;
4531	}
4532
4533	// view cells already finished before post processing step
4534	// (i.e. because they were loaded)
4535	if (mViewCellsFinished)
4536	{
4537	FinalizeViewCells(true);
4538	EvaluateViewCellsStats();
4539
4540	return 0;
4541	}
4542
4543	// check if new view cells turned invalid
4544	int minPvs, maxPvs;
4545
4546	if (0)
4547	{
4548	minPvs = mMinPvsSize;
4549	maxPvs = mMaxPvsSize;
4550	}
4551	else
4552	{
4553	// problem matt: why did I start here from zero?
4554	minPvs = 0;
4555	maxPvs = mMaxPvsSize;
4556	}
4557
4558	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4559	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4560
4561	SetValidity(minPvs, maxPvs);
4562
4563	// update valid view space according to valid view cells
4564	if (0) mVspBspTree->ValidateTree();
4565
4566	// area has to be recomputed
4567	mTotalAreaValid = false;
4568	VssRayContainer postProcessRays;
4569	GetRaySets(rays, mPostProcessSamples, postProcessRays);
4570
4571	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4572
4573	//////////
4574	//-- merge neighbouring view cells
4575	MergeViewCells(postProcessRays, objects);
4576
4577	// refines the merged view cells
4578	if (0) RefineViewCells(postProcessRays, objects);
4579
4580
4581	///////////
4582	//-- render simulation after merge + refine
4583
4584	cout << "\nview cells partition render time before compress" << endl << endl;;
4585	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4586	SimulationStatistics ss;
4587	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4588	cout << ss << endl;
4589
4590	if (0) CompressViewCells();
4591
4592	// collapse sibling leaves that share the same view cell
4593	if (0) mVspBspTree->CollapseTree();
4594
4595	// recompute view cell list and statistics
4596	ResetViewCells();
4597
4598	// compute final meshes and volume / area
4599	if (1) FinalizeViewCells(true);
4600
4601	return 0;
4602	}
4603
4604
4605	int VspBspViewCellsManager::GetType() const
4606	{
4607	return VSP_BSP;
4608	}
4609
4610
4611	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4612	{
4613	// terminate recursion
4614	if (root->IsLeaf())
4615	{
4616	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
4617	leaf->GetViewCell()->SetMergeCost(0.0f);
4618	return leaf->GetViewCell();
4619	}
4620
4621
4622	BspInterior interior = dynamic_cast<BspInterior >(root);
4623	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4624
4625	// evaluate merge cost for priority traversal
4626	float mergeCost = 1.0f / (float)root->mTimeStamp;
4627	viewCellInterior->SetMergeCost(mergeCost);
4628
4629	float volume = 0;
4630
4631	BspNode *front = interior->GetFront();
4632	BspNode *back = interior->GetBack();
4633
4634
4635	ObjectPvs frontPvs, backPvs;
4636
4637	//-- recursivly compute child hierarchies
4638	ViewCell *backVc = ConstructSpatialMergeTree(back);
4639	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4640
4641
4642	viewCellInterior->SetupChildLink(backVc);
4643	viewCellInterior->SetupChildLink(frontVc);
4644
4645	volume += backVc->GetVolume();
4646	volume += frontVc->GetVolume();
4647
4648	viewCellInterior->SetVolume(volume);
4649
4650	return viewCellInterior;
4651	}
4652
4653
4654	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4655	{
4656	if (!ViewCellsConstructed())
4657	return ViewCellsManager::GetViewPoint(viewPoint);
4658
4659	// TODO: set reasonable limit
4660	const int limit = 20;
4661
4662	for (int i = 0; i < limit; ++ i)
4663	{
4664	viewPoint = mViewSpaceBox.GetRandomPoint();
4665	if (mVspBspTree->ViewPointValid(viewPoint))
4666	{
4667	return true;
4668	}
4669	}
4670
4671	Debug << "failed to find valid view point, taking " << viewPoint << endl;
4672	return false;
4673	}
4674
4675
4676	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4677	{
4678	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4679	// validy update in preprocessor for all managers)
4680	return ViewCellsManager::ViewPointValid(viewPoint);
4681
4682	// return mViewSpaceBox.IsInside(viewPoint) &&
4683	// mVspBspTree->ViewPointValid(viewPoint);
4684	}
4685
4686
4687	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4688	const VssRayContainer &sampleRays)
4689	{
4690	if (!ViewCellsConstructed())
4691	return;
4692
4693	VssRayContainer visRays;
4694	GetRaySets(sampleRays, mVisualizationSamples, visRays);
4695
4696	if (1)
4697	{
4698	//////////////////
4699	//-- export final view cell partition
4700
4701	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4702
4703	if (exporter)
4704	{
4705	cout << "exporting view cells after post process ... ";
4706	if (0)
4707	{ // export view space box
4708	exporter->SetWireframe();
4709	exporter->ExportBox(mViewSpaceBox);
4710	exporter->SetFilled();
4711	}
4712
4713	Material m;
4714	m.mDiffuseColor.r = 0.0f;
4715	m.mDiffuseColor.g = 0.5f;
4716	m.mDiffuseColor.b = 0.5f;
4717
4718	exporter->SetForcedMaterial(m);
4719
4720	if (1 && mExportGeometry)
4721	{
4722	exporter->ExportGeometry(objects);
4723	}
4724
4725	if (0 && mExportRays)
4726	{
4727	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4728	}
4729	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4730
4731	delete exporter;
4732	cout << "finished" << endl;
4733	}
4734	}
4735
4736	////////////////
4737	//-- visualization of the BSP splits
4738
4739	bool exportSplits = false;
4740	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4741
4742	if (exportSplits)
4743	{
4744	cout << "exporting splits ... ";
4745	ExportSplits(objects, visRays);
4746	cout << "finished" << endl;
4747	}
4748
4749	////////
4750	//-- export single view cells
4751
4752	int leafOut;
4753	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4754	const int raysOut = 100;
4755
4756	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
4757	}
4758
4759
4760	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
4761	const VssRayContainer &rays)
4762	{
4763	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4764
4765	if (exporter)
4766	{
4767	Material m;
4768	m.mDiffuseColor = RgbColor(1, 0, 0);
4769	exporter->SetForcedMaterial(m);
4770	exporter->SetWireframe();
4771
4772	exporter->ExportBspSplits(*mVspBspTree, true);
4773
4774	// take forced material, else big scenes cannot be viewed
4775	m.mDiffuseColor = RgbColor(0, 1, 0);
4776	exporter->SetForcedMaterial(m);
4777	exporter->SetFilled();
4778
4779	exporter->ResetForcedMaterial();
4780
4781	// export rays
4782	if (mExportRays)
4783	{
4784	exporter->ExportRays(rays, RgbColor(1, 1, 0));
4785	}
4786
4787	if (mExportGeometry)
4788	{
4789	exporter->ExportGeometry(objects);
4790	}
4791	delete exporter;
4792	}
4793	}
4794
4795
4796	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4797	const int maxViewCells,
4798	const bool sortViewCells,
4799	const bool exportPvs,
4800	const bool exportRays,
4801	const int maxRays,
4802	const string prefix,
4803	VssRayContainer *visRays)
4804	{
4805	if (sortViewCells)
4806	{
4807	// sort view cells to visualize the largest view cells
4808	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4809	}
4810
4811	//////////
4812	//-- some view cells for output
4813
4814	ViewCell::NewMail();
4815	const int limit = min(maxViewCells, (int)mViewCells.size());
4816
4817	for (int i = 0; i < limit; ++ i)
4818	{
4819	cout << "creating output for view cell " << i << " ... ";
4820
4821	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
4822	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
4823
4824	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
4825	continue;
4826
4827	vc->Mail();
4828
4829	ObjectPvs pvs;
4830	mViewCellsTree->GetPvs(vc, pvs);
4831
4832	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
4833	Exporter *exporter = Exporter::GetExporter(s);
4834
4835	const float pvsCost = mViewCellsTree->GetPvsCost(vc);
4836	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
4837
4838	if (exportRays)
4839	{
4840	////////////
4841	//-- export rays piercing this view cell
4842
4843	// take rays stored with the view cells during subdivision
4844	VssRayContainer vcRays;
4845	VssRayContainer collectRays;
4846
4847	// collect initial view cells
4848	ViewCellContainer leaves;
4849	mViewCellsTree->CollectLeaves(vc, leaves);
4850
4851	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4852	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4853	{
4854	BspLeaf vcLeaf = dynamic_cast<BspViewCell >(*vit)->mLeaves[0];
4855	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
4856
4857	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
4858	{
4859	collectRays.push_back(*rit);
4860	}
4861	}
4862
4863	const int raysOut = min((int)collectRays.size(), maxRays);
4864
4865	// prepare some rays for output
4866	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4867	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4868	{
4869	const float p = RandomValue(0.0f, (float)collectRays.size());
4870
4871	if (p < raysOut)
4872	{
4873	vcRays.push_back(*rit);
4874	}
4875	}
4876
4877	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
4878	}
4879
4880	////////////////
4881	//-- export view cell geometry
4882
4883	exporter->SetWireframe();
4884
4885	Material m;//= RandomMaterial();
4886	m.mDiffuseColor = RgbColor(0, 1, 0);
4887	exporter->SetForcedMaterial(m);
4888
4889	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4890	exporter->SetFilled();
4891
4892	if (exportPvs)
4893	{
4894	Intersectable::NewMail();
4895
4896	ObjectPvsIterator pit = pvs.GetIterator();
4897
4898	cout << endl;
4899
4900	// output PVS of view cell
4901	while (pit.HasMoreEntries())
4902	{
4903	ObjectPvsEntry entry = pit.Next();
4904	Intersectable *intersect = entry.mObject;
4905
4906	if (!intersect->Mailed())
4907	{
4908	intersect->Mail();
4909
4910	m = RandomMaterial();
4911	exporter->SetForcedMaterial(m);
4912	exporter->ExportIntersectable(intersect);
4913	}
4914	}
4915	cout << endl;
4916	}
4917
4918	DEL_PTR(exporter);
4919	cout << "finished" << endl;
4920	}
4921	}
4922
4923
4924	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
4925	{
4926	Exporter *exporter = Exporter::GetExporter("filter.x3d");
4927
4928	Vector3 bsize = mViewSpaceBox.Size();
4929	const Vector3 viewPoint(mViewSpaceBox.Center());
4930	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
4931	const Vector3 width = Vector3(w);
4932
4933	PrVs testPrVs;
4934
4935	if (exporter)
4936	{
4937	ViewCellContainer viewCells;
4938
4939	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
4940
4941	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
4942
4943	exporter->SetWireframe();
4944
4945	exporter->SetForcedMaterial(RgbColor(1,1,1));
4946	exporter->ExportBox(tbox);
4947
4948	exporter->SetFilled();
4949
4950	exporter->SetForcedMaterial(RgbColor(0,1,0));
4951	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
4952
4953	//exporter->ResetForcedMaterial();
4954	exporter->SetForcedMaterial(RgbColor(0,0,1));
4955	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
4956
4957	exporter->SetForcedMaterial(RgbColor(1,0,0));
4958	exporter->ExportGeometry(objects);
4959
4960	delete exporter;
4961	}
4962	}
4963
4964
4965	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
4966	ViewCellContainer &viewCells) const
4967	{
4968	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
4969	}
4970
4971
4972	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
4973	const Vector3 &termination,
4974	ViewCellContainer &viewcells)
4975	{
4976	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
4977	}
4978
4979
4980	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
4981	{
4982	int numSamples;
4983
4984	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
4985	cout << "samples" << numSamples << endl;
4986
4987	vector<RenderCostSample> samples;
4988
4989	if (!mPreprocessor->GetRenderer())
4990	return;
4991
4992	//start the view point queries
4993	long startTime = GetTime();
4994	cout << "starting sampling of render cost ... ";
4995
4996	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
4997
4998	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4999
5000
5001	// for each sample:
5002	// find view cells associated with the samples
5003	// store the sample pvs with the pvs associated with the view cell
5004	//
5005	// for each view cell:
5006	// compute difference point sampled pvs - view cell pvs
5007	// export geometry with color coded pvs difference
5008
5009	std::map<ViewCell *, ObjectPvs> sampleMap;
5010
5011	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5012
5013	for (rit = samples.begin(); rit != rit_end; ++ rit)
5014	{
5015	RenderCostSample sample = *rit;
5016
5017	ViewCell *vc = GetViewCell(sample.mPosition);
5018
5019	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5020
5021	if (it == sampleMap.end())
5022	{
5023	sampleMap[vc] = sample.mPvs;
5024	}
5025	else
5026	{
5027	(*it).second.MergeInPlace(sample.mPvs);
5028	}
5029	}
5030
5031	// visualize the view cells
5032	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5033
5034	Material m;//= RandomMaterial();
5035
5036	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5037	{
5038	ViewCell vc = (vit).first;
5039
5040	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5041	const int pvsPtSamples = (*vit).second.GetSize();
5042
5043	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5044	m.mDiffuseColor.b = 1.0f;
5045	//exporter->SetForcedMaterial(m);
5046	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5047
5048	/* // counting the pvss
5049	for (rit = samples.begin(); rit != rit_end; ++ rit)
5050	{
5051	RenderCostSample sample = *rit;
5052	ViewCell *vc = GetViewCell(sample.mPosition);
5053
5054	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5055	Mesh *hMesh = CreateMeshFromBox(box);
5056
5057	DEL_PTR(hMesh);
5058	}
5059	*/
5060	}
5061	}
5062
5063
5064	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5065	ViewCell *vc,
5066	const AxisAlignedBox3 *sceneBox,
5067	const AxisAlignedPlane *clipPlane
5068	) const
5069	{
5070	if (clipPlane)
5071	{
5072	const Plane3 plane = clipPlane->GetPlane();
5073
5074	ViewCellContainer leaves;
5075	mViewCellsTree->CollectLeaves(vc, leaves);
5076	ViewCellContainer::const_iterator it, it_end = leaves.end();
5077
5078	for (it = leaves.begin(); it != it_end; ++ it)
5079	{
5080	BspNodeGeometry geom;
5081	BspNodeGeometry front;
5082	BspNodeGeometry back;
5083
5084	mVspBspTree->ConstructGeometry(*it, geom);
5085
5086	const float eps = 0.0001f;
5087	const int cf = geom.Side(plane, eps);
5088
5089	if (cf == -1)
5090	{
5091	exporter->ExportPolygons(geom.GetPolys());
5092	}
5093	else if (cf == 0)
5094	{
5095	geom.SplitGeometry(front,
5096	back,
5097	plane,
5098	mViewSpaceBox,
5099	eps);
5100
5101	if (back.Valid())
5102	{
5103	exporter->ExportPolygons(back.GetPolys());
5104	}
5105	}
5106	}
5107	}
5108	else
5109	{
5110	// export mesh if available
5111	// TODO: some bug here?
5112	if (1 && vc->GetMesh())
5113	{
5114	exporter->ExportMesh(vc->GetMesh());
5115	}
5116	else
5117	{
5118	BspNodeGeometry geom;
5119	mVspBspTree->ConstructGeometry(vc, geom);
5120	exporter->ExportPolygons(geom.GetPolys());
5121	}
5122	}
5123	}
5124
5125
5126	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5127	{
5128	ViewCellContainer leaves;
5129	mViewCellsTree->CollectLeaves(vc, leaves);
5130
5131	int maxDist = 0;
5132
5133	// compute max height difference
5134	for (int i = 0; i < (int)leaves.size(); ++ i)
5135	{
5136	for (int j = 0; j < (int)leaves.size(); ++ j)
5137	{
5138	BspLeaf leaf = dynamic_cast<BspViewCell >(leaves[i])->mLeaves[0];
5139
5140	if (i != j)
5141	{
5142	BspLeaf leaf2 =dynamic_cast<BspViewCell >(leaves[j])->mLeaves[0];
5143	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5144
5145	if (dist > maxDist)
5146	maxDist = dist;
5147	}
5148	}
5149	}
5150
5151	return maxDist;
5152	}
5153
5154
5155	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5156	{
5157	if (!ViewCellsConstructed())
5158	return NULL;
5159
5160	if (!mViewSpaceBox.IsInside(point))
5161	return NULL;
5162
5163	return mVspBspTree->GetViewCell(point, active);
5164	}
5165
5166
5167	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5168	{
5169	BspNodeGeometry geom;
5170	mVspBspTree->ConstructGeometry(vc, geom);
5171
5172	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5173	IncludeNodeGeomInMesh(geom, *mesh);
5174
5175	vc->SetMesh(mesh);
5176	}
5177
5178
5179	int VspBspViewCellsManager::CastBeam(Beam &beam)
5180	{
5181	return mVspBspTree->CastBeam(beam);
5182	}
5183
5184
5185	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5186	const bool createMesh)
5187	{
5188	float area = 0;
5189	float volume = 0;
5190
5191	ViewCellContainer leaves;
5192	mViewCellsTree->CollectLeaves(viewCell, leaves);
5193
5194	ViewCellContainer::const_iterator it, it_end = leaves.end();
5195
5196	for (it = leaves.begin(); it != it_end; ++ it)
5197	{
5198	BspNodeGeometry geom;
5199	mVspBspTree->ConstructGeometry(*it, geom);
5200
5201	const float lVol = geom.GetVolume();
5202	const float lArea = geom.GetArea();
5203
5204	area += lArea;
5205	volume += lVol;
5206
5207	if (createMesh)
5208	CreateMesh(*it);
5209	}
5210
5211	viewCell->SetVolume(volume);
5212	viewCell->SetArea(area);
5213	}
5214
5215
5216	void VspBspViewCellsManager::TestSubdivision()
5217	{
5218	ViewCellContainer leaves;
5219	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5220
5221	ViewCellContainer::const_iterator it, it_end = leaves.end();
5222
5223	const float vol = mViewSpaceBox.GetVolume();
5224	float subdivVol = 0;
5225	float newVol = 0;
5226
5227	for (it = leaves.begin(); it != it_end; ++ it)
5228	{
5229	BspNodeGeometry geom;
5230	mVspBspTree->ConstructGeometry(*it, geom);
5231
5232	const float lVol = geom.GetVolume();
5233
5234	newVol += lVol;
5235	subdivVol += (*it)->GetVolume();
5236
5237	float thres = 0.9f;
5238	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5239	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5240	}
5241
5242	Debug << "exact volume: " << vol << endl;
5243	Debug << "subdivision volume: " << subdivVol << endl;
5244	Debug << "new volume: " << newVol << endl;
5245	}
5246
5247
5248	void VspBspViewCellsManager::PrepareLoadedViewCells()
5249	{
5250	// TODO: do I still need this here?
5251	if (0)
5252	mVspBspTree->RepairViewCellsLeafLists();
5253	}
5254
5255
5256
5257	/************************************************************************/
5258	/* VspOspViewCellsManager implementation */
5259	/************************************************************************/
5260
5261
5262	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5263	const string &hierarchyType)
5264	: ViewCellsManager(vcTree)
5265	{
5266	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5267
5268	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5269
5270	Debug << "compressing objects: " << mCompressObjects << endl;
5271	cout << "compressing objects: " << mCompressObjects << endl;
5272
5273	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5274	mHierarchyManager->SetViewCellsManager(this);
5275	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5276	}
5277
5278
5279	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5280	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5281	{
5282	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5283	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5284
5285	Debug << "compressing objects: " << mCompressObjects << endl;
5286	cout << "compressing objects: " << mCompressObjects << endl;
5287
5288	mHierarchyManager->SetViewCellsManager(this);
5289	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5290	}
5291
5292
5293	Intersectable *
5294	VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
5295	{
5296	if (mUseKdPvs)
5297	{
5298	return ViewCellsManager::GetIntersectable(ray, isTermination);
5299	}
5300	else
5301	{
5302	return mHierarchyManager->GetIntersectable(ray, isTermination);
5303	}
5304	}
5305
5306
5307	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5308	{
5309	HierarchyManager *hierarchyManager;
5310
5311	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5312	{
5313	Debug << "hierarchy manager: osp" << endl;
5314	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5315	}
5316	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5317	{
5318	Debug << "hierarchy manager: bvh" << endl;
5319	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5320	}
5321	else // only view space partition
5322	{
5323	Debug << "hierarchy manager: obj" << endl;
5324	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5325	}
5326
5327	return hierarchyManager;
5328	}
5329
5330
5331	VspOspViewCellsManager::~VspOspViewCellsManager()
5332	{
5333	DEL_PTR(mHierarchyManager);
5334	}
5335
5336
5337	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5338	{
5339	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5340	}
5341
5342
5343	void VspOspViewCellsManager::CollectViewCells()
5344	{
5345	// view cells tree constructed
5346	if (!ViewCellsTreeConstructed())
5347	{
5348	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5349	}
5350	else
5351	{ // we can use the view cells tree hierarchy to get the right set
5352	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5353	}
5354	}
5355
5356
5357	bool VspOspViewCellsManager::ViewCellsConstructed() const
5358	{
5359	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5360	}
5361
5362
5363	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5364	{
5365	return new VspViewCell(mesh);
5366	}
5367
5368
5369	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5370	const VssRayContainer &rays)
5371	{
5372	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5373
5374	// skip rest if view cells were already constructed
5375	if (ViewCellsConstructed())
5376	return 0;
5377
5378	int sampleContributions = 0;
5379	VssRayContainer sampleRays;
5380
5381	int limit = min (mInitialSamples, (int)rays.size());
5382
5383	VssRayContainer constructionRays;
5384	VssRayContainer savedRays;
5385
5386	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5387	<< ", actual rays: " << (int)rays.size() << endl;
5388
5389	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5390
5391	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5392	Debug << "saved rays: " << (int)savedRays.size() << endl;
5393
5394	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5395
5396	#if TEST_EVALUATION
5397	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5398	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5399	{
5400	storedRays.push_back(new VssRay((tit)));
5401	}
5402	#endif
5403
5404	/////////////////////////
5405	//-- print satistics for subdivision and view cells
5406
5407	Debug << endl << endl << *mHierarchyManager << endl;
5408
5409	ResetViewCells();
5410	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5411
5412	//////////////
5413	//-- recast rest of rays
5414
5415	const long startTime = GetTime();
5416	cout << "Computing remaining ray contributions ... ";
5417
5418	if (SAMPLE_AFTER_SUBDIVISION)
5419	ComputeSampleContributions(savedRays, true, false);
5420
5421	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5422	<< " secs" << endl;
5423
5424	if (0)
5425	{ // real meshes are constructed at this stage
5426	cout << "finalizing view cells ... ";
5427	FinalizeViewCells(true);
5428	cout << "finished" << endl;
5429	}
5430
5431	return sampleContributions;
5432	}
5433
5434
5435	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5436	const VssRayContainer &rays)
5437	{
5438	if (!ViewCellsConstructed())
5439	{
5440	Debug << "post process error: no view cells constructed" << endl;
5441	return 0;
5442	}
5443
5444	// if view cells were already constructed before post processing step
5445	// (e.g., because they were loaded), we are finished
5446	if (mViewCellsFinished)
5447	{
5448	FinalizeViewCells(true);
5449	EvaluateViewCellsStats();
5450
5451	return 0;
5452	}
5453
5454	// check if new view cells turned invalid
5455	int minPvs, maxPvs;
5456
5457	if (0)
5458	{
5459	minPvs = mMinPvsSize;
5460	maxPvs = mMaxPvsSize;
5461	}
5462	else
5463	{
5464	// problem matt: why did I start here from zero?
5465	minPvs = 0;
5466	maxPvs = mMaxPvsSize;
5467	}
5468
5469	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5470	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5471
5472	SetValidity(minPvs, maxPvs);
5473
5474
5475	// area is not up to date, has to be recomputed
5476	mTotalAreaValid = false;
5477	VssRayContainer postProcessRays;
5478	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5479
5480	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5481
5482
5483	// compute tree by merging the nodes of the spatial hierarchy
5484	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5485	mViewCellsTree->SetRoot(root);
5486
5487	//////////////////////////
5488	//-- update pvs up to the root of the hierarchy
5489
5490	ObjectPvs pvs;
5491	UpdatePvsForEvaluation(root, pvs);
5492
5493
5494	//////////////////////
5495	//-- render simulation after merge + refine
5496
5497	cout << "\nview cells partition render time before compress" << endl << endl;
5498	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
5499	SimulationStatistics ss;
5500	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5501	cout << ss << endl;
5502
5503
5504	mHierarchyManager->CreateUniqueObjectIds();
5505
5506	///////////
5507	//-- compression
5508
5509	if (0) CompressViewCells();
5510
5511	/////////////
5512	//-- some tasks still to do on the view cells:
5513	//-- Compute meshes from view cell geometry, evaluate volume and / or area
5514
5515	if (1) FinalizeViewCells(true);
5516
5517	return 0;
5518	}
5519
5520
5521	int VspOspViewCellsManager::GetType() const
5522	{
5523	return VSP_OSP;
5524	}
5525
5526
5527	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5528	{
5529	// terminate recursion
5530	if (root->IsLeaf())
5531	{
5532	VspLeaf leaf = dynamic_cast<VspLeaf >(root);
5533	leaf->GetViewCell()->SetMergeCost(0.0f);
5534	return leaf->GetViewCell();
5535	}
5536
5537	VspInterior interior = dynamic_cast<VspInterior >(root);
5538	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5539
5540	// evaluate merge cost for priority traversal
5541	const float mergeCost = -(float)root->mTimeStamp;
5542	viewCellInterior->SetMergeCost(mergeCost);
5543
5544	float volume = 0;
5545
5546	VspNode *front = interior->GetFront();
5547	VspNode *back = interior->GetBack();
5548
5549	ObjectPvs frontPvs, backPvs;
5550
5551	/////////
5552	//-- recursivly compute child hierarchies
5553
5554	ViewCell *backVc = ConstructSpatialMergeTree(back);
5555	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5556
5557	viewCellInterior->SetupChildLink(backVc);
5558	viewCellInterior->SetupChildLink(frontVc);
5559
5560	volume += backVc->GetVolume();
5561	volume += frontVc->GetVolume();
5562
5563	viewCellInterior->SetVolume(volume);
5564
5565	return viewCellInterior;
5566	}
5567
5568
5569	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5570	{
5571	if (!ViewCellsConstructed())
5572	return ViewCellsManager::GetViewPoint(viewPoint);
5573
5574	// TODO: set reasonable limit
5575	const int limit = 20;
5576
5577	for (int i = 0; i < limit; ++ i)
5578	{
5579	viewPoint = mViewSpaceBox.GetRandomPoint();
5580
5581	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
5582	{
5583	return true;
5584	}
5585	}
5586
5587	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5588	return false;
5589	}
5590
5591
5592	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5593	ViewCell *vc,
5594	const AxisAlignedBox3 *sceneBox,
5595	const AxisAlignedPlane *clipPlane
5596	) const
5597	{
5598	ViewCellContainer leaves;
5599	mViewCellsTree->CollectLeaves(vc, leaves);
5600	ViewCellContainer::const_iterator it, it_end = leaves.end();
5601
5602	Plane3 plane;
5603	if (clipPlane)
5604	{
5605	// arbitrary plane definition
5606	plane = clipPlane->GetPlane();
5607	}
5608
5609	for (it = leaves.begin(); it != it_end; ++ it)
5610	{
5611	VspViewCell vspVc = dynamic_cast<VspViewCell >(*it);
5612	VspLeaf *l = vspVc->mLeaves[0];
5613
5614	const AxisAlignedBox3 box =
5615	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
5616
5617	if (sceneBox && !Overlap(*sceneBox, box))
5618	continue;
5619
5620	if (clipPlane)
5621	{
5622	if (box.Side(plane) == -1)
5623	{
5624	exporter->ExportBox(box);
5625	}
5626	else if (box.Side(plane) == 0)
5627	{
5628	// intersection
5629	AxisAlignedBox3 fbox, bbox;
5630	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5631	exporter->ExportBox(bbox);
5632	}
5633	}
5634	else
5635	{
5636	exporter->ExportBox(box);
5637	}
5638	}
5639	}
5640
5641
5642	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5643	{
5644	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5645	// validy update in preprocessor for all managers)
5646	return ViewCellsManager::ViewPointValid(viewPoint);
5647
5648	// return mViewSpaceBox.IsInside(viewPoint) &&
5649	// mVspTree->ViewPointValid(viewPoint);
5650	}
5651
5652
5653	float VspOspViewCellsManager::UpdateObjectCosts()
5654	{
5655	float maxRenderCost = 0;
5656
5657	cout << "updating object pvs cost ... ";
5658	const long startTime = GetTime();
5659
5660	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
5661
5662	Intersectable::NewMail();
5663
5664	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
5665
5666	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
5667	{
5668	ViewCell vc = vit;
5669
5670	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
5671
5672	// output PVS of view cell
5673	while (pit.HasMoreEntries())
5674	{
5675	ObjectPvsEntry entry = pit.Next();
5676
5677	BvhNode node = dynamic_cast<BvhNode >(entry.mObject);
5678
5679	// hack!!
5680	if (!node->IsLeaf())
5681	{
5682	cout << "error, can only do leaves" << endl;
5683	return 0;
5684	}
5685
5686	if (!node->Mailed())
5687	{
5688	node->Mail();
5689	node->mRenderCost = 0;
5690	}
5691
5692	const float rc = (float)((BvhLeaf *)node)->mObjects.size();
5693
5694	node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
5695
5696	if (node->mRenderCost > maxRenderCost)
5697	maxRenderCost = node->mRenderCost;
5698	}
5699	}
5700
5701	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
5702
5703	return maxRenderCost;
5704	}
5705
5706
5707	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5708	const VssRayContainer &sampleRays)
5709	{
5710	if (!ViewCellsConstructed())
5711	return;
5712
5713	VssRayContainer visRays;
5714	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5715
5716	////////////
5717	//-- export final view cells
5718
5719	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5720
5721	//Vector3 scale(0.9f, 0.9f, 0.9f);
5722	Vector3 scale(1.0f, 1.0f, 1.0f);
5723
5724	if (exporter)
5725	{
5726	if (CLAMP_TO_BOX)
5727	{
5728	exporter->mClampToBox = true;
5729	}
5730
5731	EvaluateViewCellsStats();
5732
5733	const long starttime = GetTime();
5734	cout << "exporting final view cells (after initial construction + post process) ... ";
5735
5736	// matt: hack for clamping scene
5737	AxisAlignedBox3 bbox = mViewSpaceBox;
5738	bbox.Scale(scale);
5739
5740	if (0 && mExportRays)
5741	{
5742	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5743	}
5744
5745	// hack color code (show pvs size)
5746	const int savedColorCode = mColorCode;
5747
5748	const float maxRenderCost = UpdateObjectCosts();
5749	cout << "maxRenderCost: " << maxRenderCost << endl;
5750	mColorCode = 0; // 0 = random, 1 = export pvs
5751
5752	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
5753	CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
5754
5755
5756	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
5757	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5758
5759	delete exporter;
5760
5761	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5762	mColorCode = savedColorCode;
5763	}
5764
5765	exporter = Exporter::GetExporter("final_object_partition.wrl");
5766
5767	if (exporter)
5768	{
5769	if (CLAMP_TO_BOX)
5770	{
5771	exporter->mClampToBox = true;
5772	}
5773
5774	EvaluateViewCellsStats();
5775
5776	const long starttime = GetTime();
5777	cout << "exporting final objects (after initial construction + post process) ... ";
5778
5779	// matt: hack for clamping scene
5780	AxisAlignedBox3 bbox = mViewSpaceBox;
5781	bbox.Scale(scale);
5782
5783	// hack color code (show pvs size)
5784	const int savedColorCode = mColorCode;
5785
5786	mColorCode = 1; // 0 = random, 1 = export pvs
5787	const float maxRenderCost = -1;
5788
5789	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
5790	CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
5791
5792
5793	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
5794	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5795
5796	delete exporter;
5797
5798	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5799	mColorCode = savedColorCode;
5800	}
5801
5802	#if 0
5803	// export final object partition
5804	exporter = Exporter::GetExporter("final_object_partition.wrl");
5805
5806	if (exporter)
5807	{
5808	if (CLAMP_TO_BOX)
5809	{
5810	exporter->mClampToBox = true;
5811	}
5812
5813	const long starttime = GetTime();
5814
5815	// matt: hack for making visualization smaller in size
5816	AxisAlignedBox3 bbox = mHierarchyManager->GetObjectSpaceBox();
5817	bbox.Scale(scale);
5818
5819	cout << "exporting object space hierarchy ... ";
5820	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, CLAMP_TO_BOX ? &bbox : NULL, -1);
5821
5822	delete exporter;
5823	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5824	}
5825	#endif
5826
5827	// visualization of the view cells
5828	if (0)
5829	{
5830	ExportMergedViewCells(objects);
5831	}
5832
5833	// export some view cells
5834	int leafOut;
5835	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5836
5837	const bool sortViewCells = false;
5838	const bool exportPvs = true;
5839	const bool exportRays = true;
5840	const int raysOut = 100;
5841
5842	ExportSingleViewCells(objects,
5843	leafOut,
5844	sortViewCells,
5845	exportPvs,
5846	exportRays,
5847	raysOut,
5848	"");
5849	}
5850
5851
5852	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5853	const int maxViewCells,
5854	const bool sortViewCells,
5855	const bool exportPvs,
5856	const bool exportRays,
5857	const int maxRays,
5858	const string prefix,
5859	VssRayContainer *visRays)
5860	{
5861	if (sortViewCells)
5862	{
5863	// sort view cells to visualize the view cells with highest render cost
5864	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5865	}
5866
5867	ViewCell::NewMail();
5868	const int limit = min(maxViewCells, (int)mViewCells.size());
5869
5870	cout << "\nExporting " << limit << " single view cells: " << endl;
5871
5872	for (int i = 0; i < limit; ++ i)
5873	{
5874	cout << "creating output for view cell " << i << " ... ";
5875
5876	// largest view cell pvs first of random view cell
5877	ViewCell *vc = sortViewCells ?
5878	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
5879
5880	if (vc->Mailed()) // view cell already processed
5881	continue;
5882
5883	vc->Mail();
5884
5885	ObjectPvs pvs;
5886	mViewCellsTree->GetPvs(vc, pvs);
5887
5888	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5889	Exporter *exporter = Exporter::GetExporter(s);
5890
5891	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;
5892
5893	if (exportPvs)
5894	{
5895	Material m;
5896
5897	Intersectable::NewMail();
5898
5899	ObjectPvsIterator pit = pvs.GetIterator();
5900
5901	// output PVS of view cell
5902	while (pit.HasMoreEntries())
5903	{
5904	ObjectPvsEntry entry = pit.Next();
5905
5906	Intersectable *intersect = entry.mObject;
5907
5908	if (!intersect->Mailed())
5909	{
5910	m = RandomMaterial();
5911	exporter->SetForcedMaterial(m);
5912
5913	exporter->ExportIntersectable(intersect);
5914	intersect->Mail();
5915	}
5916	}
5917	}
5918
5919	if (exportRays)
5920	{
5921	////////////
5922	//-- export the sample rays
5923
5924	// output rays stored with the view cells during subdivision
5925	VssRayContainer vcRays;
5926	VssRayContainer collectRays;
5927
5928	// collect intial view cells
5929	ViewCellContainer leaves;
5930	mViewCellsTree->CollectLeaves(vc, leaves);
5931
5932	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5933
5934	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5935	{
5936	VspLeaf vcLeaf = dynamic_cast<VspViewCell >(*vit)->mLeaves[0];
5937	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5938
5939	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5940	{
5941	collectRays.push_back(*rit);
5942	}
5943	}
5944
5945	const int raysOut = min((int)collectRays.size(), maxRays);
5946
5947	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5948
5949	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5950	{
5951	const float p = RandomValue(0.0f, (float)collectRays.size());
5952
5953	if (p < raysOut)
5954	vcRays.push_back(*rit);
5955	}
5956
5957	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5958	}
5959
5960
5961	/////////////////
5962	//-- export view cell geometry
5963
5964	exporter->SetWireframe();
5965
5966	Material m;
5967	m.mDiffuseColor = RgbColor(0, 1, 0);
5968	exporter->SetForcedMaterial(m);
5969
5970	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5971	exporter->SetFilled();
5972
5973	DEL_PTR(exporter);
5974	cout << "finished" << endl;
5975	}
5976
5977	cout << endl;
5978	}
5979
5980
5981	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5982	ViewCellContainer &viewCells) const
5983	{
5984	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
5985	}
5986
5987
5988	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
5989	const Vector3 &termination,
5990	ViewCellContainer &viewcells)
5991	{
5992	return mHierarchyManager->GetVspTree()->CastLineSegment(origin, termination, viewcells);
5993	}
5994
5995
5996	bool VspOspViewCellsManager::ExportViewCells(const string filename,
5997	const bool exportPvs,
5998	const ObjectContainer &objects)
5999	{
6000	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6001	return false;
6002
6003	const long starttime = GetTime();
6004	cout << "exporting view cells to xml ... ";
6005
6006	OUT_STREAM stream(filename.c_str());
6007
6008	// for output we need unique ids for each view cell
6009	CreateUniqueViewCellIds();
6010
6011	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6012	stream << "<VisibilitySolution>" << endl;
6013
6014	// §§ tmp matt: for storage cost
6015	if (0 && exportPvs)
6016	{
6017	///////////////
6018	//-- export bounding boxes
6019	//-- The bounding boxes are used to identify
6020	//-- the objects in the rendering engine
6021	mHierarchyManager->ExportBoundingBoxes(stream, objects);
6022	}
6023
6024	//////////////////////////
6025	//-- export the view cells and the pvs
6026
6027	const int numViewCells = mCurrentViewCellsStats.viewCells;
6028
6029	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6030	mViewCellsTree->Export(stream, exportPvs);
6031	stream << "</ViewCells>" << endl;
6032
6033	//////////////////////
6034	//-- export the view space hierarchy
6035
6036	stream << "<ViewSpaceHierarchy type=\"vsp\""
6037	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6038	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6039
6040	mHierarchyManager->GetVspTree()->Export(stream);
6041	stream << "</ViewSpaceHierarchy>" << endl;
6042
6043	//////////////////////
6044	//-- export the object space partition
6045
6046	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6047
6048	stream << "</VisibilitySolution>" << endl;
6049	stream.close();
6050
6051	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6052	return true;
6053	}
6054
6055
6056
6057	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6058	const bool active) const
6059	{
6060	if (!ViewCellsConstructed())
6061	return NULL;
6062
6063	if (!mViewSpaceBox.IsInside(point))
6064	return NULL;
6065
6066	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6067	}
6068
6069
6070	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6071	{
6072	// matt: TODO
6073	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6074
6075	ViewCellContainer leaves;
6076	mViewCellsTree->CollectLeaves(vc, leaves);
6077
6078	ViewCellContainer::const_iterator it, it_end = leaves.end();
6079
6080	for (it = leaves.begin(); it != it_end; ++ it)
6081	{
6082	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaves[0];
6083	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6084	IncludeBoxInMesh(box, *mesh);
6085	}
6086
6087	vc->SetMesh(mesh);
6088	}
6089
6090
6091	int VspOspViewCellsManager::CastBeam(Beam &beam)
6092	{
6093	// matt: TODO
6094	return 0;
6095	}
6096
6097
6098	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6099	{
6100	float area = 0;
6101	float volume = 0;
6102
6103	ViewCellContainer leaves;
6104	mViewCellsTree->CollectLeaves(viewCell, leaves);
6105
6106	ViewCellContainer::const_iterator it, it_end = leaves.end();
6107
6108	for (it = leaves.begin(); it != it_end; ++ it)
6109	{
6110	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaves[0];
6111
6112	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6113
6114	const float lVol = box.GetVolume();
6115	const float lArea = box.SurfaceArea();
6116
6117	area += lArea;
6118	volume += lVol;
6119
6120	CreateMesh(*it);
6121	}
6122
6123	viewCell->SetVolume(volume);
6124	viewCell->SetArea(area);
6125	}
6126
6127
6128	void VspOspViewCellsManager::PrepareLoadedViewCells()
6129	{
6130	// TODO
6131	}
6132
6133
6134	static void PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6135	{
6136	float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6137
6138	float fullmem = mem +
6139	(hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6140	hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6141
6142	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6143	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6144	}
6145
6146
6147	void VspOspViewCellsManager::CompressViewCells()
6148	{
6149	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6150	return;
6151
6152	////////////
6153	//-- compression
6154
6155	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6156
6157	cout << "before compression: " << endl;
6158	Debug << "before compression: " << endl;
6159
6160	PrintCompressionStats(mHierarchyManager, pvsEntries);
6161
6162	if (mCompressObjects)
6163	{
6164	cout << "compressing in the objects: " << endl;
6165	Debug << "compressing in the objects: " << endl;
6166
6167	pvsEntries = mHierarchyManager->CompressObjectSpace();
6168	}
6169	else
6170	{
6171	cout << "compressing in the view space: " << endl;
6172	Debug << "compressing in the view space: " << endl;
6173
6174	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6175	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6176	}
6177
6178	PrintCompressionStats(mHierarchyManager, pvsEntries);
6179	}
6180
6181
6182	ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
6183	ObjectContainer *objects,
6184	const bool finalizeViewCells,
6185	BoundingBoxConverter *bconverter)
6186
6187	{
6188	ViewCellsManager *vm =
6189	ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
6190	#if 0
6191	// insert scene objects in tree
6192	mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);
6193	#endif
6194	return vm;
6195	}
6196
6197
6198	void
6199	VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
6200	{
6201	mHierarchyManager->CollectObjects(box, objects);
6202	}
6203
6204
6205	#if 1
6206
6207	void VspOspViewCellsManager::EvalViewCellPartition()
6208	{
6209	int samplesPerPass;
6210	int numSamples;
6211	int castSamples = 0;
6212	int oldSamples = 0;
6213	int samplesForStats;
6214	char statsPrefix[100];
6215	char suffix[100];
6216	int splitsStepSize;
6217
6218	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6219	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6220	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
6221	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6222	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6223
6224	bool useHisto;
6225	int histoMem;
6226
6227	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6228	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6229
6230	Debug << "step size: " << splitsStepSize << endl;
6231	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6232	Debug << "view cell evaluation samples: " << numSamples << endl;
6233	Debug << "view cell stats prefix: " << statsPrefix << endl;
6234
6235	cout << "reseting pvs ... ";
6236
6237	// reset pvs and start over from zero
6238	mViewCellsTree->ResetPvs();
6239
6240	cout << "finished" << endl;
6241	cout << "Evaluating view cell partition ... " << endl;
6242
6243	vector<int> evalStrats;
6244
6245	// mix of sampling strategies
6246	if (0)
6247	{
6248	evalStrats.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
6249	}
6250	else
6251	{
6252	/*evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
6253	evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6254	evalStrats.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
6255	*/
6256	evalStrats.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
6257	}
6258
6259	Debug << "casting eval strategies: ";
6260	for (int i = 0; i < (int)evalStrats.size(); ++ i)
6261	Debug << evalStrats[i] << " ";
6262	Debug << endl;
6263
6264	cout << "casting eval strategies: ";
6265	for (int i = 0; i < (int)evalStrats.size(); ++ i)
6266	cout << evalStrats[i] << " ";
6267	cout << endl;
6268
6269	int pass = 0;
6270
6271	while (castSamples < numSamples)
6272	{
6273	///////////////
6274	//-- we have to use uniform sampling strategy for construction rays
6275
6276	VssRayContainer evaluationSamples;
6277	const int samplingType = mEvaluationSamplingType;
6278
6279	long startTime = GetTime();
6280
6281	cout << "casting " << samplesPerPass << " samples ... ";
6282	Debug << "casting " << samplesPerPass << " samples ... ";
6283
6284	if (1)
6285	{
6286	CastPassSamples(samplesPerPass, evalStrats, evaluationSamples);
6287	}
6288	else
6289	{
6290	// use mixed distributions
6291	CastPassSamples2(samplesPerPass, evaluationSamples);
6292	}
6293
6294	castSamples += samplesPerPass;
6295
6296	Real timeDiff = TimeDiff(startTime, GetTime());
6297
6298	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6299	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6300
6301	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6302	Debug << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6303
6304	startTime = GetTime();
6305
6306	ComputeSampleContributions(evaluationSamples, true, false);
6307
6308	timeDiff = TimeDiff(startTime, GetTime());
6309	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6310	Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6311
6312	if ((castSamples >= samplesForStats + oldSamples) \|\|
6313	(castSamples >= numSamples))
6314	{
6315	oldSamples += samplesForStats;
6316
6317	///////////
6318	//-- output stats
6319
6320	sprintf(suffix, "-%09d-eval.log", castSamples);
6321	const string filename = string(statsPrefix) + string(suffix);
6322
6323	startTime = GetTime();
6324
6325	cout << "compute new statistics ... " << endl;
6326
6327	ofstream ofstr(filename.c_str());
6328	mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6329
6330	timeDiff = TimeDiff(startTime, GetTime());
6331	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6332	cout << "*************************************" << endl;
6333
6334	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6335
6336	#if 0
6337	//////////////
6338	// filtered stats
6339
6340	sprintf(suffix, "-%09d-eval-filter.log", castSamples);
6341	const string filename2 = string(statsPrefix) + string(suffix);
6342
6343	startTime = GetTime();
6344
6345	cout << "compute new statistics for filtered pvs ... " << endl;
6346
6347	ofstream ofstr2(filename2.c_str());
6348	mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);
6349
6350	timeDiff = TimeDiff(startTime, GetTime());
6351	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6352	cout << "*************************************" << endl;
6353	Debug << "filtered statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6354	#endif
6355
6356	// only for debugging purpose
6357	if (0)
6358	{
6359	ViewCellContainer viewCells;
6360	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);
6361
6362	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
6363	int pvsSize = 0;
6364
6365	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
6366	{
6367	pvsSize += (*vit)->GetPvs().GetSize();
6368	}
6369
6370	cout << "debug entries: " << pvsSize << ", memcost: "
6371	<< (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
6372	}
6373	++ pass;
6374	}
6375
6376	disposeRays(evaluationSamples, NULL);
6377	}
6378
6379	////////////
6380	//-- histogram
6381	#if 1
6382	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
6383	int histoStepSize;
6384
6385	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6386	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
6387
6388	if (useHisto)
6389	{
6390	// evaluate view cells in a histogram
6391	char str[64];
6392
6393	// hack: just show final view cells
6394	int pass = (int)mViewCells.size();
6395	//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
6396	if (1)
6397	{
6398	string filename;
6399
6400	cout << "computing histogram for " << pass << " view cells" << endl;
6401
6402	//////////////////////////////////////////
6403	//-- evaluate histogram for pvs size
6404
6405	cout << "computing pvs histogram for " << pass << " view cells" << endl;
6406
6407	sprintf(str, "-%09d-histo-pvs2.log", pass);
6408	filename = string(statsPrefix) + string(str);
6409
6410	EvalViewCellHistogramForPvsSize(filename, pass);
6411	}
6412	}
6413	#endif
6414	}
6415
6416	#endif
6417
6418
6419
6420	}

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

Download in other formats: