Context Navigation

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

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

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

Download in other formats: