Context Navigation

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

Revision 844, 117.0 KB checked in by mattausch, 18 years ago (diff)
adding functionality for bounding box hacks

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

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

Download in other formats: