Context Navigation

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

Revision 1006, 116.7 KB checked in by mattausch, 18 years ago (diff)
started viewspace-objectspace subdivision removed memory leaks

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

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

Download in other formats: