Context Navigation

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

Revision 1876, 161.9 KB checked in by bittner, 18 years ago (diff)
halton generator updates

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

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

Download in other formats: