Context Navigation

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

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

Line
1	#include "ViewCellsManager.h"
2	#include "RenderSimulator.h"
3	#include "Mesh.h"
4	#include "Triangle3.h"
5	#include "ViewCell.h"
6	#include "Environment.h"
7	#include "X3dParser.h"
8	#include "ViewCellBsp.h"
9	#include "KdTree.h"
10	#include "HierarchyManager.h"
11	#include "Exporter.h"
12	#include "VspBspTree.h"
13	#include "ViewCellsParser.h"
14	#include "Beam.h"
15	#include "VssPreprocessor.h"
16	#include "RssPreprocessor.h"
17	#include "BoundingBoxConverter.h"
18	#include "GlRenderer.h"
19	#include "ResourceManager.h"
20	#include "KdIntersectable.h"
21	#include "VspTree.h"
22	#include "OspTree.h"
23	#include "BvHierarchy.h"
24
25
26	// should not count origin object for sampling because it disturbs heuristics
27	#define SAMPLE_ORIGIN_OBJECTS 0
28
29	namespace GtpVisibilityPreprocessor {
30
31
32	// HACK
33	const static bool SAMPLE_AFTER_SUBDIVISION = true;
34	const static bool TEST_EMPTY_VIEW_CELLS = false;
35
36
37	template <typename T> class myless
38	{
39	public:
40	//bool operator() (HierarchyNode v1, HierarchyNode v2) const
41	bool operator() (T v1, T v2) const
42	{
43	return (v1->GetMergeCost() < v2->GetMergeCost());
44	}
45	};
46
47
48	ViewCellsManager::ViewCellsManager(ViewCellsTree *viewCellsTree):
49	mRenderer(NULL),
50	mInitialSamples(0),
51	mConstructionSamples(0),
52	mPostProcessSamples(0),
53	mVisualizationSamples(0),
54	mTotalAreaValid(false),
55	mTotalArea(0.0f),
56	mViewCellsFinished(false),
57	mMaxPvsSize(9999999),
58	mMinPvsSize(0), // one means only empty view cells are invalid
59	mMaxPvsRatio(1.0),
60	mViewCellPvsIsUpdated(false),
61	mPreprocessor(NULL),
62	mViewCellsTree(viewCellsTree)
63	{
64	mViewSpaceBox.Initialize();
65	ParseEnvironment();
66
67	mViewCellsTree->SetViewCellsManager(this);
68	//mViewCellsTree = new ViewCellsTree(this);
69	}
70
71
72	void ViewCellsManager::ParseEnvironment()
73	{
74	// visualization stuff
75	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
76	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
77	Environment::GetSingleton()->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
78
79	Environment::GetSingleton()->GetBoolValue("ViewCells.pruneEmptyViewCells", mPruneEmptyViewCells);
80
81	// HACK
82	if (0)
83	mMinPvsSize = mPruneEmptyViewCells ? 1 : 0;
84	else
85	mMinPvsSize = 0;
86
87	Environment::GetSingleton()->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);
88
89	Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
90	Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
91	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
92
93	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);
94
95	Environment::GetSingleton()->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
96	Environment::GetSingleton()->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
97
98	Environment::GetSingleton()->GetIntValue("ViewCells.active", mNumActiveViewCells);
99	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
100	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.useClipPlane", mUseClipPlaneForViz);
101	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
102	Environment::GetSingleton()->GetBoolValue("ViewCells.evaluateViewCells", mEvaluateViewCells);
103	Environment::GetSingleton()->GetBoolValue("ViewCells.showVisualization", mShowVisualization);
104	Environment::GetSingleton()->GetIntValue("ViewCells.Filter.maxSize", mMaxFilterSize);
105	Environment::GetSingleton()->GetFloatValue("ViewCells.Filter.width", mFilterWidth);
106	Environment::GetSingleton()->GetIntValue("ViewCells.renderCostEvaluationType", mRenderCostEvaluationType);
107
108	Environment::GetSingleton()->GetBoolValue("ViewCells.exportBboxesForPvs", mExportBboxesForPvs);
109	Environment::GetSingleton()->GetBoolValue("ViewCells.exportPvs", mExportPvs);
110
111	char buf[100];
112	Environment::GetSingleton()->GetStringValue("ViewCells.samplingType", buf);
113
114
115	// sampling type for view cells construction samples
116	if (strcmp(buf, "box") == 0)
117	{
118	mSamplingType = Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
119	}
120	else if (strcmp(buf, "directional") == 0)
121	{
122	mSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
123	}
124	else if (strcmp(buf, "object_directional") == 0)
125	{
126	mSamplingType = Preprocessor::OBJECT_DIRECTION_BASED_DISTRIBUTION;
127	}
128	/*else if (strcmp(buf, "interior") == 0)
129	{
130	mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
131	}*/
132	else
133	{
134	Debug << "error! wrong sampling type" << endl;
135	exit(0);
136	}
137
138	// sampling type for evaluation samples
139	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf);
140
141	if (strcmp(buf, "box") == 0)
142	{
143	mEvaluationSamplingType = Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
144	}
145	else if (strcmp(buf, "directional") == 0)
146	{
147	mEvaluationSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION;
148	}
149	else if (strcmp(buf, "object_directional") == 0)
150	{
151	mEvaluationSamplingType = Preprocessor::OBJECT_DIRECTION_BASED_DISTRIBUTION;
152	}
153	/*else if (strcmp(buf, "interior") == 0)
154	{
155	mEvaluationSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION;
156	}*/
157	else
158	{
159	Debug << "error! wrong sampling type" << endl;
160	exit(0);
161	}
162
163	Environment::GetSingleton()->GetStringValue("ViewCells.renderCostEvaluationType", buf);
164
165	if (strcmp(buf, "perobject") == 0)
166	{
167	mRenderCostEvaluationType = ViewCellsManager::PER_OBJECT;
168	}
169	else if (strcmp(buf, "directional") == 0)
170	{
171	mRenderCostEvaluationType = ViewCellsManager::PER_TRIANGLE;
172	}
173	else
174	{
175	Debug << "error! wrong sampling type" << endl;
176	exit(0);
177	}
178
179	Environment::GetSingleton()->GetStringValue("ViewCells.Visualization.colorCode", buf);
180
181	if (strcmp(buf, "PVS") == 0)
182	mColorCode = 1;
183	else if (strcmp(buf, "MergedLeaves") == 0)
184	mColorCode = 2;
185	else if (strcmp(buf, "MergedTreeDiff") == 0)
186	mColorCode = 3;
187	else
188	mColorCode = 0;
189
190
191
192	Debug << "********** View Cells options *************" << endl;
193	Debug << "color code: " << mColorCode << endl;
194
195	Debug << "export rays: " << mExportRays << endl;
196	Debug << "export geometry: " << mExportGeometry << endl;
197	Debug << "max pvs ratio: " << mMaxPvsRatio << endl;
198
199	Debug << "prune empty view cells: " << mPruneEmptyViewCells << endl;
200
201	Debug << "process only valid view cells: " << mOnlyValidViewCells << endl;
202	Debug << "construction samples: " << mConstructionSamples << endl;
203	Debug << "post process samples: " << mPostProcessSamples << endl;
204	Debug << "post process use rays for merge: " << mUseRaysForMerge << endl;
205	Debug << "visualization samples: " << mVisualizationSamples << endl;
206	Debug << "construction samples per pass: " << mSamplesPerPass << endl;
207	Debug << "export to file: " << mExportViewCells << endl;
208
209	Debug << "active view cells: " << mNumActiveViewCells << endl;
210	Debug << "post process compress: " << mCompressViewCells << endl;
211	Debug << "visualization use clipPlane: " << mUseClipPlaneForViz << endl;
212	Debug << "post process merge: " << mMergeViewCells << endl;
213	Debug << "evaluate view cells: " << mEvaluateViewCells << endl;
214	Debug << "sampling type: " << mSamplingType << endl;
215	Debug << "render cost evaluation type: " << mRenderCostEvaluationType << endl;
216	Debug << "evaluation sampling type: " << mEvaluationSamplingType << endl;
217	Debug << "show visualization: " << mShowVisualization << endl;
218	Debug << "filter width: " << mFilterWidth << endl;
219	Debug << "sample after subdivision: " << SAMPLE_AFTER_SUBDIVISION << endl;
220
221	Debug << "export bounding boxes: " << mExportBboxesForPvs << endl;
222	Debug << "export pvs for view cells: " << mExportPvs << endl;
223
224	Debug << endl;
225	}
226
227
228	ViewCellsManager::~ViewCellsManager()
229	{
230	// HACK: if view cells tree does not
231	// handle view cells, we have to do it here
232	// question: rather create view cells resource manager?
233	if (!ViewCellsTreeConstructed())
234	{
235	CLEAR_CONTAINER(mViewCells);
236	}
237	//DEL_PTR(mViewCellsTree);
238	}
239
240
241	AxisAlignedBox3 ViewCellsManager::GetViewCellBox(ViewCell *vc)
242	{
243	Mesh *m = vc->GetMesh();
244
245	if (m) {
246	m->ComputeBoundingBox();
247	return m->mBox;
248	}
249
250	AxisAlignedBox3 box;
251
252	box.Initialize();
253
254	if (!vc->IsLeaf()) {
255	ViewCellInterior vci = (ViewCellInterior ) vc;
256
257	ViewCellContainer::iterator it = vci->mChildren.begin();
258	for (; it != vci->mChildren.end(); ++it) {
259	box.Include(GetViewCellBox(*it));
260	}
261	}
262
263	return box;
264	}
265
266
267	bool ViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
268	{
269	return false;
270	}
271
272
273	int ViewCellsManager::CastPassSamples(const int samplesPerPass,
274	const int sampleType,
275	VssRayContainer &passSamples) const
276	{
277	SimpleRayContainer simpleRays;
278
279	const long startTime = GetTime();
280
281	mPreprocessor->GenerateRays(samplesPerPass, sampleType, simpleRays);
282
283	Debug << "generated " << mInitialSamples << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
284
285	// shoot simple ray and add it to importance samples
286	mPreprocessor->CastRays(simpleRays, passSamples);
287
288	Debug << "cast " << mInitialSamples << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
289
290	return (int)passSamples.size();
291	}
292
293
294	/// helper function which destroys rays or copies them into the output ray container
295	inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
296	{
297	cout << "disposing samples ... ";
298	long startTime = GetTime();
299	int n = (int)rays.size();
300
301	if (outRays)
302	{
303	VssRayContainer::const_iterator it, it_end = rays.end();
304
305	for (it = rays.begin(); it != it_end; ++ it)
306	{
307	outRays->push_back(*it);
308	}
309	}
310	else
311	{
312	VssRayContainer::const_iterator it, it_end = rays.end();
313
314	for (it = rays.begin(); it != it_end; ++ it)
315	{
316	//(*it)->Unref();
317	if (!(*it)->IsActive())
318	delete (*it);
319	}
320	}
321
322	cout << "finished" << endl;
323	Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
324	}
325
326
327	int ViewCellsManager::Construct(Preprocessor preprocessor, VssRayContainer outRays)
328	{
329	mPreprocessor = preprocessor;
330
331	int numSamples = 0;
332
333	SimpleRayContainer simpleRays;
334	VssRayContainer initialSamples;
335
336	cout << "view cell construction: casting " << mInitialSamples << " initial samples ... ";
337
338	long startTime = GetTime();
339
340	//-- construction rays => we use uniform samples for this
341
342	CastPassSamples(mInitialSamples, mSamplingType, initialSamples);
343
344	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
345
346	// construct view cells
347	ConstructSubdivision(preprocessor->mObjects, initialSamples);
348
349	// initial samples count for overall samples ...
350	numSamples += mInitialSamples;
351
352	// rays can be passed or deleted
353	disposeRays(initialSamples, outRays);
354
355	cout << "time needed for initial construction: "
356	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
357
358	Debug << "time needed for initial construction: "
359	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
360
361	// take post processing time
362	startTime = GetTime();
363
364	// -- stats after 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	// traverse the view space subdivision
1791	CastLineSegment(origin, termination, viewcells);
1792
1793	if (storeViewCells)
1794	{ // copy viewcells memory efficiently
1795	ray.mViewCells.reserve(viewcells.size());
1796	ray.mViewCells = viewcells;
1797	}
1798
1799	ViewCellContainer::const_iterator it = viewcells.begin();
1800
1801	for (; it != viewcells.end(); ++ it)
1802	{
1803	ViewCell viewcell = it;
1804
1805	if (viewcell->GetValid())
1806	{
1807	// if ray not outside of view space
1808	float contribution;
1809	if (ray.mTerminationObject) {
1810	if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
1811	ray.mPdf,
1812	contribution))
1813	{
1814	++ ray.mPvsContribution;
1815	ray.mRelativePvsContribution += contribution;
1816	}
1817	}
1818	// for directional sampling it is important to count only contributions
1819	// made in one direction!!!
1820	// the other contributions of this sample will be counted for the oposite ray!
1821	#if SAMPLE_ORIGIN_OBJECTS
1822	if (ray.mOriginObject &&
1823	viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
1824	ray.mPdf,
1825	contribution))
1826	{
1827	++ ray.mPvsContribution;
1828	ray.mRelativePvsContribution += contribution;
1829	}
1830	#endif
1831	}
1832	}
1833
1834	// if addrays is true, sampled entities are stored in the pvs
1835	if (addRays)
1836	{
1837	for (it = viewcells.begin(); it != viewcells.end(); ++ it)
1838	{
1839	ViewCell viewcell = it;
1840
1841	if (viewcell->GetValid())
1842	{
1843	// if ray not outside of view space
1844
1845	// add new object to the pvs
1846	if (ray.mTerminationObject)
1847	{
1848	viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
1849	}
1850	#if SAMPLE_ORIGIN_OBJECTS
1851	if (ray.mOriginObject)
1852	{
1853	viewcell->GetPvs().AddSample(ray.mOriginObject, ray.mPdf);
1854	}
1855	#endif
1856	}
1857	}
1858	}
1859
1860	return ray.mRelativePvsContribution;
1861	}
1862
1863
1864	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
1865	const int maxSize,
1866	VssRayContainer &usedRays,
1867	VssRayContainer *savedRays) const
1868	{
1869	const int limit = min(maxSize, (int)sourceRays.size());
1870	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
1871
1872	VssRayContainer::const_iterator it, it_end = sourceRays.end();
1873	for (it = sourceRays.begin(); it != it_end; ++ it)
1874	{
1875	if (Random(1.0f) < prop)
1876	usedRays.push_back(*it);
1877	else if (savedRays)
1878	savedRays->push_back(*it);
1879	}
1880	}
1881
1882
1883	float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
1884	{
1885	return (float)mViewCellsTree->GetPvsSize(viewCell);
1886	}
1887
1888
1889	float ViewCellsManager::GetAccVcArea()
1890	{
1891	// if already computed
1892	if (mTotalAreaValid)
1893	{
1894	return mTotalArea;
1895	}
1896
1897	mTotalArea = 0;
1898	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1899
1900	for (it = mViewCells.begin(); it != it_end; ++ it)
1901	{
1902	//Debug << "area: " << GetArea(*it);
1903	mTotalArea += GetArea(*it);
1904	}
1905
1906	mTotalAreaValid = true;
1907
1908	return mTotalArea;
1909	}
1910
1911
1912	void ViewCellsManager::PrintStatistics(ostream &s) const
1913	{
1914	s << mCurrentViewCellsStats << endl;
1915	}
1916
1917
1918	void ViewCellsManager::CreateUniqueViewCellIds()
1919	{
1920	if (ViewCellsTreeConstructed())
1921	{
1922	mViewCellsTree->CreateUniqueViewCellsIds();
1923	}
1924	else // no view cells tree, handle view cells "myself"
1925	{
1926	for (int i = 0; i < (int)mViewCells.size(); ++ i)
1927	{
1928	mViewCells[i]->SetId(i);
1929	}
1930	}
1931	}
1932
1933
1934	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter) const
1935	{
1936	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1937
1938	for (it = mViewCells.begin(); it != it_end; ++ it)
1939	{
1940	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
1941	{
1942	ExportColor(exporter, *it);
1943
1944	ExportViewCellGeometry(exporter, *it,
1945	mUseClipPlaneForViz ? &mClipPlane : NULL);
1946	}
1947	}
1948	}
1949
1950
1951	void ViewCellsManager::CreateViewCellMeshes()
1952	{
1953	// convert to meshes
1954	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1955
1956	for (it = mViewCells.begin(); it != it_end; ++ it)
1957	{
1958	if (!(*it)->GetMesh())
1959	{
1960	CreateMesh(*it);
1961	}
1962	}
1963	}
1964
1965
1966	bool ViewCellsManager::ExportViewCells(const string filename,
1967	const bool exportPvs,
1968	const ObjectContainer &objects)
1969	{
1970	return false;
1971	}
1972
1973
1974	void ViewCellsManager::CollectViewCells(const int n)
1975	{
1976	mNumActiveViewCells = n;
1977	mViewCells.clear();
1978	CollectViewCells();
1979	}
1980
1981
1982	void ViewCellsManager::SetViewCellsActive()
1983	{
1984	// collect leaf view cells and set the pointers to the currently
1985	// active view cells
1986	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1987
1988	for (it = mViewCells.begin(); it != it_end; ++ it)
1989	{
1990	ViewCellContainer leaves;
1991	mViewCellsTree->CollectLeaves(*it, leaves);
1992
1993	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
1994	for (lit = mViewCells.begin(); lit != lit_end; ++ lit)
1995	{
1996	dynamic_cast<ViewCellLeaf >(lit)->SetActiveViewCell(*it);
1997	}
1998	}
1999	}
2000
2001
2002	int ViewCellsManager::GetMaxFilterSize() const
2003	{
2004	return mMaxFilterSize;
2005	}
2006
2007
2008	static const bool USE_ASCII = true;
2009
2010
2011	bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2012	const ObjectContainer &objects) const
2013	{
2014	ObjectContainer::const_iterator it, it_end = objects.end();
2015
2016	if (USE_ASCII)
2017	{
2018	ofstream boxesOut(filename.c_str());
2019	if (!boxesOut.is_open())
2020	return false;
2021
2022	for (it = objects.begin(); it != it_end; ++ it)
2023	{
2024	MeshInstance mi = dynamic_cast<MeshInstance >(*it);
2025	const AxisAlignedBox3 box = mi->GetBox();
2026
2027	boxesOut << mi->GetId() << " "
2028	<< box.Min().x << " "
2029	<< box.Min().y << " "
2030	<< box.Min().z << " "
2031	<< box.Max().x << " "
2032	<< box.Max().y << " "
2033	<< box.Max().z << endl;
2034	}
2035
2036	boxesOut.close();
2037	}
2038	else
2039	{
2040	ofstream boxesOut(filename.c_str(), ios::binary);
2041
2042	if (!boxesOut.is_open())
2043	return false;
2044
2045	for (it = objects.begin(); it != it_end; ++ it)
2046	{
2047	MeshInstance mi = dynamic_cast<MeshInstance >(*it);
2048	const AxisAlignedBox3 box = mi->GetBox();
2049	Vector3 bmin = box.Min();
2050	Vector3 bmax = box.Max();
2051	int id = mi->GetId();
2052
2053	boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2054	boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2055	boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2056	}
2057
2058	boxesOut.close();
2059	}
2060
2061	return true;
2062	}
2063
2064
2065	bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2066	IndexedBoundingBoxContainer &boxes) const
2067	{
2068	Vector3 bmin, bmax;
2069	int id;
2070
2071	if (USE_ASCII)
2072	{
2073	ifstream boxesIn(filename.c_str());
2074
2075	if (!boxesIn.is_open())
2076	{
2077	cout << "failed to open file " << filename << endl;
2078	return false;
2079	}
2080
2081	string buf;
2082	while (!(getline(boxesIn, buf)).eof())
2083	{
2084	sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2085	&id, &bmin.x, &bmin.y, &bmin.z,
2086	&bmax.x, &bmax.y, &bmax.z);
2087
2088	AxisAlignedBox3 box(bmin, bmax);
2089	// MeshInstance *mi = new MeshInstance();
2090	// HACK: set bounding box to new box
2091	//mi->mBox = box;
2092
2093	boxes.push_back(IndexedBoundingBox(id, box));
2094	}
2095
2096	boxesIn.close();
2097	}
2098	else
2099	{
2100	ifstream boxesIn(filename.c_str(), ios::binary);
2101
2102	if (!boxesIn.is_open())
2103	return false;
2104
2105	while (1)
2106	{
2107	boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2108	boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2109	boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2110
2111	if (boxesIn.eof())
2112	break;
2113
2114
2115	AxisAlignedBox3 box(bmin, bmax);
2116	MeshInstance *mi = new MeshInstance(NULL);
2117
2118	// HACK: set bounding box to new box
2119	//mi->mBox = box;
2120	//boxes.push_back(mi);
2121	boxes.push_back(IndexedBoundingBox(id, box));
2122	}
2123
2124	boxesIn.close();
2125	}
2126
2127	return true;
2128	}
2129
2130
2131	float ViewCellsManager::GetFilterWidth()
2132	{
2133	return mFilterWidth;
2134	}
2135
2136
2137	float ViewCellsManager::GetAbsFilterWidth()
2138	{
2139	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2140	}
2141
2142
2143	void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2144	const int pvsSize,
2145	const int entriesInPvs) const
2146	{
2147	vc->mPvsSize = pvsSize;
2148	vc->mEntriesInPvs = entriesInPvs;
2149
2150	vc->mPvsSizeValid = true;
2151	}
2152
2153
2154	void
2155	ViewCellsManager::ApplyFilter(ViewCell *viewCell,
2156	KdTree *kdTree,
2157	const float viewSpaceFilterSize,
2158	const float spatialFilterSize,
2159	ObjectPvs &pvs
2160	)
2161	{
2162	// extend the pvs of the viewcell by pvs of its neighbors
2163	// and apply spatial filter by including all neighbors of the objects
2164	// in the pvs
2165
2166	// get all viewcells intersecting the viewSpaceFilterBox
2167	// and compute the pvs union
2168
2169	//Vector3 center = viewCell->GetBox().Center();
2170	// Vector3 center = m->mBox.Center();
2171
2172	// AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
2173	// center + Vector3(viewSpaceFilterSize/2));
2174	if (!ViewCellsConstructed())
2175	return;
2176
2177	if (viewSpaceFilterSize >= 0.0f) {
2178
2179	bool usePrVS = false;
2180
2181	if (!usePrVS) {
2182	AxisAlignedBox3 box = GetViewCellBox(viewCell);
2183	box.Enlarge(Vector3(viewSpaceFilterSize/2));
2184
2185	ViewCellContainer viewCells;
2186	ComputeBoxIntersections(box, viewCells);
2187
2188	// cout<<"box="<<box<<endl;
2189	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
2190
2191	int i;
2192	for (i=0; it != it_end; ++ it, ++ i) {
2193	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
2194	pvs.Merge((*it)->GetPvs());
2195	}
2196	} else {
2197	PrVs prvs;
2198	AxisAlignedBox3 box = GetViewCellBox(viewCell);
2199
2200	// mViewCellsManager->SetMaxFilterSize(1);
2201	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
2202	pvs = prvs.mViewCell->GetPvs();
2203	DeleteLocalMergeTree(prvs.mViewCell);
2204	}
2205	} else
2206	pvs = viewCell->GetPvs();
2207
2208	if (spatialFilterSize >=0.0f)
2209	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
2210
2211	}
2212
2213
2214
2215	void
2216	ViewCellsManager::ApplyFilter(KdTree *kdTree,
2217	const float relViewSpaceFilterSize,
2218	const float relSpatialFilterSize
2219	)
2220	{
2221
2222	if (!ViewCellsConstructed())
2223	return;
2224
2225	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2226
2227	ObjectPvs *newPvs;
2228	newPvs = new ObjectPvs[mViewCells.size()];
2229
2230	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
2231	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
2232
2233	int i;
2234	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2235	ApplyFilter(*it,
2236	kdTree,
2237	viewSpaceFilterSize,
2238	spatialFilterSize,
2239	newPvs[i]
2240	);
2241	}
2242
2243	// now replace all pvss
2244	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
2245
2246	ObjectPvs &pvs = (*it)->GetPvs();
2247	pvs.Clear();
2248	pvs = newPvs[i];
2249	newPvs[i].Clear();
2250	}
2251
2252	delete [] newPvs;
2253	}
2254
2255
2256
2257
2258	void
2259	ViewCellsManager::ApplySpatialFilter(
2260	KdTree *kdTree,
2261	const float spatialFilterSize,
2262	ObjectPvs &pvs
2263	)
2264	{
2265	// now compute a new Pvs by including also objects intersecting the
2266	// extended boxes of visible objects
2267
2268	Intersectable::NewMail();
2269
2270	ObjectPvsMap::const_iterator oi;
2271
2272	for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++ oi)
2273	{
2274	Intersectable object = (oi).first;
2275	object->Mail();
2276	}
2277
2278	ObjectPvs nPvs;
2279	int nPvsSize = 0;
2280	// now go through the pvs again
2281	for (oi = pvs.mEntries.begin(); oi != pvs.mEntries.end(); ++oi) {
2282	Intersectable object = (oi).first;
2283
2284	// Vector3 center = object->GetBox().Center();
2285	// AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
2286	// center + Vector3(spatialFilterSize/2));
2287
2288	AxisAlignedBox3 box = object->GetBox();
2289	box.Enlarge(Vector3(spatialFilterSize/2));
2290
2291	ObjectContainer objects;
2292
2293	// $$ warning collect objects takes only unmailed ones!
2294	kdTree->CollectObjects(box,
2295	objects);
2296	// cout<<"collected objects="<<objects.size()<<endl;
2297	ObjectContainer::const_iterator noi = objects.begin();
2298	for (; noi != objects.end(); ++noi) {
2299	Intersectable o = noi;
2300	// $$ JB warning: pdfs are not correct at this point!
2301	nPvs.AddSample(o, Limits::Small);
2302	nPvsSize++;
2303	}
2304	}
2305	// cout<<"nPvs size = "<<nPvsSize<<endl;
2306	pvs.Merge(nPvs);
2307	}
2308
2309
2310	void ViewCellsManager::ExportColor(Exporter exporter, ViewCell vc) const
2311	{
2312	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
2313
2314	float importance = 0;
2315	static Material m;
2316
2317	switch (mColorCode)
2318	{
2319	case 0: // Random
2320	{
2321	if (vcValid)
2322	{
2323	m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
2324	m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
2325	m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
2326	}
2327	else
2328	{
2329	m.mDiffuseColor.r = 0.0f;
2330	m.mDiffuseColor.g = 1.0f;
2331	m.mDiffuseColor.b = 0.0f;
2332	}
2333
2334	exporter->SetForcedMaterial(m);
2335	return;
2336	}
2337
2338	case 1: // pvs
2339	{
2340	if (mCurrentViewCellsStats.maxPvs)
2341	{
2342	importance =
2343	(float)mViewCellsTree->GetPvsSize(vc) /
2344	(float)mCurrentViewCellsStats.maxPvs;
2345	}
2346	}
2347	break;
2348	case 2: // merges
2349	{
2350	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
2351	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
2352	}
2353	break;
2354	#if 0
2355	case 3: // merge tree differene
2356	{
2357	importance = (float)GetMaxTreeDiff(vc) /
2358	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
2359
2360	}
2361	break;
2362	#endif
2363	default:
2364	break;
2365	}
2366
2367	// special color code for invalid view cells
2368	m.mDiffuseColor.r = importance;
2369	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
2370	m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
2371
2372	//Debug << "importance: " << importance << endl;
2373	exporter->SetForcedMaterial(m);
2374	}
2375
2376
2377	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2378	vector<MergeCandidate> &candidates)
2379	{
2380	// implemented in subclasses
2381	}
2382
2383
2384	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
2385	{
2386	// terminate traversal
2387	if (root->IsLeaf())
2388	{
2389	// we assume that pvs is explicitly stored in leaves
2390	pvs = root->GetPvs();
2391	UpdateScalarPvsSize(root, pvs.CountObjectsInPvs(), pvs.GetSize());
2392
2393	return;
2394	}
2395
2396	//-- interior node => propagate pvs up
2397	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
2398	interior->GetPvs().Clear();
2399	pvs.Clear();
2400	vector<ObjectPvs> pvsList;
2401
2402	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
2403
2404	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
2405	{
2406	ObjectPvs objPvs;
2407
2408	//-- recursivly compute child pvss
2409	UpdatePvsForEvaluation(*vit, objPvs);
2410
2411	// store pvs in vector
2412	pvsList.push_back(objPvs);
2413	}
2414
2415	#if 1
2416	Intersectable::NewMail();
2417
2418	//-- faster way of computing pvs:
2419	// construct merged pvs by adding
2420	// and only those of the next pvs which were not mailed.
2421	// note: sumpdf is not correct!!
2422	vector<ObjectPvs>::iterator oit = pvsList.begin();
2423
2424	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
2425	{
2426	ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
2427
2428	for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
2429	{
2430	Intersectable intersect = (pit).first;
2431
2432	if (!intersect->Mailed())
2433	{
2434	pvs.AddSample(intersect, (*pit).second.mSumPdf);
2435	intersect->Mail();
2436	}
2437	}
2438	}
2439
2440	// store pvs in this node
2441	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
2442	{
2443	interior->SetPvs(pvs);
2444	}
2445
2446	// set new pvs size
2447	UpdateScalarPvsSize(interior, pvs.CountObjectsInPvs(), pvs.GetSize());
2448
2449
2450	#else // really merge cells: slow put sumPdf is correct
2451	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
2452	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
2453	#endif
2454	}
2455
2456
2457
2458	/*******************************************************************/
2459	/* BspViewCellsManager implementation */
2460	/*******************************************************************/
2461
2462
2463	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
2464	ViewCellsManager(vcTree), mBspTree(bspTree)
2465	{
2466	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
2467	mBspTree->SetViewCellsManager(this);
2468	mBspTree->mViewCellsTree = mViewCellsTree;
2469	}
2470
2471
2472	bool BspViewCellsManager::ViewCellsConstructed() const
2473	{
2474	return mBspTree->GetRoot() != NULL;
2475	}
2476
2477
2478	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
2479	{
2480	return new BspViewCell(mesh);
2481	}
2482
2483
2484	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2485	const VssRayContainer &rays)
2486	{
2487	// if view cells were already constructed
2488	if (ViewCellsConstructed())
2489	return 0;
2490
2491	int sampleContributions = 0;
2492
2493	// construct view cells using the collected samples
2494	RayContainer constructionRays;
2495	VssRayContainer savedRays;
2496
2497	const int limit = min(mInitialSamples, (int)rays.size());
2498
2499	VssRayContainer::const_iterator it, it_end = rays.end();
2500
2501	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
2502
2503	for (it = rays.begin(); it != it_end; ++ it)
2504	{
2505	if (Random(1.0f) < prop)
2506	constructionRays.push_back(new Ray((it)));
2507	else
2508	savedRays.push_back(*it);
2509	}
2510
2511	if (mViewCells.empty())
2512	{
2513	// no view cells loaded
2514	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
2515	// collect final view cells
2516	mBspTree->CollectViewCells(mViewCells);
2517	}
2518	else
2519	{
2520	mBspTree->Construct(mViewCells);
2521	}
2522
2523	// destroy rays created only for construction
2524	CLEAR_CONTAINER(constructionRays);
2525
2526	Debug << mBspTree->GetStatistics() << endl;
2527
2528	//EvaluateViewCellsStats();
2529	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
2530
2531	// recast rest of the rays
2532	if (SAMPLE_AFTER_SUBDIVISION)
2533	ComputeSampleContributions(savedRays, true, false);
2534
2535	// real meshes are contructed at this stage
2536	if (0)
2537	{
2538	cout << "finalizing view cells ... ";
2539	FinalizeViewCells(true);
2540	cout << "finished" << endl;
2541	}
2542
2543	return sampleContributions;
2544	}
2545
2546
2547	void BspViewCellsManager::CollectViewCells()
2548	{
2549	// view cells tree constructed
2550	if (!ViewCellsTreeConstructed())
2551	{
2552	mBspTree->CollectViewCells(mViewCells);
2553	}
2554	else
2555	{
2556	// we can use the view cells tree hierarchy to get the right set
2557	mViewCellsTree->CollectBestViewCellSet(mViewCells,
2558	mNumActiveViewCells);
2559	}
2560	}
2561
2562
2563	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
2564	{
2565	// compute view cell area as subsititute for probability
2566	if (1)
2567	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
2568	else
2569	return GetArea(viewCell) / GetAccVcArea();
2570	}
2571
2572
2573
2574	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
2575	const Vector3 &termination,
2576	ViewCellContainer &viewcells)
2577	{
2578	return mBspTree->CastLineSegment(origin, termination, viewcells);
2579	}
2580
2581
2582	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
2583	const VssRayContainer &rays)
2584	{
2585	if (!ViewCellsConstructed())
2586	{
2587	Debug << "view cells not constructed" << endl;
2588	return 0;
2589	}
2590
2591	// view cells already finished before post processing step (i.e. because they were loaded)
2592	if (mViewCellsFinished)
2593	{
2594	FinalizeViewCells(true);
2595	EvaluateViewCellsStats();
2596
2597	return 0;
2598	}
2599
2600	//-- post processing of bsp view cells
2601
2602	int vcSize = 0;
2603	int pvsSize = 0;
2604
2605	//-- merge view cells
2606
2607	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
2608	long startTime = GetTime();
2609
2610	VssRayContainer postProcessRays;
2611	GetRaySets(rays, mPostProcessSamples, postProcessRays);
2612
2613	if (mMergeViewCells)
2614	{
2615	cout << "constructing visibility based merge tree" << endl;
2616	mViewCellsTree->ConstructMergeTree(rays, objects);
2617	}
2618	else
2619	{
2620	cout << "constructing spatial merge tree" << endl;
2621
2622	// create spatial merge hierarchy
2623	ViewCell *root = ConstructSpatialMergeTree(mBspTree->GetRoot());
2624	mViewCellsTree->SetRoot(root);
2625
2626	// compute pvs
2627	ObjectPvs pvs;
2628	UpdatePvsForEvaluation(root, pvs);
2629	}
2630
2631	// export statistics after merge
2632	if (1)
2633	{
2634	char mstats[100];
2635	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
2636	mViewCellsTree->ExportStats(mstats);
2637	}
2638
2639	//-- stats and visualizations
2640	cout << "finished" << endl;
2641	cout << "merged view cells in "
2642	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2643
2644	Debug << "Postprocessing: Merged view cells in "
2645	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
2646
2647
2648	//-- visualization and statistics
2649	// reset view cells and stats
2650	ResetViewCells();
2651	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
2652
2653	// save color code
2654	const int savedColorCode = mColorCode;
2655
2656	//BspLeaf::NewMail();
2657	if (1) // export merged view cells
2658	{
2659	mColorCode = 0;
2660
2661	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
2662
2663
2664	cout << "exporting view cells after merge ... ";
2665
2666	if (exporter)
2667	{
2668	if (mExportGeometry)
2669	exporter->ExportGeometry(objects);
2670
2671	//exporter->SetWireframe();
2672	exporter->SetFilled();
2673	ExportViewCellsForViz(exporter);
2674
2675
2676	delete exporter;
2677	}
2678	cout << "finished" << endl;
2679	}
2680
2681	if (1) // export merged view cells using pvs color coding
2682	{
2683	mColorCode = 1;
2684
2685	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
2686
2687	cout << "exporting view cells after merge (pvs size) ... ";
2688
2689	if (exporter)
2690	{
2691	//exporter->SetWireframe();
2692	//exporter->SetForcedMaterial(RandomMaterial());
2693
2694	if (mExportGeometry)
2695	exporter->ExportGeometry(objects);
2696
2697	//exporter->SetWireframe();
2698	exporter->SetFilled();
2699	ExportViewCellsForViz(exporter);
2700
2701	delete exporter;
2702	}
2703	cout << "finished" << endl;
2704	}
2705
2706	// only for debugging purpose: test if the subdivision is valid
2707	if (0) TestSubdivision();
2708
2709	mColorCode = savedColorCode;
2710
2711	// compute final meshes and volume / area
2712	if (1) FinalizeViewCells(true);
2713
2714	// write view cells to disc
2715	if (mExportViewCells)
2716	{
2717	char filename[100];
2718	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
2719	ExportViewCells(filename, mExportPvs, objects);
2720	}
2721
2722	// export bounding boxes
2723	if (0 && mExportBboxesForPvs)
2724	{
2725	char filename[100];
2726	Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
2727	ExportBoundingBoxes(filename, objects);
2728	}
2729
2730
2731	return 0;
2732	}
2733
2734
2735	BspViewCellsManager::~BspViewCellsManager()
2736	{
2737	}
2738
2739
2740	int BspViewCellsManager::GetType() const
2741	{
2742	return BSP;
2743	}
2744
2745
2746	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
2747	const VssRayContainer &sampleRays)
2748	{
2749	if (!ViewCellsConstructed())
2750	return;
2751
2752	int savedColorCode = mColorCode;
2753
2754
2755	if (1) // export final view cells
2756	{
2757	mColorCode = 1; // hack color code
2758	Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
2759
2760	cout << "exporting view cells after merge (pvs size) ... ";
2761
2762	if (exporter)
2763	{
2764	//exporter->SetWireframe();
2765
2766	if (mExportGeometry)
2767	exporter->ExportGeometry(objects);
2768
2769	//exporter->SetFilled();
2770	const bool b = mUseClipPlaneForViz;
2771	mUseClipPlaneForViz = false;
2772
2773	ExportViewCellsForViz(exporter);
2774
2775	mUseClipPlaneForViz = b;
2776	delete exporter;
2777	}
2778	cout << "finished" << endl;
2779	}
2780
2781	mColorCode = savedColorCode;
2782
2783	//-- visualization of the BSP splits
2784	bool exportSplits = false;
2785	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
2786
2787	if (exportSplits)
2788	{
2789	cout << "exporting splits ... ";
2790	ExportSplits(objects);
2791	cout << "finished" << endl;
2792	}
2793
2794	// export single view cells
2795	ExportBspPvs(objects);
2796	}
2797
2798
2799	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
2800	{
2801	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
2802
2803	if (exporter)
2804	{
2805	//exporter->SetFilled();
2806
2807	if (mExportGeometry)
2808	exporter->ExportGeometry(objects);
2809
2810	Material m;
2811	m.mDiffuseColor = RgbColor(1, 0, 0);
2812	exporter->SetForcedMaterial(m);
2813	exporter->SetWireframe();
2814
2815	exporter->ExportBspSplits(*mBspTree, true);
2816
2817	//NOTE: take forced material, else big scenes cannot be viewed
2818	m.mDiffuseColor = RgbColor(0, 1, 0);
2819	exporter->SetForcedMaterial(m);
2820	//exporter->ResetForcedMaterial();
2821
2822	delete exporter;
2823	}
2824	}
2825
2826
2827	void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
2828	{
2829	const int leafOut = 10;
2830
2831	ViewCell::NewMail();
2832
2833	//-- some rays for output
2834	const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
2835
2836	cout << "visualization using " << mVisualizationSamples << " samples" << endl;
2837	Debug << "\nOutput view cells: " << endl;
2838
2839	// sort view cells in order to find the largest view cells
2840	if (0)
2841	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
2842
2843	int limit = min(leafOut, (int)mViewCells.size());
2844
2845	for (int i = 0; i < limit; ++ i)
2846	{
2847	cout << "creating output for view cell " << i << " ... ";
2848	VssRayContainer vcRays;
2849	Intersectable::NewMail();
2850	ViewCell *vc;
2851
2852	if (0)
2853	vc = mViewCells[i];
2854	else
2855	vc = mViewCells[Random((int)mViewCells.size())];
2856
2857	cout << "creating output for view cell " << i << " ... ";
2858
2859	if(0)
2860	{
2861	// check whether we can add the current ray to the output rays
2862	for (int k = 0; k < raysOut; ++ k)
2863	{
2864	BspRay *ray = mBspRays[k];
2865	for (int j = 0; j < (int)ray->intersections.size(); ++ j)
2866	{
2867	BspLeaf *leaf = ray->intersections[j].mLeaf;
2868	if (vc == leaf->GetViewCell())
2869	vcRays.push_back(ray->vssRay);
2870	}
2871	}
2872	}
2873
2874	//bspLeaves[j]->Mail();
2875	char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
2876
2877	Exporter *exporter = Exporter::GetExporter(s);
2878
2879	exporter->SetWireframe();
2880
2881	Material m;//= RandomMaterial();
2882	m.mDiffuseColor = RgbColor(0, 1, 0);
2883	exporter->SetForcedMaterial(m);
2884
2885	ExportViewCellGeometry(exporter, vc);
2886
2887	// export rays piercing this view cell
2888	exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
2889
2890	m.mDiffuseColor = RgbColor(1, 0, 0);
2891	exporter->SetForcedMaterial(m);
2892
2893	ObjectPvsMap::const_iterator it,
2894	it_end = vc->GetPvs().mEntries.end();
2895
2896	exporter->SetFilled();
2897
2898	// output PVS of view cell
2899	for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
2900	{
2901	Intersectable intersect = (it).first;
2902
2903	if (!intersect->Mailed())
2904	{
2905	Material m = RandomMaterial();
2906	exporter->SetForcedMaterial(m);
2907
2908	exporter->ExportIntersectable(intersect);
2909	intersect->Mail();
2910	}
2911	}
2912
2913	DEL_PTR(exporter);
2914	cout << "finished" << endl;
2915	}
2916
2917	Debug << endl;
2918	}
2919
2920
2921	void BspViewCellsManager::TestSubdivision()
2922	{
2923	ViewCellContainer leaves;
2924	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
2925
2926	ViewCellContainer::const_iterator it, it_end = leaves.end();
2927
2928	const float vol = mViewSpaceBox.GetVolume();
2929	float subdivVol = 0;
2930	float newVol = 0;
2931
2932	for (it = leaves.begin(); it != it_end; ++ it)
2933	{
2934	BspNodeGeometry geom;
2935	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
2936	mBspTree->ConstructGeometry(leaf, geom);
2937
2938	const float lVol = geom.GetVolume();
2939
2940	newVol += lVol;
2941	subdivVol += (*it)->GetVolume();
2942
2943	float thres = 0.9f;
2944	if ((lVol < ((it)->GetVolume() thres)) \|\|
2945	(lVol * thres > ((*it)->GetVolume())))
2946	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
2947	}
2948
2949	Debug << "exact volume: " << vol << endl;
2950	Debug << "subdivision volume: " << subdivVol << endl;
2951	Debug << "new volume: " << newVol << endl;
2952	}
2953
2954
2955	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
2956	ViewCell *vc,
2957	const AxisAlignedPlane *clipPlane) const
2958	{
2959	// export mesh if available
2960	if (vc->GetMesh())
2961	{
2962	exporter->ExportMesh(vc->GetMesh());
2963	return;
2964	}
2965	// otherwise construct from leaves
2966	if (clipPlane)
2967	{
2968	const Plane3 plane = clipPlane->GetPlane();
2969
2970	ViewCellContainer leaves;
2971	mViewCellsTree->CollectLeaves(vc, leaves);
2972	ViewCellContainer::const_iterator it, it_end = leaves.end();
2973
2974	for (it = leaves.begin(); it != it_end; ++ it)
2975	{
2976	BspNodeGeometry geom;
2977
2978	BspNodeGeometry front;
2979	BspNodeGeometry back;
2980
2981	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
2982	mBspTree->ConstructGeometry(leaf, geom);
2983
2984	const float eps = 0.00000001f;
2985	const int cf = geom.Side(plane, eps);
2986
2987	if (cf == -1)
2988	{
2989	exporter->ExportPolygons(geom.GetPolys());
2990	}
2991	else if (cf == 0)
2992	{
2993	geom.SplitGeometry(front,
2994	back,
2995	plane,
2996	mViewSpaceBox,
2997	eps);
2998
2999	//Debug << "geo size: " << geom.Size() << endl;
3000	//Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;
3001	if (back.Valid())
3002	{
3003	exporter->ExportPolygons(back.GetPolys());
3004	}
3005	}
3006	}
3007	}
3008	else
3009	{
3010	BspNodeGeometry geom;
3011	mBspTree->ConstructGeometry(vc, geom);
3012
3013	exporter->ExportPolygons(geom.GetPolys());
3014	}
3015	}
3016
3017
3018	void BspViewCellsManager::CreateMesh(ViewCell *vc)
3019	{
3020	// delete previous mesh
3021	///DEL_PTR(vc->GetMesh());
3022	BspNodeGeometry geom;
3023	mBspTree->ConstructGeometry(vc, geom);
3024
3025	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
3026
3027	IncludeNodeGeomInMesh(geom, *mesh);
3028	vc->SetMesh(mesh);
3029	}
3030
3031
3032	void BspViewCellsManager::Finalize(ViewCell *viewCell,
3033	const bool createMesh)
3034	{
3035	float area = 0;
3036	float volume = 0;
3037
3038	ViewCellContainer leaves;
3039	mViewCellsTree->CollectLeaves(viewCell, leaves);
3040
3041	ViewCellContainer::const_iterator it, it_end = leaves.end();
3042
3043	for (it = leaves.begin(); it != it_end; ++ it)
3044	{
3045	BspNodeGeometry geom;
3046	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
3047	mBspTree->ConstructGeometry(leaf, geom);
3048
3049	const float lVol = geom.GetVolume();
3050	const float lArea = geom.GetArea();
3051
3052	//(*it)->SetVolume(vol);
3053	//(*it)->SetArea(area);
3054
3055	area += lArea;
3056	volume += lVol;
3057
3058	CreateMesh(*it);
3059	}
3060
3061	viewCell->SetVolume(volume);
3062	viewCell->SetArea(area);
3063	}
3064
3065
3066	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
3067	{
3068	if (!ViewCellsConstructed())
3069	return NULL;
3070
3071	if (!mViewSpaceBox.IsInside(point))
3072	return NULL;
3073
3074	return mBspTree->GetViewCell(point);
3075	}
3076
3077
3078	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3079	vector<MergeCandidate> &candidates)
3080	{
3081	cout << "collecting merge candidates ... " << endl;
3082
3083	if (mUseRaysForMerge)
3084	{
3085	mBspTree->CollectMergeCandidates(rays, candidates);
3086	}
3087	else
3088	{
3089	vector<BspLeaf *> leaves;
3090	mBspTree->CollectLeaves(leaves);
3091	mBspTree->CollectMergeCandidates(leaves, candidates);
3092	}
3093
3094	cout << "fininshed collecting candidates" << endl;
3095	}
3096
3097
3098
3099	bool BspViewCellsManager::ExportViewCells(const string filename,
3100	const bool exportPvs,
3101	const ObjectContainer &objects)
3102	{
3103	#if TODO
3104	cout << "exporting view cells to xml ... ";
3105	std::ofstream stream;
3106
3107	// for output we need unique ids for each view cell
3108	CreateUniqueViewCellIds();
3109
3110
3111	stream.open(filename.c_str());
3112	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3113	stream << "<VisibilitySolution>" << endl;
3114
3115	//-- the view space bounding box
3116	stream << "<ViewSpaceBox"
3117	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3118	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
3119
3120	//-- the type of the view cells hierarchy
3121
3122	// NOTE: load in vsp bsp here because bsp and vsp bsp can use same tree and vsp bsp is bug free
3123	stream << "<Hierarchy name=\"vspBspTree\" >" << endl;
3124
3125	//-- load the view cells itself, i.e., the ids and the pvs
3126	stream << "<ViewCells>" << endl;
3127
3128	mViewCellsTree->Export(stream, exportPvs);
3129
3130	stream << "</ViewCells>" << endl;
3131
3132	//-- load the hierarchy
3133	stream << "<Hierarchy>" << endl;
3134	mBspTree->Export(stream);
3135	stream << endl << "</Hierarchy>" << endl;
3136
3137	stream << "</VisibilitySolution>" << endl;
3138	stream.close();
3139
3140	cout << "finished" << endl;
3141	#endif
3142	return true;
3143	}
3144
3145
3146	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
3147	{
3148	// terminate recursion
3149	if (root->IsLeaf())
3150	{
3151	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
3152	leaf->GetViewCell()->SetMergeCost(0.0f);
3153	return leaf->GetViewCell();
3154	}
3155
3156	BspInterior interior = dynamic_cast<BspInterior >(root);
3157	ViewCellInterior *viewCellInterior = new ViewCellInterior();
3158
3159	// evaluate merge cost for priority traversal
3160	float mergeCost = 1.0f / (float)root->mTimeStamp;
3161	viewCellInterior->SetMergeCost(mergeCost);
3162
3163	float volume = 0;
3164
3165	BspNode *front = interior->GetFront();
3166	BspNode *back = interior->GetBack();
3167
3168
3169	//-- recursivly compute child hierarchies
3170	ViewCell *backVc = ConstructSpatialMergeTree(back);
3171	ViewCell *frontVc = ConstructSpatialMergeTree(front);
3172
3173
3174	viewCellInterior->SetupChildLink(backVc);
3175	viewCellInterior->SetupChildLink(frontVc);
3176
3177	volume += backVc->GetVolume();
3178	volume += frontVc->GetVolume();
3179
3180	viewCellInterior->SetVolume(volume);
3181
3182	return viewCellInterior;
3183	}
3184
3185
3186	/************************************************************************/
3187	/* KdViewCellsManager implementation */
3188	/************************************************************************/
3189
3190
3191
3192	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
3193	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
3194	{
3195	}
3196
3197
3198	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
3199	{
3200	// compute view cell area / volume as subsititute for probability
3201	if (0)
3202	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
3203	else
3204	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3205	}
3206
3207
3208
3209
3210	void KdViewCellsManager::CollectViewCells()
3211	{
3212	//mKdTree->CollectViewCells(mViewCells); TODO
3213	}
3214
3215
3216	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3217	const VssRayContainer &rays)
3218	{
3219	// if view cells already constructed
3220	if (ViewCellsConstructed())
3221	return 0;
3222
3223	mKdTree->Construct();
3224
3225	mTotalAreaValid = false;
3226	// create the view cells
3227	mKdTree->CreateAndCollectViewCells(mViewCells);
3228
3229	// cast rays
3230	ComputeSampleContributions(rays, true, false);
3231
3232	EvaluateViewCellsStats();
3233	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3234
3235	return 0;
3236	}
3237
3238
3239	bool KdViewCellsManager::ViewCellsConstructed() const
3240	{
3241	return mKdTree->GetRoot() != NULL;
3242	}
3243
3244
3245	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
3246	const VssRayContainer &rays)
3247	{
3248	return 0;
3249	}
3250
3251
3252	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
3253	const VssRayContainer &sampleRays)
3254	{
3255	if (!ViewCellsConstructed())
3256	return;
3257
3258	// using view cells instead of the kd PVS of objects
3259	const bool useViewCells = true;
3260	bool exportRays = false;
3261
3262	int limit = min(mVisualizationSamples, (int)sampleRays.size());
3263	const int pvsOut = min((int)objects.size(), 10);
3264	VssRayContainer *rays = new VssRayContainer[pvsOut];
3265
3266	if (useViewCells)
3267	{
3268	const int leafOut = 10;
3269
3270	ViewCell::NewMail();
3271
3272	//-- some rays for output
3273	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
3274	Debug << "visualization using " << raysOut << " samples" << endl;
3275
3276	//-- some random view cells and rays for output
3277	vector<KdLeaf *> kdLeaves;
3278
3279	for (int i = 0; i < leafOut; ++ i)
3280	kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
3281
3282	for (int i = 0; i < kdLeaves.size(); ++ i)
3283	{
3284	KdLeaf *leaf = kdLeaves[i];
3285	RayContainer vcRays;
3286
3287	cout << "creating output for view cell " << i << " ... ";
3288	#if 0
3289	// check whether we can add the current ray to the output rays
3290	for (int k = 0; k < raysOut; ++ k)
3291	{
3292	Ray *ray = sampleRays[k];
3293
3294	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
3295	{
3296	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
3297
3298	if (leaf->GetViewCell() == leaf2->GetViewCell())
3299	{
3300	vcRays.push_back(ray);
3301	}
3302	}
3303	}
3304	#endif
3305	Intersectable::NewMail();
3306
3307	ViewCell *vc = leaf->mViewCell;
3308
3309	//bspLeaves[j]->Mail();
3310	char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
3311
3312	Exporter *exporter = Exporter::GetExporter(s);
3313	exporter->SetFilled();
3314
3315	exporter->SetWireframe();
3316	//exporter->SetFilled();
3317
3318	Material m;//= RandomMaterial();
3319	m.mDiffuseColor = RgbColor(1, 1, 0);
3320	exporter->SetForcedMaterial(m);
3321
3322	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
3323	exporter->ExportBox(box);
3324
3325	// export rays piercing this view cell
3326	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
3327
3328	m.mDiffuseColor = RgbColor(1, 0, 0);
3329	exporter->SetForcedMaterial(m);
3330
3331	// exporter->SetWireframe();
3332	exporter->SetFilled();
3333
3334	ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
3335	// -- output PVS of view cell
3336	for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
3337	{
3338	Intersectable intersect = (it).first;
3339	if (!intersect->Mailed())
3340	{
3341	exporter->ExportIntersectable(intersect);
3342	intersect->Mail();
3343	}
3344	}
3345
3346	DEL_PTR(exporter);
3347	cout << "finished" << endl;
3348	}
3349
3350	DEL_PTR(rays);
3351	}
3352	else // using kd PVS of objects
3353	{
3354	for (int i = 0; i < limit; ++ i)
3355	{
3356	VssRay *ray = sampleRays[i];
3357
3358	// check whether we can add this to the rays
3359	for (int j = 0; j < pvsOut; j++)
3360	{
3361	if (objects[j] == ray->mTerminationObject)
3362	{
3363	rays[j].push_back(ray);
3364	}
3365	}
3366	}
3367
3368	if (exportRays)
3369	{
3370	Exporter *exporter = NULL;
3371	exporter = Exporter::GetExporter("sample-rays.x3d");
3372	exporter->SetWireframe();
3373	exporter->ExportKdTree(*mKdTree);
3374
3375	for (i = 0; i < pvsOut; i++)
3376	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
3377
3378	exporter->SetFilled();
3379
3380	delete exporter;
3381	}
3382
3383	for (int k=0; k < pvsOut; k++)
3384	{
3385	Intersectable *object = objects[k];
3386	char s[64];
3387	sprintf(s, "sample-pvs%04d.x3d", k);
3388
3389	Exporter *exporter = Exporter::GetExporter(s);
3390	exporter->SetWireframe();
3391
3392	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
3393	Intersectable::NewMail();
3394
3395	// avoid adding the object to the list
3396	object->Mail();
3397	ObjectContainer visibleObjects;
3398
3399	for (; kit != object->mKdPvs.mEntries.end(); i++)
3400	{
3401	KdNode node = (kit).first;
3402	exporter->ExportBox(mKdTree->GetBox(node));
3403
3404	mKdTree->CollectObjects(node, visibleObjects);
3405	}
3406
3407	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
3408	exporter->SetFilled();
3409
3410	for (int j = 0; j < visibleObjects.size(); j++)
3411	exporter->ExportIntersectable(visibleObjects[j]);
3412
3413	Material m;
3414	m.mDiffuseColor = RgbColor(1, 0, 0);
3415	exporter->SetForcedMaterial(m);
3416	exporter->ExportIntersectable(object);
3417
3418	delete exporter;
3419	}
3420	}
3421	}
3422
3423
3424	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
3425	{
3426	return new KdViewCell(mesh);
3427	}
3428
3429
3430	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3431	ViewCell *vc,
3432	const AxisAlignedPlane *clipPlane) const
3433	{
3434	ViewCellContainer leaves;
3435
3436	mViewCellsTree->CollectLeaves(vc, leaves);
3437	ViewCellContainer::const_iterator it, it_end = leaves.end();
3438
3439	for (it = leaves.begin(); it != it_end; ++ it)
3440	{
3441	KdViewCell kdVc = dynamic_cast<KdViewCell >(*it);
3442
3443	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
3444	}
3445	}
3446
3447
3448	int KdViewCellsManager::GetType() const
3449	{
3450	return ViewCellsManager::KD;
3451	}
3452
3453
3454
3455	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
3456	{
3457	KdNode *node = leaf;
3458
3459	while (node->mParent && node->mDepth > mKdPvsDepth)
3460	node = node->mParent;
3461
3462	return node;
3463	}
3464
3465	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
3466	const Vector3 &termination,
3467	ViewCellContainer &viewcells)
3468	{
3469	return mKdTree->CastLineSegment(origin, termination, viewcells);
3470	}
3471
3472
3473	void KdViewCellsManager::CreateMesh(ViewCell *vc)
3474	{
3475	// TODO
3476	}
3477
3478
3479
3480	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3481	vector<MergeCandidate> &candidates)
3482	{
3483	// TODO
3484	}
3485
3486
3487
3488
3489	/**************************************************************************/
3490	/* VspBspViewCellsManager implementation */
3491	/**************************************************************************/
3492
3493
3494	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
3495	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
3496	{
3497	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
3498	mVspBspTree->SetViewCellsManager(this);
3499	mVspBspTree->mViewCellsTree = mViewCellsTree;
3500	}
3501
3502
3503	VspBspViewCellsManager::~VspBspViewCellsManager()
3504	{
3505	}
3506
3507
3508	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
3509	{
3510	if (0 && mVspBspTree->mUseAreaForPvs)
3511	return GetArea(viewCell) / GetAccVcArea();
3512	else
3513	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
3514	}
3515
3516
3517	void VspBspViewCellsManager::CollectViewCells()
3518	{
3519	// view cells tree constructed
3520	if (!ViewCellsTreeConstructed())
3521	{
3522	mVspBspTree->CollectViewCells(mViewCells, false);
3523	}
3524	else
3525	{
3526	// we can use the view cells tree hierarchy to get the right set
3527	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3528	}
3529	}
3530
3531
3532	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3533	vector<MergeCandidate> &candidates)
3534	{
3535	cout << "collecting merge candidates ... " << endl;
3536
3537	if (mUseRaysForMerge)
3538	{
3539	mVspBspTree->CollectMergeCandidates(rays, candidates);
3540	}
3541	else
3542	{
3543	vector<BspLeaf *> leaves;
3544	mVspBspTree->CollectLeaves(leaves);
3545
3546	mVspBspTree->CollectMergeCandidates(leaves, candidates);
3547	}
3548
3549	cout << "fininshed collecting candidates" << endl;
3550	}
3551
3552
3553	bool VspBspViewCellsManager::ViewCellsConstructed() const
3554	{
3555	return mVspBspTree->GetRoot() != NULL;
3556	}
3557
3558
3559	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
3560	{
3561	return new BspViewCell(mesh);
3562	}
3563
3564
3565	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3566	const VssRayContainer &rays)
3567	{
3568	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
3569
3570	// if view cells were already constructed
3571	if (ViewCellsConstructed())
3572	return 0;
3573
3574	int sampleContributions = 0;
3575
3576	VssRayContainer sampleRays;
3577
3578	int limit = min (mInitialSamples, (int)rays.size());
3579
3580	VssRayContainer constructionRays;
3581	VssRayContainer savedRays;
3582
3583	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
3584	<< ", actual rays: " << (int)rays.size() << endl;
3585
3586	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
3587
3588	Debug << "initial rays: " << (int)constructionRays.size() << endl;
3589	Debug << "saved rays: " << (int)savedRays.size() << endl;
3590
3591	long startTime;
3592
3593	if (1)
3594	{
3595	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
3596	}
3597	else
3598	{
3599	mVspBspTree->Construct(rays, &mViewSpaceBox);
3600	}
3601
3602	// collapse invalid regions
3603	cout << "collapsing invalid tree regions ... ";
3604	startTime = GetTime();
3605	const int collapsedLeaves = mVspBspTree->CollapseTree();
3606	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
3607	<< " seconds" << endl;
3608
3609	cout << "finished" << endl;
3610
3611	//-- stats after construction
3612
3613	Debug << mVspBspTree->GetStatistics() << endl;
3614
3615	ResetViewCells();
3616	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3617
3618
3619	startTime = GetTime();
3620
3621	cout << "Computing remaining ray contributions ... ";
3622
3623	// recast rest of rays
3624	if (SAMPLE_AFTER_SUBDIVISION)
3625	ComputeSampleContributions(savedRays, true, false);
3626
3627	cout << "finished" << endl;
3628
3629	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
3630	<< " secs" << endl;
3631
3632	cout << "construction finished" << endl;
3633
3634
3635	if (0)
3636	{
3637	//-- real meshes are contructed at this stage
3638	cout << "finalizing view cells ... ";
3639	FinalizeViewCells(true);
3640	cout << "finished" << endl;
3641	}
3642
3643	return sampleContributions;
3644	}
3645
3646
3647	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
3648	const ObjectContainer &objects)
3649	{
3650	int vcSize = 0;
3651	int pvsSize = 0;
3652
3653	//-- merge view cells
3654	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
3655	long startTime = GetTime();
3656
3657
3658	if (mMergeViewCells)
3659	{
3660	// TODO: should be done BEFORE the ray casting
3661	// compute tree by merging the nodes based on cost heuristics
3662	mViewCellsTree->ConstructMergeTree(rays, objects);
3663	}
3664	else
3665	{
3666	// compute tree by merging the nodes of the spatial hierarchy
3667	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
3668	mViewCellsTree->SetRoot(root);
3669
3670	// compute pvs
3671	ObjectPvs pvs;
3672	UpdatePvsForEvaluation(root, pvs);
3673	}
3674
3675	if (1)
3676	{
3677	char mstats[100];
3678	ObjectPvs pvs;
3679
3680	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3681	mViewCellsTree->ExportStats(mstats);
3682	}
3683
3684	//-- stats and visualizations
3685	cout << "finished merging" << endl;
3686	cout << "merged view cells in "
3687	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
3688
3689	Debug << "Postprocessing: Merged view cells in "
3690	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
3691
3692
3693	int savedColorCode = mColorCode;
3694
3695	// get currently active view cell set
3696	ResetViewCells();
3697	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3698
3699	//BspLeaf::NewMail();
3700	if (1) // export merged view cells
3701	{
3702	mColorCode = 0;
3703	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
3704
3705	cout << "exporting view cells after merge ... ";
3706
3707	if (exporter)
3708	{
3709	if (0)
3710	exporter->SetWireframe();
3711	else
3712	exporter->SetFilled();
3713
3714	ExportViewCellsForViz(exporter);
3715
3716	if (mExportGeometry)
3717	{
3718	Material m;
3719	m.mDiffuseColor = RgbColor(0, 1, 0);
3720	exporter->SetForcedMaterial(m);
3721	exporter->SetFilled();
3722
3723	exporter->ExportGeometry(objects);
3724	}
3725
3726	delete exporter;
3727	}
3728	cout << "finished" << endl;
3729	}
3730
3731	if (0)
3732	{
3733	mColorCode = 1; // export merged view cells using pvs coding
3734	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3735
3736	cout << "exporting view cells after merge (pvs size) ... ";
3737
3738	if (exporter)
3739	{
3740	if (0)
3741	exporter->SetWireframe();
3742	else
3743	exporter->SetFilled();
3744
3745	ExportViewCellsForViz(exporter);
3746
3747	if (mExportGeometry)
3748	{
3749	Material m;
3750	m.mDiffuseColor = RgbColor(0, 1, 0);
3751	exporter->SetForcedMaterial(m);
3752	exporter->SetFilled();
3753
3754	exporter->ExportGeometry(objects);
3755	}
3756
3757	delete exporter;
3758	}
3759	cout << "finished" << endl;
3760	}
3761
3762	mColorCode = savedColorCode;
3763
3764	}
3765
3766
3767	bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
3768	{
3769	return GetSpatialNode(viewCell) != NULL;
3770	}
3771
3772
3773	BspNode VspBspViewCellsManager::GetSpatialNode(ViewCell viewCell) const
3774	{
3775	if (!viewCell->IsLeaf())
3776	{
3777	BspViewCell bspVc = dynamic_cast<BspViewCell >(viewCell);
3778
3779	return bspVc->mLeaf;
3780	}
3781	else
3782	{
3783	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
3784
3785	// cannot be node of binary tree
3786	if (interior->mChildren.size() != 2)
3787	return NULL;
3788
3789	ViewCell *left = interior->mChildren[0];
3790	ViewCell *right = interior->mChildren[1];
3791
3792	BspNode *leftNode = GetSpatialNode(left);
3793	BspNode *rightNode = GetSpatialNode(right);
3794
3795	if (leftNode && rightNode && leftNode->IsSibling(rightNode))
3796	{
3797	return leftNode->GetParent();
3798	}
3799	}
3800
3801	return NULL;
3802	}
3803
3804
3805	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
3806	const ObjectContainer &objects)
3807	{
3808	Debug << "render time before refine:" << endl;
3809	mRenderer->RenderScene();
3810	SimulationStatistics ss;
3811	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3812	Debug << ss << endl;
3813
3814	cout << "Refining the merged view cells ... ";
3815	long startTime = GetTime();
3816
3817	// refining the merged view cells
3818	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
3819
3820	//-- stats and visualizations
3821	cout << "finished" << endl;
3822	cout << "refined " << refined << " view cells in "
3823	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
3824
3825	Debug << "Postprocessing: refined " << refined << " view cells in "
3826	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
3827	}
3828
3829
3830	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
3831	const VssRayContainer &rays)
3832	{
3833	if (!ViewCellsConstructed())
3834	{
3835	Debug << "postprocess error: no view cells constructed" << endl;
3836	return 0;
3837	}
3838
3839
3840	// view cells already finished before post processing step
3841	// (i.e. because they were loaded)
3842	if (mViewCellsFinished)
3843	{
3844	FinalizeViewCells(true);
3845	EvaluateViewCellsStats();
3846
3847	return 0;
3848	}
3849
3850	// check if new view cells turned invalid
3851	int minPvs, maxPvs;
3852
3853	if (0)
3854	{
3855	minPvs = mMinPvsSize;
3856	maxPvs = mMaxPvsSize;
3857	}
3858	else
3859	{
3860	minPvs = mPruneEmptyViewCells ? 1 : 0;
3861	maxPvs = mMaxPvsSize;
3862	}
3863
3864	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
3865	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
3866
3867	SetValidity(minPvs, maxPvs);
3868
3869	// update valid view space according to valid view cells
3870	if (0) mVspBspTree->ValidateTree();
3871
3872	// area has to be recomputed
3873	mTotalAreaValid = false;
3874	VssRayContainer postProcessRays;
3875	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3876
3877	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
3878
3879
3880	// should maybe be done here to allow merge working with area or volume
3881	// and to correct the rendering statistics
3882	if (0) FinalizeViewCells(false);
3883
3884	//-- merge the individual view cells
3885	MergeViewCells(postProcessRays, objects);
3886
3887
3888	// only for debugging purpose: test if the subdivision is valid
3889	if (0) TestSubdivision();
3890
3891	//-- refines the merged view cells
3892	if (0) RefineViewCells(postProcessRays, objects);
3893
3894
3895	//-- render simulation after merge + refine
3896	cout << "\nevaluating bsp view cells render time before compress ... ";
3897	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
3898	SimulationStatistics ss;
3899	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3900
3901
3902	cout << " finished" << endl;
3903	cout << ss << endl;
3904	Debug << ss << endl;
3905
3906
3907	//-- compression
3908	if (ViewCellsTreeConstructed() && mCompressViewCells)
3909	{
3910	int pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
3911	Debug << "number of entries before compress: " << pvsEntries << endl;
3912
3913	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
3914
3915	pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
3916	Debug << "number of entries after compress: " << pvsEntries << endl;
3917	}
3918
3919
3920	// collapse sibling leaves that share the same view cell
3921	if (0) mVspBspTree->CollapseTree();
3922
3923	// recompute view cell list and statistics
3924	ResetViewCells();
3925
3926	// compute final meshes and volume / area
3927	if (1) FinalizeViewCells(true);
3928
3929	// write view cells to disc
3930	if (mExportViewCells)
3931	{
3932	char filename[100];
3933	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
3934	ExportViewCells(filename, mExportPvs, objects);
3935	}
3936
3937
3938	// export bounding boxes
3939	if (mExportBboxesForPvs)
3940	{
3941	char filename[100];
3942	Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
3943
3944	ExportBoundingBoxes(filename, objects);
3945	}
3946
3947	return 0;
3948	}
3949
3950
3951	int VspBspViewCellsManager::GetType() const
3952	{
3953	return VSP_BSP;
3954	}
3955
3956
3957	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
3958	{
3959	// terminate recursion
3960	if (root->IsLeaf())
3961	{
3962	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
3963	leaf->GetViewCell()->SetMergeCost(0.0f);
3964	return leaf->GetViewCell();
3965	}
3966
3967
3968	BspInterior interior = dynamic_cast<BspInterior >(root);
3969	ViewCellInterior *viewCellInterior = new ViewCellInterior();
3970
3971	// evaluate merge cost for priority traversal
3972	float mergeCost = 1.0f / (float)root->mTimeStamp;
3973	viewCellInterior->SetMergeCost(mergeCost);
3974
3975	float volume = 0;
3976
3977	BspNode *front = interior->GetFront();
3978	BspNode *back = interior->GetBack();
3979
3980
3981	ObjectPvs frontPvs, backPvs;
3982
3983	//-- recursivly compute child hierarchies
3984	ViewCell *backVc = ConstructSpatialMergeTree(back);
3985	ViewCell *frontVc = ConstructSpatialMergeTree(front);
3986
3987
3988	viewCellInterior->SetupChildLink(backVc);
3989	viewCellInterior->SetupChildLink(frontVc);
3990
3991	volume += backVc->GetVolume();
3992	volume += frontVc->GetVolume();
3993
3994	viewCellInterior->SetVolume(volume);
3995
3996	return viewCellInterior;
3997	}
3998
3999
4000	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4001	{
4002	if (!ViewCellsConstructed())
4003	return ViewCellsManager::GetViewPoint(viewPoint);
4004
4005	// TODO: set reasonable limit
4006	const int limit = 20;
4007
4008	for (int i = 0; i < limit; ++ i)
4009	{
4010	viewPoint = mViewSpaceBox.GetRandomPoint();
4011	if (mVspBspTree->ViewPointValid(viewPoint))
4012	{
4013	return true;
4014	}
4015	}
4016
4017	Debug << "failed to find valid view point, taking " << viewPoint << endl;
4018	return false;
4019	}
4020
4021
4022	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4023	{
4024	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4025	// validy update in preprocessor for all managers)
4026	return ViewCellsManager::ViewPointValid(viewPoint);
4027
4028	// return mViewSpaceBox.IsInside(viewPoint) &&
4029	// mVspBspTree->ViewPointValid(viewPoint);
4030	}
4031
4032
4033	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4034	const VssRayContainer &sampleRays)
4035	{
4036	if (!ViewCellsConstructed())
4037	return;
4038
4039	VssRayContainer visRays;
4040	GetRaySets(sampleRays, mVisualizationSamples, visRays);
4041
4042	//-- export final view cell partition
4043
4044	if (0)
4045	{
4046	// hack pvs
4047	//const int savedColorCode = mColorCode;
4048	//mColorCode = 1;
4049
4050	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4051
4052	if (exporter)
4053	{
4054	cout << "exporting view cells after post process ... ";
4055
4056	if (0)
4057	{
4058	// export view space box
4059	exporter->SetWireframe();
4060	exporter->ExportBox(mViewSpaceBox);
4061	exporter->SetFilled();
4062	}
4063
4064	Material m;
4065
4066	m.mDiffuseColor.r = 0.0f;
4067	m.mDiffuseColor.g = 0.5f;
4068	m.mDiffuseColor.b = 0.5f;
4069
4070	exporter->SetForcedMaterial(m);
4071
4072	if (0 && mExportGeometry)
4073	{
4074	exporter->ExportGeometry(objects);
4075	}
4076
4077	// export rays
4078	if (0 && mExportRays)
4079	{
4080	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4081	}
4082
4083	//exporter->SetFilled();
4084
4085	// HACK: export without clip plane
4086	const bool b = mUseClipPlaneForViz;
4087	//mUseClipPlaneForViz = false;
4088
4089	ExportViewCellsForViz(exporter);
4090
4091	mUseClipPlaneForViz = b;
4092	delete exporter;
4093
4094	cout << "finished" << endl;
4095	}
4096
4097	//mColorCode = savedColorCode;
4098	}
4099
4100
4101	if (0)
4102	{
4103	cout << "exporting depth map ... ";
4104
4105	Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
4106	if (exporter)
4107	{
4108	if (1)
4109	{
4110	exporter->SetWireframe();
4111	exporter->ExportBox(mViewSpaceBox);
4112	exporter->SetFilled();
4113	}
4114
4115	if (mExportGeometry)
4116	{
4117	exporter->ExportGeometry(objects);
4118	}
4119
4120	const int maxDepth = mVspBspTree->GetStatistics().maxDepth;
4121
4122	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
4123
4124	for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
4125	{
4126	ViewCell vc = vit;
4127
4128	ViewCellContainer leaves;
4129	mViewCellsTree->CollectLeaves(vc, leaves);
4130
4131	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
4132
4133	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4134	{
4135	BspLeaf leaf = dynamic_cast<BspViewCell >(*lit)->mLeaf;
4136
4137	Material m;
4138
4139	float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
4140	m.mDiffuseColor.r = relDepth;
4141	m.mDiffuseColor.g = 0.0f;
4142	m.mDiffuseColor.b = 1.0f - relDepth;
4143
4144	exporter->SetForcedMaterial(m);
4145
4146
4147	BspNodeGeometry geom;
4148	mVspBspTree->ConstructGeometry(leaf, geom);
4149	exporter->ExportPolygons(geom.GetPolys());
4150	}
4151	}
4152
4153	delete exporter;
4154	}
4155
4156
4157	cout << "finished" << endl;
4158	}
4159
4160	//-- visualization of the BSP splits
4161	bool exportSplits = false;
4162	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4163
4164	if (exportSplits)
4165	{
4166	cout << "exporting splits ... ";
4167	ExportSplits(objects, visRays);
4168	cout << "finished" << endl;
4169	}
4170
4171	//-- export single view cells
4172	ExportBspPvs(objects, visRays);
4173	}
4174
4175
4176	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
4177	const VssRayContainer &rays)
4178	{
4179	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4180
4181	if (exporter)
4182	{
4183	Material m;
4184	m.mDiffuseColor = RgbColor(1, 0, 0);
4185	exporter->SetForcedMaterial(m);
4186	exporter->SetWireframe();
4187
4188	exporter->ExportBspSplits(*mVspBspTree, true);
4189
4190	// take forced material, else big scenes cannot be viewed
4191	m.mDiffuseColor = RgbColor(0, 1, 0);
4192	exporter->SetForcedMaterial(m);
4193	exporter->SetFilled();
4194
4195	exporter->ResetForcedMaterial();
4196
4197	// export rays
4198	if (mExportRays)
4199	exporter->ExportRays(rays, RgbColor(1, 1, 0));
4200
4201	if (mExportGeometry)
4202	exporter->ExportGeometry(objects);
4203
4204	delete exporter;
4205	}
4206	}
4207
4208
4209	void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
4210	const VssRayContainer &rays)
4211	{
4212	int leafOut;
4213	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4214
4215	ViewCell::NewMail();
4216
4217	cout << "visualization using " << (int)rays.size() << " samples" << endl;
4218	Debug << "visualization using " << (int)rays.size() << " samples" << endl;
4219	Debug << "\nOutput view cells: " << endl;
4220
4221	const bool sortViewCells = true;
4222
4223	// sort view cells to visualize the largest view cells
4224	if (sortViewCells)
4225	{
4226	//stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
4227	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4228	}
4229
4230	int limit = min(leafOut, (int)mViewCells.size());
4231
4232	int raysOut = 0;
4233
4234	//-- some rays for output
4235	for (int i = 0; i < limit; ++ i)
4236	{
4237	cout << "creating output for view cell " << i << " ... ";
4238
4239	ViewCell *vc;
4240
4241	if (sortViewCells) // largest view cell pvs first
4242	vc = mViewCells[i];
4243	else
4244	vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
4245
4246	ObjectPvs pvs;
4247	mViewCellsTree->GetPvs(vc, pvs);
4248
4249	//bspLeaves[j]->Mail();
4250	char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
4251	Exporter *exporter = Exporter::GetExporter(s);
4252
4253	Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
4254
4255	//-- export the sample rays
4256	if (mExportRays)
4257	{
4258	// output rays stored with the view cells during subdivision
4259	if (1)
4260	{
4261	VssRayContainer vcRays;
4262	VssRayContainer collectRays;
4263
4264	raysOut = min((int)rays.size(), 100);
4265
4266	// collect intial view cells
4267	ViewCellContainer leaves;
4268	mViewCellsTree->CollectLeaves(vc, leaves);
4269
4270	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4271
4272	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4273	{
4274	BspLeaf vcLeaf = dynamic_cast<BspViewCell >(*vit)->mLeaf;
4275
4276	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
4277
4278	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
4279	{
4280	collectRays.push_back(*rit);
4281	}
4282	}
4283
4284	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4285
4286	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4287	{
4288	float p = RandomValue(0.0f, (float)collectRays.size());
4289
4290	if (p < raysOut)
4291	vcRays.push_back(*rit);
4292	}
4293
4294	//Debug << "#rays: " << (int)vcRays.size() << endl;
4295
4296	//-- export rays piercing this view cell
4297	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
4298	}
4299
4300	// associate new rays with output view cell
4301	if (0)
4302	{
4303	VssRayContainer vcRays;
4304	raysOut = min((int)rays.size(), mVisualizationSamples);
4305
4306	// check whether we can add the current ray to the output rays
4307	for (int k = 0; k < raysOut; ++ k)
4308	{
4309	VssRay *ray = rays[k];
4310	for (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
4311	{
4312	ViewCell *rayvc = ray->mViewCells[j];
4313
4314	if (rayvc == vc)
4315	vcRays.push_back(ray);
4316	}
4317	}
4318
4319	//-- export rays piercing this view cell
4320	exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
4321	}
4322
4323	}
4324
4325
4326	//-- export view cell geometry
4327	exporter->SetWireframe();
4328
4329	Material m;//= RandomMaterial();
4330	m.mDiffuseColor = RgbColor(0, 1, 0);
4331	exporter->SetForcedMaterial(m);
4332
4333	ExportViewCellGeometry(exporter, vc);
4334
4335	exporter->SetFilled();
4336
4337
4338	//-- export pvs
4339	if (1)
4340	{
4341	ObjectPvsMap::const_iterator oit,
4342	oit_end = pvs.mEntries.end();
4343
4344	Intersectable::NewMail();
4345
4346	// output PVS of view cell
4347	for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
4348	{
4349	Intersectable intersect = (oit).first;
4350
4351	if (!intersect->Mailed())
4352	{
4353	m = RandomMaterial();
4354	exporter->SetForcedMaterial(m);
4355
4356	exporter->ExportIntersectable(intersect);
4357	intersect->Mail();
4358	}
4359	}
4360	}
4361
4362	if (0)
4363	{ // export scene geometry
4364	m.mDiffuseColor = RgbColor(1, 0, 0);
4365	exporter->SetForcedMaterial(m);
4366
4367	exporter->ExportGeometry(objects);
4368	}
4369
4370	DEL_PTR(exporter);
4371	cout << "finished" << endl;
4372	}
4373
4374	Debug << endl;
4375	}
4376
4377
4378	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
4379	{
4380	Exporter *exporter = Exporter::GetExporter("filter.x3d");
4381
4382	Vector3 bsize = mViewSpaceBox.Size();
4383	const Vector3 viewPoint(mViewSpaceBox.Center());
4384	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
4385	const Vector3 width = Vector3(w);
4386
4387	PrVs testPrVs;
4388
4389	if (exporter)
4390	{
4391	ViewCellContainer viewCells;
4392
4393	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
4394
4395	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
4396
4397	exporter->SetWireframe();
4398
4399	exporter->SetForcedMaterial(RgbColor(1,1,1));
4400	exporter->ExportBox(tbox);
4401
4402	exporter->SetFilled();
4403
4404	exporter->SetForcedMaterial(RgbColor(0,1,0));
4405	ExportViewCellGeometry(exporter, GetViewCell(viewPoint));
4406
4407	//exporter->ResetForcedMaterial();
4408	exporter->SetForcedMaterial(RgbColor(0,0,1));
4409	ExportViewCellGeometry(exporter, testPrVs.mViewCell);
4410
4411	exporter->SetForcedMaterial(RgbColor(1,0,0));
4412	exporter->ExportGeometry(objects);
4413
4414	delete exporter;
4415	}
4416	}
4417
4418
4419	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
4420	ViewCellContainer &viewCells) const
4421	{
4422	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
4423	}
4424
4425
4426	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
4427	const Vector3 &termination,
4428	ViewCellContainer &viewcells)
4429	{
4430	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
4431	}
4432
4433
4434	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
4435	{
4436	int numSamples;
4437
4438	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
4439	cout << "samples" << numSamples << endl;
4440
4441	vector<RenderCostSample> samples;
4442
4443	if (!mPreprocessor->GetRenderer())
4444	return;
4445
4446	//start the view point queries
4447	long startTime = GetTime();
4448	cout << "starting sampling of render cost ... ";
4449
4450	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
4451
4452	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4453
4454
4455	// for each sample:
4456	// find view cells associated with the samples
4457	// store the sample pvs with the pvs associated with the view cell
4458	// for each view cell:
4459	// compute difference point sampled pvs - view cell pvs
4460	// export geometry with color coded pvs difference
4461
4462	std::map<ViewCell *, ObjectPvs> sampleMap;
4463
4464	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
4465
4466	for (rit = samples.begin(); rit != rit_end; ++ rit)
4467	{
4468	RenderCostSample sample = *rit;
4469
4470	ViewCell *vc = GetViewCell(sample.mPosition);
4471
4472	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
4473
4474	if (it == sampleMap.end())
4475	{
4476	sampleMap[vc] = sample.mPvs;
4477	}
4478	else
4479	{
4480	(*it).second.Merge(sample.mPvs);
4481	}
4482	}
4483
4484	// visualize the view cells
4485	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
4486
4487	Material m;//= RandomMaterial();
4488
4489	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
4490	{
4491	ViewCell vc = (vit).first;
4492
4493	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
4494	const int pvsPtSamples = (*vit).second.GetSize();
4495
4496	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
4497	m.mDiffuseColor.b = 1.0f;
4498	//exporter->SetForcedMaterial(m);
4499
4500	// ExportViewCellGeometry(exporter, vc, mClipPlane);
4501
4502	/* // counting the pvss
4503	for (rit = samples.begin(); rit != rit_end; ++ rit)
4504	{
4505	RenderCostSample sample = *rit;
4506
4507	ViewCell *vc = GetViewCell(sample.mPosition);
4508
4509	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
4510	Mesh *hMesh = CreateMeshFromBox(box);
4511
4512	DEL_PTR(hMesh);
4513
4514	*/
4515	}
4516	}
4517
4518
4519	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4520	ViewCell *vc,
4521	const AxisAlignedPlane *clipPlane) const
4522	{
4523	if (clipPlane)
4524	{
4525	const Plane3 plane = clipPlane->GetPlane();
4526
4527	ViewCellContainer leaves;
4528	mViewCellsTree->CollectLeaves(vc, leaves);
4529	ViewCellContainer::const_iterator it, it_end = leaves.end();
4530
4531	for (it = leaves.begin(); it != it_end; ++ it)
4532	{
4533	BspNodeGeometry geom;
4534
4535	BspNodeGeometry front;
4536	BspNodeGeometry back;
4537
4538	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
4539	mVspBspTree->ConstructGeometry(leaf, geom);
4540
4541	const float eps = 0.0001f;
4542	const int cf = geom.Side(plane, eps);
4543
4544	if (cf == -1)
4545	{
4546	exporter->ExportPolygons(geom.GetPolys());
4547	}
4548	else if (cf == 0)
4549	{
4550	geom.SplitGeometry(front,
4551	back,
4552	plane,
4553	mViewSpaceBox,
4554	eps);
4555
4556	//Debug << "geo size: " << geom.Size() << endl;
4557	//Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;
4558
4559	if (back.Valid())
4560	{
4561	exporter->ExportPolygons(back.GetPolys());
4562	}
4563	}
4564	}
4565	}
4566	else
4567	{
4568	// export mesh if available
4569	// TODO: some bug here?
4570	if (0 && vc->GetMesh())
4571	{
4572	exporter->ExportMesh(vc->GetMesh());
4573	}
4574	else
4575	{
4576	BspNodeGeometry geom;
4577	mVspBspTree->ConstructGeometry(vc, geom);
4578	exporter->ExportPolygons(geom.GetPolys());
4579	}
4580	}
4581	}
4582
4583
4584	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
4585	{
4586	ViewCellContainer leaves;
4587	mViewCellsTree->CollectLeaves(vc, leaves);
4588
4589	int maxDist = 0;
4590
4591	// compute max height difference
4592	for (int i = 0; i < (int)leaves.size(); ++ i)
4593	{
4594	for (int j = 0; j < (int)leaves.size(); ++ j)
4595	{
4596	BspLeaf leaf = dynamic_cast<BspViewCell >(leaves[i])->mLeaf;
4597
4598	if (i != j)
4599	{
4600	BspLeaf leaf2 =dynamic_cast<BspViewCell >(leaves[j])->mLeaf;
4601
4602	int dist = mVspBspTree->TreeDistance(leaf, leaf2);
4603
4604	if (dist > maxDist)
4605	maxDist = dist;
4606	}
4607	}
4608	}
4609
4610	return maxDist;
4611	}
4612
4613
4614	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4615	{
4616	if (!ViewCellsConstructed())
4617	return NULL;
4618
4619	if (!mViewSpaceBox.IsInside(point))
4620	return NULL;
4621
4622	return mVspBspTree->GetViewCell(point, active);
4623	}
4624
4625
4626	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
4627	{
4628	//if (vc->GetMesh()) delete vc->GetMesh();
4629	BspNodeGeometry geom;
4630
4631	mVspBspTree->ConstructGeometry(vc, geom);
4632
4633	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4634	IncludeNodeGeomInMesh(geom, *mesh);
4635
4636	vc->SetMesh(mesh);
4637	}
4638
4639
4640	int VspBspViewCellsManager::CastBeam(Beam &beam)
4641	{
4642	return mVspBspTree->CastBeam(beam);
4643	}
4644
4645
4646	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
4647	const bool createMesh)
4648	{
4649	float area = 0;
4650	float volume = 0;
4651
4652	ViewCellContainer leaves;
4653	mViewCellsTree->CollectLeaves(viewCell, leaves);
4654
4655	ViewCellContainer::const_iterator it, it_end = leaves.end();
4656
4657	for (it = leaves.begin(); it != it_end; ++ it)
4658	{
4659	BspNodeGeometry geom;
4660	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
4661	mVspBspTree->ConstructGeometry(leaf, geom);
4662
4663	const float lVol = geom.GetVolume();
4664	const float lArea = geom.GetArea();
4665
4666	//(*it)->SetVolume(vol);
4667	//(*it)->SetArea(area);
4668
4669	area += lArea;
4670	volume += lVol;
4671
4672	CreateMesh(*it);
4673	}
4674
4675	viewCell->SetVolume(volume);
4676	viewCell->SetArea(area);
4677	}
4678
4679
4680	void VspBspViewCellsManager::TestSubdivision()
4681	{
4682	ViewCellContainer leaves;
4683	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4684
4685	ViewCellContainer::const_iterator it, it_end = leaves.end();
4686
4687	const float vol = mViewSpaceBox.GetVolume();
4688	float subdivVol = 0;
4689	float newVol = 0;
4690
4691	for (it = leaves.begin(); it != it_end; ++ it)
4692	{
4693	BspNodeGeometry geom;
4694	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
4695	mVspBspTree->ConstructGeometry(leaf, geom);
4696
4697	const float lVol = geom.GetVolume();
4698
4699	newVol += lVol;
4700	subdivVol += (*it)->GetVolume();
4701
4702	float thres = 0.9f;
4703	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
4704	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4705	}
4706
4707	Debug << "exact volume: " << vol << endl;
4708	Debug << "subdivision volume: " << subdivVol << endl;
4709	Debug << "new volume: " << newVol << endl;
4710	}
4711
4712
4713	void VspBspViewCellsManager::PrepareLoadedViewCells()
4714	{
4715	// TODO: do I still need this here?
4716	if (0)
4717	mVspBspTree->RepairViewCellsLeafLists();
4718	}
4719
4720
4721
4722	/**************************************************************************/
4723	/* VspOspViewCellsManager implementation */
4724	/**************************************************************************/
4725
4726
4727	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
4728	: ViewCellsManager(vcTree), mHierarchyManager(hm)
4729	{
4730	Environment::GetSingleton()->GetIntValue("VspTree.Construction.samples", mInitialSamples);
4731
4732	mHierarchyManager->SetViewCellsManager(this);
4733	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
4734	}
4735
4736
4737	VspOspViewCellsManager::~VspOspViewCellsManager()
4738	{
4739	}
4740
4741
4742	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
4743	{
4744	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4745	}
4746
4747
4748	void VspOspViewCellsManager::CollectViewCells()
4749	{
4750	// view cells tree constructed
4751	if (!ViewCellsTreeConstructed())
4752	{
4753	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
4754	}
4755	else
4756	{ // we can use the view cells tree hierarchy to get the right set
4757	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4758	}
4759	}
4760
4761
4762	bool VspOspViewCellsManager::ViewCellsConstructed() const
4763	{
4764	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
4765	}
4766
4767
4768	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
4769	{
4770	return new VspViewCell(mesh);
4771	}
4772
4773
4774	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4775	const VssRayContainer &rays)
4776	{
4777	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4778
4779	// skip rest if view cells were already constructed
4780	if (ViewCellsConstructed())
4781	return 0;
4782
4783	int sampleContributions = 0;
4784
4785	VssRayContainer sampleRays;
4786
4787	int limit = min (mInitialSamples, (int)rays.size());
4788
4789	VssRayContainer constructionRays;
4790	VssRayContainer savedRays;
4791
4792	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4793	<< ", actual rays: " << (int)rays.size() << endl;
4794
4795	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4796
4797	Debug << "initial rays: " << (int)constructionRays.size() << endl;
4798	Debug << "saved rays: " << (int)savedRays.size() << endl;
4799
4800	//mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
4801	mHierarchyManager->Construct2(constructionRays, objects, &mViewSpaceBox);
4802
4803	VssRayContainer::const_iterator vit, vit_end = constructionRays.end();
4804
4805	for (vit = constructionRays.begin(); vit != vit_end; ++ vit)
4806	{
4807	storedRays.push_back(new VssRay((vit)));
4808	}
4809
4810	// print subdivision statistics
4811	Debug << mHierarchyManager->GetVspTree()->GetStatistics() << endl;
4812	mHierarchyManager->PrintObjectSpaceHierarchyStatistics(Debug);
4813
4814	if (0)
4815	{
4816	OUT_STREAM stream("osptree.xml.zip");
4817	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
4818	}
4819
4820	// print view cell statistics
4821	ResetViewCells();
4822	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4823
4824
4825	const long startTime = GetTime();
4826
4827	cout << "Computing remaining ray contributions ... ";
4828
4829	// recast rest of rays
4830	if (SAMPLE_AFTER_SUBDIVISION)
4831	ComputeSampleContributions(savedRays, true, false);
4832
4833	cout << "finished" << endl;
4834
4835	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4836	<< " secs" << endl;
4837
4838	cout << "construction finished" << endl;
4839
4840	// real meshes are contructed at this stage
4841	if (0)
4842	{
4843	cout << "finalizing view cells ... ";
4844	FinalizeViewCells(true);
4845	cout << "finished" << endl;
4846	}
4847
4848	return sampleContributions;
4849	}
4850
4851
4852	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
4853	const VssRayContainer &rays)
4854	{
4855	if (!ViewCellsConstructed())
4856	{
4857	Debug << "postprocess error: no view cells constructed" << endl;
4858	return 0;
4859	}
4860
4861
4862	// take this step only if
4863	// view cells already constructed before post processing step
4864	// (e.g., because they were loaded)
4865	if (mViewCellsFinished)
4866	{
4867	FinalizeViewCells(true);
4868	EvaluateViewCellsStats();
4869
4870	return 0;
4871	}
4872
4873	// check if new view cells turned invalid
4874	int minPvs, maxPvs;
4875
4876	if (0)
4877	{
4878	minPvs = mMinPvsSize;
4879	maxPvs = mMaxPvsSize;
4880	}
4881	else
4882	{
4883	minPvs = mPruneEmptyViewCells ? 1 : 0;
4884	maxPvs = mMaxPvsSize;
4885	}
4886
4887	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4888	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4889
4890	SetValidity(minPvs, maxPvs);
4891
4892
4893	// area has to be recomputed
4894	mTotalAreaValid = false;
4895	VssRayContainer postProcessRays;
4896	GetRaySets(rays, mPostProcessSamples, postProcessRays);
4897
4898	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4899
4900
4901	// should maybe be done here to allow merge working with area or volume
4902	// and to correct the rendering statistics
4903	if (0) FinalizeViewCells(false);
4904
4905	// compute tree by merging the nodes of the spatial hierarchy
4906	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
4907	mViewCellsTree->SetRoot(root);
4908
4909	// compute pvs
4910	ObjectPvs pvs;
4911	UpdatePvsForEvaluation(root, pvs);
4912
4913
4914	//-- render simulation after merge + refine
4915	cout << "\nevaluating bsp view cells render time before compress ... ";
4916	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4917	SimulationStatistics ss;
4918	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4919
4920
4921	cout << " finished" << endl;
4922	cout << ss << endl;
4923	Debug << ss << endl;
4924
4925
4926	//-- compression
4927
4928	if (ViewCellsTreeConstructed() && mCompressViewCells)
4929	{
4930	int pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
4931	Debug << "number of entries before compress: " << pvsEntries << endl;
4932
4933	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
4934
4935	pvsEntries = mViewCellsTree->GetStoredPvsEntriesNum(mViewCellsTree->GetRoot());
4936	Debug << "number of entries after compress: " << pvsEntries << endl;
4937	}
4938
4939	// compute final meshes and volume / area
4940	if (1) FinalizeViewCells(true);
4941
4942	// write view cells to disc
4943	if (mExportViewCells)
4944	{
4945	char filename[100];
4946	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
4947	ExportViewCells(filename, mExportPvs, objects);
4948	}
4949
4950
4951	return 0;
4952	}
4953
4954
4955	int VspOspViewCellsManager::GetType() const
4956	{
4957	return VSP_OSP;
4958	}
4959
4960
4961	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
4962	{
4963	// terminate recursion
4964	if (root->IsLeaf())
4965	{
4966	VspLeaf leaf = dynamic_cast<VspLeaf >(root);
4967	leaf->GetViewCell()->SetMergeCost(0.0f);
4968	return leaf->GetViewCell();
4969	}
4970
4971	VspInterior interior = dynamic_cast<VspInterior >(root);
4972	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4973
4974	// evaluate merge cost for priority traversal
4975	float mergeCost = 1.0f / (float)root->mTimeStamp;
4976	viewCellInterior->SetMergeCost(mergeCost);
4977
4978	float volume = 0;
4979
4980	VspNode *front = interior->GetFront();
4981	VspNode *back = interior->GetBack();
4982
4983
4984	ObjectPvs frontPvs, backPvs;
4985
4986	//-- recursivly compute child hierarchies
4987	ViewCell *backVc = ConstructSpatialMergeTree(back);
4988	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4989
4990
4991	viewCellInterior->SetupChildLink(backVc);
4992	viewCellInterior->SetupChildLink(frontVc);
4993
4994	volume += backVc->GetVolume();
4995	volume += frontVc->GetVolume();
4996
4997	viewCellInterior->SetVolume(volume);
4998
4999	return viewCellInterior;
5000	}
5001
5002
5003	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5004	{
5005	if (!ViewCellsConstructed())
5006	return ViewCellsManager::GetViewPoint(viewPoint);
5007
5008	// TODO: set reasonable limit
5009	const int limit = 20;
5010
5011	for (int i = 0; i < limit; ++ i)
5012	{
5013	viewPoint = mViewSpaceBox.GetRandomPoint();
5014
5015	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
5016	{
5017	return true;
5018	}
5019	}
5020
5021	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5022	return false;
5023	}
5024
5025
5026	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5027	ViewCell *vc,
5028	const AxisAlignedPlane *clipPlane) const
5029	{
5030	ViewCellContainer leaves;
5031
5032	mViewCellsTree->CollectLeaves(vc, leaves);
5033	ViewCellContainer::const_iterator it, it_end = leaves.end();
5034
5035	Plane3 plane;
5036
5037	if (clipPlane)
5038	plane = clipPlane->GetPlane();
5039
5040	for (it = leaves.begin(); it != it_end; ++ it)
5041	{
5042	VspViewCell vspVc = dynamic_cast<VspViewCell >(*it);
5043	VspLeaf *l = vspVc->mLeaf;
5044
5045	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaf);
5046
5047	if (clipPlane)
5048	{
5049	if (box.Side(plane) == -1)
5050	{
5051	exporter->ExportBox(box);
5052	}
5053	else if (box.Side(plane) == 0)
5054	{
5055	AxisAlignedBox3 fbox, bbox;
5056	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5057
5058	exporter->ExportBox(bbox);
5059	}
5060	}
5061	else
5062	{
5063	exporter->ExportBox(box);
5064	}
5065	}
5066	}
5067
5068
5069	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5070	{
5071	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5072	// validy update in preprocessor for all managers)
5073	return ViewCellsManager::ViewPointValid(viewPoint);
5074
5075	// return mViewSpaceBox.IsInside(viewPoint) &&
5076	// mVspTree->ViewPointValid(viewPoint);
5077	}
5078
5079
5080	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5081	const VssRayContainer &sampleRays)
5082	{
5083	if (!ViewCellsConstructed())
5084	return;
5085
5086	VssRayContainer visRays;
5087	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5088
5089	if (1)
5090	{
5091	//-- export final view cells
5092
5093	// hack pvs
5094	const int savedColorCode = mColorCode;
5095	mColorCode = 0;
5096
5097	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5098
5099	if (exporter)
5100	{
5101	cout << "exporting view cells after post process ... ";
5102
5103	if (0)
5104	{
5105	// export view space box
5106	exporter->SetWireframe();
5107	exporter->ExportBox(mViewSpaceBox);
5108	exporter->SetFilled();
5109	}
5110
5111	if (mExportGeometry)
5112	{
5113	exporter->ExportGeometry(objects);
5114	}
5115
5116	// export rays
5117	if (0 && mExportRays)
5118	{
5119	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5120	}
5121
5122	//exporter->SetFilled();
5123
5124	// HACK: export without clip plane
5125	const bool b = mUseClipPlaneForViz;
5126	if (0) mUseClipPlaneForViz = false;
5127
5128	ExportViewCellsForViz(exporter);
5129
5130	mUseClipPlaneForViz = b;
5131	delete exporter;
5132
5133	cout << "finished" << endl;
5134	}
5135
5136	mColorCode = savedColorCode;
5137	}
5138
5139	mHierarchyManager->ExportObjectSpaceHierarchyForViz(objects);
5140
5141	//-- export single view cells
5142	ExportPvs(objects, visRays);
5143	}
5144
5145
5146	void VspOspViewCellsManager::ExportPvs(const ObjectContainer &objects,
5147	const VssRayContainer &rays)
5148	{
5149	int leafOut;
5150	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5151
5152	ViewCell::NewMail();
5153
5154	cout << "visualization using " << (int)rays.size() << " samples" << endl;
5155	Debug << "visualization using " << (int)rays.size() << " samples" << endl;
5156	Debug << "\nOutput view cells: " << endl;
5157
5158	const bool sortViewCells = true;
5159
5160	// sort view cells to visualize the largest view cells
5161	if (sortViewCells)
5162	{
5163	//stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
5164	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5165	}
5166
5167	int limit = min(leafOut, (int)mViewCells.size());
5168
5169	int raysOut = 0;
5170
5171
5172	//-- some rays for output
5173
5174	for (int i = 0; i < limit; ++ i)
5175	{
5176	cout << "creating output for view cell " << i << " ... ";
5177
5178	ViewCell *vc;
5179
5180	if (sortViewCells) // largest view cell pvs first
5181	vc = mViewCells[i];
5182	else // random view cell
5183	vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
5184
5185	ObjectPvs pvs;
5186	mViewCellsTree->GetPvs(vc, pvs);
5187
5188	//bspLeaves[j]->Mail();
5189	char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
5190	Exporter *exporter = Exporter::GetExporter(s);
5191
5192	Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
5193
5194	//-- export the sample rays
5195	if (1 \|\| mExportRays)
5196	{
5197	// output rays stored with the view cells during subdivision
5198	if (1)
5199	{
5200	VssRayContainer vcRays;
5201	VssRayContainer collectRays;
5202
5203	raysOut = min((int)rays.size(), 100);
5204
5205	// collect intial view cells
5206	ViewCellContainer leaves;
5207	mViewCellsTree->CollectLeaves(vc, leaves);
5208
5209	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5210
5211	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5212	{
5213	VspLeaf vcLeaf = dynamic_cast<VspViewCell >(*vit)->mLeaf;
5214
5215	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5216
5217	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5218	{
5219	collectRays.push_back(*rit);
5220	}
5221	}
5222
5223	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5224
5225	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5226	{
5227	float p = RandomValue(0.0f, (float)collectRays.size());
5228
5229	if (p < raysOut)
5230	vcRays.push_back(*rit);
5231	}
5232
5233	//-- export rays piercing this view cell
5234	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5235	}
5236
5237	// associate new rays with output view cell
5238	if (0)
5239	{
5240	VssRayContainer vcRays;
5241	raysOut = min((int)rays.size(), mVisualizationSamples);
5242
5243	// check whether we can add the current ray to the output rays
5244	for (int k = 0; k < raysOut; ++ k)
5245	{
5246	VssRay *ray = rays[k];
5247	for (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
5248	{
5249	ViewCell *rayvc = ray->mViewCells[j];
5250
5251	if (rayvc == vc)
5252	vcRays.push_back(ray);
5253	}
5254	}
5255
5256	//-- export rays piercing this view cell
5257	exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
5258	}
5259	}
5260
5261	//-- export view cell geometry
5262
5263	exporter->SetWireframe();
5264
5265	Material m;//= RandomMaterial();
5266	m.mDiffuseColor = RgbColor(0, 1, 0);
5267	exporter->SetForcedMaterial(m);
5268
5269	ExportViewCellGeometry(exporter, vc);
5270
5271	exporter->SetFilled();
5272
5273	#if 0
5274	//-- export pvs
5275
5276	Intersectable::NewMail();
5277	KdLeaf::NewMail();
5278
5279	vector<KdLeaf *> kdLeaves;
5280
5281	ObjectPvsMap::const_iterator oit, oit_end = pvs.mEntries.end();
5282
5283	for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
5284	{
5285	Intersectable obj = (oit).first;
5286
5287	if (obj->Type() == Intersectable::KD_INTERSECTABLE)
5288	{
5289	m.mDiffuseColor = RgbColor(1, 1, 1);
5290	exporter->SetForcedMaterial(m);
5291
5292	// export bounding box of node
5293	KdIntersectable kdObj = dynamic_cast<KdIntersectable >(obj);
5294	AxisAlignedBox3 box = mOspTree->GetBoundingBox(kdObj->GetItem());
5295
5296	exporter->SetWireframe();
5297	exporter->ExportBox(box);
5298	exporter->SetFilled();
5299	}
5300
5301	m.mDiffuseColor = RgbColor(1, 0, 0);
5302	exporter->SetForcedMaterial(m);
5303
5304	// export pvs entry
5305	if (!obj->Mailed())
5306	{
5307	exporter->ExportIntersectable(obj);
5308	obj->Mail();
5309	}
5310	}
5311	#endif
5312
5313	DEL_PTR(exporter);
5314	cout << "finished" << endl;
5315	}
5316
5317	Debug << endl;
5318	}
5319
5320
5321	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5322	ViewCellContainer &viewCells) const
5323	{
5324	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
5325	}
5326
5327
5328	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
5329	const Vector3 &termination,
5330	ViewCellContainer &viewcells)
5331	{
5332	return mHierarchyManager->GetVspTree()->CastLineSegment(origin, termination, viewcells);
5333	}
5334
5335
5336	bool VspOspViewCellsManager::ExportViewCells(const string filename,
5337	const bool exportPvs,
5338	const ObjectContainer &objects)
5339	{
5340	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
5341	return false;
5342
5343	cout << "exporting view cells to xml ... ";
5344
5345	OUT_STREAM stream(filename.c_str());
5346
5347	// for output we need unique ids for each view cell
5348	CreateUniqueViewCellIds();
5349
5350	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
5351	stream << "<VisibilitySolution>" << endl;
5352
5353
5354	//-- export bounding boxes
5355
5356	stream << "<BoundingBoxes>" << endl;
5357
5358	ObjectContainer::const_iterator oit, oit_end = objects.end();
5359
5360	for (oit = objects.begin(); oit != oit_end; ++ oit)
5361	{
5362	MeshInstance mi = dynamic_cast<MeshInstance >(*oit);
5363	const AxisAlignedBox3 box = mi->GetBox();
5364
5365	//-- the bounding boxes
5366	stream << "<BoundingBox" << " id=\"" << mi->GetId() << "\""
5367	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
5368	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
5369	}
5370
5371	stream << "</BoundingBoxes>" << endl;
5372
5373
5374	//-- export the view cells and the pvs
5375
5376	const int numViewCells = mCurrentViewCellsStats.viewCells;
5377
5378	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
5379	mViewCellsTree->Export(stream, exportPvs);
5380	stream << "</ViewCells>" << endl;
5381
5382
5383	//-- export the view space hierarchy
5384
5385	stream << "<ViewSpaceHierarchy type=\"vsp\""
5386	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
5387	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
5388
5389	mHierarchyManager->GetVspTree()->Export(stream);
5390	stream << "</ViewSpaceHierarchy>" << endl;
5391
5392
5393	//-- export the object space partition
5394
5395	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
5396
5397	stream << "</VisibilitySolution>" << endl;
5398	stream.close();
5399
5400	cout << "finished" << endl;
5401
5402	return true;
5403	}
5404
5405
5406
5407	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
5408	const bool active) const
5409	{
5410	if (!ViewCellsConstructed())
5411	return NULL;
5412
5413	if (!mViewSpaceBox.IsInside(point))
5414	return NULL;
5415
5416	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
5417	}
5418
5419
5420	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
5421	{
5422	// matt: TODO
5423	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5424
5425	ViewCellContainer leaves;
5426	mViewCellsTree->CollectLeaves(vc, leaves);
5427
5428	ViewCellContainer::const_iterator it, it_end = leaves.end();
5429
5430	for (it = leaves.begin(); it != it_end; ++ it)
5431	{
5432	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaf;
5433	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5434
5435	IncludeBoxInMesh(box, *mesh);
5436	}
5437
5438	vc->SetMesh(mesh);
5439	}
5440
5441
5442	int VspOspViewCellsManager::CastBeam(Beam &beam)
5443	{
5444	// matt: TODO
5445	return 0;
5446	}
5447
5448
5449	void VspOspViewCellsManager::Finalize(ViewCell *viewCell,
5450	const bool createMesh)
5451	{
5452	float area = 0;
5453	float volume = 0;
5454
5455	ViewCellContainer leaves;
5456	mViewCellsTree->CollectLeaves(viewCell, leaves);
5457
5458	ViewCellContainer::const_iterator it, it_end = leaves.end();
5459
5460	for (it = leaves.begin(); it != it_end; ++ it)
5461	{
5462	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaf;
5463
5464	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5465
5466	const float lVol = box.GetVolume();
5467	const float lArea = box.SurfaceArea();
5468
5469	//(*it)->SetVolume(vol);
5470	//(*it)->SetArea(area);
5471
5472	area += lArea;
5473	volume += lVol;
5474
5475	CreateMesh(*it);
5476	}
5477
5478	viewCell->SetVolume(volume);
5479	viewCell->SetArea(area);
5480	}
5481
5482
5483	float VspOspViewCellsManager::ComputeSampleContribution(VssRay &ray,
5484	const bool addRays,
5485	const bool storeViewCells)
5486	{
5487	ViewCellContainer viewcells;
5488
5489	ray.mPvsContribution = 0;
5490	ray.mRelativePvsContribution = 0.0f;
5491
5492	static Ray hray;
5493	hray.Init(ray);
5494	//hray.mFlags \|= Ray::CULL_BACKFACES;
5495	//Ray hray(ray);
5496
5497	float tmin = 0, tmax = 1.0;
5498
5499	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
5500	return 0;
5501
5502	Vector3 origin = hray.Extrap(tmin);
5503	Vector3 termination = hray.Extrap(tmax);
5504
5505	// traverse the view space subdivision
5506	CastLineSegment(origin, termination, viewcells);
5507
5508	if (storeViewCells)
5509	{ // copy viewcells memory efficiently
5510	ray.mViewCells.reserve(viewcells.size());
5511	ray.mViewCells = viewcells;
5512	}
5513
5514	ViewCellContainer::const_iterator it = viewcells.begin();
5515
5516	for (; it != viewcells.end(); ++ it)
5517	{
5518	ViewCell viewcell = it;
5519
5520	if (viewcell->GetValid())
5521	{
5522	// if ray not outside of view space
5523	float contribution;
5524
5525	if (ray.mTerminationObject)
5526	{
5527	// todo: maybe not correct for kd node pvs
5528	if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
5529	ray.mPdf, contribution))
5530	{
5531	++ ray.mPvsContribution;
5532	}
5533
5534	ray.mRelativePvsContribution += contribution;
5535	}
5536
5537	// for directional sampling it is important to count only contributions
5538	// made in one direction!!!
5539	// the other contributions of this sample will be counted for the oposite ray!
5540	#if SAMPLE_ORIGIN_OBJECTS
5541	if (ray.mOriginObject &&
5542	viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
5543	ray.mPdf,
5544	contribution))
5545	{
5546	++ ray.mPvsContribution;
5547	ray.mRelativePvsContribution += contribution;
5548	}
5549	#endif
5550	}
5551	}
5552
5553	if (!addRays)
5554	return ray.mRelativePvsContribution;
5555
5556	// sampled objects are stored in the pvs
5557	for (it = viewcells.begin(); it != viewcells.end(); ++ it)
5558	{
5559	ViewCell viewCell = it;
5560
5561	if (!viewCell->GetValid())
5562	break;
5563
5564	AddSampleToPvs(
5565	ray.mTerminationObject,
5566	ray.mTermination,
5567	viewCell,
5568	ray.mPdf,
5569	ray.mRelativePvsContribution);
5570
5571	#if SAMPLE_ORIGIN_OBJECTS
5572
5573	AddSampleToPvs(
5574	ray.mOriginObject,
5575	ray.mOrigin,
5576	viewCell,
5577	ray.mPdf,
5578	ray.mRelativePvsContribution);
5579	#endif
5580	}
5581
5582	return ray.mRelativePvsContribution;
5583	}
5584
5585
5586	bool VspOspViewCellsManager::AddSampleToPvs(Intersectable *obj,
5587	const Vector3 &hitPoint,
5588	ViewCell *vc,
5589	const float pdf,
5590	float &contribution) const
5591	{
5592	return mHierarchyManager->AddSampleToPvs(obj, hitPoint, vc, pdf, contribution);
5593	}
5594
5595
5596	void VspOspViewCellsManager::PrepareLoadedViewCells()
5597	{
5598	// TODO
5599	}
5600
5601
5602	ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
5603	ObjectContainer *objects,
5604	const bool finalizeViewCells,
5605	BoundingBoxConverter *bconverter)
5606
5607	{
5608	ViewCellsManager *vm =
5609	ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
5610	#if 0
5611	// insert scene objects in tree
5612	mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);
5613	#endif
5614	return vm;
5615	}
5616
5617
5618	#if TEST_EVALUATION
5619	void VspOspViewCellsManager::EvalViewCellPartition()
5620	{
5621	int castSamples = (int)storedRays.size();
5622
5623	char s[64];
5624	char statsPrefix[100];
5625
5626	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
5627
5628	Debug << "view cell stats prefix: " << statsPrefix << endl;
5629
5630	// should directional sampling be used?
5631	bool dirSamples = (mEvaluationSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);
5632
5633	cout << "reseting pvs ... ";
5634
5635	const bool startFromZero = true;
5636
5637
5638	// reset pvs and start over from zero
5639	if (startFromZero)
5640	{
5641	mViewCellsTree->ResetPvs();
5642	}
5643	else // start from current sampless
5644	{
5645	// statistics before casting more samples
5646	cout << "compute new statistics ... ";
5647	sprintf(s, "-%09d-eval.log", castSamples);
5648	string fName = string(statsPrefix) + string(s);
5649
5650	mViewCellsTree->ExportStats(fName);
5651	cout << "finished" << endl;
5652	}
5653	cout << "finished" << endl;
5654
5655	cout << "Evaluating view cell partition ... " << endl;
5656
5657	VssRayContainer evaluationSamples = storedRays;
5658	const int samplingType = mEvaluationSamplingType;
5659
5660	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
5661
5662	ComputeSampleContributions(evaluationSamples, true, false);
5663
5664	cout << "finished" << endl;
5665
5666	cout << "compute new statistics ... ";
5667	Debug << "compute new statistics ... ";
5668
5669	// propagate pvs or pvs size information
5670	ObjectPvs pvs;
5671	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), pvs);
5672
5673	///////////////////////////////////////
5674	//-- temporary matt: test render cost
5675
5676	sprintf(s, "-%09d-eval.log", castSamples);
5677	string fileName = string(statsPrefix) + string(s);
5678
5679	ViewCellContainer leaves;
5680
5681	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5682	float rc = 0;
5683	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5684	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5685	{
5686	ViewCell vc = vit;
5687	int pvs = vc->GetPvs().CountObjectsInPvs();
5688	float vol = vc->GetVolume();
5689	rc += pvs * vol;
5690
5691	}
5692
5693	Debug << "\nhere295 " << rc / mHierarchyManager->GetVspTree()->GetBoundingBox().GetVolume() << endl;
5694	mViewCellsTree->ExportStats(fileName);
5695	cout << "finished" << endl;
5696
5697	disposeRays(evaluationSamples, NULL);
5698	}
5699	#endif
5700
5701
5702	}

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

Download in other formats: