Context Navigation

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

Revision 1178, 141.9 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: