Context Navigation

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

Revision 1184, 142.0 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: