Context Navigation

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

Revision 2601, 179.2 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: