Context Navigation

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

Revision 2064, 177.5 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: