Context Navigation

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

Revision 2539, 179.8 KB checked in by mattausch, 17 years ago (diff)
fixed obj loading error

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

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

Download in other formats: