Context Navigation

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

Revision 2614, 179.8 KB checked in by mattausch, 16 years ago (diff)
worked on dynamic objects

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

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

Download in other formats: