Context Navigation

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

Revision 729, 104.6 KB checked in by mattausch, 18 years ago (diff)
added cost flexible render cost measurements

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

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

Download in other formats: