Context Navigation

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

Revision 752, 113.3 KB checked in by mattausch, 19 years ago (diff)
after rendering workshop submissioin x3dparser can use def - use constructs implemented improved evaluation (samples are only stored in leaves, only propagate pvs size)

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

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

Download in other formats: