Context Navigation

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

Revision 1756, 154.4 KB checked in by bittner, 18 years ago (diff)

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

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

Download in other formats: