Context Navigation

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

Revision 904, 121.7 KB checked in by bittner, 18 years ago (diff)
visibility filter updates

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

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

Download in other formats: