Context Navigation

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

Revision 859, 120.4 KB checked in by bittner, 18 years ago (diff)
apply filter routine for working modules

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

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

Download in other formats: