Context Navigation

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

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

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

Download in other formats: