Context Navigation

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

Revision 2048, 178.5 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: