Context Navigation

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

Revision 1263, 144.0 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: