Context Navigation

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

Revision 2051, 178.6 KB checked in by bittner, 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	mFilterWidth,
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
3508	// radius = 0.5fglobalRadius + 0.5flocalRadius;
3509	radius = Min(globalRadius, localRadius);
3510
3511	if (localRadius > globalRadius)
3512	stats.mLocalFilterCount++;
3513	else
3514	stats.mGlobalFilterCount++;
3515	#endif
3516
3517	stats.mAvgFilterRadius += radius;
3518
3519	// cout<<"box = "<<box<<endl;
3520	// cout<<"distance = "<<distance<<endl;
3521	// cout<<"radiues = "<<radius<<endl;
3522
3523	box.Enlarge(Vector3(radius));
3524
3525	if (filteredBoxes)
3526	filteredBoxes->push_back(box);
3527
3528	objects.clear();
3529	// $$ warning collect objects takes only unmailed ones!
3530	if (mUseKdPvsAfterFiltering) {
3531	GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
3532	} else
3533	CollectObjects(box, objects);
3534
3535	// cout<<"collected objects="<<objects.size()<<endl;
3536	ObjectContainer::const_iterator noi = objects.begin();
3537	for (; noi != objects.end(); ++ noi) {
3538	Intersectable o = noi;
3539	// $$ JB warning: pdfs are not correct at this point!
3540	pvs.AddSampleDirty(o, Limits::Small);
3541	}
3542	}
3543	stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
3544	}
3545
3546	Debug<<" nPvs size = "<<pvs.GetSize()<<endl;
3547
3548	if (!mUseKdPvs)
3549	{
3550	// copy the base pvs to the new pvs
3551	pit = basePvs.GetIterator();
3552	while (pit.HasMoreEntries())
3553	{
3554	ObjectPvsEntry entry = pit.Next();
3555	pvs.AddSampleDirty(entry.mObject, entry.mData.mSumPdf);
3556	}
3557	}
3558
3559	pvs.SimpleSort();
3560	viewCell->SetFilteredPvsSize(pvs.GetSize());
3561
3562	Intersectable::NewMail();
3563	return stats;
3564	}
3565
3566
3567
3568	void ViewCellsManager::ExportColor(Exporter *exporter,
3569	ViewCell *vc,
3570	bool colorCode) const
3571	{
3572	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3573
3574	float importance = 0;
3575	static Material m;
3576	//cout << "color code: " << colorCode << endl;
3577	switch (mColorCode)
3578	{
3579	case 0: // Random
3580	{
3581	if (vcValid)
3582	{
3583	m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
3584	m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
3585	m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
3586	}
3587	else
3588	{
3589	m.mDiffuseColor.r = 0.0f;
3590	m.mDiffuseColor.g = 1.0f;
3591	m.mDiffuseColor.b = 0.0f;
3592	}
3593
3594	exporter->SetForcedMaterial(m);
3595	return;
3596	}
3597
3598	case 1: // pvs
3599	{
3600	if (mCurrentViewCellsStats.maxPvs)
3601	{
3602	importance = (float)mViewCellsTree->GetPvsCost(vc) /
3603	(float)mCurrentViewCellsStats.maxPvs;
3604	}
3605	}
3606	break;
3607	case 2: // merges
3608	{
3609	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
3610	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3611	}
3612	break;
3613	#if 0
3614	case 3: // merge tree differene
3615	{
3616	importance = (float)GetMaxTreeDiff(vc) /
3617	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
3618
3619	}
3620	break;
3621	#endif
3622	default:
3623	break;
3624	}
3625
3626	// special color code for invalid view cells
3627	m.mDiffuseColor.r = importance;
3628	m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
3629	m.mDiffuseColor.g = 1.0f - importance;
3630
3631	//Debug << "importance: " << importance << endl;
3632	exporter->SetForcedMaterial(m);
3633	}
3634
3635
3636	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3637	vector<MergeCandidate> &candidates)
3638	{
3639	// implemented in subclasses
3640	}
3641
3642
3643	void ViewCellsManager::UpdatePvsForEvaluation()
3644	{
3645	ObjectPvs objPvs;
3646	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
3647	}
3648
3649
3650	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
3651	{
3652	// terminate traversal
3653	if (root->IsLeaf())
3654	{
3655	//cout << "updating leaf" << endl;
3656	// we assume that pvs is explicitly stored in leaves
3657	pvs = root->GetPvs();
3658	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
3659	return;
3660	}
3661
3662	////////////////
3663	//-- interior node => propagate pvs up the tree
3664
3665	ViewCellInterior interior = static_cast<ViewCellInterior >(root);
3666
3667	// reset interior pvs
3668	interior->GetPvs().Clear();
3669	// reset recursive pvs
3670	pvs.Clear();
3671
3672	// pvss of child nodes
3673	vector<ObjectPvs> pvsList;
3674	pvsList.resize((int)interior->mChildren.size());
3675
3676	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3677
3678	int i = 0;
3679
3680	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3681	{
3682	//////////////////
3683	//-- recursivly compute child pvss
3684	UpdatePvsForEvaluation(vit, pvsList[i]/objPvs*/);
3685	}
3686
3687	#if 1
3688	Intersectable::NewMail();
3689
3690	//-- faster way of computing pvs:
3691	//-- construct merged pvs by adding
3692	//-- and only those of the next pvs which were not mailed.
3693	//-- note: sumpdf is not correct!!
3694
3695	vector<ObjectPvs>::iterator oit = pvsList.begin();
3696
3697	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3698	{
3699	ObjectPvsIterator pit = (*oit).GetIterator();
3700
3701	// first mark all object from this pvs
3702	while (pit.HasMoreEntries())
3703	{
3704	ObjectPvsEntry entry = pit.Next();
3705
3706	Intersectable *intersect = entry.mObject;
3707
3708	if (!intersect->Mailed())
3709	{
3710	pvs.AddSample(intersect, entry.mData.mSumPdf);
3711	intersect->Mail();
3712	}
3713	}
3714	}
3715
3716	// store pvs in this node
3717	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3718	{
3719	interior->SetPvs(pvs);
3720	}
3721
3722	// set new pvs size
3723	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3724
3725	#else
3726	// really merge cells: slow put sumPdf is correct
3727	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3728	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3729	#endif
3730	}
3731
3732
3733
3734	/*******************************************************************/
3735	/* BspViewCellsManager implementation */
3736	/*******************************************************************/
3737
3738
3739	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
3740	ViewCellsManager(vcTree), mBspTree(bspTree)
3741	{
3742	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3743
3744	mBspTree->SetViewCellsManager(this);
3745	mBspTree->SetViewCellsTree(mViewCellsTree);
3746	}
3747
3748
3749	bool BspViewCellsManager::ViewCellsConstructed() const
3750	{
3751	return mBspTree->GetRoot() != NULL;
3752	}
3753
3754
3755	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
3756	{
3757	return new BspViewCell(mesh);
3758	}
3759
3760
3761	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3762	const VssRayContainer &rays)
3763	{
3764	// if view cells were already constructed, we can finish
3765	if (ViewCellsConstructed())
3766	return 0;
3767
3768	int sampleContributions = 0;
3769
3770	// construct view cells using the collected samples
3771	RayContainer constructionRays;
3772	VssRayContainer savedRays;
3773
3774	// choose a a number of rays based on the ratio of cast rays / requested rays
3775	const int limit = min(mInitialSamples, (int)rays.size());
3776	VssRayContainer::const_iterator it, it_end = rays.end();
3777
3778	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3779
3780	for (it = rays.begin(); it != it_end; ++ it)
3781	{
3782	if (Random(1.0f) < prop)
3783	constructionRays.push_back(new Ray((it)));
3784	else
3785	savedRays.push_back(*it);
3786	}
3787
3788	if (!mUsePredefinedViewCells)
3789	{
3790	// no view cells loaded
3791	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3792	// collect final view cells
3793	mBspTree->CollectViewCells(mViewCells);
3794	}
3795	else
3796	{
3797	// use predefined view cells geometry =>
3798	// contruct bsp hierarchy over them
3799	mBspTree->Construct(mViewCells);
3800	}
3801
3802	// destroy rays created only for construction
3803	CLEAR_CONTAINER(constructionRays);
3804
3805	Debug << mBspTree->GetStatistics() << endl;
3806	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3807
3808	// recast rest of the rays
3809	if (SAMPLE_AFTER_SUBDIVISION)
3810	ComputeSampleContributions(savedRays, true, false);
3811
3812	// real meshes are contructed at this stage
3813	if (0)
3814	{
3815	cout << "finalizing view cells ... ";
3816	FinalizeViewCells(true);
3817	cout << "finished" << endl;
3818	}
3819
3820	return sampleContributions;
3821	}
3822
3823
3824	void BspViewCellsManager::CollectViewCells()
3825	{
3826	if (!ViewCellsTreeConstructed())
3827	{ // view cells tree constructed
3828	mBspTree->CollectViewCells(mViewCells);
3829	}
3830	else
3831	{ // we can use the view cells tree hierarchy to get the right set
3832	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3833	}
3834	}
3835
3836
3837	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3838	{
3839	if (1)
3840	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3841	else
3842	// compute view cell area as subsititute for probability
3843	return GetArea(viewCell) / GetAccVcArea();
3844	}
3845
3846
3847
3848	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3849	const Vector3 &termination,
3850	ViewCellContainer &viewcells)
3851	{
3852	return mBspTree->CastLineSegment(origin, termination, viewcells);
3853	}
3854
3855
3856	bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
3857	const Vector3 &termination,
3858	ViewCell *viewCell)
3859	{
3860	return false;
3861	}
3862
3863
3864	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3865	{
3866	// save color code
3867	const int savedColorCode = mColorCode;
3868
3869	Exporter *exporter;
3870
3871	#if 0
3872	// export merged view cells
3873	mColorCode = 0; // use random colors
3874
3875	exporter = Exporter::GetExporter("merged_view_cells.wrl");
3876
3877	cout << "exporting view cells after merge ... ";
3878
3879	if (exporter)
3880	{
3881	if (mExportGeometry)
3882	{
3883	exporter->ExportGeometry(objects);
3884	}
3885
3886	exporter->SetFilled();
3887	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3888
3889	delete exporter;
3890	}
3891	cout << "finished" << endl;
3892	#endif
3893
3894	// export merged view cells using pvs color coding
3895	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3896	cout << "exporting view cells after merge (pvs size) ... ";
3897
3898	if (exporter)
3899	{
3900	if (mExportGeometry)
3901	{
3902	exporter->ExportGeometry(objects);
3903	}
3904
3905	exporter->SetFilled();
3906	mColorCode = 1;
3907
3908	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3909
3910	delete exporter;
3911	}
3912	cout << "finished" << endl;
3913
3914	mColorCode = savedColorCode;
3915	}
3916
3917
3918	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3919	const VssRayContainer &rays)
3920	{
3921	if (!ViewCellsConstructed())
3922	{
3923	Debug << "view cells not constructed" << endl;
3924	return 0;
3925	}
3926
3927	// view cells already finished before post processing step,
3928	// i.e., because they were loaded from disc
3929	if (mViewCellsFinished)
3930	{
3931	FinalizeViewCells(true);
3932	EvaluateViewCellsStats();
3933
3934	return 0;
3935	}
3936
3937	//////////////////
3938	//-- merge leaves of the view cell hierarchy
3939
3940	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3941	long startTime = GetTime();
3942
3943	VssRayContainer postProcessRays;
3944	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3945
3946	if (mMergeViewCells)
3947	{
3948	cout << "constructing visibility based merge tree" << endl;
3949	mViewCellsTree->ConstructMergeTree(rays, objects);
3950	}
3951	else
3952	{
3953	cout << "constructing spatial merge tree" << endl;
3954	ViewCell *root;
3955	// the spatial merge tree is difficult to build for
3956	// this type of construction, as view cells cover several
3957	// leaves => create dummy tree which is only 2 levels deep
3958	if (mUsePredefinedViewCells)
3959	{
3960	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3961	}
3962	else
3963	{
3964	// create spatial merge hierarchy
3965	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3966	}
3967
3968	mViewCellsTree->SetRoot(root);
3969
3970	// recompute pvs in the whole hierarchy
3971	ObjectPvs pvs;
3972	UpdatePvsForEvaluation(root, pvs);
3973	}
3974
3975	cout << "finished" << endl;
3976	cout << "merged view cells in "
3977	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3978
3979	Debug << "Postprocessing: Merged view cells in "
3980	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3981
3982
3983	////////////////////////
3984	//-- visualization and statistics after merge
3985
3986	if (1)
3987	{
3988	char mstats[100];
3989	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3990	mViewCellsTree->ExportStats(mstats);
3991	}
3992
3993	// recompute view cells and stats
3994	ResetViewCells();
3995	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3996
3997	// visualization of the view cells
3998	if (1) ExportMergedViewCells(objects);
3999
4000	// compute final meshes and volume / area
4001	if (1) FinalizeViewCells(true);
4002
4003	return 0;
4004	}
4005
4006
4007	BspViewCellsManager::~BspViewCellsManager()
4008	{
4009	}
4010
4011
4012	int BspViewCellsManager::GetType() const
4013	{
4014	return BSP;
4015	}
4016
4017
4018	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
4019	const VssRayContainer &sampleRays)
4020	{
4021	if (!ViewCellsConstructed())
4022	return;
4023
4024	const int savedColorCode = mColorCode;
4025
4026	if (1) // export final view cells
4027	{
4028	mColorCode = 1; // hack color code
4029	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
4030
4031	cout << "exporting view cells after merge (pvs size) ... ";
4032
4033	if (exporter)
4034	{
4035	if (mExportGeometry)
4036	{
4037	exporter->ExportGeometry(objects);
4038	}
4039
4040	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4041	delete exporter;
4042	}
4043	cout << "finished" << endl;
4044	}
4045
4046	// reset color code
4047	mColorCode = savedColorCode;
4048
4049
4050	//////////////////
4051	//-- visualization of the BSP splits
4052
4053	bool exportSplits = false;
4054	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
4055
4056	if (exportSplits)
4057	{
4058	cout << "exporting splits ... ";
4059	ExportSplits(objects);
4060	cout << "finished" << endl;
4061	}
4062
4063	int leafOut;
4064	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
4065	const int raysOut = 100;
4066	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
4067	}
4068
4069
4070	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
4071	{
4072	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
4073
4074	if (exporter)
4075	{
4076	//exporter->SetFilled();
4077	if (mExportGeometry)
4078	{
4079	exporter->ExportGeometry(objects);
4080	}
4081
4082	Material m;
4083	m.mDiffuseColor = RgbColor(1, 0, 0);
4084	exporter->SetForcedMaterial(m);
4085	exporter->SetWireframe();
4086
4087	exporter->ExportBspSplits(*mBspTree, true);
4088
4089	// NOTE: take forced material, else big scenes cannot be viewed
4090	m.mDiffuseColor = RgbColor(0, 1, 0);
4091	exporter->SetForcedMaterial(m);
4092	//exporter->ResetForcedMaterial();
4093
4094	delete exporter;
4095	}
4096	}
4097
4098
4099	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4100	const int maxViewCells,
4101	const bool sortViewCells,
4102	const bool exportPvs,
4103	const bool exportRays,
4104	const int maxRays,
4105	const string prefix,
4106	VssRayContainer *visRays)
4107	{
4108	if (sortViewCells)
4109	{ // sort view cells to visualize the largest view cells
4110	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
4111	}
4112
4113	//////////
4114	//-- some view cells for output
4115
4116	ViewCell::NewMail();
4117	const int limit = min(maxViewCells, (int)mViewCells.size());
4118
4119	for (int i = 0; i < limit; ++ i)
4120	{
4121	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
4122	ViewCell *vc = mViewCells[idx];
4123
4124	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
4125	continue;
4126
4127	vc->Mail();
4128
4129	ObjectPvs pvs;
4130	mViewCellsTree->GetPvs(vc, pvs);
4131
4132	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
4133	Exporter *exporter = Exporter::GetExporter(s);
4134
4135	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetPvsCost(vc) << endl;
4136
4137	if (exportRays)
4138	{
4139	////////////
4140	//-- export rays piercing this view cell
4141
4142	// use rays stored with the view cells
4143	VssRayContainer vcRays, vcRays2, vcRays3;
4144	VssRayContainer collectRays;
4145
4146	// collect initial view cells
4147	ViewCellContainer leaves;
4148	mViewCellsTree->CollectLeaves(vc, leaves);
4149
4150	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4151	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4152	{
4153	// prepare some rays for output
4154	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
4155	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
4156	{
4157	collectRays.push_back(*rit);
4158	}
4159	}
4160
4161	const int raysOut = min((int)collectRays.size(), maxRays);
4162
4163	// prepare some rays for output
4164	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4165	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4166	{
4167	const float p = RandomValue(0.0f, (float)collectRays.size());
4168	if (p < raysOut)
4169	{
4170	if ((*rit)->mFlags & VssRay::BorderSample)
4171	{
4172	vcRays.push_back(*rit);
4173	}
4174	else if ((*rit)->mFlags & VssRay::ReverseSample)
4175	{
4176	vcRays2.push_back(*rit);
4177	}
4178	else
4179	{
4180	vcRays3.push_back(*rit);
4181	}
4182	}
4183	}
4184
4185	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
4186	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
4187	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
4188	}
4189
4190	////////////////
4191	//-- export view cell geometry
4192
4193	exporter->SetWireframe();
4194
4195	Material m;//= RandomMaterial();
4196	m.mDiffuseColor = RgbColor(0, 1, 0);
4197	exporter->SetForcedMaterial(m);
4198
4199	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4200	exporter->SetFilled();
4201
4202	if (exportPvs)
4203	{
4204	Intersectable::NewMail();
4205	ObjectPvsIterator pit = pvs.GetIterator();
4206
4207	while (pit.HasMoreEntries())
4208	{
4209	ObjectPvsEntry entry = pit.Next();
4210
4211	// output PVS of view cell
4212	Intersectable *intersect = entry.mObject;
4213
4214	if (!intersect->Mailed())
4215	{
4216	intersect->Mail();
4217
4218	m = RandomMaterial();
4219	exporter->SetForcedMaterial(m);
4220	exporter->ExportIntersectable(intersect);
4221	}
4222	}
4223	cout << endl;
4224	}
4225
4226	DEL_PTR(exporter);
4227	cout << "finished" << endl;
4228	}
4229	}
4230
4231
4232	void BspViewCellsManager::TestSubdivision()
4233	{
4234	ViewCellContainer leaves;
4235	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4236
4237	ViewCellContainer::const_iterator it, it_end = leaves.end();
4238
4239	const float vol = mViewSpaceBox.GetVolume();
4240	float subdivVol = 0;
4241	float newVol = 0;
4242
4243	for (it = leaves.begin(); it != it_end; ++ it)
4244	{
4245	BspNodeGeometry geom;
4246	mBspTree->ConstructGeometry(*it, geom);
4247
4248	const float lVol = geom.GetVolume();
4249	newVol += lVol;
4250	subdivVol += (*it)->GetVolume();
4251
4252	const float thres = 0.9f;
4253	if ((lVol < ((it)->GetVolume() thres)) \|\|
4254	(lVol * thres > ((*it)->GetVolume())))
4255	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4256	}
4257
4258	Debug << "exact volume: " << vol << endl;
4259	Debug << "subdivision volume: " << subdivVol << endl;
4260	Debug << "new volume: " << newVol << endl;
4261	}
4262
4263
4264	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4265	ViewCell *vc,
4266	const AxisAlignedBox3 *sceneBox,
4267	const AxisAlignedPlane *clipPlane
4268	) const
4269	{
4270	if (clipPlane)
4271	{
4272	const Plane3 plane = clipPlane->GetPlane();
4273
4274	ViewCellContainer leaves;
4275	mViewCellsTree->CollectLeaves(vc, leaves);
4276	ViewCellContainer::const_iterator it, it_end = leaves.end();
4277
4278	for (it = leaves.begin(); it != it_end; ++ it)
4279	{
4280	BspNodeGeometry geom;
4281	BspNodeGeometry front;
4282	BspNodeGeometry back;
4283
4284	mBspTree->ConstructGeometry(*it, geom);
4285
4286	const float eps = 0.0001f;
4287	const int cf = geom.Side(plane, eps);
4288
4289	if (cf == -1)
4290	{
4291	exporter->ExportPolygons(geom.GetPolys());
4292	}
4293	else if (cf == 0)
4294	{
4295	geom.SplitGeometry(front,
4296	back,
4297	plane,
4298	mViewSpaceBox,
4299	eps);
4300
4301	if (back.Valid())
4302	{
4303	exporter->ExportPolygons(back.GetPolys());
4304	}
4305	}
4306	}
4307	}
4308	else
4309	{
4310	// export mesh if available
4311	// TODO: some bug here?
4312	if (1 && vc->GetMesh())
4313	{
4314	exporter->ExportMesh(vc->GetMesh());
4315	}
4316	else
4317	{
4318	BspNodeGeometry geom;
4319	mBspTree->ConstructGeometry(vc, geom);
4320	exporter->ExportPolygons(geom.GetPolys());
4321	}
4322	}
4323	}
4324
4325
4326	void BspViewCellsManager::CreateMesh(ViewCell *vc)
4327	{
4328	// note: should previous mesh be deleted (via mesh manager?)
4329	BspNodeGeometry geom;
4330	mBspTree->ConstructGeometry(vc, geom);
4331
4332	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4333
4334	IncludeNodeGeomInMesh(geom, *mesh);
4335	mesh->ComputeBoundingBox();
4336
4337	vc->SetMesh(mesh);
4338	}
4339
4340
4341	void BspViewCellsManager::Finalize(ViewCell *viewCell,
4342	const bool createMesh)
4343	{
4344	float area = 0;
4345	float volume = 0;
4346
4347	ViewCellContainer leaves;
4348	mViewCellsTree->CollectLeaves(viewCell, leaves);
4349
4350	ViewCellContainer::const_iterator it, it_end = leaves.end();
4351
4352	for (it = leaves.begin(); it != it_end; ++ it)
4353	{
4354	BspNodeGeometry geom;
4355
4356	mBspTree->ConstructGeometry(*it, geom);
4357
4358	const float lVol = geom.GetVolume();
4359	const float lArea = geom.GetArea();
4360
4361	area += lArea;
4362	volume += lVol;
4363
4364	CreateMesh(*it);
4365	}
4366
4367	viewCell->SetVolume(volume);
4368	viewCell->SetArea(area);
4369	}
4370
4371
4372	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4373	{
4374	if (!ViewCellsConstructed())
4375	{
4376	return NULL;
4377	}
4378	if (!mViewSpaceBox.IsInside(point))
4379	{
4380	return NULL;
4381	}
4382	return mBspTree->GetViewCell(point);
4383	}
4384
4385
4386	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4387	vector<MergeCandidate> &candidates)
4388	{
4389	cout << "collecting merge candidates ... " << endl;
4390
4391	if (mUseRaysForMerge)
4392	{
4393	mBspTree->CollectMergeCandidates(rays, candidates);
4394	}
4395	else
4396	{
4397	vector<BspLeaf *> leaves;
4398	mBspTree->CollectLeaves(leaves);
4399	mBspTree->CollectMergeCandidates(leaves, candidates);
4400	}
4401
4402	cout << "fininshed collecting candidates" << endl;
4403	}
4404
4405
4406
4407	bool BspViewCellsManager::ExportViewCells(const string filename,
4408	const bool exportPvs,
4409	const ObjectContainer &objects)
4410	{
4411	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
4412	{
4413	return false;
4414	}
4415
4416	cout << "exporting view cells to xml ... ";
4417
4418	OUT_STREAM stream(filename.c_str());
4419
4420	// for output we need unique ids for each view cell
4421	CreateUniqueViewCellIds();
4422
4423	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
4424	stream << "<VisibilitySolution>" << endl;
4425
4426	if (exportPvs)
4427	{
4428	//////////
4429	//-- export bounding boxes: they are used to identify the objects from the pvs and
4430	//-- assign them to the entities in the rendering engine
4431
4432	stream << "<BoundingBoxes>" << endl;
4433	ObjectContainer::const_iterator oit, oit_end = objects.end();
4434
4435	for (oit = objects.begin(); oit != oit_end; ++ oit)
4436	{
4437	const AxisAlignedBox3 box = (*oit)->GetBox();
4438
4439	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
4440	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
4441	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
4442	}
4443
4444	stream << "</BoundingBoxes>" << endl;
4445	}
4446
4447	///////////
4448	//-- export the view cells and the pvs
4449
4450	const int numViewCells = mCurrentViewCellsStats.viewCells;
4451	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
4452
4453	mViewCellsTree->Export(stream, exportPvs);
4454
4455	stream << "</ViewCells>" << endl;
4456
4457	/////////////
4458	//-- export the view space hierarchy
4459	stream << "<ViewSpaceHierarchy type=\"bsp\""
4460	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
4461	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
4462
4463	mBspTree->Export(stream);
4464
4465	// end tags
4466	stream << "</ViewSpaceHierarchy>" << endl;
4467	stream << "</VisibilitySolution>" << endl;
4468
4469	stream.close();
4470	cout << "finished" << endl;
4471
4472	return true;
4473	}
4474
4475
4476	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
4477	{
4478	ViewCellInterior *vcRoot = new ViewCellInterior();
4479
4480	// evaluate merge cost for priority traversal
4481	const float mergeCost = -(float)root->mTimeStamp;
4482	vcRoot->SetMergeCost(mergeCost);
4483
4484	float volume = 0;
4485	vector<BspLeaf *> leaves;
4486	mBspTree->CollectLeaves(leaves);
4487	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
4488	ViewCell::NewMail();
4489
4490	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4491	{
4492	BspLeaf leaf = lit;
4493	ViewCell *vc = leaf->GetViewCell();
4494
4495	if (!vc->Mailed())
4496	{
4497	vc->Mail();
4498	vc->SetMergeCost(0.0f);
4499	vcRoot->SetupChildLink(vc);
4500
4501	volume += vc->GetVolume();
4502	volume += vc->GetVolume();
4503	vcRoot->SetVolume(volume);
4504	}
4505	}
4506
4507	return vcRoot;
4508	}
4509
4510
4511	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4512	{
4513	// terminate recursion
4514	if (root->IsLeaf())
4515	{
4516	BspLeaf leaf = static_cast<BspLeaf >(root);
4517	leaf->GetViewCell()->SetMergeCost(0.0f);
4518	return leaf->GetViewCell();
4519	}
4520
4521	BspInterior interior = static_cast<BspInterior >(root);
4522	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4523
4524	// evaluate merge cost for priority traversal
4525	const float mergeCost = -(float)root->mTimeStamp;
4526	viewCellInterior->SetMergeCost(mergeCost);
4527
4528	float volume = 0;
4529
4530	BspNode *front = interior->GetFront();
4531	BspNode *back = interior->GetBack();
4532
4533
4534	////////////
4535	//-- recursivly compute child hierarchies
4536
4537	ViewCell *backVc = ConstructSpatialMergeTree(back);
4538	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4539
4540	viewCellInterior->SetupChildLink(backVc);
4541	viewCellInterior->SetupChildLink(frontVc);
4542
4543	volume += backVc->GetVolume();
4544	volume += frontVc->GetVolume();
4545
4546	viewCellInterior->SetVolume(volume);
4547
4548	return viewCellInterior;
4549	}
4550
4551
4552	/************************************************************************/
4553	/* KdViewCellsManager implementation */
4554	/************************************************************************/
4555
4556
4557
4558	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
4559	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
4560	{
4561	}
4562
4563
4564	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
4565	{
4566	// compute view cell area / volume as subsititute for probability
4567	if (0)
4568	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
4569	else
4570	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
4571	}
4572
4573
4574
4575
4576	void KdViewCellsManager::CollectViewCells()
4577	{
4578	//mKdTree->CollectViewCells(mViewCells); TODO
4579	}
4580
4581
4582	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4583	const VssRayContainer &rays)
4584	{
4585	// if view cells already constructed
4586	if (ViewCellsConstructed())
4587	return 0;
4588
4589	mKdTree->Construct();
4590
4591	mTotalAreaValid = false;
4592	// create the view cells
4593	mKdTree->CreateAndCollectViewCells(mViewCells);
4594	// cast rays
4595	ComputeSampleContributions(rays, true, false);
4596
4597	EvaluateViewCellsStats();
4598	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4599
4600	return 0;
4601	}
4602
4603
4604	bool KdViewCellsManager::ViewCellsConstructed() const
4605	{
4606	return mKdTree->GetRoot() != NULL;
4607	}
4608
4609
4610	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
4611	const VssRayContainer &rays)
4612	{
4613	return 0;
4614	}
4615
4616
4617	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4618	const int maxViewCells,
4619	const bool sortViewCells,
4620	const bool exportPvs,
4621	const bool exportRays,
4622	const int maxRays,
4623	const string prefix,
4624	VssRayContainer *visRays)
4625	{
4626	// TODO
4627	}
4628
4629
4630	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
4631	const VssRayContainer &sampleRays)
4632	{
4633	if (!ViewCellsConstructed())
4634	return;
4635
4636	// using view cells instead of the kd PVS of objects
4637	const bool useViewCells = true;
4638	bool exportRays = false;
4639
4640	int limit = min(mVisualizationSamples, (int)sampleRays.size());
4641	const int pvsOut = min((int)objects.size(), 10);
4642	VssRayContainer *rays = new VssRayContainer[pvsOut];
4643
4644	if (useViewCells)
4645	{
4646	const int leafOut = 10;
4647
4648	ViewCell::NewMail();
4649
4650	//-- some rays for output
4651	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4652	Debug << "visualization using " << raysOut << " samples" << endl;
4653
4654	//-- some random view cells and rays for output
4655	vector<KdLeaf *> kdLeaves;
4656
4657	for (int i = 0; i < leafOut; ++ i)
4658	kdLeaves.push_back(static_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4659
4660	for (int i = 0; i < kdLeaves.size(); ++ i)
4661	{
4662	KdLeaf *leaf = kdLeaves[i];
4663	RayContainer vcRays;
4664
4665	cout << "creating output for view cell " << i << " ... ";
4666	#if 0
4667	// check whether we can add the current ray to the output rays
4668	for (int k = 0; k < raysOut; ++ k)
4669	{
4670	Ray *ray = sampleRays[k];
4671
4672	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4673	{
4674	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4675
4676	if (leaf->GetViewCell() == leaf2->GetViewCell())
4677	{
4678	vcRays.push_back(ray);
4679	}
4680	}
4681	}
4682	#endif
4683	Intersectable::NewMail();
4684
4685	ViewCell *vc = leaf->mViewCell;
4686	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4687
4688	Exporter *exporter = Exporter::GetExporter(str);
4689	exporter->SetFilled();
4690
4691	exporter->SetWireframe();
4692	//exporter->SetFilled();
4693
4694	Material m;//= RandomMaterial();
4695	m.mDiffuseColor = RgbColor(1, 1, 0);
4696	exporter->SetForcedMaterial(m);
4697
4698	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4699	exporter->ExportBox(box);
4700
4701	// export rays piercing this view cell
4702	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4703
4704	m.mDiffuseColor = RgbColor(1, 0, 0);
4705	exporter->SetForcedMaterial(m);
4706
4707	// exporter->SetWireframe();
4708	exporter->SetFilled();
4709
4710	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4711
4712	while (pit.HasMoreEntries())
4713	{
4714	ObjectPvsEntry entry = pit.Next();
4715
4716	//-- output PVS of view cell
4717	Intersectable *intersect = entry.mObject;
4718	if (!intersect->Mailed())
4719	{
4720	exporter->ExportIntersectable(intersect);
4721	intersect->Mail();
4722	}
4723	}
4724
4725	DEL_PTR(exporter);
4726	cout << "finished" << endl;
4727	}
4728
4729	DEL_PTR(rays);
4730	}
4731	else // using kd PVS of objects
4732	{
4733	for (int i = 0; i < limit; ++ i)
4734	{
4735	VssRay *ray = sampleRays[i];
4736
4737	// check whether we can add this to the rays
4738	for (int j = 0; j < pvsOut; j++)
4739	{
4740	if (objects[j] == ray->mTerminationObject)
4741	{
4742	rays[j].push_back(ray);
4743	}
4744	}
4745	}
4746
4747	if (exportRays)
4748	{
4749	Exporter *exporter = NULL;
4750	exporter = Exporter::GetExporter("sample-rays.x3d");
4751	exporter->SetWireframe();
4752	exporter->ExportKdTree(*mKdTree);
4753
4754	for (int i = 0; i < pvsOut; i++)
4755	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4756
4757	exporter->SetFilled();
4758	delete exporter;
4759	}
4760
4761	for (int k=0; k < pvsOut; k++)
4762	{
4763	Intersectable *object = objects[k];
4764	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4765
4766	Exporter *exporter = Exporter::GetExporter(str);
4767	exporter->SetWireframe();
4768
4769	// matt: we don't have no kd pvs
4770	#if 0
4771	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4772	Intersectable::NewMail();
4773
4774	// avoid adding the object to the list
4775	object->Mail();
4776	ObjectContainer visibleObjects;
4777
4778	for (; kit != object->mKdPvs.mEntries.end(); i++)
4779	{
4780	KdNode node = (kit).first;
4781	exporter->ExportBox(mKdTree->GetBox(node));
4782
4783	mKdTree->CollectObjects(node, visibleObjects);
4784	}
4785
4786	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4787	exporter->SetFilled();
4788
4789	for (int j = 0; j < visibleObjects.size(); j++)
4790	exporter->ExportIntersectable(visibleObjects[j]);
4791
4792	Material m;
4793	m.mDiffuseColor = RgbColor(1, 0, 0);
4794	exporter->SetForcedMaterial(m);
4795	exporter->ExportIntersectable(object);
4796	#endif
4797	delete exporter;
4798	}
4799	}
4800	}
4801
4802
4803	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4804	{
4805	return new KdViewCell(mesh);
4806	}
4807
4808
4809	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4810	ViewCell *vc,
4811	const AxisAlignedBox3 *sceneBox,
4812	const AxisAlignedPlane *clipPlane
4813	) const
4814	{
4815	ViewCellContainer leaves;
4816	mViewCellsTree->CollectLeaves(vc, leaves);
4817	ViewCellContainer::const_iterator it, it_end = leaves.end();
4818
4819	for (it = leaves.begin(); it != it_end; ++ it)
4820	{
4821	KdViewCell kdVc = static_cast<KdViewCell >(*it);
4822	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4823	}
4824	}
4825
4826
4827	int KdViewCellsManager::GetType() const
4828	{
4829	return ViewCellsManager::KD;
4830	}
4831
4832
4833
4834	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4835	{
4836	KdNode *node = leaf;
4837
4838	while (node->mParent && node->mDepth > mKdPvsDepth)
4839	node = node->mParent;
4840
4841	return node;
4842	}
4843
4844	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4845	const Vector3 &termination,
4846	ViewCellContainer &viewcells)
4847	{
4848	return mKdTree->CastLineSegment(origin, termination, viewcells);
4849	}
4850
4851
4852	bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
4853	const Vector3 &termination,
4854	ViewCell *viewCell)
4855	{
4856	return false;
4857	}
4858
4859
4860	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4861	{
4862	// TODO
4863	}
4864
4865
4866
4867	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4868	vector<MergeCandidate> &candidates)
4869	{
4870	// TODO
4871	}
4872
4873
4874
4875	/**************************************************************************/
4876	/* VspBspViewCellsManager implementation */
4877	/**************************************************************************/
4878
4879
4880	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4881	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4882	{
4883	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4884	mVspBspTree->SetViewCellsManager(this);
4885	mVspBspTree->mViewCellsTree = mViewCellsTree;
4886	}
4887
4888
4889	VspBspViewCellsManager::~VspBspViewCellsManager()
4890	{
4891	}
4892
4893
4894	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4895	{
4896	if (0 && mVspBspTree->mUseAreaForPvs)
4897	return GetArea(viewCell) / GetAccVcArea();
4898	else
4899	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4900	}
4901
4902
4903	void VspBspViewCellsManager::CollectViewCells()
4904	{
4905	// view cells tree constructed?
4906	if (!ViewCellsTreeConstructed())
4907	{
4908	mVspBspTree->CollectViewCells(mViewCells, false);
4909	}
4910	else
4911	{
4912	// we can use the view cells tree hierarchy to get the right set
4913	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4914	}
4915	}
4916
4917
4918	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4919	vector<MergeCandidate> &candidates)
4920	{
4921	cout << "collecting merge candidates ... " << endl;
4922
4923	if (mUseRaysForMerge)
4924	{
4925	mVspBspTree->CollectMergeCandidates(rays, candidates);
4926	}
4927	else
4928	{
4929	vector<BspLeaf *> leaves;
4930	mVspBspTree->CollectLeaves(leaves);
4931
4932	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4933	}
4934
4935	cout << "fininshed collecting candidates" << endl;
4936	}
4937
4938
4939	bool VspBspViewCellsManager::ViewCellsConstructed() const
4940	{
4941	return mVspBspTree->GetRoot() != NULL;
4942	}
4943
4944
4945	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4946	{
4947	return new BspViewCell(mesh);
4948	}
4949
4950
4951	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4952	const VssRayContainer &rays)
4953	{
4954	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4955
4956	// if view cells were already constructed
4957	if (ViewCellsConstructed())
4958	{
4959	return 0;
4960	}
4961
4962	int sampleContributions = 0;
4963	VssRayContainer sampleRays;
4964
4965	const int limit = min(mInitialSamples, (int)rays.size());
4966
4967	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4968	<< ", actual rays: " << (int)rays.size() << endl;
4969
4970	VssRayContainer savedRays;
4971
4972	if (SAMPLE_AFTER_SUBDIVISION)
4973	{
4974	VssRayContainer constructionRays;
4975
4976	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4977
4978	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4979	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4980
4981	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4982	}
4983	else
4984	{
4985	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4986	mVspBspTree->Construct(rays, &mViewSpaceBox);
4987	}
4988
4989	// collapse invalid regions
4990	cout << "collapsing invalid tree regions ... ";
4991	long startTime = GetTime();
4992
4993	const int collapsedLeaves = mVspBspTree->CollapseTree();
4994	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4995	<< " seconds" << endl;
4996
4997	cout << "finished" << endl;
4998
4999	/////////////////
5000	//-- stats after construction
5001
5002	Debug << mVspBspTree->GetStatistics() << endl;
5003
5004	ResetViewCells();
5005	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5006
5007
5008	//////////////////////
5009	//-- recast the rest of the rays
5010
5011	startTime = GetTime();
5012
5013	cout << "Computing remaining ray contributions ... ";
5014
5015	if (SAMPLE_AFTER_SUBDIVISION)
5016	ComputeSampleContributions(savedRays, true, false);
5017
5018	cout << "finished" << endl;
5019
5020	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5021	<< " secs" << endl;
5022
5023	cout << "construction finished" << endl;
5024
5025	if (0)
5026	{ ////////
5027	//-- real meshes are contructed at this stage
5028
5029	cout << "finalizing view cells ... ";
5030	FinalizeViewCells(true);
5031	cout << "finished" << endl;
5032	}
5033
5034	return sampleContributions;
5035	}
5036
5037
5038	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
5039	const ObjectContainer &objects)
5040	{
5041	int vcSize = 0;
5042	int pvsSize = 0;
5043
5044	//-- merge view cells
5045	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
5046	long startTime = GetTime();
5047
5048
5049	if (mMergeViewCells)
5050	{
5051	// TODO: should be done BEFORE the ray casting
5052	// compute tree by merging the nodes based on cost heuristics
5053	mViewCellsTree->ConstructMergeTree(rays, objects);
5054	}
5055	else
5056	{
5057	// compute tree by merging the nodes of the spatial hierarchy
5058	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
5059	mViewCellsTree->SetRoot(root);
5060
5061	// compute pvs
5062	ObjectPvs pvs;
5063	UpdatePvsForEvaluation(root, pvs);
5064	}
5065
5066	if (1)
5067	{
5068	char mstats[100];
5069	ObjectPvs pvs;
5070
5071	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
5072	mViewCellsTree->ExportStats(mstats);
5073	}
5074
5075	cout << "merged view cells in "
5076	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
5077
5078	Debug << "Postprocessing: Merged view cells in "
5079	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
5080
5081
5082	//////////////////
5083	//-- stats and visualizations
5084
5085	int savedColorCode = mColorCode;
5086
5087	// get currently active view cell set
5088	ResetViewCells();
5089	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
5090
5091	if (mShowVisualization) // export merged view cells
5092	{
5093	mColorCode = 0;
5094	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
5095
5096	cout << "exporting view cells after merge ... ";
5097
5098	if (exporter)
5099	{
5100	if (0)
5101	exporter->SetWireframe();
5102	else
5103	exporter->SetFilled();
5104
5105	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5106
5107	if (mExportGeometry)
5108	{
5109	Material m;
5110	m.mDiffuseColor = RgbColor(0, 1, 0);
5111	exporter->SetForcedMaterial(m);
5112	exporter->SetFilled();
5113
5114	exporter->ExportGeometry(objects);
5115	}
5116
5117	delete exporter;
5118	}
5119	cout << "finished" << endl;
5120	}
5121
5122	if (mShowVisualization)
5123	{
5124	// use pvs size for color coding
5125	mColorCode = 1;
5126	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
5127
5128	cout << "exporting view cells after merge (pvs size) ... ";
5129
5130	if (exporter)
5131	{
5132	exporter->SetFilled();
5133
5134	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5135
5136	if (mExportGeometry)
5137	{
5138	Material m;
5139	m.mDiffuseColor = RgbColor(0, 1, 0);
5140	exporter->SetForcedMaterial(m);
5141	exporter->SetFilled();
5142
5143	exporter->ExportGeometry(objects);
5144	}
5145
5146	delete exporter;
5147	}
5148	cout << "finished" << endl;
5149	}
5150
5151	mColorCode = savedColorCode;
5152	}
5153
5154
5155	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
5156	const ObjectContainer &objects)
5157	{
5158	mRenderer->RenderScene();
5159
5160	SimulationStatistics ss;
5161	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5162	Debug << "render time before refine\n\n" << ss << endl;
5163
5164	const long startTime = GetTime();
5165	cout << "Refining the merged view cells ... ";
5166
5167	// refining the merged view cells
5168	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
5169
5170	//-- stats and visualizations
5171	cout << "finished" << endl;
5172	cout << "refined " << refined << " view cells in "
5173	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
5174
5175	Debug << "Postprocessing: refined " << refined << " view cells in "
5176	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
5177	}
5178
5179
5180	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
5181	const VssRayContainer &rays)
5182	{
5183	if (!ViewCellsConstructed())
5184	{
5185	Debug << "postprocess error: no view cells constructed" << endl;
5186	return 0;
5187	}
5188
5189	// view cells already finished before post processing step
5190	// (i.e. because they were loaded)
5191	if (mViewCellsFinished)
5192	{
5193	FinalizeViewCells(true);
5194	EvaluateViewCellsStats();
5195
5196	return 0;
5197	}
5198
5199	// check if new view cells turned invalid
5200	int minPvs, maxPvs;
5201
5202	if (0)
5203	{
5204	minPvs = mMinPvsSize;
5205	maxPvs = mMaxPvsSize;
5206	}
5207	else
5208	{
5209	// problem matt: why did I start here from zero?
5210	minPvs = 0;
5211	maxPvs = mMaxPvsSize;
5212	}
5213
5214	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5215	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5216
5217	SetValidity(minPvs, maxPvs);
5218
5219	// update valid view space according to valid view cells
5220	if (0) mVspBspTree->ValidateTree();
5221
5222	// area has to be recomputed
5223	mTotalAreaValid = false;
5224	VssRayContainer postProcessRays;
5225	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5226
5227	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5228
5229	//////////
5230	//-- merge neighbouring view cells
5231	MergeViewCells(postProcessRays, objects);
5232
5233	// refines the merged view cells
5234	if (0) RefineViewCells(postProcessRays, objects);
5235
5236
5237	///////////
5238	//-- render simulation after merge + refine
5239
5240	cout << "\nview cells partition render time before compress" << endl << endl;;
5241	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5242	SimulationStatistics ss;
5243	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5244	cout << ss << endl;
5245
5246	if (0) CompressViewCells();
5247
5248	// collapse sibling leaves that share the same view cell
5249	if (0) mVspBspTree->CollapseTree();
5250
5251	// recompute view cell list and statistics
5252	ResetViewCells();
5253
5254	// compute final meshes and volume / area
5255	if (1) FinalizeViewCells(true);
5256
5257	return 0;
5258	}
5259
5260
5261	int VspBspViewCellsManager::GetType() const
5262	{
5263	return VSP_BSP;
5264	}
5265
5266
5267	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
5268	{
5269	// terminate recursion
5270	if (root->IsLeaf())
5271	{
5272	BspLeaf leaf = static_cast<BspLeaf >(root);
5273	leaf->GetViewCell()->SetMergeCost(0.0f);
5274	return leaf->GetViewCell();
5275	}
5276
5277
5278	BspInterior interior = static_cast<BspInterior >(root);
5279	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5280
5281	// evaluate merge cost for priority traversal
5282	float mergeCost = 1.0f / (float)root->mTimeStamp;
5283	viewCellInterior->SetMergeCost(mergeCost);
5284
5285	float volume = 0;
5286
5287	BspNode *front = interior->GetFront();
5288	BspNode *back = interior->GetBack();
5289
5290
5291	ObjectPvs frontPvs, backPvs;
5292
5293	//-- recursivly compute child hierarchies
5294	ViewCell *backVc = ConstructSpatialMergeTree(back);
5295	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5296
5297
5298	viewCellInterior->SetupChildLink(backVc);
5299	viewCellInterior->SetupChildLink(frontVc);
5300
5301	volume += backVc->GetVolume();
5302	volume += frontVc->GetVolume();
5303
5304	viewCellInterior->SetVolume(volume);
5305
5306	return viewCellInterior;
5307	}
5308
5309
5310	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5311	{
5312	if (!ViewCellsConstructed())
5313	return ViewCellsManager::GetViewPoint(viewPoint);
5314
5315	// TODO: set reasonable limit
5316	const int limit = 20;
5317
5318	for (int i = 0; i < limit; ++ i)
5319	{
5320	viewPoint = mViewSpaceBox.GetRandomPoint();
5321	if (mVspBspTree->ViewPointValid(viewPoint))
5322	{
5323	return true;
5324	}
5325	}
5326
5327	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5328	return false;
5329	}
5330
5331
5332	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5333	{
5334	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5335	// validy update in preprocessor for all managers)
5336	return ViewCellsManager::ViewPointValid(viewPoint);
5337
5338	// return mViewSpaceBox.IsInside(viewPoint) &&
5339	// mVspBspTree->ViewPointValid(viewPoint);
5340	}
5341
5342
5343	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
5344	const VssRayContainer &sampleRays)
5345	{
5346	if (!ViewCellsConstructed())
5347	return;
5348
5349	VssRayContainer visRays;
5350	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5351
5352	if (1)
5353	{
5354	//////////////////
5355	//-- export final view cell partition
5356
5357	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5358
5359	if (exporter)
5360	{
5361	cout << "exporting view cells after post process ... ";
5362	if (0)
5363	{ // export view space box
5364	exporter->SetWireframe();
5365	exporter->ExportBox(mViewSpaceBox);
5366	exporter->SetFilled();
5367	}
5368
5369	Material m;
5370	m.mDiffuseColor.r = 0.0f;
5371	m.mDiffuseColor.g = 0.5f;
5372	m.mDiffuseColor.b = 0.5f;
5373
5374	exporter->SetForcedMaterial(m);
5375
5376	if (1 && mExportGeometry)
5377	{
5378	exporter->ExportGeometry(objects);
5379	}
5380
5381	if (0 && mExportRays)
5382	{
5383	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
5384	}
5385	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5386
5387	delete exporter;
5388	cout << "finished" << endl;
5389	}
5390	}
5391
5392	////////////////
5393	//-- visualization of the BSP splits
5394
5395	bool exportSplits = false;
5396	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
5397
5398	if (exportSplits)
5399	{
5400	cout << "exporting splits ... ";
5401	ExportSplits(objects, visRays);
5402	cout << "finished" << endl;
5403	}
5404
5405	////////
5406	//-- export single view cells
5407
5408	int leafOut;
5409	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5410	const int raysOut = 100;
5411
5412	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5413	}
5414
5415
5416	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
5417	const VssRayContainer &rays)
5418	{
5419	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
5420
5421	if (exporter)
5422	{
5423	Material m;
5424	m.mDiffuseColor = RgbColor(1, 0, 0);
5425	exporter->SetForcedMaterial(m);
5426	exporter->SetWireframe();
5427
5428	exporter->ExportBspSplits(*mVspBspTree, true);
5429
5430	// take forced material, else big scenes cannot be viewed
5431	m.mDiffuseColor = RgbColor(0, 1, 0);
5432	exporter->SetForcedMaterial(m);
5433	exporter->SetFilled();
5434
5435	exporter->ResetForcedMaterial();
5436
5437	// export rays
5438	if (mExportRays)
5439	{
5440	exporter->ExportRays(rays, RgbColor(1, 1, 0));
5441	}
5442
5443	if (mExportGeometry)
5444	{
5445	exporter->ExportGeometry(objects);
5446	}
5447	delete exporter;
5448	}
5449	}
5450
5451
5452	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5453	const int maxViewCells,
5454	const bool sortViewCells,
5455	const bool exportPvs,
5456	const bool exportRays,
5457	const int maxRays,
5458	const string prefix,
5459	VssRayContainer *visRays)
5460	{
5461	if (sortViewCells)
5462	{
5463	// sort view cells to visualize the largest view cells
5464	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5465	}
5466
5467	//////////
5468	//-- some view cells for output
5469
5470	ViewCell::NewMail();
5471	const int limit = min(maxViewCells, (int)mViewCells.size());
5472
5473	for (int i = 0; i < limit; ++ i)
5474	{
5475	cout << "creating output for view cell " << i << " ... ";
5476
5477	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
5478	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
5479
5480	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
5481	continue;
5482
5483	vc->Mail();
5484
5485	ObjectPvs pvs;
5486	mViewCellsTree->GetPvs(vc, pvs);
5487
5488	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5489	Exporter *exporter = Exporter::GetExporter(s);
5490
5491	const float pvsCost = mViewCellsTree->GetPvsCost(vc);
5492	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
5493
5494	if (exportRays)
5495	{
5496	////////////
5497	//-- export rays piercing this view cell
5498
5499	// take rays stored with the view cells during subdivision
5500	VssRayContainer vcRays;
5501	VssRayContainer collectRays;
5502
5503	// collect initial view cells
5504	ViewCellContainer leaves;
5505	mViewCellsTree->CollectLeaves(vc, leaves);
5506
5507	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5508	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5509	{
5510	BspLeaf vcLeaf = static_cast<BspViewCell >(*vit)->mLeaves[0];
5511	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5512
5513	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5514	{
5515	collectRays.push_back(*rit);
5516	}
5517	}
5518
5519	const int raysOut = min((int)collectRays.size(), maxRays);
5520
5521	// prepare some rays for output
5522	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5523	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5524	{
5525	const float p = RandomValue(0.0f, (float)collectRays.size());
5526
5527	if (p < raysOut)
5528	{
5529	vcRays.push_back(*rit);
5530	}
5531	}
5532
5533	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5534	}
5535
5536	////////////////
5537	//-- export view cell geometry
5538
5539	exporter->SetWireframe();
5540
5541	Material m;//= RandomMaterial();
5542	m.mDiffuseColor = RgbColor(0, 1, 0);
5543	exporter->SetForcedMaterial(m);
5544
5545	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5546	exporter->SetFilled();
5547
5548	if (exportPvs)
5549	{
5550	Intersectable::NewMail();
5551
5552	ObjectPvsIterator pit = pvs.GetIterator();
5553
5554	cout << endl;
5555
5556	// output PVS of view cell
5557	while (pit.HasMoreEntries())
5558	{
5559	ObjectPvsEntry entry = pit.Next();
5560	Intersectable *intersect = entry.mObject;
5561
5562	if (!intersect->Mailed())
5563	{
5564	intersect->Mail();
5565
5566	m = RandomMaterial();
5567	exporter->SetForcedMaterial(m);
5568	exporter->ExportIntersectable(intersect);
5569	}
5570	}
5571	cout << endl;
5572	}
5573
5574	DEL_PTR(exporter);
5575	cout << "finished" << endl;
5576	}
5577	}
5578
5579
5580	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
5581	{
5582	Exporter *exporter = Exporter::GetExporter("filter.x3d");
5583
5584	Vector3 bsize = mViewSpaceBox.Size();
5585	const Vector3 viewPoint(mViewSpaceBox.Center());
5586	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
5587	const Vector3 width = Vector3(w);
5588
5589	PrVs testPrVs;
5590
5591	if (exporter)
5592	{
5593	ViewCellContainer viewCells;
5594
5595	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
5596
5597	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
5598
5599	exporter->SetWireframe();
5600
5601	exporter->SetForcedMaterial(RgbColor(1,1,1));
5602	exporter->ExportBox(tbox);
5603
5604	exporter->SetFilled();
5605
5606	exporter->SetForcedMaterial(RgbColor(0,1,0));
5607	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
5608
5609	//exporter->ResetForcedMaterial();
5610	exporter->SetForcedMaterial(RgbColor(0,0,1));
5611	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
5612
5613	exporter->SetForcedMaterial(RgbColor(1,0,0));
5614	exporter->ExportGeometry(objects);
5615
5616	delete exporter;
5617	}
5618	}
5619
5620
5621	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5622	ViewCellContainer &viewCells) const
5623	{
5624	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
5625	}
5626
5627
5628	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
5629	const Vector3 &termination,
5630	ViewCellContainer &viewcells)
5631	{
5632	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
5633	}
5634
5635
5636	bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
5637	const Vector3 &termination,
5638	ViewCell *viewCell)
5639	{
5640	return false;
5641	}
5642
5643
5644	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
5645	{
5646	int numSamples;
5647
5648	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
5649	cout << "samples" << numSamples << endl;
5650
5651	vector<RenderCostSample> samples;
5652
5653	if (!mPreprocessor->GetRenderer())
5654	return;
5655
5656	//start the view point queries
5657	long startTime = GetTime();
5658	cout << "starting sampling of render cost ... ";
5659
5660	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
5661
5662	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
5663
5664
5665	// for each sample:
5666	// find view cells associated with the samples
5667	// store the sample pvs with the pvs associated with the view cell
5668	//
5669	// for each view cell:
5670	// compute difference point sampled pvs - view cell pvs
5671	// export geometry with color coded pvs difference
5672
5673	std::map<ViewCell *, ObjectPvs> sampleMap;
5674
5675	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5676
5677	for (rit = samples.begin(); rit != rit_end; ++ rit)
5678	{
5679	RenderCostSample sample = *rit;
5680
5681	ViewCell *vc = GetViewCell(sample.mPosition);
5682
5683	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5684
5685	if (it == sampleMap.end())
5686	{
5687	sampleMap[vc] = sample.mPvs;
5688	}
5689	else
5690	{
5691	(*it).second.MergeInPlace(sample.mPvs);
5692	}
5693	}
5694
5695	// visualize the view cells
5696	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5697
5698	Material m;//= RandomMaterial();
5699
5700	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5701	{
5702	ViewCell vc = (vit).first;
5703
5704	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5705	const int pvsPtSamples = (*vit).second.GetSize();
5706
5707	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5708	m.mDiffuseColor.b = 1.0f;
5709	//exporter->SetForcedMaterial(m);
5710	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5711
5712	/* // counting the pvss
5713	for (rit = samples.begin(); rit != rit_end; ++ rit)
5714	{
5715	RenderCostSample sample = *rit;
5716	ViewCell *vc = GetViewCell(sample.mPosition);
5717
5718	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5719	Mesh *hMesh = CreateMeshFromBox(box);
5720
5721	DEL_PTR(hMesh);
5722	}
5723	*/
5724	}
5725	}
5726
5727
5728	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5729	ViewCell *vc,
5730	const AxisAlignedBox3 *sceneBox,
5731	const AxisAlignedPlane *clipPlane
5732	) const
5733	{
5734	if (clipPlane)
5735	{
5736	const Plane3 plane = clipPlane->GetPlane();
5737
5738	ViewCellContainer leaves;
5739	mViewCellsTree->CollectLeaves(vc, leaves);
5740	ViewCellContainer::const_iterator it, it_end = leaves.end();
5741
5742	for (it = leaves.begin(); it != it_end; ++ it)
5743	{
5744	BspNodeGeometry geom;
5745	BspNodeGeometry front;
5746	BspNodeGeometry back;
5747
5748	mVspBspTree->ConstructGeometry(*it, geom);
5749
5750	const float eps = 0.0001f;
5751	const int cf = geom.Side(plane, eps);
5752
5753	if (cf == -1)
5754	{
5755	exporter->ExportPolygons(geom.GetPolys());
5756	}
5757	else if (cf == 0)
5758	{
5759	geom.SplitGeometry(front,
5760	back,
5761	plane,
5762	mViewSpaceBox,
5763	eps);
5764
5765	if (back.Valid())
5766	{
5767	exporter->ExportPolygons(back.GetPolys());
5768	}
5769	}
5770	}
5771	}
5772	else
5773	{
5774	// export mesh if available
5775	// TODO: some bug here?
5776	if (1 && vc->GetMesh())
5777	{
5778	exporter->ExportMesh(vc->GetMesh());
5779	}
5780	else
5781	{
5782	BspNodeGeometry geom;
5783	mVspBspTree->ConstructGeometry(vc, geom);
5784	exporter->ExportPolygons(geom.GetPolys());
5785	}
5786	}
5787	}
5788
5789
5790	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5791	{
5792	ViewCellContainer leaves;
5793	mViewCellsTree->CollectLeaves(vc, leaves);
5794
5795	int maxDist = 0;
5796
5797	// compute max height difference
5798	for (int i = 0; i < (int)leaves.size(); ++ i)
5799	{
5800	for (int j = 0; j < (int)leaves.size(); ++ j)
5801	{
5802	BspLeaf leaf = static_cast<BspViewCell >(leaves[i])->mLeaves[0];
5803
5804	if (i != j)
5805	{
5806	BspLeaf leaf2 =static_cast<BspViewCell >(leaves[j])->mLeaves[0];
5807	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5808
5809	if (dist > maxDist)
5810	maxDist = dist;
5811	}
5812	}
5813	}
5814
5815	return maxDist;
5816	}
5817
5818
5819	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5820	{
5821	if (!ViewCellsConstructed())
5822	return NULL;
5823
5824	if (!mViewSpaceBox.IsInside(point))
5825	return NULL;
5826
5827	return mVspBspTree->GetViewCell(point, active);
5828	}
5829
5830
5831	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5832	{
5833	BspNodeGeometry geom;
5834	mVspBspTree->ConstructGeometry(vc, geom);
5835
5836	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5837
5838	IncludeNodeGeomInMesh(geom, *mesh);
5839	mesh->ComputeBoundingBox();
5840
5841	vc->SetMesh(mesh);
5842	}
5843
5844
5845	int VspBspViewCellsManager::CastBeam(Beam &beam)
5846	{
5847	return mVspBspTree->CastBeam(beam);
5848	}
5849
5850
5851	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5852	const bool createMesh)
5853	{
5854	float area = 0;
5855	float volume = 0;
5856
5857	ViewCellContainer leaves;
5858	mViewCellsTree->CollectLeaves(viewCell, leaves);
5859
5860	ViewCellContainer::const_iterator it, it_end = leaves.end();
5861
5862	for (it = leaves.begin(); it != it_end; ++ it)
5863	{
5864	BspNodeGeometry geom;
5865	mVspBspTree->ConstructGeometry(*it, geom);
5866
5867	const float lVol = geom.GetVolume();
5868	const float lArea = geom.GetArea();
5869
5870	area += lArea;
5871	volume += lVol;
5872
5873	if (createMesh)
5874	CreateMesh(*it);
5875	}
5876
5877	viewCell->SetVolume(volume);
5878	viewCell->SetArea(area);
5879	}
5880
5881
5882	void VspBspViewCellsManager::TestSubdivision()
5883	{
5884	ViewCellContainer leaves;
5885	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5886
5887	ViewCellContainer::const_iterator it, it_end = leaves.end();
5888
5889	const float vol = mViewSpaceBox.GetVolume();
5890	float subdivVol = 0;
5891	float newVol = 0;
5892
5893	for (it = leaves.begin(); it != it_end; ++ it)
5894	{
5895	BspNodeGeometry geom;
5896	mVspBspTree->ConstructGeometry(*it, geom);
5897
5898	const float lVol = geom.GetVolume();
5899
5900	newVol += lVol;
5901	subdivVol += (*it)->GetVolume();
5902
5903	float thres = 0.9f;
5904	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5905	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5906	}
5907
5908	Debug << "exact volume: " << vol << endl;
5909	Debug << "subdivision volume: " << subdivVol << endl;
5910	Debug << "new volume: " << newVol << endl;
5911	}
5912
5913
5914	void VspBspViewCellsManager::PrepareLoadedViewCells()
5915	{
5916	// TODO: do I still need this here?
5917	if (0) mVspBspTree->RepairViewCellsLeafLists();
5918	}
5919
5920
5921
5922	/************************************************************************/
5923	/* VspOspViewCellsManager implementation */
5924	/************************************************************************/
5925
5926
5927	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5928	const string &hierarchyType)
5929	: ViewCellsManager(vcTree)
5930	{
5931	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5932
5933	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5934
5935	Debug << "compressing objects: " << mCompressObjects << endl;
5936	cout << "compressing objects: " << mCompressObjects << endl;
5937
5938	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5939	mHierarchyManager->SetViewCellsManager(this);
5940	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5941	}
5942
5943
5944	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5945	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5946	{
5947	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5948	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5949
5950	Debug << "compressing objects: " << mCompressObjects << endl;
5951	cout << "compressing objects: " << mCompressObjects << endl;
5952
5953	mHierarchyManager->SetViewCellsManager(this);
5954	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5955	}
5956
5957
5958	Intersectable *
5959	VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
5960	{
5961	if (mUseKdPvs)
5962	{
5963	return ViewCellsManager::GetIntersectable(ray, isTermination);
5964	}
5965	else
5966	{
5967	return mHierarchyManager->GetIntersectable(ray, isTermination);
5968	}
5969	}
5970
5971
5972	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5973	{
5974	HierarchyManager *hierarchyManager;
5975
5976	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5977	{
5978	Debug << "hierarchy manager: osp" << endl;
5979	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5980	}
5981	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5982	{
5983	Debug << "hierarchy manager: bvh" << endl;
5984	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5985	}
5986	else // only view space partition
5987	{
5988	Debug << "hierarchy manager: obj" << endl;
5989	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5990	}
5991
5992	return hierarchyManager;
5993	}
5994
5995
5996	VspOspViewCellsManager::~VspOspViewCellsManager()
5997	{
5998	DEL_PTR(mHierarchyManager);
5999	}
6000
6001
6002	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
6003	{
6004	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
6005	}
6006
6007
6008	void VspOspViewCellsManager::CollectViewCells()
6009	{
6010	// view cells tree constructed
6011	if (!ViewCellsTreeConstructed())
6012	{
6013	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
6014	}
6015	else
6016	{ // we can use the view cells tree hierarchy to get the right set
6017	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
6018	}
6019	}
6020
6021
6022	bool VspOspViewCellsManager::ViewCellsConstructed() const
6023	{
6024	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
6025	}
6026
6027
6028	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
6029	{
6030	return new VspViewCell(mesh);
6031	}
6032
6033
6034	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
6035	const VssRayContainer &rays)
6036	{
6037	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
6038
6039	// skip rest if view cells were already constructed
6040	if (ViewCellsConstructed())
6041	return 0;
6042
6043	int sampleContributions = 0;
6044	VssRayContainer sampleRays;
6045
6046	int limit = min (mInitialSamples, (int)rays.size());
6047
6048	VssRayContainer constructionRays;
6049	VssRayContainer savedRays;
6050
6051	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
6052	<< ", actual rays: " << (int)rays.size() << endl;
6053
6054	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
6055
6056	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
6057	Debug << "saved rays: " << (int)savedRays.size() << endl;
6058
6059	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
6060
6061	#if TEST_EVALUATION
6062	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
6063	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
6064	{
6065	storedRays.push_back(new VssRay((tit)));
6066	}
6067	#endif
6068
6069	/////////////////////////
6070	//-- print satistics for subdivision and view cells
6071
6072	Debug << endl << endl << *mHierarchyManager << endl;
6073
6074	ResetViewCells();
6075	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
6076
6077	//////////////
6078	//-- recast rest of rays
6079
6080	const long startTime = GetTime();
6081	cout << "Computing remaining ray contributions ... ";
6082
6083	if (SAMPLE_AFTER_SUBDIVISION)
6084	ComputeSampleContributions(savedRays, true, false);
6085
6086	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
6087	<< " secs" << endl;
6088
6089	if (0)
6090	{
6091	// real meshes are constructed at this stage
6092	cout << "finalizing view cells ... ";
6093	FinalizeViewCells(true);
6094	cout << "finished" << endl;
6095	}
6096
6097	return sampleContributions;
6098	}
6099
6100
6101	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
6102	const VssRayContainer &rays)
6103	{
6104	if (!ViewCellsConstructed())
6105	{
6106	Debug << "post process error: no view cells constructed" << endl;
6107	return 0;
6108	}
6109
6110	// if view cells were already constructed before post processing step
6111	// (e.g., because they were loaded), we are finished
6112	if (mViewCellsFinished)
6113	{
6114	FinalizeViewCells(true);
6115	EvaluateViewCellsStats();
6116
6117	return 0;
6118	}
6119
6120	// check if new view cells turned invalid
6121	int minPvs, maxPvs;
6122
6123	if (0)
6124	{
6125	minPvs = mMinPvsSize;
6126	maxPvs = mMaxPvsSize;
6127	}
6128	else
6129	{
6130	// problem matt: why did I start here from zero?
6131	minPvs = 0;
6132	maxPvs = mMaxPvsSize;
6133	}
6134
6135	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
6136	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
6137
6138	SetValidity(minPvs, maxPvs);
6139
6140
6141	// area is not up to date, has to be recomputed
6142	mTotalAreaValid = false;
6143	VssRayContainer postProcessRays;
6144	GetRaySets(rays, mPostProcessSamples, postProcessRays);
6145
6146	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
6147
6148
6149	// compute tree by merging the nodes of the spatial hierarchy
6150	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
6151	mViewCellsTree->SetRoot(root);
6152
6153	//////////////////////////
6154	//-- update pvs up to the root of the hierarchy
6155
6156	ObjectPvs pvs;
6157	UpdatePvsForEvaluation(root, pvs);
6158
6159
6160	//////////////////////
6161	//-- render simulation after merge + refine
6162
6163	cout << "\nview cells partition render time before compress" << endl << endl;
6164	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
6165	SimulationStatistics ss;
6166	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
6167	cout << ss << endl;
6168
6169
6170	mHierarchyManager->CreateUniqueObjectIds();
6171
6172	///////////
6173	//-- compression
6174
6175	if (0) CompressViewCells();
6176
6177	/////////////
6178	//-- some tasks still to do on the view cells:
6179	//-- Compute meshes from view cell geometry, evaluate volume and / or area
6180
6181	if (1) FinalizeViewCells(true);
6182
6183	return 0;
6184	}
6185
6186
6187	int VspOspViewCellsManager::GetType() const
6188	{
6189	return VSP_OSP;
6190	}
6191
6192
6193	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
6194	{
6195	// terminate recursion
6196	if (root->IsLeaf())
6197	{
6198	VspLeaf leaf = static_cast<VspLeaf >(root);
6199	leaf->GetViewCell()->SetMergeCost(0.0f);
6200	return leaf->GetViewCell();
6201	}
6202
6203	VspInterior interior = static_cast<VspInterior >(root);
6204	ViewCellInterior *viewCellInterior = new ViewCellInterior();
6205
6206	// evaluate merge cost for priority traversal
6207	const float mergeCost = -(float)root->mTimeStamp;
6208	viewCellInterior->SetMergeCost(mergeCost);
6209
6210	float volume = 0;
6211
6212	VspNode *front = interior->GetFront();
6213	VspNode *back = interior->GetBack();
6214
6215	ObjectPvs frontPvs, backPvs;
6216
6217	/////////
6218	//-- recursivly compute child hierarchies
6219
6220	ViewCell *backVc = ConstructSpatialMergeTree(back);
6221	ViewCell *frontVc = ConstructSpatialMergeTree(front);
6222
6223	viewCellInterior->SetupChildLink(backVc);
6224	viewCellInterior->SetupChildLink(frontVc);
6225
6226	volume += backVc->GetVolume();
6227	volume += frontVc->GetVolume();
6228
6229	viewCellInterior->SetVolume(volume);
6230
6231	return viewCellInterior;
6232	}
6233
6234
6235	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
6236	{
6237	if (!ViewCellsConstructed())
6238	return ViewCellsManager::GetViewPoint(viewPoint);
6239
6240	// TODO: set reasonable limit
6241	const int limit = 20;
6242
6243	for (int i = 0; i < limit; ++ i)
6244	{
6245	viewPoint = mViewSpaceBox.GetRandomPoint();
6246
6247	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
6248	{
6249	return true;
6250	}
6251	}
6252
6253	Debug << "failed to find valid view point, taking " << viewPoint << endl;
6254	return false;
6255	}
6256
6257
6258	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
6259	ViewCell *vc,
6260	const AxisAlignedBox3 *sceneBox,
6261	const AxisAlignedPlane *clipPlane
6262	) const
6263	{
6264	ViewCellContainer leaves;
6265	mViewCellsTree->CollectLeaves(vc, leaves);
6266	ViewCellContainer::const_iterator it, it_end = leaves.end();
6267
6268	Plane3 plane;
6269	if (clipPlane)
6270	{
6271	// arbitrary plane definition
6272	plane = clipPlane->GetPlane();
6273	}
6274
6275	for (it = leaves.begin(); it != it_end; ++ it)
6276	{
6277	VspViewCell vspVc = static_cast<VspViewCell >(*it);
6278	VspLeaf *l = vspVc->mLeaves[0];
6279
6280	const AxisAlignedBox3 box =
6281	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
6282
6283	if (sceneBox && !Overlap(*sceneBox, box))
6284	continue;
6285
6286	if (clipPlane)
6287	{
6288	if (box.Side(plane) == -1)
6289	{
6290	exporter->ExportBox(box);
6291	}
6292	else if (box.Side(plane) == 0)
6293	{
6294	// intersection
6295	AxisAlignedBox3 fbox, bbox;
6296	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
6297	exporter->ExportBox(bbox);
6298	}
6299	}
6300	else
6301	{
6302	exporter->ExportBox(box);
6303	}
6304	}
6305	}
6306
6307
6308	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
6309	{
6310	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
6311	// validy update in preprocessor for all managers)
6312	return ViewCellsManager::ViewPointValid(viewPoint);
6313
6314	// return mViewSpaceBox.IsInside(viewPoint) &&
6315	// mVspTree->ViewPointValid(viewPoint);
6316	}
6317
6318
6319	float VspOspViewCellsManager::UpdateObjectCosts()
6320	{
6321	float maxRenderCost = 0;
6322
6323	cout << "updating object pvs cost ... ";
6324	const long startTime = GetTime();
6325
6326	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
6327
6328	Intersectable::NewMail();
6329
6330	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
6331
6332	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
6333	{
6334	ViewCell vc = vit;
6335
6336	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
6337
6338	// output PVS of view cell
6339	while (pit.HasMoreEntries())
6340	{
6341	ObjectPvsEntry entry = pit.Next();
6342
6343	BvhNode node = static_cast<BvhNode >(entry.mObject);
6344
6345	// hack!!
6346	if (!node->IsLeaf())
6347	{
6348	cout << "error, can only do leaves" << endl;
6349	return 0;
6350	}
6351
6352	if (!node->Mailed())
6353	{
6354	node->Mail();
6355	node->mRenderCost = 0;
6356	}
6357
6358	const float rc = (float)((BvhLeaf *)node)->mObjects.size();
6359
6360	node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
6361
6362	if (node->mRenderCost > maxRenderCost)
6363	maxRenderCost = node->mRenderCost;
6364	}
6365	}
6366
6367	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
6368
6369	return maxRenderCost;
6370	}
6371
6372
6373	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
6374	const VssRayContainer &sampleRays)
6375	{
6376	if (!ViewCellsConstructed())
6377	return;
6378
6379	VssRayContainer visRays;
6380	GetRaySets(sampleRays, mVisualizationSamples, visRays);
6381
6382	////////////
6383	//-- export final view cells
6384
6385	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
6386
6387	//Vector3 scale(0.9f, 0.9f, 0.9f);
6388	Vector3 scale(1.0f, 1.0f, 1.0f);
6389
6390	if (exporter)
6391	{
6392	if (CLAMP_TO_BOX)
6393	{
6394	exporter->mClampToBox = true;
6395	}
6396
6397	EvaluateViewCellsStats();
6398
6399	const long starttime = GetTime();
6400	cout << "exporting final view cells (after initial construction + post process) ... " << endl;
6401
6402	// matt: hack for clamping scene
6403	AxisAlignedBox3 bbox = mViewSpaceBox;
6404	bbox.Scale(scale);
6405
6406	if (1 && mExportRays)
6407	{
6408	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
6409	}
6410
6411	// hack color code
6412	const int savedColorCode = mColorCode;
6413
6414	const float maxRenderCost = UpdateObjectCosts();
6415	cout << "maxRenderCost: " << maxRenderCost << endl;
6416	mColorCode = 0; // 0 = random, 1 = export pvs
6417
6418	if (0)
6419	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
6420	CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
6421
6422
6423	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6424	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
6425
6426	delete exporter;
6427
6428	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6429	mColorCode = savedColorCode;
6430	}
6431
6432	exporter = Exporter::GetExporter("final_object_partition.wrl");
6433
6434	if (exporter)
6435	{
6436	if (CLAMP_TO_BOX)
6437	{
6438	exporter->mClampToBox = true;
6439	}
6440
6441	EvaluateViewCellsStats();
6442
6443	const long starttime = GetTime();
6444	cout << "exporting final objects (after initial construction + post process) ... ";
6445
6446	// matt: hack for clamping scene
6447	AxisAlignedBox3 bbox = mViewSpaceBox;
6448	bbox.Scale(scale);
6449
6450	// hack color code (show pvs size)
6451	const int savedColorCode = mColorCode;
6452
6453	mColorCode = 1; // 0 = random, 1 = export pvs
6454	// don't visualize render cost
6455	const float maxRenderCost = -1;
6456
6457	if (1)
6458	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
6459	CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
6460
6461
6462	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6463	if (0)
6464	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
6465
6466	delete exporter;
6467
6468	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6469	mColorCode = savedColorCode;
6470	}
6471
6472	// visualization of the merged view cells
6473	if (0)
6474	{
6475	ExportMergedViewCells(objects);
6476	}
6477
6478	// export some view cells
6479	int leafOut;
6480	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
6481
6482	const bool sortViewCells = false;
6483	const bool exportPvs = true;
6484	const bool exportRays = true;
6485	const int raysOut = 100;
6486
6487	ExportSingleViewCells(objects,
6488	leafOut,
6489	sortViewCells,
6490	exportPvs,
6491	exportRays,
6492	raysOut,
6493	"");
6494	}
6495
6496
6497	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
6498	const int maxViewCells,
6499	const bool sortViewCells,
6500	const bool exportPvs,
6501	const bool exportRays,
6502	const int maxRays,
6503	const string prefix,
6504	VssRayContainer *visRays)
6505	{
6506	if (sortViewCells)
6507	{
6508	// sort view cells to visualize the view cells with highest render cost
6509	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
6510	}
6511
6512	ViewCell::NewMail();
6513	const int limit = min(maxViewCells, (int)mViewCells.size());
6514
6515	cout << "\nExporting " << limit << " single view cells: " << endl;
6516
6517	for (int i = 0; i < limit; ++ i)
6518	{
6519	cout << "creating output for view cell " << i << " ... ";
6520
6521	// largest view cell pvs first of random view cell
6522	ViewCell *vc = sortViewCells ?
6523	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
6524
6525	if (vc->Mailed()) // view cell already processed
6526	continue;
6527
6528	vc->Mail();
6529
6530	ObjectPvs pvs;
6531	mViewCellsTree->GetPvs(vc, pvs);
6532
6533	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
6534	Exporter *exporter = Exporter::GetExporter(s);
6535
6536	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;
6537
6538	if (exportPvs)
6539	{
6540	Material m;
6541
6542	Intersectable::NewMail();
6543
6544	ObjectPvsIterator pit = pvs.GetIterator();
6545
6546	// output PVS of view cell
6547	while (pit.HasMoreEntries())
6548	{
6549	ObjectPvsEntry entry = pit.Next();
6550
6551	Intersectable *intersect = entry.mObject;
6552
6553	if (!intersect->Mailed())
6554	{
6555	m = RandomMaterial();
6556	exporter->SetForcedMaterial(m);
6557
6558	exporter->ExportIntersectable(intersect);
6559	intersect->Mail();
6560	}
6561	}
6562	}
6563
6564	if (exportRays)
6565	{
6566	////////////
6567	//-- export the sample rays
6568
6569	// output rays stored with the view cells during subdivision
6570	VssRayContainer vcRays;
6571	VssRayContainer collectRays;
6572
6573	// collect intial view cells
6574	ViewCellContainer leaves;
6575	mViewCellsTree->CollectLeaves(vc, leaves);
6576
6577	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
6578
6579	for (vit = leaves.begin(); vit != vit_end; ++ vit)
6580	{
6581	VspLeaf vcLeaf = static_cast<VspViewCell >(*vit)->mLeaves[0];
6582	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
6583
6584	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
6585	{
6586	collectRays.push_back(*rit);
6587	}
6588	}
6589
6590	const int raysOut = min((int)collectRays.size(), maxRays);
6591
6592	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
6593
6594	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
6595	{
6596	const float p = RandomValue(0.0f, (float)collectRays.size());
6597
6598	if (p < raysOut)
6599	vcRays.push_back(*rit);
6600	}
6601
6602	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
6603	}
6604
6605
6606	/////////////////
6607	//-- export view cell geometry
6608
6609	exporter->SetWireframe();
6610
6611	Material m;
6612	m.mDiffuseColor = RgbColor(0, 1, 0);
6613	exporter->SetForcedMaterial(m);
6614
6615	ExportViewCellGeometry(exporter, vc, NULL, NULL);
6616	exporter->SetFilled();
6617
6618	DEL_PTR(exporter);
6619	cout << "finished" << endl;
6620	}
6621
6622	cout << endl;
6623	}
6624
6625
6626	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
6627	ViewCellContainer &viewCells) const
6628	{
6629	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
6630	}
6631
6632
6633	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
6634	const Vector3 &termination,
6635	ViewCellContainer &viewcells)
6636	{
6637	return mHierarchyManager->
6638	GetVspTree()->CastLineSegment(origin, termination, viewcells);
6639	}
6640
6641
6642	bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
6643	const Vector3 &termination,
6644	ViewCell *viewCell)
6645	{
6646	return mHierarchyManager->
6647	GetVspTree()->LineSegmentIntersects(origin, termination, viewCell);
6648	}
6649
6650
6651	bool VspOspViewCellsManager::ExportViewCells(const string filename,
6652	const bool exportPvs,
6653	const ObjectContainer &objects)
6654	{
6655	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6656	return false;
6657
6658	const long starttime = GetTime();
6659	cout << "exporting view cells to xml ... ";
6660
6661	OUT_STREAM stream(filename.c_str());
6662
6663	// for output we need unique ids for each view cell
6664	CreateUniqueViewCellIds();
6665
6666	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6667	stream << "<VisibilitySolution>" << endl;
6668
6669	// §§ tmp matt: for storage cost
6670	if (0 && exportPvs)
6671	{
6672	///////////////
6673	//-- export bounding boxes
6674	//-- The bounding boxes are used to identify
6675	//-- the objects in the rendering engine
6676	mHierarchyManager->ExportBoundingBoxes(stream, objects);
6677	}
6678
6679	//////////////////////////
6680	//-- export the view cells and the pvs
6681
6682	const int numViewCells = mCurrentViewCellsStats.viewCells;
6683
6684	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6685	mViewCellsTree->Export(stream, exportPvs);
6686	stream << "</ViewCells>" << endl;
6687
6688	//////////////////////
6689	//-- export the view space hierarchy
6690
6691	stream << "<ViewSpaceHierarchy type=\"vsp\""
6692	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6693	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6694
6695	mHierarchyManager->GetVspTree()->Export(stream);
6696	stream << "</ViewSpaceHierarchy>" << endl;
6697
6698	//////////////////////
6699	//-- export the object space partition
6700
6701	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6702
6703	stream << "</VisibilitySolution>" << endl;
6704	stream.close();
6705
6706	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6707	return true;
6708	}
6709
6710
6711
6712	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6713	const bool active) const
6714	{
6715	if (!ViewCellsConstructed())
6716	return NULL;
6717
6718	if (!mViewSpaceBox.IsInside(point))
6719	return NULL;
6720
6721	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6722	}
6723
6724
6725	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6726	{
6727	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6728
6729	ViewCellContainer leaves;
6730	mViewCellsTree->CollectLeaves(vc, leaves);
6731
6732	ViewCellContainer::const_iterator it, it_end = leaves.end();
6733
6734	for (it = leaves.begin(); it != it_end; ++ it)
6735	{
6736	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6737	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6738	IncludeBoxInMesh(box, *mesh);
6739	}
6740
6741	mesh->ComputeBoundingBox();
6742
6743	vc->SetMesh(mesh);
6744	}
6745
6746
6747	int VspOspViewCellsManager::CastBeam(Beam &beam)
6748	{
6749	// matt: TODO
6750	return 0;
6751	}
6752
6753
6754	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6755	{
6756	float area = 0;
6757	float volume = 0;
6758
6759	ViewCellContainer leaves;
6760	mViewCellsTree->CollectLeaves(viewCell, leaves);
6761
6762	ViewCellContainer::const_iterator it, it_end = leaves.end();
6763
6764	for (it = leaves.begin(); it != it_end; ++ it)
6765	{
6766	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6767
6768	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6769
6770	const float lVol = box.GetVolume();
6771	const float lArea = box.SurfaceArea();
6772
6773	area += lArea;
6774	volume += lVol;
6775
6776	CreateMesh(*it);
6777	}
6778
6779	viewCell->SetVolume(volume);
6780	viewCell->SetArea(area);
6781	}
6782
6783
6784	void VspOspViewCellsManager::PrepareLoadedViewCells()
6785	{
6786	// TODO
6787	}
6788
6789
6790	static void PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6791	{
6792	float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6793
6794	float fullmem = mem +
6795	(hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6796	hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6797
6798	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6799	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6800	}
6801
6802
6803	void VspOspViewCellsManager::CompressViewCells()
6804	{
6805	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6806	return;
6807
6808	////////////
6809	//-- compression
6810
6811	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6812
6813	cout << "before compression: " << endl;
6814	Debug << "before compression: " << endl;
6815
6816	PrintCompressionStats(mHierarchyManager, pvsEntries);
6817
6818	if (mCompressObjects)
6819	{
6820	cout << "compressing in the objects: " << endl;
6821	Debug << "compressing in the objects: " << endl;
6822
6823	pvsEntries = mHierarchyManager->CompressObjectSpace();
6824	}
6825	else
6826	{
6827	cout << "compressing in the view space: " << endl;
6828	Debug << "compressing in the view space: " << endl;
6829
6830	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6831	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6832	}
6833
6834	PrintCompressionStats(mHierarchyManager, pvsEntries);
6835	}
6836
6837
6838	ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
6839	ObjectContainer *objects,
6840	const bool finalizeViewCells,
6841	BoundingBoxConverter *bconverter)
6842
6843	{
6844	ViewCellsManager *vm =
6845	ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
6846
6847	return vm;
6848	}
6849
6850
6851	void
6852	VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
6853	{
6854	mHierarchyManager->CollectObjects(box, objects);
6855	}
6856
6857
6858	#if 1
6859
6860	void VspOspViewCellsManager::EvalViewCellPartition()
6861	{
6862	int samplesPerPass;
6863	int numSamples;
6864	int castSamples = 0;
6865	int oldSamples = 0;
6866	int samplesForStats;
6867	char statsPrefix[100];
6868	char suffix[100];
6869	int splitsStepSize;
6870
6871	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6872	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6873	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
6874	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6875	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6876
6877	bool useHisto;
6878	int histoMem;
6879
6880	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6881	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6882
6883	Debug << "step size: " << splitsStepSize << endl;
6884	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6885	Debug << "view cell evaluation samples: " << numSamples << endl;
6886	Debug << "view cell stats prefix: " << statsPrefix << endl;
6887
6888	cout << "reseting pvs ... ";
6889
6890	// reset pvs and start over from zero
6891	mViewCellsTree->ResetPvs();
6892
6893	cout << "finished" << endl;
6894	cout << "Evaluating view cell partition ... " << endl;
6895
6896	vector<int> evalStrats;
6897
6898	// mix of sampling strategies
6899	if (0)
6900	{
6901	evalStrats.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
6902	}
6903	else
6904	{
6905	/*evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
6906	evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6907	evalStrats.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
6908	*/
6909	evalStrats.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
6910	}
6911
6912	Debug << "casting eval strategies: ";
6913	for (int i = 0; i < (int)evalStrats.size(); ++ i)
6914	Debug << evalStrats[i] << " ";
6915	Debug << endl;
6916
6917	cout << "casting eval strategies: ";
6918	for (int i = 0; i < (int)evalStrats.size(); ++ i)
6919	cout << evalStrats[i] << " ";
6920	cout << endl;
6921
6922	int pass = 0;
6923
6924	while (castSamples < numSamples)
6925	{
6926	///////////////
6927	//-- we have to use uniform sampling strategy for construction rays
6928
6929	VssRayContainer evaluationSamples;
6930	const int samplingType = mEvaluationSamplingType;
6931
6932	long startTime = GetTime();
6933
6934	cout << "casting " << samplesPerPass << " samples ... ";
6935	Debug << "casting " << samplesPerPass << " samples ... ";
6936
6937	if (1)
6938	{
6939	CastPassSamples(samplesPerPass, evalStrats, evaluationSamples);
6940	}
6941	else
6942	{
6943	// use mixed distributions
6944	CastPassSamples2(samplesPerPass, evaluationSamples);
6945	}
6946
6947	castSamples += samplesPerPass;
6948
6949	Real timeDiff = TimeDiff(startTime, GetTime());
6950
6951	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6952	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6953
6954	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6955	Debug << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6956
6957	startTime = GetTime();
6958
6959	ComputeSampleContributions(evaluationSamples, true, false);
6960
6961	timeDiff = TimeDiff(startTime, GetTime());
6962	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6963	Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6964
6965	if ((castSamples >= samplesForStats + oldSamples) \|\|
6966	(castSamples >= numSamples))
6967	{
6968	oldSamples += samplesForStats;
6969
6970	///////////
6971	//-- output stats
6972
6973	sprintf(suffix, "-%09d-eval.log", castSamples);
6974	const string filename = string(statsPrefix) + string(suffix);
6975
6976	startTime = GetTime();
6977
6978	cout << "compute new statistics ... " << endl;
6979
6980	ofstream ofstr(filename.c_str());
6981	mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6982
6983	timeDiff = TimeDiff(startTime, GetTime());
6984	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6985	cout << "*************************************" << endl;
6986
6987	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6988
6989	#if 0
6990	//////////////
6991	// filtered stats
6992
6993	sprintf(suffix, "-%09d-eval-filter.log", castSamples);
6994	const string filename2 = string(statsPrefix) + string(suffix);
6995
6996	startTime = GetTime();
6997
6998	cout << "compute new statistics for filtered pvs ... " << endl;
6999
7000	ofstream ofstr2(filename2.c_str());
7001	mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);
7002
7003	timeDiff = TimeDiff(startTime, GetTime());
7004	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
7005	cout << "*************************************" << endl;
7006	Debug << "filtered statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
7007	#endif
7008
7009	// only for debugging purpose
7010	if (0)
7011	{
7012	ViewCellContainer viewCells;
7013	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);
7014
7015	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
7016	int pvsSize = 0;
7017
7018	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
7019	{
7020	pvsSize += (*vit)->GetPvs().GetSize();
7021	}
7022
7023	cout << "debug entries: " << pvsSize << ", memcost: "
7024	<< (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
7025	}
7026	++ pass;
7027	}
7028
7029	disposeRays(evaluationSamples, NULL);
7030	}
7031
7032	////////////
7033	//-- histogram
7034	#if 1
7035	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
7036	int histoStepSize;
7037
7038	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
7039	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
7040
7041	if (useHisto)
7042	{
7043	// evaluate view cells in a histogram
7044	char str[64];
7045
7046	// hack: just show final view cells
7047	int pass = (int)mViewCells.size();
7048	//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
7049	if (1)
7050	{
7051	string filename;
7052
7053	cout << "computing histogram for " << pass << " view cells" << endl;
7054
7055	//////////////////////////////////////////
7056	//-- evaluate histogram for pvs size
7057
7058	cout << "computing pvs histogram for " << pass << " view cells" << endl;
7059
7060	sprintf(str, "-%09d-histo-pvs2.log", pass);
7061	filename = string(statsPrefix) + string(str);
7062
7063	EvalViewCellHistogramForPvsSize(filename, pass);
7064	}
7065	}
7066	#endif
7067	}
7068
7069	#endif
7070
7071
7072
7073	}

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

Download in other formats: