Context Navigation

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

Revision 1832, 160.8 KB checked in by bittner, 18 years ago (diff)
gl render updates - separate gl viewer widget

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

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

Download in other formats: