Context Navigation

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

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

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

Download in other formats: