Context Navigation

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

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

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

Download in other formats: