Context Navigation

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

Revision 727, 101.4 KB checked in by mattausch, 19 years ago (diff)
added view cell description bsp tree

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

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

Download in other formats: