Context Navigation

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

Revision 734, 106.9 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: