Context Navigation

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

Revision 2116, 177.0 KB checked in by mattausch, 17 years ago (diff)
implemented hashpvs

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

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

Download in other formats: