Context Navigation

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

Revision 2606, 179.5 KB checked in by bittner, 17 years ago (diff)
merge on nemo

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	// if (vssRay->mTerminationObject == NULL)
2496	// cerr<<"Error NULL termination object!"<<endl;
2497	vssRay->mTerminationObject = GetIntersectable(*vssRay, true);
2498	#if 0
2499	if (vssRay->mTerminationObject == NULL) {
2500	cerr<<"Error in DeterminePvsObjects - termination object maps to NULL!"<<endl;
2501	}
2502	#endif
2503	}
2504	}
2505
2506	}
2507
2508
2509	float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2510	const bool addRays,
2511	ViewCell *currentViewCell,
2512	const bool useHitObjects)
2513	{
2514	ray.mPvsContribution = 0;
2515	ray.mRelativePvsContribution = 0.0f;
2516
2517	if (!ray.mTerminationObject)
2518	return 0.0f;
2519
2520	// optain pvs entry (can be different from hit object)
2521	Intersectable *terminationObj;
2522
2523	terminationObj = ray.mTerminationObject;
2524	//cout << "rayd: " << ray.GetDir() << " ";
2525	ComputeViewCellContribution(currentViewCell,
2526	ray,
2527	terminationObj,
2528	ray.mTermination,
2529	addRays);
2530
2531	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2532	float c = 0.0f;
2533	if (terminationObj)
2534	c = ray.Length();
2535
2536	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2537	return c;
2538	#else
2539	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2540	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2541	#endif
2542	}
2543
2544
2545	float
2546	ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2547	const bool addRays,
2548	const bool storeViewCells,
2549	const bool useHitObjects)
2550	{
2551	ray.mPvsContribution = 0;
2552	ray.mRelativePvsContribution = 0.0f;
2553
2554	++ mSamplesStat.mRays;
2555
2556	#if MYSTATS
2557	mSamplesStat.mRayLengths += ray.Length();
2558	#endif
2559	if (!ray.mTerminationObject)
2560	return 0.0f;
2561
2562	static Ray hray;
2563	hray.Init(ray);
2564
2565	float tmin = 0, tmax = 1.0;
2566
2567	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
2568	{
2569	// cerr<<"ray outside view space box\n";
2570	return 0;
2571	}
2572
2573	Vector3 origin = hray.Extrap(tmin);
2574	Vector3 termination = hray.Extrap(tmax);
2575
2576	ViewCell::NewMail();
2577
2578	#ifdef USE_PERFTIMER
2579	viewCellCastTimer.Entry();
2580	#endif
2581	static ViewCellContainer viewCells;
2582	static VssRay *lastVssRay = NULL;
2583
2584	// check if last ray was not same ray with reverse direction
2585	if (1)
2586	// tmp matt: don't use when origin objects are not accounted for, currently the second ray is lost!!
2587	//!lastVssRay \|\|
2588	//!(ray.mOrigin == lastVssRay->mTermination) \|\|
2589	//!(ray.mTermination == lastVssRay->mOrigin))
2590	{
2591	viewCells.clear();
2592
2593	// traverse the view space subdivision
2594	CastLineSegment(origin, termination, viewCells);
2595
2596	lastVssRay = &ray;
2597	}
2598
2599	#ifdef USE_PERFTIMER
2600	viewCellCastTimer.Exit();
2601	#endif
2602
2603	mSamplesStat.mViewCells += (int)viewCells.size();
2604
2605	if (storeViewCells)
2606	{
2607	// cerr << "Store viewcells should not be used in the test!" << endl;
2608	// copy viewcells memory efficiently
2609	#if VSS_STORE_VIEWCELLS
2610	ray.mViewCells.reserve(viewCells.size());
2611	ray.mViewCells = viewCells;
2612	#else
2613	cerr << "Vss store viewcells not supported." << endl;
2614	exit(1);
2615	#endif
2616	}
2617
2618	Intersectable *terminationObj;
2619
2620	#ifdef USE_PERFTIMER
2621	objTimer.Entry();
2622	#endif
2623	// obtain pvs entry (can be different from hit object)
2624	terminationObj = ray.mTerminationObject;
2625
2626	#ifdef USE_PERFTIMER
2627	objTimer.Exit();
2628
2629	pvsTimer.Entry();
2630	#endif
2631
2632	bool contri = false;
2633	ViewCellContainer::const_iterator it = viewCells.begin();
2634	//cout << "rayd: " << ray.GetDir() << " ";
2635	for (; it != viewCells.end(); ++ it)
2636	{
2637	if (ComputeViewCellContribution(*it,
2638	ray,
2639	terminationObj,
2640	ray.mTermination,
2641	addRays))
2642	{
2643	contri = true;
2644	}
2645
2646	(*it)->IncNumPiercingRays();
2647
2648	}
2649
2650	#if MYSTATS
2651	if (contri)
2652	{
2653	if (rand() < (RAND_MAX / 10))
2654	// cout << "rayd: " /<< ray.GetOrigin() << " " << ray.GetTermination() << " "/ << Normalize(ray.GetDir()) << " " << endl;
2655	mVizBuffer.AddRay(&ray);
2656	}
2657	#endif
2658	#ifdef USE_PERFTIMER
2659	pvsTimer.Exit();
2660	#endif
2661
2662	mSamplesStat.mPvsContributions += ray.mPvsContribution;
2663	if (ray.mPvsContribution)
2664	++ mSamplesStat.mContributingRays;
2665
2666	#if AVG_RAY_CONTRIBUTIONS
2667	ray.mRelativePvsContribution /= (float)viewCells.size();
2668	#endif
2669
2670	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2671	float c = 0.0f;
2672	if (terminationObj)
2673	c = ray.Length();
2674	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2675	return c;
2676	#else
2677	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2678	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2679	#endif
2680	}
2681
2682
2683	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
2684	const int maxSize,
2685	VssRayContainer &usedRays,
2686	VssRayContainer *savedRays) const
2687	{
2688	const int limit = min(maxSize, (int)sourceRays.size());
2689	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
2690
2691	VssRayContainer::const_iterator it, it_end = sourceRays.end();
2692	for (it = sourceRays.begin(); it != it_end; ++ it)
2693	{
2694	if (Random(1.0f) < prop)
2695	usedRays.push_back(*it);
2696	else if (savedRays)
2697	savedRays->push_back(*it);
2698	}
2699	}
2700
2701
2702	float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
2703	{
2704	return (float)mViewCellsTree->GetTrianglesInPvs(viewCell);
2705	}
2706
2707
2708	float ViewCellsManager::GetAccVcArea()
2709	{
2710	// if already computed
2711	if (mTotalAreaValid)
2712	{
2713	return mTotalArea;
2714	}
2715
2716	mTotalArea = 0;
2717	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2718
2719	for (it = mViewCells.begin(); it != it_end; ++ it)
2720	{
2721	//Debug << "area: " << GetArea(*it);
2722	mTotalArea += GetArea(*it);
2723	}
2724
2725	mTotalAreaValid = true;
2726
2727	return mTotalArea;
2728	}
2729
2730
2731	void ViewCellsManager::PrintStatistics(ostream &s) const
2732	{
2733	s << mCurrentViewCellsStats << endl;
2734	}
2735
2736
2737	void ViewCellsManager::CreateUniqueViewCellIds()
2738	{
2739	if (ViewCellsTreeConstructed())
2740	{
2741	mViewCellsTree->CreateUniqueViewCellsIds();
2742	}
2743	else // no view cells tree, handle view cells "myself"
2744	{
2745	int i = 0;
2746	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2747	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2748	{
2749	if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2750	{
2751	mViewCells[i]->SetId(i ++);
2752	}
2753	}
2754	}
2755	}
2756
2757
2758	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2759	const AxisAlignedBox3 *sceneBox,
2760	const bool colorCode,
2761	const AxisAlignedPlane *clipPlane
2762	) const
2763	{
2764	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2765
2766	for (it = mViewCells.begin(); it != it_end; ++ it)
2767	{
2768	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
2769	{
2770	ExportColor(exporter, *it, colorCode);
2771	ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2772	}
2773	}
2774	}
2775
2776
2777	void ViewCellsManager::CreateViewCellMeshes()
2778	{
2779	// convert to meshes
2780	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2781
2782	for (it = mViewCells.begin(); it != it_end; ++ it)
2783	{
2784	if (!(*it)->GetMesh())
2785	{
2786	CreateMesh(*it);
2787	}
2788	}
2789	}
2790
2791
2792	bool ViewCellsManager::ExportViewCells(const string filename,
2793	const bool exportPvs,
2794	const ObjectContainer &objects)
2795	{
2796	return false;
2797	}
2798
2799
2800	void ViewCellsManager::CollectViewCells(const int n)
2801	{
2802	mNumActiveViewCells = n;
2803	mViewCells.clear();
2804	// implemented in subclasses
2805	CollectViewCells();
2806	}
2807
2808
2809	void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
2810	{
2811	ViewCellContainer leaves;
2812	// sets the pointers to the currently active view cells
2813	mViewCellsTree->CollectLeaves(vc, leaves);
2814
2815	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2816	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2817	{
2818	static_cast<ViewCellLeaf >(lit)->SetActiveViewCell(vc);
2819	}
2820	}
2821
2822
2823	void ViewCellsManager::SetViewCellsActive()
2824	{
2825	// collect leaf view cells and set the pointers to
2826	// the currently active view cells
2827	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2828
2829	for (it = mViewCells.begin(); it != it_end; ++ it)
2830	{
2831	SetViewCellActive(*it);
2832	}
2833	}
2834
2835
2836	int ViewCellsManager::GetMaxFilterSize() const
2837	{
2838	return mMaxFilterSize;
2839	}
2840
2841
2842	static const bool USE_ASCII = true;
2843
2844
2845	bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2846	const ObjectContainer &objects) const
2847	{
2848	ObjectContainer::const_iterator it, it_end = objects.end();
2849
2850	if (USE_ASCII)
2851	{
2852	ofstream boxesOut(filename.c_str());
2853	if (!boxesOut.is_open())
2854	return false;
2855
2856	for (it = objects.begin(); it != it_end; ++ it)
2857	{
2858	MeshInstance mi = static_cast<MeshInstance >(*it);
2859	const AxisAlignedBox3 box = mi->GetBox();
2860
2861	boxesOut << mi->GetId() << " "
2862	<< box.Min().x << " "
2863	<< box.Min().y << " "
2864	<< box.Min().z << " "
2865	<< box.Max().x << " "
2866	<< box.Max().y << " "
2867	<< box.Max().z << endl;
2868	}
2869
2870	boxesOut.close();
2871	}
2872	else
2873	{
2874	ofstream boxesOut(filename.c_str(), ios::binary);
2875
2876	if (!boxesOut.is_open())
2877	return false;
2878
2879	for (it = objects.begin(); it != it_end; ++ it)
2880	{
2881	MeshInstance mi = static_cast<MeshInstance >(*it);
2882	const AxisAlignedBox3 box = mi->GetBox();
2883
2884	Vector3 bmin = box.Min();
2885	Vector3 bmax = box.Max();
2886
2887	int id = mi->GetId();
2888
2889	boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2890	boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2891	boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2892	}
2893
2894	boxesOut.close();
2895	}
2896
2897	return true;
2898	}
2899
2900
2901	bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2902	IndexedBoundingBoxContainer &boxes) const
2903	{
2904	Vector3 bmin, bmax;
2905	int id;
2906
2907	if (USE_ASCII)
2908	{
2909	ifstream boxesIn(filename.c_str());
2910
2911	if (!boxesIn.is_open())
2912	{
2913	cout << "failed to open file " << filename << endl;
2914	return false;
2915	}
2916
2917	string buf;
2918	while (!(getline(boxesIn, buf)).eof())
2919	{
2920	sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
2921	&id, &bmin.x, &bmin.y, &bmin.z,
2922	&bmax.x, &bmax.y, &bmax.z);
2923
2924	AxisAlignedBox3 box(bmin, bmax);
2925	// MeshInstance *mi = new MeshInstance();
2926	// HACK: set bounding box to new box
2927	//mi->mBox = box;
2928
2929	boxes.push_back(IndexedBoundingBox(id, box));
2930	}
2931
2932	boxesIn.close();
2933	}
2934	else
2935	{
2936	ifstream boxesIn(filename.c_str(), ios::binary);
2937
2938	if (!boxesIn.is_open())
2939	return false;
2940
2941	while (1)
2942	{
2943	boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
2944	boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2945	boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2946
2947	if (boxesIn.eof())
2948	break;
2949
2950	AxisAlignedBox3 box(bmin, bmax);
2951	MeshInstance *mi = new MeshInstance(NULL);
2952
2953	boxes.push_back(IndexedBoundingBox(id, box));
2954	}
2955
2956	boxesIn.close();
2957	}
2958
2959	return true;
2960	}
2961
2962
2963	float ViewCellsManager::GetFilterWidth()
2964	{
2965	return mFilterWidth;
2966	}
2967
2968
2969	float ViewCellsManager::GetAbsFilterWidth()
2970	{
2971	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
2972	}
2973
2974
2975	void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
2976	const float pvsCost,
2977	const int entriesInPvs) const
2978	{
2979	vc->mPvsCost = pvsCost;
2980	vc->mEntriesInPvs = entriesInPvs;
2981
2982	vc->mPvsSizeValid = true;
2983	}
2984
2985
2986	void ViewCellsManager::UpdateScalarPvsCost(ViewCell *vc, const float pvsCost) const
2987	{
2988	vc->mPvsCost = pvsCost;
2989	}
2990
2991
2992	void
2993	ViewCellsManager::ApplyFilter(ViewCell *viewCell,
2994	KdTree *kdTree,
2995	const float viewSpaceFilterSize,
2996	const float spatialFilterSize,
2997	ObjectPvs &pvs
2998	)
2999	{
3000	// extend the pvs of the viewcell by pvs of its neighbors
3001	// and apply spatial filter by including all neighbors of the objects
3002	// in the pvs
3003
3004	// get all viewcells intersecting the viewSpaceFilterBox
3005	// and compute the pvs union
3006
3007	//Vector3 center = viewCell->GetBox().Center();
3008	// Vector3 center = m->mBox.Center();
3009
3010	// AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
3011	// center + Vector3(viewSpaceFilterSize/2));
3012	if (!ViewCellsConstructed())
3013	return;
3014
3015	if (viewSpaceFilterSize >= 0.0f)
3016	{
3017	const bool usePrVS = false;
3018
3019	if (!usePrVS)
3020	{
3021	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3022	box.Enlarge(Vector3(viewSpaceFilterSize/2));
3023
3024	ViewCellContainer viewCells;
3025	ComputeBoxIntersections(box, viewCells);
3026
3027	// cout<<"box="<<box<<endl;
3028	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3029
3030	for (; it != it_end; ++ it)
3031	{
3032	ObjectPvs interPvs;
3033	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3034	ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
3035
3036	pvs = interPvs;
3037	}
3038	}
3039	else
3040	{
3041	PrVs prvs;
3042	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3043
3044	// mViewCellsManager->SetMaxFilterSize(1);
3045	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
3046	pvs = prvs.mViewCell->GetPvs();
3047	DeleteLocalMergeTree(prvs.mViewCell);
3048	}
3049	}
3050	else
3051	{
3052	pvs = viewCell->GetPvs();
3053	}
3054
3055	if (spatialFilterSize >=0.0f)
3056	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
3057
3058	}
3059
3060
3061
3062	void
3063	ViewCellsManager::ApplyFilter(KdTree *kdTree,
3064	const float relViewSpaceFilterSize,
3065	const float relSpatialFilterSize
3066	)
3067	{
3068
3069	if (!ViewCellsConstructed())
3070	return;
3071
3072	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3073
3074	ObjectPvs *newPvs;
3075	newPvs = new ObjectPvs[mViewCells.size()];
3076
3077	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
3078	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
3079
3080	int i;
3081	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3082	ApplyFilter(*it,
3083	kdTree,
3084	viewSpaceFilterSize,
3085	spatialFilterSize,
3086	newPvs[i]
3087	);
3088	}
3089
3090	// now replace all pvss
3091	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3092
3093	ObjectPvs &pvs = (*it)->GetPvs();
3094	pvs.Clear();
3095	pvs = newPvs[i];
3096	newPvs[i].Clear();
3097	}
3098
3099	delete [] newPvs;
3100	}
3101
3102
3103	void
3104	ViewCellsManager::ApplySpatialFilter(
3105	KdTree *kdTree,
3106	const float spatialFilterSize,
3107	ObjectPvs &pvs
3108	)
3109	{
3110	// now compute a new Pvs by including also objects intersecting the
3111	// extended boxes of visible objects
3112	Intersectable::NewMail();
3113
3114	ObjectPvsIterator pit = pvs.GetIterator();
3115
3116	while (pit.HasMoreEntries())
3117	pit.Next()->Mail();
3118
3119	ObjectPvs nPvs;
3120	int nPvsSize = 0;
3121
3122	ObjectPvsIterator pit2 = pvs.GetIterator();
3123
3124	while (pit2.HasMoreEntries())
3125	{
3126	// now go through the pvs again
3127	Intersectable *object = pit2.Next();
3128
3129	// Vector3 center = object->GetBox().Center();
3130	// AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
3131	// center + Vector3(spatialFilterSize/2));
3132
3133	AxisAlignedBox3 box = object->GetBox();
3134	box.Enlarge(Vector3(spatialFilterSize/2));
3135
3136	ObjectContainer objects;
3137
3138	// $$ warning collect objects takes only unmailed ones!
3139	kdTree->CollectObjects(box, objects);
3140	// cout<<"collected objects="<<objects.size()<<endl;
3141	ObjectContainer::const_iterator noi = objects.begin();
3142	for (; noi != objects.end(); ++ noi)
3143	{
3144	Intersectable o = noi;
3145	cout<<"w";
3146	// $$ JB warning: pdfs are not correct at this point!
3147	nPvs.AddSample(o, Limits::Small);
3148	nPvsSize ++;
3149	}
3150	}
3151
3152	// cout<<"nPvs size = "<<nPvsSize<<endl;
3153	pvs.MergeInPlace(nPvs);
3154	}
3155
3156
3157	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3158	const ViewCellContainer &viewCells) const
3159	{
3160	MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
3161	}
3162
3163
3164	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3165	const ViewCellContainer &viewCells,
3166	const int leftIdx,
3167	const int rightIdx) const
3168	{
3169	if (leftIdx == rightIdx)
3170	{
3171	pvs = viewCells[leftIdx]->GetPvs();
3172	}
3173	else
3174	{
3175	const int midSplit = (leftIdx + rightIdx) / 2;
3176
3177	ObjectPvs leftPvs, rightPvs;
3178	MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
3179	MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);
3180
3181	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
3182	}
3183	}
3184
3185
3186	PvsFilterStatistics
3187	ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
3188	const bool useViewSpaceFilter,
3189	const float filterSize,
3190	ObjectPvs &pvs,
3191	vector<AxisAlignedBox3> *filteredBoxes,
3192	const bool onlyNewObjects
3193	)
3194	{
3195	pvs.Reserve(viewCell->GetFilteredPvsSize());
3196
3197	PvsFilterStatistics stats;
3198
3199	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
3200	const Vector3 center = vbox.Center();
3201
3202	// copy the PVS
3203	if (!mUseKdPvs)
3204	Intersectable::NewMail();
3205	else
3206	KdNode::NewMail();
3207
3208	ObjectPvs basePvs = viewCell->GetPvs();
3209	ObjectPvsIterator pit = basePvs.GetIterator();
3210
3211	if (!mUseKdPvs)
3212	{
3213	// first mark all objects from this pvs
3214	while (pit.HasMoreEntries())
3215	pit.Next()->Mail();
3216	}
3217
3218	int pvsSize = 0;
3219	int nPvsSize = 0;
3220
3221	//Debug<<"f #s="<<samples<<" pvs size = "<<basePvs.GetSize();
3222	// cout<<"Filter size = "<<filterSize<<endl;
3223	// cout<<"vbox = "<<vbox<<endl;
3224	// cout<<"center = "<<center<<endl;
3225
3226
3227	// Minimal number of local samples to take into account
3228	// the local sampling density.
3229	// The size of the filter is a minimum of the conservative
3230	// local sampling density estimate (#rays intersecting teh viewcell and
3231	// the object)
3232	// and gobal estimate for the view cell
3233	// (total #rays intersecting the viewcell)
3234	const int minLocalSamples = 2;
3235	const float viewCellRadius = 0.5f * Magnitude(vbox.Diagonal());
3236
3237	float samples = (float)basePvs.GetSamples();
3238
3239
3240	//////////
3241	//-- now compute the filter box around the current viewCell
3242
3243	if (useViewSpaceFilter)
3244	{
3245	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
3246	float radius = viewCellRadius / 100.0f;
3247	vbox.Enlarge(radius);
3248	cout<<"vbox = "<<vbox<<endl;
3249
3250	ViewCellContainer viewCells;
3251	ComputeBoxIntersections(vbox, viewCells);
3252
3253	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3254
3255	for (int i = 0; it != it_end; ++ it, ++ i)
3256	{
3257	if ((*it) != viewCell)
3258	{
3259	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3260	basePvs.MergeInPlace((*it)->GetPvs());
3261	}
3262
3263	// update samples and globalC
3264	samples = (float)pvs.GetSamples();
3265	// cout<<"neighboring viewcells = "<<i-1<<endl;
3266	// cout<<"Samples' = "<<samples<<endl;
3267	}
3268	}
3269
3270	// Minimal number of samples so that filtering takes place
3271	const float MIN_SAMPLES = 50;
3272
3273	if (samples > MIN_SAMPLES)
3274	{
3275	float globalC = 2.0f * filterSize / sqrt(samples);
3276
3277	ObjectContainer objects;
3278	PvsData pvsData;
3279
3280	pit = basePvs.GetIterator();
3281
3282	if (onlyNewObjects) {
3283	while (pit.HasMoreEntries()) {
3284	// mail all objects from the original not to include them in the
3285	// resulting pvs
3286	Intersectable *obj = pit.Next(pvsData);
3287	obj->Mail();
3288	}
3289	pit = basePvs.GetIterator();
3290	}
3291
3292	while (pit.HasMoreEntries())
3293	{
3294	Intersectable *object = pit.Next(pvsData);
3295
3296	// compute filter size based on the distance and the numebr of samples
3297	AxisAlignedBox3 box = object->GetBox();
3298
3299	float distance = Distance(center, box.Center());
3300	float globalRadius = distance*globalC;
3301
3302	int objectSamples = (int)pvsData.mSumPdf;
3303	float localRadius = MAX_FLOAT;
3304
3305	localRadius = filterSize0.5fMagnitude(box.Diagonal())/
3306	sqrt((float)objectSamples);
3307
3308	// cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;
3309
3310	// now compute the filter size
3311	float radius;
3312
3313	#if 0
3314	if (objectSamples <= 1)
3315	{
3316	if (localRadius > globalRadius)
3317	{
3318	radius = 0.5flRadius;
3319	stats.mLocalFilterCount++;
3320	}
3321	else
3322	{
3323	radius = globalRadius;
3324	stats.mGlobalFilterCount++;
3325	}
3326	}
3327	else
3328	{
3329	radius = localRadius;
3330	stats.mLocalFilterCount++;
3331	}
3332	#else
3333
3334	// radius = 0.5fglobalRadius + 0.5flocalRadius;
3335	radius = Min(globalRadius, localRadius);
3336
3337	if (localRadius > globalRadius)
3338	++ stats.mLocalFilterCount;
3339	else
3340	++ stats.mGlobalFilterCount;
3341	#endif
3342
3343	stats.mAvgFilterRadius += radius;
3344
3345	// cout<<"box = "<<box<<endl;
3346	// cout<<"distance = "<<distance<<endl;
3347	// cout<<"radiues = "<<radius<<endl;
3348
3349	box.Enlarge(Vector3(radius));
3350
3351	if (filteredBoxes)
3352	filteredBoxes->push_back(box);
3353
3354	objects.clear();
3355
3356	// $$ warning collect objects takes only unmailed ones!
3357	if (mUseKdPvs) {
3358	// GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
3359	GetPreprocessor()->mKdTree->CollectSmallKdObjects(box, objects, 0.1f);
3360
3361	} else
3362	CollectObjects(box, objects);
3363
3364	// cout<<"collected objects="<<objects.size()<<endl;
3365	ObjectContainer::const_iterator noi = objects.begin();
3366	for (; noi != objects.end(); ++ noi)
3367	{
3368	Intersectable o = noi;
3369	// $$ JB warning: pdfs are not correct at this point!
3370	pvs.AddSampleDirty(o, Limits::Small);
3371	}
3372	}
3373
3374	stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
3375	}
3376
3377	//Debug << " nPvs size = " << pvs.GetSize() << endl;
3378
3379	if (!mUseKdPvs && !onlyNewObjects)
3380	{
3381	PvsData pvsData;
3382
3383	// copy the base pvs to the new pvs
3384	pit = basePvs.GetIterator();
3385	while (pit.HasMoreEntries())
3386	{
3387	Intersectable *obj = pit.Next(pvsData);
3388	pvs.AddSampleDirty(obj, pvsData.mSumPdf);
3389	}
3390	}
3391
3392	pvs.SimpleSort();
3393	viewCell->SetFilteredPvsSize(pvs.GetSize());
3394
3395	// warning: not thread-safe!
3396	if (!mUseKdPvs)
3397	Intersectable::NewMail();
3398
3399	return stats;
3400	}
3401
3402
3403
3404	void ViewCellsManager::ExportColor(Exporter *exporter,
3405	ViewCell *vc,
3406	int colorCode) const
3407	{
3408	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3409
3410	float importance = 0;
3411	static Material m;
3412	//cout << "color code: " << colorCode << endl;
3413
3414	switch (colorCode)
3415	{
3416	case 0: // Random
3417	{
3418	if (vcValid)
3419	{
3420	m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
3421	m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
3422	m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
3423	}
3424	else
3425	{
3426	m.mDiffuseColor.r = 0.0f;
3427	m.mDiffuseColor.g = 1.0f;
3428	m.mDiffuseColor.b = 0.0f;
3429	}
3430
3431	exporter->SetForcedMaterial(m);
3432	return;
3433	}
3434
3435	case 1: // pvs
3436	{
3437	if (mCurrentViewCellsStats.maxPvs)
3438	{
3439	importance = //(float)mViewCellsTree->GetTrianglesInPvs(vc) / 700;
3440	(float)mCurrentViewCellsStats.maxPvs;
3441	}
3442	}
3443	break;
3444	case 2: // merges
3445	{
3446	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
3447	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3448	}
3449	break;
3450	default:
3451	break;
3452	}
3453
3454	// special color code for invalid view cells
3455	m.mDiffuseColor.r = importance;
3456	m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
3457	m.mDiffuseColor.g = 1.0f - importance;
3458
3459	//Debug << "importance: " << importance << endl;
3460	exporter->SetForcedMaterial(m);
3461	}
3462
3463
3464	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3465	vector<MergeCandidate> &candidates)
3466	{
3467	// implemented in subclasses
3468	}
3469
3470
3471	void ViewCellsManager::UpdatePvsForEvaluation()
3472	{
3473	ObjectPvs objPvs;
3474	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
3475	}
3476
3477
3478	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
3479	{
3480	// terminate traversal
3481	if (root->IsLeaf())
3482	{
3483	// we assume that pvs is explicitly stored in leaves
3484	pvs = root->GetPvs();
3485	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
3486
3487	return;
3488	}
3489
3490	////////////////
3491	//-- interior node => propagate pvs up the tree
3492
3493	ViewCellInterior interior = static_cast<ViewCellInterior >(root);
3494
3495	// reset interior pvs
3496	interior->GetPvs().Clear();
3497
3498	// reset recursive pvs
3499	pvs.Clear();
3500
3501	// pvss of child nodes
3502	vector<ObjectPvs> pvsList;
3503	pvsList.resize((int)interior->mChildren.size());
3504
3505	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3506
3507	int i = 0;
3508
3509	////////
3510	//-- recursivly compute child pvss
3511
3512	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3513	{
3514	UpdatePvsForEvaluation(*vit, pvsList[i]);
3515	}
3516
3517	#if 1
3518	Intersectable::NewMail();
3519
3520
3521	///////////
3522	//-- merge pvss
3523
3524	PvsData pvsData;
3525
3526	vector<ObjectPvs>::iterator oit = pvsList.begin();
3527
3528	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3529	{
3530	ObjectPvsIterator pit = (*oit).GetIterator();
3531
3532	// add pvss to new pvs: use mailing to avoid adding entries two times.
3533	while (pit.HasMoreEntries())
3534	{
3535	Intersectable *intersect = pit.Next(pvsData);
3536
3537	if (!intersect->Mailed())
3538	{
3539	intersect->Mail();
3540	pvs.AddSampleDirty(intersect, pvsData.mSumPdf);
3541	}
3542	}
3543	}
3544
3545	// store pvs in this node
3546	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3547	{
3548	interior->SetPvs(pvs);
3549	}
3550
3551	// set new pvs size
3552	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3553
3554	#else
3555	// really merge cells: slow but sumPdf is correct
3556	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3557	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3558	#endif
3559	}
3560
3561
3562
3563	/*******************************************************************/
3564	/* BspViewCellsManager implementation */
3565	/*******************************************************************/
3566
3567
3568	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
3569	ViewCellsManager(vcTree), mBspTree(bspTree)
3570	{
3571	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3572
3573	mBspTree->SetViewCellsManager(this);
3574	mBspTree->SetViewCellsTree(mViewCellsTree);
3575	}
3576
3577
3578	bool BspViewCellsManager::ViewCellsConstructed() const
3579	{
3580	return mBspTree->GetRoot() != NULL;
3581	}
3582
3583
3584	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
3585	{
3586	return new BspViewCell(mesh);
3587	}
3588
3589
3590	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3591	const VssRayContainer &rays)
3592	{
3593	// if view cells were already constructed, we can finish
3594	if (ViewCellsConstructed())
3595	return 0;
3596
3597	int sampleContributions = 0;
3598
3599	// construct view cells using the collected samples
3600	RayContainer constructionRays;
3601	VssRayContainer savedRays;
3602
3603	// choose a a number of rays based on the ratio of cast rays / requested rays
3604	const int limit = min(mInitialSamples, (int)rays.size());
3605	VssRayContainer::const_iterator it, it_end = rays.end();
3606
3607	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3608
3609	for (it = rays.begin(); it != it_end; ++ it)
3610	{
3611	if (Random(1.0f) < prop)
3612	constructionRays.push_back(new Ray((it)));
3613	else
3614	savedRays.push_back(*it);
3615	}
3616
3617	if (!mUsePredefinedViewCells)
3618	{
3619	// no view cells loaded
3620	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3621	// collect final view cells
3622	mBspTree->CollectViewCells(mViewCells);
3623	}
3624	else
3625	{
3626	// use predefined view cells geometry =>
3627	// contruct bsp hierarchy over them
3628	mBspTree->Construct(mViewCells);
3629	}
3630
3631	// destroy rays created only for construction
3632	CLEAR_CONTAINER(constructionRays);
3633
3634	Debug << mBspTree->GetStatistics() << endl;
3635	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3636
3637	// recast rest of the rays
3638	if (SAMPLE_AFTER_SUBDIVISION)
3639	ComputeSampleContributions(savedRays, true, false);
3640
3641	// real meshes are contructed at this stage
3642	if (0)
3643	{
3644	cout << "finalizing view cells ... ";
3645	FinalizeViewCells(true);
3646	cout << "finished" << endl;
3647	}
3648
3649	return sampleContributions;
3650	}
3651
3652
3653	void BspViewCellsManager::CollectViewCells()
3654	{
3655	if (!ViewCellsTreeConstructed())
3656	{ // view cells tree constructed
3657	mBspTree->CollectViewCells(mViewCells);
3658	}
3659	else
3660	{ // we can use the view cells tree hierarchy to get the right set
3661	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3662	}
3663	}
3664
3665
3666	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3667	{
3668	if (1)
3669	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3670	else
3671	// compute view cell area as subsititute for probability
3672	return GetArea(viewCell) / GetAccVcArea();
3673	}
3674
3675
3676
3677	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3678	const Vector3 &termination,
3679	ViewCellContainer &viewcells)
3680	{
3681	return mBspTree->CastLineSegment(origin, termination, viewcells);
3682	}
3683
3684
3685	bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
3686	const Vector3 &termination,
3687	ViewCell *viewCell)
3688	{
3689	return false;
3690	}
3691
3692
3693	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3694	{
3695	// save color code
3696	const int savedColorCode = mColorCode;
3697
3698	Exporter *exporter;
3699
3700	// export merged view cells using pvs color coding
3701	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3702	cout << "exporting view cells after merge (pvs size) ... ";
3703
3704	if (exporter)
3705	{
3706	if (mExportGeometry)
3707	{
3708	exporter->ExportGeometry(objects);
3709	}
3710
3711	exporter->SetFilled();
3712	mColorCode = 1;
3713
3714	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3715
3716	delete exporter;
3717	}
3718	cout << "finished" << endl;
3719
3720	mColorCode = savedColorCode;
3721	}
3722
3723
3724	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3725	const VssRayContainer &rays)
3726	{
3727	if (!ViewCellsConstructed())
3728	{
3729	Debug << "view cells not constructed" << endl;
3730	return 0;
3731	}
3732
3733	// view cells already finished before post processing step,
3734	// i.e., because they were loaded from disc
3735	if (mViewCellsFinished)
3736	{
3737	FinalizeViewCells(true);
3738	EvaluateViewCellsStats();
3739
3740	return 0;
3741	}
3742
3743	//////////////////
3744	//-- merge leaves of the view cell hierarchy
3745
3746	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3747	long startTime = GetTime();
3748
3749	VssRayContainer postProcessRays;
3750	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3751
3752	if (mMergeViewCells)
3753	{
3754	cout << "constructing visibility based merge tree" << endl;
3755	mViewCellsTree->ConstructMergeTree(rays, objects);
3756	}
3757	else
3758	{
3759	cout << "constructing spatial merge tree" << endl;
3760	ViewCell *root;
3761	// the spatial merge tree is difficult to build for
3762	// this type of construction, as view cells cover several
3763	// leaves => create dummy tree which is only 2 levels deep
3764	if (mUsePredefinedViewCells)
3765	{
3766	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3767	}
3768	else
3769	{
3770	// create spatial merge hierarchy
3771	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3772	}
3773
3774	mViewCellsTree->SetRoot(root);
3775
3776	// recompute pvs in the whole hierarchy
3777	ObjectPvs pvs;
3778	UpdatePvsForEvaluation(root, pvs);
3779	}
3780
3781	cout << "finished" << endl;
3782	cout << "merged view cells in "
3783	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3784
3785	Debug << "Postprocessing: Merged view cells in "
3786	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3787
3788
3789	////////////////////////
3790	//-- visualization and statistics after merge
3791
3792	if (1)
3793	{
3794	char mstats[100];
3795	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3796	mViewCellsTree->ExportStats(mstats);
3797	}
3798
3799	// recompute view cells and stats
3800	ResetViewCells();
3801	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3802
3803	// visualization of the view cells
3804	if (1) ExportMergedViewCells(objects);
3805
3806	// compute final meshes and volume / area
3807	if (1) FinalizeViewCells(true);
3808
3809	return 0;
3810	}
3811
3812
3813	BspViewCellsManager::~BspViewCellsManager()
3814	{
3815	}
3816
3817
3818	int BspViewCellsManager::GetType() const
3819	{
3820	return BSP;
3821	}
3822
3823
3824	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3825	const VssRayContainer &sampleRays)
3826	{
3827	if (!ViewCellsConstructed())
3828	return;
3829
3830	const int savedColorCode = mColorCode;
3831
3832	if (1) // export final view cells
3833	{
3834	mColorCode = 1; // 0 = pvs, 1 = random
3835	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3836
3837	cout << "exporting view cells after merge (pvs size) ... ";
3838
3839	if (exporter)
3840	{
3841	if (mExportGeometry)
3842	{
3843	exporter->ExportGeometry(objects);
3844	}
3845
3846	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3847	delete exporter;
3848	}
3849	cout << "finished" << endl;
3850	}
3851
3852	// reset color code
3853	mColorCode = savedColorCode;
3854
3855
3856	//////////////////
3857	//-- visualization of the BSP splits
3858
3859	bool exportSplits = false;
3860	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3861
3862	if (exportSplits)
3863	{
3864	cout << "exporting splits ... ";
3865	ExportSplits(objects);
3866	cout << "finished" << endl;
3867	}
3868
3869	int leafOut;
3870	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3871	const int raysOut = 100;
3872	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3873	}
3874
3875
3876	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3877	{
3878	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3879
3880	if (exporter)
3881	{
3882	//exporter->SetFilled();
3883	if (mExportGeometry)
3884	{
3885	exporter->ExportGeometry(objects);
3886	}
3887
3888	Material m;
3889	m.mDiffuseColor = RgbColor(1, 0, 0);
3890	exporter->SetForcedMaterial(m);
3891	exporter->SetWireframe();
3892
3893	exporter->ExportBspSplits(*mBspTree, true);
3894
3895	// NOTE: take forced material, else big scenes cannot be viewed
3896	m.mDiffuseColor = RgbColor(0, 1, 0);
3897	exporter->SetForcedMaterial(m);
3898	//exporter->ResetForcedMaterial();
3899
3900	delete exporter;
3901	}
3902	}
3903
3904
3905	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3906	const int maxViewCells,
3907	const bool sortViewCells,
3908	const bool exportPvs,
3909	const bool exportRays,
3910	const int maxRays,
3911	const string &prefix,
3912	VssRayContainer *visRays)
3913	{
3914	if (sortViewCells)
3915	{ // sort view cells to visualize the largest view cells
3916	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
3917	}
3918
3919	//////////
3920	//-- export visualizations of some view cells
3921
3922	ViewCell::NewMail();
3923	const int limit = min(maxViewCells, (int)mViewCells.size());
3924
3925	for (int i = 0; i < limit; ++ i)
3926	{
3927	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
3928	ViewCell *vc = mViewCells[idx];
3929
3930	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
3931	continue;
3932
3933	vc->Mail();
3934
3935	ObjectPvs pvs;
3936	mViewCellsTree->GetPvs(vc, pvs);
3937
3938	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
3939	Exporter *exporter = Exporter::GetExporter(s);
3940
3941	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetTrianglesInPvs(vc) << endl;
3942
3943	if (exportRays)
3944	{
3945	////////////
3946	//-- export rays piercing this view cell
3947
3948	// use rays stored with the view cells
3949	VssRayContainer vcRays, vcRays2, vcRays3;
3950	VssRayContainer collectRays;
3951
3952	// collect initial view cells
3953	ViewCellContainer leaves;
3954	mViewCellsTree->CollectLeaves(vc, leaves);
3955
3956	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3957	for (vit = leaves.begin(); vit != vit_end; ++ vit)
3958	{
3959	// prepare some rays for visualization
3960	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
3961	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
3962	{
3963	collectRays.push_back(*rit);
3964	}
3965	}
3966
3967	const int raysOut = min((int)collectRays.size(), maxRays);
3968
3969	// prepare some rays for visualization
3970	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3971	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3972	{
3973	const float p = RandomValue(0.0f, (float)collectRays.size());
3974	if (p < raysOut)
3975	{
3976	if ((*rit)->mFlags & VssRay::BorderSample)
3977	{
3978	vcRays.push_back(*rit);
3979	}
3980	else if ((*rit)->mFlags & VssRay::ReverseSample)
3981	{
3982	vcRays2.push_back(*rit);
3983	}
3984	else
3985	{
3986	vcRays3.push_back(*rit);
3987	}
3988	}
3989	}
3990
3991	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
3992	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
3993	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
3994	}
3995
3996	////////////////
3997	//-- export view cell geometry
3998
3999	exporter->SetWireframe();
4000
4001	Material m;//= RandomMaterial();
4002	m.mDiffuseColor = RgbColor(0, 1, 0);
4003	exporter->SetForcedMaterial(m);
4004
4005	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4006	exporter->SetFilled();
4007
4008	if (exportPvs)
4009	{
4010	Intersectable::NewMail();
4011	ObjectPvsIterator pit = pvs.GetIterator();
4012
4013	while (pit.HasMoreEntries())
4014	{
4015	Intersectable *intersect = pit.Next();
4016
4017	// output PVS of view cell
4018	if (!intersect->Mailed())
4019	{
4020	intersect->Mail();
4021
4022	m = RandomMaterial();
4023	exporter->SetForcedMaterial(m);
4024	exporter->ExportIntersectable(intersect);
4025	}
4026	}
4027	cout << endl;
4028	}
4029
4030	DEL_PTR(exporter);
4031	cout << "finished" << endl;
4032	}
4033	}
4034
4035
4036	void BspViewCellsManager::TestSubdivision()
4037	{
4038	ViewCellContainer leaves;
4039	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4040
4041	ViewCellContainer::const_iterator it, it_end = leaves.end();
4042
4043	const float vol = mViewSpaceBox.GetVolume();
4044	float subdivVol = 0;
4045	float newVol = 0;
4046
4047	for (it = leaves.begin(); it != it_end; ++ it)
4048	{
4049	BspNodeGeometry geom;
4050	mBspTree->ConstructGeometry(*it, geom);
4051
4052	const float lVol = geom.GetVolume();
4053	newVol += lVol;
4054	subdivVol += (*it)->GetVolume();
4055
4056	const float thres = 0.9f;
4057	if ((lVol < ((it)->GetVolume() thres)) \|\|
4058	(lVol * thres > ((*it)->GetVolume())))
4059	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4060	}
4061
4062	Debug << "exact volume: " << vol << endl;
4063	Debug << "subdivision volume: " << subdivVol << endl;
4064	Debug << "new volume: " << newVol << endl;
4065	}
4066
4067
4068	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4069	ViewCell *vc,
4070	const AxisAlignedBox3 *sceneBox,
4071	const AxisAlignedPlane *clipPlane
4072	) const
4073	{
4074	if (clipPlane)
4075	{
4076	const Plane3 plane = clipPlane->GetPlane();
4077
4078	ViewCellContainer leaves;
4079	mViewCellsTree->CollectLeaves(vc, leaves);
4080	ViewCellContainer::const_iterator it, it_end = leaves.end();
4081
4082	for (it = leaves.begin(); it != it_end; ++ it)
4083	{
4084	BspNodeGeometry geom;
4085	BspNodeGeometry front;
4086	BspNodeGeometry back;
4087
4088	mBspTree->ConstructGeometry(*it, geom);
4089
4090	const float eps = 0.0001f;
4091	const int cf = geom.Side(plane, eps);
4092
4093	if (cf == -1)
4094	{
4095	exporter->ExportPolygons(geom.GetPolys());
4096	}
4097	else if (cf == 0)
4098	{
4099	geom.SplitGeometry(front,
4100	back,
4101	plane,
4102	mViewSpaceBox,
4103	eps);
4104
4105	if (back.Valid())
4106	{
4107	exporter->ExportPolygons(back.GetPolys());
4108	}
4109	}
4110	}
4111	}
4112	else
4113	{
4114	// export mesh if available
4115	// TODO: some bug here?
4116	if (1 && vc->GetMesh())
4117	{
4118	exporter->ExportMesh(vc->GetMesh());
4119	}
4120	else
4121	{
4122	BspNodeGeometry geom;
4123	mBspTree->ConstructGeometry(vc, geom);
4124	exporter->ExportPolygons(geom.GetPolys());
4125	}
4126	}
4127	}
4128
4129
4130	void BspViewCellsManager::CreateMesh(ViewCell *vc)
4131	{
4132	// note: should previous mesh be deleted (via mesh manager?)
4133	BspNodeGeometry geom;
4134	mBspTree->ConstructGeometry(vc, geom);
4135
4136	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4137
4138	IncludeNodeGeomInMesh(geom, *mesh);
4139	mesh->ComputeBoundingBox();
4140
4141	vc->SetMesh(mesh);
4142	}
4143
4144
4145	void BspViewCellsManager::Finalize(ViewCell *viewCell,
4146	const bool createMesh)
4147	{
4148	float area = 0;
4149	float volume = 0;
4150
4151	ViewCellContainer leaves;
4152	mViewCellsTree->CollectLeaves(viewCell, leaves);
4153
4154	ViewCellContainer::const_iterator it, it_end = leaves.end();
4155
4156	for (it = leaves.begin(); it != it_end; ++ it)
4157	{
4158	BspNodeGeometry geom;
4159
4160	mBspTree->ConstructGeometry(*it, geom);
4161
4162	const float lVol = geom.GetVolume();
4163	const float lArea = geom.GetArea();
4164
4165	area += lArea;
4166	volume += lVol;
4167
4168	CreateMesh(*it);
4169	}
4170
4171	viewCell->SetVolume(volume);
4172	viewCell->SetArea(area);
4173	}
4174
4175
4176	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4177	{
4178	if (!ViewCellsConstructed())
4179	{
4180	return NULL;
4181	}
4182	if (!mViewSpaceBox.IsInside(point))
4183	{
4184	return NULL;
4185	}
4186	return mBspTree->GetViewCell(point);
4187	}
4188
4189
4190	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4191	vector<MergeCandidate> &candidates)
4192	{
4193	cout << "collecting merge candidates ... " << endl;
4194
4195	if (mUseRaysForMerge)
4196	{
4197	mBspTree->CollectMergeCandidates(rays, candidates);
4198	}
4199	else
4200	{
4201	vector<BspLeaf *> leaves;
4202	mBspTree->CollectLeaves(leaves);
4203	mBspTree->CollectMergeCandidates(leaves, candidates);
4204	}
4205
4206	cout << "fininshed collecting candidates" << endl;
4207	}
4208
4209
4210
4211	bool BspViewCellsManager::ExportViewCells(const string filename,
4212	const bool exportPvs,
4213	const ObjectContainer &objects)
4214	{
4215	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
4216	{
4217	return false;
4218	}
4219
4220	cout << "exporting view cells to xml ... ";
4221
4222	OUT_STREAM stream(filename.c_str());
4223
4224	// we need unique ids for each view cell
4225	CreateUniqueViewCellIds();
4226
4227	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
4228	stream << "<VisibilitySolution>" << endl;
4229
4230	if (exportPvs)
4231	{
4232	//////////
4233	//-- export bounding boxes: they are used to identify the objects from the pvs and
4234	//-- assign them to the entities in the rendering engine
4235
4236	stream << "<BoundingBoxes>" << endl;
4237	ObjectContainer::const_iterator oit, oit_end = objects.end();
4238
4239	for (oit = objects.begin(); oit != oit_end; ++ oit)
4240	{
4241	const AxisAlignedBox3 box = (*oit)->GetBox();
4242
4243	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
4244	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
4245	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
4246	}
4247
4248	stream << "</BoundingBoxes>" << endl;
4249	}
4250
4251	///////////
4252	//-- export the view cells and the pvs
4253
4254	const int numViewCells = mCurrentViewCellsStats.viewCells;
4255	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
4256
4257	mViewCellsTree->Export(stream, exportPvs);
4258
4259	stream << "</ViewCells>" << endl;
4260
4261	/////////////
4262	//-- export the view space hierarchy
4263	stream << "<ViewSpaceHierarchy type=\"bsp\""
4264	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
4265	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
4266
4267	mBspTree->Export(stream);
4268
4269	// end tags
4270	stream << "</ViewSpaceHierarchy>" << endl;
4271	stream << "</VisibilitySolution>" << endl;
4272
4273	stream.close();
4274	cout << "finished" << endl;
4275
4276	return true;
4277	}
4278
4279
4280	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
4281	{
4282	ViewCellInterior *vcRoot = new ViewCellInterior();
4283
4284	// evaluate merge cost for priority traversal
4285	const float mergeCost = -(float)root->mTimeStamp;
4286	vcRoot->SetMergeCost(mergeCost);
4287
4288	float volume = 0;
4289	vector<BspLeaf *> leaves;
4290	mBspTree->CollectLeaves(leaves);
4291	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
4292	ViewCell::NewMail();
4293
4294	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4295	{
4296	BspLeaf leaf = lit;
4297	ViewCell *vc = leaf->GetViewCell();
4298
4299	if (!vc->Mailed())
4300	{
4301	vc->Mail();
4302	vc->SetMergeCost(0.0f);
4303	vcRoot->SetupChildLink(vc);
4304
4305	volume += vc->GetVolume();
4306	volume += vc->GetVolume();
4307	vcRoot->SetVolume(volume);
4308	}
4309	}
4310
4311	return vcRoot;
4312	}
4313
4314
4315	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4316	{
4317	// terminate recursion
4318	if (root->IsLeaf())
4319	{
4320	BspLeaf leaf = static_cast<BspLeaf >(root);
4321	leaf->GetViewCell()->SetMergeCost(0.0f);
4322	return leaf->GetViewCell();
4323	}
4324
4325	BspInterior interior = static_cast<BspInterior >(root);
4326	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4327
4328	// evaluate merge cost for priority traversal
4329	const float mergeCost = -(float)root->mTimeStamp;
4330	viewCellInterior->SetMergeCost(mergeCost);
4331
4332	float volume = 0;
4333
4334	BspNode *front = interior->GetFront();
4335	BspNode *back = interior->GetBack();
4336
4337
4338	////////////
4339	//-- recursivly compute child hierarchies
4340
4341	ViewCell *backVc = ConstructSpatialMergeTree(back);
4342	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4343
4344	viewCellInterior->SetupChildLink(backVc);
4345	viewCellInterior->SetupChildLink(frontVc);
4346
4347	volume += backVc->GetVolume();
4348	volume += frontVc->GetVolume();
4349
4350	viewCellInterior->SetVolume(volume);
4351
4352	return viewCellInterior;
4353	}
4354
4355
4356	/************************************************************************/
4357	/* KdViewCellsManager implementation */
4358	/************************************************************************/
4359
4360
4361
4362	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
4363	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
4364	{
4365	}
4366
4367
4368	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
4369	{
4370	// compute view cell area / volume as subsititute for probability
4371	if (0)
4372	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
4373	else
4374	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
4375	}
4376
4377
4378
4379
4380	void KdViewCellsManager::CollectViewCells()
4381	{
4382	//mKdTree->CollectViewCells(mViewCells); TODO
4383	}
4384
4385
4386	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4387	const VssRayContainer &rays)
4388	{
4389	// if view cells already constructed
4390	if (ViewCellsConstructed())
4391	return 0;
4392
4393	mKdTree->Construct();
4394
4395	mTotalAreaValid = false;
4396	// create the view cells
4397	mKdTree->CreateAndCollectViewCells(mViewCells);
4398	// cast rays
4399	ComputeSampleContributions(rays, true, false);
4400
4401	EvaluateViewCellsStats();
4402	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4403
4404	return 0;
4405	}
4406
4407
4408	bool KdViewCellsManager::ViewCellsConstructed() const
4409	{
4410	return mKdTree->GetRoot() != NULL;
4411	}
4412
4413
4414	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
4415	const VssRayContainer &rays)
4416	{
4417	return 0;
4418	}
4419
4420
4421	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4422	const int maxViewCells,
4423	const bool sortViewCells,
4424	const bool exportPvs,
4425	const bool exportRays,
4426	const int maxRays,
4427	const string &prefix,
4428	VssRayContainer *visRays)
4429	{
4430	// TODO
4431	}
4432
4433
4434	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
4435	const VssRayContainer &sampleRays)
4436	{
4437	if (!ViewCellsConstructed())
4438	return;
4439
4440	// using view cells instead of the kd PVS of objects
4441	const bool useViewCells = true;
4442	bool exportRays = false;
4443
4444	int limit = min(mVisualizationSamples, (int)sampleRays.size());
4445	const int pvsOut = min((int)objects.size(), 10);
4446	VssRayContainer *rays = new VssRayContainer[pvsOut];
4447
4448	if (useViewCells)
4449	{
4450	const int leafOut = 10;
4451
4452	ViewCell::NewMail();
4453
4454	//-- some rays for visualization
4455	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4456	Debug << "visualization using " << raysOut << " samples" << endl;
4457
4458	//-- some random view cells and rays for visualization
4459	vector<KdLeaf *> kdLeaves;
4460
4461	for (int i = 0; i < leafOut; ++ i)
4462	kdLeaves.push_back(static_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4463
4464	for (int i = 0; i < kdLeaves.size(); ++ i)
4465	{
4466	KdLeaf *leaf = kdLeaves[i];
4467	RayContainer vcRays;
4468
4469	cout << "creating output for view cell " << i << " ... ";
4470	#if 0
4471	// check whether we can add the current ray to the output rays
4472	for (int k = 0; k < raysOut; ++ k)
4473	{
4474	Ray *ray = sampleRays[k];
4475
4476	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4477	{
4478	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4479
4480	if (leaf->GetViewCell() == leaf2->GetViewCell())
4481	{
4482	vcRays.push_back(ray);
4483	}
4484	}
4485	}
4486	#endif
4487	Intersectable::NewMail();
4488
4489	ViewCell *vc = leaf->mViewCell;
4490	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4491
4492	Exporter *exporter = Exporter::GetExporter(str);
4493	exporter->SetFilled();
4494
4495	exporter->SetWireframe();
4496	//exporter->SetFilled();
4497
4498	Material m;//= RandomMaterial();
4499	m.mDiffuseColor = RgbColor(1, 1, 0);
4500	exporter->SetForcedMaterial(m);
4501
4502	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4503	exporter->ExportBox(box);
4504
4505	// export rays piercing this view cell
4506	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4507
4508	m.mDiffuseColor = RgbColor(1, 0, 0);
4509	exporter->SetForcedMaterial(m);
4510
4511	// exporter->SetWireframe();
4512	exporter->SetFilled();
4513
4514	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4515
4516	while (pit.HasMoreEntries())
4517	{
4518	//-- output PVS of view cell
4519	Intersectable *intersect = pit.Next();
4520
4521	if (!intersect->Mailed())
4522	{
4523	exporter->ExportIntersectable(intersect);
4524	intersect->Mail();
4525	}
4526	}
4527
4528	DEL_PTR(exporter);
4529	cout << "finished" << endl;
4530	}
4531
4532	DEL_PTR(rays);
4533	}
4534	else // using kd PVS of objects
4535	{
4536	for (int i = 0; i < limit; ++ i)
4537	{
4538	VssRay *ray = sampleRays[i];
4539
4540	// check whether we can add this to the rays
4541	for (int j = 0; j < pvsOut; j++)
4542	{
4543	if (objects[j] == ray->mTerminationObject)
4544	{
4545	rays[j].push_back(ray);
4546	}
4547	}
4548	}
4549
4550	if (exportRays)
4551	{
4552	Exporter *exporter = NULL;
4553	exporter = Exporter::GetExporter("sample-rays.x3d");
4554	exporter->SetWireframe();
4555	exporter->ExportKdTree(*mKdTree);
4556
4557	for (int i = 0; i < pvsOut; i++)
4558	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4559
4560	exporter->SetFilled();
4561	delete exporter;
4562	}
4563
4564	for (int k=0; k < pvsOut; k++)
4565	{
4566	Intersectable *object = objects[k];
4567	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4568
4569	Exporter *exporter = Exporter::GetExporter(str);
4570	exporter->SetWireframe();
4571
4572	// matt: we do not use kd pvs
4573	#if 0
4574	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4575	Intersectable::NewMail();
4576
4577	// avoid adding the object to the list
4578	object->Mail();
4579	ObjectContainer visibleObjects;
4580
4581	for (; kit != object->mKdPvs.mEntries.end(); i++)
4582	{
4583	KdNode node = (kit).first;
4584	exporter->ExportBox(mKdTree->GetBox(node));
4585
4586	mKdTree->CollectObjects(node, visibleObjects);
4587	}
4588
4589	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4590	exporter->SetFilled();
4591
4592	for (int j = 0; j < visibleObjects.size(); j++)
4593	exporter->ExportIntersectable(visibleObjects[j]);
4594
4595	Material m;
4596	m.mDiffuseColor = RgbColor(1, 0, 0);
4597	exporter->SetForcedMaterial(m);
4598	exporter->ExportIntersectable(object);
4599	#endif
4600	delete exporter;
4601	}
4602	}
4603	}
4604
4605
4606	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4607	{
4608	return new KdViewCell(mesh);
4609	}
4610
4611
4612	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4613	ViewCell *vc,
4614	const AxisAlignedBox3 *sceneBox,
4615	const AxisAlignedPlane *clipPlane
4616	) const
4617	{
4618	ViewCellContainer leaves;
4619	mViewCellsTree->CollectLeaves(vc, leaves);
4620	ViewCellContainer::const_iterator it, it_end = leaves.end();
4621
4622	for (it = leaves.begin(); it != it_end; ++ it)
4623	{
4624	KdViewCell kdVc = static_cast<KdViewCell >(*it);
4625	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4626	}
4627	}
4628
4629
4630	int KdViewCellsManager::GetType() const
4631	{
4632	return ViewCellsManager::KD;
4633	}
4634
4635
4636
4637	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4638	{
4639	KdNode *node = leaf;
4640
4641	while (node->mParent && node->mDepth > mKdPvsDepth)
4642	node = node->mParent;
4643
4644	return node;
4645	}
4646
4647	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4648	const Vector3 &termination,
4649	ViewCellContainer &viewcells)
4650	{
4651	return mKdTree->CastLineSegment(origin, termination, viewcells);
4652	}
4653
4654
4655	bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
4656	const Vector3 &termination,
4657	ViewCell *viewCell)
4658	{
4659	return false;
4660	}
4661
4662
4663	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4664	{
4665	// TODO
4666	}
4667
4668
4669
4670	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4671	vector<MergeCandidate> &candidates)
4672	{
4673	// TODO
4674	}
4675
4676
4677
4678	/**************************************************************************/
4679	/* VspBspViewCellsManager implementation */
4680	/**************************************************************************/
4681
4682
4683	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4684	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4685	{
4686	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4687	mVspBspTree->SetViewCellsManager(this);
4688	mVspBspTree->mViewCellsTree = mViewCellsTree;
4689	}
4690
4691
4692	VspBspViewCellsManager::~VspBspViewCellsManager()
4693	{
4694	}
4695
4696
4697	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4698	{
4699	if (0 && mVspBspTree->mUseAreaForPvs)
4700	return GetArea(viewCell) / GetAccVcArea();
4701	else
4702	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4703	}
4704
4705
4706	void VspBspViewCellsManager::CollectViewCells()
4707	{
4708	// view cells tree constructed?
4709	if (!ViewCellsTreeConstructed())
4710	{
4711	mVspBspTree->CollectViewCells(mViewCells, false);
4712	}
4713	else
4714	{
4715	// we can use the view cells tree hierarchy to get the right set
4716	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4717	}
4718	}
4719
4720
4721	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4722	vector<MergeCandidate> &candidates)
4723	{
4724	cout << "collecting merge candidates ... " << endl;
4725
4726	if (mUseRaysForMerge)
4727	{
4728	mVspBspTree->CollectMergeCandidates(rays, candidates);
4729	}
4730	else
4731	{
4732	vector<BspLeaf *> leaves;
4733	mVspBspTree->CollectLeaves(leaves);
4734
4735	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4736	}
4737
4738	cout << "fininshed collecting candidates" << endl;
4739	}
4740
4741
4742	bool VspBspViewCellsManager::ViewCellsConstructed() const
4743	{
4744	return mVspBspTree->GetRoot() != NULL;
4745	}
4746
4747
4748	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4749	{
4750	return new BspViewCell(mesh);
4751	}
4752
4753
4754	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4755	const VssRayContainer &rays)
4756	{
4757	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4758
4759	// if view cells were already constructed
4760	if (ViewCellsConstructed())
4761	{
4762	return 0;
4763	}
4764
4765	int sampleContributions = 0;
4766	VssRayContainer sampleRays;
4767
4768	const int limit = min(mInitialSamples, (int)rays.size());
4769
4770	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4771	<< ", actual rays: " << (int)rays.size() << endl;
4772
4773	VssRayContainer savedRays;
4774
4775	if (SAMPLE_AFTER_SUBDIVISION)
4776	{
4777	VssRayContainer constructionRays;
4778
4779	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4780
4781	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4782	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4783
4784	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4785	}
4786	else
4787	{
4788	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4789	mVspBspTree->Construct(rays, &mViewSpaceBox);
4790	}
4791
4792	// collapse invalid regions
4793	cout << "collapsing invalid tree regions ... ";
4794	long startTime = GetTime();
4795
4796	const int collapsedLeaves = mVspBspTree->CollapseTree();
4797	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4798	<< " seconds" << endl;
4799
4800	cout << "finished" << endl;
4801
4802	/////////////////
4803	//-- stats after construction
4804
4805	Debug << mVspBspTree->GetStatistics() << endl;
4806
4807	ResetViewCells();
4808	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4809
4810
4811	//////////////////////
4812	//-- recast the rest of the rays
4813
4814	startTime = GetTime();
4815
4816	cout << "Computing remaining ray contributions ... ";
4817
4818	if (SAMPLE_AFTER_SUBDIVISION)
4819	ComputeSampleContributions(savedRays, true, false);
4820
4821	cout << "finished" << endl;
4822
4823	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4824	<< " secs" << endl;
4825
4826	cout << "construction finished" << endl;
4827
4828	if (0)
4829	{ ////////
4830	//-- real meshes are contructed at this stage
4831
4832	cout << "finalizing view cells ... ";
4833	FinalizeViewCells(true);
4834	cout << "finished" << endl;
4835	}
4836
4837	return sampleContributions;
4838	}
4839
4840
4841	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4842	const ObjectContainer &objects)
4843	{
4844	int vcSize = 0;
4845	int pvsSize = 0;
4846
4847	//-- merge view cells
4848	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4849	long startTime = GetTime();
4850
4851
4852	if (mMergeViewCells)
4853	{
4854	// TODO: should be done BEFORE the ray casting
4855	// compute tree by merging the nodes based on cost heuristics
4856	mViewCellsTree->ConstructMergeTree(rays, objects);
4857	}
4858	else
4859	{
4860	// compute tree by merging the nodes of the spatial hierarchy
4861	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4862	mViewCellsTree->SetRoot(root);
4863
4864	// compute pvs
4865	ObjectPvs pvs;
4866	UpdatePvsForEvaluation(root, pvs);
4867	}
4868
4869	if (1)
4870	{
4871	char mstats[100];
4872	ObjectPvs pvs;
4873
4874	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4875	mViewCellsTree->ExportStats(mstats);
4876	}
4877
4878	cout << "merged view cells in "
4879	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4880
4881	Debug << "Postprocessing: Merged view cells in "
4882	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4883
4884
4885	//////////////////
4886	//-- stats and visualizations
4887
4888	int savedColorCode = mColorCode;
4889
4890	// get currently active view cell set
4891	ResetViewCells();
4892	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4893
4894	if (mShowVisualization) // export merged view cells
4895	{
4896	mColorCode = 0;
4897	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4898
4899	cout << "exporting view cells after merge ... ";
4900
4901	if (exporter)
4902	{
4903	if (0)
4904	exporter->SetWireframe();
4905	else
4906	exporter->SetFilled();
4907
4908	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4909
4910	if (mExportGeometry)
4911	{
4912	Material m;
4913	m.mDiffuseColor = RgbColor(0, 1, 0);
4914	exporter->SetForcedMaterial(m);
4915	exporter->SetFilled();
4916
4917	exporter->ExportGeometry(objects);
4918	}
4919
4920	delete exporter;
4921	}
4922	cout << "finished" << endl;
4923	}
4924
4925	mColorCode = savedColorCode;
4926	}
4927
4928
4929	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4930	const ObjectContainer &objects)
4931	{
4932	mRenderer->RenderScene();
4933
4934	SimulationStatistics ss;
4935	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4936	Debug << "render time before refine\n\n" << ss << endl;
4937
4938	const long startTime = GetTime();
4939	cout << "Refining the merged view cells ... ";
4940
4941	// refining the merged view cells
4942	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4943
4944	//-- stats and visualizations
4945	cout << "finished" << endl;
4946	cout << "refined " << refined << " view cells in "
4947	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4948
4949	Debug << "Postprocessing: refined " << refined << " view cells in "
4950	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4951	}
4952
4953
4954	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4955	const VssRayContainer &rays)
4956	{
4957	if (!ViewCellsConstructed())
4958	{
4959	Debug << "postprocess error: no view cells constructed" << endl;
4960	return 0;
4961	}
4962
4963	// view cells already finished before post processing step
4964	// (i.e. because they were loaded)
4965	if (mViewCellsFinished)
4966	{
4967	FinalizeViewCells(true);
4968	EvaluateViewCellsStats();
4969
4970	return 0;
4971	}
4972
4973	// check if new view cells turned invalid
4974	int minPvs, maxPvs;
4975
4976	if (0)
4977	{
4978	minPvs = mMinPvsSize;
4979	maxPvs = mMaxPvsSize;
4980	}
4981	else
4982	{
4983	// problem matt: why did I start here from zero?
4984	minPvs = 0;
4985	maxPvs = mMaxPvsSize;
4986	}
4987
4988	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4989	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4990
4991	SetValidity(minPvs, maxPvs);
4992
4993	// update valid view space according to valid view cells
4994	if (0) mVspBspTree->ValidateTree();
4995
4996	// area has to be recomputed
4997	mTotalAreaValid = false;
4998	VssRayContainer postProcessRays;
4999	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5000
5001	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5002
5003	//////////
5004	//-- merge neighbouring view cells
5005	MergeViewCells(postProcessRays, objects);
5006
5007	// refines the merged view cells
5008	if (0) RefineViewCells(postProcessRays, objects);
5009
5010
5011	///////////
5012	//-- render simulation after merge + refine
5013
5014	cout << "\nview cells partition render time before compress" << endl << endl;;
5015	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5016	SimulationStatistics ss;
5017	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5018	cout << ss << endl;
5019
5020	if (0) CompressViewCells();
5021
5022	// collapse sibling leaves that share the same view cell
5023	if (0) mVspBspTree->CollapseTree();
5024
5025	// recompute view cell list and statistics
5026	ResetViewCells();
5027
5028	// compute final meshes and volume / area
5029	if (1) FinalizeViewCells(true);
5030
5031	return 0;
5032	}
5033
5034
5035	int VspBspViewCellsManager::GetType() const
5036	{
5037	return VSP_BSP;
5038	}
5039
5040
5041	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
5042	{
5043	// terminate recursion
5044	if (root->IsLeaf())
5045	{
5046	BspLeaf leaf = static_cast<BspLeaf >(root);
5047	leaf->GetViewCell()->SetMergeCost(0.0f);
5048	return leaf->GetViewCell();
5049	}
5050
5051
5052	BspInterior interior = static_cast<BspInterior >(root);
5053	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5054
5055	// evaluate merge cost for priority traversal
5056	float mergeCost = 1.0f / (float)root->mTimeStamp;
5057	viewCellInterior->SetMergeCost(mergeCost);
5058
5059	float volume = 0;
5060
5061	BspNode *front = interior->GetFront();
5062	BspNode *back = interior->GetBack();
5063
5064
5065	ObjectPvs frontPvs, backPvs;
5066
5067	//-- recursivly compute child hierarchies
5068	ViewCell *backVc = ConstructSpatialMergeTree(back);
5069	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5070
5071
5072	viewCellInterior->SetupChildLink(backVc);
5073	viewCellInterior->SetupChildLink(frontVc);
5074
5075	volume += backVc->GetVolume();
5076	volume += frontVc->GetVolume();
5077
5078	viewCellInterior->SetVolume(volume);
5079
5080	return viewCellInterior;
5081	}
5082
5083
5084	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5085	{
5086	if (!ViewCellsConstructed())
5087	return ViewCellsManager::GetViewPoint(viewPoint);
5088
5089	// TODO: set reasonable limit
5090	const int limit = 20;
5091
5092	for (int i = 0; i < limit; ++ i)
5093	{
5094	viewPoint = mViewSpaceBox.GetRandomPoint();
5095	if (mVspBspTree->ViewPointValid(viewPoint))
5096	{
5097	return true;
5098	}
5099	}
5100
5101	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5102	return false;
5103	}
5104
5105
5106	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5107	{
5108	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5109	// validy update in preprocessor for all managers)
5110	return ViewCellsManager::ViewPointValid(viewPoint);
5111
5112	// return mViewSpaceBox.IsInside(viewPoint) &&
5113	// mVspBspTree->ViewPointValid(viewPoint);
5114	}
5115
5116
5117	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
5118	const VssRayContainer &sampleRays)
5119	{
5120	if (!ViewCellsConstructed())
5121	return;
5122
5123	VssRayContainer visRays;
5124	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5125
5126	if (1)
5127	{
5128	//////////////////
5129	//-- export final view cell partition
5130
5131	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5132
5133	if (exporter)
5134	{
5135	cout << "exporting view cells after post process ... ";
5136
5137	if (0)
5138	{ // export view space box
5139	exporter->SetWireframe();
5140	exporter->ExportBox(mViewSpaceBox);
5141	exporter->SetFilled();
5142	}
5143
5144	Material m;
5145	m.mDiffuseColor.r = 0.0f;
5146	m.mDiffuseColor.g = 0.5f;
5147	m.mDiffuseColor.b = 0.5f;
5148
5149	exporter->SetForcedMaterial(m);
5150
5151	if (1 && mExportGeometry)
5152	{
5153	exporter->ExportGeometry(objects);
5154	}
5155
5156	if (0 && mExportRays)
5157	{
5158	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
5159	}
5160	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5161
5162	delete exporter;
5163	cout << "finished" << endl;
5164	}
5165	}
5166
5167	////////////////
5168	//-- visualization of the BSP splits
5169
5170	bool exportSplits = false;
5171	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
5172
5173	if (exportSplits)
5174	{
5175	cout << "exporting splits ... ";
5176	ExportSplits(objects, visRays);
5177	cout << "finished" << endl;
5178	}
5179
5180	////////
5181	//-- export single view cells
5182
5183	int leafOut;
5184	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5185	const int raysOut = 100;
5186
5187	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5188	}
5189
5190
5191	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
5192	const VssRayContainer &rays)
5193	{
5194	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
5195
5196	if (exporter)
5197	{
5198	Material m;
5199	m.mDiffuseColor = RgbColor(1, 0, 0);
5200	exporter->SetForcedMaterial(m);
5201	exporter->SetWireframe();
5202
5203	exporter->ExportBspSplits(*mVspBspTree, true);
5204
5205	// take forced material, else big scenes cannot be viewed
5206	m.mDiffuseColor = RgbColor(0, 1, 0);
5207	exporter->SetForcedMaterial(m);
5208	exporter->SetFilled();
5209
5210	exporter->ResetForcedMaterial();
5211
5212	// export rays
5213	if (mExportRays)
5214	{
5215	exporter->ExportRays(rays, RgbColor(1, 1, 0));
5216	}
5217
5218	if (mExportGeometry)
5219	{
5220	exporter->ExportGeometry(objects);
5221	}
5222	delete exporter;
5223	}
5224	}
5225
5226
5227	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5228	const int maxViewCells,
5229	const bool sortViewCells,
5230	const bool exportPvs,
5231	const bool exportRays,
5232	const int maxRays,
5233	const string &prefix,
5234	VssRayContainer *visRays)
5235	{
5236	if (sortViewCells)
5237	{
5238	// sort view cells to visualize the largest view cells
5239	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
5240	}
5241
5242	//////////
5243	//-- export some view cells for visualization
5244
5245	ViewCell::NewMail();
5246	const int limit = min(maxViewCells, (int)mViewCells.size());
5247
5248	for (int i = 0; i < limit; ++ i)
5249	{
5250	cout << "creating output for view cell " << i << " ... ";
5251
5252	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
5253	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
5254
5255	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
5256	continue;
5257
5258	vc->Mail();
5259
5260	ObjectPvs pvs;
5261	mViewCellsTree->GetPvs(vc, pvs);
5262
5263	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5264	Exporter *exporter = Exporter::GetExporter(s);
5265
5266	const float pvsCost = mViewCellsTree->GetTrianglesInPvs(vc);
5267	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
5268
5269	if (exportRays)
5270	{
5271	////////////
5272	//-- export rays piercing this view cell
5273
5274	// take rays stored with the view cells during subdivision
5275	VssRayContainer vcRays;
5276	VssRayContainer collectRays;
5277
5278	// collect initial view cells
5279	ViewCellContainer leaves;
5280	mViewCellsTree->CollectLeaves(vc, leaves);
5281
5282	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5283	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5284	{
5285	BspLeaf vcLeaf = static_cast<BspViewCell >(*vit)->mLeaves[0];
5286	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5287
5288	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5289	{
5290	collectRays.push_back(*rit);
5291	}
5292	}
5293
5294	const int raysOut = min((int)collectRays.size(), maxRays);
5295
5296	// prepare some rays for visualization
5297	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5298	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5299	{
5300	const float p = RandomValue(0.0f, (float)collectRays.size());
5301
5302	if (p < raysOut)
5303	{
5304	vcRays.push_back(*rit);
5305	}
5306	}
5307
5308	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5309	}
5310
5311	////////////////
5312	//-- export view cell geometry
5313
5314	exporter->SetWireframe();
5315
5316	Material m;//= RandomMaterial();
5317	m.mDiffuseColor = RgbColor(0, 1, 0);
5318	exporter->SetForcedMaterial(m);
5319
5320	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5321	exporter->SetFilled();
5322
5323	if (exportPvs)
5324	{
5325	Intersectable::NewMail();
5326	ObjectPvsIterator pit = pvs.GetIterator();
5327
5328	cout << endl;
5329
5330	// output PVS of view cell
5331	while (pit.HasMoreEntries())
5332	{
5333	Intersectable *intersect = pit.Next();
5334
5335	if (!intersect->Mailed())
5336	{
5337	intersect->Mail();
5338
5339	m = RandomMaterial();
5340	exporter->SetForcedMaterial(m);
5341	exporter->ExportIntersectable(intersect);
5342	}
5343	}
5344	cout << endl;
5345	}
5346
5347	DEL_PTR(exporter);
5348	cout << "finished" << endl;
5349	}
5350	}
5351
5352
5353	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
5354	{
5355	Exporter *exporter = Exporter::GetExporter("filter.x3d");
5356
5357	Vector3 bsize = mViewSpaceBox.Size();
5358	const Vector3 viewPoint(mViewSpaceBox.Center());
5359	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
5360	const Vector3 width = Vector3(w);
5361
5362	PrVs testPrVs;
5363
5364	if (exporter)
5365	{
5366	ViewCellContainer viewCells;
5367
5368	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
5369
5370	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
5371
5372	exporter->SetWireframe();
5373
5374	exporter->SetForcedMaterial(RgbColor(1,1,1));
5375	exporter->ExportBox(tbox);
5376
5377	exporter->SetFilled();
5378
5379	exporter->SetForcedMaterial(RgbColor(0,1,0));
5380	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
5381
5382	//exporter->ResetForcedMaterial();
5383	exporter->SetForcedMaterial(RgbColor(0,0,1));
5384	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
5385
5386	exporter->SetForcedMaterial(RgbColor(1,0,0));
5387	exporter->ExportGeometry(objects);
5388
5389	delete exporter;
5390	}
5391	}
5392
5393
5394	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5395	ViewCellContainer &viewCells) const
5396	{
5397	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
5398	}
5399
5400
5401	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
5402	const Vector3 &termination,
5403	ViewCellContainer &viewcells)
5404	{
5405	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
5406	}
5407
5408
5409	bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
5410	const Vector3 &termination,
5411	ViewCell *viewCell)
5412	{
5413	return false;
5414	}
5415
5416
5417	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
5418	{
5419	int numSamples;
5420
5421	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
5422	cout << "samples" << numSamples << endl;
5423
5424	vector<RenderCostSample> samples;
5425
5426	if (!mPreprocessor->GetRenderer())
5427	return;
5428
5429	//start the view point queries
5430	long startTime = GetTime();
5431	cout << "starting sampling of render cost ... ";
5432
5433	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
5434
5435	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
5436
5437
5438	// for each sample:
5439	// find view cells associated with the samples
5440	// store the sample pvs with the pvs associated with the view cell
5441	//
5442	// for each view cell:
5443	// compute difference point sampled pvs - view cell pvs
5444	// export geometry with color coded pvs difference
5445
5446	std::map<ViewCell *, ObjectPvs> sampleMap;
5447
5448	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5449
5450	for (rit = samples.begin(); rit != rit_end; ++ rit)
5451	{
5452	RenderCostSample sample = *rit;
5453
5454	ViewCell *vc = GetViewCell(sample.mPosition);
5455
5456	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5457
5458	if (it == sampleMap.end())
5459	{
5460	sampleMap[vc] = sample.mPvs;
5461	}
5462	else
5463	{
5464	(*it).second.MergeInPlace(sample.mPvs);
5465	}
5466	}
5467
5468	// visualize the view cells
5469	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5470
5471	Material m;//= RandomMaterial();
5472
5473	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5474	{
5475	ViewCell vc = (vit).first;
5476
5477	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5478	const int pvsPtSamples = (*vit).second.GetSize();
5479
5480	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5481	m.mDiffuseColor.b = 1.0f;
5482	//exporter->SetForcedMaterial(m);
5483	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5484
5485	/* // counting the pvss
5486	for (rit = samples.begin(); rit != rit_end; ++ rit)
5487	{
5488	RenderCostSample sample = *rit;
5489	ViewCell *vc = GetViewCell(sample.mPosition);
5490
5491	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5492	Mesh *hMesh = CreateMeshFromBox(box);
5493
5494	DEL_PTR(hMesh);
5495	}
5496	*/
5497	}
5498	}
5499
5500
5501	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5502	ViewCell *vc,
5503	const AxisAlignedBox3 *sceneBox,
5504	const AxisAlignedPlane *clipPlane
5505	) const
5506	{
5507	if (clipPlane)
5508	{
5509	const Plane3 plane = clipPlane->GetPlane();
5510
5511	ViewCellContainer leaves;
5512	mViewCellsTree->CollectLeaves(vc, leaves);
5513	ViewCellContainer::const_iterator it, it_end = leaves.end();
5514
5515	for (it = leaves.begin(); it != it_end; ++ it)
5516	{
5517	BspNodeGeometry geom;
5518	BspNodeGeometry front;
5519	BspNodeGeometry back;
5520
5521	mVspBspTree->ConstructGeometry(*it, geom);
5522
5523	const float eps = 0.0001f;
5524	const int cf = geom.Side(plane, eps);
5525
5526	if (cf == -1)
5527	{
5528	exporter->ExportPolygons(geom.GetPolys());
5529	}
5530	else if (cf == 0)
5531	{
5532	geom.SplitGeometry(front,
5533	back,
5534	plane,
5535	mViewSpaceBox,
5536	eps);
5537
5538	if (back.Valid())
5539	{
5540	exporter->ExportPolygons(back.GetPolys());
5541	}
5542	}
5543	}
5544	}
5545	else
5546	{
5547	// export mesh if available
5548	// TODO: some bug here?
5549	if (1 && vc->GetMesh())
5550	{
5551	exporter->ExportMesh(vc->GetMesh());
5552	}
5553	else
5554	{
5555	BspNodeGeometry geom;
5556	mVspBspTree->ConstructGeometry(vc, geom);
5557	exporter->ExportPolygons(geom.GetPolys());
5558	}
5559	}
5560	}
5561
5562
5563	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5564	{
5565	ViewCellContainer leaves;
5566	mViewCellsTree->CollectLeaves(vc, leaves);
5567
5568	int maxDist = 0;
5569
5570	// compute max height difference
5571	for (int i = 0; i < (int)leaves.size(); ++ i)
5572	{
5573	for (int j = 0; j < (int)leaves.size(); ++ j)
5574	{
5575	BspLeaf leaf = static_cast<BspViewCell >(leaves[i])->mLeaves[0];
5576
5577	if (i != j)
5578	{
5579	BspLeaf leaf2 =static_cast<BspViewCell >(leaves[j])->mLeaves[0];
5580	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5581
5582	if (dist > maxDist)
5583	maxDist = dist;
5584	}
5585	}
5586	}
5587
5588	return maxDist;
5589	}
5590
5591
5592	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5593	{
5594	if (!ViewCellsConstructed())
5595	return NULL;
5596
5597	if (!mViewSpaceBox.IsInside(point))
5598	return NULL;
5599
5600	return mVspBspTree->GetViewCell(point, active);
5601	}
5602
5603
5604	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5605	{
5606	BspNodeGeometry geom;
5607	mVspBspTree->ConstructGeometry(vc, geom);
5608
5609	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5610
5611	IncludeNodeGeomInMesh(geom, *mesh);
5612	mesh->ComputeBoundingBox();
5613
5614	vc->SetMesh(mesh);
5615	}
5616
5617
5618	int VspBspViewCellsManager::CastBeam(Beam &beam)
5619	{
5620	return mVspBspTree->CastBeam(beam);
5621	}
5622
5623
5624	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5625	const bool createMesh)
5626	{
5627	float area = 0;
5628	float volume = 0;
5629
5630	ViewCellContainer leaves;
5631	mViewCellsTree->CollectLeaves(viewCell, leaves);
5632
5633	ViewCellContainer::const_iterator it, it_end = leaves.end();
5634
5635	for (it = leaves.begin(); it != it_end; ++ it)
5636	{
5637	BspNodeGeometry geom;
5638	mVspBspTree->ConstructGeometry(*it, geom);
5639
5640	const float lVol = geom.GetVolume();
5641	const float lArea = geom.GetArea();
5642
5643	area += lArea;
5644	volume += lVol;
5645
5646	if (createMesh)
5647	CreateMesh(*it);
5648	}
5649
5650	viewCell->SetVolume(volume);
5651	viewCell->SetArea(area);
5652	}
5653
5654
5655	void VspBspViewCellsManager::TestSubdivision()
5656	{
5657	ViewCellContainer leaves;
5658	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5659
5660	ViewCellContainer::const_iterator it, it_end = leaves.end();
5661
5662	const float vol = mViewSpaceBox.GetVolume();
5663	float subdivVol = 0;
5664	float newVol = 0;
5665
5666	for (it = leaves.begin(); it != it_end; ++ it)
5667	{
5668	BspNodeGeometry geom;
5669	mVspBspTree->ConstructGeometry(*it, geom);
5670
5671	const float lVol = geom.GetVolume();
5672
5673	newVol += lVol;
5674	subdivVol += (*it)->GetVolume();
5675
5676	float thres = 0.9f;
5677	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5678	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5679	}
5680
5681	Debug << "exact volume: " << vol << endl;
5682	Debug << "subdivision volume: " << subdivVol << endl;
5683	Debug << "new volume: " << newVol << endl;
5684	}
5685
5686
5687	void VspBspViewCellsManager::PrepareLoadedViewCells()
5688	{
5689	// TODO: do I still need this here?
5690	if (0) mVspBspTree->RepairViewCellsLeafLists();
5691	}
5692
5693
5694
5695	/************************************************************************/
5696	/* VspOspViewCellsManager implementation */
5697	/************************************************************************/
5698
5699
5700	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5701	const string &hierarchyType)
5702	: ViewCellsManager(vcTree)
5703	{
5704	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5705	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5706
5707	Debug << "compressing objects: " << mCompressObjects << endl;
5708	cout << "compressing objects: " << mCompressObjects << endl;
5709
5710	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5711
5712	mHierarchyManager->SetViewCellsManager(this);
5713	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5714	}
5715
5716
5717	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5718	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5719	{
5720	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5721	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5722
5723	Debug << "compressing objects: " << mCompressObjects << endl;
5724	cout << "compressing objects: " << mCompressObjects << endl;
5725
5726	mHierarchyManager->SetViewCellsManager(this);
5727	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5728	}
5729
5730
5731	Intersectable *VspOspViewCellsManager::GetIntersectable(const VssRay &ray,
5732	const bool isTermination) const
5733	{
5734	if (mUseKdPvs)
5735	return ViewCellsManager::GetIntersectable(ray, isTermination);
5736	else
5737	return mHierarchyManager->GetIntersectable(ray, isTermination);
5738	}
5739
5740
5741	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5742	{
5743	HierarchyManager *hierarchyManager;
5744
5745	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5746	{
5747	Debug << "hierarchy manager: osp" << endl;
5748	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5749	}
5750	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5751	{
5752	Debug << "hierarchy manager: bvh" << endl;
5753	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5754	}
5755	else // only view space partition
5756	{
5757	Debug << "hierarchy manager: obj" << endl;
5758	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5759	}
5760
5761	return hierarchyManager;
5762	}
5763
5764
5765	VspOspViewCellsManager::~VspOspViewCellsManager()
5766	{
5767	DEL_PTR(mHierarchyManager);
5768	}
5769
5770
5771	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5772	{
5773	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5774	}
5775
5776
5777	void VspOspViewCellsManager::CollectViewCells()
5778	{
5779	// view cells tree constructed
5780	if (!ViewCellsTreeConstructed())
5781	{
5782	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5783	}
5784	else
5785	{ // we can use the view cells tree hierarchy to get the right set
5786	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5787	}
5788	}
5789
5790
5791	bool VspOspViewCellsManager::ViewCellsConstructed() const
5792	{
5793	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5794	}
5795
5796
5797	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5798	{
5799	return new VspViewCell(mesh);
5800	}
5801
5802
5803	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5804	const VssRayContainer &rays)
5805	{
5806	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5807
5808	// skip rest if view cells were already constructed
5809	if (ViewCellsConstructed())
5810	return 0;
5811
5812	int sampleContributions = 0;
5813	VssRayContainer sampleRays;
5814
5815	int limit = min (mInitialSamples, (int)rays.size());
5816
5817	VssRayContainer constructionRays;
5818	VssRayContainer savedRays;
5819
5820	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5821	<< ", actual rays: " << (int)rays.size() << endl;
5822
5823	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5824
5825	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5826	Debug << "saved rays: " << (int)savedRays.size() << endl;
5827
5828	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5829
5830	#if TEST_EVALUATION
5831	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5832	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5833	{
5834	storedRays.push_back(new VssRay((tit)));
5835	}
5836	#endif
5837
5838	/////////////////////////
5839	//-- print satistics for subdivision and view cells
5840
5841	Debug << endl << endl << *mHierarchyManager << endl;
5842
5843	ResetViewCells();
5844	//Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5845
5846	//////////////
5847	//-- recast rest of rays
5848
5849	const long startTime = GetTime();
5850	cout << "Computing remaining ray contributions ... ";
5851
5852	if (SAMPLE_AFTER_SUBDIVISION)
5853	ComputeSampleContributions(savedRays, true, false);
5854
5855	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5856	<< " secs" << endl;
5857
5858	if (0)
5859	{
5860	// real meshes are constructed at this stage
5861	cout << "finalizing view cells ... ";
5862	FinalizeViewCells(true);
5863	cout << "finished" << endl;
5864	}
5865
5866	return sampleContributions;
5867	}
5868
5869
5870	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5871	const VssRayContainer &rays)
5872	{
5873	if (!ViewCellsConstructed())
5874	{
5875	Debug << "post process error: no view cells constructed" << endl;
5876	return 0;
5877	}
5878
5879	// if view cells were already constructed before post processing step
5880	// (e.g., because they were loaded), we are finished
5881	if (mViewCellsFinished)
5882	{
5883	FinalizeViewCells(true);
5884	EvaluateViewCellsStats();
5885
5886	return 0;
5887	}
5888
5889	// check if new view cells turned invalid
5890	int minPvs, maxPvs;
5891
5892	if (0)
5893	{
5894	minPvs = mMinPvsSize;
5895	maxPvs = mMaxPvsSize;
5896	}
5897	else
5898	{
5899	// problem matt: why did I start here from zero?
5900	minPvs = 0;
5901	maxPvs = mMaxPvsSize;
5902	}
5903
5904	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5905	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5906
5907	SetValidity(minPvs, maxPvs);
5908
5909
5910	// area is not up to date, has to be recomputed
5911	mTotalAreaValid = false;
5912	VssRayContainer postProcessRays;
5913	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5914
5915	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5916
5917
5918	// compute tree by merging the nodes of the spatial hierarchy
5919	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5920	mViewCellsTree->SetRoot(root);
5921
5922	//////////////////////////
5923	//-- update pvs up to the root of the hierarchy
5924
5925	ObjectPvs pvs;
5926	UpdatePvsForEvaluation(root, pvs);
5927
5928
5929	//////////////////////
5930	//-- render simulation after merge + refine
5931
5932	cout << "\nview cells partition render time before compress" << endl << endl;
5933	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5934	SimulationStatistics ss;
5935	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5936	cout << ss << endl;
5937
5938
5939	mHierarchyManager->CreateUniqueObjectIds();
5940
5941	///////////
5942	//-- compression
5943
5944	if (0) CompressViewCells();
5945
5946	/////////////
5947	//-- some tasks still to do on the view cells:
5948	//-- Compute meshes from view cell geometry, evaluate volume and / or area
5949
5950	if (1) FinalizeViewCells(true);
5951
5952	return 0;
5953	}
5954
5955
5956	int VspOspViewCellsManager::GetType() const
5957	{
5958	return VSP_OSP;
5959	}
5960
5961
5962	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5963	{
5964	// terminate recursion
5965	if (root->IsLeaf())
5966	{
5967	VspLeaf leaf = static_cast<VspLeaf >(root);
5968	leaf->GetViewCell()->SetMergeCost(0.0f);
5969	return leaf->GetViewCell();
5970	}
5971
5972	VspInterior interior = static_cast<VspInterior >(root);
5973	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5974
5975	// evaluate merge cost for priority traversal
5976	const float mergeCost = -(float)root->mTimeStamp;
5977	viewCellInterior->SetMergeCost(mergeCost);
5978
5979	float volume = 0;
5980
5981	VspNode *front = interior->GetFront();
5982	VspNode *back = interior->GetBack();
5983
5984	ObjectPvs frontPvs, backPvs;
5985
5986	/////////
5987	//-- recursivly compute child hierarchies
5988
5989	ViewCell *backVc = ConstructSpatialMergeTree(back);
5990	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5991
5992	viewCellInterior->SetupChildLink(backVc);
5993	viewCellInterior->SetupChildLink(frontVc);
5994
5995	volume += backVc->GetVolume();
5996	volume += frontVc->GetVolume();
5997
5998	viewCellInterior->SetVolume(volume);
5999
6000	return viewCellInterior;
6001	}
6002
6003
6004	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
6005	{
6006	if (!ViewCellsConstructed())
6007	return ViewCellsManager::GetViewPoint(viewPoint);
6008
6009	// TODO: set reasonable limit
6010	const int limit = 20;
6011
6012	for (int i = 0; i < limit; ++ i)
6013	{
6014	viewPoint = mViewSpaceBox.GetRandomPoint();
6015
6016	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
6017	{
6018	return true;
6019	}
6020	}
6021
6022	Debug << "failed to find valid view point, taking " << viewPoint << endl;
6023	return false;
6024	}
6025
6026
6027	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
6028	ViewCell *vc,
6029	const AxisAlignedBox3 *sceneBox,
6030	const AxisAlignedPlane *clipPlane
6031	) const
6032	{
6033	Plane3 plane;
6034	if (clipPlane)
6035	{
6036	// arbitrary plane definition
6037	plane = clipPlane->GetPlane();
6038	}
6039
6040	ViewCellContainer leaves;
6041	mViewCellsTree->CollectLeaves(vc, leaves);
6042
6043	ViewCellContainer::const_iterator it, it_end = leaves.end();
6044
6045	for (it = leaves.begin(); it != it_end; ++ it)
6046	{
6047	VspViewCell vspVc = static_cast<VspViewCell >(*it);
6048	VspLeaf *l = vspVc->mLeaves[0];
6049
6050	const AxisAlignedBox3 box =
6051	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
6052
6053	if (sceneBox && !Overlap(*sceneBox, box))
6054	continue;
6055
6056	if (clipPlane)
6057	{
6058	if (box.Side(plane) == -1)
6059	{
6060	exporter->ExportBox(box);
6061	}
6062	else if (box.Side(plane) == 0)
6063	{
6064	// intersection
6065	AxisAlignedBox3 fbox, bbox;
6066	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
6067	exporter->ExportBox(bbox);
6068	}
6069	}
6070	else
6071	{
6072	exporter->ExportBox(box);
6073	}
6074	}
6075	}
6076
6077
6078	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
6079	{
6080	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
6081	// validy update in preprocessor for all managers)
6082	return ViewCellsManager::ViewPointValid(viewPoint);
6083
6084	// return mViewSpaceBox.IsInside(viewPoint) &&
6085	// mVspTree->ViewPointValid(viewPoint);
6086	}
6087
6088
6089	float VspOspViewCellsManager::UpdateObjectCosts()
6090	{
6091	float maxRenderCost = 0;
6092
6093	cout << "updating object pvs cost ... ";
6094	const long startTime = GetTime();
6095
6096	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
6097
6098	Intersectable::NewMail();
6099
6100	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
6101
6102	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
6103	{
6104	ViewCell vc = vit;
6105
6106	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
6107
6108	// output PVS of view cell
6109	while (pit.HasMoreEntries())
6110	{
6111	Intersectable *obj = pit.Next();
6112
6113	BvhNode node = static_cast<BvhNode >(obj);
6114
6115	// hack!!
6116	if (!node->IsLeaf())
6117	{
6118	cout << "error, can only process leaves" << endl;
6119	return 0;
6120	}
6121
6122	if (!node->Mailed())
6123	{
6124	node->Mail();
6125	node->mRenderCost = 0;
6126	}
6127
6128	const float rc = (float)((BvhLeaf *)node)->mObjects.size();
6129
6130	node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
6131
6132	if (node->mRenderCost > maxRenderCost)
6133	maxRenderCost = node->mRenderCost;
6134	}
6135	}
6136
6137	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
6138
6139	return maxRenderCost;
6140	}
6141
6142
6143	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
6144	const VssRayContainer &sampleRays)
6145	{
6146	if (!ViewCellsConstructed())
6147	return;
6148
6149	VssRayContainer visRays;
6150	GetRaySets(sampleRays, mVisualizationSamples, visRays);
6151
6152	////////////
6153	//-- export final view cells
6154
6155	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
6156
6157	Vector3 scale(0.9f, 0.9f, 0.9f);
6158	//Vector3 scale(1.0f, 1.0f, 1.0f);
6159
6160	if (exporter)
6161	{
6162	// clamp to a scene boudning box
6163	if (CLAMP_TO_BOX)
6164	exporter->mClampToBox = true;
6165
6166	const long starttime = GetTime();
6167	cout << "exporting final view cells (after initial construction + post process) ... " << endl;
6168
6169	// matt: hack for clamping scene
6170	AxisAlignedBox3 bbox = mViewSpaceBox;
6171	bbox.Scale(scale);
6172
6173	if (1 && mExportRays)
6174	{
6175	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
6176	}
6177
6178	// hack color code
6179	const int savedColorCode = mColorCode;
6180
6181	EvaluateViewCellsStats();
6182	const int colorCode = 0;
6183
6184	const float maxRenderCost = -1;//UpdateObjectCosts();
6185	const bool exportBounds = false;
6186
6187	//cout << "maxRenderCost: " << maxRenderCost << endl;
6188	if (1)
6189	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
6190	objects,
6191	CLAMP_TO_BOX ? &bbox : NULL,
6192	maxRenderCost,
6193	exportBounds);
6194
6195	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6196	ExportViewCellsForViz(exporter, NULL, colorCode, GetClipPlane());
6197
6198	delete exporter;
6199
6200	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6201	}
6202
6203	if (1)
6204	{
6205	exporter = Exporter::GetExporter("final_object_partition.wrl");
6206
6207	if (exporter)
6208	{
6209	if (CLAMP_TO_BOX)
6210	{
6211	exporter->mClampToBox = true;
6212	}
6213
6214	const long starttime = GetTime();
6215	cout << "exporting final objects (after initial construction + post process) ... ";
6216
6217	// matt: hack for clamping scene
6218	AxisAlignedBox3 bbox = mViewSpaceBox;
6219	bbox.Scale(scale);
6220
6221	// hack color code (show pvs size)
6222	const int savedColorCode = mColorCode;
6223
6224	EvaluateViewCellsStats();
6225	mColorCode = 1; // 0 = random, 1 = export pvs
6226
6227	// don't visualize render cost
6228	const float maxRenderCost = -1;
6229	//const bool exportBounds = true;
6230	const bool exportBounds = false;
6231
6232	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
6233	objects,
6234	CLAMP_TO_BOX ? &bbox : NULL,
6235	maxRenderCost,
6236	exportBounds);
6237
6238
6239	delete exporter;
6240
6241	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6242	mColorCode = savedColorCode;
6243	}
6244	}
6245
6246	// export some view cells
6247	int leafOut;
6248	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
6249
6250	const bool sortViewCells = false;
6251	const bool exportPvs = true;
6252	const bool exportRays = true;
6253	const int raysOut = 100;
6254
6255	ExportSingleViewCells(objects,
6256	leafOut,
6257	sortViewCells,
6258	exportPvs,
6259	exportRays,
6260	raysOut,
6261	"");
6262	}
6263
6264
6265	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
6266	const int maxViewCells,
6267	const bool sortViewCells,
6268	const bool exportPvs,
6269	const bool exportRays,
6270	const int maxRays,
6271	const string &prefix,
6272	VssRayContainer *visRays)
6273	{
6274	if (sortViewCells)
6275	{
6276	// sort view cells to visualize the view cells with highest render cost
6277	sort(mViewCells.begin(), mViewCells.end(), LargerRenderCost);
6278	}
6279
6280	ViewCell::NewMail();
6281	const int limit = min(maxViewCells, (int)mViewCells.size());
6282
6283	cout << "\nExporting " << limit << " single view cells: " << endl;
6284
6285	for (int i = 0; i < limit; ++ i)
6286	{
6287	cout << "creating output for view cell " << i << " ... ";
6288
6289	// largest view cell pvs first of random view cell
6290	ViewCell *vc = sortViewCells ?
6291	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
6292
6293	if (vc->Mailed()) // view cell already processed
6294	continue;
6295
6296	vc->Mail();
6297
6298	ObjectPvs pvs;
6299	mViewCellsTree->GetPvs(vc, pvs);
6300
6301	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
6302	Exporter *exporter = Exporter::GetExporter(s);
6303
6304	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetTrianglesInPvs(vc) << endl;
6305
6306	if (exportPvs)
6307	{
6308	Material m;
6309	Intersectable::NewMail();
6310
6311	ObjectPvsIterator pit = pvs.GetIterator();
6312
6313	// output PVS of view cell
6314	while (pit.HasMoreEntries())
6315	{
6316	Intersectable *intersect = pit.Next();
6317
6318	if (!intersect->Mailed())
6319	{
6320	m = RandomMaterial();
6321	exporter->SetForcedMaterial(m);
6322
6323	exporter->ExportIntersectable(intersect);
6324	intersect->Mail();
6325	}
6326	}
6327	}
6328
6329	if (exportRays)
6330	{
6331	////////////
6332	//-- export the sample rays
6333
6334	// output rays stored with the view cells during subdivision
6335	VssRayContainer vcRays;
6336	VssRayContainer collectRays;
6337
6338	// collect intial view cells
6339	ViewCellContainer leaves;
6340	mViewCellsTree->CollectLeaves(vc, leaves);
6341
6342	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
6343
6344	for (vit = leaves.begin(); vit != vit_end; ++ vit)
6345	{
6346	VspLeaf vcLeaf = static_cast<VspViewCell >(*vit)->mLeaves[0];
6347	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
6348
6349	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
6350	{
6351	collectRays.push_back(*rit);
6352	}
6353	}
6354
6355	const int raysOut = min((int)collectRays.size(), maxRays);
6356
6357	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
6358
6359	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
6360	{
6361	const float p = RandomValue(0.0f, (float)collectRays.size());
6362
6363	if (p < raysOut)
6364	vcRays.push_back(*rit);
6365	}
6366
6367	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
6368	}
6369
6370
6371	/////////////////
6372	//-- export view cell geometry
6373
6374	exporter->SetWireframe();
6375
6376	Material m;
6377	m.mDiffuseColor = RgbColor(0, 1, 0);
6378	exporter->SetForcedMaterial(m);
6379
6380	ExportViewCellGeometry(exporter, vc, NULL, NULL);
6381	exporter->SetFilled();
6382
6383	DEL_PTR(exporter);
6384	cout << "finished" << endl;
6385	}
6386
6387	cout << endl;
6388	}
6389
6390
6391	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
6392	ViewCellContainer &viewCells) const
6393	{
6394	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
6395	}
6396
6397
6398	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
6399	const Vector3 &termination,
6400	ViewCellContainer &viewcells)
6401	{
6402	return mHierarchyManager->CastLineSegment(origin, termination, viewcells);
6403	}
6404
6405
6406	bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
6407	const Vector3 &termination,
6408	ViewCell *viewCell)
6409	{
6410	return false;
6411	}
6412
6413
6414	bool VspOspViewCellsManager::ExportViewCells(const string filename,
6415	const bool exportPvs,
6416	const ObjectContainer &objects)
6417	{
6418	// no view cells were computed
6419	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6420	return false;
6421
6422	if (strstr(filename.c_str(), ".bn"))
6423	{
6424	return ExportViewCellsBinary(filename, exportPvs, objects);
6425	}
6426
6427	//cout << "exporting binary" << endl; string fname("test.vc"); return ExportViewCellsBinary(fname, exportPvs, objects);
6428
6429	const long starttime = GetTime();
6430	cout << "exporting view cells to xml ... ";
6431
6432	OUT_STREAM stream(filename.c_str());
6433
6434	// we need unique ids for each view cell
6435	CreateUniqueViewCellIds();
6436
6437	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6438	stream << "<VisibilitySolution>" << endl;
6439
6440	if (exportPvs)
6441	{
6442	///////////////
6443	//-- export bounding boxes
6444	//-- we need the boxes to identify objects in the target engine
6445
6446	if (mUseKdPvs)
6447	{
6448	stream << "<BoundingBoxes>" << endl;
6449
6450	int id = 0;
6451	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
6452
6453	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
6454	{
6455	Intersectable obj = (kit);
6456	const AxisAlignedBox3 box = obj->GetBox();
6457
6458	// set kd node id
6459	obj->SetId(id);
6460
6461	stream << "<BoundingBox" << " id=\"" << id << "\""
6462	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
6463	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
6464	}
6465
6466	stream << "</BoundingBoxes>" << endl;
6467	}
6468	else
6469	{
6470	mHierarchyManager->ExportBoundingBoxes(stream, objects);
6471	}
6472	}
6473
6474
6475	//////////////////////////
6476	//-- export the view cells and the pvs
6477
6478	const int numViewCells = mCurrentViewCellsStats.viewCells;
6479
6480	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6481	mViewCellsTree->Export(stream, exportPvs);
6482	stream << "</ViewCells>" << endl;
6483
6484
6485	/////////////////
6486	//-- export the view space hierarchy
6487
6488	stream << "<ViewSpaceHierarchy type=\"vsp\""
6489	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6490	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6491
6492	mHierarchyManager->GetVspTree()->Export(stream);
6493	stream << "</ViewSpaceHierarchy>" << endl;
6494
6495	/////////////////
6496	//-- export the object space hierarchy
6497
6498	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6499
6500	stream << "</VisibilitySolution>" << endl;
6501	stream.close();
6502
6503	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6504	return true;
6505	}
6506
6507
6508	bool VspOspViewCellsManager::ExportViewCellsBinary(const string filename,
6509	const bool exportPvs,
6510	const ObjectContainer &objects)
6511	{
6512	// no view cells constructed yet
6513	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6514	return false;
6515
6516	const long starttime = GetTime();
6517	cout << "exporting view cells to binary format ... ";
6518
6519	OUT_STREAM stream(filename.c_str());
6520
6521	// we need unique ids for each view cell
6522	CreateUniqueViewCellIds();
6523
6524	int numBoxes = mPreprocessor->mKdTree->mKdIntersectables.size();
6525	stream.write(reinterpret_cast<char *>(&numBoxes), sizeof(int));
6526
6527
6528	///////////////
6529	//-- export bounding boxes
6530
6531	// we use bounding box intersection to identify pvs objects in the target engine
6532	vector<KdIntersectable *>::const_iterator kit, kit_end = mPreprocessor->mKdTree->mKdIntersectables.end();
6533
6534	int id = 0;
6535
6536	for (kit = mPreprocessor->mKdTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
6537	{
6538	Intersectable obj = (kit);
6539	// set the kd node id to identify the kd node as a pvs entry
6540	obj->SetId(id);
6541
6542	const AxisAlignedBox3 &box = obj->GetBox();
6543	Vector3 bmin = box.Min();
6544	Vector3 bmax = box.Max();
6545
6546	stream.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
6547	stream.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
6548	stream.write(reinterpret_cast<char *>(&id), sizeof(int));
6549	}
6550
6551	cout << "written " << numBoxes << " kd nodes" << endl;
6552
6553	///////////////
6554	//-- export the view cells and the pvs
6555
6556	int numViewCells = mViewCells.size();
6557	stream.write(reinterpret_cast<char *>(&numViewCells), sizeof(int));
6558
6559	Vector3 vmin = mViewSpaceBox.Min();
6560	Vector3 vmax = mViewSpaceBox.Max();
6561
6562	stream.write(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
6563	stream.write(reinterpret_cast<char *>(&vmax), sizeof(Vector3));
6564
6565
6566	//////////
6567	//-- export binary view cells
6568
6569	mViewCellsTree->ExportBinary(stream);
6570
6571
6572	/////////
6573	//-- export the view space hierarchy
6574
6575	mHierarchyManager->GetVspTree()->ExportBinary(stream);
6576
6577
6578	////////
6579	//-- export the object space hierarchy
6580
6581	//mHierarchyManager->ExportObjectSpaceHierarchyBinary();
6582
6583	stream.close();
6584
6585	//mHierarchyManager->GetVspTree()->TestOutput("output.txt");
6586
6587	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6588	return true;
6589	}
6590
6591
6592	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6593	const bool active) const
6594	{
6595	if (!ViewCellsConstructed())
6596	return NULL;
6597
6598	if (!mViewSpaceBox.IsInside(point))
6599	return NULL;
6600
6601	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6602	}
6603
6604
6605	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6606	{
6607	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6608
6609	ViewCellContainer leaves;
6610	mViewCellsTree->CollectLeaves(vc, leaves);
6611
6612	ViewCellContainer::const_iterator it, it_end = leaves.end();
6613
6614	for (it = leaves.begin(); it != it_end; ++ it)
6615	{
6616	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6617	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6618	IncludeBoxInMesh(box, *mesh);
6619	}
6620
6621	mesh->ComputeBoundingBox();
6622
6623	vc->SetMesh(mesh);
6624	}
6625
6626
6627	int VspOspViewCellsManager::CastBeam(Beam &beam)
6628	{
6629	// matt: TODO
6630	return 0;
6631	}
6632
6633
6634	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6635	{
6636	float area = 0;
6637	float volume = 0;
6638
6639	ViewCellContainer leaves;
6640	mViewCellsTree->CollectLeaves(viewCell, leaves);
6641
6642	ViewCellContainer::const_iterator it, it_end = leaves.end();
6643
6644	for (it = leaves.begin(); it != it_end; ++ it)
6645	{
6646	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6647
6648	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6649
6650	const float lVol = box.GetVolume();
6651	const float lArea = box.SurfaceArea();
6652
6653	area += lArea;
6654	volume += lVol;
6655
6656	CreateMesh(*it);
6657	}
6658
6659	viewCell->SetVolume(volume);
6660	viewCell->SetArea(area);
6661	}
6662
6663
6664	void VspOspViewCellsManager::PrepareLoadedViewCells()
6665	{
6666	// TODO
6667	}
6668
6669
6670	void VspOspViewCellsManager::PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6671	{
6672	const float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6673
6674	float fullmem = mem +
6675	(hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6676	hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6677
6678	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6679	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6680	}
6681
6682
6683	void VspOspViewCellsManager::CompressViewCells()
6684	{
6685	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6686	return;
6687
6688
6689	////////////
6690	//-- compression
6691
6692	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6693
6694	cout << "before compression: " << endl;
6695	Debug << "before compression: " << endl;
6696
6697	PrintCompressionStats(mHierarchyManager, pvsEntries);
6698
6699	if (mCompressObjects)
6700	{
6701	cout << "compressing in the objects: " << endl;
6702	Debug << "compressing in the objects: " << endl;
6703
6704	pvsEntries = mHierarchyManager->CompressObjectSpace();
6705	}
6706	else
6707	{
6708	cout << "compressing in the view space: " << endl;
6709	Debug << "compressing in the view space: " << endl;
6710
6711	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6712	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6713	}
6714
6715	PrintCompressionStats(mHierarchyManager, pvsEntries);
6716	}
6717
6718
6719	void VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box,
6720	ObjectContainer &objects)
6721	{
6722	mHierarchyManager->CollectObjects(box, objects);
6723	}
6724
6725
6726	void VspOspViewCellsManager::EvalViewCellPartition()
6727	{
6728	int samplesPerPass;
6729	int castSamples = 0;
6730	int oldSamples = 0;
6731	int samplesForStats;
6732	char statsPrefix[100];
6733	char suffix[100];
6734	int splitsStepSize;
6735
6736	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6737	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6738	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", mEvaluationSamples);
6739	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6740	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6741
6742	bool useHisto;
6743	int histoMem;
6744
6745	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6746	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6747
6748	Debug << "step size: " << splitsStepSize << endl;
6749	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6750	Debug << "view cell evaluation samples: " << mEvaluationSamples << endl;
6751	Debug << "view cell stats prefix: " << statsPrefix << endl;
6752
6753	cout << "reseting pvs ... ";
6754
6755	// reset pvs and start over from zero
6756	mViewCellsTree->ResetPvs();
6757
6758	cout << "finished" << endl;
6759	cout << "Evaluating view cell partition ... " << endl;
6760
6761	int pass = 0;
6762
6763	while (castSamples < mEvaluationSamples)
6764	{
6765	///////////////
6766	//-- we have to use uniform sampling strategy for construction rays
6767
6768	VssRayContainer evaluationSamples;
6769	const int samplingType = mEvaluationSamplingType;
6770
6771	long startTime = GetTime();
6772	Real timeDiff;
6773
6774	cout << "casting " << samplesPerPass << " samples ... ";
6775	Debug << "casting " << samplesPerPass << " samples ... ";
6776
6777	// use mixed distributions
6778	CastEvaluationSamples(samplesPerPass, evaluationSamples);
6779
6780	timeDiff = TimeDiff(startTime, GetTime());
6781	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6782	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6783
6784	// don't computed sample contributions
6785	// because already accounted for inside the mixture distribution!
6786
6787	castSamples += samplesPerPass;
6788
6789	if ((castSamples >= samplesForStats + oldSamples) \|\|
6790	(castSamples >= mEvaluationSamples))
6791	{
6792	oldSamples += samplesForStats;
6793
6794	///////////
6795	//-- output stats
6796
6797	sprintf(suffix, "-%09d-eval.log", castSamples);
6798	const string filename = string(statsPrefix) + string(suffix);
6799
6800	startTime = GetTime();
6801
6802	cout << "compute new statistics ... " << endl;
6803
6804	ofstream ofstr(filename.c_str());
6805	mHierarchyManager->EvaluateSubdivision(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6806
6807	timeDiff = TimeDiff(startTime, GetTime());
6808	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6809	cout << "*************************************" << endl;
6810
6811	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6812
6813	++ pass;
6814	}
6815
6816	disposeRays(evaluationSamples, NULL);
6817	}
6818
6819	////////////
6820	//-- histogram
6821
6822	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
6823	int histoStepSize;
6824
6825	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6826	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
6827
6828	if (useHisto)
6829	{
6830	// evaluate view cells in a histogram
6831	char str[64];
6832
6833	// hack: just show final view cells
6834	const int pass = (int)mViewCells.size();
6835
6836	//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
6837
6838	string filename;
6839
6840	cout << "computing histogram for " << pass << " view cells" << endl;
6841
6842	///////////////////
6843	//-- evaluate histogram for pvs size
6844
6845	cout << "computing pvs histogram for " << pass << " view cells" << endl;
6846
6847	sprintf(str, "-%09d-histo-pvs2.log", pass);
6848	filename = string(statsPrefix) + string(str);
6849
6850	EvalViewCellHistogramForPvsSize(filename, pass);
6851	}
6852	}
6853
6854
6855	void VspOspViewCellsManager::FinalizeViewCells(const bool createMesh)
6856	{
6857	ViewCellsManager::FinalizeViewCells(createMesh);
6858
6859	if (mHierarchyManager->mUseTraversalTree)
6860	{ // create a traversal tree for optimal view cell casting
6861	mHierarchyManager->CreateTraversalTree();
6862	}
6863	}
6864
6865
6866	#if TEST_PACKETS
6867
6868	float VspOspViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
6869	const bool addContributions,
6870	const bool storeViewCells,
6871	const bool useHitObjects)
6872	{
6873	if (!ViewCellsConstructed())
6874	return 0;
6875
6876	float sum = 0.0f;
6877	VssRayContainer::const_iterator it, it_end = rays.end();
6878
6879	VssRayContainer tmpRays;
6880
6881	for (it = rays.begin(); it != it_end; ++ it)
6882	{
6883	sum += ComputeSampleContribution((it), addContributions, storeViewCells, useHitObjects);
6884
6885	tmpRays.push_back(new VssRay((it)));
6886
6887	if (tmpRays.size() == 4)
6888	{
6889	// cast packets of 4 rays
6890	RayPacket packet(tmpRays);
6891	mHierarchyManager->CastLineSegment(packet);
6892
6893	for (int i = 0; i < 4; ++ i)
6894	{
6895	ComputeSampleContribution(*tmpRays[i], addContributions, true, useHitObjects);
6896	// compare results
6897	cout << "ray " << i << ": " << (int)tmpRays[i]->mViewCells.size() << " "
6898	<< (int)packet.mViewCells[i].size() << endl;
6899	}
6900
6901	CLEAR_CONTAINER(tmpRays);
6902	}
6903	}
6904
6905	CLEAR_CONTAINER(tmpRays);
6906
6907	#ifdef USE_PERFTIMER
6908	cout << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
6909	Debug << "view cell cast time: " << viewCellCastTimer.TotalTime() << " s" << endl;
6910	cout << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
6911	Debug << "pvs time: " << pvsTimer.TotalTime() << " s" << endl;
6912	#endif
6913
6914	return sum;
6915	}
6916
6917	#endif
6918
6919
6920	ViewCellsManager *
6921	ViewCellsManager::LoadViewCellsBinary(const string &filename,
6922	ObjectContainer &pvsObjects,
6923	bool finalizeViewCells,
6924	BoundingBoxConverter *bconverter)
6925	{
6926	IN_STREAM stream(filename.c_str());
6927
6928	if (!stream.is_open())
6929	{
6930	Debug << "View cells loading failed: could not open file" << endl;
6931	return NULL;
6932	}
6933
6934	Debug << "loading boxes" << endl;
6935
6936	const long startTime = GetTime();
6937
6938	// load all the bounding boxes
6939	IndexedBoundingBoxContainer iboxes;
6940	ViewCellsManager::LoadIndexedBoundingBoxesBinary(stream, iboxes);
6941
6942	pvsObjects.reserve(iboxes.size());
6943
6944	if (bconverter)
6945	{
6946	// associate object ids with bounding boxes
6947	bconverter->IdentifyObjects(iboxes, pvsObjects);
6948	}
6949
6950
6951	ObjectContainer pvsLookup;
6952	pvsLookup.resize(iboxes.size());
6953
6954	for (size_t i = 0; i < pvsLookup.size(); ++ i)
6955	{
6956	pvsLookup[i] = NULL;
6957	}
6958
6959	for (size_t i = 0; i < pvsObjects.size(); ++ i)
6960	{
6961	pvsLookup[pvsObjects[i]->GetId()] = pvsObjects[i];
6962	}
6963
6964
6965	/////////////
6966	//-- load the view cells
6967
6968	int numViewCells;
6969	stream.read(reinterpret_cast<char *>(&numViewCells), sizeof(int));
6970
6971	Debug << "loading " << numViewCells << " view cells " << endl;
6972
6973	Vector3 vmin, vmax;
6974
6975	stream.read(reinterpret_cast<char *>(&vmin), sizeof(Vector3));
6976	stream.read(reinterpret_cast<char *>(&vmax), sizeof(Vector3));
6977
6978	AxisAlignedBox3 viewSpaceBox(vmin, vmax);
6979
6980	Debug << "view space box: " << viewSpaceBox << endl;
6981
6982	ViewCellsTree *vcTree = new ViewCellsTree();
6983
6984	if (!vcTree->ImportBinary(stream, pvsLookup))
6985	{
6986	Debug << "Error: loading view cells tree failed!" << endl;
6987	delete vcTree;
6988
6989	return NULL;
6990	}
6991
6992	Debug << "loading the view space partition tree" << endl;
6993	VspTree *vspTree = new VspTree(viewSpaceBox);
6994
6995	if (!vspTree->ImportBinary(stream))
6996	{
6997	Debug << "Error: loading vsp tree failed!" << endl;
6998	delete vcTree; delete vspTree;
6999
7000	return NULL;
7001	}
7002
7003
7004	HierarchyManager * hm =
7005	new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
7006
7007	hm->SetVspTree(vspTree);
7008
7009
7010	/////////
7011	//-- create view cells manager
7012
7013	VspOspViewCellsManager *vm = new VspOspViewCellsManager(vcTree, hm);
7014
7015
7016	//////////////
7017	//-- do some more preparation
7018
7019	vm->mViewSpaceBox = viewSpaceBox;
7020	vm->mViewCells.clear();
7021
7022	ViewCellContainer viewCells;
7023	vcTree->CollectLeaves(vcTree->GetRoot(), viewCells);
7024
7025	ViewCellContainer::const_iterator cit, cit_end = viewCells.end();
7026
7027	for (cit = viewCells.begin(); cit != cit_end; ++ cit)
7028	{
7029	vm->mViewCells.push_back(*cit);
7030	}
7031
7032
7033	//////////////
7034	//-- associate view cells with vsp leaves
7035
7036	vector<VspLeaf *> vspLeaves;
7037	vspTree->CollectLeaves(vspLeaves);
7038
7039	vector<VspLeaf *>::const_iterator vit, vit_end = vspLeaves.end();
7040	cit = viewCells.begin();
7041
7042	for (vit = vspLeaves.begin(); vit != vit_end; ++ vit, ++ cit)
7043	{
7044	VspLeaf leaf = vit;
7045	VspViewCell vc = static_cast<VspViewCell >(*cit);
7046
7047	leaf->SetViewCell(vc);
7048	vc->mLeaves.push_back(leaf);
7049	}
7050
7051
7052	/*for (cit = viewCells.begin(); cit != cit_end; ++ cit)
7053	{
7054	Debug << "pvssize: " << (*cit)->GetPvs().GetSize();
7055	}*/
7056
7057
7058	vm->mViewCellsFinished = true;
7059	vm->mMaxPvsSize = (int)pvsObjects.size();
7060
7061	if (finalizeViewCells)
7062	{
7063	// create the meshes and compute view cell volumes
7064	const bool createMeshes = true;
7065	vm->FinalizeViewCells(createMeshes);
7066	}
7067
7068	Debug << (int)vm->mViewCells.size() << " view cells loaded in "
7069	<< TimeDiff(startTime, GetTime()) * 1e-6f << " secs" << endl;
7070
7071	//vspTree->TestOutput("input.txt");
7072
7073	return vm;
7074	}
7075
7076
7077	ViewCellPointsList *ViewCellsManager::GetViewCellPointsList()
7078	{
7079	return mRandomViewCellsHandler->GetViewCellPointsList();
7080	}
7081
7082
7083	bool ViewCellsManager::ExportRandomViewCells(const string &filename)
7084	{
7085	// export ten view cells with 100 random view points inside each
7086	const int numViewCells = 100;
7087	const int numViewPoints = 10;
7088
7089	//cout << "exporting random view cells" << endl;
7090	return mRandomViewCellsHandler->ExportRandomViewCells(filename);
7091	}
7092
7093
7094	bool ViewCellsManager::ImportViewCellsList(const string &filename)
7095	{
7096	return mRandomViewCellsHandler->ImportViewCellsList(filename);
7097	}
7098
7099
7100	}

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

Download in other formats: