Context Navigation

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

Revision 1221, 142.9 KB checked in by mattausch, 18 years ago (diff)
added intel ray tracing

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

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

Download in other formats: