Context Navigation

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

Revision 2542, 181.6 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: