Context Navigation

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

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

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

Download in other formats: