Context Navigation

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

Revision 938, 123.1 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: