Context Navigation

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

Revision 1151, 138.6 KB checked in by mattausch, 18 years ago (diff)
worded on dll loading

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

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

Download in other formats: