Context Navigation

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

Revision 2538, 176.7 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: