Context Navigation

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

Revision 884, 121.2 KB checked in by bittner, 18 years ago (diff)
Spatial visibility filter

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

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

Download in other formats: