Context Navigation

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

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

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

Download in other formats: