Context Navigation

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

Revision 2571, 184.8 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: