Context Navigation

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

Revision 2228, 176.8 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: