Context Navigation

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

Revision 2726, 180.6 KB checked in by mattausch, 16 years ago (diff)
worked on gvs efficiency

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

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

Download in other formats: