Context Navigation

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

Revision 2609, 179.6 KB checked in by mattausch, 16 years ago (diff)

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

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

Download in other formats: