Context Navigation

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

Revision 1284, 139.6 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: