Context Navigation

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

Revision 1001, 124.4 KB checked in by mattausch, 18 years ago (diff)
added mesh instance support improved support for occlusion queries + other extensions

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

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

Download in other formats: