Context Navigation

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

Revision 1773, 153.4 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: