Context Navigation

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

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

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

Download in other formats: