Context Navigation

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

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

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

Download in other formats: