Context Navigation

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

Revision 2021, 175.5 KB checked in by bittner, 17 years ago (diff)

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

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

Download in other formats: