Context Navigation

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

Revision 1751, 154.4 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: