Context Navigation

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

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

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

Download in other formats: