Context Navigation

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

Revision 2280, 177.0 KB checked in by mattausch, 18 years ago (diff)
removed dependency on ogre in gtpvisibility

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

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

Download in other formats: