Context Navigation

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

Revision 1785, 154.5 KB checked in by bittner, 18 years ago (diff)
merge, filter update, renderebuffer made functional

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

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

Download in other formats: