Context Navigation

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

Revision 1566, 139.9 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: