Context Navigation

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

Revision 1233, 143.0 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: