Context Navigation

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

Revision 2115, 177.2 KB checked in by mattausch, 17 years ago (diff)
changed pvs loading: loading objects in a first pass

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

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

Download in other formats: