Context Navigation

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

Revision 1278, 141.8 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: