Context Navigation

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

Revision 2239, 176.9 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: