Context Navigation

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

Revision 2575, 185.5 KB checked in by bittner, 17 years ago (diff)
big merge: preparation for havran ray caster, check if everything works

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

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

Download in other formats: