Context Navigation

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

Revision 2702, 180.0 KB checked in by mattausch, 16 years ago (diff)
implemented dynamic object placement / removal

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(const int tri, const 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	KdIntersectable kdObj = static_cast<KdIntersectable >(obj);
2377
2378	const AxisAlignedBox3 box = kdObj->GetBox();
2379	const float dist = Distance(vc->GetBox().Center(), box.Center());
2380
2381	float f;
2382
2383	const float radius = box.Radius();
2384	const float fullRadius = max(0.2f * mViewSpaceBox.Radius(), radius);
2385
2386	const float minVal = 0.01f;
2387	const float maxVal = 1.0f;
2388
2389	if (dist <= radius)
2390	f = maxVal;
2391	else if (dist >= fullRadius)
2392	f = minVal;
2393	else // linear blending
2394	{
2395	f = minVal * (dist - radius) / (fullRadius - radius) +
2396	maxVal * (fullRadius - radius - dist) / (fullRadius - radius);
2397	}
2398
2399	//cout << "x " << radius << " " << dist << " " << fullRadius << " " << f << " " << f * f << endl;
2400	//const int numTriangles = kdObj->ComputeNumTriangles();
2401
2402	vc->GetPvs().mStats.mDistanceWeightedTriangles += f * numTriangles;
2403	vc->GetPvs().mStats.mDistanceWeightedPvs += f ;
2404	vc->GetPvs().mStats.mWeightedTriangles += numTriangles;
2405	#endif
2406	}
2407
2408
2409	bool ViewCellsManager::ComputeViewCellContribution(ViewCell *viewCell,
2410	VssRay &ray,
2411	Intersectable *obj,
2412	const Vector3 &pt,
2413	bool addSamplesToPvs)
2414	{
2415	// check if we are outside of view space
2416	// $$JB tmp commented to speedup up computations
2417	#if 0
2418	if (!obj \|\| !viewCell->GetValid())
2419	return false;
2420	#endif
2421
2422	// if ray not outside of view space
2423	float relContribution = 0.0f;
2424	float absContribution = 0.0f;
2425	bool hasAbsContribution;
2426
2427	// todo: probably not correct for kd node pvs
2428	if (addSamplesToPvs)
2429	{
2430	hasAbsContribution = viewCell->GetPvs().AddSampleDirtyCheck(obj, ray.mPdf);
2431	//hasAbsContribution = viewCell->GetPvs().AddSample(obj,ray.mPdf);
2432
2433	//if (hasAbsContribution) UpdateStatsForViewCell(viewCell, obj);
2434
2435	}
2436	else
2437	{
2438	hasAbsContribution =
2439	viewCell->GetPvs().GetSampleContribution(obj, ray.mPdf, relContribution);
2440	}
2441
2442	// $$ clear the relative contribution as it is currently not correct anyway
2443	// relContribution = 0.0f;
2444
2445	if (hasAbsContribution)
2446	{
2447	++ ray.mPvsContribution;
2448	absContribution = relContribution = 1.0f;
2449
2450	if (viewCell->GetPvs().RequiresResort())
2451	viewCell->GetPvs().SimpleSort();
2452
2453	#if CONTRIBUTION_RELATIVE_TO_PVS_SIZE
2454	relContribution /= viewcell->GetPvs().GetSize();
2455	#endif
2456
2457	#if DIST_WEIGHTED_CONTRIBUTION
2458	// recalculate the contribution - weight the 1.0f contribution by the sqr distance to the
2459	// object-> a new contribution in the proximity of the viewcell has a larger weight!
2460	relContribution /=
2461	SqrDistance(GetViewCellBox(viewcell).Center(), ray.mTermination);
2462
2463	#endif
2464	}
2465
2466	#if SUM_RAY_CONTRIBUTIONS \|\| AVG_RAY_CONTRIBUTIONS
2467	ray.mRelativePvsContribution += relContribution;
2468	#else
2469	// recalculate relative contribution - use max of Rel Contribution
2470	if (ray.mRelativePvsContribution < relContribution)
2471	ray.mRelativePvsContribution = relContribution;
2472	#endif
2473
2474	return hasAbsContribution;
2475	}
2476
2477
2478	int ViewCellsManager::GetNumViewCells() const
2479	{
2480	return (int)mViewCells.size();
2481	}
2482
2483
2484	void
2485	ViewCellsManager::DeterminePvsObjects(VssRayContainer &rays,
2486	bool useHitObjects)
2487	{
2488	if (!useHitObjects)
2489	{
2490	// store higher order object (e.g., bvh node) instead of object itself
2491	VssRayContainer::const_iterator it, it_end = rays.end();
2492
2493	for (it = rays.begin(); it != it_end; ++ it)
2494	{
2495	VssRay vssRay = it;
2496
2497	// set only the termination object
2498	vssRay->mTerminationObject = GetIntersectable(*vssRay, true);
2499
2500	if (vssRay->mTerminationObject->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
2501	cout << "r";
2502
2503	#if 0
2504	if (vssRay->mTerminationObject == NULL)
2505	cerr<<"Error in DeterminePvsObjects - termination object maps to NULL!"<<endl;
2506	#endif
2507	}
2508	}
2509	}
2510
2511
2512	float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2513	const bool addRays,
2514	ViewCell *currentViewCell,
2515	const bool useHitObjects)
2516	{
2517	ray.mPvsContribution = 0;
2518	ray.mRelativePvsContribution = 0.0f;
2519
2520	if (!ray.mTerminationObject)
2521	return 0.0f;
2522
2523	// optain pvs entry (can be different from hit object)
2524	Intersectable *terminationObj;
2525
2526	terminationObj = ray.mTerminationObject;
2527	//cout << "rayd: " << ray.GetDir() << " ";
2528	ComputeViewCellContribution(currentViewCell,
2529	ray,
2530	terminationObj,
2531	ray.mTermination,
2532	addRays);
2533
2534	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2535	float c = 0.0f;
2536	if (terminationObj)
2537	c = ray.Length();
2538
2539	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2540	return c;
2541	#else
2542	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2543	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2544	#endif
2545	}
2546
2547
2548	float
2549	ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2550	bool addRays,
2551	bool storeViewCells,
2552	bool useHitObjects)
2553	{
2554	ray.mPvsContribution = 0;
2555	ray.mRelativePvsContribution = 0.0f;
2556
2557	++ mSamplesStat.mRays;
2558
2559	#if MYSTATS
2560	mSamplesStat.mRayLengths += ray.Length();
2561	#endif
2562	if (!ray.mTerminationObject)
2563	return 0.0f;
2564
2565	static Ray hray;
2566	hray.Init(ray);
2567
2568	float tmin = 0, tmax = 1.0;
2569
2570	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2571	{
2572	// cerr<<"ray outside view space box\n";
2573	return 0;
2574	}
2575
2576	Vector3 origin = hray.Extrap(tmin);
2577	Vector3 termination = hray.Extrap(tmax);
2578
2579	ViewCell::NewMail();
2580
2581	static ViewCellContainer viewCells;
2582	static VssRay *lastVssRay = NULL;
2583
2584	// check if last ray was not same ray with reverse direction
2585	if (1)
2586	// tmp matt: don't use when origin objects are not accounted for, currently the second ray is lost!!
2587	// $$JB: reenabled again - should use the same viewcells for the next ray ray if
2588	// it goes in the oposite direction
2589	// if (!lastVssRay \|\|
2590	// !(ray.mOrigin == lastVssRay->mTermination) \|\|
2591	// !(ray.mTermination == lastVssRay->mOrigin))
2592	{
2593	#ifdef USE_PERFTIMER
2594	viewCellCastTimer.Entry();
2595	#endif
2596	viewCells.clear();
2597
2598	// traverse the view space subdivision
2599	CastLineSegment(origin, termination, viewCells);
2600	lastVssRay = &ray;
2601	#ifdef USE_PERFTIMER
2602	viewCellCastTimer.Exit();
2603	#endif
2604	}
2605	mSamplesStat.mViewCells += (int)viewCells.size();
2606
2607	if (storeViewCells)
2608	{
2609	// cerr << "Store viewcells should not be used in the test!" << endl;
2610	// copy viewcells memory efficiently
2611	#if VSS_STORE_VIEWCELLS
2612	ray.mViewCells.reserve(viewCells.size());
2613	ray.mViewCells = viewCells;
2614	#else
2615	cerr << "Vss store viewcells not supported." << endl;
2616	exit(1);
2617	#endif
2618	}
2619
2620	Intersectable *terminationObj;
2621
2622	#ifdef USE_PERFTIMER
2623	// objTimer.Entry();
2624	#endif
2625	// obtain pvs entry (can be different from hit object)
2626	terminationObj = ray.mTerminationObject;
2627
2628	#ifdef USE_PERFTIMER
2629	// objTimer.Exit();
2630	pvsTimer.Entry();
2631	#endif
2632	//if (terminationObj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
2633	// cout << "found tmi: " << Intersectable::GetTypeName(terminationObj) << " " << viewCells.size() << endl;
2634	bool contri = false;
2635	ViewCellContainer::const_iterator it = viewCells.begin();
2636	//cout << "rayd: " << ray.GetDir() << " ";
2637	for (; it != viewCells.end(); ++ it)
2638	{
2639	if (ComputeViewCellContribution(*it,
2640	ray,
2641	terminationObj,
2642	ray.mTermination,
2643	addRays))
2644	{
2645	contri = true;
2646	}
2647
2648	(*it)->IncNumPiercingRays();
2649
2650	}
2651
2652	#if MYSTATS
2653	if (contri)
2654	{
2655	if (rand() < (RAND_MAX / 10))
2656	// cout << "rayd: " /<< ray.GetOrigin() << " " << ray.GetTermination() << " "/ << Normalize(ray.GetDir()) << " " << endl;
2657	mVizBuffer.AddRay(&ray);
2658	}
2659	#endif
2660	#ifdef USE_PERFTIMER
2661	pvsTimer.Exit();
2662	#endif
2663
2664	mSamplesStat.mPvsContributions += ray.mPvsContribution;
2665	if (ray.mPvsContribution)
2666	++ mSamplesStat.mContributingRays;
2667
2668	#if AVG_RAY_CONTRIBUTIONS
2669	ray.mRelativePvsContribution /= (float)viewCells.size();
2670	#endif
2671
2672	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2673	float c = 0.0f;
2674	if (terminationObj)
2675	c = ray.Length();
2676	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2677	return c;
2678	#else
2679	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2680	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2681	#endif
2682	}
2683
2684
2685	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
2686	const int maxSize,
2687	VssRayContainer &usedRays,
2688	VssRayContainer *savedRays) const
2689	{
2690	const int limit = min(maxSize, (int)sourceRays.size());
2691	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
2692
2693	VssRayContainer::const_iterator it, it_end = sourceRays.end();
2694	for (it = sourceRays.begin(); it != it_end; ++ it)
2695	{
2696	if (Random(1.0f) < prop)
2697	usedRays.push_back(*it);
2698	else if (savedRays)
2699	savedRays->push_back(*it);
2700	}
2701	}
2702
2703
2704	float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
2705	{
2706	return (float)mViewCellsTree->GetTrianglesInPvs(viewCell);
2707	}
2708
2709
2710	float ViewCellsManager::GetAccVcArea()
2711	{
2712	// if already computed
2713	if (mTotalAreaValid)
2714	{
2715	return mTotalArea;
2716	}
2717
2718	mTotalArea = 0;
2719	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2720
2721	for (it = mViewCells.begin(); it != it_end; ++ it)
2722	{
2723	//Debug << "area: " << GetArea(*it);
2724	mTotalArea += GetArea(*it);
2725	}
2726
2727	mTotalAreaValid = true;
2728
2729	return mTotalArea;
2730	}
2731
2732
2733	void ViewCellsManager::PrintStatistics(ostream &s) const
2734	{
2735	s << mCurrentViewCellsStats << endl;
2736	}
2737
2738
2739	void ViewCellsManager::CreateUniqueViewCellIds()
2740	{
2741	if (ViewCellsTreeConstructed())
2742	{
2743	mViewCellsTree->CreateUniqueViewCellsIds();
2744	}
2745	else // no view cells tree, handle view cells "myself"
2746	{
2747	int i = 0;
2748	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2749	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2750	{
2751	if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2752	{
2753	mViewCells[i]->SetId(i ++);
2754	}
2755	}
2756	}
2757	}
2758
2759
2760	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2761	const AxisAlignedBox3 *sceneBox,
2762	const bool colorCode,
2763	const AxisAlignedPlane *clipPlane
2764	) const
2765	{
2766	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2767
2768	for (it = mViewCells.begin(); it != it_end; ++ it)
2769	{
2770	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
2771	{
2772	ExportColor(exporter, *it, colorCode);
2773	ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2774	}
2775	}
2776	}
2777
2778
2779	void ViewCellsManager::CreateViewCellMeshes()
2780	{
2781	// convert to meshes
2782	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2783
2784	for (it = mViewCells.begin(); it != it_end; ++ it)
2785	{
2786	if (!(*it)->GetMesh())
2787	{
2788	CreateMesh(*it);
2789	}
2790	}
2791	}
2792
2793
2794	bool ViewCellsManager::ExportViewCells(const string filename,
2795	const bool exportPvs,
2796	const ObjectContainer &objects)
2797	{
2798	return false;
2799	}
2800
2801
2802	void ViewCellsManager::CollectViewCells(const int n)
2803	{
2804	mNumActiveViewCells = n;
2805	mViewCells.clear();
2806	// implemented in subclasses
2807	CollectViewCells();
2808	}
2809
2810
2811	void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
2812	{
2813	ViewCellContainer leaves;
2814	// sets the pointers to the currently active view cells
2815	mViewCellsTree->CollectLeaves(vc, leaves);
2816
2817	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2818	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2819	{
2820	static_cast<ViewCellLeaf >(lit)->SetActiveViewCell(vc);
2821	}
2822	}
2823
2824
2825	void ViewCellsManager::SetViewCellsActive()
2826	{
2827	// collect leaf view cells and set the pointers to
2828	// the currently active view cells
2829	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2830
2831	for (it = mViewCells.begin(); it != it_end; ++ it)
2832	{
2833	SetViewCellActive(*it);
2834	}
2835	}
2836
2837
2838	int ViewCellsManager::GetMaxFilterSize() const
2839	{
2840	return mMaxFilterSize;
2841	}
2842
2843
2844	static const bool USE_ASCII = true;
2845
2846
2847	bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2848	const ObjectContainer &objects) const
2849	{
2850	ObjectContainer::const_iterator it, it_end = objects.end();
2851
2852	if (USE_ASCII)
2853	{
2854	ofstream boxesOut(filename.c_str());
2855	if (!boxesOut.is_open())
2856	return false;
2857
2858	for (it = objects.begin(); it != it_end; ++ it)
2859	{
2860	MeshInstance mi = static_cast<MeshInstance >(*it);
2861	const AxisAlignedBox3 box = mi->GetBox();
2862
2863	boxesOut << mi->GetId() << " "
2864	<< box.Min().x << " "
2865	<< box.Min().y << " "
2866	<< box.Min().z << " "
2867	<< box.Max().x << " "
2868	<< box.Max().y << " "
2869	<< box.Max().z << endl;
2870	}
2871
2872	boxesOut.close();
2873	}
2874	else
2875	{
2876	ofstream boxesOut(filename.c_str(), ios::binary);
2877
2878	if (!boxesOut.is_open())
2879	return false;
2880
2881	for (it = objects.begin(); it != it_end; ++ it)
2882	{
2883	MeshInstance mi = static_cast<MeshInstance >(*it);
2884	const AxisAlignedBox3 box = mi->GetBox();
2885
2886	Vector3 bmin = box.Min();
2887	Vector3 bmax = box.Max();
2888
2889	int id = mi->GetId();
2890
2891	boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2892	boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2893	boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2894	}
2895
2896	boxesOut.close();
2897	}
2898
2899	return true;
2900	}
2901
2902
2903	bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2904	IndexedBoundingBoxContainer &boxes) const
2905	{
2906	Vector3 bmin, bmax;
2907	int id;
2908
2909	if (USE_ASCII)
2910	{
2911	ifstream boxesIn(filename.c_str());
2912
2913	if (!boxesIn.is_open())
2914	{
2915	cout << "failed to open file " << filename << endl;
2916	return false;
2917	}
2918
2919	string buf;
2920	while (!(getline(boxesIn, buf)).eof())
2921	{
2922	sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2923	&id, &bmin.x, &bmin.y, &bmin.z,
2924	&bmax.x, &bmax.y, &bmax.z);
2925
2926	AxisAlignedBox3 box(bmin, bmax);
2927	// MeshInstance *mi = new MeshInstance();
2928	// HACK: set bounding box to new box
2929	//mi->mBox = box;
2930
2931	boxes.push_back(IndexedBoundingBox(id, box));
2932	}
2933
2934	boxesIn.close();
2935	}
2936	else
2937	{
2938	ifstream boxesIn(filename.c_str(), ios::binary);
2939
2940	if (!boxesIn.is_open())
2941	return false;
2942
2943	while (1)
2944	{
2945	boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2946	boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2947	boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2948
2949	if (boxesIn.eof())
2950	break;
2951
2952	AxisAlignedBox3 box(bmin, bmax);
2953	MeshInstance *mi = new MeshInstance(NULL);
2954
2955	boxes.push_back(IndexedBoundingBox(id, box));
2956	}
2957
2958	boxesIn.close();
2959	}
2960
2961	return true;
2962	}
2963
2964
2965	float ViewCellsManager::GetFilterWidth()
2966	{
2967	return mFilterWidth;
2968	}
2969
2970
2971	float ViewCellsManager::GetAbsFilterWidth()
2972	{
2973	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2974	}
2975
2976
2977	void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2978	const float pvsCost,
2979	const int entriesInPvs) const
2980	{
2981	vc->mPvsCost = pvsCost;
2982	vc->mEntriesInPvs = entriesInPvs;
2983
2984	vc->mPvsSizeValid = true;
2985	}
2986
2987
2988	void ViewCellsManager::UpdateScalarPvsCost(ViewCell *vc, const float pvsCost) const
2989	{
2990	vc->mPvsCost = pvsCost;
2991	}
2992
2993
2994	void
2995	ViewCellsManager::ApplyFilter(ViewCell *viewCell,
2996	KdTree *kdTree,
2997	const float viewSpaceFilterSize,
2998	const float spatialFilterSize,
2999	ObjectPvs &pvs
3000	)
3001	{
3002	// extend the pvs of the viewcell by pvs of its neighbors
3003	// and apply spatial filter by including all neighbors of the objects
3004	// in the pvs
3005
3006	// get all viewcells intersecting the viewSpaceFilterBox
3007	// and compute the pvs union
3008
3009	//Vector3 center = viewCell->GetBox().Center();
3010	// Vector3 center = m->mBox.Center();
3011
3012	// AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
3013	// center + Vector3(viewSpaceFilterSize/2));
3014	if (!ViewCellsConstructed())
3015	return;
3016
3017	if (viewSpaceFilterSize >= 0.0f)
3018	{
3019	const bool usePrVS = false;
3020
3021	if (!usePrVS)
3022	{
3023	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3024	box.Enlarge(Vector3(viewSpaceFilterSize/2));
3025
3026	ViewCellContainer viewCells;
3027	ComputeBoxIntersections(box, viewCells);
3028
3029	// cout<<"box="<<box<<endl;
3030	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3031
3032	for (; it != it_end; ++ it)
3033	{
3034	ObjectPvs interPvs;
3035	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3036	ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
3037
3038	pvs = interPvs;
3039	}
3040	}
3041	else
3042	{
3043	PrVs prvs;
3044	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3045
3046	// mViewCellsManager->SetMaxFilterSize(1);
3047	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
3048	pvs = prvs.mViewCell->GetPvs();
3049	DeleteLocalMergeTree(prvs.mViewCell);
3050	}
3051	}
3052	else
3053	{
3054	pvs = viewCell->GetPvs();
3055	}
3056
3057	if (spatialFilterSize >=0.0f)
3058	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
3059
3060	}
3061
3062
3063
3064	void
3065	ViewCellsManager::ApplyFilter(KdTree *kdTree,
3066	const float relViewSpaceFilterSize,
3067	const float relSpatialFilterSize
3068	)
3069	{
3070
3071	if (!ViewCellsConstructed())
3072	return;
3073
3074	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3075
3076	ObjectPvs *newPvs;
3077	newPvs = new ObjectPvs[mViewCells.size()];
3078
3079	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
3080	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
3081
3082	int i;
3083	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3084	ApplyFilter(*it,
3085	kdTree,
3086	viewSpaceFilterSize,
3087	spatialFilterSize,
3088	newPvs[i]
3089	);
3090	}
3091
3092	// now replace all pvss
3093	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3094
3095	ObjectPvs &pvs = (*it)->GetPvs();
3096	pvs.Clear();
3097	pvs = newPvs[i];
3098	newPvs[i].Clear();
3099	}
3100
3101	delete [] newPvs;
3102	}
3103
3104
3105	void
3106	ViewCellsManager::ApplySpatialFilter(
3107	KdTree *kdTree,
3108	const float spatialFilterSize,
3109	ObjectPvs &pvs
3110	)
3111	{
3112	// now compute a new Pvs by including also objects intersecting the
3113	// extended boxes of visible objects
3114	Intersectable::NewMail();
3115
3116	ObjectPvsIterator pit = pvs.GetIterator();
3117
3118	while (pit.HasMoreEntries())
3119	pit.Next()->Mail();
3120
3121	ObjectPvs nPvs;
3122	int nPvsSize = 0;
3123
3124	ObjectPvsIterator pit2 = pvs.GetIterator();
3125
3126	while (pit2.HasMoreEntries())
3127	{
3128	// now go through the pvs again
3129	Intersectable *object = pit2.Next();
3130
3131	// Vector3 center = object->GetBox().Center();
3132	// AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
3133	// center + Vector3(spatialFilterSize/2));
3134
3135	AxisAlignedBox3 box = object->GetBox();
3136	box.Enlarge(Vector3(spatialFilterSize/2));
3137
3138	ObjectContainer objects;
3139
3140	// $$ warning collect objects takes only unmailed ones!
3141	kdTree->CollectObjects(box, objects);
3142	// cout<<"collected objects="<<objects.size()<<endl;
3143	ObjectContainer::const_iterator noi = objects.begin();
3144	for (; noi != objects.end(); ++ noi)
3145	{
3146	Intersectable o = noi;
3147	cout<<"w";
3148	// $$ JB warning: pdfs are not correct at this point!
3149	nPvs.AddSample(o, Limits::Small);
3150	nPvsSize ++;
3151	}
3152	}
3153
3154	// cout<<"nPvs size = "<<nPvsSize<<endl;
3155	pvs.MergeInPlace(nPvs);
3156	}
3157
3158
3159	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3160	const ViewCellContainer &viewCells) const
3161	{
3162	MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
3163	}
3164
3165
3166	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3167	const ViewCellContainer &viewCells,
3168	int leftIdx,
3169	int rightIdx) const
3170	{
3171	if (leftIdx == rightIdx)
3172	{
3173	pvs = viewCells[leftIdx]->GetPvs();
3174	}
3175	else
3176	{
3177	const int midSplit = (leftIdx + rightIdx) / 2;
3178
3179	ObjectPvs leftPvs, rightPvs;
3180	MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
3181	MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);
3182
3183	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
3184	}
3185	}
3186
3187
3188	PvsFilterStatistics
3189	ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
3190	const bool useViewSpaceFilter,
3191	const float filterSize,
3192	ObjectPvs &pvs,
3193	vector<AxisAlignedBox3> *filteredBoxes,
3194	const bool onlyNewObjects
3195	)
3196	{
3197
3198
3199	pvs.Reserve(viewCell->GetFilteredPvsSize());
3200
3201	PvsFilterStatistics stats;
3202
3203	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
3204	const Vector3 center = vbox.Center();
3205
3206	// copy the PVS
3207	if (!mUseKdPvs)
3208	Intersectable::NewMail();
3209	else
3210	KdNode::NewMail();
3211
3212	ObjectPvs basePvs = viewCell->GetPvs();
3213	ObjectPvsIterator pit = basePvs.GetIterator();
3214
3215	if (!mUseKdPvs)
3216	{
3217	// first mark all objects from this pvs
3218	while (pit.HasMoreEntries())
3219	pit.Next()->Mail();
3220	}
3221
3222	int pvsSize = 0;
3223	int nPvsSize = 0;
3224
3225	//Debug<<"f #s="<<samples<<" pvs size = "<<basePvs.GetSize();
3226	// cout<<"Filter size = "<<filterSize<<endl;
3227	// cout<<"vbox = "<<vbox<<endl;
3228	// cout<<"center = "<<center<<endl;
3229
3230
3231	// Minimal number of local samples to take into account
3232	// the local sampling density.
3233	// The size of the filter is a minimum of the conservative
3234	// local sampling density estimate (#rays intersecting teh viewcell and
3235	// the object)
3236	// and gobal estimate for the view cell
3237	// (total #rays intersecting the viewcell)
3238	const int minLocalSamples = 2;
3239	const float viewCellRadius = 0.5f * Magnitude(vbox.Diagonal());
3240
3241	float samples = (float)basePvs.GetSamples();
3242
3243
3244	//////////
3245	//-- now compute the filter box around the current viewCell
3246
3247	if (useViewSpaceFilter)
3248	{
3249	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
3250	float radius = viewCellRadius / 100.0f;
3251	vbox.Enlarge(radius);
3252	cout<<"vbox = "<<vbox<<endl;
3253
3254	ViewCellContainer viewCells;
3255	ComputeBoxIntersections(vbox, viewCells);
3256
3257	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3258
3259	for (int i = 0; it != it_end; ++ it, ++ i)
3260	{
3261	if ((*it) != viewCell)
3262	{
3263	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3264	basePvs.MergeInPlace((*it)->GetPvs());
3265	}
3266
3267	// update samples and globalC
3268	samples = (float)pvs.GetSamples();
3269	// cout<<"neighboring viewcells = "<<i-1<<endl;
3270	// cout<<"Samples' = "<<samples<<endl;
3271	}
3272	}
3273
3274	// Minimal number of samples so that filtering takes place
3275	const float MIN_SAMPLES = 50;
3276
3277	if (samples > MIN_SAMPLES)
3278	{
3279	float globalC = 2.0f * filterSize / sqrt(samples);
3280
3281	ObjectContainer objects;
3282	PvsData pvsData;
3283
3284	pit = basePvs.GetIterator();
3285
3286	if (onlyNewObjects) {
3287	while (pit.HasMoreEntries()) {
3288	// mail all objects from the original not to include them in the
3289	// resulting pvs
3290	Intersectable *obj = pit.Next(pvsData);
3291	obj->Mail();
3292	}
3293	pit = basePvs.GetIterator();
3294	}
3295
3296	while (pit.HasMoreEntries())
3297	{
3298	Intersectable *object = pit.Next(pvsData);
3299
3300	// compute filter size based on the distance and the numebr of samples
3301	AxisAlignedBox3 box = object->GetBox();
3302
3303	float distance = Distance(center, box.Center());
3304	float globalRadius = distance*globalC;
3305
3306	int objectSamples = (int)pvsData.mSumPdf;
3307	float localRadius = MAX_FLOAT;
3308
3309	localRadius = filterSize0.5fMagnitude(box.Diagonal())/
3310	sqrt((float)objectSamples);
3311
3312	// cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;
3313
3314	// now compute the filter size
3315	float radius;
3316
3317	#if 0
3318	if (objectSamples <= 1)
3319	{
3320	if (localRadius > globalRadius)
3321	{
3322	radius = 0.5flRadius;
3323	stats.mLocalFilterCount++;
3324	}
3325	else
3326	{
3327	radius = globalRadius;
3328	stats.mGlobalFilterCount++;
3329	}
3330	}
3331	else
3332	{
3333	radius = localRadius;
3334	stats.mLocalFilterCount++;
3335	}
3336	#else
3337
3338	// radius = 0.5fglobalRadius + 0.5flocalRadius;
3339	radius = Min(globalRadius, localRadius);
3340
3341	if (localRadius > globalRadius)
3342	++ stats.mLocalFilterCount;
3343	else
3344	++ stats.mGlobalFilterCount;
3345	#endif
3346
3347	stats.mAvgFilterRadius += radius;
3348
3349	// cout<<"box = "<<box<<endl;
3350	// cout<<"distance = "<<distance<<endl;
3351	// cout<<"radiues = "<<radius<<endl;
3352
3353	box.Enlarge(Vector3(radius));
3354
3355	if (filteredBoxes)
3356	filteredBoxes->push_back(box);
3357
3358	objects.clear();
3359
3360	// $$ warning collect objects takes only unmailed ones!
3361	if (mUseKdPvs) {
3362	GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
3363	//GetPreprocessor()->mKdTree->CollectSmallKdObjects(box, objects, 0.02f);
3364
3365	} else
3366	CollectObjects(box, objects);
3367
3368	// cout<<"collected objects="<<objects.size()<<endl;
3369	ObjectContainer::const_iterator noi = objects.begin();
3370	for (; noi != objects.end(); ++ noi)
3371	{
3372	Intersectable o = noi;
3373
3374	// $$ JB warning: pdfs are not correct at this point!
3375	pvs.AddSampleDirty(o, Limits::Small);
3376	}
3377	}
3378
3379	stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
3380	}
3381
3382	//Debug << " nPvs size = " << pvs.GetSize() << endl;
3383
3384	if (!mUseKdPvs && !onlyNewObjects)
3385	{
3386	PvsData pvsData;
3387
3388	// copy the base pvs to the new pvs
3389	pit = basePvs.GetIterator();
3390	while (pit.HasMoreEntries())
3391	{
3392	Intersectable *obj = pit.Next(pvsData);
3393	pvs.AddSampleDirty(obj, pvsData.mSumPdf);
3394	}
3395	}
3396
3397	pvs.SimpleSort();
3398	viewCell->SetFilteredPvsSize(pvs.GetSize());
3399
3400	// cout<<"pvsCost="<<basePvs.EvalPvsCost()<<endl;
3401	// cout<<"fPvsCost="<<pvs.EvalPvsCost()<<endl;
3402
3403
3404	// warning: not thread-safe!
3405	if (!mUseKdPvs)
3406	Intersectable::NewMail();
3407
3408	return stats;
3409	}
3410
3411
3412
3413	void ViewCellsManager::ExportColor(Exporter *exporter,
3414	ViewCell *vc,
3415	int colorCode) const
3416	{
3417	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3418
3419	float importance = 0;
3420	static Material m;
3421	//cout << "color code: " << colorCode << endl;
3422
3423	switch (colorCode)
3424	{
3425	case 0: // Random
3426	{
3427	if (vcValid)
3428	{
3429	m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
3430	m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
3431	m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
3432	}
3433	else
3434	{
3435	m.mDiffuseColor.r = 0.0f;
3436	m.mDiffuseColor.g = 1.0f;
3437	m.mDiffuseColor.b = 0.0f;
3438	}
3439
3440	exporter->SetForcedMaterial(m);
3441	return;
3442	}
3443
3444	case 1: // pvs
3445	{
3446	if (mCurrentViewCellsStats.maxPvs)
3447	{
3448	importance = //(float)mViewCellsTree->GetTrianglesInPvs(vc) / 700;
3449	(float)mCurrentViewCellsStats.maxPvs;
3450	}
3451	}
3452	break;
3453	case 2: // merges
3454	{
3455	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
3456	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3457	}
3458	break;
3459	default:
3460	break;
3461	}
3462
3463	// special color code for invalid view cells
3464	m.mDiffuseColor.r = importance;
3465	m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
3466	m.mDiffuseColor.g = 1.0f - importance;
3467
3468	//Debug << "importance: " << importance << endl;
3469	exporter->SetForcedMaterial(m);
3470	}
3471
3472
3473	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3474	vector<MergeCandidate> &candidates)
3475	{
3476	// implemented in subclasses
3477	}
3478
3479
3480	void ViewCellsManager::UpdatePvsForEvaluation()
3481	{
3482	ObjectPvs objPvs;
3483	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
3484	}
3485
3486
3487	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
3488	{
3489	// terminate traversal
3490	if (root->IsLeaf())
3491	{
3492	// we assume that pvs is explicitly stored in leaves
3493	pvs = root->GetPvs();
3494	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
3495
3496	return;
3497	}
3498
3499	////////////////
3500	//-- interior node => propagate pvs up the tree
3501
3502	ViewCellInterior interior = static_cast<ViewCellInterior >(root);
3503
3504	// reset interior pvs
3505	interior->GetPvs().Clear();
3506
3507	// reset recursive pvs
3508	pvs.Clear();
3509
3510	// pvss of child nodes
3511	vector<ObjectPvs> pvsList;
3512	pvsList.resize((int)interior->mChildren.size());
3513
3514	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3515
3516	int i = 0;
3517
3518	////////
3519	//-- recursivly compute child pvss
3520
3521	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3522	{
3523	UpdatePvsForEvaluation(*vit, pvsList[i]);
3524	}
3525
3526	#if 1
3527	Intersectable::NewMail();
3528
3529
3530	///////////
3531	//-- merge pvss
3532
3533	PvsData pvsData;
3534
3535	vector<ObjectPvs>::iterator oit = pvsList.begin();
3536
3537	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3538	{
3539	ObjectPvsIterator pit = (*oit).GetIterator();
3540
3541	// add pvss to new pvs: use mailing to avoid adding entries two times.
3542	while (pit.HasMoreEntries())
3543	{
3544	Intersectable *intersect = pit.Next(pvsData);
3545
3546	if (!intersect->Mailed())
3547	{
3548	intersect->Mail();
3549	pvs.AddSampleDirty(intersect, pvsData.mSumPdf);
3550	}
3551	}
3552	}
3553
3554	// store pvs in this node
3555	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3556	{
3557	interior->SetPvs(pvs);
3558	}
3559
3560	// set new pvs size
3561	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3562
3563	#else
3564	// really merge cells: slow but sumPdf is correct
3565	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3566	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3567	#endif
3568	}
3569
3570
3571
3572	/*******************************************************************/
3573	/* BspViewCellsManager implementation */
3574	/*******************************************************************/
3575
3576
3577	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
3578	ViewCellsManager(vcTree), mBspTree(bspTree)
3579	{
3580	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3581
3582	mBspTree->SetViewCellsManager(this);
3583	mBspTree->SetViewCellsTree(mViewCellsTree);
3584	}
3585
3586
3587	bool BspViewCellsManager::ViewCellsConstructed() const
3588	{
3589	return mBspTree->GetRoot() != NULL;
3590	}
3591
3592
3593	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
3594	{
3595	return new BspViewCell(mesh);
3596	}
3597
3598
3599	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3600	const VssRayContainer &rays)
3601	{
3602	// if view cells were already constructed, we can finish
3603	if (ViewCellsConstructed())
3604	return 0;
3605
3606	int sampleContributions = 0;
3607
3608	// construct view cells using the collected samples
3609	RayContainer constructionRays;
3610	VssRayContainer savedRays;
3611
3612	// choose a a number of rays based on the ratio of cast rays / requested rays
3613	const int limit = min(mInitialSamples, (int)rays.size());
3614	VssRayContainer::const_iterator it, it_end = rays.end();
3615
3616	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3617
3618	for (it = rays.begin(); it != it_end; ++ it)
3619	{
3620	if (Random(1.0f) < prop)
3621	constructionRays.push_back(new Ray((it)));
3622	else
3623	savedRays.push_back(*it);
3624	}
3625
3626	if (!mUsePredefinedViewCells)
3627	{
3628	// no view cells loaded
3629	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3630	// collect final view cells
3631	mBspTree->CollectViewCells(mViewCells);
3632	}
3633	else
3634	{
3635	// use predefined view cells geometry =>
3636	// contruct bsp hierarchy over them
3637	mBspTree->Construct(mViewCells);
3638	}
3639
3640	// destroy rays created only for construction
3641	CLEAR_CONTAINER(constructionRays);
3642
3643	Debug << mBspTree->GetStatistics() << endl;
3644	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3645
3646	// recast rest of the rays
3647	if (SAMPLE_AFTER_SUBDIVISION)
3648	ComputeSampleContributions(savedRays, true, false);
3649
3650	// real meshes are contructed at this stage
3651	if (0)
3652	{
3653	cout << "finalizing view cells ... ";
3654	FinalizeViewCells(true);
3655	cout << "finished" << endl;
3656	}
3657
3658	return sampleContributions;
3659	}
3660
3661
3662	void BspViewCellsManager::CollectViewCells()
3663	{
3664	if (!ViewCellsTreeConstructed())
3665	{ // view cells tree constructed
3666	mBspTree->CollectViewCells(mViewCells);
3667	}
3668	else
3669	{ // we can use the view cells tree hierarchy to get the right set
3670	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3671	}
3672	}
3673
3674
3675	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3676	{
3677	if (1)
3678	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3679	else
3680	// compute view cell area as subsititute for probability
3681	return GetArea(viewCell) / GetAccVcArea();
3682	}
3683
3684
3685
3686	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3687	const Vector3 &termination,
3688	ViewCellContainer &viewcells)
3689	{
3690	return mBspTree->CastLineSegment(origin, termination, viewcells);
3691	}
3692
3693
3694	bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
3695	const Vector3 &termination,
3696	ViewCell *viewCell)
3697	{
3698	return false;
3699	}
3700
3701
3702	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3703	{
3704	// save color code
3705	const int savedColorCode = mColorCode;
3706
3707	Exporter *exporter;
3708
3709	// export merged view cells using pvs color coding
3710	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3711	cout << "exporting view cells after merge (pvs size) ... ";
3712
3713	if (exporter)
3714	{
3715	if (mExportGeometry)
3716	{
3717	exporter->ExportGeometry(objects);
3718	}
3719
3720	exporter->SetFilled();
3721	mColorCode = 1;
3722
3723	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3724
3725	delete exporter;
3726	}
3727	cout << "finished" << endl;
3728
3729	mColorCode = savedColorCode;
3730	}
3731
3732
3733	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3734	const VssRayContainer &rays)
3735	{
3736	if (!ViewCellsConstructed())
3737	{
3738	Debug << "view cells not constructed" << endl;
3739	return 0;
3740	}
3741
3742	// view cells already finished before post processing step,
3743	// i.e., because they were loaded from disc
3744	if (mViewCellsFinished)
3745	{
3746	FinalizeViewCells(true);
3747	EvaluateViewCellsStats();
3748
3749	return 0;
3750	}
3751
3752	//////////////////
3753	//-- merge leaves of the view cell hierarchy
3754
3755	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3756	long startTime = GetTime();
3757
3758	VssRayContainer postProcessRays;
3759	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3760
3761	if (mMergeViewCells)
3762	{
3763	cout << "constructing visibility based merge tree" << endl;
3764	mViewCellsTree->ConstructMergeTree(rays, objects);
3765	}
3766	else
3767	{
3768	cout << "constructing spatial merge tree" << endl;
3769	ViewCell *root;
3770	// the spatial merge tree is difficult to build for
3771	// this type of construction, as view cells cover several
3772	// leaves => create dummy tree which is only 2 levels deep
3773	if (mUsePredefinedViewCells)
3774	{
3775	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3776	}
3777	else
3778	{
3779	// create spatial merge hierarchy
3780	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3781	}
3782
3783	mViewCellsTree->SetRoot(root);
3784
3785	// recompute pvs in the whole hierarchy
3786	ObjectPvs pvs;
3787	UpdatePvsForEvaluation(root, pvs);
3788	}
3789
3790	cout << "finished" << endl;
3791	cout << "merged view cells in "
3792	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3793
3794	Debug << "Postprocessing: Merged view cells in "
3795	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3796
3797
3798	////////////////////////
3799	//-- visualization and statistics after merge
3800
3801	if (1)
3802	{
3803	char mstats[100];
3804	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3805	mViewCellsTree->ExportStats(mstats);
3806	}
3807
3808	// recompute view cells and stats
3809	ResetViewCells();
3810	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3811
3812	// visualization of the view cells
3813	if (1) ExportMergedViewCells(objects);
3814
3815	// compute final meshes and volume / area
3816	if (1) FinalizeViewCells(true);
3817
3818	return 0;
3819	}
3820
3821
3822	BspViewCellsManager::~BspViewCellsManager()
3823	{
3824	}
3825
3826
3827	int BspViewCellsManager::GetType() const
3828	{
3829	return BSP;
3830	}
3831
3832
3833	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3834	const VssRayContainer &sampleRays)
3835	{
3836	if (!ViewCellsConstructed())
3837	return;
3838
3839	const int savedColorCode = mColorCode;
3840
3841	if (1) // export final view cells
3842	{
3843	mColorCode = 1; // 0 = pvs, 1 = random
3844	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3845
3846	cout << "exporting view cells after merge (pvs size) ... ";
3847
3848	if (exporter)
3849	{
3850	if (mExportGeometry)
3851	{
3852	exporter->ExportGeometry(objects);
3853	}
3854
3855	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3856	delete exporter;
3857	}
3858	cout << "finished" << endl;
3859	}
3860
3861	// reset color code
3862	mColorCode = savedColorCode;
3863
3864
3865	//////////////////
3866	//-- visualization of the BSP splits
3867
3868	bool exportSplits = false;
3869	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3870
3871	if (exportSplits)
3872	{
3873	cout << "exporting splits ... ";
3874	ExportSplits(objects);
3875	cout << "finished" << endl;
3876	}
3877
3878	int leafOut;
3879	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3880	const int raysOut = 100;
3881	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3882	}
3883
3884
3885	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3886	{
3887	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3888
3889	if (exporter)
3890	{
3891	//exporter->SetFilled();
3892	if (mExportGeometry)
3893	{
3894	exporter->ExportGeometry(objects);
3895	}
3896
3897	Material m;
3898	m.mDiffuseColor = RgbColor(1, 0, 0);
3899	exporter->SetForcedMaterial(m);
3900	exporter->SetWireframe();
3901
3902	exporter->ExportBspSplits(*mBspTree, true);
3903
3904	// NOTE: take forced material, else big scenes cannot be viewed
3905	m.mDiffuseColor = RgbColor(0, 1, 0);
3906	exporter->SetForcedMaterial(m);
3907	//exporter->ResetForcedMaterial();
3908
3909	delete exporter;
3910	}
3911	}
3912
3913
3914	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3915	const int maxViewCells,
3916	const bool sortViewCells,
3917	const bool exportPvs,
3918	const bool exportRays,
3919	const int maxRays,
3920	const string &prefix,
3921	VssRayContainer *visRays)
3922	{
3923	if (sortViewCells)
3924	{ // sort view cells to visualize the largest view cells
3925	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
3926	}
3927
3928	//////////
3929	//-- export visualizations of some view cells
3930
3931	ViewCell::NewMail();
3932	const int limit = min(maxViewCells, (int)mViewCells.size());
3933
3934	for (int i = 0; i < limit; ++ i)
3935	{
3936	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
3937	ViewCell *vc = mViewCells[idx];
3938
3939	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
3940	continue;
3941
3942	vc->Mail();
3943
3944	ObjectPvs pvs;
3945	mViewCellsTree->GetPvs(vc, pvs);
3946
3947	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
3948	Exporter *exporter = Exporter::GetExporter(s);
3949
3950	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetTrianglesInPvs(vc) << endl;
3951
3952	if (exportRays)
3953	{
3954	////////////
3955	//-- export rays piercing this view cell
3956
3957	// use rays stored with the view cells
3958	VssRayContainer vcRays, vcRays2, vcRays3;
3959	VssRayContainer collectRays;
3960
3961	// collect initial view cells
3962	ViewCellContainer leaves;
3963	mViewCellsTree->CollectLeaves(vc, leaves);
3964
3965	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3966	for (vit = leaves.begin(); vit != vit_end; ++ vit)
3967	{
3968	// prepare some rays for visualization
3969	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
3970	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
3971	{
3972	collectRays.push_back(*rit);
3973	}
3974	}
3975
3976	const int raysOut = min((int)collectRays.size(), maxRays);
3977
3978	// prepare some rays for visualization
3979	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3980	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3981	{
3982	const float p = RandomValue(0.0f, (float)collectRays.size());
3983	if (p < raysOut)
3984	{
3985	if ((*rit)->mFlags & VssRay::BorderSample)
3986	{
3987	vcRays.push_back(*rit);
3988	}
3989	else if ((*rit)->mFlags & VssRay::ReverseSample)
3990	{
3991	vcRays2.push_back(*rit);
3992	}
3993	else
3994	{
3995	vcRays3.push_back(*rit);
3996	}
3997	}
3998	}
3999
4000	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
4001	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
4002	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
4003	}
4004
4005	////////////////
4006	//-- export view cell geometry
4007
4008	exporter->SetWireframe();
4009
4010	Material m;//= RandomMaterial();
4011	m.mDiffuseColor = RgbColor(0, 1, 0);
4012	exporter->SetForcedMaterial(m);
4013
4014	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4015	exporter->SetFilled();
4016
4017	if (exportPvs)
4018	{
4019	Intersectable::NewMail();
4020	ObjectPvsIterator pit = pvs.GetIterator();
4021
4022	while (pit.HasMoreEntries())
4023	{
4024	Intersectable *intersect = pit.Next();
4025
4026	// output PVS of view cell
4027	if (!intersect->Mailed())
4028	{
4029	intersect->Mail();
4030
4031	m = RandomMaterial();
4032	exporter->SetForcedMaterial(m);
4033	exporter->ExportIntersectable(intersect);
4034	}
4035	}
4036	cout << endl;
4037	}
4038
4039	DEL_PTR(exporter);
4040	cout << "finished" << endl;
4041	}
4042	}
4043
4044
4045	void BspViewCellsManager::TestSubdivision()
4046	{
4047	ViewCellContainer leaves;
4048	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4049
4050	ViewCellContainer::const_iterator it, it_end = leaves.end();
4051
4052	const float vol = mViewSpaceBox.GetVolume();
4053	float subdivVol = 0;
4054	float newVol = 0;
4055
4056	for (it = leaves.begin(); it != it_end; ++ it)
4057	{
4058	BspNodeGeometry geom;
4059	mBspTree->ConstructGeometry(*it, geom);
4060
4061	const float lVol = geom.GetVolume();
4062	newVol += lVol;
4063	subdivVol += (*it)->GetVolume();
4064
4065	const float thres = 0.9f;
4066	if ((lVol < ((it)->GetVolume() thres)) \|\|
4067	(lVol * thres > ((*it)->GetVolume())))
4068	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4069	}
4070
4071	Debug << "exact volume: " << vol << endl;
4072	Debug << "subdivision volume: " << subdivVol << endl;
4073	Debug << "new volume: " << newVol << endl;
4074	}
4075
4076
4077	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4078	ViewCell *vc,
4079	const AxisAlignedBox3 *sceneBox,
4080	const AxisAlignedPlane *clipPlane
4081	) const
4082	{
4083	if (clipPlane)
4084	{
4085	const Plane3 plane = clipPlane->GetPlane();
4086
4087	ViewCellContainer leaves;
4088	mViewCellsTree->CollectLeaves(vc, leaves);
4089	ViewCellContainer::const_iterator it, it_end = leaves.end();
4090
4091	for (it = leaves.begin(); it != it_end; ++ it)
4092	{
4093	BspNodeGeometry geom;
4094	BspNodeGeometry front;
4095	BspNodeGeometry back;
4096
4097	mBspTree->ConstructGeometry(*it, geom);
4098
4099	const float eps = 0.0001f;
4100	const int cf = geom.Side(plane, eps);
4101
4102	if (cf == -1)
4103	{
4104	exporter->ExportPolygons(geom.GetPolys());
4105	}
4106	else if (cf == 0)
4107	{
4108	geom.SplitGeometry(front,
4109	back,
4110	plane,
4111	mViewSpaceBox,
4112	eps);
4113
4114	if (back.Valid())
4115	{
4116	exporter->ExportPolygons(back.GetPolys());
4117	}
4118	}
4119	}
4120	}
4121	else
4122	{
4123	// export mesh if available
4124	// TODO: some bug here?
4125	if (1 && vc->GetMesh())
4126	{
4127	exporter->ExportMesh(vc->GetMesh());
4128	}
4129	else
4130	{
4131	BspNodeGeometry geom;
4132	mBspTree->ConstructGeometry(vc, geom);
4133	exporter->ExportPolygons(geom.GetPolys());
4134	}
4135	}
4136	}
4137
4138
4139	void BspViewCellsManager::CreateMesh(ViewCell *vc)
4140	{
4141	// note: should previous mesh be deleted (via mesh manager?)
4142	BspNodeGeometry geom;
4143	mBspTree->ConstructGeometry(vc, geom);
4144
4145	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4146
4147	IncludeNodeGeomInMesh(geom, *mesh);
4148	mesh->ComputeBoundingBox();
4149
4150	vc->SetMesh(mesh);
4151	}
4152
4153
4154	void BspViewCellsManager::Finalize(ViewCell *viewCell,
4155	const bool createMesh)
4156	{
4157	float area = 0;
4158	float volume = 0;
4159
4160	ViewCellContainer leaves;
4161	mViewCellsTree->CollectLeaves(viewCell, leaves);
4162
4163	ViewCellContainer::const_iterator it, it_end = leaves.end();
4164
4165	for (it = leaves.begin(); it != it_end; ++ it)
4166	{
4167	BspNodeGeometry geom;
4168
4169	mBspTree->ConstructGeometry(*it, geom);
4170
4171	const float lVol = geom.GetVolume();
4172	const float lArea = geom.GetArea();
4173
4174	area += lArea;
4175	volume += lVol;
4176
4177	CreateMesh(*it);
4178	}
4179
4180	viewCell->SetVolume(volume);
4181	viewCell->SetArea(area);
4182	}
4183
4184
4185	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4186	{
4187	if (!ViewCellsConstructed())
4188	{
4189	return NULL;
4190	}
4191	if (!mViewSpaceBox.IsInside(point))
4192	{
4193	return NULL;
4194	}
4195	return mBspTree->GetViewCell(point);
4196	}
4197
4198
4199	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4200	vector<MergeCandidate> &candidates)
4201	{
4202	cout << "collecting merge candidates ... " << endl;
4203
4204	if (mUseRaysForMerge)
4205	{
4206	mBspTree->CollectMergeCandidates(rays, candidates);
4207	}
4208	else
4209	{
4210	vector<BspLeaf *> leaves;
4211	mBspTree->CollectLeaves(leaves);
4212	mBspTree->CollectMergeCandidates(leaves, candidates);
4213	}
4214
4215	cout << "fininshed collecting candidates" << endl;
4216	}
4217
4218
4219
4220	bool BspViewCellsManager::ExportViewCells(const string filename,
4221	const bool exportPvs,
4222	const ObjectContainer &objects)
4223	{
4224	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
4225	{
4226	return false;
4227	}
4228
4229	cout << "exporting view cells to xml ... ";
4230
4231	OUT_STREAM stream(filename.c_str());
4232
4233	// we need unique ids for each view cell
4234	CreateUniqueViewCellIds();
4235
4236	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
4237	stream << "<VisibilitySolution>" << endl;
4238
4239	if (exportPvs)
4240	{
4241	//////////
4242	//-- export bounding boxes: they are used to identify the objects from the pvs and
4243	//-- assign them to the entities in the rendering engine
4244
4245	stream << "<BoundingBoxes>" << endl;
4246	ObjectContainer::const_iterator oit, oit_end = objects.end();
4247
4248	for (oit = objects.begin(); oit != oit_end; ++ oit)
4249	{
4250	const AxisAlignedBox3 box = (*oit)->GetBox();
4251
4252	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
4253	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
4254	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
4255	}
4256
4257	stream << "</BoundingBoxes>" << endl;
4258	}
4259
4260	///////////
4261	//-- export the view cells and the pvs
4262
4263	const int numViewCells = mCurrentViewCellsStats.viewCells;
4264	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
4265
4266	mViewCellsTree->Export(stream, exportPvs);
4267
4268	stream << "</ViewCells>" << endl;
4269
4270	/////////////
4271	//-- export the view space hierarchy
4272	stream << "<ViewSpaceHierarchy type=\"bsp\""
4273	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
4274	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
4275
4276	mBspTree->Export(stream);
4277
4278	// end tags
4279	stream << "</ViewSpaceHierarchy>" << endl;
4280	stream << "</VisibilitySolution>" << endl;
4281
4282	stream.close();
4283	cout << "finished" << endl;
4284
4285	return true;
4286	}
4287
4288
4289	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
4290	{
4291	ViewCellInterior *vcRoot = new ViewCellInterior();
4292
4293	// evaluate merge cost for priority traversal
4294	const float mergeCost = -(float)root->mTimeStamp;
4295	vcRoot->SetMergeCost(mergeCost);
4296
4297	float volume = 0;
4298	vector<BspLeaf *> leaves;
4299	mBspTree->CollectLeaves(leaves);
4300	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
4301	ViewCell::NewMail();
4302
4303	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4304	{
4305	BspLeaf leaf = lit;
4306	ViewCell *vc = leaf->GetViewCell();
4307
4308	if (!vc->Mailed())
4309	{
4310	vc->Mail();
4311	vc->SetMergeCost(0.0f);
4312	vcRoot->SetupChildLink(vc);
4313
4314	volume += vc->GetVolume();
4315	volume += vc->GetVolume();
4316	vcRoot->SetVolume(volume);
4317	}
4318	}
4319
4320	return vcRoot;
4321	}
4322
4323
4324	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4325	{
4326	// terminate recursion
4327	if (root->IsLeaf())
4328	{
4329	BspLeaf leaf = static_cast<BspLeaf >(root);
4330	leaf->GetViewCell()->SetMergeCost(0.0f);
4331	return leaf->GetViewCell();
4332	}
4333
4334	BspInterior interior = static_cast<BspInterior >(root);
4335	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4336
4337	// evaluate merge cost for priority traversal
4338	const float mergeCost = -(float)root->mTimeStamp;
4339	viewCellInterior->SetMergeCost(mergeCost);
4340
4341	float volume = 0;
4342
4343	BspNode *front = interior->GetFront();
4344	BspNode *back = interior->GetBack();
4345
4346
4347	////////////
4348	//-- recursivly compute child hierarchies
4349
4350	ViewCell *backVc = ConstructSpatialMergeTree(back);
4351	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4352
4353	viewCellInterior->SetupChildLink(backVc);
4354	viewCellInterior->SetupChildLink(frontVc);
4355
4356	volume += backVc->GetVolume();
4357	volume += frontVc->GetVolume();
4358
4359	viewCellInterior->SetVolume(volume);
4360
4361	return viewCellInterior;
4362	}
4363
4364
4365	/************************************************************************/
4366	/* KdViewCellsManager implementation */
4367	/************************************************************************/
4368
4369
4370
4371	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
4372	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
4373	{
4374	}
4375
4376
4377	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
4378	{
4379	// compute view cell area / volume as subsititute for probability
4380	if (0)
4381	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
4382	else
4383	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
4384	}
4385
4386
4387
4388
4389	void KdViewCellsManager::CollectViewCells()
4390	{
4391	//mKdTree->CollectViewCells(mViewCells); TODO
4392	}
4393
4394
4395	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4396	const VssRayContainer &rays)
4397	{
4398	// if view cells already constructed
4399	if (ViewCellsConstructed())
4400	return 0;
4401
4402	mKdTree->Construct();
4403
4404	mTotalAreaValid = false;
4405	// create the view cells
4406	mKdTree->CreateAndCollectViewCells(mViewCells);
4407	// cast rays
4408	ComputeSampleContributions(rays, true, false);
4409
4410	EvaluateViewCellsStats();
4411	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4412
4413	return 0;
4414	}
4415
4416
4417	bool KdViewCellsManager::ViewCellsConstructed() const
4418	{
4419	return mKdTree->GetRoot() != NULL;
4420	}
4421
4422
4423	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
4424	const VssRayContainer &rays)
4425	{
4426	return 0;
4427	}
4428
4429
4430	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4431	const int maxViewCells,
4432	const bool sortViewCells,
4433	const bool exportPvs,
4434	const bool exportRays,
4435	const int maxRays,
4436	const string &prefix,
4437	VssRayContainer *visRays)
4438	{
4439	// TODO
4440	}
4441
4442
4443	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
4444	const VssRayContainer &sampleRays)
4445	{
4446	if (!ViewCellsConstructed())
4447	return;
4448
4449	// using view cells instead of the kd PVS of objects
4450	const bool useViewCells = true;
4451	bool exportRays = false;
4452
4453	int limit = min(mVisualizationSamples, (int)sampleRays.size());
4454	const int pvsOut = min((int)objects.size(), 10);
4455	VssRayContainer *rays = new VssRayContainer[pvsOut];
4456
4457	if (useViewCells)
4458	{
4459	const int leafOut = 10;
4460
4461	ViewCell::NewMail();
4462
4463	//-- some rays for visualization
4464	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4465	Debug << "visualization using " << raysOut << " samples" << endl;
4466
4467	//-- some random view cells and rays for visualization
4468	vector<KdLeaf *> kdLeaves;
4469
4470	for (int i = 0; i < leafOut; ++ i)
4471	kdLeaves.push_back(static_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4472
4473	for (int i = 0; i < kdLeaves.size(); ++ i)
4474	{
4475	KdLeaf *leaf = kdLeaves[i];
4476	RayContainer vcRays;
4477
4478	cout << "creating output for view cell " << i << " ... ";
4479	#if 0
4480	// check whether we can add the current ray to the output rays
4481	for (int k = 0; k < raysOut; ++ k)
4482	{
4483	Ray *ray = sampleRays[k];
4484
4485	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4486	{
4487	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4488
4489	if (leaf->GetViewCell() == leaf2->GetViewCell())
4490	{
4491	vcRays.push_back(ray);
4492	}
4493	}
4494	}
4495	#endif
4496	Intersectable::NewMail();
4497
4498	ViewCell *vc = leaf->mViewCell;
4499	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4500
4501	Exporter *exporter = Exporter::GetExporter(str);
4502	exporter->SetFilled();
4503
4504	exporter->SetWireframe();
4505	//exporter->SetFilled();
4506
4507	Material m;//= RandomMaterial();
4508	m.mDiffuseColor = RgbColor(1, 1, 0);
4509	exporter->SetForcedMaterial(m);
4510
4511	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4512	exporter->ExportBox(box);
4513
4514	// export rays piercing this view cell
4515	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4516
4517	m.mDiffuseColor = RgbColor(1, 0, 0);
4518	exporter->SetForcedMaterial(m);
4519
4520	// exporter->SetWireframe();
4521	exporter->SetFilled();
4522
4523	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4524
4525	while (pit.HasMoreEntries())
4526	{
4527	//-- output PVS of view cell
4528	Intersectable *intersect = pit.Next();
4529
4530	if (!intersect->Mailed())
4531	{
4532	exporter->ExportIntersectable(intersect);
4533	intersect->Mail();
4534	}
4535	}
4536
4537	DEL_PTR(exporter);
4538	cout << "finished" << endl;
4539	}
4540
4541	DEL_PTR(rays);
4542	}
4543	else // using kd PVS of objects
4544	{
4545	for (int i = 0; i < limit; ++ i)
4546	{
4547	VssRay *ray = sampleRays[i];
4548
4549	// check whether we can add this to the rays
4550	for (int j = 0; j < pvsOut; j++)
4551	{
4552	if (objects[j] == ray->mTerminationObject)
4553	{
4554	rays[j].push_back(ray);
4555	}
4556	}
4557	}
4558
4559	if (exportRays)
4560	{
4561	Exporter *exporter = NULL;
4562	exporter = Exporter::GetExporter("sample-rays.x3d");
4563	exporter->SetWireframe();
4564	exporter->ExportKdTree(*mKdTree);
4565
4566	for (int i = 0; i < pvsOut; i++)
4567	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4568
4569	exporter->SetFilled();
4570	delete exporter;
4571	}
4572
4573	for (int k=0; k < pvsOut; k++)
4574	{
4575	Intersectable *object = objects[k];
4576	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4577
4578	Exporter *exporter = Exporter::GetExporter(str);
4579	exporter->SetWireframe();
4580
4581	// matt: we do not use kd pvs
4582	#if 0
4583	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4584	Intersectable::NewMail();
4585
4586	// avoid adding the object to the list
4587	object->Mail();
4588	ObjectContainer visibleObjects;
4589
4590	for (; kit != object->mKdPvs.mEntries.end(); i++)
4591	{
4592	KdNode node = (kit).first;
4593	exporter->ExportBox(mKdTree->GetBox(node));
4594
4595	mKdTree->CollectObjects(node, visibleObjects);
4596	}
4597
4598	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4599	exporter->SetFilled();
4600
4601	for (int j = 0; j < visibleObjects.size(); j++)
4602	exporter->ExportIntersectable(visibleObjects[j]);
4603
4604	Material m;
4605	m.mDiffuseColor = RgbColor(1, 0, 0);
4606	exporter->SetForcedMaterial(m);
4607	exporter->ExportIntersectable(object);
4608	#endif
4609	delete exporter;
4610	}
4611	}
4612	}
4613
4614
4615	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4616	{
4617	return new KdViewCell(mesh);
4618	}
4619
4620
4621	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4622	ViewCell *vc,
4623	const AxisAlignedBox3 *sceneBox,
4624	const AxisAlignedPlane *clipPlane
4625	) const
4626	{
4627	ViewCellContainer leaves;
4628	mViewCellsTree->CollectLeaves(vc, leaves);
4629	ViewCellContainer::const_iterator it, it_end = leaves.end();
4630
4631	for (it = leaves.begin(); it != it_end; ++ it)
4632	{
4633	KdViewCell kdVc = static_cast<KdViewCell >(*it);
4634	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4635	}
4636	}
4637
4638
4639	int KdViewCellsManager::GetType() const
4640	{
4641	return ViewCellsManager::KD;
4642	}
4643
4644
4645
4646	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4647	{
4648	KdNode *node = leaf;
4649
4650	while (node->mParent && node->mDepth > mKdPvsDepth)
4651	node = node->mParent;
4652
4653	return node;
4654	}
4655
4656	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4657	const Vector3 &termination,
4658	ViewCellContainer &viewcells)
4659	{
4660	return mKdTree->CastLineSegment(origin, termination, viewcells);
4661	}
4662
4663
4664	bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
4665	const Vector3 &termination,
4666	ViewCell *viewCell)
4667	{
4668	return false;
4669	}
4670
4671
4672	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4673	{
4674	// TODO
4675	}
4676
4677
4678
4679	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4680	vector<MergeCandidate> &candidates)
4681	{
4682	// TODO
4683	}
4684
4685
4686
4687	/**************************************************************************/
4688	/* VspBspViewCellsManager implementation */
4689	/**************************************************************************/
4690
4691
4692	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4693	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4694	{
4695	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4696	mVspBspTree->SetViewCellsManager(this);
4697	mVspBspTree->mViewCellsTree = mViewCellsTree;
4698	}
4699
4700
4701	VspBspViewCellsManager::~VspBspViewCellsManager()
4702	{
4703	}
4704
4705
4706	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4707	{
4708	if (0 && mVspBspTree->mUseAreaForPvs)
4709	return GetArea(viewCell) / GetAccVcArea();
4710	else
4711	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4712	}
4713
4714
4715	void VspBspViewCellsManager::CollectViewCells()
4716	{
4717	// view cells tree constructed?
4718	if (!ViewCellsTreeConstructed())
4719	{
4720	mVspBspTree->CollectViewCells(mViewCells, false);
4721	}
4722	else
4723	{
4724	// we can use the view cells tree hierarchy to get the right set
4725	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4726	}
4727	}
4728
4729
4730	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4731	vector<MergeCandidate> &candidates)
4732	{
4733	cout << "collecting merge candidates ... " << endl;
4734
4735	if (mUseRaysForMerge)
4736	{
4737	mVspBspTree->CollectMergeCandidates(rays, candidates);
4738	}
4739	else
4740	{
4741	vector<BspLeaf *> leaves;
4742	mVspBspTree->CollectLeaves(leaves);
4743
4744	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4745	}
4746
4747	cout << "fininshed collecting candidates" << endl;
4748	}
4749
4750
4751	bool VspBspViewCellsManager::ViewCellsConstructed() const
4752	{
4753	return mVspBspTree->GetRoot() != NULL;
4754	}
4755
4756
4757	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4758	{
4759	return new BspViewCell(mesh);
4760	}
4761
4762
4763	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4764	const VssRayContainer &rays)
4765	{
4766	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4767
4768	// if view cells were already constructed
4769	if (ViewCellsConstructed())
4770	{
4771	return 0;
4772	}
4773
4774	int sampleContributions = 0;
4775	VssRayContainer sampleRays;
4776
4777	const int limit = min(mInitialSamples, (int)rays.size());
4778
4779	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4780	<< ", actual rays: " << (int)rays.size() << endl;
4781
4782	VssRayContainer savedRays;
4783
4784	if (SAMPLE_AFTER_SUBDIVISION)
4785	{
4786	VssRayContainer constructionRays;
4787
4788	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4789
4790	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4791	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4792
4793	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4794	}
4795	else
4796	{
4797	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4798	mVspBspTree->Construct(rays, &mViewSpaceBox);
4799	}
4800
4801	// collapse invalid regions
4802	cout << "collapsing invalid tree regions ... ";
4803	long startTime = GetTime();
4804
4805	const int collapsedLeaves = mVspBspTree->CollapseTree();
4806	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4807	<< " seconds" << endl;
4808
4809	cout << "finished" << endl;
4810
4811	/////////////////
4812	//-- stats after construction
4813
4814	Debug << mVspBspTree->GetStatistics() << endl;
4815
4816	ResetViewCells();
4817	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4818
4819
4820	//////////////////////
4821	//-- recast the rest of the rays
4822
4823	startTime = GetTime();
4824
4825	cout << "Computing remaining ray contributions ... ";
4826
4827	if (SAMPLE_AFTER_SUBDIVISION)
4828	ComputeSampleContributions(savedRays, true, false);
4829
4830	cout << "finished" << endl;
4831
4832	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4833	<< " secs" << endl;
4834
4835	cout << "construction finished" << endl;
4836
4837	if (0)
4838	{ ////////
4839	//-- real meshes are contructed at this stage
4840
4841	cout << "finalizing view cells ... ";
4842	FinalizeViewCells(true);
4843	cout << "finished" << endl;
4844	}
4845
4846	return sampleContributions;
4847	}
4848
4849
4850	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4851	const ObjectContainer &objects)
4852	{
4853	int vcSize = 0;
4854	int pvsSize = 0;
4855
4856	//-- merge view cells
4857	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4858	long startTime = GetTime();
4859
4860
4861	if (mMergeViewCells)
4862	{
4863	// TODO: should be done BEFORE the ray casting
4864	// compute tree by merging the nodes based on cost heuristics
4865	mViewCellsTree->ConstructMergeTree(rays, objects);
4866	}
4867	else
4868	{
4869	// compute tree by merging the nodes of the spatial hierarchy
4870	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4871	mViewCellsTree->SetRoot(root);
4872
4873	// compute pvs
4874	ObjectPvs pvs;
4875	UpdatePvsForEvaluation(root, pvs);
4876	}
4877
4878	if (1)
4879	{
4880	char mstats[100];
4881	ObjectPvs pvs;
4882
4883	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4884	mViewCellsTree->ExportStats(mstats);
4885	}
4886
4887	cout << "merged view cells in "
4888	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4889
4890	Debug << "Postprocessing: Merged view cells in "
4891	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4892
4893
4894	//////////////////
4895	//-- stats and visualizations
4896
4897	int savedColorCode = mColorCode;
4898
4899	// get currently active view cell set
4900	ResetViewCells();
4901	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4902
4903	if (mShowVisualization) // export merged view cells
4904	{
4905	mColorCode = 0;
4906	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4907
4908	cout << "exporting view cells after merge ... ";
4909
4910	if (exporter)
4911	{
4912	if (0)
4913	exporter->SetWireframe();
4914	else
4915	exporter->SetFilled();
4916
4917	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4918
4919	if (mExportGeometry)
4920	{
4921	Material m;
4922	m.mDiffuseColor = RgbColor(0, 1, 0);
4923	exporter->SetForcedMaterial(m);
4924	exporter->SetFilled();
4925
4926	exporter->ExportGeometry(objects);
4927	}
4928
4929	delete exporter;
4930	}
4931	cout << "finished" << endl;
4932	}
4933
4934	mColorCode = savedColorCode;
4935	}
4936
4937
4938	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4939	const ObjectContainer &objects)
4940	{
4941	mRenderer->RenderScene();
4942
4943	SimulationStatistics ss;
4944	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4945	Debug << "render time before refine\n\n" << ss << endl;
4946
4947	const long startTime = GetTime();
4948	cout << "Refining the merged view cells ... ";
4949
4950	// refining the merged view cells
4951	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4952
4953	//-- stats and visualizations
4954	cout << "finished" << endl;
4955	cout << "refined " << refined << " view cells in "
4956	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4957
4958	Debug << "Postprocessing: refined " << refined << " view cells in "
4959	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4960	}
4961
4962
4963	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4964	const VssRayContainer &rays)
4965	{
4966	if (!ViewCellsConstructed())
4967	{
4968	Debug << "postprocess error: no view cells constructed" << endl;
4969	return 0;
4970	}
4971
4972	// view cells already finished before post processing step
4973	// (i.e. because they were loaded)
4974	if (mViewCellsFinished)
4975	{
4976	FinalizeViewCells(true);
4977	EvaluateViewCellsStats();
4978
4979	return 0;
4980	}
4981
4982	// check if new view cells turned invalid
4983	int minPvs, maxPvs;
4984
4985	if (0)
4986	{
4987	minPvs = mMinPvsSize;
4988	maxPvs = mMaxPvsSize;
4989	}
4990	else
4991	{
4992	// problem matt: why did I start here from zero?
4993	minPvs = 0;
4994	maxPvs = mMaxPvsSize;
4995	}
4996
4997	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4998	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4999
5000	SetValidity(minPvs, maxPvs);
5001
5002	// update valid view space according to valid view cells
5003	if (0) mVspBspTree->ValidateTree();
5004
5005	// area has to be recomputed
5006	mTotalAreaValid = false;
5007	VssRayContainer postProcessRays;
5008	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5009
5010	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5011
5012	//////////
5013	//-- merge neighbouring view cells
5014	MergeViewCells(postProcessRays, objects);
5015
5016	// refines the merged view cells
5017	if (0) RefineViewCells(postProcessRays, objects);
5018
5019
5020	///////////
5021	//-- render simulation after merge + refine
5022
5023	cout << "\nview cells partition render time before compress" << endl << endl;;
5024	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5025	SimulationStatistics ss;
5026	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5027	cout << ss << endl;
5028
5029	if (0) CompressViewCells();
5030
5031	// collapse sibling leaves that share the same view cell
5032	if (0) mVspBspTree->CollapseTree();
5033
5034	// recompute view cell list and statistics
5035	ResetViewCells();
5036
5037	// compute final meshes and volume / area
5038	if (1) FinalizeViewCells(true);
5039
5040	return 0;
5041	}
5042
5043
5044	int VspBspViewCellsManager::GetType() const
5045	{
5046	return VSP_BSP;
5047	}
5048
5049
5050	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
5051	{
5052	// terminate recursion
5053	if (root->IsLeaf())
5054	{
5055	BspLeaf leaf = static_cast<BspLeaf >(root);
5056	leaf->GetViewCell()->SetMergeCost(0.0f);
5057	return leaf->GetViewCell();
5058	}
5059
5060
5061	BspInterior interior = static_cast<BspInterior >(root);
5062	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5063
5064	// evaluate merge cost for priority traversal
5065	float mergeCost = 1.0f / (float)root->mTimeStamp;
5066	viewCellInterior->SetMergeCost(mergeCost);
5067
5068	float volume = 0;
5069
5070	BspNode *front = interior->GetFront();
5071	BspNode *back = interior->GetBack();
5072
5073
5074	ObjectPvs frontPvs, backPvs;
5075
5076	//-- recursivly compute child hierarchies
5077	ViewCell *backVc = ConstructSpatialMergeTree(back);
5078	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5079
5080
5081	viewCellInterior->SetupChildLink(backVc);
5082	viewCellInterior->SetupChildLink(frontVc);
5083
5084	volume += backVc->GetVolume();
5085	volume += frontVc->GetVolume();
5086
5087	viewCellInterior->SetVolume(volume);
5088
5089	return viewCellInterior;
5090	}
5091
5092
5093	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5094	{
5095	if (!ViewCellsConstructed())
5096	return ViewCellsManager::GetViewPoint(viewPoint);
5097
5098	// TODO: set reasonable limit
5099	const int limit = 20;
5100
5101	for (int i = 0; i < limit; ++ i)
5102	{
5103	viewPoint = mViewSpaceBox.GetRandomPoint();
5104	if (mVspBspTree->ViewPointValid(viewPoint))
5105	{
5106	return true;
5107	}
5108	}
5109
5110	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5111	return false;
5112	}
5113
5114
5115	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5116	{
5117	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5118	// validy update in preprocessor for all managers)
5119	return ViewCellsManager::ViewPointValid(viewPoint);
5120
5121	// return mViewSpaceBox.IsInside(viewPoint) &&
5122	// mVspBspTree->ViewPointValid(viewPoint);
5123	}
5124
5125
5126	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
5127	const VssRayContainer &sampleRays)
5128	{
5129	if (!ViewCellsConstructed())
5130	return;
5131
5132	VssRayContainer visRays;
5133	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5134
5135	if (1)
5136	{
5137	//////////////////
5138	//-- export final view cell partition
5139
5140	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5141
5142	if (exporter)
5143	{
5144	cout << "exporting view cells after post process ... ";
5145
5146	if (0)
5147	{ // export view space box
5148	exporter->SetWireframe();
5149	exporter->ExportBox(mViewSpaceBox);
5150	exporter->SetFilled();
5151	}
5152
5153	Material m;
5154	m.mDiffuseColor.r = 0.0f;
5155	m.mDiffuseColor.g = 0.5f;
5156	m.mDiffuseColor.b = 0.5f;
5157
5158	exporter->SetForcedMaterial(m);
5159
5160	if (1 && mExportGeometry)
5161	{
5162	exporter->ExportGeometry(objects);
5163	}
5164
5165	if (0 && mExportRays)
5166	{
5167	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
5168	}
5169	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5170
5171	delete exporter;
5172	cout << "finished" << endl;
5173	}
5174	}
5175
5176	////////////////
5177	//-- visualization of the BSP splits
5178
5179	bool exportSplits = false;
5180	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
5181
5182	if (exportSplits)
5183	{
5184	cout << "exporting splits ... ";
5185	ExportSplits(objects, visRays);
5186	cout << "finished" << endl;
5187	}
5188
5189	////////
5190	//-- export single view cells
5191
5192	int leafOut;
5193	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5194	const int raysOut = 100;
5195
5196	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5197	}
5198
5199
5200	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
5201	const VssRayContainer &rays)
5202	{
5203	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
5204
5205	if (exporter)
5206	{
5207	Material m;
5208	m.mDiffuseColor = RgbColor(1, 0, 0);
5209	exporter->SetForcedMaterial(m);
5210	exporter->SetWireframe();
5211
5212	exporter->ExportBspSplits(*mVspBspTree, true);
5213
5214	// take forced material, else big scenes cannot be viewed
5215	m.mDiffuseColor = RgbColor(0, 1, 0);
5216	exporter->SetForcedMaterial(m);
5217	exporter->SetFilled();
5218
5219	exporter->ResetForcedMaterial();
5220
5221	// export rays
5222	if (mExportRays)
5223	{
5224	exporter->ExportRays(rays, RgbColor(1, 1, 0));
5225	}
5226
5227	if (mExportGeometry)
5228	{
5229	exporter->ExportGeometry(objects);
5230	}
5231	delete exporter;
5232	}
5233	}
5234
5235
5236	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5237	const int maxViewCells,
5238	const bool sortViewCells,
5239	const bool exportPvs,
5240	const bool exportRays,
5241	const int maxRays,
5242	const string &prefix,
5243	VssRayContainer *visRays)
5244	{
5245	if (sortViewCells)
5246	{
5247	// sort view cells to visualize the largest view cells
5248	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
5249	}
5250
5251	//////////
5252	//-- export some view cells for visualization
5253
5254	ViewCell::NewMail();
5255	const int limit = min(maxViewCells, (int)mViewCells.size());
5256
5257	for (int i = 0; i < limit; ++ i)
5258	{
5259	cout << "creating output for view cell " << i << " ... ";
5260
5261	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
5262	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
5263
5264	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
5265	continue;
5266
5267	vc->Mail();
5268
5269	ObjectPvs pvs;
5270	mViewCellsTree->GetPvs(vc, pvs);
5271
5272	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5273	Exporter *exporter = Exporter::GetExporter(s);
5274
5275	const float pvsCost = mViewCellsTree->GetTrianglesInPvs(vc);
5276	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
5277
5278	if (exportRays)
5279	{
5280	////////////
5281	//-- export rays piercing this view cell
5282
5283	// take rays stored with the view cells during subdivision
5284	VssRayContainer vcRays;
5285	VssRayContainer collectRays;
5286
5287	// collect initial view cells
5288	ViewCellContainer leaves;
5289	mViewCellsTree->CollectLeaves(vc, leaves);
5290
5291	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5292	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5293	{
5294	BspLeaf vcLeaf = static_cast<BspViewCell >(*vit)->mLeaves[0];
5295	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5296
5297	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5298	{
5299	collectRays.push_back(*rit);
5300	}
5301	}
5302
5303	const int raysOut = min((int)collectRays.size(), maxRays);
5304
5305	// prepare some rays for visualization
5306	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5307	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5308	{
5309	const float p = RandomValue(0.0f, (float)collectRays.size());
5310
5311	if (p < raysOut)
5312	{
5313	vcRays.push_back(*rit);
5314	}
5315	}
5316
5317	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5318	}
5319
5320	////////////////
5321	//-- export view cell geometry
5322
5323	exporter->SetWireframe();
5324
5325	Material m;//= RandomMaterial();
5326	m.mDiffuseColor = RgbColor(0, 1, 0);
5327	exporter->SetForcedMaterial(m);
5328
5329	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5330	exporter->SetFilled();
5331
5332	if (exportPvs)
5333	{
5334	Intersectable::NewMail();
5335	ObjectPvsIterator pit = pvs.GetIterator();
5336
5337	cout << endl;
5338
5339	// output PVS of view cell
5340	while (pit.HasMoreEntries())
5341	{
5342	Intersectable *intersect = pit.Next();
5343
5344	if (!intersect->Mailed())
5345	{
5346	intersect->Mail();
5347
5348	m = RandomMaterial();
5349	exporter->SetForcedMaterial(m);
5350	exporter->ExportIntersectable(intersect);
5351	}
5352	}
5353	cout << endl;
5354	}
5355
5356	DEL_PTR(exporter);
5357	cout << "finished" << endl;
5358	}
5359	}
5360
5361
5362	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
5363	{
5364	Exporter *exporter = Exporter::GetExporter("filter.x3d");
5365
5366	Vector3 bsize = mViewSpaceBox.Size();
5367	const Vector3 viewPoint(mViewSpaceBox.Center());
5368	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
5369	const Vector3 width = Vector3(w);
5370
5371	PrVs testPrVs;
5372
5373	if (exporter)
5374	{
5375	ViewCellContainer viewCells;
5376
5377	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
5378
5379	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
5380
5381	exporter->SetWireframe();
5382
5383	exporter->SetForcedMaterial(RgbColor(1,1,1));
5384	exporter->ExportBox(tbox);
5385
5386	exporter->SetFilled();
5387
5388	exporter->SetForcedMaterial(RgbColor(0,1,0));
5389	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
5390
5391	//exporter->ResetForcedMaterial();
5392	exporter->SetForcedMaterial(RgbColor(0,0,1));
5393	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
5394
5395	exporter->SetForcedMaterial(RgbColor(1,0,0));
5396	exporter->ExportGeometry(objects);
5397
5398	delete exporter;
5399	}
5400	}
5401
5402
5403	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5404	ViewCellContainer &viewCells) const
5405	{
5406	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
5407	}
5408
5409
5410	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
5411	const Vector3 &termination,
5412	ViewCellContainer &viewcells)
5413	{
5414	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
5415	}
5416
5417
5418	bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
5419	const Vector3 &termination,
5420	ViewCell *viewCell)
5421	{
5422	return false;
5423	}
5424
5425
5426	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
5427	{
5428	int numSamples;
5429
5430	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
5431	cout << "samples" << numSamples << endl;
5432
5433	vector<RenderCostSample> samples;
5434
5435	if (!mPreprocessor->GetRenderer())
5436	return;
5437
5438	//start the view point queries
5439	long startTime = GetTime();
5440	cout << "starting sampling of render cost ... ";
5441
5442	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
5443
5444	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
5445
5446
5447	// for each sample:
5448	// find view cells associated with the samples
5449	// store the sample pvs with the pvs associated with the view cell
5450	//
5451	// for each view cell:
5452	// compute difference point sampled pvs - view cell pvs
5453	// export geometry with color coded pvs difference
5454
5455	std::map<ViewCell *, ObjectPvs> sampleMap;
5456
5457	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5458
5459	for (rit = samples.begin(); rit != rit_end; ++ rit)
5460	{
5461	RenderCostSample sample = *rit;
5462
5463	ViewCell *vc = GetViewCell(sample.mPosition);
5464
5465	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5466
5467	if (it == sampleMap.end())
5468	{
5469	sampleMap[vc] = sample.mPvs;
5470	}
5471	else
5472	{
5473	(*it).second.MergeInPlace(sample.mPvs);
5474	}
5475	}
5476
5477	// visualize the view cells
5478	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5479
5480	Material m;//= RandomMaterial();
5481
5482	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5483	{
5484	ViewCell vc = (vit).first;
5485
5486	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5487	const int pvsPtSamples = (*vit).second.GetSize();
5488
5489	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5490	m.mDiffuseColor.b = 1.0f;
5491	//exporter->SetForcedMaterial(m);
5492	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5493
5494	/* // counting the pvss
5495	for (rit = samples.begin(); rit != rit_end; ++ rit)
5496	{
5497	RenderCostSample sample = *rit;
5498	ViewCell *vc = GetViewCell(sample.mPosition);
5499
5500	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5501	Mesh *hMesh = CreateMeshFromBox(box);
5502
5503	DEL_PTR(hMesh);
5504	}
5505	*/
5506	}
5507	}
5508
5509
5510	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5511	ViewCell *vc,
5512	const AxisAlignedBox3 *sceneBox,
5513	const AxisAlignedPlane *clipPlane
5514	) const
5515	{
5516	if (clipPlane)
5517	{
5518	const Plane3 plane = clipPlane->GetPlane();
5519
5520	ViewCellContainer leaves;
5521	mViewCellsTree->CollectLeaves(vc, leaves);
5522	ViewCellContainer::const_iterator it, it_end = leaves.end();
5523
5524	for (it = leaves.begin(); it != it_end; ++ it)
5525	{
5526	BspNodeGeometry geom;
5527	BspNodeGeometry front;
5528	BspNodeGeometry back;
5529
5530	mVspBspTree->ConstructGeometry(*it, geom);
5531
5532	const float eps = 0.0001f;
5533	const int cf = geom.Side(plane, eps);
5534
5535	if (cf == -1)
5536	{
5537	exporter->ExportPolygons(geom.GetPolys());
5538	}
5539	else if (cf == 0)
5540	{
5541	geom.SplitGeometry(front,
5542	back,
5543	plane,
5544	mViewSpaceBox,
5545	eps);
5546
5547	if (back.Valid())
5548	{
5549	exporter->ExportPolygons(back.GetPolys());
5550	}
5551	}
5552	}
5553	}
5554	else
5555	{
5556	// export mesh if available
5557	// TODO: some bug here?
5558	if (1 && vc->GetMesh())
5559	{
5560	exporter->ExportMesh(vc->GetMesh());
5561	}
5562	else
5563	{
5564	BspNodeGeometry geom;
5565	mVspBspTree->ConstructGeometry(vc, geom);
5566	exporter->ExportPolygons(geom.GetPolys());
5567	}
5568	}
5569	}
5570
5571
5572	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5573	{
5574	ViewCellContainer leaves;
5575	mViewCellsTree->CollectLeaves(vc, leaves);
5576
5577	int maxDist = 0;
5578
5579	// compute max height difference
5580	for (int i = 0; i < (int)leaves.size(); ++ i)
5581	{
5582	for (int j = 0; j < (int)leaves.size(); ++ j)
5583	{
5584	BspLeaf leaf = static_cast<BspViewCell >(leaves[i])->mLeaves[0];
5585
5586	if (i != j)
5587	{
5588	BspLeaf leaf2 =static_cast<BspViewCell >(leaves[j])->mLeaves[0];
5589	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5590
5591	if (dist > maxDist)
5592	maxDist = dist;
5593	}
5594	}
5595	}
5596
5597	return maxDist;
5598	}
5599
5600
5601	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5602	{
5603	if (!ViewCellsConstructed())
5604	return NULL;
5605
5606	if (!mViewSpaceBox.IsInside(point))
5607	return NULL;
5608
5609	return mVspBspTree->GetViewCell(point, active);
5610	}
5611
5612
5613	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5614	{
5615	BspNodeGeometry geom;
5616	mVspBspTree->ConstructGeometry(vc, geom);
5617
5618	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5619
5620	IncludeNodeGeomInMesh(geom, *mesh);
5621	mesh->ComputeBoundingBox();
5622
5623	vc->SetMesh(mesh);
5624	}
5625
5626
5627	int VspBspViewCellsManager::CastBeam(Beam &beam)
5628	{
5629	return mVspBspTree->CastBeam(beam);
5630	}
5631
5632
5633	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5634	const bool createMesh)
5635	{
5636	float area = 0;
5637	float volume = 0;
5638
5639	ViewCellContainer leaves;
5640	mViewCellsTree->CollectLeaves(viewCell, leaves);
5641
5642	ViewCellContainer::const_iterator it, it_end = leaves.end();
5643
5644	for (it = leaves.begin(); it != it_end; ++ it)
5645	{
5646	BspNodeGeometry geom;
5647	mVspBspTree->ConstructGeometry(*it, geom);
5648
5649	const float lVol = geom.GetVolume();
5650	const float lArea = geom.GetArea();
5651
5652	area += lArea;
5653	volume += lVol;
5654
5655	if (createMesh)
5656	CreateMesh(*it);
5657	}
5658
5659	viewCell->SetVolume(volume);
5660	viewCell->SetArea(area);
5661	}
5662
5663
5664	void VspBspViewCellsManager::TestSubdivision()
5665	{
5666	ViewCellContainer leaves;
5667	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5668
5669	ViewCellContainer::const_iterator it, it_end = leaves.end();
5670
5671	const float vol = mViewSpaceBox.GetVolume();
5672	float subdivVol = 0;
5673	float newVol = 0;
5674
5675	for (it = leaves.begin(); it != it_end; ++ it)
5676	{
5677	BspNodeGeometry geom;
5678	mVspBspTree->ConstructGeometry(*it, geom);
5679
5680	const float lVol = geom.GetVolume();
5681
5682	newVol += lVol;
5683	subdivVol += (*it)->GetVolume();
5684
5685	float thres = 0.9f;
5686	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5687	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5688	}
5689
5690	Debug << "exact volume: " << vol << endl;
5691	Debug << "subdivision volume: " << subdivVol << endl;
5692	Debug << "new volume: " << newVol << endl;
5693	}
5694
5695
5696	void VspBspViewCellsManager::PrepareLoadedViewCells()
5697	{
5698	// TODO: do I still need this here?
5699	if (0) mVspBspTree->RepairViewCellsLeafLists();
5700	}
5701
5702
5703
5704	/************************************************************************/
5705	/* VspOspViewCellsManager implementation */
5706	/************************************************************************/
5707
5708
5709	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5710	const string &hierarchyType)
5711	: ViewCellsManager(vcTree)
5712	{
5713	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5714	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5715
5716	Debug << "compressing objects: " << mCompressObjects << endl;
5717	cout << "compressing objects: " << mCompressObjects << endl;
5718
5719	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5720
5721	mHierarchyManager->SetViewCellsManager(this);
5722	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5723	}
5724
5725
5726	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5727	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5728	{
5729	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5730	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5731
5732	Debug << "compressing objects: " << mCompressObjects << endl;
5733	cout << "compressing objects: " << mCompressObjects << endl;
5734
5735	mHierarchyManager->SetViewCellsManager(this);
5736	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5737	}
5738
5739
5740	Intersectable *VspOspViewCellsManager::GetIntersectable(const VssRay &ray,
5741	const bool isTermination) const
5742	{
5743	if (mUseKdPvs)
5744	return ViewCellsManager::GetIntersectable(ray, isTermination);
5745	else
5746	return mHierarchyManager->GetIntersectable(ray, isTermination);
5747	}
5748
5749
5750	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5751	{
5752	HierarchyManager *hierarchyManager;
5753
5754	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5755	{
5756	Debug << "hierarchy manager: osp" << endl;
5757	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5758	}
5759	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5760	{
5761	Debug << "hierarchy manager: bvh" << endl;
5762	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5763	}
5764	else // only view space partition
5765	{
5766	Debug << "hierarchy manager: obj" << endl;
5767	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5768	}
5769
5770	return hierarchyManager;
5771	}
5772
5773
5774	VspOspViewCellsManager::~VspOspViewCellsManager()
5775	{
5776	DEL_PTR(mHierarchyManager);
5777	}
5778
5779
5780	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5781	{
5782	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5783	}
5784
5785
5786	void VspOspViewCellsManager::CollectViewCells()
5787	{
5788	// view cells tree constructed
5789	if (!ViewCellsTreeConstructed())
5790	{
5791	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5792	}
5793	else
5794	{ // we can use the view cells tree hierarchy to get the right set
5795	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5796	}
5797	}
5798
5799
5800	bool VspOspViewCellsManager::ViewCellsConstructed() const
5801	{
5802	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5803	}
5804
5805
5806	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5807	{
5808	return new VspViewCell(mesh);
5809	}
5810
5811
5812	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5813	const VssRayContainer &rays)
5814	{
5815	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5816
5817	// skip rest if view cells were already constructed
5818	if (ViewCellsConstructed())
5819	return 0;
5820
5821	int sampleContributions = 0;
5822	VssRayContainer sampleRays;
5823
5824	int limit = min (mInitialSamples, (int)rays.size());
5825
5826	VssRayContainer constructionRays;
5827	VssRayContainer savedRays;
5828
5829	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5830	<< ", actual rays: " << (int)rays.size() << endl;
5831
5832	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5833
5834	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5835	Debug << "saved rays: " << (int)savedRays.size() << endl;
5836
5837	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5838
5839	#if TEST_EVALUATION
5840	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5841	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5842	{
5843	storedRays.push_back(new VssRay((tit)));
5844	}
5845	#endif
5846
5847	/////////////////////////
5848	//-- print satistics for subdivision and view cells
5849
5850	Debug << endl << endl << *mHierarchyManager << endl;
5851
5852	ResetViewCells();
5853	//Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5854
5855	//////////////
5856	//-- recast rest of rays
5857
5858	const long startTime = GetTime();
5859	cout << "Computing remaining ray contributions ... ";
5860
5861	if (SAMPLE_AFTER_SUBDIVISION)
5862	ComputeSampleContributions(savedRays, true, false);
5863
5864	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5865	<< " secs" << endl;
5866
5867	if (0)
5868	{
5869	// real meshes are constructed at this stage
5870	cout << "finalizing view cells ... ";
5871	FinalizeViewCells(true);
5872	cout << "finished" << endl;
5873	}
5874
5875	return sampleContributions;
5876	}
5877
5878
5879	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5880	const VssRayContainer &rays)
5881	{
5882	if (!ViewCellsConstructed())
5883	{
5884	Debug << "post process error: no view cells constructed" << endl;
5885	return 0;
5886	}
5887
5888	// if view cells were already constructed before post processing step
5889	// (e.g., because they were loaded), we are finished
5890	if (mViewCellsFinished)
5891	{
5892	FinalizeViewCells(true);
5893	EvaluateViewCellsStats();
5894
5895	return 0;
5896	}
5897
5898	// check if new view cells turned invalid
5899	int minPvs, maxPvs;
5900
5901	if (0)
5902	{
5903	minPvs = mMinPvsSize;
5904	maxPvs = mMaxPvsSize;
5905	}
5906	else
5907	{
5908	// problem matt: why did I start here from zero?
5909	minPvs = 0;
5910	maxPvs = mMaxPvsSize;
5911	}
5912
5913	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5914	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5915
5916	SetValidity(minPvs, maxPvs);
5917
5918
5919	// area is not up to date, has to be recomputed
5920	mTotalAreaValid = false;
5921	VssRayContainer postProcessRays;
5922	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5923
5924	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5925
5926
5927	// compute tree by merging the nodes of the spatial hierarchy
5928	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5929	mViewCellsTree->SetRoot(root);
5930
5931	//////////////////////////
5932	//-- update pvs up to the root of the hierarchy
5933
5934	ObjectPvs pvs;
5935	UpdatePvsForEvaluation(root, pvs);
5936
5937
5938	//////////////////////
5939	//-- render simulation after merge + refine
5940
5941	cout << "\nview cells partition render time before compress" << endl << endl;
5942	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5943	SimulationStatistics ss;
5944	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5945	cout << ss << endl;
5946
5947
5948	mHierarchyManager->CreateUniqueObjectIds();
5949
5950	///////////
5951	//-- compression
5952
5953	if (0) CompressViewCells();
5954
5955	/////////////
5956	//-- some tasks still to do on the view cells:
5957	//-- Compute meshes from view cell geometry, evaluate volume and / or area
5958
5959	if (1) FinalizeViewCells(true);
5960
5961	return 0;
5962	}
5963
5964
5965	int VspOspViewCellsManager::GetType() const
5966	{
5967	return VSP_OSP;
5968	}
5969
5970
5971	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5972	{
5973	// terminate recursion
5974	if (root->IsLeaf())
5975	{
5976	VspLeaf leaf = static_cast<VspLeaf >(root);
5977	leaf->GetViewCell()->SetMergeCost(0.0f);
5978	return leaf->GetViewCell();
5979	}
5980
5981	VspInterior interior = static_cast<VspInterior >(root);
5982	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5983
5984	// evaluate merge cost for priority traversal
5985	const float mergeCost = -(float)root->mTimeStamp;
5986	viewCellInterior->SetMergeCost(mergeCost);
5987
5988	float volume = 0;
5989
5990	VspNode *front = interior->GetFront();
5991	VspNode *back = interior->GetBack();
5992
5993	ObjectPvs frontPvs, backPvs;
5994
5995	/////////
5996	//-- recursivly compute child hierarchies
5997
5998	ViewCell *backVc = ConstructSpatialMergeTree(back);
5999	ViewCell *frontVc = ConstructSpatialMergeTree(front);
6000
6001	viewCellInterior->SetupChildLink(backVc);
6002	viewCellInterior->SetupChildLink(frontVc);
6003
6004	volume += backVc->GetVolume();
6005	volume += frontVc->GetVolume();
6006
6007	viewCellInterior->SetVolume(volume);
6008
6009	return viewCellInterior;
6010	}
6011
6012
6013	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
6014	{
6015	if (!ViewCellsConstructed())
6016	return ViewCellsManager::GetViewPoint(viewPoint);
6017
6018	// TODO: set reasonable limit
6019	const int limit = 20;
6020
6021	for (int i = 0; i < limit; ++ i)
6022	{
6023	viewPoint = mViewSpaceBox.GetRandomPoint();
6024
6025	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
6026	{
6027	return true;
6028	}
6029	}
6030
6031	Debug << "failed to find valid view point, taking " << viewPoint << endl;
6032	return false;
6033	}
6034
6035
6036	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
6037	ViewCell *vc,
6038	const AxisAlignedBox3 *sceneBox,
6039	const AxisAlignedPlane *clipPlane
6040	) const
6041	{
6042	Plane3 plane;
6043	if (clipPlane)
6044	{
6045	// arbitrary plane definition
6046	plane = clipPlane->GetPlane();
6047	}
6048
6049	ViewCellContainer leaves;
6050	mViewCellsTree->CollectLeaves(vc, leaves);
6051
6052	ViewCellContainer::const_iterator it, it_end = leaves.end();
6053
6054	for (it = leaves.begin(); it != it_end; ++ it)
6055	{
6056	VspViewCell vspVc = static_cast<VspViewCell >(*it);
6057	VspLeaf *l = vspVc->mLeaves[0];
6058
6059	const AxisAlignedBox3 box =
6060	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
6061
6062	if (sceneBox && !Overlap(*sceneBox, box))
6063	continue;
6064
6065	if (clipPlane)
6066	{
6067	if (box.Side(plane) == -1)
6068	{
6069	exporter->ExportBox(box);
6070	}
6071	else if (box.Side(plane) == 0)
6072	{
6073	// intersection
6074	AxisAlignedBox3 fbox, bbox;
6075	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
6076	exporter->ExportBox(bbox);
6077	}
6078	}
6079	else
6080	{
6081	exporter->ExportBox(box);
6082	}
6083	}
6084	}
6085
6086
6087	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
6088	{
6089	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
6090	// validy update in preprocessor for all managers)
6091	return ViewCellsManager::ViewPointValid(viewPoint);
6092
6093	// return mViewSpaceBox.IsInside(viewPoint) &&
6094	// mVspTree->ViewPointValid(viewPoint);
6095	}
6096
6097
6098	float VspOspViewCellsManager::UpdateObjectCosts()
6099	{
6100	float maxRenderCost = 0;
6101
6102	cout << "updating object pvs cost ... ";
6103	const long startTime = GetTime();
6104
6105	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
6106
6107	Intersectable::NewMail();
6108
6109	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
6110
6111	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
6112	{
6113	ViewCell vc = vit;
6114
6115	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
6116
6117	// output PVS of view cell
6118	while (pit.HasMoreEntries())
6119	{
6120	Intersectable *obj = pit.Next();
6121
6122	BvhNode node = static_cast<BvhNode >(obj);
6123
6124	// hack!!
6125	if (!node->IsLeaf())
6126	{
6127	cout << "error, can only process leaves" << endl;
6128	return 0;
6129	}
6130
6131	if (!node->Mailed())
6132	{
6133	node->Mail();
6134	node->mRenderCost = 0;
6135	}
6136
6137	const float rc = (float)((BvhLeaf *)node)->mObjects.size();
6138
6139	node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
6140
6141	if (node->mRenderCost > maxRenderCost)
6142	maxRenderCost = node->mRenderCost;
6143	}
6144	}
6145
6146	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
6147
6148	return maxRenderCost;
6149	}
6150
6151
6152	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
6153	const VssRayContainer &sampleRays)
6154	{
6155	if (!ViewCellsConstructed())
6156	return;
6157
6158	VssRayContainer visRays;
6159	GetRaySets(sampleRays, mVisualizationSamples, visRays);
6160
6161	////////////
6162	//-- export final view cells
6163
6164	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
6165
6166	Vector3 scale(0.9f, 0.9f, 0.9f);
6167	//Vector3 scale(1.0f, 1.0f, 1.0f);
6168
6169	if (exporter)
6170	{
6171	// clamp to a scene boudning box
6172	if (CLAMP_TO_BOX)
6173	exporter->mClampToBox = true;
6174
6175	const long starttime = GetTime();
6176	cout << "exporting final view cells (after initial construction + post process) ... " << endl;
6177
6178	// matt: hack for clamping scene
6179	AxisAlignedBox3 bbox = mViewSpaceBox;
6180	bbox.Scale(scale);
6181
6182	if (1 && mExportRays)
6183	{
6184	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
6185	}
6186
6187	// hack color code
6188	const int savedColorCode = mColorCode;
6189
6190	EvaluateViewCellsStats();
6191	const int colorCode = 0;
6192
6193	const float maxRenderCost = -1;
6194	const bool exportBounds = false;
6195
6196	//cout << "maxRenderCost: " << maxRenderCost << endl;
6197	if (1)
6198	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
6199	objects,
6200	CLAMP_TO_BOX ? &bbox : NULL,
6201	maxRenderCost,
6202	exportBounds);
6203
6204	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6205	ExportViewCellsForViz(exporter, NULL, colorCode, GetClipPlane());
6206
6207	delete exporter;
6208
6209	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6210	}
6211
6212	if (1)
6213	{
6214	exporter = Exporter::GetExporter("final_object_partition.wrl");
6215
6216	if (exporter)
6217	{
6218	if (CLAMP_TO_BOX) exporter->mClampToBox = true;
6219
6220	const long starttime = GetTime();
6221	cout << "exporting final objects (after initial construction + post process) ... ";
6222
6223	// matt: hack for clamping scene
6224	AxisAlignedBox3 bbox = mViewSpaceBox;
6225	bbox.Scale(scale);
6226
6227	// hack color code (show pvs size)
6228	const int savedColorCode = mColorCode;
6229
6230	EvaluateViewCellsStats();
6231	mColorCode = 1; // 0 = random, 1 = export pvs
6232
6233	// don't visualize render cost
6234	const float maxRenderCost = -1;
6235	//const bool exportBounds = true;
6236	const bool exportBounds = false;
6237
6238	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
6239	objects,
6240	CLAMP_TO_BOX ? &bbox : NULL,
6241	maxRenderCost,
6242	exportBounds);
6243
6244
6245	delete exporter;
6246
6247	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6248	mColorCode = savedColorCode;
6249	}
6250	}
6251
6252	// export some view cells
6253	int leafOut;
6254	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
6255
6256	const bool sortViewCells = false;
6257	const bool exportPvs = true;
6258	const bool exportRays = true;
6259	const int raysOut = 100;
6260
6261	ExportSingleViewCells(objects,
6262	leafOut,
6263	sortViewCells,
6264	exportPvs,
6265	exportRays,
6266	raysOut,
6267	"");
6268	}
6269
6270
6271	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
6272	const int maxViewCells,
6273	const bool sortViewCells,
6274	const bool exportPvs,
6275	const bool exportRays,
6276	const int maxRays,
6277	const string &prefix,
6278	VssRayContainer *visRays)
6279	{
6280	if (sortViewCells)
6281	{
6282	// sort view cells to visualize the view cells with highest render cost
6283	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
6284	}
6285
6286	ViewCell::NewMail();
6287	const int limit = min(maxViewCells, (int)mViewCells.size());
6288
6289	cout << "\nExporting " << limit << " single view cells: " << endl;
6290
6291	for (int i = 0; i < limit; ++ i)
6292	{
6293	cout << "creating output for view cell " << i << " ... ";
6294
6295	// largest view cell pvs first of random view cell
6296	ViewCell *vc = sortViewCells ?
6297	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
6298
6299	if (vc->Mailed()) // view cell already processed
6300	continue;
6301
6302	vc->Mail();
6303
6304	ObjectPvs pvs;
6305	mViewCellsTree->GetPvs(vc, pvs);
6306
6307	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
6308	Exporter *exporter = Exporter::GetExporter(s);
6309
6310	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetTrianglesInPvs(vc) << endl;
6311
6312	if (exportPvs)
6313	{
6314	Material m;
6315	Intersectable::NewMail();
6316
6317	ObjectPvsIterator pit = pvs.GetIterator();
6318
6319	// output PVS of view cell
6320	while (pit.HasMoreEntries())
6321	{
6322	Intersectable *intersect = pit.Next();
6323
6324	if (!intersect->Mailed())
6325	{
6326	m = RandomMaterial();
6327	exporter->SetForcedMaterial(m);
6328
6329	exporter->ExportIntersectable(intersect);
6330	intersect->Mail();
6331	}
6332	}
6333	}
6334
6335	if (exportRays)
6336	{
6337	////////////
6338	//-- export the sample rays
6339
6340	// output rays stored with the view cells during subdivision
6341	VssRayContainer vcRays;
6342	VssRayContainer collectRays;
6343
6344	// collect intial view cells
6345	ViewCellContainer leaves;
6346	mViewCellsTree->CollectLeaves(vc, leaves);
6347
6348	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
6349
6350	for (vit = leaves.begin(); vit != vit_end; ++ vit)
6351	{
6352	VspLeaf vcLeaf = static_cast<VspViewCell >(*vit)->mLeaves[0];
6353	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
6354
6355	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
6356	{
6357	collectRays.push_back(*rit);
6358	}
6359	}
6360
6361	const int raysOut = min((int)collectRays.size(), maxRays);
6362
6363	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
6364
6365	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
6366	{
6367	const float p = RandomValue(0.0f, (float)collectRays.size());
6368
6369	if (p < raysOut)
6370	vcRays.push_back(*rit);
6371	}
6372
6373	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
6374	}
6375
6376
6377	/////////////////
6378	//-- export view cell geometry
6379
6380	exporter->SetWireframe();
6381
6382	Material m;
6383	m.mDiffuseColor = RgbColor(0, 1, 0);
6384	exporter->SetForcedMaterial(m);
6385
6386	ExportViewCellGeometry(exporter, vc, NULL, NULL);
6387	exporter->SetFilled();
6388
6389	DEL_PTR(exporter);
6390	cout << "finished" << endl;
6391	}
6392
6393	cout << endl;
6394	}
6395
6396
6397	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
6398	ViewCellContainer &viewCells) const
6399	{
6400	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
6401	}
6402
6403
6404	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
6405	const Vector3 &termination,
6406	ViewCellContainer &viewcells)
6407	{
6408
6409	return mHierarchyManager->CastLineSegment(origin, termination, viewcells);
6410	}
6411
6412
6413	bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
6414	const Vector3 &termination,
6415	ViewCell *viewCell)
6416	{
6417	return false;
6418	}
6419
6420
6421	bool VspOspViewCellsManager::ExportViewCells(const string filename,
6422	const bool exportPvs,
6423	const ObjectContainer &objects)
6424	{
6425	// no view cells were computed
6426	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6427	return false;
6428
6429	if (strstr(filename.c_str(), ".bn"))
6430	{
6431	return ExportViewCellsBinary(filename, exportPvs, objects);
6432	}
6433
6434	//cout << "exporting binary" << endl; string fname("test.vc"); return ExportViewCellsBinary(fname, exportPvs, objects);
6435
6436	const long starttime = GetTime();
6437	cout << "exporting view cells to xml ... ";
6438
6439	OUT_STREAM stream(filename.c_str());
6440
6441	// we need unique ids for each view cell
6442	CreateUniqueViewCellIds();
6443
6444	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6445	stream << "<VisibilitySolution>" << endl;
6446
6447	if (exportPvs)
6448	{
6449	///////////////
6450	//-- export bounding boxes
6451	//-- we need the boxes to identify objects in the target engine
6452
6453	if (mUseKdPvs)
6454	{
6455	stream << "<BoundingBoxes>" << endl;
6456
6457	int id = 0;
6458	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
6459
6460	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
6461	{
6462	Intersectable obj = (kit);
6463	const AxisAlignedBox3 box = obj->GetBox();
6464
6465	// set kd node id
6466	obj->SetId(id);
6467
6468	stream << "<BoundingBox" << " id=\"" << id << "\""
6469	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
6470	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
6471	}
6472
6473	stream << "</BoundingBoxes>" << endl;
6474	}
6475	else
6476	{
6477	mHierarchyManager->ExportBoundingBoxes(stream, objects);
6478	}
6479	}
6480
6481
6482	//////////////////////////
6483	//-- export the view cells and the pvs
6484
6485	const int numViewCells = mCurrentViewCellsStats.viewCells;
6486
6487	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6488	mViewCellsTree->Export(stream, exportPvs);
6489	stream << "</ViewCells>" << endl;
6490
6491
6492	/////////////////
6493	//-- export the view space hierarchy
6494
6495	stream << "<ViewSpaceHierarchy type=\"vsp\""
6496	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6497	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6498
6499	mHierarchyManager->GetVspTree()->Export(stream);
6500	stream << "</ViewSpaceHierarchy>" << endl;
6501
6502	/////////////////
6503	//-- export the object space hierarchy
6504
6505	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6506
6507	stream << "</VisibilitySolution>" << endl;
6508	stream.close();
6509
6510	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6511	return true;
6512	}
6513
6514
6515	bool VspOspViewCellsManager::ExportViewCellsBinary(const string filename,
6516	const bool exportPvs,
6517	const ObjectContainer &objects)
6518	{
6519	// no view cells constructed yet
6520	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6521	return false;
6522
6523	const long starttime = GetTime();
6524	cout << "exporting view cells to binary format ... ";
6525
6526	OUT_STREAM stream(filename.c_str());
6527
6528	// we need unique ids for each view cell
6529	CreateUniqueViewCellIds();
6530
6531	int numBoxes = (int)mPreprocessor->mKdTree->mKdIntersectables.size();
6532	stream.write(reinterpret_cast<char *>(&numBoxes), sizeof(int));
6533
6534
6535	///////////////
6536	//-- export bounding boxes
6537
6538	// we use bounding box intersection to identify pvs objects in the target engine
6539	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
6540
6541	int id = 0;
6542
6543	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
6544	{
6545	Intersectable obj = (kit);
6546	// set the kd node id to identify the kd node as a pvs entry
6547	obj->SetId(id);
6548
6549	const AxisAlignedBox3 &box = obj->GetBox();
6550	Vector3 bmin = box.Min();
6551	Vector3 bmax = box.Max();
6552
6553	stream.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
6554	stream.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
6555	stream.write(reinterpret_cast<char *>(&id), sizeof(int));
6556	}
6557
6558	cout << "written " << numBoxes << " kd nodes" << endl;
6559
6560	///////////////
6561	//-- export the view cells and the pvs
6562
6563	int numViewCells = (int)mViewCells.size();
6564	stream.write(reinterpret_cast<char *>(&numViewCells), sizeof(int));
6565
6566	Vector3 vmin = mViewSpaceBox.Min();
6567	Vector3 vmax = mViewSpaceBox.Max();
6568
6569	stream.write(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
6570	stream.write(reinterpret_cast<char *>(&vmax), sizeof(Vector3));
6571
6572
6573	//////////
6574	//-- export binary view cells
6575
6576	mViewCellsTree->ExportBinary(stream);
6577
6578
6579	/////////
6580	//-- export the view space hierarchy
6581
6582	mHierarchyManager->GetVspTree()->ExportBinary(stream);
6583
6584
6585	////////
6586	//-- export the object space hierarchy
6587
6588	//mHierarchyManager->ExportObjectSpaceHierarchyBinary();
6589
6590	stream.close();
6591
6592	//mHierarchyManager->GetVspTree()->TestOutput("output.txt");
6593
6594	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6595	return true;
6596	}
6597
6598
6599	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6600	const bool active) const
6601	{
6602	if (!ViewCellsConstructed())
6603	return NULL;
6604
6605	if (!mViewSpaceBox.IsInside(point))
6606	return NULL;
6607
6608	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6609	}
6610
6611
6612	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6613	{
6614	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6615
6616	ViewCellContainer leaves;
6617	mViewCellsTree->CollectLeaves(vc, leaves);
6618
6619	ViewCellContainer::const_iterator it, it_end = leaves.end();
6620
6621	for (it = leaves.begin(); it != it_end; ++ it)
6622	{
6623	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6624	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6625	IncludeBoxInMesh(box, *mesh);
6626	}
6627
6628	mesh->ComputeBoundingBox();
6629
6630	vc->SetMesh(mesh);
6631	}
6632
6633
6634	int VspOspViewCellsManager::CastBeam(Beam &beam)
6635	{
6636	// matt: TODO
6637	return 0;
6638	}
6639
6640
6641	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6642	{
6643	float area = 0;
6644	float volume = 0;
6645
6646	ViewCellContainer leaves;
6647	mViewCellsTree->CollectLeaves(viewCell, leaves);
6648
6649	ViewCellContainer::const_iterator it, it_end = leaves.end();
6650
6651	for (it = leaves.begin(); it != it_end; ++ it)
6652	{
6653	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6654
6655	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6656
6657	const float lVol = box.GetVolume();
6658	const float lArea = box.SurfaceArea();
6659
6660	area += lArea;
6661	volume += lVol;
6662
6663	CreateMesh(*it);
6664	}
6665
6666	viewCell->SetVolume(volume);
6667	viewCell->SetArea(area);
6668	}
6669
6670
6671	void VspOspViewCellsManager::PrepareLoadedViewCells()
6672	{
6673	// TODO
6674	}
6675
6676
6677	void VspOspViewCellsManager::PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6678	{
6679	const float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6680
6681	float fullmem = mem +
6682	(hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6683	hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6684
6685	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6686	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6687	}
6688
6689
6690	void VspOspViewCellsManager::CompressViewCells()
6691	{
6692	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6693	return;
6694
6695
6696	////////////
6697	//-- compression
6698
6699	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6700
6701	cout << "before compression: " << endl;
6702	Debug << "before compression: " << endl;
6703
6704	PrintCompressionStats(mHierarchyManager, pvsEntries);
6705
6706	if (mCompressObjects)
6707	{
6708	cout << "compressing in the objects: " << endl;
6709	Debug << "compressing in the objects: " << endl;
6710
6711	pvsEntries = mHierarchyManager->CompressObjectSpace();
6712	}
6713	else
6714	{
6715	cout << "compressing in the view space: " << endl;
6716	Debug << "compressing in the view space: " << endl;
6717
6718	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6719	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6720	}
6721
6722	PrintCompressionStats(mHierarchyManager, pvsEntries);
6723	}
6724
6725
6726	void VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box,
6727	ObjectContainer &objects)
6728	{
6729	mHierarchyManager->CollectObjects(box, objects);
6730	}
6731
6732
6733	void VspOspViewCellsManager::EvalViewCellPartition()
6734	{
6735	int samplesPerPass;
6736	int castSamples = 0;
6737	int oldSamples = 0;
6738	int samplesForStats;
6739	char statsPrefix[100];
6740	char suffix[100];
6741	int splitsStepSize;
6742
6743	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6744	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6745	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", mEvaluationSamples);
6746	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6747	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6748
6749	bool useHisto;
6750	int histoMem;
6751
6752	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6753	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6754
6755	Debug << "step size: " << splitsStepSize << endl;
6756	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6757	Debug << "view cell evaluation samples: " << mEvaluationSamples << endl;
6758	Debug << "view cell stats prefix: " << statsPrefix << endl;
6759
6760	cout << "reseting pvs ... ";
6761
6762	// reset pvs and start over from zero
6763	mViewCellsTree->ResetPvs();
6764
6765	cout << "finished" << endl;
6766	cout << "Evaluating view cell partition ... " << endl;
6767
6768	int pass = 0;
6769
6770	while (castSamples < mEvaluationSamples)
6771	{
6772	///////////////
6773	//-- we have to use uniform sampling strategy for construction rays
6774
6775	VssRayContainer evaluationSamples;
6776	const int samplingType = mEvaluationSamplingType;
6777
6778	long startTime = GetTime();
6779	Real timeDiff;
6780
6781	cout << "casting " << samplesPerPass << " samples ... ";
6782	Debug << "casting " << samplesPerPass << " samples ... ";
6783
6784	// use mixed distributions
6785	CastEvaluationSamples(samplesPerPass, evaluationSamples);
6786
6787	timeDiff = TimeDiff(startTime, GetTime());
6788	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6789	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6790
6791	// don't computed sample contributions
6792	// because already accounted for inside the mixture distribution!
6793
6794	castSamples += samplesPerPass;
6795
6796	if ((castSamples >= samplesForStats + oldSamples) \|\|
6797	(castSamples >= mEvaluationSamples))
6798	{
6799	oldSamples += samplesForStats;
6800
6801	///////////
6802	//-- output stats
6803
6804	sprintf(suffix, "-%09d-eval.log", castSamples);
6805	const string filename = string(statsPrefix) + string(suffix);
6806
6807	startTime = GetTime();
6808
6809	cout << "compute new statistics ... " << endl;
6810
6811	ofstream ofstr(filename.c_str());
6812	mHierarchyManager->EvaluateSubdivision(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6813
6814	timeDiff = TimeDiff(startTime, GetTime());
6815	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6816	cout << "*************************************" << endl;
6817
6818	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6819
6820	++ pass;
6821	}
6822
6823	disposeRays(evaluationSamples, NULL);
6824	}
6825
6826	////////////
6827	//-- histogram
6828
6829	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
6830	int histoStepSize;
6831
6832	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6833	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
6834
6835	if (useHisto)
6836	{
6837	// evaluate view cells in a histogram
6838	char str[64];
6839
6840	// hack: just show final view cells
6841	const int pass = (int)mViewCells.size();
6842
6843	//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
6844
6845	string filename;
6846
6847	cout << "computing histogram for " << pass << " view cells" << endl;
6848
6849	///////////////////
6850	//-- evaluate histogram for pvs size
6851
6852	cout << "computing pvs histogram for " << pass << " view cells" << endl;
6853
6854	sprintf(str, "-%09d-histo-pvs2.log", pass);
6855	filename = string(statsPrefix) + string(str);
6856
6857	EvalViewCellHistogramForPvsSize(filename, pass);
6858	}
6859	}
6860
6861
6862	void VspOspViewCellsManager::FinalizeViewCells(const bool createMesh)
6863	{
6864	ViewCellsManager::FinalizeViewCells(createMesh);
6865
6866	if (mHierarchyManager->mUseTraversalTree)
6867	{ // create a traversal tree for optimal view cell casting
6868	mHierarchyManager->CreateTraversalTree();
6869	}
6870	}
6871
6872
6873	#if TEST_PACKETS
6874
6875	float VspOspViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
6876	const bool addContributions,
6877	const bool storeViewCells,
6878	const bool useHitObjects)
6879	{
6880	if (!ViewCellsConstructed())
6881	return 0;
6882
6883	float sum = 0.0f;
6884	VssRayContainer::const_iterator it, it_end = rays.end();
6885
6886	VssRayContainer tmpRays;
6887
6888	for (it = rays.begin(); it != it_end; ++ it)
6889	{
6890	sum += ComputeSampleContribution((it), addContributions, storeViewCells, useHitObjects);
6891
6892	tmpRays.push_back(new VssRay((it)));
6893
6894	if (tmpRays.size() == 4)
6895	{
6896	// cast packets of 4 rays
6897	RayPacket packet(tmpRays);
6898	mHierarchyManager->CastLineSegment(packet);
6899
6900	for (int i = 0; i < 4; ++ i)
6901	{
6902	ComputeSampleContribution(*tmpRays[i], addContributions, true, useHitObjects);
6903	// compare results
6904	cout << "ray " << i << ": " << (int)tmpRays[i]->mViewCells.size() << " "
6905	<< (int)packet.mViewCells[i].size() << endl;
6906	}
6907
6908	CLEAR_CONTAINER(tmpRays);
6909	}
6910	}
6911
6912	CLEAR_CONTAINER(tmpRays);
6913
6914	#ifdef USE_PERFTIMER
6915	cout << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
6916	Debug << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
6917	cout << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
6918	Debug << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
6919	#endif
6920
6921	return sum;
6922	}
6923
6924	#endif
6925
6926
6927	ViewCellsManager *
6928	ViewCellsManager::LoadViewCellsBinary(const string &filename,
6929	ObjectContainer &pvsObjects,
6930	bool finalizeViewCells,
6931	BoundingBoxConverter *bconverter)
6932	{
6933	IN_STREAM stream(filename.c_str());
6934
6935	if (!stream.is_open())
6936	{
6937	Debug << "View cells loading failed: could not open file" << endl;
6938	return NULL;
6939	}
6940
6941	Debug << "loading boxes" << endl;
6942
6943	const long startTime = GetTime();
6944
6945	// load all the bounding boxes
6946	IndexedBoundingBoxContainer iboxes;
6947	ViewCellsManager::LoadIndexedBoundingBoxesBinary(stream, iboxes);
6948
6949	pvsObjects.reserve(iboxes.size());
6950
6951	if (bconverter)
6952	{
6953	// associate object ids with bounding boxes
6954	bconverter->IdentifyObjects(iboxes, pvsObjects);
6955	}
6956
6957
6958	ObjectContainer pvsLookup;
6959	pvsLookup.resize(iboxes.size());
6960
6961	for (size_t i = 0; i < pvsLookup.size(); ++ i)
6962	{
6963	pvsLookup[i] = NULL;
6964	}
6965
6966	for (size_t i = 0; i < pvsObjects.size(); ++ i)
6967	{
6968	pvsLookup[pvsObjects[i]->GetId()] = pvsObjects[i];
6969	}
6970
6971
6972	/////////////
6973	//-- load the view cells
6974
6975	int numViewCells;
6976	stream.read(reinterpret_cast<char *>(&numViewCells), sizeof(int));
6977
6978	Debug << "loading " << numViewCells << " view cells " << endl;
6979
6980	Vector3 vmin, vmax;
6981
6982	stream.read(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
6983	stream.read(reinterpret_cast<char *>(&vmax), sizeof(Vector3));
6984
6985	AxisAlignedBox3 viewSpaceBox(vmin, vmax);
6986
6987	Debug << "view space box: " << viewSpaceBox << endl;
6988
6989	ViewCellsTree *vcTree = new ViewCellsTree();
6990
6991	if (!vcTree->ImportBinary(stream, pvsLookup))
6992	{
6993	Debug << "Error: loading view cells tree failed!" << endl;
6994	delete vcTree;
6995
6996	return NULL;
6997	}
6998
6999	Debug << "loading the view space partition tree" << endl;
7000	VspTree *vspTree = new VspTree(viewSpaceBox);
7001
7002	if (!vspTree->ImportBinary(stream))
7003	{
7004	Debug << "Error: loading vsp tree failed!" << endl;
7005	delete vcTree; delete vspTree;
7006
7007	return NULL;
7008	}
7009
7010
7011	HierarchyManager * hm =
7012	new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
7013
7014	hm->SetVspTree(vspTree);
7015
7016
7017	/////////
7018	//-- create view cells manager
7019
7020	VspOspViewCellsManager *vm = new VspOspViewCellsManager(vcTree, hm);
7021
7022
7023	//////////////
7024	//-- do some more preparation
7025
7026	vm->mViewSpaceBox = viewSpaceBox;
7027	vm->mViewCells.clear();
7028
7029	ViewCellContainer viewCells;
7030	vcTree->CollectLeaves(vcTree->GetRoot(), viewCells);
7031
7032	ViewCellContainer::const_iterator cit, cit_end = viewCells.end();
7033
7034	for (cit = viewCells.begin(); cit != cit_end; ++ cit)
7035	{
7036	vm->mViewCells.push_back(*cit);
7037	}
7038
7039
7040	//////////////
7041	//-- associate view cells with vsp leaves
7042
7043	vector<VspLeaf *> vspLeaves;
7044	vspTree->CollectLeaves(vspLeaves);
7045
7046	vector<VspLeaf *>::const_iterator vit, vit_end = vspLeaves.end();
7047	cit = viewCells.begin();
7048
7049	for (vit = vspLeaves.begin(); vit != vit_end; ++ vit, ++ cit)
7050	{
7051	VspLeaf leaf = vit;
7052	VspViewCell vc = static_cast<VspViewCell >(*cit);
7053
7054	leaf->SetViewCell(vc);
7055	vc->mLeaves.push_back(leaf);
7056	}
7057
7058
7059	/*for (cit = viewCells.begin(); cit != cit_end; ++ cit)
7060	{
7061	Debug << "pvssize: " << (*cit)->GetPvs().GetSize();
7062	}*/
7063
7064
7065	vm->mViewCellsFinished = true;
7066	vm->mMaxPvsSize = (int)pvsObjects.size();
7067
7068	if (finalizeViewCells)
7069	{
7070	// create the meshes and compute view cell volumes
7071	const bool createMeshes = true;
7072	vm->FinalizeViewCells(createMeshes);
7073	}
7074
7075	Debug << (int)vm->mViewCells.size() << " view cells loaded in "
7076	<< TimeDiff(startTime, GetTime()) * 1e-6f << " secs" << endl;
7077
7078	//vspTree->TestOutput("input.txt");
7079
7080	return vm;
7081	}
7082
7083
7084	ViewCellPointsList *ViewCellsManager::GetViewCellPointsList()
7085	{
7086	return mRandomViewCellsHandler->GetViewCellPointsList();
7087	}
7088
7089
7090	bool ViewCellsManager::ExportRandomViewCells(const string &filename)
7091	{
7092	// export ten view cells with 100 random view points inside each
7093	const int numViewCells = 100;
7094	const int numViewPoints = 10;
7095
7096	//cout << "exporting random view cells" << endl;
7097	return mRandomViewCellsHandler->ExportRandomViewCells(filename);
7098	}
7099
7100
7101	bool ViewCellsManager::ImportViewCellsList(const string &filename)
7102	{
7103	return mRandomViewCellsHandler->ImportViewCellsList(filename);
7104	}
7105
7106
7107	}

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

Download in other formats: