Context Navigation

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

Revision 2066, 177.2 KB checked in by mattausch, 17 years ago (diff)
worked on integration manual

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

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

Download in other formats: