Context Navigation

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

Revision 1077, 137.7 KB checked in by mattausch, 18 years ago (diff)
worked on object space /view space partitioning

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
389	SimpleRayContainer simpleRays;
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 (0) // 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	if (1) 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 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
3676	if (0)
3677	{
3678	//-- real meshes are contructed at this stage
3679	cout << "finalizing view cells ... ";
3680	FinalizeViewCells(true);
3681	cout << "finished" << endl;
3682	}
3683
3684	return sampleContributions;
3685	}
3686
3687
3688	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
3689	const ObjectContainer &objects)
3690	{
3691	int vcSize = 0;
3692	int pvsSize = 0;
3693
3694	//-- merge view cells
3695	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
3696	long startTime = GetTime();
3697
3698
3699	if (mMergeViewCells)
3700	{
3701	// TODO: should be done BEFORE the ray casting
3702	// compute tree by merging the nodes based on cost heuristics
3703	mViewCellsTree->ConstructMergeTree(rays, objects);
3704	}
3705	else
3706	{
3707	// compute tree by merging the nodes of the spatial hierarchy
3708	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
3709	mViewCellsTree->SetRoot(root);
3710
3711	// compute pvs
3712	ObjectPvs pvs;
3713	UpdatePvsForEvaluation(root, pvs);
3714	}
3715
3716	if (1)
3717	{
3718	char mstats[100];
3719	ObjectPvs pvs;
3720
3721	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3722	mViewCellsTree->ExportStats(mstats);
3723	}
3724
3725	//-- stats and visualizations
3726	cout << "finished merging" << endl;
3727	cout << "merged view cells in "
3728	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
3729
3730	Debug << "Postprocessing: Merged view cells in "
3731	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
3732
3733
3734	int savedColorCode = mColorCode;
3735
3736	// get currently active view cell set
3737	ResetViewCells();
3738	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3739
3740	//BspLeaf::NewMail();
3741	if (1) // export merged view cells
3742	{
3743	mColorCode = 0;
3744	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
3745
3746	cout << "exporting view cells after merge ... ";
3747
3748	if (exporter)
3749	{
3750	if (0)
3751	exporter->SetWireframe();
3752	else
3753	exporter->SetFilled();
3754
3755	ExportViewCellsForViz(exporter);
3756
3757	if (mExportGeometry)
3758	{
3759	Material m;
3760	m.mDiffuseColor = RgbColor(0, 1, 0);
3761	exporter->SetForcedMaterial(m);
3762	exporter->SetFilled();
3763
3764	exporter->ExportGeometry(objects);
3765	}
3766
3767	delete exporter;
3768	}
3769	cout << "finished" << endl;
3770	}
3771
3772	if (0) // export merged view cells using pvs coding
3773	{
3774	mColorCode = 1;
3775
3776	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3777
3778	cout << "exporting view cells after merge (pvs size) ... ";
3779
3780	if (exporter)
3781	{
3782	if (0)
3783	exporter->SetWireframe();
3784	else
3785	exporter->SetFilled();
3786
3787	ExportViewCellsForViz(exporter);
3788
3789	if (mExportGeometry)
3790	{
3791	Material m;
3792	m.mDiffuseColor = RgbColor(0, 1, 0);
3793	exporter->SetForcedMaterial(m);
3794	exporter->SetFilled();
3795
3796	exporter->ExportGeometry(objects);
3797	}
3798
3799	delete exporter;
3800	}
3801	cout << "finished" << endl;
3802	}
3803
3804	mColorCode = savedColorCode;
3805
3806	}
3807
3808
3809	bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
3810	{
3811	return GetSpatialNode(viewCell) != NULL;
3812	}
3813
3814
3815	BspNode VspBspViewCellsManager::GetSpatialNode(ViewCell viewCell) const
3816	{
3817	if (!viewCell->IsLeaf())
3818	{
3819	BspViewCell bspVc = dynamic_cast<BspViewCell >(viewCell);
3820
3821	return bspVc->mLeaf;
3822	}
3823	else
3824	{
3825	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
3826
3827	// cannot be node of binary tree
3828	if (interior->mChildren.size() != 2)
3829	return NULL;
3830
3831	ViewCell *left = interior->mChildren[0];
3832	ViewCell *right = interior->mChildren[1];
3833
3834	BspNode *leftNode = GetSpatialNode(left);
3835	BspNode *rightNode = GetSpatialNode(right);
3836
3837	if (leftNode && rightNode && leftNode->IsSibling(rightNode))
3838	{
3839	return leftNode->GetParent();
3840	}
3841	}
3842
3843	return NULL;
3844	}
3845
3846
3847	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
3848	const ObjectContainer &objects)
3849	{
3850	Debug << "render time before refine:" << endl;
3851	mRenderer->RenderScene();
3852	SimulationStatistics ss;
3853	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3854	Debug << ss << endl;
3855
3856	cout << "Refining the merged view cells ... ";
3857	long startTime = GetTime();
3858
3859	// refining the merged view cells
3860	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
3861
3862	//-- stats and visualizations
3863	cout << "finished" << endl;
3864	cout << "refined " << refined << " view cells in "
3865	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
3866
3867	Debug << "Postprocessing: refined " << refined << " view cells in "
3868	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
3869	}
3870
3871
3872	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
3873	const VssRayContainer &rays)
3874	{
3875	if (!ViewCellsConstructed())
3876	{
3877	Debug << "postprocess error: no view cells constructed" << endl;
3878	return 0;
3879	}
3880
3881
3882	// view cells already finished before post processing step
3883	// (i.e. because they were loaded)
3884	if (mViewCellsFinished)
3885	{
3886	FinalizeViewCells(true);
3887	EvaluateViewCellsStats();
3888
3889	return 0;
3890	}
3891
3892	// check if new view cells turned invalid
3893	int minPvs, maxPvs;
3894
3895	if (0)
3896	{
3897	minPvs = mMinPvsSize;
3898	maxPvs = mMaxPvsSize;
3899	}
3900	else
3901	{
3902	minPvs = mPruneEmptyViewCells ? 1 : 0;
3903	maxPvs = mMaxPvsSize;
3904	}
3905
3906	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
3907	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
3908
3909	SetValidity(minPvs, maxPvs);
3910
3911	// update valid view space according to valid view cells
3912	if (0) mVspBspTree->ValidateTree();
3913
3914	// area has to be recomputed
3915	mTotalAreaValid = false;
3916	VssRayContainer postProcessRays;
3917	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3918
3919	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
3920
3921
3922	// should maybe be done here to allow merge working with area or volume
3923	// and to correct the rendering statistics
3924	if (0) FinalizeViewCells(false);
3925
3926	//-- merge the individual view cells
3927	MergeViewCells(postProcessRays, objects);
3928
3929
3930	// only for debugging purpose: test if the subdivision is valid
3931	TestSubdivision();
3932
3933	//-- refines the merged view cells
3934	if (0) RefineViewCells(postProcessRays, objects);
3935
3936
3937	//-- render simulation after merge + refine
3938	cout << "\nevaluating bsp view cells render time before compress ... ";
3939	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
3940	SimulationStatistics ss;
3941	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
3942
3943
3944	cout << " finished" << endl;
3945	cout << ss << endl;
3946	Debug << ss << endl;
3947
3948
3949	//-- compression
3950	if (ViewCellsTreeConstructed() && mCompressViewCells)
3951	{
3952	int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
3953	Debug << "number of entries before compress: " << pvsEntries << endl;
3954
3955	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
3956
3957	pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
3958	Debug << "number of entries after compress: " << pvsEntries << endl;
3959	}
3960
3961
3962	// collapse sibling leaves that share the same view cell
3963	if (0) mVspBspTree->CollapseTree();
3964
3965	// recompute view cell list and statistics
3966	ResetViewCells();
3967
3968	// compute final meshes and volume / area
3969	if (1) FinalizeViewCells(true);
3970
3971	// write view cells to disc
3972	if (mExportViewCells)
3973	{
3974	char filename[100];
3975	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
3976	ExportViewCells(filename, mExportPvs, objects);
3977	}
3978
3979
3980	// export bounding boxes
3981	if (mExportBboxesForPvs)
3982	{
3983	char filename[100];
3984	Environment::GetSingleton()->GetStringValue("ViewCells.boxesFilename", filename);
3985
3986	ExportBoundingBoxes(filename, objects);
3987	}
3988
3989	return 0;
3990	}
3991
3992
3993	int VspBspViewCellsManager::GetType() const
3994	{
3995	return VSP_BSP;
3996	}
3997
3998
3999	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4000	{
4001	// terminate recursion
4002	if (root->IsLeaf())
4003	{
4004	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
4005	leaf->GetViewCell()->SetMergeCost(0.0f);
4006	return leaf->GetViewCell();
4007	}
4008
4009
4010	BspInterior interior = dynamic_cast<BspInterior >(root);
4011	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4012
4013	// evaluate merge cost for priority traversal
4014	float mergeCost = 1.0f / (float)root->mTimeStamp;
4015	viewCellInterior->SetMergeCost(mergeCost);
4016
4017	float volume = 0;
4018
4019	BspNode *front = interior->GetFront();
4020	BspNode *back = interior->GetBack();
4021
4022
4023	ObjectPvs frontPvs, backPvs;
4024
4025	//-- recursivly compute child hierarchies
4026	ViewCell *backVc = ConstructSpatialMergeTree(back);
4027	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4028
4029
4030	viewCellInterior->SetupChildLink(backVc);
4031	viewCellInterior->SetupChildLink(frontVc);
4032
4033	volume += backVc->GetVolume();
4034	volume += frontVc->GetVolume();
4035
4036	viewCellInterior->SetVolume(volume);
4037
4038	return viewCellInterior;
4039	}
4040
4041
4042
4043	void VspBspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
4044	{
4045	// terminate traversal
4046	if (root->IsLeaf())
4047	{
4048	pvs = root->GetPvs();
4049	SetScalarPvsSize(root, root->GetPvs().GetSize());
4050
4051	return;
4052	}
4053
4054	//-- interior node => propagate pvs up
4055	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
4056	interior->GetPvs().Clear();
4057	pvs.Clear();
4058	vector<ObjectPvs> pvsList;
4059
4060	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
4061
4062	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
4063	{
4064	ObjectPvs objPvs;
4065
4066	//-- recursivly compute child pvss
4067	UpdatePvsForEvaluation(*vit, objPvs);
4068
4069	// store pvs in vector
4070	pvsList.push_back(objPvs);
4071	}
4072
4073	#if 1
4074
4075	Intersectable::NewMail();
4076
4077	//-- faster way of computing pvs:
4078	// construct merged pvs by adding
4079	// and only those of the next pvs which were not mailed.
4080	// note: sumpdf is not correct!!
4081	vector<ObjectPvs>::iterator oit = pvsList.begin();
4082
4083	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
4084	{
4085	ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
4086
4087	for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
4088	{
4089	Intersectable intersect = (pit).first;
4090
4091	if (!intersect->Mailed())
4092	{
4093	pvs.AddSample(intersect, (*pit).second.mSumPdf);
4094	intersect->Mail();
4095	}
4096	}
4097	}
4098
4099	// store pvs in this node
4100	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
4101	{
4102	interior->SetPvs(pvs);
4103	}
4104
4105	// set new pvs size
4106	SetScalarPvsSize(interior, pvs.GetSize());
4107
4108
4109	#else
4110
4111	// really merge cells: slow but sumpdf is correct
4112	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
4113	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
4114	#endif
4115
4116	}
4117
4118
4119	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4120	{
4121	if (!ViewCellsConstructed())
4122	return ViewCellsManager::GetViewPoint(viewPoint);
4123
4124	// TODO: set reasonable limit
4125	const int limit = 20;
4126
4127	for (int i = 0; i < limit; ++ i)
4128	{
4129	viewPoint = mViewSpaceBox.GetRandomPoint();
4130	if (mVspBspTree->ViewPointValid(viewPoint))
4131	{
4132	return true;
4133	}
4134	}
4135
4136	Debug << "failed to find valid view point, taking " << viewPoint << endl;
4137	return false;
4138	}
4139
4140
4141	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4142	{
4143	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4144	// validy update in preprocessor for all managers)
4145	return ViewCellsManager::ViewPointValid(viewPoint);
4146
4147	// return mViewSpaceBox.IsInside(viewPoint) &&
4148	// mVspBspTree->ViewPointValid(viewPoint);
4149	}
4150
4151
4152	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4153	const VssRayContainer &sampleRays)
4154	{
4155	if (!ViewCellsConstructed())
4156	return;
4157
4158	VssRayContainer visRays;
4159	GetRaySets(sampleRays, mVisualizationSamples, visRays);
4160
4161	//-- export final view cell partition
4162
4163	if (0)
4164	{
4165	// hack pvs
4166	//const int savedColorCode = mColorCode;
4167	//mColorCode = 1;
4168
4169	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4170
4171	if (exporter)
4172	{
4173	cout << "exporting view cells after post process ... ";
4174
4175	if (0)
4176	{
4177	// export view space box
4178	exporter->SetWireframe();
4179	exporter->ExportBox(mViewSpaceBox);
4180	exporter->SetFilled();
4181	}
4182
4183	Material m;
4184
4185	m.mDiffuseColor.r = 0.0f;
4186	m.mDiffuseColor.g = 0.5f;
4187	m.mDiffuseColor.b = 0.5f;
4188
4189	exporter->SetForcedMaterial(m);
4190
4191	if (0 && mExportGeometry)
4192	{
4193	exporter->ExportGeometry(objects);
4194	}
4195
4196	// export rays
4197	if (0 && mExportRays)
4198	{
4199	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4200	}
4201
4202	//exporter->SetFilled();
4203
4204	// HACK: export without clip plane
4205	const bool b = mUseClipPlaneForViz;
4206	//mUseClipPlaneForViz = false;
4207
4208	ExportViewCellsForViz(exporter);
4209
4210	mUseClipPlaneForViz = b;
4211	delete exporter;
4212
4213	cout << "finished" << endl;
4214	}
4215
4216	//mColorCode = savedColorCode;
4217	}
4218
4219
4220	if (0)
4221	{
4222	cout << "exporting depth map ... ";
4223
4224	Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
4225	if (exporter)
4226	{
4227	if (1)
4228	{
4229	exporter->SetWireframe();
4230	exporter->ExportBox(mViewSpaceBox);
4231	exporter->SetFilled();
4232	}
4233
4234	if (mExportGeometry)
4235	{
4236	exporter->ExportGeometry(objects);
4237	}
4238
4239	const int maxDepth = mVspBspTree->mBspStats.maxDepth;
4240
4241	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
4242
4243	for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
4244	{
4245	ViewCell vc = vit;
4246
4247	ViewCellContainer leaves;
4248	mViewCellsTree->CollectLeaves(vc, leaves);
4249
4250	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
4251
4252	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4253	{
4254	BspLeaf leaf = dynamic_cast<BspViewCell >(*lit)->mLeaf;
4255
4256	Material m;
4257
4258	float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
4259	m.mDiffuseColor.r = relDepth;
4260	m.mDiffuseColor.g = 0.0f;
4261	m.mDiffuseColor.b = 1.0f - relDepth;
4262
4263	exporter->SetForcedMaterial(m);
4264
4265
4266	BspNodeGeometry geom;
4267	mVspBspTree->ConstructGeometry(leaf, geom);
4268	exporter->ExportPolygons(geom.GetPolys());
4269	}
4270	}
4271
4272	delete exporter;
4273	}
4274
4275
4276	cout << "finished" << endl;
4277	}
4278
4279	//-- visualization of the BSP splits
4280	bool exportSplits = false;
4281	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4282
4283	if (exportSplits)
4284	{
4285	cout << "exporting splits ... ";
4286	ExportSplits(objects, visRays);
4287	cout << "finished" << endl;
4288	}
4289
4290	//-- export single view cells
4291	ExportBspPvs(objects, visRays);
4292	}
4293
4294
4295	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
4296	const VssRayContainer &rays)
4297	{
4298	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4299
4300	if (exporter)
4301	{
4302	Material m;
4303	m.mDiffuseColor = RgbColor(1, 0, 0);
4304	exporter->SetForcedMaterial(m);
4305	exporter->SetWireframe();
4306
4307	exporter->ExportBspSplits(*mVspBspTree, true);
4308
4309	// take forced material, else big scenes cannot be viewed
4310	m.mDiffuseColor = RgbColor(0, 1, 0);
4311	exporter->SetForcedMaterial(m);
4312	exporter->SetFilled();
4313
4314	exporter->ResetForcedMaterial();
4315
4316	// export rays
4317	if (mExportRays)
4318	exporter->ExportRays(rays, RgbColor(1, 1, 0));
4319
4320	if (mExportGeometry)
4321	exporter->ExportGeometry(objects);
4322
4323	delete exporter;
4324	}
4325	}
4326
4327
4328	void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
4329	const VssRayContainer &rays)
4330	{
4331	int leafOut;
4332	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4333
4334	ViewCell::NewMail();
4335
4336	cout << "visualization using " << (int)rays.size() << " samples" << endl;
4337	Debug << "visualization using " << (int)rays.size() << " samples" << endl;
4338	Debug << "\nOutput view cells: " << endl;
4339
4340	const bool sortViewCells = true;
4341
4342	// sort view cells to visualize the largest view cells
4343	if (sortViewCells)
4344	{
4345	//stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
4346	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4347	}
4348
4349	int limit = min(leafOut, (int)mViewCells.size());
4350
4351	int raysOut = 0;
4352
4353	//-- some rays for output
4354	for (int i = 0; i < limit; ++ i)
4355	{
4356	cout << "creating output for view cell " << i << " ... ";
4357
4358	ViewCell *vc;
4359
4360	if (sortViewCells) // largest view cell pvs first
4361	vc = mViewCells[i];
4362	else
4363	vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
4364
4365	ObjectPvs pvs;
4366	mViewCellsTree->GetPvs(vc, pvs);
4367
4368	//bspLeaves[j]->Mail();
4369	char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
4370	Exporter *exporter = Exporter::GetExporter(s);
4371
4372	Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
4373
4374	//-- export the sample rays
4375	if (mExportRays)
4376	{
4377	// output rays stored with the view cells during subdivision
4378	if (1)
4379	{
4380	VssRayContainer vcRays;
4381	VssRayContainer collectRays;
4382
4383	raysOut = min((int)rays.size(), 100);
4384
4385	// collect intial view cells
4386	ViewCellContainer leaves;
4387	mViewCellsTree->CollectLeaves(vc, leaves);
4388
4389	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4390
4391	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4392	{
4393	BspLeaf vcLeaf = dynamic_cast<BspViewCell >(*vit)->mLeaf;
4394
4395	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
4396
4397	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
4398	{
4399	collectRays.push_back(*rit);
4400	}
4401	}
4402
4403	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4404
4405	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4406	{
4407	float p = RandomValue(0.0f, (float)collectRays.size());
4408
4409	if (p < raysOut)
4410	vcRays.push_back(*rit);
4411	}
4412
4413	//Debug << "#rays: " << (int)vcRays.size() << endl;
4414
4415	//-- export rays piercing this view cell
4416	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
4417	}
4418
4419	// associate new rays with output view cell
4420	if (0)
4421	{
4422	VssRayContainer vcRays;
4423	raysOut = min((int)rays.size(), mVisualizationSamples);
4424
4425	// check whether we can add the current ray to the output rays
4426	for (int k = 0; k < raysOut; ++ k)
4427	{
4428	VssRay *ray = rays[k];
4429	for (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
4430	{
4431	ViewCell *rayvc = ray->mViewCells[j];
4432
4433	if (rayvc == vc)
4434	vcRays.push_back(ray);
4435	}
4436	}
4437
4438	//-- export rays piercing this view cell
4439	exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
4440	}
4441
4442	}
4443
4444
4445	//-- export view cell geometry
4446	exporter->SetWireframe();
4447
4448	Material m;//= RandomMaterial();
4449	m.mDiffuseColor = RgbColor(0, 1, 0);
4450	exporter->SetForcedMaterial(m);
4451
4452	ExportViewCellGeometry(exporter, vc);
4453
4454	exporter->SetFilled();
4455
4456
4457	//-- export pvs
4458	if (1)
4459	{
4460	ObjectPvsMap::const_iterator oit,
4461	oit_end = pvs.mEntries.end();
4462
4463	Intersectable::NewMail();
4464
4465	// output PVS of view cell
4466	for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
4467	{
4468	Intersectable intersect = (oit).first;
4469
4470	if (!intersect->Mailed())
4471	{
4472	m = RandomMaterial();
4473	exporter->SetForcedMaterial(m);
4474
4475	exporter->ExportIntersectable(intersect);
4476	intersect->Mail();
4477	}
4478	}
4479	}
4480
4481	if (0)
4482	{ // export scene geometry
4483	m.mDiffuseColor = RgbColor(1, 0, 0);
4484	exporter->SetForcedMaterial(m);
4485
4486	exporter->ExportGeometry(objects);
4487	}
4488
4489	DEL_PTR(exporter);
4490	cout << "finished" << endl;
4491	}
4492
4493	Debug << endl;
4494	}
4495
4496
4497	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
4498	{
4499	Exporter *exporter = Exporter::GetExporter("filter.x3d");
4500
4501	Vector3 bsize = mViewSpaceBox.Size();
4502	const Vector3 viewPoint(mViewSpaceBox.Center());
4503	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
4504	const Vector3 width = Vector3(w);
4505
4506	PrVs testPrVs;
4507
4508	if (exporter)
4509	{
4510	ViewCellContainer viewCells;
4511
4512	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
4513
4514	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
4515
4516	exporter->SetWireframe();
4517
4518	exporter->SetForcedMaterial(RgbColor(1,1,1));
4519	exporter->ExportBox(tbox);
4520
4521	exporter->SetFilled();
4522
4523	exporter->SetForcedMaterial(RgbColor(0,1,0));
4524	ExportViewCellGeometry(exporter, GetViewCell(viewPoint));
4525
4526	//exporter->ResetForcedMaterial();
4527	exporter->SetForcedMaterial(RgbColor(0,0,1));
4528	ExportViewCellGeometry(exporter, testPrVs.mViewCell);
4529
4530	exporter->SetForcedMaterial(RgbColor(1,0,0));
4531	exporter->ExportGeometry(objects);
4532
4533	delete exporter;
4534	}
4535	}
4536
4537
4538	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
4539	ViewCellContainer &viewCells) const
4540	{
4541	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
4542	}
4543
4544
4545	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
4546	const Vector3 &termination,
4547	ViewCellContainer &viewcells)
4548	{
4549	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
4550	}
4551
4552
4553	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
4554	{
4555	int numSamples;
4556
4557	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
4558	cout << "samples" << numSamples << endl;
4559
4560	vector<RenderCostSample> samples;
4561
4562	if (!preprocessor->GetRenderer())
4563	return;
4564
4565	//start the from point queries
4566	long startTime = GetTime();
4567	cout << "starting sampling of render cost ... ";
4568
4569	preprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
4570
4571	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4572
4573
4574	// counting the pvss
4575	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
4576
4577	//std::map<ViewCell *, ObjectPvs> sampleMap;
4578
4579	for (rit = samples.begin(); rit != rit_end; ++ rit)
4580	{
4581	RenderCostSample sample = *rit;
4582
4583	ViewCell *vc = GetViewCell(sample.mPosition);
4584
4585	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
4586	Mesh *hMesh = CreateMeshFromBox(box);
4587
4588	DEL_PTR(hMesh);
4589	#if 0
4590	if (!sampleMap.find(vc))
4591	sampleMap.insert(vc, sample.mVisibleObjects);
4592	else
4593	sampleMap[vc].Merge(Merge(sample.mVisibleObjects);
4594	#endif
4595	}
4596	}
4597
4598
4599	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4600	ViewCell *vc,
4601	const AxisAlignedPlane *clipPlane) const
4602	{
4603	if (clipPlane)
4604	{
4605	const Plane3 plane = clipPlane->GetPlane();
4606
4607	ViewCellContainer leaves;
4608	mViewCellsTree->CollectLeaves(vc, leaves);
4609	ViewCellContainer::const_iterator it, it_end = leaves.end();
4610
4611	for (it = leaves.begin(); it != it_end; ++ it)
4612	{
4613	BspNodeGeometry geom;
4614
4615	BspNodeGeometry front;
4616	BspNodeGeometry back;
4617
4618	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
4619	mVspBspTree->ConstructGeometry(leaf, geom);
4620
4621	const float eps = 0.0001f;
4622	const int cf = geom.Side(plane, eps);
4623
4624	if (cf == -1)
4625	{
4626	exporter->ExportPolygons(geom.GetPolys());
4627	}
4628	else if (cf == 0)
4629	{
4630	geom.SplitGeometry(front,
4631	back,
4632	plane,
4633	mViewSpaceBox,
4634	eps);
4635
4636	//Debug << "geo size: " << geom.Size() << endl;
4637	//Debug << "size b: " << back.Size() << " f: " << front.Size() << endl;
4638
4639	if (back.Valid())
4640	{
4641	exporter->ExportPolygons(back.GetPolys());
4642	}
4643	}
4644	}
4645	}
4646	else
4647	{
4648	// export mesh if available
4649	// TODO: some bug here?
4650	if (0 && vc->GetMesh())
4651	{
4652	exporter->ExportMesh(vc->GetMesh());
4653	}
4654	else
4655	{
4656	BspNodeGeometry geom;
4657	mVspBspTree->ConstructGeometry(vc, geom);
4658	exporter->ExportPolygons(geom.GetPolys());
4659	}
4660	}
4661	}
4662
4663
4664	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
4665	{
4666	ViewCellContainer leaves;
4667	mViewCellsTree->CollectLeaves(vc, leaves);
4668
4669	int maxDist = 0;
4670
4671	// compute max height difference
4672	for (int i = 0; i < (int)leaves.size(); ++ i)
4673	{
4674	for (int j = 0; j < (int)leaves.size(); ++ j)
4675	{
4676	BspLeaf leaf = dynamic_cast<BspViewCell >(leaves[i])->mLeaf;
4677
4678	if (i != j)
4679	{
4680	BspLeaf leaf2 =dynamic_cast<BspViewCell >(leaves[j])->mLeaf;
4681
4682	int dist = mVspBspTree->TreeDistance(leaf, leaf2);
4683
4684	if (dist > maxDist)
4685	maxDist = dist;
4686	}
4687	}
4688	}
4689
4690	return maxDist;
4691	}
4692
4693
4694	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4695	{
4696	if (!ViewCellsConstructed())
4697	return NULL;
4698
4699	if (!mViewSpaceBox.IsInside(point))
4700	return NULL;
4701
4702	return mVspBspTree->GetViewCell(point, active);
4703	}
4704
4705
4706	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
4707	{
4708	//if (vc->GetMesh()) delete vc->GetMesh();
4709	BspNodeGeometry geom;
4710
4711	mVspBspTree->ConstructGeometry(vc, geom);
4712
4713	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4714	IncludeNodeGeomInMesh(geom, *mesh);
4715
4716	vc->SetMesh(mesh);
4717	}
4718
4719
4720	int VspBspViewCellsManager::CastBeam(Beam &beam)
4721	{
4722	return mVspBspTree->CastBeam(beam);
4723	}
4724
4725
4726	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
4727	const bool createMesh)
4728	{
4729	float area = 0;
4730	float volume = 0;
4731
4732	ViewCellContainer leaves;
4733	mViewCellsTree->CollectLeaves(viewCell, leaves);
4734
4735	ViewCellContainer::const_iterator it, it_end = leaves.end();
4736
4737	for (it = leaves.begin(); it != it_end; ++ it)
4738	{
4739	BspNodeGeometry geom;
4740	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
4741	mVspBspTree->ConstructGeometry(leaf, geom);
4742
4743	const float lVol = geom.GetVolume();
4744	const float lArea = geom.GetArea();
4745
4746	//(*it)->SetVolume(vol);
4747	//(*it)->SetArea(area);
4748
4749	area += lArea;
4750	volume += lVol;
4751
4752	CreateMesh(*it);
4753	}
4754
4755	viewCell->SetVolume(volume);
4756	viewCell->SetArea(area);
4757	}
4758
4759
4760	void VspBspViewCellsManager::TestSubdivision()
4761	{
4762	ViewCellContainer leaves;
4763	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4764
4765	ViewCellContainer::const_iterator it, it_end = leaves.end();
4766
4767	const float vol = mViewSpaceBox.GetVolume();
4768	float subdivVol = 0;
4769	float newVol = 0;
4770
4771	for (it = leaves.begin(); it != it_end; ++ it)
4772	{
4773	BspNodeGeometry geom;
4774	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
4775	mVspBspTree->ConstructGeometry(leaf, geom);
4776
4777	const float lVol = geom.GetVolume();
4778
4779	newVol += lVol;
4780	subdivVol += (*it)->GetVolume();
4781
4782	float thres = 0.9f;
4783	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
4784	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4785	}
4786
4787	Debug << "exact volume: " << vol << endl;
4788	Debug << "subdivision volume: " << subdivVol << endl;
4789	Debug << "new volume: " << newVol << endl;
4790	}
4791
4792
4793	void VspBspViewCellsManager::PrepareLoadedViewCells()
4794	{
4795	// TODO: do I still need this here?
4796	if (0)
4797	mVspBspTree->RepairViewCellsLeafLists();
4798	}
4799
4800
4801
4802	/**************************************************************************/
4803	/* VspOspViewCellsManager implementation */
4804	/**************************************************************************/
4805
4806
4807	VspOspViewCellsManager::VspOspViewCellsManager(VspTree vspTree, OspTree ospTree):
4808	ViewCellsManager(), mVspTree(vspTree), mOspTree(ospTree)
4809	{
4810	mHierarchyManager = new HierarchyManager(vspTree, ospTree);
4811	Environment::GetSingleton()->GetIntValue("VspTree.Construction.samples", mInitialSamples);
4812	mVspTree->SetViewCellsManager(this);
4813	mVspTree->mViewCellsTree = mViewCellsTree;
4814	}
4815
4816
4817	VspOspViewCellsManager::~VspOspViewCellsManager()
4818	{
4819	DEL_PTR(mHierarchyManager);
4820	}
4821
4822
4823	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
4824	{
4825	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4826	}
4827
4828
4829	void VspOspViewCellsManager::CollectViewCells()
4830	{
4831	// view cells tree constructed
4832	if (!ViewCellsTreeConstructed())
4833	{
4834	mVspTree->CollectViewCells(mViewCells, false);
4835	}
4836	else
4837	{ // we can use the view cells tree hierarchy to get the right set
4838	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4839	}
4840	}
4841
4842
4843	bool VspOspViewCellsManager::ViewCellsConstructed() const
4844	{
4845	return mVspTree->GetRoot() != NULL;
4846	}
4847
4848
4849	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
4850	{
4851	return new VspViewCell(mesh);
4852	}
4853
4854
4855	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4856	const VssRayContainer &rays)
4857	{
4858	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4859
4860	// skip rest if view cells were already constructed
4861	if (ViewCellsConstructed())
4862	return 0;
4863
4864	int sampleContributions = 0;
4865
4866	VssRayContainer sampleRays;
4867
4868	int limit = min (mInitialSamples, (int)rays.size());
4869
4870	VssRayContainer constructionRays;
4871	VssRayContainer savedRays;
4872
4873	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4874	<< ", actual rays: " << (int)rays.size() << endl;
4875
4876	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4877
4878	Debug << "initial rays: " << (int)constructionRays.size() << endl;
4879	Debug << "saved rays: " << (int)savedRays.size() << endl;
4880
4881	long startTime;
4882
4883	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
4884
4885
4886	//-- stats
4887	Debug << mVspTree->GetStatistics() << endl;
4888
4889	ResetViewCells();
4890	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4891
4892
4893	startTime = GetTime();
4894
4895	cout << "Computing remaining ray contributions ... ";
4896
4897	// recast rest of rays
4898	if (SAMPLE_AFTER_SUBDIVISION)
4899	ComputeSampleContributions(savedRays, true, false);
4900
4901	cout << "finished" << endl;
4902
4903	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4904	<< " secs" << endl;
4905
4906	cout << "construction finished" << endl;
4907
4908	// real meshes are contructed at this stage
4909	if (0)
4910	{
4911	cout << "finalizing view cells ... ";
4912	FinalizeViewCells(true);
4913	cout << "finished" << endl;
4914	}
4915
4916	return sampleContributions;
4917	}
4918
4919
4920	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
4921	const VssRayContainer &rays)
4922	{
4923	if (!ViewCellsConstructed())
4924	{
4925	Debug << "postprocess error: no view cells constructed" << endl;
4926	return 0;
4927	}
4928
4929
4930	// take this step only if
4931	// view cells already constructed before post processing step
4932	// (e.g., because they were loaded)
4933	if (mViewCellsFinished)
4934	{
4935	FinalizeViewCells(true);
4936	EvaluateViewCellsStats();
4937
4938	return 0;
4939	}
4940
4941	// check if new view cells turned invalid
4942	int minPvs, maxPvs;
4943
4944	if (0)
4945	{
4946	minPvs = mMinPvsSize;
4947	maxPvs = mMaxPvsSize;
4948	}
4949	else
4950	{
4951	minPvs = mPruneEmptyViewCells ? 1 : 0;
4952	maxPvs = mMaxPvsSize;
4953	}
4954
4955	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4956	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4957
4958	SetValidity(minPvs, maxPvs);
4959
4960
4961	// area has to be recomputed
4962	mTotalAreaValid = false;
4963	VssRayContainer postProcessRays;
4964	GetRaySets(rays, mPostProcessSamples, postProcessRays);
4965
4966	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4967
4968
4969	// should maybe be done here to allow merge working with area or volume
4970	// and to correct the rendering statistics
4971	if (0) FinalizeViewCells(false);
4972
4973	// compute tree by merging the nodes of the spatial hierarchy
4974	ViewCell *root = ConstructSpatialMergeTree(mVspTree->GetRoot());
4975	mViewCellsTree->SetRoot(root);
4976
4977	// compute pvs
4978	ObjectPvs pvs;
4979	UpdatePvsForEvaluation(root, pvs);
4980
4981
4982	//-- render simulation after merge + refine
4983	cout << "\nevaluating bsp view cells render time before compress ... ";
4984	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4985	SimulationStatistics ss;
4986	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4987
4988
4989	cout << " finished" << endl;
4990	cout << ss << endl;
4991	Debug << ss << endl;
4992
4993
4994	//-- compression
4995	if (ViewCellsTreeConstructed() && mCompressViewCells)
4996	{
4997	int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
4998	Debug << "number of entries before compress: " << pvsEntries << endl;
4999
5000	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
5001
5002	pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
5003	Debug << "number of entries after compress: " << pvsEntries << endl;
5004	}
5005
5006	// compute final meshes and volume / area
5007	if (1) FinalizeViewCells(true);
5008
5009	// write view cells to disc
5010	if (mExportViewCells)
5011	{
5012	char filename[100];
5013	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
5014	ExportViewCells(filename, mExportPvs, objects);
5015	}
5016
5017
5018	return 0;
5019	}
5020
5021
5022	int VspOspViewCellsManager::GetType() const
5023	{
5024	return VSP_OSP;
5025	}
5026
5027
5028	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5029	{
5030	// terminate recursion
5031	if (root->IsLeaf())
5032	{
5033	VspLeaf leaf = dynamic_cast<VspLeaf >(root);
5034	leaf->GetViewCell()->SetMergeCost(0.0f);
5035	return leaf->GetViewCell();
5036	}
5037
5038
5039	VspInterior interior = dynamic_cast<VspInterior >(root);
5040	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5041
5042	// evaluate merge cost for priority traversal
5043	float mergeCost = 1.0f / (float)root->mTimeStamp;
5044	viewCellInterior->SetMergeCost(mergeCost);
5045
5046	float volume = 0;
5047
5048	VspNode *front = interior->GetFront();
5049	VspNode *back = interior->GetBack();
5050
5051
5052	ObjectPvs frontPvs, backPvs;
5053
5054	//-- recursivly compute child hierarchies
5055	ViewCell *backVc = ConstructSpatialMergeTree(back);
5056	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5057
5058
5059	viewCellInterior->SetupChildLink(backVc);
5060	viewCellInterior->SetupChildLink(frontVc);
5061
5062	volume += backVc->GetVolume();
5063	volume += frontVc->GetVolume();
5064
5065	viewCellInterior->SetVolume(volume);
5066
5067	return viewCellInterior;
5068	}
5069
5070
5071
5072	void VspOspViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
5073	{
5074	// terminate traversal
5075	if (root->IsLeaf())
5076	{
5077	pvs = root->GetPvs();
5078	SetScalarPvsSize(root, root->GetPvs().GetSize());
5079
5080	return;
5081	}
5082
5083	//-- interior node => propagate pvs up
5084	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
5085	interior->GetPvs().Clear();
5086	pvs.Clear();
5087	vector<ObjectPvs> pvsList;
5088
5089	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
5090
5091	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit)
5092	{
5093	ObjectPvs objPvs;
5094
5095	//-- recursivly compute child pvss
5096	UpdatePvsForEvaluation(*vit, objPvs);
5097
5098	// store pvs in vector
5099	pvsList.push_back(objPvs);
5100	}
5101
5102	#if 1
5103	Intersectable::NewMail();
5104
5105	//-- faster way of computing pvs:
5106	// construct merged pvs by adding
5107	// and only those of the next pvs which were not mailed.
5108	// note: sumpdf is not correct!!
5109	vector<ObjectPvs>::iterator oit = pvsList.begin();
5110
5111	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
5112	{
5113	ObjectPvsMap::iterator pit, pit_end = (*oit).mEntries.end();
5114
5115	for (pit = (*oit).mEntries.begin(); pit != pit_end; ++ pit)
5116	{
5117	Intersectable intersect = (pit).first;
5118
5119	if (!intersect->Mailed())
5120	{
5121	pvs.AddSample(intersect, (*pit).second.mSumPdf);
5122	intersect->Mail();
5123	}
5124	}
5125	}
5126
5127	// store pvs in this node
5128	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
5129	{
5130	interior->SetPvs(pvs);
5131	}
5132
5133	// set new pvs size
5134	SetScalarPvsSize(interior, pvs.GetSize());
5135
5136
5137	#else
5138
5139	// really merge cells: slow put sumpdf is correct
5140	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
5141	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
5142	#endif
5143	}
5144
5145
5146	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5147	{
5148	if (!ViewCellsConstructed())
5149	return ViewCellsManager::GetViewPoint(viewPoint);
5150
5151	// TODO: set reasonable limit
5152	const int limit = 20;
5153
5154	for (int i = 0; i < limit; ++ i)
5155	{
5156	viewPoint = mViewSpaceBox.GetRandomPoint();
5157
5158	if (mVspTree->ViewPointValid(viewPoint))
5159	{
5160	return true;
5161	}
5162	}
5163
5164	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5165	return false;
5166	}
5167
5168
5169	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5170	ViewCell *vc,
5171	const AxisAlignedPlane *clipPlane) const
5172	{
5173	ViewCellContainer leaves;
5174
5175	mViewCellsTree->CollectLeaves(vc, leaves);
5176	ViewCellContainer::const_iterator it, it_end = leaves.end();
5177
5178	Plane3 plane;
5179
5180	if (clipPlane)
5181	plane = clipPlane->GetPlane();
5182
5183	for (it = leaves.begin(); it != it_end; ++ it)
5184	{
5185	VspViewCell vspVc = dynamic_cast<VspViewCell >(*it);
5186	VspLeaf *l = vspVc->mLeaf;
5187
5188	const AxisAlignedBox3 box = mVspTree->GetBBox(vspVc->mLeaf);
5189
5190	if (clipPlane)
5191	{
5192	if (box.Side(plane) == -1)
5193	exporter->ExportBox(box);
5194	else if (box.Side(plane) == 0)
5195	{
5196	AxisAlignedBox3 fbox, bbox;
5197
5198	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5199
5200	exporter->ExportBox(bbox);
5201	}
5202	}
5203	else
5204	{
5205	exporter->ExportBox(box);
5206	}
5207	}
5208	}
5209
5210
5211	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5212	{
5213	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5214	// validy update in preprocessor for all managers)
5215	return ViewCellsManager::ViewPointValid(viewPoint);
5216
5217	// return mViewSpaceBox.IsInside(viewPoint) &&
5218	// mVspTree->ViewPointValid(viewPoint);
5219	}
5220
5221
5222	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5223	const VssRayContainer &sampleRays)
5224	{
5225	if (!ViewCellsConstructed())
5226	return;
5227
5228	VssRayContainer visRays;
5229	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5230
5231	//-- export final view cells
5232
5233	if (1)
5234	{
5235	// hack pvs
5236	const int savedColorCode = mColorCode;
5237	mColorCode = 0;
5238
5239	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5240
5241	if (exporter)
5242	{
5243	cout << "exporting view cells after post process ... ";
5244
5245	if (0)
5246	{
5247	// export view space box
5248	exporter->SetWireframe();
5249	exporter->ExportBox(mViewSpaceBox);
5250	exporter->SetFilled();
5251	}
5252
5253	if (mExportGeometry)
5254	{
5255	exporter->ExportGeometry(objects);
5256	}
5257
5258	// export rays
5259	if (0 && mExportRays)
5260	{
5261	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5262	}
5263
5264	//exporter->SetFilled();
5265
5266	// HACK: export without clip plane
5267	const bool b = mUseClipPlaneForViz;
5268	if (0)
5269	mUseClipPlaneForViz = false;
5270
5271	ExportViewCellsForViz(exporter);
5272
5273	mUseClipPlaneForViz = b;
5274	delete exporter;
5275
5276	cout << "finished" << endl;
5277	}
5278
5279	mColorCode = savedColorCode;
5280	}
5281
5282	//-- export single view cells
5283	ExportPvs(objects, visRays);
5284	}
5285
5286
5287	void VspOspViewCellsManager::ExportPvs(const ObjectContainer &objects,
5288	const VssRayContainer &rays)
5289	{
5290	int leafOut;
5291	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5292
5293	ViewCell::NewMail();
5294
5295	cout << "visualization using " << (int)rays.size() << " samples" << endl;
5296	Debug << "visualization using " << (int)rays.size() << " samples" << endl;
5297	Debug << "\nOutput view cells: " << endl;
5298
5299	const bool sortViewCells = true;
5300
5301	// sort view cells to visualize the largest view cells
5302	if (sortViewCells)
5303	{
5304	//stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
5305	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5306	}
5307
5308	int limit = min(leafOut, (int)mViewCells.size());
5309
5310	int raysOut = 0;
5311
5312	//-- some rays for output
5313	for (int i = 0; i < limit; ++ i)
5314	{
5315	cout << "creating output for view cell " << i << " ... ";
5316
5317	ViewCell *vc;
5318
5319	if (sortViewCells) // largest view cell pvs first
5320	vc = mViewCells[i];
5321	else // random view cell
5322	vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
5323
5324	ObjectPvs pvs;
5325	mViewCellsTree->GetPvs(vc, pvs);
5326
5327	//bspLeaves[j]->Mail();
5328	char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i);
5329	Exporter *exporter = Exporter::GetExporter(s);
5330
5331	Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
5332
5333	//-- export the sample rays
5334	if (1 \|\| mExportRays)
5335	{
5336	// output rays stored with the view cells during subdivision
5337	if (1)
5338	{
5339	VssRayContainer vcRays;
5340	VssRayContainer collectRays;
5341
5342	raysOut = min((int)rays.size(), 100);
5343
5344	// collect intial view cells
5345	ViewCellContainer leaves;
5346	mViewCellsTree->CollectLeaves(vc, leaves);
5347
5348	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5349
5350	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5351	{
5352	VspLeaf vcLeaf = dynamic_cast<VspViewCell >(*vit)->mLeaf;
5353
5354	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5355
5356	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5357	{
5358	collectRays.push_back(*rit);
5359	}
5360	}
5361
5362	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5363
5364	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5365	{
5366	float p = RandomValue(0.0f, (float)collectRays.size());
5367
5368	if (p < raysOut)
5369	vcRays.push_back(*rit);
5370	}
5371
5372	//-- export rays piercing this view cell
5373	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5374	}
5375
5376	// associate new rays with output view cell
5377	if (0)
5378	{
5379	VssRayContainer vcRays;
5380	raysOut = min((int)rays.size(), mVisualizationSamples);
5381
5382	// check whether we can add the current ray to the output rays
5383	for (int k = 0; k < raysOut; ++ k)
5384	{
5385	VssRay *ray = rays[k];
5386	for (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
5387	{
5388	ViewCell *rayvc = ray->mViewCells[j];
5389
5390	if (rayvc == vc)
5391	vcRays.push_back(ray);
5392	}
5393	}
5394
5395	//-- export rays piercing this view cell
5396	exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
5397	}
5398
5399	}
5400
5401
5402	//-- export view cell geometry
5403	exporter->SetWireframe();
5404
5405	Material m;//= RandomMaterial();
5406	m.mDiffuseColor = RgbColor(0, 1, 0);
5407	exporter->SetForcedMaterial(m);
5408
5409	ExportViewCellGeometry(exporter, vc);
5410
5411	exporter->SetFilled();
5412
5413
5414	if (1)
5415	{ //-- export pvs
5416	ObjectPvsMap::const_iterator oit,
5417	oit_end = pvs.mEntries.end();
5418
5419	Intersectable::NewMail();
5420
5421	vector<KdLeaf *> kdLeaves;
5422
5423	KdLeaf::NewMail();
5424
5425	m.mDiffuseColor = RgbColor(1, 0, 0);
5426	exporter->SetForcedMaterial(m);
5427
5428	// find kd nodes
5429	for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
5430	{
5431	// "original" pvs
5432	Intersectable obj = (oit).first;
5433
5434	if (1 && !obj->Mailed())
5435	{
5436	exporter->ExportIntersectable(obj);
5437	obj->Mail();
5438	}
5439
5440	// collect kd leaves
5441	set<KdLeaf *>::const_iterator kdit, kdit_end = obj->mKdLeaves.end();
5442
5443	for (kdit = obj->mKdLeaves.begin(); kdit != kdit_end; ++ kdit)
5444	{
5445	KdLeaf kdleaf = kdit;
5446
5447	if (!kdleaf->Mailed())
5448	{
5449	kdleaf->Mail();
5450	kdLeaves.push_back(kdleaf);
5451	}
5452	}
5453	}
5454
5455	m.mDiffuseColor = RgbColor(0, 0, 1);
5456	exporter->SetForcedMaterial(m);
5457
5458	// export kd node pvs
5459	Intersectable::NewMail();
5460
5461	vector<KdLeaf *>::const_iterator kdit, kdit_end = kdLeaves.end();
5462
5463	for (kdit = kdLeaves.begin(); kdit != kdit_end; ++ kdit)
5464	{
5465	KdLeaf kdleaf = kdit;
5466
5467	//-- export kd node
5468	/*exporter->SetWireframe();
5469	exporter->ExportBox(mKdTree->GetBox(kdleaf));
5470	exporter->SetFilled();*/
5471
5472	ObjectContainer::const_iterator oit, oit_end = kdleaf->mObjects.end();
5473
5474	for (oit = kdleaf->mObjects.begin(); oit != oit_end; ++ oit)
5475	{
5476	Intersectable obj = oit;
5477
5478	if (!obj->Mailed())
5479	{
5480	exporter->ExportIntersectable(obj);
5481	obj->Mail();
5482	}
5483	}
5484	}
5485	}
5486
5487	DEL_PTR(exporter);
5488	cout << "finished" << endl;
5489	}
5490
5491	Debug << endl;
5492	}
5493
5494
5495	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5496	ViewCellContainer &viewCells) const
5497	{
5498	return mVspTree->ComputeBoxIntersections(box, viewCells);
5499	}
5500
5501
5502	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
5503	const Vector3 &termination,
5504	ViewCellContainer &viewcells)
5505	{
5506	return mVspTree->CastLineSegment(origin, termination, viewcells);
5507	}
5508
5509
5510	bool VspOspViewCellsManager::ExportViewCells(const string filename,
5511	const bool exportPvs,
5512	const ObjectContainer &objects)
5513	{
5514	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
5515	return false;
5516
5517	cout << "exporting view cells to xml ... ";
5518
5519	#if ZIPPED_VIEWCELLS
5520	ogzstream stream(filename.c_str());
5521	#else
5522	std::ofstream stream(filename.c_str());
5523	#endif
5524
5525	// for output we need unique ids for each view cell
5526	CreateUniqueViewCellIds();
5527
5528	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
5529	stream << "<VisibilitySolution>" << endl;
5530
5531	//-- the view space bounding box
5532	stream << "<ViewSpaceBox"
5533	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
5534	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
5535
5536
5537	//-- export bounding boxes
5538	stream << "<BoundingBoxes>" << endl;
5539
5540	ObjectContainer::const_iterator oit, oit_end = objects.end();
5541
5542	for (oit = objects.begin(); oit != oit_end; ++ oit)
5543	{
5544	MeshInstance mi = dynamic_cast<MeshInstance >(*oit);
5545	const AxisAlignedBox3 box = mi->GetBox();
5546
5547	//-- the bounding boxes
5548	stream << "<BoundingBox" << " id=\"" << mi->GetId() << "\""
5549	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
5550	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
5551	}
5552
5553	stream << "</BoundingBoxes>" << endl;
5554
5555
5556	//-- export the view cells and the pvs
5557	stream << "<HierarchyType name=\"vspTree\" />" << endl;
5558
5559	const int numViewCells = mCurrentViewCellsStats.viewCells;
5560
5561	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
5562
5563	mViewCellsTree->Export(stream, exportPvs);
5564
5565	stream << "</ViewCells>" << endl;
5566
5567
5568	//-- export the spatial hierarchy
5569
5570	// the type of the view cells hierarchy
5571	stream << "<Hierarchy>" << endl;
5572	mVspTree->Export(stream);
5573	stream << endl << "</Hierarchy>" << endl;
5574
5575	stream << "</VisibilitySolution>" << endl;
5576
5577
5578	stream.close();
5579	cout << "finished" << endl;
5580
5581	return true;
5582	}
5583
5584
5585
5586	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
5587	const bool active) const
5588	{
5589	if (!ViewCellsConstructed())
5590	return NULL;
5591
5592	if (!mViewSpaceBox.IsInside(point))
5593	return NULL;
5594
5595	return mVspTree->GetViewCell(point, active);
5596	}
5597
5598
5599	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
5600	{
5601	// matt: TODO
5602	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5603
5604	ViewCellContainer leaves;
5605	mViewCellsTree->CollectLeaves(vc, leaves);
5606
5607	ViewCellContainer::const_iterator it, it_end = leaves.end();
5608
5609	for (it = leaves.begin(); it != it_end; ++ it)
5610	{
5611	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaf;
5612	const AxisAlignedBox3 box = mVspTree->GetBBox(leaf);
5613
5614	IncludeBoxInMesh(box, *mesh);
5615	}
5616
5617	vc->SetMesh(mesh);
5618	}
5619
5620
5621	int VspOspViewCellsManager::CastBeam(Beam &beam)
5622	{
5623	// matt: TODO
5624	return 0;
5625	}
5626
5627
5628	void VspOspViewCellsManager::Finalize(ViewCell *viewCell,
5629	const bool createMesh)
5630	{
5631	float area = 0;
5632	float volume = 0;
5633
5634	ViewCellContainer leaves;
5635	mViewCellsTree->CollectLeaves(viewCell, leaves);
5636
5637	ViewCellContainer::const_iterator it, it_end = leaves.end();
5638
5639	for (it = leaves.begin(); it != it_end; ++ it)
5640	{
5641	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaf;
5642
5643	const AxisAlignedBox3 box = mVspTree->GetBBox(leaf);
5644
5645	const float lVol = box.GetVolume();
5646	const float lArea = box.SurfaceArea();
5647
5648	//(*it)->SetVolume(vol);
5649	//(*it)->SetArea(area);
5650
5651	area += lArea;
5652	volume += lVol;
5653
5654	CreateMesh(*it);
5655	}
5656
5657	viewCell->SetVolume(volume);
5658	viewCell->SetArea(area);
5659	}
5660
5661
5662	void VspOspViewCellsManager::PrepareLoadedViewCells()
5663	{
5664	// TODO
5665	}
5666
5667
5668	//////////////////////////////////
5669	/ViewCellsManager ViewCellsManagerFactory::Create(const string mName)
5670	{
5671	//TODO
5672	return NULL;// new VspBspViewCellsManager();
5673	}*/
5674
5675
5676	}

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

Download in other formats: