Context Navigation

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

Revision 840, 116.9 KB checked in by mattausch, 18 years ago (diff)
implementing bounding box hack

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

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

Download in other formats: