Context Navigation

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

Revision 1745, 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	////////////////
584	//-- Evaluation of the resulting view cell partition.
585	//-- We cast a number of new samples and measure the render cost
586
587	if (mEvaluateViewCells)
588	{
589	EvalViewCellPartition();
590	}
591
592	// write view cells to disc
593	if (1 && mExportViewCells)
594	{
595	char filename[100];
596	Environment::GetSingleton()->GetStringValue("ViewCells.filename", filename);
597	ExportViewCells(filename, mExportPvs, mPreprocessor->mObjects);
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<<"Filter size = "<<filterSize<<endl;
2618	// cout<<"vbox = "<<vbox<<endl;
2619	// cout<<"center = "<<center<<endl;
2620
2621
2622	#define MIN_LOCAL_SAMPLES 5
2623
2624	// compute the average filter radius
2625	float globalC = 2.0f*filterSize/sqrt(samples);
2626
2627	float sumRadius = 0.0f;
2628
2629	ObjectPvsIterator pit2 = pvs.GetIterator();
2630
2631	// first mark all object from this pvs
2632	for (; pit2.HasMoreEntries(); pvsSize++) {
2633	ObjectPvsEntry entry = pit2.Next();
2634	Intersectable *object = entry.mObject;
2635	// compute filter size based on the distance and the numebr of samples
2636	AxisAlignedBox3 box = object->GetBox();
2637
2638	float distance = Distance(center, box.Center());
2639	float globalRadius = distance*globalC;
2640
2641	int objectSamples = (int)entry.mData.mSumPdf;
2642	float localRadius = MAX_FLOAT;
2643
2644	if (objectSamples > MIN_LOCAL_SAMPLES)
2645	localRadius = 0.5f*Magnitude(box.Diagonal())/sqrt((float)objectSamples);
2646
2647	// now compute the filter size
2648	float radius = Min(localRadius, globalRadius);
2649
2650	sumRadius +=radius;
2651	}
2652
2653	float avgRadius = sumRadius/pvsSize;
2654	float viewCellRadius = 0.5f*Magnitude(vbox.Diagonal());
2655	cout<<"radius ratio = "<<avgRadius/viewCellRadius<<endl;
2656
2657	// now compute the filter box around the current viewCell
2658
2659	if (useViewSpaceFilter) {
2660	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
2661	float radius = viewCellRadius/100.0f;
2662	vbox.Enlarge(radius);
2663	cout<<"vbox = "<<vbox<<endl;
2664	ViewCellContainer viewCells;
2665	ComputeBoxIntersections(vbox, viewCells);
2666
2667	// cout<<"box="<<box<<endl;
2668	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
2669
2670	int i;
2671	for (i=0; it != it_end; ++ it, ++ i)
2672	if ((*it) != viewCell) {
2673	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
2674	pvs.MergeInPlace((*it)->GetPvs());
2675	}
2676
2677	// update samples and globalC
2678	samples = (float)pvs.GetSamples();
2679	globalC = 2.0f*filterSize/sqrt(samples);
2680	cout<<"neighboring viewcells = "<<i-1<<endl;
2681	cout<<"Samples' = "<<samples<<endl;
2682	}
2683
2684	pit = pvs.GetIterator();
2685
2686	// first mark all object from this pvs
2687	while (pit.HasMoreEntries())
2688	{
2689	ObjectPvsEntry entry = pit.Next();
2690
2691	Intersectable *object = entry.mObject;
2692	// compute filter size based on the distance and the numebr of samples
2693	AxisAlignedBox3 box = object->GetBox();
2694
2695	float distance = Distance(center, box.Center());
2696	float globalRadius = distance*globalC;
2697
2698	int objectSamples = (int)entry.mData.mSumPdf;
2699	float localRadius = MAX_FLOAT;
2700	if (objectSamples > MIN_LOCAL_SAMPLES)
2701	localRadius = filterSize0.5fMagnitude(box.Diagonal())/sqrt((float)objectSamples);
2702
2703	// cout<<"lr="<<localRadius<<" gr="<<globalRadius<<endl;
2704
2705	// now compute the filter size
2706	float radius = Min(localRadius, globalRadius);
2707
2708	// cout<<"box = "<<box<<endl;
2709	// cout<<"distance = "<<distance<<endl;
2710	// cout<<"radiues = "<<radius<<endl;
2711
2712	box.Enlarge(Vector3(radius));
2713
2714	ObjectContainer objects;
2715	// $$ warning collect objects takes only unmailed ones!
2716	CollectObjects(box, objects);
2717	// cout<<"collected objects="<<objects.size()<<endl;
2718	ObjectContainer::const_iterator noi = objects.begin();
2719	for (; noi != objects.end(); ++ noi) {
2720	Intersectable o = noi;
2721	// $$ JB warning: pdfs are not correct at this point!
2722	nPvs.AddSample(o, Limits::Small);
2723	nPvsSize ++;
2724	}
2725	}
2726	cout<<"nPvs size = "<<nPvsSize<<endl;
2727
2728	pvs.MergeInPlace(nPvs);
2729
2730	Intersectable::NewMail();
2731	}
2732
2733
2734
2735
2736
2737	void ViewCellsManager::ExportColor(Exporter *exporter,
2738	ViewCell *vc,
2739	bool colorCode) const
2740	{
2741	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
2742
2743	float importance = 0;
2744	static Material m;
2745
2746	switch (mColorCode)
2747	{
2748	case 0: // Random
2749	{
2750	if (vcValid)
2751	{
2752	m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
2753	m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
2754	m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
2755	}
2756	else
2757	{
2758	m.mDiffuseColor.r = 0.0f;
2759	m.mDiffuseColor.g = 1.0f;
2760	m.mDiffuseColor.b = 0.0f;
2761	}
2762
2763	exporter->SetForcedMaterial(m);
2764	return;
2765	}
2766
2767	case 1: // pvs
2768	{
2769	if (mCurrentViewCellsStats.maxPvs)
2770	{
2771	importance =
2772	(float)mViewCellsTree->GetPvsCost(vc) /
2773	(float)mCurrentViewCellsStats.maxPvs;
2774	}
2775	}
2776	break;
2777	case 2: // merges
2778	{
2779	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
2780	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
2781	}
2782	break;
2783	#if 0
2784	case 3: // merge tree differene
2785	{
2786	importance = (float)GetMaxTreeDiff(vc) /
2787	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
2788
2789	}
2790	break;
2791	#endif
2792	default:
2793	break;
2794	}
2795
2796	// special color code for invalid view cells
2797	m.mDiffuseColor.r = importance;
2798	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
2799	m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
2800
2801	//Debug << "importance: " << importance << endl;
2802	exporter->SetForcedMaterial(m);
2803	}
2804
2805
2806	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2807	vector<MergeCandidate> &candidates)
2808	{
2809	// implemented in subclasses
2810	}
2811
2812
2813	void ViewCellsManager::UpdatePvsForEvaluation()
2814	{
2815	ObjectPvs objPvs;
2816	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
2817	}
2818
2819	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
2820	{
2821	// terminate traversal
2822	if (root->IsLeaf())
2823	{
2824	//cout << "updating leaf" << endl;
2825	// we assume that pvs is explicitly stored in leaves
2826	pvs = root->GetPvs();
2827	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
2828	return;
2829	}
2830
2831	//cout << "recursivly updating pvs" << endl;
2832
2833	////////////////
2834	//-- interior node => propagate pvs up the tree
2835
2836	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
2837
2838	// reset interior pvs
2839	interior->GetPvs().Clear();
2840	// reset recursive pvs
2841	pvs.Clear();
2842
2843	// pvss of child nodes
2844	vector<ObjectPvs> pvsList;
2845	pvsList.resize((int)interior->mChildren.size());
2846
2847	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
2848
2849	int i = 0;
2850
2851	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
2852	{
2853	//////////////////
2854	//-- recursivly compute child pvss
2855	UpdatePvsForEvaluation(vit, pvsList[i]/objPvs*/);
2856	}
2857
2858	#if 1
2859	Intersectable::NewMail();
2860
2861	//-- faster way of computing pvs:
2862	//-- construct merged pvs by adding
2863	//-- and only those of the next pvs which were not mailed.
2864	//-- note: sumpdf is not correct!!
2865
2866	vector<ObjectPvs>::iterator oit = pvsList.begin();
2867
2868	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
2869	{
2870	ObjectPvsIterator pit = (*oit).GetIterator();
2871
2872	// first mark all object from this pvs
2873	while (pit.HasMoreEntries())
2874	{
2875	ObjectPvsEntry entry = pit.Next();
2876
2877	Intersectable *intersect = entry.mObject;
2878
2879	if (!intersect->Mailed())
2880	{
2881	pvs.AddSample(intersect, entry.mData.mSumPdf);
2882	intersect->Mail();
2883	}
2884	}
2885	}
2886
2887	// store pvs in this node
2888	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
2889	{
2890	interior->SetPvs(pvs);
2891	}
2892
2893	// set new pvs size
2894	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
2895
2896	#else
2897	// really merge cells: slow put sumPdf is correct
2898	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
2899	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
2900	#endif
2901	}
2902
2903
2904
2905	/*******************************************************************/
2906	/* BspViewCellsManager implementation */
2907	/*******************************************************************/
2908
2909
2910	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
2911	ViewCellsManager(vcTree), mBspTree(bspTree)
2912	{
2913	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
2914
2915	mBspTree->SetViewCellsManager(this);
2916	mBspTree->SetViewCellsTree(mViewCellsTree);
2917	}
2918
2919
2920	bool BspViewCellsManager::ViewCellsConstructed() const
2921	{
2922	return mBspTree->GetRoot() != NULL;
2923	}
2924
2925
2926	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
2927	{
2928	return new BspViewCell(mesh);
2929	}
2930
2931
2932	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2933	const VssRayContainer &rays)
2934	{
2935	// if view cells were already constructed, we can finish
2936	if (ViewCellsConstructed())
2937	return 0;
2938
2939	int sampleContributions = 0;
2940
2941	// construct view cells using the collected samples
2942	RayContainer constructionRays;
2943	VssRayContainer savedRays;
2944
2945	// choose a a number of rays based on the ratio of cast rays / requested rays
2946	const int limit = min(mInitialSamples, (int)rays.size());
2947	VssRayContainer::const_iterator it, it_end = rays.end();
2948
2949	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
2950
2951	for (it = rays.begin(); it != it_end; ++ it)
2952	{
2953	if (Random(1.0f) < prop)
2954	constructionRays.push_back(new Ray((it)));
2955	else
2956	savedRays.push_back(*it);
2957	}
2958
2959	if (!mUsePredefinedViewCells)
2960	{
2961	// no view cells loaded
2962	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
2963	// collect final view cells
2964	mBspTree->CollectViewCells(mViewCells);
2965	}
2966	else
2967	{
2968	// use predefined view cells geometry =>
2969	// contruct bsp hierarchy over them
2970	mBspTree->Construct(mViewCells);
2971	}
2972
2973	// destroy rays created only for construction
2974	CLEAR_CONTAINER(constructionRays);
2975
2976	Debug << mBspTree->GetStatistics() << endl;
2977	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
2978
2979	// recast rest of the rays
2980	if (SAMPLE_AFTER_SUBDIVISION)
2981	ComputeSampleContributions(savedRays, true, false);
2982
2983	// real meshes are contructed at this stage
2984	if (0)
2985	{
2986	cout << "finalizing view cells ... ";
2987	FinalizeViewCells(true);
2988	cout << "finished" << endl;
2989	}
2990
2991	return sampleContributions;
2992	}
2993
2994
2995	void BspViewCellsManager::CollectViewCells()
2996	{
2997	if (!ViewCellsTreeConstructed())
2998	{ // view cells tree constructed
2999	mBspTree->CollectViewCells(mViewCells);
3000	}
3001	else
3002	{ // we can use the view cells tree hierarchy to get the right set
3003	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3004	}
3005	}
3006
3007
3008	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3009	{
3010	if (1)
3011	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3012	else
3013	// compute view cell area as subsititute for probability
3014	return GetArea(viewCell) / GetAccVcArea();
3015	}
3016
3017
3018
3019	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3020	const Vector3 &termination,
3021	ViewCellContainer &viewcells)
3022	{
3023	return mBspTree->CastLineSegment(origin, termination, viewcells);
3024	}
3025
3026
3027	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3028	{
3029	// save color code
3030	const int savedColorCode = mColorCode;
3031
3032	// export merged view cells
3033	mColorCode = 0; // use random colors
3034
3035	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
3036
3037	cout << "exporting view cells after merge ... ";
3038
3039	if (exporter)
3040	{
3041	if (mExportGeometry)
3042	{
3043	exporter->ExportGeometry(objects);
3044	}
3045
3046	exporter->SetFilled();
3047	ExportViewCellsForViz(exporter, NULL, GetClipPlane());
3048
3049	delete exporter;
3050	}
3051	cout << "finished" << endl;
3052
3053	// export merged view cells using pvs color coding
3054	mColorCode = 1;
3055
3056	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3057	cout << "exporting view cells after merge (pvs size) ... ";
3058
3059	if (exporter)
3060	{
3061	if (mExportGeometry)
3062	{
3063	exporter->ExportGeometry(objects);
3064	}
3065
3066	exporter->SetFilled();
3067	ExportViewCellsForViz(exporter, NULL, GetClipPlane());
3068
3069	delete exporter;
3070	}
3071	cout << "finished" << endl;
3072
3073	mColorCode = savedColorCode;
3074	}
3075
3076
3077	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3078	const VssRayContainer &rays)
3079	{
3080	if (!ViewCellsConstructed())
3081	{
3082	Debug << "view cells not constructed" << endl;
3083	return 0;
3084	}
3085
3086	// view cells already finished before post processing step,
3087	// i.e., because they were loaded from disc
3088	if (mViewCellsFinished)
3089	{
3090	FinalizeViewCells(true);
3091	EvaluateViewCellsStats();
3092
3093	return 0;
3094	}
3095
3096	//////////////////
3097	//-- merge leaves of the view cell hierarchy
3098
3099	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3100	long startTime = GetTime();
3101
3102	VssRayContainer postProcessRays;
3103	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3104
3105	if (mMergeViewCells)
3106	{
3107	cout << "constructing visibility based merge tree" << endl;
3108	mViewCellsTree->ConstructMergeTree(rays, objects);
3109	}
3110	else
3111	{
3112	cout << "constructing spatial merge tree" << endl;
3113	ViewCell *root;
3114	// the spatial merge tree is difficult to build for
3115	// this type of construction, as view cells cover several
3116	// leaves => create dummy tree which is only 2 levels deep
3117	if (mUsePredefinedViewCells)
3118	{
3119	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3120	}
3121	else
3122	{
3123	// create spatial merge hierarchy
3124	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3125	}
3126
3127	mViewCellsTree->SetRoot(root);
3128
3129	// recompute pvs in the whole hierarchy
3130	ObjectPvs pvs;
3131	UpdatePvsForEvaluation(root, pvs);
3132	}
3133
3134	cout << "finished" << endl;
3135	cout << "merged view cells in "
3136	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3137
3138	Debug << "Postprocessing: Merged view cells in "
3139	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3140
3141
3142	////////////////////////
3143	//-- visualization and statistics after merge
3144
3145	if (1)
3146	{
3147	char mstats[100];
3148	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3149	mViewCellsTree->ExportStats(mstats);
3150	}
3151
3152	// recompute view cells and stats
3153	ResetViewCells();
3154	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3155
3156	// visualization of the view cells
3157	if (1) ExportMergedViewCells(objects);
3158
3159	// compute final meshes and volume / area
3160	if (1) FinalizeViewCells(true);
3161
3162	return 0;
3163	}
3164
3165
3166	BspViewCellsManager::~BspViewCellsManager()
3167	{
3168	}
3169
3170
3171	int BspViewCellsManager::GetType() const
3172	{
3173	return BSP;
3174	}
3175
3176
3177	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3178	const VssRayContainer &sampleRays)
3179	{
3180	if (!ViewCellsConstructed())
3181	return;
3182
3183	const int savedColorCode = mColorCode;
3184
3185	if (1) // export final view cells
3186	{
3187	mColorCode = 1; // hack color code
3188	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3189
3190	cout << "exporting view cells after merge (pvs size) ... ";
3191
3192	if (exporter)
3193	{
3194	if (mExportGeometry)
3195	{
3196	exporter->ExportGeometry(objects);
3197	}
3198
3199	ExportViewCellsForViz(exporter, NULL, GetClipPlane());
3200	delete exporter;
3201	}
3202	cout << "finished" << endl;
3203	}
3204
3205	// reset color code
3206	mColorCode = savedColorCode;
3207
3208
3209	//////////////////
3210	//-- visualization of the BSP splits
3211
3212	bool exportSplits = false;
3213	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3214
3215	if (exportSplits)
3216	{
3217	cout << "exporting splits ... ";
3218	ExportSplits(objects);
3219	cout << "finished" << endl;
3220	}
3221
3222	int leafOut;
3223	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3224	const int raysOut = 100;
3225	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3226	}
3227
3228
3229	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3230	{
3231	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3232
3233	if (exporter)
3234	{
3235	//exporter->SetFilled();
3236	if (mExportGeometry)
3237	{
3238	exporter->ExportGeometry(objects);
3239	}
3240
3241	Material m;
3242	m.mDiffuseColor = RgbColor(1, 0, 0);
3243	exporter->SetForcedMaterial(m);
3244	exporter->SetWireframe();
3245
3246	exporter->ExportBspSplits(*mBspTree, true);
3247
3248	// NOTE: take forced material, else big scenes cannot be viewed
3249	m.mDiffuseColor = RgbColor(0, 1, 0);
3250	exporter->SetForcedMaterial(m);
3251	//exporter->ResetForcedMaterial();
3252
3253	delete exporter;
3254	}
3255	}
3256
3257
3258	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3259	const int maxViewCells,
3260	const bool sortViewCells,
3261	const bool exportPvs,
3262	const bool exportRays,
3263	const int maxRays,
3264	const string prefix,
3265	VssRayContainer *visRays)
3266	{
3267	if (sortViewCells)
3268	{ // sort view cells to visualize the largest view cells
3269	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
3270	}
3271
3272	//////////
3273	//-- some view cells for output
3274
3275	ViewCell::NewMail();
3276	const int limit = min(maxViewCells, (int)mViewCells.size());
3277
3278	for (int i = 0; i < limit; ++ i)
3279	{
3280	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
3281	ViewCell *vc = mViewCells[idx];
3282
3283	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
3284	continue;
3285
3286	vc->Mail();
3287
3288	ObjectPvs pvs;
3289	mViewCellsTree->GetPvs(vc, pvs);
3290
3291	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
3292	Exporter *exporter = Exporter::GetExporter(s);
3293
3294	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetPvsCost(vc) << endl;
3295
3296	if (exportRays)
3297	{
3298	////////////
3299	//-- export rays piercing this view cell
3300
3301	// use rays stored with the view cells
3302	VssRayContainer vcRays, vcRays2, vcRays3;
3303	VssRayContainer collectRays;
3304
3305	// collect initial view cells
3306	ViewCellContainer leaves;
3307	mViewCellsTree->CollectLeaves(vc, leaves);
3308
3309	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3310	for (vit = leaves.begin(); vit != vit_end; ++ vit)
3311	{
3312	// prepare some rays for output
3313	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
3314	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
3315	{
3316	collectRays.push_back(*rit);
3317	}
3318	}
3319
3320	const int raysOut = min((int)collectRays.size(), maxRays);
3321
3322	// prepare some rays for output
3323	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3324	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3325	{
3326	const float p = RandomValue(0.0f, (float)collectRays.size());
3327	if (p < raysOut)
3328	{
3329	if ((*rit)->mFlags & VssRay::BorderSample)
3330	{
3331	vcRays.push_back(*rit);
3332	}
3333	else if ((*rit)->mFlags & VssRay::ReverseSample)
3334	vcRays2.push_back(*rit);
3335	else
3336	vcRays3.push_back(*rit);
3337
3338	}
3339	}
3340
3341	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
3342	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
3343	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
3344	}
3345
3346	////////////////
3347	//-- export view cell geometry
3348
3349	exporter->SetWireframe();
3350
3351	Material m;//= RandomMaterial();
3352	m.mDiffuseColor = RgbColor(0, 1, 0);
3353	exporter->SetForcedMaterial(m);
3354
3355	ExportViewCellGeometry(exporter, vc, NULL, NULL);
3356	exporter->SetFilled();
3357
3358	if (exportPvs)
3359	{
3360	Intersectable::NewMail();
3361	ObjectPvsIterator pit = pvs.GetIterator();
3362
3363	while (pit.HasMoreEntries())
3364	{
3365	ObjectPvsEntry entry = pit.Next();
3366
3367	// output PVS of view cell
3368	Intersectable *intersect = entry.mObject;
3369
3370	if (!intersect->Mailed())
3371	{
3372	intersect->Mail();
3373
3374	m = RandomMaterial();
3375	exporter->SetForcedMaterial(m);
3376	exporter->ExportIntersectable(intersect);
3377	}
3378	}
3379	cout << endl;
3380	}
3381
3382	DEL_PTR(exporter);
3383	cout << "finished" << endl;
3384	}
3385	}
3386
3387
3388	void BspViewCellsManager::TestSubdivision()
3389	{
3390	ViewCellContainer leaves;
3391	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
3392
3393	ViewCellContainer::const_iterator it, it_end = leaves.end();
3394
3395	const float vol = mViewSpaceBox.GetVolume();
3396	float subdivVol = 0;
3397	float newVol = 0;
3398
3399	for (it = leaves.begin(); it != it_end; ++ it)
3400	{
3401	BspNodeGeometry geom;
3402	mBspTree->ConstructGeometry(*it, geom);
3403
3404	const float lVol = geom.GetVolume();
3405	newVol += lVol;
3406	subdivVol += (*it)->GetVolume();
3407
3408	const float thres = 0.9f;
3409	if ((lVol < ((it)->GetVolume() thres)) \|\|
3410	(lVol * thres > ((*it)->GetVolume())))
3411	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
3412	}
3413
3414	Debug << "exact volume: " << vol << endl;
3415	Debug << "subdivision volume: " << subdivVol << endl;
3416	Debug << "new volume: " << newVol << endl;
3417	}
3418
3419
3420	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3421	ViewCell *vc,
3422	const AxisAlignedBox3 *sceneBox,
3423	const AxisAlignedPlane *clipPlane
3424	) const
3425	{
3426	if (clipPlane)
3427	{
3428	const Plane3 plane = clipPlane->GetPlane();
3429
3430	ViewCellContainer leaves;
3431	mViewCellsTree->CollectLeaves(vc, leaves);
3432	ViewCellContainer::const_iterator it, it_end = leaves.end();
3433
3434	for (it = leaves.begin(); it != it_end; ++ it)
3435	{
3436	BspNodeGeometry geom;
3437	BspNodeGeometry front;
3438	BspNodeGeometry back;
3439
3440	mBspTree->ConstructGeometry(*it, geom);
3441
3442	const float eps = 0.0001f;
3443	const int cf = geom.Side(plane, eps);
3444
3445	if (cf == -1)
3446	{
3447	exporter->ExportPolygons(geom.GetPolys());
3448	}
3449	else if (cf == 0)
3450	{
3451	geom.SplitGeometry(front,
3452	back,
3453	plane,
3454	mViewSpaceBox,
3455	eps);
3456
3457	if (back.Valid())
3458	{
3459	exporter->ExportPolygons(back.GetPolys());
3460	}
3461	}
3462	}
3463	}
3464	else
3465	{
3466	// export mesh if available
3467	// TODO: some bug here?
3468	if (1 && vc->GetMesh())
3469	{
3470	exporter->ExportMesh(vc->GetMesh());
3471	}
3472	else
3473	{
3474	BspNodeGeometry geom;
3475	mBspTree->ConstructGeometry(vc, geom);
3476	exporter->ExportPolygons(geom.GetPolys());
3477	}
3478	}
3479	}
3480
3481
3482	void BspViewCellsManager::CreateMesh(ViewCell *vc)
3483	{
3484	// note: should previous mesh be deleted (via mesh manager?)
3485	BspNodeGeometry geom;
3486	mBspTree->ConstructGeometry(vc, geom);
3487
3488	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
3489
3490	IncludeNodeGeomInMesh(geom, *mesh);
3491	vc->SetMesh(mesh);
3492	}
3493
3494
3495	void BspViewCellsManager::Finalize(ViewCell *viewCell,
3496	const bool createMesh)
3497	{
3498	float area = 0;
3499	float volume = 0;
3500
3501	ViewCellContainer leaves;
3502	mViewCellsTree->CollectLeaves(viewCell, leaves);
3503
3504	ViewCellContainer::const_iterator it, it_end = leaves.end();
3505
3506	for (it = leaves.begin(); it != it_end; ++ it)
3507	{
3508	BspNodeGeometry geom;
3509
3510	mBspTree->ConstructGeometry(*it, geom);
3511
3512	const float lVol = geom.GetVolume();
3513	const float lArea = geom.GetArea();
3514
3515	area += lArea;
3516	volume += lVol;
3517
3518	CreateMesh(*it);
3519	}
3520
3521	viewCell->SetVolume(volume);
3522	viewCell->SetArea(area);
3523	}
3524
3525
3526	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
3527	{
3528	if (!ViewCellsConstructed())
3529	{
3530	return NULL;
3531	}
3532	if (!mViewSpaceBox.IsInside(point))
3533	{
3534	return NULL;
3535	}
3536	return mBspTree->GetViewCell(point);
3537	}
3538
3539
3540	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3541	vector<MergeCandidate> &candidates)
3542	{
3543	cout << "collecting merge candidates ... " << endl;
3544
3545	if (mUseRaysForMerge)
3546	{
3547	mBspTree->CollectMergeCandidates(rays, candidates);
3548	}
3549	else
3550	{
3551	vector<BspLeaf *> leaves;
3552	mBspTree->CollectLeaves(leaves);
3553	mBspTree->CollectMergeCandidates(leaves, candidates);
3554	}
3555
3556	cout << "fininshed collecting candidates" << endl;
3557	}
3558
3559
3560
3561	bool BspViewCellsManager::ExportViewCells(const string filename,
3562	const bool exportPvs,
3563	const ObjectContainer &objects)
3564	{
3565	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
3566	{
3567	return false;
3568	}
3569
3570	cout << "exporting view cells to xml ... ";
3571
3572	OUT_STREAM stream(filename.c_str());
3573
3574	// for output we need unique ids for each view cell
3575	CreateUniqueViewCellIds();
3576
3577	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3578	stream << "<VisibilitySolution>" << endl;
3579
3580	if (exportPvs)
3581	{
3582	//////////
3583	//-- export bounding boxes: they are used to identify the objects from the pvs and
3584	//-- assign them to the entities in the rendering engine
3585
3586	stream << "<BoundingBoxes>" << endl;
3587	ObjectContainer::const_iterator oit, oit_end = objects.end();
3588
3589	for (oit = objects.begin(); oit != oit_end; ++ oit)
3590	{
3591	const AxisAlignedBox3 box = (*oit)->GetBox();
3592
3593	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
3594	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
3595	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
3596	}
3597
3598	stream << "</BoundingBoxes>" << endl;
3599	}
3600
3601	///////////
3602	//-- export the view cells and the pvs
3603
3604	const int numViewCells = mCurrentViewCellsStats.viewCells;
3605	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
3606
3607	mViewCellsTree->Export(stream, exportPvs);
3608
3609	stream << "</ViewCells>" << endl;
3610
3611	/////////////
3612	//-- export the view space hierarchy
3613	stream << "<ViewSpaceHierarchy type=\"bsp\""
3614	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3615	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
3616
3617	mBspTree->Export(stream);
3618
3619	// end tags
3620	stream << "</ViewSpaceHierarchy>" << endl;
3621	stream << "</VisibilitySolution>" << endl;
3622
3623	stream.close();
3624	cout << "finished" << endl;
3625
3626	return true;
3627	}
3628
3629
3630	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
3631	{
3632	ViewCellInterior *vcRoot = new ViewCellInterior();
3633
3634	// evaluate merge cost for priority traversal
3635	const float mergeCost = -(float)root->mTimeStamp;
3636	vcRoot->SetMergeCost(mergeCost);
3637
3638	float volume = 0;
3639	vector<BspLeaf *> leaves;
3640	mBspTree->CollectLeaves(leaves);
3641	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
3642	ViewCell::NewMail();
3643
3644	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3645	{
3646	BspLeaf leaf = lit;
3647	ViewCell *vc = leaf->GetViewCell();
3648
3649	if (!vc->Mailed())
3650	{
3651	vc->Mail();
3652	vc->SetMergeCost(0.0f);
3653	vcRoot->SetupChildLink(vc);
3654
3655	volume += vc->GetVolume();
3656	volume += vc->GetVolume();
3657	vcRoot->SetVolume(volume);
3658	}
3659	}
3660
3661	return vcRoot;
3662	}
3663
3664
3665	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
3666	{
3667	// terminate recursion
3668	if (root->IsLeaf())
3669	{
3670	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
3671	leaf->GetViewCell()->SetMergeCost(0.0f);
3672	return leaf->GetViewCell();
3673	}
3674
3675	BspInterior interior = dynamic_cast<BspInterior >(root);
3676	ViewCellInterior *viewCellInterior = new ViewCellInterior();
3677
3678	// evaluate merge cost for priority traversal
3679	const float mergeCost = -(float)root->mTimeStamp;
3680	viewCellInterior->SetMergeCost(mergeCost);
3681
3682	float volume = 0;
3683
3684	BspNode *front = interior->GetFront();
3685	BspNode *back = interior->GetBack();
3686
3687
3688	////////////
3689	//-- recursivly compute child hierarchies
3690
3691	ViewCell *backVc = ConstructSpatialMergeTree(back);
3692	ViewCell *frontVc = ConstructSpatialMergeTree(front);
3693
3694	viewCellInterior->SetupChildLink(backVc);
3695	viewCellInterior->SetupChildLink(frontVc);
3696
3697	volume += backVc->GetVolume();
3698	volume += frontVc->GetVolume();
3699
3700	viewCellInterior->SetVolume(volume);
3701
3702	return viewCellInterior;
3703	}
3704
3705
3706	/************************************************************************/
3707	/* KdViewCellsManager implementation */
3708	/************************************************************************/
3709
3710
3711
3712	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
3713	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
3714	{
3715	}
3716
3717
3718	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
3719	{
3720	// compute view cell area / volume as subsititute for probability
3721	if (0)
3722	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
3723	else
3724	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3725	}
3726
3727
3728
3729
3730	void KdViewCellsManager::CollectViewCells()
3731	{
3732	//mKdTree->CollectViewCells(mViewCells); TODO
3733	}
3734
3735
3736	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3737	const VssRayContainer &rays)
3738	{
3739	// if view cells already constructed
3740	if (ViewCellsConstructed())
3741	return 0;
3742
3743	mKdTree->Construct();
3744
3745	mTotalAreaValid = false;
3746	// create the view cells
3747	mKdTree->CreateAndCollectViewCells(mViewCells);
3748	// cast rays
3749	ComputeSampleContributions(rays, true, false);
3750
3751	EvaluateViewCellsStats();
3752	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3753
3754	return 0;
3755	}
3756
3757
3758	bool KdViewCellsManager::ViewCellsConstructed() const
3759	{
3760	return mKdTree->GetRoot() != NULL;
3761	}
3762
3763
3764	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
3765	const VssRayContainer &rays)
3766	{
3767	return 0;
3768	}
3769
3770
3771	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3772	const int maxViewCells,
3773	const bool sortViewCells,
3774	const bool exportPvs,
3775	const bool exportRays,
3776	const int maxRays,
3777	const string prefix,
3778	VssRayContainer *visRays)
3779	{
3780	// TODO
3781	}
3782
3783
3784	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
3785	const VssRayContainer &sampleRays)
3786	{
3787	if (!ViewCellsConstructed())
3788	return;
3789
3790	// using view cells instead of the kd PVS of objects
3791	const bool useViewCells = true;
3792	bool exportRays = false;
3793
3794	int limit = min(mVisualizationSamples, (int)sampleRays.size());
3795	const int pvsOut = min((int)objects.size(), 10);
3796	VssRayContainer *rays = new VssRayContainer[pvsOut];
3797
3798	if (useViewCells)
3799	{
3800	const int leafOut = 10;
3801
3802	ViewCell::NewMail();
3803
3804	//-- some rays for output
3805	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
3806	Debug << "visualization using " << raysOut << " samples" << endl;
3807
3808	//-- some random view cells and rays for output
3809	vector<KdLeaf *> kdLeaves;
3810
3811	for (int i = 0; i < leafOut; ++ i)
3812	kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
3813
3814	for (int i = 0; i < kdLeaves.size(); ++ i)
3815	{
3816	KdLeaf *leaf = kdLeaves[i];
3817	RayContainer vcRays;
3818
3819	cout << "creating output for view cell " << i << " ... ";
3820	#if 0
3821	// check whether we can add the current ray to the output rays
3822	for (int k = 0; k < raysOut; ++ k)
3823	{
3824	Ray *ray = sampleRays[k];
3825
3826	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
3827	{
3828	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
3829
3830	if (leaf->GetViewCell() == leaf2->GetViewCell())
3831	{
3832	vcRays.push_back(ray);
3833	}
3834	}
3835	}
3836	#endif
3837	Intersectable::NewMail();
3838
3839	ViewCell *vc = leaf->mViewCell;
3840	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
3841
3842	Exporter *exporter = Exporter::GetExporter(str);
3843	exporter->SetFilled();
3844
3845	exporter->SetWireframe();
3846	//exporter->SetFilled();
3847
3848	Material m;//= RandomMaterial();
3849	m.mDiffuseColor = RgbColor(1, 1, 0);
3850	exporter->SetForcedMaterial(m);
3851
3852	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
3853	exporter->ExportBox(box);
3854
3855	// export rays piercing this view cell
3856	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
3857
3858	m.mDiffuseColor = RgbColor(1, 0, 0);
3859	exporter->SetForcedMaterial(m);
3860
3861	// exporter->SetWireframe();
3862	exporter->SetFilled();
3863
3864	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
3865
3866	while (pit.HasMoreEntries())
3867	{
3868	ObjectPvsEntry entry = pit.Next();
3869
3870	//-- output PVS of view cell
3871	Intersectable *intersect = entry.mObject;
3872	if (!intersect->Mailed())
3873	{
3874	exporter->ExportIntersectable(intersect);
3875	intersect->Mail();
3876	}
3877	}
3878
3879	DEL_PTR(exporter);
3880	cout << "finished" << endl;
3881	}
3882
3883	DEL_PTR(rays);
3884	}
3885	else // using kd PVS of objects
3886	{
3887	for (int i = 0; i < limit; ++ i)
3888	{
3889	VssRay *ray = sampleRays[i];
3890
3891	// check whether we can add this to the rays
3892	for (int j = 0; j < pvsOut; j++)
3893	{
3894	if (objects[j] == ray->mTerminationObject)
3895	{
3896	rays[j].push_back(ray);
3897	}
3898	}
3899	}
3900
3901	if (exportRays)
3902	{
3903	Exporter *exporter = NULL;
3904	exporter = Exporter::GetExporter("sample-rays.x3d");
3905	exporter->SetWireframe();
3906	exporter->ExportKdTree(*mKdTree);
3907
3908	for (i = 0; i < pvsOut; i++)
3909	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
3910
3911	exporter->SetFilled();
3912	delete exporter;
3913	}
3914
3915	for (int k=0; k < pvsOut; k++)
3916	{
3917	Intersectable *object = objects[k];
3918	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
3919
3920	Exporter *exporter = Exporter::GetExporter(str);
3921	exporter->SetWireframe();
3922
3923	// matt: no kd pvs
3924	/*
3925	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
3926	Intersectable::NewMail();
3927
3928	// avoid adding the object to the list
3929	object->Mail();
3930	ObjectContainer visibleObjects;
3931
3932	for (; kit != object->mKdPvs.mEntries.end(); i++)
3933	{
3934	KdNode node = (kit).first;
3935	exporter->ExportBox(mKdTree->GetBox(node));
3936
3937	mKdTree->CollectObjects(node, visibleObjects);
3938	}
3939
3940	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
3941	exporter->SetFilled();
3942
3943	for (int j = 0; j < visibleObjects.size(); j++)
3944	exporter->ExportIntersectable(visibleObjects[j]);
3945
3946	Material m;
3947	m.mDiffuseColor = RgbColor(1, 0, 0);
3948	exporter->SetForcedMaterial(m);
3949	exporter->ExportIntersectable(object);
3950	*/
3951	delete exporter;
3952	}
3953	}
3954	}
3955
3956
3957	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
3958	{
3959	return new KdViewCell(mesh);
3960	}
3961
3962
3963	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3964	ViewCell *vc,
3965	const AxisAlignedBox3 *sceneBox,
3966	const AxisAlignedPlane *clipPlane
3967	) const
3968	{
3969	ViewCellContainer leaves;
3970	mViewCellsTree->CollectLeaves(vc, leaves);
3971	ViewCellContainer::const_iterator it, it_end = leaves.end();
3972
3973	for (it = leaves.begin(); it != it_end; ++ it)
3974	{
3975	KdViewCell kdVc = dynamic_cast<KdViewCell >(*it);
3976	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
3977	}
3978	}
3979
3980
3981	int KdViewCellsManager::GetType() const
3982	{
3983	return ViewCellsManager::KD;
3984	}
3985
3986
3987
3988	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
3989	{
3990	KdNode *node = leaf;
3991
3992	while (node->mParent && node->mDepth > mKdPvsDepth)
3993	node = node->mParent;
3994
3995	return node;
3996	}
3997
3998	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
3999	const Vector3 &termination,
4000	ViewCellContainer &viewcells)
4001	{
4002	return mKdTree->CastLineSegment(origin, termination, viewcells);
4003	}
4004
4005
4006	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4007	{
4008	// TODO
4009	}
4010
4011
4012
4013	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4014	vector<MergeCandidate> &candidates)
4015	{
4016	// TODO
4017	}
4018
4019
4020
4021	/**************************************************************************/
4022	/* VspBspViewCellsManager implementation */
4023	/**************************************************************************/
4024
4025
4026	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4027	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4028	{
4029	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4030	mVspBspTree->SetViewCellsManager(this);
4031	mVspBspTree->mViewCellsTree = mViewCellsTree;
4032	}
4033
4034
4035	VspBspViewCellsManager::~VspBspViewCellsManager()
4036	{
4037	}
4038
4039
4040	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4041	{
4042	if (0 && mVspBspTree->mUseAreaForPvs)
4043	return GetArea(viewCell) / GetAccVcArea();
4044	else
4045	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4046	}
4047
4048
4049	void VspBspViewCellsManager::CollectViewCells()
4050	{
4051	// view cells tree constructed?
4052	if (!ViewCellsTreeConstructed())
4053	{
4054	mVspBspTree->CollectViewCells(mViewCells, false);
4055	}
4056	else
4057	{
4058	// we can use the view cells tree hierarchy to get the right set
4059	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4060	}
4061	}
4062
4063
4064	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4065	vector<MergeCandidate> &candidates)
4066	{
4067	cout << "collecting merge candidates ... " << endl;
4068
4069	if (mUseRaysForMerge)
4070	{
4071	mVspBspTree->CollectMergeCandidates(rays, candidates);
4072	}
4073	else
4074	{
4075	vector<BspLeaf *> leaves;
4076	mVspBspTree->CollectLeaves(leaves);
4077
4078	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4079	}
4080
4081	cout << "fininshed collecting candidates" << endl;
4082	}
4083
4084
4085	bool VspBspViewCellsManager::ViewCellsConstructed() const
4086	{
4087	return mVspBspTree->GetRoot() != NULL;
4088	}
4089
4090
4091	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4092	{
4093	return new BspViewCell(mesh);
4094	}
4095
4096
4097	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4098	const VssRayContainer &rays)
4099	{
4100	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4101
4102	// if view cells were already constructed
4103	if (ViewCellsConstructed())
4104	{
4105	return 0;
4106	}
4107
4108	int sampleContributions = 0;
4109	VssRayContainer sampleRays;
4110
4111	const int limit = min(mInitialSamples, (int)rays.size());
4112
4113	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4114	<< ", actual rays: " << (int)rays.size() << endl;
4115
4116	VssRayContainer savedRays;
4117
4118	if (SAMPLE_AFTER_SUBDIVISION)
4119	{
4120	VssRayContainer constructionRays;
4121
4122	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4123
4124	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4125	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4126
4127	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4128	}
4129	else
4130	{
4131	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4132	mVspBspTree->Construct(rays, &mViewSpaceBox);
4133	}
4134
4135	// collapse invalid regions
4136	cout << "collapsing invalid tree regions ... ";
4137	long startTime = GetTime();
4138
4139	const int collapsedLeaves = mVspBspTree->CollapseTree();
4140	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4141	<< " seconds" << endl;
4142
4143	cout << "finished" << endl;
4144
4145	/////////////////
4146	//-- stats after construction
4147
4148	Debug << mVspBspTree->GetStatistics() << endl;
4149
4150	ResetViewCells();
4151	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4152
4153
4154	//////////////////////
4155	//-- recast the rest of the rays
4156
4157	startTime = GetTime();
4158
4159	cout << "Computing remaining ray contributions ... ";
4160
4161	if (SAMPLE_AFTER_SUBDIVISION)
4162	ComputeSampleContributions(savedRays, true, false);
4163
4164	cout << "finished" << endl;
4165
4166	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4167	<< " secs" << endl;
4168
4169	cout << "construction finished" << endl;
4170
4171	if (0)
4172	{ ////////
4173	//-- real meshes are contructed at this stage
4174	cout << "finalizing view cells ... ";
4175	FinalizeViewCells(true);
4176	cout << "finished" << endl;
4177	}
4178
4179	return sampleContributions;
4180	}
4181
4182
4183	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4184	const ObjectContainer &objects)
4185	{
4186	int vcSize = 0;
4187	int pvsSize = 0;
4188
4189	//-- merge view cells
4190	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4191	long startTime = GetTime();
4192
4193
4194	if (mMergeViewCells)
4195	{
4196	// TODO: should be done BEFORE the ray casting
4197	// compute tree by merging the nodes based on cost heuristics
4198	mViewCellsTree->ConstructMergeTree(rays, objects);
4199	}
4200	else
4201	{
4202	// compute tree by merging the nodes of the spatial hierarchy
4203	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4204	mViewCellsTree->SetRoot(root);
4205
4206	// compute pvs
4207	ObjectPvs pvs;
4208	UpdatePvsForEvaluation(root, pvs);
4209	}
4210
4211	if (1)
4212	{
4213	char mstats[100];
4214	ObjectPvs pvs;
4215
4216	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4217	mViewCellsTree->ExportStats(mstats);
4218	}
4219
4220	cout << "merged view cells in "
4221	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4222
4223	Debug << "Postprocessing: Merged view cells in "
4224	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4225
4226
4227	//////////////////
4228	//-- stats and visualizations
4229
4230	int savedColorCode = mColorCode;
4231
4232	// get currently active view cell set
4233	ResetViewCells();
4234	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4235
4236	if (mShowVisualization) // export merged view cells
4237	{
4238	mColorCode = 0;
4239	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4240
4241	cout << "exporting view cells after merge ... ";
4242
4243	if (exporter)
4244	{
4245	if (0)
4246	exporter->SetWireframe();
4247	else
4248	exporter->SetFilled();
4249
4250	ExportViewCellsForViz(exporter, NULL, GetClipPlane());
4251
4252	if (mExportGeometry)
4253	{
4254	Material m;
4255	m.mDiffuseColor = RgbColor(0, 1, 0);
4256	exporter->SetForcedMaterial(m);
4257	exporter->SetFilled();
4258
4259	exporter->ExportGeometry(objects);
4260	}
4261
4262	delete exporter;
4263	}
4264	cout << "finished" << endl;
4265	}
4266
4267	if (mShowVisualization)
4268	{
4269	// use pvs size for color coding
4270	mColorCode = 1;
4271	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
4272
4273	cout << "exporting view cells after merge (pvs size) ... ";
4274
4275	if (exporter)
4276	{
4277	exporter->SetFilled();
4278
4279	ExportViewCellsForViz(exporter, NULL, GetClipPlane());
4280
4281	if (mExportGeometry)
4282	{
4283	Material m;
4284	m.mDiffuseColor = RgbColor(0, 1, 0);
4285	exporter->SetForcedMaterial(m);
4286	exporter->SetFilled();
4287
4288	exporter->ExportGeometry(objects);
4289	}
4290
4291	delete exporter;
4292	}
4293	cout << "finished" << endl;
4294	}
4295
4296	mColorCode = savedColorCode;
4297	}
4298
4299
4300	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
4301	const ObjectContainer &objects)
4302	{
4303	mRenderer->RenderScene();
4304
4305	SimulationStatistics ss;
4306	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4307	Debug << "render time before refine\n\n" << ss << endl;
4308
4309	const long startTime = GetTime();
4310	cout << "Refining the merged view cells ... ";
4311
4312	// refining the merged view cells
4313	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
4314
4315	//-- stats and visualizations
4316	cout << "finished" << endl;
4317	cout << "refined " << refined << " view cells in "
4318	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4319
4320	Debug << "Postprocessing: refined " << refined << " view cells in "
4321	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4322	}
4323
4324
4325	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
4326	const VssRayContainer &rays)
4327	{
4328	if (!ViewCellsConstructed())
4329	{
4330	Debug << "postprocess error: no view cells constructed" << endl;
4331	return 0;
4332	}
4333
4334	// view cells already finished before post processing step
4335	// (i.e. because they were loaded)
4336	if (mViewCellsFinished)
4337	{
4338	FinalizeViewCells(true);
4339	EvaluateViewCellsStats();
4340
4341	return 0;
4342	}
4343
4344	// check if new view cells turned invalid
4345	int minPvs, maxPvs;
4346
4347	if (0)
4348	{
4349	minPvs = mMinPvsSize;
4350	maxPvs = mMaxPvsSize;
4351	}
4352	else
4353	{
4354	// problem matt: why did I start here from zero?
4355	minPvs = 0;
4356	maxPvs = mMaxPvsSize;
4357	}
4358
4359	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4360	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
4361
4362	SetValidity(minPvs, maxPvs);
4363
4364	// update valid view space according to valid view cells
4365	if (0) mVspBspTree->ValidateTree();
4366
4367	// area has to be recomputed
4368	mTotalAreaValid = false;
4369	VssRayContainer postProcessRays;
4370	GetRaySets(rays, mPostProcessSamples, postProcessRays);
4371
4372	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
4373
4374	// should maybe be done here to allow merge working
4375	// with area or volume and to correct the rendering statistics
4376	if (0) FinalizeViewCells(false);
4377
4378	//////////
4379	//-- merge the individual view cells
4380	MergeViewCells(postProcessRays, objects);
4381
4382	// refines the merged view cells
4383	if (0) RefineViewCells(postProcessRays, objects);
4384
4385
4386	///////////
4387	//-- render simulation after merge + refine
4388
4389	cout << "\nview cells partition render time before compress" << endl << endl;;
4390	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
4391	SimulationStatistics ss;
4392	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
4393	cout << ss << endl;
4394
4395
4396	////////////
4397	//-- compression
4398	//#if HAS_TO_BE_REDONE
4399	if (ViewCellsTreeConstructed() && mCompressViewCells)
4400	{
4401	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4402	Debug << "number of entries before compress: " << pvsEntries << endl;
4403
4404	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
4405
4406	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
4407	Debug << "number of entries after compress: " << pvsEntries << endl;
4408	}
4409	//#endif
4410
4411	// collapse sibling leaves that share the same view cell
4412	if (0) mVspBspTree->CollapseTree();
4413
4414	// recompute view cell list and statistics
4415	ResetViewCells();
4416
4417	// compute final meshes and volume / area
4418	if (1) FinalizeViewCells(true);
4419
4420	return 0;
4421	}
4422
4423
4424	int VspBspViewCellsManager::GetType() const
4425	{
4426	return VSP_BSP;
4427	}
4428
4429
4430	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4431	{
4432	// terminate recursion
4433	if (root->IsLeaf())
4434	{
4435	BspLeaf leaf = dynamic_cast<BspLeaf >(root);
4436	leaf->GetViewCell()->SetMergeCost(0.0f);
4437	return leaf->GetViewCell();
4438	}
4439
4440
4441	BspInterior interior = dynamic_cast<BspInterior >(root);
4442	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4443
4444	// evaluate merge cost for priority traversal
4445	float mergeCost = 1.0f / (float)root->mTimeStamp;
4446	viewCellInterior->SetMergeCost(mergeCost);
4447
4448	float volume = 0;
4449
4450	BspNode *front = interior->GetFront();
4451	BspNode *back = interior->GetBack();
4452
4453
4454	ObjectPvs frontPvs, backPvs;
4455
4456	//-- recursivly compute child hierarchies
4457	ViewCell *backVc = ConstructSpatialMergeTree(back);
4458	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4459
4460
4461	viewCellInterior->SetupChildLink(backVc);
4462	viewCellInterior->SetupChildLink(frontVc);
4463
4464	volume += backVc->GetVolume();
4465	volume += frontVc->GetVolume();
4466
4467	viewCellInterior->SetVolume(volume);
4468
4469	return viewCellInterior;
4470	}
4471
4472
4473	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
4474	{
4475	if (!ViewCellsConstructed())
4476	return ViewCellsManager::GetViewPoint(viewPoint);
4477
4478	// TODO: set reasonable limit
4479	const int limit = 20;
4480
4481	for (int i = 0; i < limit; ++ i)
4482	{
4483	viewPoint = mViewSpaceBox.GetRandomPoint();
4484	if (mVspBspTree->ViewPointValid(viewPoint))
4485	{
4486	return true;
4487	}
4488	}
4489
4490	Debug << "failed to find valid view point, taking " << viewPoint << endl;
4491	return false;
4492	}
4493
4494
4495	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
4496	{
4497	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
4498	// validy update in preprocessor for all managers)
4499	return ViewCellsManager::ViewPointValid(viewPoint);
4500
4501	// return mViewSpaceBox.IsInside(viewPoint) &&
4502	// mVspBspTree->ViewPointValid(viewPoint);
4503	}
4504
4505
4506	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
4507	const VssRayContainer &sampleRays)
4508	{
4509	if (!ViewCellsConstructed())
4510	return;
4511
4512	VssRayContainer visRays;
4513	GetRaySets(sampleRays, mVisualizationSamples, visRays);
4514
4515	if (1)
4516	{
4517	//////////////////
4518	//-- export final view cell partition
4519
4520	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4521
4522	if (exporter)
4523	{
4524	cout << "exporting view cells after post process ... ";
4525	if (0)
4526	{ // export view space box
4527	exporter->SetWireframe();
4528	exporter->ExportBox(mViewSpaceBox);
4529	exporter->SetFilled();
4530	}
4531
4532	Material m;
4533	m.mDiffuseColor.r = 0.0f;
4534	m.mDiffuseColor.g = 0.5f;
4535	m.mDiffuseColor.b = 0.5f;
4536
4537	exporter->SetForcedMaterial(m);
4538
4539	if (1 && mExportGeometry)
4540	{
4541	exporter->ExportGeometry(objects);
4542	}
4543
4544	if (0 && mExportRays)
4545	{
4546	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
4547	}
4548	ExportViewCellsForViz(exporter, NULL, GetClipPlane());
4549
4550	delete exporter;
4551	cout << "finished" << endl;
4552	}
4553	}
4554
4555	////////////////
4556	//-- visualization of the BSP splits
4557
4558	bool exportSplits = false;
4559	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
4560
4561	if (exportSplits)
4562	{
4563	cout << "exporting splits ... ";
4564	ExportSplits(objects, visRays);
4565	cout << "finished" << endl;
4566	}
4567
4568	////////
4569	//-- export single view cells
4570
4571	int leafOut;
4572	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4573	const int raysOut = 100;
4574
4575	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
4576	}
4577
4578
4579	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
4580	const VssRayContainer &rays)
4581	{
4582	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4583
4584	if (exporter)
4585	{
4586	Material m;
4587	m.mDiffuseColor = RgbColor(1, 0, 0);
4588	exporter->SetForcedMaterial(m);
4589	exporter->SetWireframe();
4590
4591	exporter->ExportBspSplits(*mVspBspTree, true);
4592
4593	// take forced material, else big scenes cannot be viewed
4594	m.mDiffuseColor = RgbColor(0, 1, 0);
4595	exporter->SetForcedMaterial(m);
4596	exporter->SetFilled();
4597
4598	exporter->ResetForcedMaterial();
4599
4600	// export rays
4601	if (mExportRays)
4602	{
4603	exporter->ExportRays(rays, RgbColor(1, 1, 0));
4604	}
4605
4606	if (mExportGeometry)
4607	{
4608	exporter->ExportGeometry(objects);
4609	}
4610	delete exporter;
4611	}
4612	}
4613
4614
4615	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4616	const int maxViewCells,
4617	const bool sortViewCells,
4618	const bool exportPvs,
4619	const bool exportRays,
4620	const int maxRays,
4621	const string prefix,
4622	VssRayContainer *visRays)
4623	{
4624	if (sortViewCells)
4625	{
4626	// sort view cells to visualize the largest view cells
4627	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4628	}
4629
4630	//////////
4631	//-- some view cells for output
4632
4633	ViewCell::NewMail();
4634	const int limit = min(maxViewCells, (int)mViewCells.size());
4635
4636	for (int i = 0; i < limit; ++ i)
4637	{
4638	cout << "creating output for view cell " << i << " ... ";
4639
4640	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
4641	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
4642
4643	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
4644	continue;
4645
4646	vc->Mail();
4647
4648	ObjectPvs pvs;
4649	mViewCellsTree->GetPvs(vc, pvs);
4650
4651	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
4652	Exporter *exporter = Exporter::GetExporter(s);
4653
4654	const float pvsCost = mViewCellsTree->GetPvsCost(vc);
4655	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
4656
4657	if (exportRays)
4658	{
4659	////////////
4660	//-- export rays piercing this view cell
4661
4662	// take rays stored with the view cells during subdivision
4663	VssRayContainer vcRays;
4664	VssRayContainer collectRays;
4665
4666	// collect initial view cells
4667	ViewCellContainer leaves;
4668	mViewCellsTree->CollectLeaves(vc, leaves);
4669
4670	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4671	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4672	{
4673	BspLeaf vcLeaf = dynamic_cast<BspViewCell >(*vit)->mLeaves[0];
4674	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
4675
4676	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
4677	{
4678	collectRays.push_back(*rit);
4679	}
4680	}
4681
4682	const int raysOut = min((int)collectRays.size(), maxRays);
4683
4684	// prepare some rays for output
4685	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4686	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4687	{
4688	const float p = RandomValue(0.0f, (float)collectRays.size());
4689
4690	if (p < raysOut)
4691	{
4692	vcRays.push_back(*rit);
4693	}
4694	}
4695
4696	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
4697	}
4698
4699	////////////////
4700	//-- export view cell geometry
4701
4702	exporter->SetWireframe();
4703
4704	Material m;//= RandomMaterial();
4705	m.mDiffuseColor = RgbColor(0, 1, 0);
4706	exporter->SetForcedMaterial(m);
4707
4708	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4709	exporter->SetFilled();
4710
4711	if (exportPvs)
4712	{
4713	Intersectable::NewMail();
4714
4715	ObjectPvsIterator pit = pvs.GetIterator();
4716
4717	cout << endl;
4718
4719	// output PVS of view cell
4720	while (pit.HasMoreEntries())
4721	{
4722	ObjectPvsEntry entry = pit.Next();
4723	Intersectable *intersect = entry.mObject;
4724
4725	if (!intersect->Mailed())
4726	{
4727	intersect->Mail();
4728
4729	m = RandomMaterial();
4730	exporter->SetForcedMaterial(m);
4731	exporter->ExportIntersectable(intersect);
4732	}
4733	}
4734	cout << endl;
4735	}
4736
4737	DEL_PTR(exporter);
4738	cout << "finished" << endl;
4739	}
4740	}
4741
4742
4743	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
4744	{
4745	Exporter *exporter = Exporter::GetExporter("filter.x3d");
4746
4747	Vector3 bsize = mViewSpaceBox.Size();
4748	const Vector3 viewPoint(mViewSpaceBox.Center());
4749	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
4750	const Vector3 width = Vector3(w);
4751
4752	PrVs testPrVs;
4753
4754	if (exporter)
4755	{
4756	ViewCellContainer viewCells;
4757
4758	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
4759
4760	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
4761
4762	exporter->SetWireframe();
4763
4764	exporter->SetForcedMaterial(RgbColor(1,1,1));
4765	exporter->ExportBox(tbox);
4766
4767	exporter->SetFilled();
4768
4769	exporter->SetForcedMaterial(RgbColor(0,1,0));
4770	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
4771
4772	//exporter->ResetForcedMaterial();
4773	exporter->SetForcedMaterial(RgbColor(0,0,1));
4774	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
4775
4776	exporter->SetForcedMaterial(RgbColor(1,0,0));
4777	exporter->ExportGeometry(objects);
4778
4779	delete exporter;
4780	}
4781	}
4782
4783
4784	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
4785	ViewCellContainer &viewCells) const
4786	{
4787	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
4788	}
4789
4790
4791	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
4792	const Vector3 &termination,
4793	ViewCellContainer &viewcells)
4794	{
4795	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
4796	}
4797
4798
4799	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
4800	{
4801	int numSamples;
4802
4803	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
4804	cout << "samples" << numSamples << endl;
4805
4806	vector<RenderCostSample> samples;
4807
4808	if (!mPreprocessor->GetRenderer())
4809	return;
4810
4811	//start the view point queries
4812	long startTime = GetTime();
4813	cout << "starting sampling of render cost ... ";
4814
4815	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
4816
4817	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
4818
4819
4820	// for each sample:
4821	// find view cells associated with the samples
4822	// store the sample pvs with the pvs associated with the view cell
4823	//
4824	// for each view cell:
4825	// compute difference point sampled pvs - view cell pvs
4826	// export geometry with color coded pvs difference
4827
4828	std::map<ViewCell *, ObjectPvs> sampleMap;
4829
4830	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
4831
4832	for (rit = samples.begin(); rit != rit_end; ++ rit)
4833	{
4834	RenderCostSample sample = *rit;
4835
4836	ViewCell *vc = GetViewCell(sample.mPosition);
4837
4838	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
4839
4840	if (it == sampleMap.end())
4841	{
4842	sampleMap[vc] = sample.mPvs;
4843	}
4844	else
4845	{
4846	(*it).second.MergeInPlace(sample.mPvs);
4847	}
4848	}
4849
4850	// visualize the view cells
4851	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
4852
4853	Material m;//= RandomMaterial();
4854
4855	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
4856	{
4857	ViewCell vc = (vit).first;
4858
4859	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
4860	const int pvsPtSamples = (*vit).second.GetSize();
4861
4862	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
4863	m.mDiffuseColor.b = 1.0f;
4864	//exporter->SetForcedMaterial(m);
4865	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
4866
4867	/* // counting the pvss
4868	for (rit = samples.begin(); rit != rit_end; ++ rit)
4869	{
4870	RenderCostSample sample = *rit;
4871	ViewCell *vc = GetViewCell(sample.mPosition);
4872
4873	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
4874	Mesh *hMesh = CreateMeshFromBox(box);
4875
4876	DEL_PTR(hMesh);
4877	}
4878	*/
4879	}
4880	}
4881
4882
4883	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4884	ViewCell *vc,
4885	const AxisAlignedBox3 *sceneBox,
4886	const AxisAlignedPlane *clipPlane
4887	) const
4888	{
4889	if (clipPlane)
4890	{
4891	const Plane3 plane = clipPlane->GetPlane();
4892
4893	ViewCellContainer leaves;
4894	mViewCellsTree->CollectLeaves(vc, leaves);
4895	ViewCellContainer::const_iterator it, it_end = leaves.end();
4896
4897	for (it = leaves.begin(); it != it_end; ++ it)
4898	{
4899	BspNodeGeometry geom;
4900	BspNodeGeometry front;
4901	BspNodeGeometry back;
4902
4903	mVspBspTree->ConstructGeometry(*it, geom);
4904
4905	const float eps = 0.0001f;
4906	const int cf = geom.Side(plane, eps);
4907
4908	if (cf == -1)
4909	{
4910	exporter->ExportPolygons(geom.GetPolys());
4911	}
4912	else if (cf == 0)
4913	{
4914	geom.SplitGeometry(front,
4915	back,
4916	plane,
4917	mViewSpaceBox,
4918	eps);
4919
4920	if (back.Valid())
4921	{
4922	exporter->ExportPolygons(back.GetPolys());
4923	}
4924	}
4925	}
4926	}
4927	else
4928	{
4929	// export mesh if available
4930	// TODO: some bug here?
4931	if (1 && vc->GetMesh())
4932	{
4933	exporter->ExportMesh(vc->GetMesh());
4934	}
4935	else
4936	{
4937	BspNodeGeometry geom;
4938	mVspBspTree->ConstructGeometry(vc, geom);
4939	exporter->ExportPolygons(geom.GetPolys());
4940	}
4941	}
4942	}
4943
4944
4945	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
4946	{
4947	ViewCellContainer leaves;
4948	mViewCellsTree->CollectLeaves(vc, leaves);
4949
4950	int maxDist = 0;
4951
4952	// compute max height difference
4953	for (int i = 0; i < (int)leaves.size(); ++ i)
4954	{
4955	for (int j = 0; j < (int)leaves.size(); ++ j)
4956	{
4957	BspLeaf leaf = dynamic_cast<BspViewCell >(leaves[i])->mLeaves[0];
4958
4959	if (i != j)
4960	{
4961	BspLeaf leaf2 =dynamic_cast<BspViewCell >(leaves[j])->mLeaves[0];
4962	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
4963
4964	if (dist > maxDist)
4965	maxDist = dist;
4966	}
4967	}
4968	}
4969
4970	return maxDist;
4971	}
4972
4973
4974	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4975	{
4976	if (!ViewCellsConstructed())
4977	return NULL;
4978
4979	if (!mViewSpaceBox.IsInside(point))
4980	return NULL;
4981
4982	return mVspBspTree->GetViewCell(point, active);
4983	}
4984
4985
4986	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
4987	{
4988	BspNodeGeometry geom;
4989	mVspBspTree->ConstructGeometry(vc, geom);
4990
4991	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4992	IncludeNodeGeomInMesh(geom, *mesh);
4993
4994	vc->SetMesh(mesh);
4995	}
4996
4997
4998	int VspBspViewCellsManager::CastBeam(Beam &beam)
4999	{
5000	return mVspBspTree->CastBeam(beam);
5001	}
5002
5003
5004	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5005	const bool createMesh)
5006	{
5007	float area = 0;
5008	float volume = 0;
5009
5010	ViewCellContainer leaves;
5011	mViewCellsTree->CollectLeaves(viewCell, leaves);
5012
5013	ViewCellContainer::const_iterator it, it_end = leaves.end();
5014
5015	for (it = leaves.begin(); it != it_end; ++ it)
5016	{
5017	BspNodeGeometry geom;
5018	mVspBspTree->ConstructGeometry(*it, geom);
5019
5020	const float lVol = geom.GetVolume();
5021	const float lArea = geom.GetArea();
5022
5023	area += lArea;
5024	volume += lVol;
5025
5026	if (createMesh)
5027	CreateMesh(*it);
5028	}
5029
5030	viewCell->SetVolume(volume);
5031	viewCell->SetArea(area);
5032	}
5033
5034
5035	void VspBspViewCellsManager::TestSubdivision()
5036	{
5037	ViewCellContainer leaves;
5038	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5039
5040	ViewCellContainer::const_iterator it, it_end = leaves.end();
5041
5042	const float vol = mViewSpaceBox.GetVolume();
5043	float subdivVol = 0;
5044	float newVol = 0;
5045
5046	for (it = leaves.begin(); it != it_end; ++ it)
5047	{
5048	BspNodeGeometry geom;
5049	mVspBspTree->ConstructGeometry(*it, geom);
5050
5051	const float lVol = geom.GetVolume();
5052
5053	newVol += lVol;
5054	subdivVol += (*it)->GetVolume();
5055
5056	float thres = 0.9f;
5057	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5058	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5059	}
5060
5061	Debug << "exact volume: " << vol << endl;
5062	Debug << "subdivision volume: " << subdivVol << endl;
5063	Debug << "new volume: " << newVol << endl;
5064	}
5065
5066
5067	void VspBspViewCellsManager::PrepareLoadedViewCells()
5068	{
5069	// TODO: do I still need this here?
5070	if (0)
5071	mVspBspTree->RepairViewCellsLeafLists();
5072	}
5073
5074
5075
5076	/**************************************************************************/
5077	/* VspOspViewCellsManager implementation */
5078	/**************************************************************************/
5079
5080
5081	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree, const string &hierarchyType)
5082	: ViewCellsManager(vcTree)
5083	{
5084	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5085
5086	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5087	mHierarchyManager->SetViewCellsManager(this);
5088	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5089	}
5090
5091
5092	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5093	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5094	{
5095	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5096
5097	mHierarchyManager->SetViewCellsManager(this);
5098	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5099	}
5100
5101	Intersectable *
5102	VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
5103	{
5104	return mHierarchyManager->GetIntersectable(ray, isTermination);
5105	}
5106
5107	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5108	{
5109	HierarchyManager *hierarchyManager;
5110
5111	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5112	{
5113	Debug << "hierarchy manager: osp" << endl;
5114	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5115	}
5116	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5117	{
5118	Debug << "hierarchy manager: bvh" << endl;
5119	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5120	}
5121	else // only view space partition
5122	{
5123	Debug << "hierarchy manager: obj" << endl;
5124	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5125	}
5126
5127	return hierarchyManager;
5128	}
5129
5130
5131	VspOspViewCellsManager::~VspOspViewCellsManager()
5132	{
5133	DEL_PTR(mHierarchyManager);
5134	}
5135
5136
5137	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5138	{
5139	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5140	}
5141
5142
5143	void VspOspViewCellsManager::CollectViewCells()
5144	{
5145	// view cells tree constructed
5146	if (!ViewCellsTreeConstructed())
5147	{
5148	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5149	}
5150	else
5151	{ // we can use the view cells tree hierarchy to get the right set
5152	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5153	}
5154	}
5155
5156
5157	bool VspOspViewCellsManager::ViewCellsConstructed() const
5158	{
5159	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5160	}
5161
5162
5163	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5164	{
5165	return new VspViewCell(mesh);
5166	}
5167
5168
5169	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5170	const VssRayContainer &rays)
5171	{
5172	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5173
5174	// skip rest if view cells were already constructed
5175	if (ViewCellsConstructed())
5176	return 0;
5177
5178	int sampleContributions = 0;
5179	VssRayContainer sampleRays;
5180
5181	int limit = min (mInitialSamples, (int)rays.size());
5182
5183	VssRayContainer constructionRays;
5184	VssRayContainer savedRays;
5185
5186	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5187	<< ", actual rays: " << (int)rays.size() << endl;
5188
5189	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5190
5191	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5192	Debug << "saved rays: " << (int)savedRays.size() << endl;
5193
5194	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5195
5196	#if TEST_EVALUATION
5197	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5198	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5199	{
5200	storedRays.push_back(new VssRay((tit)));
5201	}
5202	#endif
5203
5204	/////////////////////////
5205	//-- print satistics for subdivision and view cells
5206
5207	Debug << endl << endl << *mHierarchyManager << endl;
5208
5209	ResetViewCells();
5210	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5211
5212	//////////////
5213	//-- recast rest of rays
5214
5215	const long startTime = GetTime();
5216	cout << "Computing remaining ray contributions ... ";
5217
5218	if (SAMPLE_AFTER_SUBDIVISION)
5219	ComputeSampleContributions(savedRays, true, false);
5220
5221	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5222	<< " secs" << endl;
5223
5224	if (0)
5225	{ // real meshes are constructed at this stage
5226	cout << "finalizing view cells ... ";
5227	FinalizeViewCells(true);
5228	cout << "finished" << endl;
5229	}
5230
5231	return sampleContributions;
5232	}
5233
5234
5235	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5236	const VssRayContainer &rays)
5237	{
5238	if (!ViewCellsConstructed())
5239	{
5240	Debug << "postprocess error: no view cells constructed" << endl;
5241	return 0;
5242	}
5243
5244	// if view cells were already constructed before post processing step
5245	// (e.g., because they were loaded), we are finished
5246	if (mViewCellsFinished)
5247	{
5248	FinalizeViewCells(true);
5249	EvaluateViewCellsStats();
5250
5251	return 0;
5252	}
5253
5254	// check if new view cells turned invalid
5255	int minPvs, maxPvs;
5256
5257	if (0)
5258	{
5259	minPvs = mMinPvsSize;
5260	maxPvs = mMaxPvsSize;
5261	}
5262	else
5263	{
5264	// problem matt: why did I start here from zero?
5265	minPvs = 0;
5266	maxPvs = mMaxPvsSize;
5267	}
5268
5269	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5270	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5271
5272	SetValidity(minPvs, maxPvs);
5273
5274
5275	// area is not up to date, has to be recomputed
5276	mTotalAreaValid = false;
5277	VssRayContainer postProcessRays;
5278	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5279
5280	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5281
5282
5283	// compute tree by merging the nodes of the spatial hierarchy
5284	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
5285	mViewCellsTree->SetRoot(root);
5286
5287	//////////////////////////
5288	//-- update pvs up to the root of the hierarchy
5289
5290	ObjectPvs pvs;
5291	UpdatePvsForEvaluation(root, pvs);
5292
5293
5294	//////////////////////
5295	//-- render simulation after merge + refine
5296
5297	cout << "\nview cells partition render time before compress" << endl << endl;
5298	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
5299	SimulationStatistics ss;
5300	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5301	cout << ss << endl;
5302
5303
5304	///////////
5305	//-- compression
5306
5307	if (ViewCellsTreeConstructed() && mCompressViewCells)
5308	{
5309	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
5310	Debug << "number of entries before compress: " << pvsEntries << endl;
5311
5312	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
5313
5314	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
5315	Debug << "number of entries after compress: " << pvsEntries << endl;
5316	}
5317
5318	/////////////
5319	//-- some tasks still to do on the view cells:
5320	//-- Compute meshes from view cell geometry, evaluate volume and / or area
5321
5322	if (1) FinalizeViewCells(true);
5323
5324	return 0;
5325	}
5326
5327
5328	int VspOspViewCellsManager::GetType() const
5329	{
5330	return VSP_OSP;
5331	}
5332
5333
5334	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
5335	{
5336	// terminate recursion
5337	if (root->IsLeaf())
5338	{
5339	VspLeaf leaf = dynamic_cast<VspLeaf >(root);
5340	leaf->GetViewCell()->SetMergeCost(0.0f);
5341	return leaf->GetViewCell();
5342	}
5343
5344	VspInterior interior = dynamic_cast<VspInterior >(root);
5345	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5346
5347	// evaluate merge cost for priority traversal
5348	const float mergeCost = -(float)root->mTimeStamp;
5349	viewCellInterior->SetMergeCost(mergeCost);
5350
5351	float volume = 0;
5352
5353	VspNode *front = interior->GetFront();
5354	VspNode *back = interior->GetBack();
5355
5356	ObjectPvs frontPvs, backPvs;
5357
5358	/////////
5359	//-- recursivly compute child hierarchies
5360
5361	ViewCell *backVc = ConstructSpatialMergeTree(back);
5362	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5363
5364	viewCellInterior->SetupChildLink(backVc);
5365	viewCellInterior->SetupChildLink(frontVc);
5366
5367	volume += backVc->GetVolume();
5368	volume += frontVc->GetVolume();
5369
5370	viewCellInterior->SetVolume(volume);
5371
5372	return viewCellInterior;
5373	}
5374
5375
5376	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5377	{
5378	if (!ViewCellsConstructed())
5379	return ViewCellsManager::GetViewPoint(viewPoint);
5380
5381	// TODO: set reasonable limit
5382	const int limit = 20;
5383
5384	for (int i = 0; i < limit; ++ i)
5385	{
5386	viewPoint = mViewSpaceBox.GetRandomPoint();
5387
5388	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
5389	{
5390	return true;
5391	}
5392	}
5393
5394	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5395	return false;
5396	}
5397
5398
5399	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5400	ViewCell *vc,
5401	const AxisAlignedBox3 *sceneBox,
5402	const AxisAlignedPlane *clipPlane
5403	) const
5404	{
5405	ViewCellContainer leaves;
5406	mViewCellsTree->CollectLeaves(vc, leaves);
5407	ViewCellContainer::const_iterator it, it_end = leaves.end();
5408
5409	Plane3 plane;
5410	if (clipPlane)
5411	{
5412	// arbitrary plane definition
5413	plane = clipPlane->GetPlane();
5414	}
5415
5416	for (it = leaves.begin(); it != it_end; ++ it)
5417	{
5418	VspViewCell vspVc = dynamic_cast<VspViewCell >(*it);
5419	VspLeaf *l = vspVc->mLeaves[0];
5420
5421	const AxisAlignedBox3 box =
5422	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
5423
5424	if (sceneBox && !Overlap(*sceneBox, box))
5425	continue;
5426
5427	if (clipPlane)
5428	{
5429	if (box.Side(plane) == -1)
5430	{
5431	exporter->ExportBox(box);
5432	}
5433	else if (box.Side(plane) == 0)
5434	{
5435	// intersection
5436	AxisAlignedBox3 fbox, bbox;
5437	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
5438	exporter->ExportBox(bbox);
5439	}
5440	}
5441	else
5442	{
5443	exporter->ExportBox(box);
5444	}
5445	}
5446	}
5447
5448
5449	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5450	{
5451	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5452	// validy update in preprocessor for all managers)
5453	return ViewCellsManager::ViewPointValid(viewPoint);
5454
5455	// return mViewSpaceBox.IsInside(viewPoint) &&
5456	// mVspTree->ViewPointValid(viewPoint);
5457	}
5458
5459
5460	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
5461	const VssRayContainer &sampleRays)
5462	{
5463	if (!ViewCellsConstructed())
5464	return;
5465
5466	VssRayContainer visRays;
5467	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5468
5469	////////////
5470	//-- export final view cells
5471
5472	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5473
5474	if (exporter)
5475	{
5476	// hack color code (show pvs size)
5477	const int savedColorCode = mColorCode;
5478	mColorCode = 0;
5479
5480	const long starttime = GetTime();
5481	cout << "exporting final view cells (after initial construction + post process) ... ";
5482
5483	// matt: hack for clamping scene
5484	AxisAlignedBox3 bbox = mViewSpaceBox;
5485	bbox.Scale(Vector3(0.5, 1, 0.5));
5486
5487	if (CLAMP_TO_BOX)
5488	{
5489	exporter->SetWireframe();
5490	exporter->ExportBox(bbox);
5491	exporter->SetFilled();
5492	}
5493
5494	if (0 && mExportGeometry)
5495	{
5496	exporter->ExportGeometry(objects, true, CLAMP_TO_BOX ? &bbox : NULL);
5497	}
5498
5499	if (1 && mExportRays)
5500	{
5501	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
5502	}
5503
5504	mHierarchyManager->ExportObjectSpaceHierarchy(exporter,
5505	objects, CLAMP_TO_BOX ? &bbox : NULL, false);
5506	ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, GetClipPlane());
5507
5508	delete exporter;
5509	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5510	mColorCode = savedColorCode;
5511	}
5512
5513	// export final object partition
5514	exporter = Exporter::GetExporter("final_object_partition.wrl");
5515
5516	if (exporter)
5517	{
5518	const long starttime = GetTime();
5519
5520	// matt: hack for making visualization smaller in size
5521	AxisAlignedBox3 bbox = mHierarchyManager->GetObjectSpaceBox();
5522	bbox.Scale(Vector3(0.5, 1, 0.5));
5523
5524	cout << "exporting object space hierarchy ... ";
5525	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects, CLAMP_TO_BOX ? &bbox : NULL);
5526
5527	delete exporter;
5528	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
5529	}
5530
5531
5532	// visualization of the view cells
5533	if (0) ExportMergedViewCells(objects);
5534
5535	// export some view cell
5536	int leafOut;
5537	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5538	const int raysOut = 100;
5539
5540	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5541	}
5542
5543
5544	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5545	const int maxViewCells,
5546	const bool sortViewCells,
5547	const bool exportPvs,
5548	const bool exportRays,
5549	const int maxRays,
5550	const string prefix,
5551	VssRayContainer *visRays)
5552	{
5553	if (sortViewCells)
5554	{
5555	// sort view cells to visualize the view cells with highest render cost
5556	stable_sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5557	}
5558
5559	ViewCell::NewMail();
5560	const int limit = min(maxViewCells, (int)mViewCells.size());
5561
5562	cout << "\nExporting " << limit << " single view cells: " << endl;
5563
5564	for (int i = 0; i < limit; ++ i)
5565	{
5566	cout << "creating output for view cell " << i << " ... ";
5567
5568	// largest view cell pvs first of random view cell
5569	ViewCell *vc = sortViewCells ?
5570	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
5571
5572	if (vc->Mailed()) // already used
5573	continue;
5574
5575	vc->Mail();
5576
5577	ObjectPvs pvs;
5578	mViewCellsTree->GetPvs(vc, pvs);
5579
5580	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5581	Exporter *exporter = Exporter::GetExporter(s);
5582
5583	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;
5584
5585	if (exportPvs)
5586	{
5587	Material m;
5588
5589	Intersectable::NewMail();
5590
5591	ObjectPvsIterator pit = pvs.GetIterator();
5592
5593	// output PVS of view cell
5594	while (pit.HasMoreEntries())
5595	{
5596	ObjectPvsEntry entry = pit.Next();
5597
5598	Intersectable *intersect = entry.mObject;
5599
5600	if (!intersect->Mailed())
5601	{
5602	m = RandomMaterial();
5603	exporter->SetForcedMaterial(m);
5604
5605	exporter->ExportIntersectable(intersect);
5606	intersect->Mail();
5607	}
5608	}
5609	}
5610
5611	if (exportRays)
5612	{
5613	////////////
5614	//-- export the sample rays
5615
5616	// output rays stored with the view cells during subdivision
5617	VssRayContainer vcRays;
5618	VssRayContainer collectRays;
5619
5620	// collect intial view cells
5621	ViewCellContainer leaves;
5622	mViewCellsTree->CollectLeaves(vc, leaves);
5623
5624	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5625
5626	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5627	{
5628	VspLeaf vcLeaf = dynamic_cast<VspViewCell >(*vit)->mLeaves[0];
5629	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5630
5631	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5632	{
5633	collectRays.push_back(*rit);
5634	}
5635	}
5636
5637	const int raysOut = min((int)collectRays.size(), maxRays);
5638
5639	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5640
5641	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5642	{
5643	const float p = RandomValue(0.0f, (float)collectRays.size());
5644
5645	if (p < raysOut)
5646	vcRays.push_back(*rit);
5647	}
5648
5649	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5650	}
5651
5652
5653	/////////////////
5654	//-- export view cell geometry
5655
5656	exporter->SetWireframe();
5657
5658	Material m;
5659	m.mDiffuseColor = RgbColor(0, 1, 0);
5660	exporter->SetForcedMaterial(m);
5661
5662	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5663	exporter->SetFilled();
5664
5665	DEL_PTR(exporter);
5666	cout << "finished" << endl;
5667	}
5668
5669	cout << endl;
5670	}
5671
5672
5673	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5674	ViewCellContainer &viewCells) const
5675	{
5676	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
5677	}
5678
5679
5680	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
5681	const Vector3 &termination,
5682	ViewCellContainer &viewcells)
5683	{
5684	return mHierarchyManager->GetVspTree()->CastLineSegment(origin, termination, viewcells);
5685	}
5686
5687
5688	bool VspOspViewCellsManager::ExportViewCells(const string filename,
5689	const bool exportPvs,
5690	const ObjectContainer &objects)
5691	{
5692	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
5693	return false;
5694
5695	const long starttime = GetTime();
5696	cout << "exporting view cells to xml ... ";
5697
5698	OUT_STREAM stream(filename.c_str());
5699
5700	// for output we need unique ids for each view cell
5701	CreateUniqueViewCellIds();
5702
5703	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
5704	stream << "<VisibilitySolution>" << endl;
5705
5706	if (exportPvs)
5707	{
5708	///////////////
5709	//-- export bounding boxes
5710	//-- The bounding boxes are used to identify
5711	//-- the objects in the rendering engine
5712	mHierarchyManager->ExportBoundingBoxes(stream, objects);
5713	}
5714
5715	//////////////////////////
5716	//-- export the view cells and the pvs
5717
5718	const int numViewCells = mCurrentViewCellsStats.viewCells;
5719
5720	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
5721	mViewCellsTree->Export(stream, exportPvs);
5722	stream << "</ViewCells>" << endl;
5723
5724	//////////////////////
5725	//-- export the view space hierarchy
5726
5727	stream << "<ViewSpaceHierarchy type=\"vsp\""
5728	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
5729	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
5730
5731	mHierarchyManager->GetVspTree()->Export(stream);
5732	stream << "</ViewSpaceHierarchy>" << endl;
5733
5734	//////////////////////
5735	//-- export the object space partition
5736
5737	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
5738
5739	stream << "</VisibilitySolution>" << endl;
5740	stream.close();
5741
5742	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
5743	return true;
5744	}
5745
5746
5747
5748	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
5749	const bool active) const
5750	{
5751	if (!ViewCellsConstructed())
5752	return NULL;
5753
5754	if (!mViewSpaceBox.IsInside(point))
5755	return NULL;
5756
5757	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
5758	}
5759
5760
5761	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
5762	{
5763	// matt: TODO
5764	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5765
5766	ViewCellContainer leaves;
5767	mViewCellsTree->CollectLeaves(vc, leaves);
5768
5769	ViewCellContainer::const_iterator it, it_end = leaves.end();
5770
5771	for (it = leaves.begin(); it != it_end; ++ it)
5772	{
5773	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaves[0];
5774	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5775	IncludeBoxInMesh(box, *mesh);
5776	}
5777
5778	vc->SetMesh(mesh);
5779	}
5780
5781
5782	int VspOspViewCellsManager::CastBeam(Beam &beam)
5783	{
5784	// matt: TODO
5785	return 0;
5786	}
5787
5788
5789	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
5790	{
5791	float area = 0;
5792	float volume = 0;
5793
5794	ViewCellContainer leaves;
5795	mViewCellsTree->CollectLeaves(viewCell, leaves);
5796
5797	ViewCellContainer::const_iterator it, it_end = leaves.end();
5798
5799	for (it = leaves.begin(); it != it_end; ++ it)
5800	{
5801	VspLeaf leaf = dynamic_cast<VspViewCell >(*it)->mLeaves[0];
5802
5803	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
5804
5805	const float lVol = box.GetVolume();
5806	const float lArea = box.SurfaceArea();
5807
5808	area += lArea;
5809	volume += lVol;
5810
5811	CreateMesh(*it);
5812	}
5813
5814	viewCell->SetVolume(volume);
5815	viewCell->SetArea(area);
5816	}
5817
5818
5819	float VspOspViewCellsManager::ComputeSampleContribution(VssRay &ray,
5820	const bool addRays,
5821	const bool storeViewCells)
5822	{
5823	ViewCellContainer viewcells;
5824
5825	ray.mPvsContribution = 0;
5826	ray.mRelativePvsContribution = 0.0f;
5827
5828	static Ray hray;
5829	hray.Init(ray);
5830	//hray.mFlags \|= Ray::CULL_BACKFACES;
5831	//Ray hray(ray);
5832
5833	float tmin = 0, tmax = 1.0;
5834
5835	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
5836	return 0;
5837
5838	Vector3 origin = hray.Extrap(tmin);
5839	Vector3 termination = hray.Extrap(tmax);
5840
5841	ViewCell::NewMail();
5842
5843	// traverse the view space subdivision
5844	CastLineSegment(origin, termination, viewcells);
5845
5846	if (storeViewCells)
5847	{
5848	// copy viewcells memory efficiently
5849	ray.mViewCells.reserve(viewcells.size());
5850	ray.mViewCells = viewcells;
5851	}
5852
5853	ViewCellContainer::const_iterator it = viewcells.begin();
5854
5855	for (; it != viewcells.end(); ++ it)
5856	{
5857	ViewCell viewcell = it;
5858
5859	if (viewcell->GetValid())
5860	{ // if ray not outside of view space
5861	float contribution;
5862
5863	if (ray.mTerminationObject)
5864	{
5865	// todo: maybe not correct for kd node pvs
5866	Intersectable *obj = mHierarchyManager->GetIntersectable(ray, true);
5867
5868	if (viewcell->GetPvs().GetSampleContribution(obj,
5869	ray.mPdf,
5870	contribution))
5871	{
5872	++ ray.mPvsContribution;
5873	}
5874
5875	ray.mRelativePvsContribution += contribution;
5876	}
5877
5878	////////////////
5879	//-- for directional sampling it is important to count only contributions
5880	//-- made in one direction!
5881	//-- the other contributions of this sample will be counted for the opposite ray!
5882	#if SAMPLE_ORIGIN_OBJECTS
5883	if (ray.mOriginObject &&
5884	viewcell->GetPvs().GetSampleContribution(ray.mOriginObject,
5885	ray.mPdf,
5886	contribution))
5887	{
5888	++ ray.mPvsContribution;
5889	ray.mRelativePvsContribution += contribution;
5890	}
5891	#endif
5892	}
5893	}
5894
5895	if (!addRays)
5896	{
5897	return ray.mRelativePvsContribution;
5898	}
5899
5900	// sampled objects are stored in the pvs
5901	for (it = viewcells.begin(); it != viewcells.end(); ++ it)
5902	{
5903	ViewCell viewCell = it;
5904
5905	if (!viewCell->GetValid())
5906	break;
5907
5908	AddSampleToPvs(
5909	ray.mTerminationObject,
5910	ray.mTermination,
5911	viewCell,
5912	ray.mPdf,
5913	ray.mRelativePvsContribution);
5914
5915	#if SAMPLE_ORIGIN_OBJECTS
5916
5917	AddSampleToPvs(
5918	ray.mOriginObject,
5919	ray.mOrigin,
5920	viewCell,
5921	ray.mPdf,
5922	ray.mRelativePvsContribution);
5923	#endif
5924	}
5925
5926
5927
5928	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
5929	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
5930	}
5931
5932
5933	bool VspOspViewCellsManager::AddSampleToPvs(Intersectable *obj,
5934	const Vector3 &hitPoint,
5935	ViewCell *vc,
5936	const float pdf,
5937	float &contribution) const
5938	{
5939	// The hierarchy manager decides about the type of sample cast
5940	return mHierarchyManager->AddSampleToPvs(obj, hitPoint, vc, pdf, contribution);
5941	}
5942
5943
5944	void VspOspViewCellsManager::PrepareLoadedViewCells()
5945	{
5946	// TODO
5947	}
5948
5949
5950	ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
5951	ObjectContainer *objects,
5952	const bool finalizeViewCells,
5953	BoundingBoxConverter *bconverter)
5954
5955	{
5956	ViewCellsManager *vm =
5957	ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
5958	#if 0
5959	// insert scene objects in tree
5960	mOspTree->InsertObjects(mOspTree->GetRoot(), *objects);
5961	#endif
5962	return vm;
5963	}
5964
5965	void
5966	VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
5967	{
5968	mHierarchyManager->CollectObjects(box, objects);
5969	}
5970
5971
5972	#if 1
5973
5974	void VspOspViewCellsManager::EvalViewCellPartition()
5975	{
5976	int samplesPerPass;
5977	int numSamples;
5978	int castSamples = 0;
5979	int oldSamples = 0;
5980	int samplesForStats;
5981	char statsPrefix[100];
5982	char suffix[100];
5983	int splitsStepSize;
5984
5985
5986	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
5987	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
5988	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
5989	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
5990	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
5991
5992	Debug << "step size: " << splitsStepSize << endl;
5993	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
5994	Debug << "view cell evaluation samples: " << numSamples << endl;
5995	Debug << "view cell stats prefix: " << statsPrefix << endl;
5996
5997	// should directional sampling be used?
5998	bool dirSamples =
5999	(mEvaluationSamplingType == SamplingStrategy::DIRECTION_BASED_DISTRIBUTION);
6000
6001	cout << "reseting pvs ... ";
6002
6003	// reset pvs and start over from zero
6004	mViewCellsTree->ResetPvs();
6005
6006	cout << "finished" << endl;
6007	cout << "Evaluating view cell partition ... " << endl;
6008
6009	while (castSamples < numSamples)
6010	{
6011	///////////////
6012	//-- we have to use uniform sampling strategy for construction rays
6013
6014	VssRayContainer evaluationSamples;
6015	const int samplingType = mEvaluationSamplingType;
6016
6017	long startTime = GetTime();
6018
6019	cout << "casting " << samplesPerPass << " samples ... ";
6020	Debug << "casting " << samplesPerPass << " samples ... ";
6021
6022	CastPassSamples(samplesPerPass, samplingType, evaluationSamples);
6023
6024	castSamples += samplesPerPass;
6025
6026	Real timeDiff = TimeDiff(startTime, GetTime());
6027
6028	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6029	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6030
6031	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6032	Debug << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6033
6034	startTime = GetTime();
6035
6036	ComputeSampleContributions(evaluationSamples, true, false);
6037
6038	timeDiff = TimeDiff(startTime, GetTime());
6039	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6040	Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6041
6042	if ((castSamples >= samplesForStats + oldSamples) \|\| (castSamples >= numSamples))
6043	{
6044	oldSamples += samplesForStats;
6045
6046	///////////
6047	//-- output stats
6048
6049	sprintf(suffix, "-%09d-eval.log", castSamples);
6050	const string filename = string(statsPrefix) + string(suffix);
6051
6052	startTime = GetTime();
6053
6054	cout << "compute new statistics ... " << endl;
6055
6056	ofstream ofstr(filename.c_str());
6057	mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false);
6058
6059	timeDiff = TimeDiff(startTime, GetTime());
6060	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6061	cout << "*************************************" << endl;
6062
6063	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6064
6065	#if 0
6066	////////////////////////////
6067	// filtered stats
6068	sprintf(suffix, "-%09d-eval-filter.log", castSamples);
6069	const string filename2 = string(statsPrefix) + string(suffix);
6070
6071	startTime = GetTime();
6072
6073	cout << "compute new statistics for filtered pvs ... " << endl;
6074
6075	ofstream ofstr2(filename2.c_str());
6076	mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);
6077
6078	timeDiff = TimeDiff(startTime, GetTime());
6079	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6080	cout << "*************************************" << endl;
6081
6082	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6083	#endif
6084
6085	// only for debugging purpose
6086	if (0)
6087	{
6088	ViewCellContainer viewCells;
6089	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);
6090
6091	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
6092	int pvsSize = 0;
6093
6094	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
6095	{
6096	pvsSize += (*vit)->GetPvs().GetSize();
6097	}
6098
6099	cout << "debug entries: " << pvsSize << ", memcost: " << (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
6100	}
6101	}
6102
6103	disposeRays(evaluationSamples, NULL);
6104	}
6105
6106	}
6107	#endif
6108	}

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

Download in other formats: