Context Navigation

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

Revision 991, 124.1 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: