Context Navigation

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

Revision 1784, 154.3 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: