Context Navigation

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

Revision 1201, 142.6 KB checked in by mattausch, 18 years ago (diff)
added loader for osp trees

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

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

Download in other formats: