Context Navigation

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

Revision 1189, 141.9 KB checked in by mattausch, 18 years ago (diff)
changed osp partition to something taking mult references into account

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

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

Download in other formats: