Context Navigation

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

Revision 2096, 177.0 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: