Context Navigation

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

Revision 2710, 180.7 KB checked in by mattausch, 16 years ago (diff)

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

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

Download in other formats: