Context Navigation

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

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

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

Download in other formats: