Context Navigation

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

Revision 2678, 180.1 KB checked in by mattausch, 16 years ago (diff)
started working on dynamic objects

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

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

Download in other formats: