Context Navigation

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

Revision 1074, 137.7 KB checked in by mattausch, 18 years ago (diff)
wked on view space object space partition

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

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

Download in other formats: