Context Navigation

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

Revision 1520, 140.1 KB checked in by mattausch, 18 years ago (diff)
moved raycasting out of preprocessor into specific ray casting interface

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

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

Download in other formats: