Context Navigation

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

Revision 2117, 176.8 KB checked in by mattausch, 17 years ago (diff)
implemented bit pvs (warnin: only worjs for preprocessing)

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

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

Download in other formats: