Context Navigation

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

Revision 2017, 175.2 KB checked in by mattausch, 17 years ago (diff)
changed to static cast

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

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

Download in other formats: