Context Navigation

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

Revision 931, 122.9 KB checked in by mattausch, 18 years ago (diff)
added bounding boxes to xml description

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

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

Download in other formats: