Context Navigation

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

Revision 1129, 139.0 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: