Context Navigation

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

Revision 871, 120.6 KB checked in by bittner, 18 years ago (diff)
RenderSampler?

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

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

Download in other formats: