Context Navigation

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

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

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

Download in other formats: