Context Navigation

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

Revision 1765, 153.2 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: