Context Navigation

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

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

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

Download in other formats: