Context Navigation

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

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

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

Download in other formats: