Context Navigation

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

Revision 2199, 177.7 KB checked in by mattausch, 17 years ago (diff)
using mutationsamples for evaluation

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

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

Download in other formats: