Context Navigation

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

Revision 2659, 180.3 KB checked in by mattausch, 16 years ago (diff)

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

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

Download in other formats: