Context Navigation

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

Revision 944, 123.3 KB checked in by mattausch, 19 years ago (diff)

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

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

Download in other formats: