Context Navigation

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

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

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

Download in other formats: