Context Navigation

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

Revision 1344, 139.7 KB checked in by mattausch, 18 years ago (diff)
worked on triangle processing. logical units will be created by grouping objects using their visibility definitions.

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

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

Download in other formats: