Context Navigation

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

Revision 2705, 180.4 KB checked in by mattausch, 16 years ago (diff)
enabled view cell visualization

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

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

Download in other formats: