Context Navigation

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

Revision 2019, 175.2 KB checked in by bittner, 17 years ago (diff)
merge

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	float ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2618	const bool addRays,
2619	ViewCell *currentViewCell,
2620	const bool useHitObjects)
2621	{
2622	ray.mPvsContribution = 0;
2623	ray.mRelativePvsContribution = 0.0f;
2624
2625	if (!ray.mTerminationObject)
2626	return 0.0f;
2627
2628	// optain pvs entry (can be different from hit object)
2629	Intersectable *terminationObj;
2630
2631	if (!useHitObjects)
2632	terminationObj = GetIntersectable(ray, true);
2633	else
2634	terminationObj = ray.mTerminationObject;
2635
2636	ComputeViewCellContribution(currentViewCell,
2637	ray,
2638	terminationObj,
2639	ray.mTermination,
2640	addRays);
2641
2642	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2643	float c = 0.0f;
2644	if (terminationObj)
2645	c = ray.Length();
2646
2647	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2648	return c;
2649	#else
2650	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2651	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2652	#endif
2653	}
2654
2655
2656	float
2657	ViewCellsManager::ComputeSampleContribution(VssRay &ray,
2658	const bool addRays,
2659	const bool storeViewCells,
2660	const bool useHitObjects)
2661	{
2662	ray.mPvsContribution = 0;
2663	ray.mRelativePvsContribution = 0.0f;
2664
2665	mSamplesStat.mRays++;
2666
2667	if (!ray.mTerminationObject)
2668	return 0.0f;
2669
2670	static Ray hray;
2671	hray.Init(ray);
2672
2673	float tmin = 0, tmax = 1.0;
2674
2675	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax)) {
2676	// cerr<<"ray outside view space box\n";
2677	return 0;
2678	}
2679
2680	Vector3 origin = hray.Extrap(tmin);
2681	Vector3 termination = hray.Extrap(tmax);
2682
2683	ViewCell::NewMail();
2684
2685	viewCellCastTimer.Entry();
2686
2687	static ViewCellContainer viewCells;
2688	static VssRay *lastVssRay = NULL;
2689
2690	if (lastVssRay == NULL \|\|
2691	!(ray.mOrigin == lastVssRay->mTermination) \|\|
2692	!(ray.mTermination == lastVssRay->mOrigin)) {
2693	viewCells.clear();
2694	// traverse the view space subdivision
2695	CastLineSegment(origin, termination, viewCells);
2696	lastVssRay = &ray;
2697	}
2698
2699	viewCellCastTimer.Exit();
2700
2701	mSamplesStat.mViewCells += (int)viewCells.size();
2702
2703	if (storeViewCells)
2704	{
2705	cerr<<"Store viewcells should not be used in the test!"<<endl;
2706	// copy viewcells memory efficiently
2707	#if VSS_STORE_VIEWCELLS
2708	ray.mViewCells.reserve(viewCells.size());
2709	ray.mViewCells = viewCells;
2710	#else
2711	cerr<<"Vss store viewcells not supported."<<endl;
2712	exit(1);
2713	#endif
2714	}
2715
2716	Intersectable *terminationObj;
2717
2718	objTimer.Entry();
2719
2720	// obtain pvs entry (can be different from hit object)
2721	if (!useHitObjects)
2722	terminationObj = GetIntersectable(ray, true);
2723	else
2724	terminationObj = ray.mTerminationObject;
2725
2726	objTimer.Exit();
2727
2728	pvsTimer.Entry();
2729
2730	ViewCellContainer::const_iterator it = viewCells.begin();
2731
2732	for (; it != viewCells.end(); ++ it)
2733	{
2734	ComputeViewCellContribution(*it,
2735	ray,
2736	terminationObj,
2737	ray.mTermination,
2738	addRays);
2739	}
2740
2741	pvsTimer.Exit();
2742
2743	mSamplesStat.mPvsContributions += ray.mPvsContribution;
2744	if (ray.mPvsContribution)
2745	mSamplesStat.mContributingRays++;
2746
2747	#if AVG_RAY_CONTRIBUTIONS
2748	ray.mRelativePvsContribution /= (float)viewCells.size();
2749	#endif
2750
2751	#if USE_RAY_LENGTH_AS_CONTRIBUTION
2752	float c = 0.0f;
2753	if (terminationObj)
2754	c = ray.Length();
2755	ray.mRelativePvsContribution = ray.mPvsContribution = c;
2756	return c;
2757	#else
2758	return ABS_CONTRIBUTION_WEIGHT*ray.mPvsContribution +
2759	(1.0f - ABS_CONTRIBUTION_WEIGHT)*ray.mRelativePvsContribution;
2760	#endif
2761	}
2762
2763
2764	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
2765	const int maxSize,
2766	VssRayContainer &usedRays,
2767	VssRayContainer *savedRays) const
2768	{
2769	const int limit = min(maxSize, (int)sourceRays.size());
2770	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
2771
2772	VssRayContainer::const_iterator it, it_end = sourceRays.end();
2773	for (it = sourceRays.begin(); it != it_end; ++ it)
2774	{
2775	if (Random(1.0f) < prop)
2776	usedRays.push_back(*it);
2777	else if (savedRays)
2778	savedRays->push_back(*it);
2779	}
2780	}
2781
2782
2783	float ViewCellsManager::GetRendercost(ViewCell *viewCell) const
2784	{
2785	return (float)mViewCellsTree->GetPvsCost(viewCell);
2786	}
2787
2788
2789	float ViewCellsManager::GetAccVcArea()
2790	{
2791	// if already computed
2792	if (mTotalAreaValid)
2793	{
2794	return mTotalArea;
2795	}
2796
2797	mTotalArea = 0;
2798	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2799
2800	for (it = mViewCells.begin(); it != it_end; ++ it)
2801	{
2802	//Debug << "area: " << GetArea(*it);
2803	mTotalArea += GetArea(*it);
2804	}
2805
2806	mTotalAreaValid = true;
2807
2808	return mTotalArea;
2809	}
2810
2811
2812	void ViewCellsManager::PrintStatistics(ostream &s) const
2813	{
2814	s << mCurrentViewCellsStats << endl;
2815	}
2816
2817
2818	void ViewCellsManager::CreateUniqueViewCellIds()
2819	{
2820	if (ViewCellsTreeConstructed())
2821	{
2822	mViewCellsTree->CreateUniqueViewCellsIds();
2823	}
2824	else // no view cells tree, handle view cells "myself"
2825	{
2826	int i = 0;
2827	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
2828	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
2829	{
2830	if ((*vit)->GetId() != OUT_OF_BOUNDS_ID)
2831	{
2832	mViewCells[i]->SetId(i ++);
2833	}
2834	}
2835	}
2836	}
2837
2838
2839	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter,
2840	const AxisAlignedBox3 *sceneBox,
2841	const bool colorCode,
2842	const AxisAlignedPlane *clipPlane
2843	) const
2844	{
2845	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2846
2847	for (it = mViewCells.begin(); it != it_end; ++ it)
2848	{
2849	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
2850	{
2851	ExportColor(exporter, *it, colorCode);
2852	ExportViewCellGeometry(exporter, *it, sceneBox, clipPlane);
2853	}
2854	}
2855	}
2856
2857
2858	void ViewCellsManager::CreateViewCellMeshes()
2859	{
2860	// convert to meshes
2861	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2862
2863	for (it = mViewCells.begin(); it != it_end; ++ it)
2864	{
2865	if (!(*it)->GetMesh())
2866	{
2867	CreateMesh(*it);
2868	}
2869	}
2870	}
2871
2872
2873	bool ViewCellsManager::ExportViewCells(const string filename,
2874	const bool exportPvs,
2875	const ObjectContainer &objects)
2876	{
2877	return false;
2878	}
2879
2880
2881	void ViewCellsManager::CollectViewCells(const int n)
2882	{
2883	mNumActiveViewCells = n;
2884	mViewCells.clear();
2885	// implemented in subclasses
2886	CollectViewCells();
2887	}
2888
2889
2890	void ViewCellsManager::SetViewCellActive(ViewCell *vc) const
2891	{
2892	ViewCellContainer leaves;
2893	// sets the pointers to the currently active view cells
2894	mViewCellsTree->CollectLeaves(vc, leaves);
2895
2896	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
2897	for (lit = leaves.begin(); lit != lit_end; ++ lit)
2898	{
2899	static_cast<ViewCellLeaf >(lit)->SetActiveViewCell(vc);
2900	}
2901	}
2902
2903
2904	void ViewCellsManager::SetViewCellsActive()
2905	{
2906	// collect leaf view cells and set the pointers to
2907	// the currently active view cells
2908	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
2909
2910	for (it = mViewCells.begin(); it != it_end; ++ it)
2911	{
2912	SetViewCellActive(*it);
2913	}
2914	}
2915
2916
2917	int ViewCellsManager::GetMaxFilterSize() const
2918	{
2919	return mMaxFilterSize;
2920	}
2921
2922
2923	static const bool USE_ASCII = true;
2924
2925
2926	bool ViewCellsManager::ExportBoundingBoxes(const string filename,
2927	const ObjectContainer &objects) const
2928	{
2929	ObjectContainer::const_iterator it, it_end = objects.end();
2930
2931	if (USE_ASCII)
2932	{
2933	ofstream boxesOut(filename.c_str());
2934	if (!boxesOut.is_open())
2935	return false;
2936
2937	for (it = objects.begin(); it != it_end; ++ it)
2938	{
2939	MeshInstance mi = static_cast<MeshInstance >(*it);
2940	const AxisAlignedBox3 box = mi->GetBox();
2941
2942	boxesOut << mi->GetId() << " "
2943	<< box.Min().x << " "
2944	<< box.Min().y << " "
2945	<< box.Min().z << " "
2946	<< box.Max().x << " "
2947	<< box.Max().y << " "
2948	<< box.Max().z << endl;
2949	}
2950
2951	boxesOut.close();
2952	}
2953	else
2954	{
2955	ofstream boxesOut(filename.c_str(), ios::binary);
2956
2957	if (!boxesOut.is_open())
2958	return false;
2959
2960	for (it = objects.begin(); it != it_end; ++ it)
2961	{
2962	MeshInstance mi = static_cast<MeshInstance >(*it);
2963	const AxisAlignedBox3 box = mi->GetBox();
2964	Vector3 bmin = box.Min();
2965	Vector3 bmax = box.Max();
2966	int id = mi->GetId();
2967
2968	boxesOut.write(reinterpret_cast<char *>(&id), sizeof(int));
2969	boxesOut.write(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
2970	boxesOut.write(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
2971	}
2972
2973	boxesOut.close();
2974	}
2975
2976	return true;
2977	}
2978
2979
2980	bool ViewCellsManager::LoadBoundingBoxes(const string filename,
2981	IndexedBoundingBoxContainer &boxes) const
2982	{
2983	Vector3 bmin, bmax;
2984	int id;
2985
2986	if (USE_ASCII)
2987	{
2988	ifstream boxesIn(filename.c_str());
2989
2990	if (!boxesIn.is_open())
2991	{
2992	cout << "failed to open file " << filename << endl;
2993	return false;
2994	}
2995
2996	string buf;
2997	while (!(getline(boxesIn, buf)).eof())
2998	{
2999	sscanf(buf.c_str(), "%d %f %f %f %f %f %f",
3000	&id, &bmin.x, &bmin.y, &bmin.z,
3001	&bmax.x, &bmax.y, &bmax.z);
3002
3003	AxisAlignedBox3 box(bmin, bmax);
3004	// MeshInstance *mi = new MeshInstance();
3005	// HACK: set bounding box to new box
3006	//mi->mBox = box;
3007
3008	boxes.push_back(IndexedBoundingBox(id, box));
3009	}
3010
3011	boxesIn.close();
3012	}
3013	else
3014	{
3015	ifstream boxesIn(filename.c_str(), ios::binary);
3016
3017	if (!boxesIn.is_open())
3018	return false;
3019
3020	while (1)
3021	{
3022	boxesIn.read(reinterpret_cast<char *>(&id), sizeof(Vector3));
3023	boxesIn.read(reinterpret_cast<char *>(&bmin), sizeof(Vector3));
3024	boxesIn.read(reinterpret_cast<char *>(&bmax), sizeof(Vector3));
3025
3026	if (boxesIn.eof())
3027	break;
3028
3029
3030	AxisAlignedBox3 box(bmin, bmax);
3031	MeshInstance *mi = new MeshInstance(NULL);
3032
3033	// HACK: set bounding box to new box
3034	//mi->mBox = box;
3035	//boxes.push_back(mi);
3036	boxes.push_back(IndexedBoundingBox(id, box));
3037	}
3038
3039	boxesIn.close();
3040	}
3041
3042	return true;
3043	}
3044
3045
3046	float ViewCellsManager::GetFilterWidth()
3047	{
3048	return mFilterWidth;
3049	}
3050
3051
3052	float ViewCellsManager::GetAbsFilterWidth()
3053	{
3054	return Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
3055	}
3056
3057
3058	void ViewCellsManager::UpdateScalarPvsSize(ViewCell *vc,
3059	const float pvsCost,
3060	const int entriesInPvs) const
3061	{
3062	vc->mPvsCost = pvsCost;
3063	vc->mEntriesInPvs = entriesInPvs;
3064
3065	vc->mPvsSizeValid = true;
3066	}
3067
3068
3069	void
3070	ViewCellsManager::ApplyFilter(ViewCell *viewCell,
3071	KdTree *kdTree,
3072	const float viewSpaceFilterSize,
3073	const float spatialFilterSize,
3074	ObjectPvs &pvs
3075	)
3076	{
3077	// extend the pvs of the viewcell by pvs of its neighbors
3078	// and apply spatial filter by including all neighbors of the objects
3079	// in the pvs
3080
3081	// get all viewcells intersecting the viewSpaceFilterBox
3082	// and compute the pvs union
3083
3084	//Vector3 center = viewCell->GetBox().Center();
3085	// Vector3 center = m->mBox.Center();
3086
3087	// AxisAlignedBox3 box(center - Vector3(viewSpaceFilterSize/2),
3088	// center + Vector3(viewSpaceFilterSize/2));
3089	if (!ViewCellsConstructed())
3090	return;
3091
3092	if (viewSpaceFilterSize >= 0.0f) {
3093
3094	const bool usePrVS = false;
3095
3096	if (!usePrVS) {
3097	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3098	box.Enlarge(Vector3(viewSpaceFilterSize/2));
3099
3100	ViewCellContainer viewCells;
3101	ComputeBoxIntersections(box, viewCells);
3102
3103	// cout<<"box="<<box<<endl;
3104	ViewCellContainer::const_iterator it = viewCells.begin(), it_end = viewCells.end();
3105
3106	for (; it != it_end; ++ it)
3107	{
3108	ObjectPvs interPvs;
3109	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3110	ObjectPvs::Merge(interPvs, pvs, (*it)->GetPvs());
3111
3112	pvs = interPvs;
3113	}
3114	} else
3115	{
3116	PrVs prvs;
3117	AxisAlignedBox3 box = GetViewCellBox(viewCell);
3118
3119	// mViewCellsManager->SetMaxFilterSize(1);
3120	GetPrVS(box.Center(), prvs, viewSpaceFilterSize);
3121	pvs = prvs.mViewCell->GetPvs();
3122	DeleteLocalMergeTree(prvs.mViewCell);
3123	}
3124	}
3125	else
3126	{
3127	pvs = viewCell->GetPvs();
3128	}
3129
3130	if (spatialFilterSize >=0.0f)
3131	ApplySpatialFilter(kdTree, spatialFilterSize, pvs);
3132
3133	}
3134
3135
3136
3137	void
3138	ViewCellsManager::ApplyFilter(KdTree *kdTree,
3139	const float relViewSpaceFilterSize,
3140	const float relSpatialFilterSize
3141	)
3142	{
3143
3144	if (!ViewCellsConstructed())
3145	return;
3146
3147	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3148
3149	ObjectPvs *newPvs;
3150	newPvs = new ObjectPvs[mViewCells.size()];
3151
3152	float viewSpaceFilterSize = Magnitude(mViewSpaceBox.Size())*relViewSpaceFilterSize;
3153	float spatialFilterSize = Magnitude(kdTree->GetBox().Size())*relSpatialFilterSize;
3154
3155	int i;
3156	for (i=0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3157	ApplyFilter(*it,
3158	kdTree,
3159	viewSpaceFilterSize,
3160	spatialFilterSize,
3161	newPvs[i]
3162	);
3163	}
3164
3165	// now replace all pvss
3166	for (i = 0, it = mViewCells.begin(); it != it_end; ++ it, ++ i) {
3167
3168	ObjectPvs &pvs = (*it)->GetPvs();
3169	pvs.Clear();
3170	pvs = newPvs[i];
3171	newPvs[i].Clear();
3172	}
3173
3174	delete [] newPvs;
3175	}
3176
3177
3178	void
3179	ViewCellsManager::ApplySpatialFilter(
3180	KdTree *kdTree,
3181	const float spatialFilterSize,
3182	ObjectPvs &pvs
3183	)
3184	{
3185	// now compute a new Pvs by including also objects intersecting the
3186	// extended boxes of visible objects
3187	Intersectable::NewMail();
3188
3189	ObjectPvsIterator pit = pvs.GetIterator();
3190
3191	while (pit.HasMoreEntries())
3192	{
3193	ObjectPvsEntry entry = pit.Next();
3194
3195	Intersectable *object = entry.mObject;
3196	object->Mail();
3197	}
3198
3199	ObjectPvs nPvs;
3200	int nPvsSize = 0;
3201
3202	ObjectPvsIterator pit2 = pvs.GetIterator();
3203
3204	while (pit2.HasMoreEntries())
3205	{
3206	// now go through the pvs again
3207	ObjectPvsEntry entry = pit2.Next();
3208	Intersectable *object = entry.mObject;
3209
3210	// Vector3 center = object->GetBox().Center();
3211	// AxisAlignedBox3 box(center - Vector3(spatialFilterSize/2),
3212	// center + Vector3(spatialFilterSize/2));
3213
3214	AxisAlignedBox3 box = object->GetBox();
3215	box.Enlarge(Vector3(spatialFilterSize/2));
3216
3217	ObjectContainer objects;
3218
3219	// $$ warning collect objects takes only unmailed ones!
3220	kdTree->CollectObjects(box, objects);
3221	// cout<<"collected objects="<<objects.size()<<endl;
3222	ObjectContainer::const_iterator noi = objects.begin();
3223	for (; noi != objects.end(); ++ noi)
3224	{
3225	Intersectable o = noi;
3226
3227	// $$ JB warning: pdfs are not correct at this point!
3228	nPvs.AddSample(o, Limits::Small);
3229	nPvsSize ++;
3230	}
3231	}
3232
3233	// cout<<"nPvs size = "<<nPvsSize<<endl;
3234	pvs.MergeInPlace(nPvs);
3235	}
3236
3237
3238	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3239	const ViewCellContainer &viewCells) const
3240	{
3241	MergeViewCellsRecursivly(pvs, viewCells, 0, (int)viewCells.size() - 1);
3242	}
3243
3244
3245	void ViewCellsManager::MergeViewCellsRecursivly(ObjectPvs &pvs,
3246	const ViewCellContainer &viewCells,
3247	const int leftIdx,
3248	const int rightIdx) const
3249	{
3250	if (leftIdx == rightIdx)
3251	{
3252	pvs = viewCells[leftIdx]->GetPvs();
3253	}
3254	else
3255	{
3256	const int midSplit = (leftIdx + rightIdx) / 2;
3257
3258	ObjectPvs leftPvs, rightPvs;
3259	MergeViewCellsRecursivly(leftPvs, viewCells, leftIdx, midSplit);
3260	MergeViewCellsRecursivly(rightPvs, viewCells, midSplit, rightIdx);
3261
3262	ObjectPvs::Merge(pvs, leftPvs, rightPvs);
3263	}
3264	}
3265
3266
3267	PvsFilterStatistics
3268	ViewCellsManager::ApplyFilter2(ViewCell *viewCell,
3269	const bool useViewSpaceFilter,
3270	const float filterSize,
3271	ObjectPvs &pvs,
3272	vector<AxisAlignedBox3> *filteredBoxes
3273	)
3274	{
3275	PvsFilterStatistics stats;
3276
3277	AxisAlignedBox3 vbox = GetViewCellBox(viewCell);
3278	Vector3 center = vbox.Center();
3279	// copy the PVS
3280	Intersectable::NewMail();
3281	ObjectPvs basePvs = viewCell->GetPvs();
3282	ObjectPvsIterator pit = basePvs.GetIterator();
3283
3284	pvs.Reserve(viewCell->GetFilteredPvsSize());
3285
3286	if (!mUseKdPvs)
3287	{
3288	// first mark all objects from this pvs
3289	while (pit.HasMoreEntries())
3290	{
3291	ObjectPvsEntry entry = pit.Next();
3292	Intersectable *object = entry.mObject;
3293	object->Mail();
3294	}
3295	}
3296
3297	int pvsSize = 0;
3298	int nPvsSize = 0;
3299	float samples = (float)basePvs.GetSamples();
3300
3301	Debug<<"f #s="<<samples<<" pvs size = "<<basePvs.GetSize();
3302	// cout<<"Filter size = "<<filterSize<<endl;
3303	// cout<<"vbox = "<<vbox<<endl;
3304	// cout<<"center = "<<center<<endl;
3305
3306
3307	// Minimal number of local samples to take into account
3308	// the local sampling density.
3309	// The size of the filter is a minimum of the conservative
3310	// local sampling density estimate (#rays intersecting teh viewcell and
3311	// the object)
3312	// and gobal estimate for the view cell
3313	// (total #rays intersecting the viewcell)
3314	int minLocalSamples = 2;
3315
3316	float viewCellRadius = 0.5f*Magnitude(vbox.Diagonal());
3317
3318	// now compute the filter box around the current viewCell
3319
3320	if (useViewSpaceFilter) {
3321	// float radius = Max(viewCellRadius/100.0f, avgRadius - viewCellRadius);
3322	float radius = viewCellRadius/100.0f;
3323	vbox.Enlarge(radius);
3324	cout<<"vbox = "<<vbox<<endl;
3325	ViewCellContainer viewCells;
3326	ComputeBoxIntersections(vbox, viewCells);
3327
3328	ViewCellContainer::const_iterator it = viewCells.begin(),
3329	it_end = viewCells.end();
3330	int i = 0;
3331	for (i=0; it != it_end; ++ it, ++ i)
3332	if ((*it) != viewCell) {
3333	//cout<<"v"<<i<<" pvs="<<(*it)->GetPvs().mEntries.size()<<endl;
3334	basePvs.MergeInPlace((*it)->GetPvs());
3335	}
3336
3337	// update samples and globalC
3338	samples = (float)pvs.GetSamples();
3339	// cout<<"neighboring viewcells = "<<i-1<<endl;
3340	// cout<<"Samples' = "<<samples<<endl;
3341	}
3342
3343	// Minimal number of samples so that filtering takes place
3344	#define MIN_SAMPLES 50
3345
3346	if (samples > MIN_SAMPLES) {
3347	float globalC = 2.0f*filterSize/sqrt(samples);
3348
3349	pit = basePvs.GetIterator();
3350
3351	ObjectContainer objects;
3352
3353	while (pit.HasMoreEntries()) {
3354	ObjectPvsEntry entry = pit.Next();
3355
3356	Intersectable *object = entry.mObject;
3357	// compute filter size based on the distance and the numebr of samples
3358	AxisAlignedBox3 box = object->GetBox();
3359
3360	float distance = Distance(center, box.Center());
3361	float globalRadius = distance*globalC;
3362
3363	int objectSamples = (int)entry.mData.mSumPdf;
3364	float localRadius = MAX_FLOAT;
3365
3366	localRadius = filterSize0.5fMagnitude(box.Diagonal())/
3367	sqrt((float)objectSamples);
3368
3369	// cout<<"os="<<objectSamples<<" lr="<<localRadius<<" gr="<<globalRadius<<endl;
3370
3371	// now compute the filter size
3372	float radius;
3373
3374	#if 0
3375	if (objectSamples <= 1) {
3376	if (localRadius > globalRadius) {
3377	radius = 0.5flRadius;
3378	stats.mLocalFilterCount++;
3379	} else {
3380	radius = globalRadius;
3381	stats.mGlobalFilterCount++;
3382	}
3383	} else {
3384	radius = localRadius;
3385	stats.mLocalFilterCount++;
3386	}
3387	#else
3388	radius = 0.5fglobalRadius + 0.5flocalRadius;
3389
3390	if (localRadius > globalRadius)
3391	stats.mLocalFilterCount++;
3392	else
3393	stats.mGlobalFilterCount++;
3394	#endif
3395
3396	stats.mAvgFilterRadius += radius;
3397
3398	// cout<<"box = "<<box<<endl;
3399	// cout<<"distance = "<<distance<<endl;
3400	// cout<<"radiues = "<<radius<<endl;
3401
3402	box.Enlarge(Vector3(radius));
3403
3404	if (filteredBoxes)
3405	filteredBoxes->push_back(box);
3406
3407	objects.clear();
3408	// $$ warning collect objects takes only unmailed ones!
3409	if (mUseKdPvsAfterFiltering) {
3410	GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
3411	} else
3412	CollectObjects(box, objects);
3413
3414	// cout<<"collected objects="<<objects.size()<<endl;
3415	ObjectContainer::const_iterator noi = objects.begin();
3416	for (; noi != objects.end(); ++ noi) {
3417	Intersectable o = noi;
3418	// $$ JB warning: pdfs are not correct at this point!
3419	pvs.AddSampleDirty(o, Limits::Small);
3420	}
3421	}
3422	stats.mAvgFilterRadius /= (stats.mLocalFilterCount + stats.mGlobalFilterCount);
3423	}
3424
3425	Debug<<" nPvs size = "<<pvs.GetSize()<<endl;
3426
3427	if (!mUseKdPvs)
3428	{
3429	// copy the base pvs to the new pvs
3430	pit = basePvs.GetIterator();
3431	while (pit.HasMoreEntries())
3432	{
3433	ObjectPvsEntry entry = pit.Next();
3434	pvs.AddSampleDirty(entry.mObject, entry.mData.mSumPdf);
3435	}
3436	}
3437
3438	pvs.SimpleSort();
3439	viewCell->SetFilteredPvsSize(pvs.GetSize());
3440
3441	Intersectable::NewMail();
3442	return stats;
3443	}
3444
3445
3446
3447	void ViewCellsManager::ExportColor(Exporter *exporter,
3448	ViewCell *vc,
3449	bool colorCode) const
3450	{
3451	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3452
3453	float importance = 0;
3454	static Material m;
3455	//cout << "color code: " << colorCode << endl;
3456	switch (mColorCode)
3457	{
3458	case 0: // Random
3459	{
3460	if (vcValid)
3461	{
3462	m.mDiffuseColor.r = 0.2f + RandomValue(0.0f, 0.8f);
3463	m.mDiffuseColor.g = 0.2f + RandomValue(0.0f, 0.8f);
3464	m.mDiffuseColor.b = 0.2f + RandomValue(0.0f, 0.8f);
3465	}
3466	else
3467	{
3468	m.mDiffuseColor.r = 0.0f;
3469	m.mDiffuseColor.g = 1.0f;
3470	m.mDiffuseColor.b = 0.0f;
3471	}
3472
3473	exporter->SetForcedMaterial(m);
3474	return;
3475	}
3476
3477	case 1: // pvs
3478	{
3479	if (mCurrentViewCellsStats.maxPvs)
3480	{
3481	importance = (float)mViewCellsTree->GetPvsCost(vc) /
3482	(float)mCurrentViewCellsStats.maxPvs;
3483	}
3484	}
3485	break;
3486	case 2: // merges
3487	{
3488	const int lSize = mViewCellsTree->GetNumInitialViewCells(vc);
3489	importance = (float)lSize / (float)mCurrentViewCellsStats.maxLeaves;
3490	}
3491	break;
3492	#if 0
3493	case 3: // merge tree differene
3494	{
3495	importance = (float)GetMaxTreeDiff(vc) /
3496	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
3497
3498	}
3499	break;
3500	#endif
3501	default:
3502	break;
3503	}
3504
3505	// special color code for invalid view cells
3506	m.mDiffuseColor.r = importance;
3507	m.mDiffuseColor.b = 1.0f;//vcValid ? 0.0f : 1.0f;
3508	m.mDiffuseColor.g = 1.0f - importance;
3509
3510	//Debug << "importance: " << importance << endl;
3511	exporter->SetForcedMaterial(m);
3512	}
3513
3514
3515	void ViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3516	vector<MergeCandidate> &candidates)
3517	{
3518	// implemented in subclasses
3519	}
3520
3521
3522	void ViewCellsManager::UpdatePvsForEvaluation()
3523	{
3524	ObjectPvs objPvs;
3525	UpdatePvsForEvaluation(mViewCellsTree->GetRoot(), objPvs);
3526	}
3527
3528	void ViewCellsManager::UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs)
3529	{
3530	// terminate traversal
3531	if (root->IsLeaf())
3532	{
3533	//cout << "updating leaf" << endl;
3534	// we assume that pvs is explicitly stored in leaves
3535	pvs = root->GetPvs();
3536	UpdateScalarPvsSize(root, pvs.EvalPvsCost(), pvs.GetSize());
3537	return;
3538	}
3539
3540	////////////////
3541	//-- interior node => propagate pvs up the tree
3542
3543	ViewCellInterior interior = static_cast<ViewCellInterior >(root);
3544
3545	// reset interior pvs
3546	interior->GetPvs().Clear();
3547	// reset recursive pvs
3548	pvs.Clear();
3549
3550	// pvss of child nodes
3551	vector<ObjectPvs> pvsList;
3552	pvsList.resize((int)interior->mChildren.size());
3553
3554	ViewCellContainer::const_iterator vit, vit_end = interior->mChildren.end();
3555
3556	int i = 0;
3557
3558	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ i)
3559	{
3560	//////////////////
3561	//-- recursivly compute child pvss
3562	UpdatePvsForEvaluation(vit, pvsList[i]/objPvs*/);
3563	}
3564
3565	#if 1
3566	Intersectable::NewMail();
3567
3568	//-- faster way of computing pvs:
3569	//-- construct merged pvs by adding
3570	//-- and only those of the next pvs which were not mailed.
3571	//-- note: sumpdf is not correct!!
3572
3573	vector<ObjectPvs>::iterator oit = pvsList.begin();
3574
3575	for (vit = interior->mChildren.begin(); vit != vit_end; ++ vit, ++ oit)
3576	{
3577	ObjectPvsIterator pit = (*oit).GetIterator();
3578
3579	// first mark all object from this pvs
3580	while (pit.HasMoreEntries())
3581	{
3582	ObjectPvsEntry entry = pit.Next();
3583
3584	Intersectable *intersect = entry.mObject;
3585
3586	if (!intersect->Mailed())
3587	{
3588	pvs.AddSample(intersect, entry.mData.mSumPdf);
3589	intersect->Mail();
3590	}
3591	}
3592	}
3593
3594	// store pvs in this node
3595	if (mViewCellsTree->ViewCellsStorage() == ViewCellsTree::PVS_IN_INTERIORS)
3596	{
3597	interior->SetPvs(pvs);
3598	}
3599
3600	// set new pvs size
3601	UpdateScalarPvsSize(interior, pvs.EvalPvsCost(), pvs.GetSize());
3602
3603	#else
3604	// really merge cells: slow put sumPdf is correct
3605	viewCellInterior->GetPvs().Merge(backVc->GetPvs());
3606	viewCellInterior->GetPvs().Merge(frontVc->GetPvs());
3607	#endif
3608	}
3609
3610
3611
3612	/*******************************************************************/
3613	/* BspViewCellsManager implementation */
3614	/*******************************************************************/
3615
3616
3617	BspViewCellsManager::BspViewCellsManager(ViewCellsTree vcTree, BspTree bspTree):
3618	ViewCellsManager(vcTree), mBspTree(bspTree)
3619	{
3620	Environment::GetSingleton()->GetIntValue("BspTree.Construction.samples", mInitialSamples);
3621
3622	mBspTree->SetViewCellsManager(this);
3623	mBspTree->SetViewCellsTree(mViewCellsTree);
3624	}
3625
3626
3627	bool BspViewCellsManager::ViewCellsConstructed() const
3628	{
3629	return mBspTree->GetRoot() != NULL;
3630	}
3631
3632
3633	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
3634	{
3635	return new BspViewCell(mesh);
3636	}
3637
3638
3639	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
3640	const VssRayContainer &rays)
3641	{
3642	// if view cells were already constructed, we can finish
3643	if (ViewCellsConstructed())
3644	return 0;
3645
3646	int sampleContributions = 0;
3647
3648	// construct view cells using the collected samples
3649	RayContainer constructionRays;
3650	VssRayContainer savedRays;
3651
3652	// choose a a number of rays based on the ratio of cast rays / requested rays
3653	const int limit = min(mInitialSamples, (int)rays.size());
3654	VssRayContainer::const_iterator it, it_end = rays.end();
3655
3656	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
3657
3658	for (it = rays.begin(); it != it_end; ++ it)
3659	{
3660	if (Random(1.0f) < prop)
3661	constructionRays.push_back(new Ray((it)));
3662	else
3663	savedRays.push_back(*it);
3664	}
3665
3666	if (!mUsePredefinedViewCells)
3667	{
3668	// no view cells loaded
3669	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
3670	// collect final view cells
3671	mBspTree->CollectViewCells(mViewCells);
3672	}
3673	else
3674	{
3675	// use predefined view cells geometry =>
3676	// contruct bsp hierarchy over them
3677	mBspTree->Construct(mViewCells);
3678	}
3679
3680	// destroy rays created only for construction
3681	CLEAR_CONTAINER(constructionRays);
3682
3683	Debug << mBspTree->GetStatistics() << endl;
3684	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
3685
3686	// recast rest of the rays
3687	if (SAMPLE_AFTER_SUBDIVISION)
3688	ComputeSampleContributions(savedRays, true, false);
3689
3690	// real meshes are contructed at this stage
3691	if (0)
3692	{
3693	cout << "finalizing view cells ... ";
3694	FinalizeViewCells(true);
3695	cout << "finished" << endl;
3696	}
3697
3698	return sampleContributions;
3699	}
3700
3701
3702	void BspViewCellsManager::CollectViewCells()
3703	{
3704	if (!ViewCellsTreeConstructed())
3705	{ // view cells tree constructed
3706	mBspTree->CollectViewCells(mViewCells);
3707	}
3708	else
3709	{ // we can use the view cells tree hierarchy to get the right set
3710	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
3711	}
3712	}
3713
3714
3715	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
3716	{
3717	if (1)
3718	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
3719	else
3720	// compute view cell area as subsititute for probability
3721	return GetArea(viewCell) / GetAccVcArea();
3722	}
3723
3724
3725
3726	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
3727	const Vector3 &termination,
3728	ViewCellContainer &viewcells)
3729	{
3730	return mBspTree->CastLineSegment(origin, termination, viewcells);
3731	}
3732
3733
3734	bool BspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
3735	const Vector3 &termination,
3736	ViewCell *viewCell)
3737	{
3738	return false;
3739	}
3740
3741
3742	void ViewCellsManager::ExportMergedViewCells(const ObjectContainer &objects)
3743	{
3744	// save color code
3745	const int savedColorCode = mColorCode;
3746
3747	Exporter *exporter;
3748
3749	#if 0
3750	// export merged view cells
3751	mColorCode = 0; // use random colors
3752
3753	exporter = Exporter::GetExporter("merged_view_cells.wrl");
3754
3755	cout << "exporting view cells after merge ... ";
3756
3757	if (exporter)
3758	{
3759	if (mExportGeometry)
3760	{
3761	exporter->ExportGeometry(objects);
3762	}
3763
3764	exporter->SetFilled();
3765	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3766
3767	delete exporter;
3768	}
3769	cout << "finished" << endl;
3770	#endif
3771
3772	// export merged view cells using pvs color coding
3773	exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
3774	cout << "exporting view cells after merge (pvs size) ... ";
3775
3776	if (exporter)
3777	{
3778	if (mExportGeometry)
3779	{
3780	exporter->ExportGeometry(objects);
3781	}
3782
3783	exporter->SetFilled();
3784	mColorCode = 1;
3785
3786	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3787
3788	delete exporter;
3789	}
3790	cout << "finished" << endl;
3791
3792	mColorCode = savedColorCode;
3793	}
3794
3795
3796	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
3797	const VssRayContainer &rays)
3798	{
3799	if (!ViewCellsConstructed())
3800	{
3801	Debug << "view cells not constructed" << endl;
3802	return 0;
3803	}
3804
3805	// view cells already finished before post processing step,
3806	// i.e., because they were loaded from disc
3807	if (mViewCellsFinished)
3808	{
3809	FinalizeViewCells(true);
3810	EvaluateViewCellsStats();
3811
3812	return 0;
3813	}
3814
3815	//////////////////
3816	//-- merge leaves of the view cell hierarchy
3817
3818	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
3819	long startTime = GetTime();
3820
3821	VssRayContainer postProcessRays;
3822	GetRaySets(rays, mPostProcessSamples, postProcessRays);
3823
3824	if (mMergeViewCells)
3825	{
3826	cout << "constructing visibility based merge tree" << endl;
3827	mViewCellsTree->ConstructMergeTree(rays, objects);
3828	}
3829	else
3830	{
3831	cout << "constructing spatial merge tree" << endl;
3832	ViewCell *root;
3833	// the spatial merge tree is difficult to build for
3834	// this type of construction, as view cells cover several
3835	// leaves => create dummy tree which is only 2 levels deep
3836	if (mUsePredefinedViewCells)
3837	{
3838	root = ConstructDummyMergeTree(mBspTree->GetRoot());
3839	}
3840	else
3841	{
3842	// create spatial merge hierarchy
3843	root = ConstructSpatialMergeTree(mBspTree->GetRoot());
3844	}
3845
3846	mViewCellsTree->SetRoot(root);
3847
3848	// recompute pvs in the whole hierarchy
3849	ObjectPvs pvs;
3850	UpdatePvsForEvaluation(root, pvs);
3851	}
3852
3853	cout << "finished" << endl;
3854	cout << "merged view cells in "
3855	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
3856
3857	Debug << "Postprocessing: Merged view cells in "
3858	<< TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl << endl;
3859
3860
3861	////////////////////////
3862	//-- visualization and statistics after merge
3863
3864	if (1)
3865	{
3866	char mstats[100];
3867	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
3868	mViewCellsTree->ExportStats(mstats);
3869	}
3870
3871	// recompute view cells and stats
3872	ResetViewCells();
3873	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
3874
3875	// visualization of the view cells
3876	if (1) ExportMergedViewCells(objects);
3877
3878	// compute final meshes and volume / area
3879	if (1) FinalizeViewCells(true);
3880
3881	return 0;
3882	}
3883
3884
3885	BspViewCellsManager::~BspViewCellsManager()
3886	{
3887	}
3888
3889
3890	int BspViewCellsManager::GetType() const
3891	{
3892	return BSP;
3893	}
3894
3895
3896	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
3897	const VssRayContainer &sampleRays)
3898	{
3899	if (!ViewCellsConstructed())
3900	return;
3901
3902	const int savedColorCode = mColorCode;
3903
3904	if (1) // export final view cells
3905	{
3906	mColorCode = 1; // hack color code
3907	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
3908
3909	cout << "exporting view cells after merge (pvs size) ... ";
3910
3911	if (exporter)
3912	{
3913	if (mExportGeometry)
3914	{
3915	exporter->ExportGeometry(objects);
3916	}
3917
3918	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
3919	delete exporter;
3920	}
3921	cout << "finished" << endl;
3922	}
3923
3924	// reset color code
3925	mColorCode = savedColorCode;
3926
3927
3928	//////////////////
3929	//-- visualization of the BSP splits
3930
3931	bool exportSplits = false;
3932	Environment::GetSingleton()->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
3933
3934	if (exportSplits)
3935	{
3936	cout << "exporting splits ... ";
3937	ExportSplits(objects);
3938	cout << "finished" << endl;
3939	}
3940
3941	int leafOut;
3942	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
3943	const int raysOut = 100;
3944	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
3945	}
3946
3947
3948	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
3949	{
3950	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3951
3952	if (exporter)
3953	{
3954	//exporter->SetFilled();
3955	if (mExportGeometry)
3956	{
3957	exporter->ExportGeometry(objects);
3958	}
3959
3960	Material m;
3961	m.mDiffuseColor = RgbColor(1, 0, 0);
3962	exporter->SetForcedMaterial(m);
3963	exporter->SetWireframe();
3964
3965	exporter->ExportBspSplits(*mBspTree, true);
3966
3967	// NOTE: take forced material, else big scenes cannot be viewed
3968	m.mDiffuseColor = RgbColor(0, 1, 0);
3969	exporter->SetForcedMaterial(m);
3970	//exporter->ResetForcedMaterial();
3971
3972	delete exporter;
3973	}
3974	}
3975
3976
3977	void BspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
3978	const int maxViewCells,
3979	const bool sortViewCells,
3980	const bool exportPvs,
3981	const bool exportRays,
3982	const int maxRays,
3983	const string prefix,
3984	VssRayContainer *visRays)
3985	{
3986	if (sortViewCells)
3987	{ // sort view cells to visualize the largest view cells
3988	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
3989	}
3990
3991	//////////
3992	//-- some view cells for output
3993
3994	ViewCell::NewMail();
3995	const int limit = min(maxViewCells, (int)mViewCells.size());
3996
3997	for (int i = 0; i < limit; ++ i)
3998	{
3999	const int idx = sortViewCells ? (int)RandomValue(0, (float)mViewCells.size() - 0.5f) : i;
4000	ViewCell *vc = mViewCells[idx];
4001
4002	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
4003	continue;
4004
4005	vc->Mail();
4006
4007	ObjectPvs pvs;
4008	mViewCellsTree->GetPvs(vc, pvs);
4009
4010	char s[64]; sprintf(s, "%sviewcell-%04d.wrl", prefix.c_str(), i);
4011	Exporter *exporter = Exporter::GetExporter(s);
4012
4013	cout << "view cell " << idx << ": pvs cost=" << (int)mViewCellsTree->GetPvsCost(vc) << endl;
4014
4015	if (exportRays)
4016	{
4017	////////////
4018	//-- export rays piercing this view cell
4019
4020	// use rays stored with the view cells
4021	VssRayContainer vcRays, vcRays2, vcRays3;
4022	VssRayContainer collectRays;
4023
4024	// collect initial view cells
4025	ViewCellContainer leaves;
4026	mViewCellsTree->CollectLeaves(vc, leaves);
4027
4028	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
4029	for (vit = leaves.begin(); vit != vit_end; ++ vit)
4030	{
4031	// prepare some rays for output
4032	VssRayContainer::const_iterator rit, rit_end = (*vit)->GetOrCreateRays()->end();
4033	for (rit = (*vit)->GetOrCreateRays()->begin(); rit != rit_end; ++ rit)
4034	{
4035	collectRays.push_back(*rit);
4036	}
4037	}
4038
4039	const int raysOut = min((int)collectRays.size(), maxRays);
4040
4041	// prepare some rays for output
4042	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
4043	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
4044	{
4045	const float p = RandomValue(0.0f, (float)collectRays.size());
4046	if (p < raysOut)
4047	{
4048	if ((*rit)->mFlags & VssRay::BorderSample)
4049	{
4050	vcRays.push_back(*rit);
4051	}
4052	else if ((*rit)->mFlags & VssRay::ReverseSample)
4053	{
4054	vcRays2.push_back(*rit);
4055	}
4056	else
4057	{
4058	vcRays3.push_back(*rit);
4059	}
4060	}
4061	}
4062
4063	exporter->ExportRays(vcRays, RgbColor(1, 0, 0));
4064	exporter->ExportRays(vcRays2, RgbColor(0, 1, 0));
4065	exporter->ExportRays(vcRays3, RgbColor(1, 1, 1));
4066	}
4067
4068	////////////////
4069	//-- export view cell geometry
4070
4071	exporter->SetWireframe();
4072
4073	Material m;//= RandomMaterial();
4074	m.mDiffuseColor = RgbColor(0, 1, 0);
4075	exporter->SetForcedMaterial(m);
4076
4077	ExportViewCellGeometry(exporter, vc, NULL, NULL);
4078	exporter->SetFilled();
4079
4080	if (exportPvs)
4081	{
4082	Intersectable::NewMail();
4083	ObjectPvsIterator pit = pvs.GetIterator();
4084
4085	while (pit.HasMoreEntries())
4086	{
4087	ObjectPvsEntry entry = pit.Next();
4088
4089	// output PVS of view cell
4090	Intersectable *intersect = entry.mObject;
4091
4092	if (!intersect->Mailed())
4093	{
4094	intersect->Mail();
4095
4096	m = RandomMaterial();
4097	exporter->SetForcedMaterial(m);
4098	exporter->ExportIntersectable(intersect);
4099	}
4100	}
4101	cout << endl;
4102	}
4103
4104	DEL_PTR(exporter);
4105	cout << "finished" << endl;
4106	}
4107	}
4108
4109
4110	void BspViewCellsManager::TestSubdivision()
4111	{
4112	ViewCellContainer leaves;
4113	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
4114
4115	ViewCellContainer::const_iterator it, it_end = leaves.end();
4116
4117	const float vol = mViewSpaceBox.GetVolume();
4118	float subdivVol = 0;
4119	float newVol = 0;
4120
4121	for (it = leaves.begin(); it != it_end; ++ it)
4122	{
4123	BspNodeGeometry geom;
4124	mBspTree->ConstructGeometry(*it, geom);
4125
4126	const float lVol = geom.GetVolume();
4127	newVol += lVol;
4128	subdivVol += (*it)->GetVolume();
4129
4130	const float thres = 0.9f;
4131	if ((lVol < ((it)->GetVolume() thres)) \|\|
4132	(lVol * thres > ((*it)->GetVolume())))
4133	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
4134	}
4135
4136	Debug << "exact volume: " << vol << endl;
4137	Debug << "subdivision volume: " << subdivVol << endl;
4138	Debug << "new volume: " << newVol << endl;
4139	}
4140
4141
4142	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4143	ViewCell *vc,
4144	const AxisAlignedBox3 *sceneBox,
4145	const AxisAlignedPlane *clipPlane
4146	) const
4147	{
4148	if (clipPlane)
4149	{
4150	const Plane3 plane = clipPlane->GetPlane();
4151
4152	ViewCellContainer leaves;
4153	mViewCellsTree->CollectLeaves(vc, leaves);
4154	ViewCellContainer::const_iterator it, it_end = leaves.end();
4155
4156	for (it = leaves.begin(); it != it_end; ++ it)
4157	{
4158	BspNodeGeometry geom;
4159	BspNodeGeometry front;
4160	BspNodeGeometry back;
4161
4162	mBspTree->ConstructGeometry(*it, geom);
4163
4164	const float eps = 0.0001f;
4165	const int cf = geom.Side(plane, eps);
4166
4167	if (cf == -1)
4168	{
4169	exporter->ExportPolygons(geom.GetPolys());
4170	}
4171	else if (cf == 0)
4172	{
4173	geom.SplitGeometry(front,
4174	back,
4175	plane,
4176	mViewSpaceBox,
4177	eps);
4178
4179	if (back.Valid())
4180	{
4181	exporter->ExportPolygons(back.GetPolys());
4182	}
4183	}
4184	}
4185	}
4186	else
4187	{
4188	// export mesh if available
4189	// TODO: some bug here?
4190	if (1 && vc->GetMesh())
4191	{
4192	exporter->ExportMesh(vc->GetMesh());
4193	}
4194	else
4195	{
4196	BspNodeGeometry geom;
4197	mBspTree->ConstructGeometry(vc, geom);
4198	exporter->ExportPolygons(geom.GetPolys());
4199	}
4200	}
4201	}
4202
4203
4204	void BspViewCellsManager::CreateMesh(ViewCell *vc)
4205	{
4206	// note: should previous mesh be deleted (via mesh manager?)
4207	BspNodeGeometry geom;
4208	mBspTree->ConstructGeometry(vc, geom);
4209
4210	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
4211
4212	IncludeNodeGeomInMesh(geom, *mesh);
4213	mesh->ComputeBoundingBox();
4214
4215	vc->SetMesh(mesh);
4216	}
4217
4218
4219	void BspViewCellsManager::Finalize(ViewCell *viewCell,
4220	const bool createMesh)
4221	{
4222	float area = 0;
4223	float volume = 0;
4224
4225	ViewCellContainer leaves;
4226	mViewCellsTree->CollectLeaves(viewCell, leaves);
4227
4228	ViewCellContainer::const_iterator it, it_end = leaves.end();
4229
4230	for (it = leaves.begin(); it != it_end; ++ it)
4231	{
4232	BspNodeGeometry geom;
4233
4234	mBspTree->ConstructGeometry(*it, geom);
4235
4236	const float lVol = geom.GetVolume();
4237	const float lArea = geom.GetArea();
4238
4239	area += lArea;
4240	volume += lVol;
4241
4242	CreateMesh(*it);
4243	}
4244
4245	viewCell->SetVolume(volume);
4246	viewCell->SetArea(area);
4247	}
4248
4249
4250	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
4251	{
4252	if (!ViewCellsConstructed())
4253	{
4254	return NULL;
4255	}
4256	if (!mViewSpaceBox.IsInside(point))
4257	{
4258	return NULL;
4259	}
4260	return mBspTree->GetViewCell(point);
4261	}
4262
4263
4264	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4265	vector<MergeCandidate> &candidates)
4266	{
4267	cout << "collecting merge candidates ... " << endl;
4268
4269	if (mUseRaysForMerge)
4270	{
4271	mBspTree->CollectMergeCandidates(rays, candidates);
4272	}
4273	else
4274	{
4275	vector<BspLeaf *> leaves;
4276	mBspTree->CollectLeaves(leaves);
4277	mBspTree->CollectMergeCandidates(leaves, candidates);
4278	}
4279
4280	cout << "fininshed collecting candidates" << endl;
4281	}
4282
4283
4284
4285	bool BspViewCellsManager::ExportViewCells(const string filename,
4286	const bool exportPvs,
4287	const ObjectContainer &objects)
4288	{
4289	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
4290	{
4291	return false;
4292	}
4293
4294	cout << "exporting view cells to xml ... ";
4295
4296	OUT_STREAM stream(filename.c_str());
4297
4298	// for output we need unique ids for each view cell
4299	CreateUniqueViewCellIds();
4300
4301	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
4302	stream << "<VisibilitySolution>" << endl;
4303
4304	if (exportPvs)
4305	{
4306	//////////
4307	//-- export bounding boxes: they are used to identify the objects from the pvs and
4308	//-- assign them to the entities in the rendering engine
4309
4310	stream << "<BoundingBoxes>" << endl;
4311	ObjectContainer::const_iterator oit, oit_end = objects.end();
4312
4313	for (oit = objects.begin(); oit != oit_end; ++ oit)
4314	{
4315	const AxisAlignedBox3 box = (*oit)->GetBox();
4316
4317	stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
4318	<< " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
4319	<< " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
4320	}
4321
4322	stream << "</BoundingBoxes>" << endl;
4323	}
4324
4325	///////////
4326	//-- export the view cells and the pvs
4327
4328	const int numViewCells = mCurrentViewCellsStats.viewCells;
4329	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
4330
4331	mViewCellsTree->Export(stream, exportPvs);
4332
4333	stream << "</ViewCells>" << endl;
4334
4335	/////////////
4336	//-- export the view space hierarchy
4337	stream << "<ViewSpaceHierarchy type=\"bsp\""
4338	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
4339	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
4340
4341	mBspTree->Export(stream);
4342
4343	// end tags
4344	stream << "</ViewSpaceHierarchy>" << endl;
4345	stream << "</VisibilitySolution>" << endl;
4346
4347	stream.close();
4348	cout << "finished" << endl;
4349
4350	return true;
4351	}
4352
4353
4354	ViewCell BspViewCellsManager::ConstructDummyMergeTree(BspNode root)
4355	{
4356	ViewCellInterior *vcRoot = new ViewCellInterior();
4357
4358	// evaluate merge cost for priority traversal
4359	const float mergeCost = -(float)root->mTimeStamp;
4360	vcRoot->SetMergeCost(mergeCost);
4361
4362	float volume = 0;
4363	vector<BspLeaf *> leaves;
4364	mBspTree->CollectLeaves(leaves);
4365	vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
4366	ViewCell::NewMail();
4367
4368	for (lit = leaves.begin(); lit != lit_end; ++ lit)
4369	{
4370	BspLeaf leaf = lit;
4371	ViewCell *vc = leaf->GetViewCell();
4372
4373	if (!vc->Mailed())
4374	{
4375	vc->Mail();
4376	vc->SetMergeCost(0.0f);
4377	vcRoot->SetupChildLink(vc);
4378
4379	volume += vc->GetVolume();
4380	volume += vc->GetVolume();
4381	vcRoot->SetVolume(volume);
4382	}
4383	}
4384
4385	return vcRoot;
4386	}
4387
4388
4389	ViewCell BspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
4390	{
4391	// terminate recursion
4392	if (root->IsLeaf())
4393	{
4394	BspLeaf leaf = static_cast<BspLeaf >(root);
4395	leaf->GetViewCell()->SetMergeCost(0.0f);
4396	return leaf->GetViewCell();
4397	}
4398
4399	BspInterior interior = static_cast<BspInterior >(root);
4400	ViewCellInterior *viewCellInterior = new ViewCellInterior();
4401
4402	// evaluate merge cost for priority traversal
4403	const float mergeCost = -(float)root->mTimeStamp;
4404	viewCellInterior->SetMergeCost(mergeCost);
4405
4406	float volume = 0;
4407
4408	BspNode *front = interior->GetFront();
4409	BspNode *back = interior->GetBack();
4410
4411
4412	////////////
4413	//-- recursivly compute child hierarchies
4414
4415	ViewCell *backVc = ConstructSpatialMergeTree(back);
4416	ViewCell *frontVc = ConstructSpatialMergeTree(front);
4417
4418	viewCellInterior->SetupChildLink(backVc);
4419	viewCellInterior->SetupChildLink(frontVc);
4420
4421	volume += backVc->GetVolume();
4422	volume += frontVc->GetVolume();
4423
4424	viewCellInterior->SetVolume(volume);
4425
4426	return viewCellInterior;
4427	}
4428
4429
4430	/************************************************************************/
4431	/* KdViewCellsManager implementation */
4432	/************************************************************************/
4433
4434
4435
4436	KdViewCellsManager::KdViewCellsManager(ViewCellsTree vcTree, KdTree kdTree):
4437	ViewCellsManager(vcTree), mKdTree(kdTree), mKdPvsDepth(100)
4438	{
4439	}
4440
4441
4442	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
4443	{
4444	// compute view cell area / volume as subsititute for probability
4445	if (0)
4446	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
4447	else
4448	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
4449	}
4450
4451
4452
4453
4454	void KdViewCellsManager::CollectViewCells()
4455	{
4456	//mKdTree->CollectViewCells(mViewCells); TODO
4457	}
4458
4459
4460	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4461	const VssRayContainer &rays)
4462	{
4463	// if view cells already constructed
4464	if (ViewCellsConstructed())
4465	return 0;
4466
4467	mKdTree->Construct();
4468
4469	mTotalAreaValid = false;
4470	// create the view cells
4471	mKdTree->CreateAndCollectViewCells(mViewCells);
4472	// cast rays
4473	ComputeSampleContributions(rays, true, false);
4474
4475	EvaluateViewCellsStats();
4476	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4477
4478	return 0;
4479	}
4480
4481
4482	bool KdViewCellsManager::ViewCellsConstructed() const
4483	{
4484	return mKdTree->GetRoot() != NULL;
4485	}
4486
4487
4488	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
4489	const VssRayContainer &rays)
4490	{
4491	return 0;
4492	}
4493
4494
4495	void KdViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
4496	const int maxViewCells,
4497	const bool sortViewCells,
4498	const bool exportPvs,
4499	const bool exportRays,
4500	const int maxRays,
4501	const string prefix,
4502	VssRayContainer *visRays)
4503	{
4504	// TODO
4505	}
4506
4507
4508	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
4509	const VssRayContainer &sampleRays)
4510	{
4511	if (!ViewCellsConstructed())
4512	return;
4513
4514	// using view cells instead of the kd PVS of objects
4515	const bool useViewCells = true;
4516	bool exportRays = false;
4517
4518	int limit = min(mVisualizationSamples, (int)sampleRays.size());
4519	const int pvsOut = min((int)objects.size(), 10);
4520	VssRayContainer *rays = new VssRayContainer[pvsOut];
4521
4522	if (useViewCells)
4523	{
4524	const int leafOut = 10;
4525
4526	ViewCell::NewMail();
4527
4528	//-- some rays for output
4529	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
4530	Debug << "visualization using " << raysOut << " samples" << endl;
4531
4532	//-- some random view cells and rays for output
4533	vector<KdLeaf *> kdLeaves;
4534
4535	for (int i = 0; i < leafOut; ++ i)
4536	kdLeaves.push_back(static_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
4537
4538	for (int i = 0; i < kdLeaves.size(); ++ i)
4539	{
4540	KdLeaf *leaf = kdLeaves[i];
4541	RayContainer vcRays;
4542
4543	cout << "creating output for view cell " << i << " ... ";
4544	#if 0
4545	// check whether we can add the current ray to the output rays
4546	for (int k = 0; k < raysOut; ++ k)
4547	{
4548	Ray *ray = sampleRays[k];
4549
4550	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
4551	{
4552	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
4553
4554	if (leaf->GetViewCell() == leaf2->GetViewCell())
4555	{
4556	vcRays.push_back(ray);
4557	}
4558	}
4559	}
4560	#endif
4561	Intersectable::NewMail();
4562
4563	ViewCell *vc = leaf->mViewCell;
4564	char str[64]; sprintf(str, "viewcell%04d.wrl", i);
4565
4566	Exporter *exporter = Exporter::GetExporter(str);
4567	exporter->SetFilled();
4568
4569	exporter->SetWireframe();
4570	//exporter->SetFilled();
4571
4572	Material m;//= RandomMaterial();
4573	m.mDiffuseColor = RgbColor(1, 1, 0);
4574	exporter->SetForcedMaterial(m);
4575
4576	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
4577	exporter->ExportBox(box);
4578
4579	// export rays piercing this view cell
4580	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
4581
4582	m.mDiffuseColor = RgbColor(1, 0, 0);
4583	exporter->SetForcedMaterial(m);
4584
4585	// exporter->SetWireframe();
4586	exporter->SetFilled();
4587
4588	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
4589
4590	while (pit.HasMoreEntries())
4591	{
4592	ObjectPvsEntry entry = pit.Next();
4593
4594	//-- output PVS of view cell
4595	Intersectable *intersect = entry.mObject;
4596	if (!intersect->Mailed())
4597	{
4598	exporter->ExportIntersectable(intersect);
4599	intersect->Mail();
4600	}
4601	}
4602
4603	DEL_PTR(exporter);
4604	cout << "finished" << endl;
4605	}
4606
4607	DEL_PTR(rays);
4608	}
4609	else // using kd PVS of objects
4610	{
4611	for (int i = 0; i < limit; ++ i)
4612	{
4613	VssRay *ray = sampleRays[i];
4614
4615	// check whether we can add this to the rays
4616	for (int j = 0; j < pvsOut; j++)
4617	{
4618	if (objects[j] == ray->mTerminationObject)
4619	{
4620	rays[j].push_back(ray);
4621	}
4622	}
4623	}
4624
4625	if (exportRays)
4626	{
4627	Exporter *exporter = NULL;
4628	exporter = Exporter::GetExporter("sample-rays.x3d");
4629	exporter->SetWireframe();
4630	exporter->ExportKdTree(*mKdTree);
4631
4632	for (int i = 0; i < pvsOut; i++)
4633	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
4634
4635	exporter->SetFilled();
4636	delete exporter;
4637	}
4638
4639	for (int k=0; k < pvsOut; k++)
4640	{
4641	Intersectable *object = objects[k];
4642	char str[64]; sprintf(str, "viewcell%04d.wrl", k);
4643
4644	Exporter *exporter = Exporter::GetExporter(str);
4645	exporter->SetWireframe();
4646
4647	// matt: we don't have no kd pvs
4648	#if 0
4649	KdPvsMap::iterator kit = object->mKdPvs.mEntries.begin();
4650	Intersectable::NewMail();
4651
4652	// avoid adding the object to the list
4653	object->Mail();
4654	ObjectContainer visibleObjects;
4655
4656	for (; kit != object->mKdPvs.mEntries.end(); i++)
4657	{
4658	KdNode node = (kit).first;
4659	exporter->ExportBox(mKdTree->GetBox(node));
4660
4661	mKdTree->CollectObjects(node, visibleObjects);
4662	}
4663
4664	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
4665	exporter->SetFilled();
4666
4667	for (int j = 0; j < visibleObjects.size(); j++)
4668	exporter->ExportIntersectable(visibleObjects[j]);
4669
4670	Material m;
4671	m.mDiffuseColor = RgbColor(1, 0, 0);
4672	exporter->SetForcedMaterial(m);
4673	exporter->ExportIntersectable(object);
4674	#endif
4675	delete exporter;
4676	}
4677	}
4678	}
4679
4680
4681	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
4682	{
4683	return new KdViewCell(mesh);
4684	}
4685
4686
4687	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
4688	ViewCell *vc,
4689	const AxisAlignedBox3 *sceneBox,
4690	const AxisAlignedPlane *clipPlane
4691	) const
4692	{
4693	ViewCellContainer leaves;
4694	mViewCellsTree->CollectLeaves(vc, leaves);
4695	ViewCellContainer::const_iterator it, it_end = leaves.end();
4696
4697	for (it = leaves.begin(); it != it_end; ++ it)
4698	{
4699	KdViewCell kdVc = static_cast<KdViewCell >(*it);
4700	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaves[0]));
4701	}
4702	}
4703
4704
4705	int KdViewCellsManager::GetType() const
4706	{
4707	return ViewCellsManager::KD;
4708	}
4709
4710
4711
4712	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
4713	{
4714	KdNode *node = leaf;
4715
4716	while (node->mParent && node->mDepth > mKdPvsDepth)
4717	node = node->mParent;
4718
4719	return node;
4720	}
4721
4722	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
4723	const Vector3 &termination,
4724	ViewCellContainer &viewcells)
4725	{
4726	return mKdTree->CastLineSegment(origin, termination, viewcells);
4727	}
4728
4729
4730	bool KdViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
4731	const Vector3 &termination,
4732	ViewCell *viewCell)
4733	{
4734	return false;
4735	}
4736
4737
4738	void KdViewCellsManager::CreateMesh(ViewCell *vc)
4739	{
4740	// TODO
4741	}
4742
4743
4744
4745	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4746	vector<MergeCandidate> &candidates)
4747	{
4748	// TODO
4749	}
4750
4751
4752
4753	/**************************************************************************/
4754	/* VspBspViewCellsManager implementation */
4755	/**************************************************************************/
4756
4757
4758	VspBspViewCellsManager::VspBspViewCellsManager(ViewCellsTree vcTree, VspBspTree vspBspTree):
4759	ViewCellsManager(vcTree), mVspBspTree(vspBspTree)
4760	{
4761	Environment::GetSingleton()->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
4762	mVspBspTree->SetViewCellsManager(this);
4763	mVspBspTree->mViewCellsTree = mViewCellsTree;
4764	}
4765
4766
4767	VspBspViewCellsManager::~VspBspViewCellsManager()
4768	{
4769	}
4770
4771
4772	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
4773	{
4774	if (0 && mVspBspTree->mUseAreaForPvs)
4775	return GetArea(viewCell) / GetAccVcArea();
4776	else
4777	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
4778	}
4779
4780
4781	void VspBspViewCellsManager::CollectViewCells()
4782	{
4783	// view cells tree constructed?
4784	if (!ViewCellsTreeConstructed())
4785	{
4786	mVspBspTree->CollectViewCells(mViewCells, false);
4787	}
4788	else
4789	{
4790	// we can use the view cells tree hierarchy to get the right set
4791	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
4792	}
4793	}
4794
4795
4796	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
4797	vector<MergeCandidate> &candidates)
4798	{
4799	cout << "collecting merge candidates ... " << endl;
4800
4801	if (mUseRaysForMerge)
4802	{
4803	mVspBspTree->CollectMergeCandidates(rays, candidates);
4804	}
4805	else
4806	{
4807	vector<BspLeaf *> leaves;
4808	mVspBspTree->CollectLeaves(leaves);
4809
4810	mVspBspTree->CollectMergeCandidates(leaves, candidates);
4811	}
4812
4813	cout << "fininshed collecting candidates" << endl;
4814	}
4815
4816
4817	bool VspBspViewCellsManager::ViewCellsConstructed() const
4818	{
4819	return mVspBspTree->GetRoot() != NULL;
4820	}
4821
4822
4823	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
4824	{
4825	return new BspViewCell(mesh);
4826	}
4827
4828
4829	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
4830	const VssRayContainer &rays)
4831	{
4832	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
4833
4834	// if view cells were already constructed
4835	if (ViewCellsConstructed())
4836	{
4837	return 0;
4838	}
4839
4840	int sampleContributions = 0;
4841	VssRayContainer sampleRays;
4842
4843	const int limit = min(mInitialSamples, (int)rays.size());
4844
4845	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
4846	<< ", actual rays: " << (int)rays.size() << endl;
4847
4848	VssRayContainer savedRays;
4849
4850	if (SAMPLE_AFTER_SUBDIVISION)
4851	{
4852	VssRayContainer constructionRays;
4853
4854	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
4855
4856	Debug << "rays used for initial construction: " << (int)constructionRays.size() << endl;
4857	Debug << "rays saved for later use: " << (int)savedRays.size() << endl;
4858
4859	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
4860	}
4861	else
4862	{
4863	Debug << "rays used for initial construction: " << (int)rays.size() << endl;
4864	mVspBspTree->Construct(rays, &mViewSpaceBox);
4865	}
4866
4867	// collapse invalid regions
4868	cout << "collapsing invalid tree regions ... ";
4869	long startTime = GetTime();
4870
4871	const int collapsedLeaves = mVspBspTree->CollapseTree();
4872	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
4873	<< " seconds" << endl;
4874
4875	cout << "finished" << endl;
4876
4877	/////////////////
4878	//-- stats after construction
4879
4880	Debug << mVspBspTree->GetStatistics() << endl;
4881
4882	ResetViewCells();
4883	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
4884
4885
4886	//////////////////////
4887	//-- recast the rest of the rays
4888
4889	startTime = GetTime();
4890
4891	cout << "Computing remaining ray contributions ... ";
4892
4893	if (SAMPLE_AFTER_SUBDIVISION)
4894	ComputeSampleContributions(savedRays, true, false);
4895
4896	cout << "finished" << endl;
4897
4898	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
4899	<< " secs" << endl;
4900
4901	cout << "construction finished" << endl;
4902
4903	if (0)
4904	{ ////////
4905	//-- real meshes are contructed at this stage
4906
4907	cout << "finalizing view cells ... ";
4908	FinalizeViewCells(true);
4909	cout << "finished" << endl;
4910	}
4911
4912	return sampleContributions;
4913	}
4914
4915
4916	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
4917	const ObjectContainer &objects)
4918	{
4919	int vcSize = 0;
4920	int pvsSize = 0;
4921
4922	//-- merge view cells
4923	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
4924	long startTime = GetTime();
4925
4926
4927	if (mMergeViewCells)
4928	{
4929	// TODO: should be done BEFORE the ray casting
4930	// compute tree by merging the nodes based on cost heuristics
4931	mViewCellsTree->ConstructMergeTree(rays, objects);
4932	}
4933	else
4934	{
4935	// compute tree by merging the nodes of the spatial hierarchy
4936	ViewCell *root = ConstructSpatialMergeTree(mVspBspTree->GetRoot());
4937	mViewCellsTree->SetRoot(root);
4938
4939	// compute pvs
4940	ObjectPvs pvs;
4941	UpdatePvsForEvaluation(root, pvs);
4942	}
4943
4944	if (1)
4945	{
4946	char mstats[100];
4947	ObjectPvs pvs;
4948
4949	Environment::GetSingleton()->GetStringValue("ViewCells.mergeStats", mstats);
4950	mViewCellsTree->ExportStats(mstats);
4951	}
4952
4953	cout << "merged view cells in "
4954	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
4955
4956	Debug << "Postprocessing: Merged view cells in "
4957	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
4958
4959
4960	//////////////////
4961	//-- stats and visualizations
4962
4963	int savedColorCode = mColorCode;
4964
4965	// get currently active view cell set
4966	ResetViewCells();
4967	Debug << "\nView cells after merge:\n" << mCurrentViewCellsStats << endl;
4968
4969	if (mShowVisualization) // export merged view cells
4970	{
4971	mColorCode = 0;
4972	Exporter *exporter = Exporter::GetExporter("merged_view_cells.wrl");
4973
4974	cout << "exporting view cells after merge ... ";
4975
4976	if (exporter)
4977	{
4978	if (0)
4979	exporter->SetWireframe();
4980	else
4981	exporter->SetFilled();
4982
4983	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
4984
4985	if (mExportGeometry)
4986	{
4987	Material m;
4988	m.mDiffuseColor = RgbColor(0, 1, 0);
4989	exporter->SetForcedMaterial(m);
4990	exporter->SetFilled();
4991
4992	exporter->ExportGeometry(objects);
4993	}
4994
4995	delete exporter;
4996	}
4997	cout << "finished" << endl;
4998	}
4999
5000	if (mShowVisualization)
5001	{
5002	// use pvs size for color coding
5003	mColorCode = 1;
5004	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.wrl");
5005
5006	cout << "exporting view cells after merge (pvs size) ... ";
5007
5008	if (exporter)
5009	{
5010	exporter->SetFilled();
5011
5012	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5013
5014	if (mExportGeometry)
5015	{
5016	Material m;
5017	m.mDiffuseColor = RgbColor(0, 1, 0);
5018	exporter->SetForcedMaterial(m);
5019	exporter->SetFilled();
5020
5021	exporter->ExportGeometry(objects);
5022	}
5023
5024	delete exporter;
5025	}
5026	cout << "finished" << endl;
5027	}
5028
5029	mColorCode = savedColorCode;
5030	}
5031
5032
5033	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
5034	const ObjectContainer &objects)
5035	{
5036	mRenderer->RenderScene();
5037
5038	SimulationStatistics ss;
5039	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5040	Debug << "render time before refine\n\n" << ss << endl;
5041
5042	const long startTime = GetTime();
5043	cout << "Refining the merged view cells ... ";
5044
5045	// refining the merged view cells
5046	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
5047
5048	//-- stats and visualizations
5049	cout << "finished" << endl;
5050	cout << "refined " << refined << " view cells in "
5051	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
5052
5053	Debug << "Postprocessing: refined " << refined << " view cells in "
5054	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
5055	}
5056
5057
5058	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
5059	const VssRayContainer &rays)
5060	{
5061	if (!ViewCellsConstructed())
5062	{
5063	Debug << "postprocess error: no view cells constructed" << endl;
5064	return 0;
5065	}
5066
5067	// view cells already finished before post processing step
5068	// (i.e. because they were loaded)
5069	if (mViewCellsFinished)
5070	{
5071	FinalizeViewCells(true);
5072	EvaluateViewCellsStats();
5073
5074	return 0;
5075	}
5076
5077	// check if new view cells turned invalid
5078	int minPvs, maxPvs;
5079
5080	if (0)
5081	{
5082	minPvs = mMinPvsSize;
5083	maxPvs = mMaxPvsSize;
5084	}
5085	else
5086	{
5087	// problem matt: why did I start here from zero?
5088	minPvs = 0;
5089	maxPvs = mMaxPvsSize;
5090	}
5091
5092	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5093	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
5094
5095	SetValidity(minPvs, maxPvs);
5096
5097	// update valid view space according to valid view cells
5098	if (0) mVspBspTree->ValidateTree();
5099
5100	// area has to be recomputed
5101	mTotalAreaValid = false;
5102	VssRayContainer postProcessRays;
5103	GetRaySets(rays, mPostProcessSamples, postProcessRays);
5104
5105	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
5106
5107	//////////
5108	//-- merge neighbouring view cells
5109	MergeViewCells(postProcessRays, objects);
5110
5111	// refines the merged view cells
5112	if (0) RefineViewCells(postProcessRays, objects);
5113
5114
5115	///////////
5116	//-- render simulation after merge + refine
5117
5118	cout << "\nview cells partition render time before compress" << endl << endl;;
5119	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
5120	SimulationStatistics ss;
5121	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
5122	cout << ss << endl;
5123
5124	if (0) CompressViewCells();
5125
5126	// collapse sibling leaves that share the same view cell
5127	if (0) mVspBspTree->CollapseTree();
5128
5129	// recompute view cell list and statistics
5130	ResetViewCells();
5131
5132	// compute final meshes and volume / area
5133	if (1) FinalizeViewCells(true);
5134
5135	return 0;
5136	}
5137
5138
5139	int VspBspViewCellsManager::GetType() const
5140	{
5141	return VSP_BSP;
5142	}
5143
5144
5145	ViewCell VspBspViewCellsManager::ConstructSpatialMergeTree(BspNode root)
5146	{
5147	// terminate recursion
5148	if (root->IsLeaf())
5149	{
5150	BspLeaf leaf = static_cast<BspLeaf >(root);
5151	leaf->GetViewCell()->SetMergeCost(0.0f);
5152	return leaf->GetViewCell();
5153	}
5154
5155
5156	BspInterior interior = static_cast<BspInterior >(root);
5157	ViewCellInterior *viewCellInterior = new ViewCellInterior();
5158
5159	// evaluate merge cost for priority traversal
5160	float mergeCost = 1.0f / (float)root->mTimeStamp;
5161	viewCellInterior->SetMergeCost(mergeCost);
5162
5163	float volume = 0;
5164
5165	BspNode *front = interior->GetFront();
5166	BspNode *back = interior->GetBack();
5167
5168
5169	ObjectPvs frontPvs, backPvs;
5170
5171	//-- recursivly compute child hierarchies
5172	ViewCell *backVc = ConstructSpatialMergeTree(back);
5173	ViewCell *frontVc = ConstructSpatialMergeTree(front);
5174
5175
5176	viewCellInterior->SetupChildLink(backVc);
5177	viewCellInterior->SetupChildLink(frontVc);
5178
5179	volume += backVc->GetVolume();
5180	volume += frontVc->GetVolume();
5181
5182	viewCellInterior->SetVolume(volume);
5183
5184	return viewCellInterior;
5185	}
5186
5187
5188	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
5189	{
5190	if (!ViewCellsConstructed())
5191	return ViewCellsManager::GetViewPoint(viewPoint);
5192
5193	// TODO: set reasonable limit
5194	const int limit = 20;
5195
5196	for (int i = 0; i < limit; ++ i)
5197	{
5198	viewPoint = mViewSpaceBox.GetRandomPoint();
5199	if (mVspBspTree->ViewPointValid(viewPoint))
5200	{
5201	return true;
5202	}
5203	}
5204
5205	Debug << "failed to find valid view point, taking " << viewPoint << endl;
5206	return false;
5207	}
5208
5209
5210	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
5211	{
5212	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
5213	// validy update in preprocessor for all managers)
5214	return ViewCellsManager::ViewPointValid(viewPoint);
5215
5216	// return mViewSpaceBox.IsInside(viewPoint) &&
5217	// mVspBspTree->ViewPointValid(viewPoint);
5218	}
5219
5220
5221	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
5222	const VssRayContainer &sampleRays)
5223	{
5224	if (!ViewCellsConstructed())
5225	return;
5226
5227	VssRayContainer visRays;
5228	GetRaySets(sampleRays, mVisualizationSamples, visRays);
5229
5230	if (1)
5231	{
5232	//////////////////
5233	//-- export final view cell partition
5234
5235	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
5236
5237	if (exporter)
5238	{
5239	cout << "exporting view cells after post process ... ";
5240	if (0)
5241	{ // export view space box
5242	exporter->SetWireframe();
5243	exporter->ExportBox(mViewSpaceBox);
5244	exporter->SetFilled();
5245	}
5246
5247	Material m;
5248	m.mDiffuseColor.r = 0.0f;
5249	m.mDiffuseColor.g = 0.5f;
5250	m.mDiffuseColor.b = 0.5f;
5251
5252	exporter->SetForcedMaterial(m);
5253
5254	if (1 && mExportGeometry)
5255	{
5256	exporter->ExportGeometry(objects);
5257	}
5258
5259	if (0 && mExportRays)
5260	{
5261	exporter->ExportRays(visRays, RgbColor(1, 0, 0));
5262	}
5263	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
5264
5265	delete exporter;
5266	cout << "finished" << endl;
5267	}
5268	}
5269
5270	////////////////
5271	//-- visualization of the BSP splits
5272
5273	bool exportSplits = false;
5274	Environment::GetSingleton()->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
5275
5276	if (exportSplits)
5277	{
5278	cout << "exporting splits ... ";
5279	ExportSplits(objects, visRays);
5280	cout << "finished" << endl;
5281	}
5282
5283	////////
5284	//-- export single view cells
5285
5286	int leafOut;
5287	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
5288	const int raysOut = 100;
5289
5290	ExportSingleViewCells(objects, leafOut, false, true, false, raysOut, "");
5291	}
5292
5293
5294	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
5295	const VssRayContainer &rays)
5296	{
5297	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
5298
5299	if (exporter)
5300	{
5301	Material m;
5302	m.mDiffuseColor = RgbColor(1, 0, 0);
5303	exporter->SetForcedMaterial(m);
5304	exporter->SetWireframe();
5305
5306	exporter->ExportBspSplits(*mVspBspTree, true);
5307
5308	// take forced material, else big scenes cannot be viewed
5309	m.mDiffuseColor = RgbColor(0, 1, 0);
5310	exporter->SetForcedMaterial(m);
5311	exporter->SetFilled();
5312
5313	exporter->ResetForcedMaterial();
5314
5315	// export rays
5316	if (mExportRays)
5317	{
5318	exporter->ExportRays(rays, RgbColor(1, 1, 0));
5319	}
5320
5321	if (mExportGeometry)
5322	{
5323	exporter->ExportGeometry(objects);
5324	}
5325	delete exporter;
5326	}
5327	}
5328
5329
5330	void VspBspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
5331	const int maxViewCells,
5332	const bool sortViewCells,
5333	const bool exportPvs,
5334	const bool exportRays,
5335	const int maxRays,
5336	const string prefix,
5337	VssRayContainer *visRays)
5338	{
5339	if (sortViewCells)
5340	{
5341	// sort view cells to visualize the largest view cells
5342	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
5343	}
5344
5345	//////////
5346	//-- some view cells for output
5347
5348	ViewCell::NewMail();
5349	const int limit = min(maxViewCells, (int)mViewCells.size());
5350
5351	for (int i = 0; i < limit; ++ i)
5352	{
5353	cout << "creating output for view cell " << i << " ... ";
5354
5355	ViewCell *vc = sortViewCells ? // largest view cell pvs first?
5356	mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 0.5f)] : mViewCells[i];
5357
5358	if (vc->Mailed() \|\| vc->GetId() == OUT_OF_BOUNDS_ID)
5359	continue;
5360
5361	vc->Mail();
5362
5363	ObjectPvs pvs;
5364	mViewCellsTree->GetPvs(vc, pvs);
5365
5366	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
5367	Exporter *exporter = Exporter::GetExporter(s);
5368
5369	const float pvsCost = mViewCellsTree->GetPvsCost(vc);
5370	cout << "view cell " << vc->GetId() << ": pvs cost=" << pvsCost << endl;
5371
5372	if (exportRays)
5373	{
5374	////////////
5375	//-- export rays piercing this view cell
5376
5377	// take rays stored with the view cells during subdivision
5378	VssRayContainer vcRays;
5379	VssRayContainer collectRays;
5380
5381	// collect initial view cells
5382	ViewCellContainer leaves;
5383	mViewCellsTree->CollectLeaves(vc, leaves);
5384
5385	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
5386	for (vit = leaves.begin(); vit != vit_end; ++ vit)
5387	{
5388	BspLeaf vcLeaf = static_cast<BspViewCell >(*vit)->mLeaves[0];
5389	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
5390
5391	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
5392	{
5393	collectRays.push_back(*rit);
5394	}
5395	}
5396
5397	const int raysOut = min((int)collectRays.size(), maxRays);
5398
5399	// prepare some rays for output
5400	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
5401	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
5402	{
5403	const float p = RandomValue(0.0f, (float)collectRays.size());
5404
5405	if (p < raysOut)
5406	{
5407	vcRays.push_back(*rit);
5408	}
5409	}
5410
5411	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
5412	}
5413
5414	////////////////
5415	//-- export view cell geometry
5416
5417	exporter->SetWireframe();
5418
5419	Material m;//= RandomMaterial();
5420	m.mDiffuseColor = RgbColor(0, 1, 0);
5421	exporter->SetForcedMaterial(m);
5422
5423	ExportViewCellGeometry(exporter, vc, NULL, NULL);
5424	exporter->SetFilled();
5425
5426	if (exportPvs)
5427	{
5428	Intersectable::NewMail();
5429
5430	ObjectPvsIterator pit = pvs.GetIterator();
5431
5432	cout << endl;
5433
5434	// output PVS of view cell
5435	while (pit.HasMoreEntries())
5436	{
5437	ObjectPvsEntry entry = pit.Next();
5438	Intersectable *intersect = entry.mObject;
5439
5440	if (!intersect->Mailed())
5441	{
5442	intersect->Mail();
5443
5444	m = RandomMaterial();
5445	exporter->SetForcedMaterial(m);
5446	exporter->ExportIntersectable(intersect);
5447	}
5448	}
5449	cout << endl;
5450	}
5451
5452	DEL_PTR(exporter);
5453	cout << "finished" << endl;
5454	}
5455	}
5456
5457
5458	void VspBspViewCellsManager::TestFilter(const ObjectContainer &objects)
5459	{
5460	Exporter *exporter = Exporter::GetExporter("filter.x3d");
5461
5462	Vector3 bsize = mViewSpaceBox.Size();
5463	const Vector3 viewPoint(mViewSpaceBox.Center());
5464	float w = Magnitude(mViewSpaceBox.Size()) * mFilterWidth;
5465	const Vector3 width = Vector3(w);
5466
5467	PrVs testPrVs;
5468
5469	if (exporter)
5470	{
5471	ViewCellContainer viewCells;
5472
5473	const AxisAlignedBox3 tbox = GetFilterBBox(viewPoint, mFilterWidth);
5474
5475	GetPrVS(viewPoint, testPrVs, GetFilterWidth());
5476
5477	exporter->SetWireframe();
5478
5479	exporter->SetForcedMaterial(RgbColor(1,1,1));
5480	exporter->ExportBox(tbox);
5481
5482	exporter->SetFilled();
5483
5484	exporter->SetForcedMaterial(RgbColor(0,1,0));
5485	ExportViewCellGeometry(exporter, GetViewCell(viewPoint), NULL, NULL);
5486
5487	//exporter->ResetForcedMaterial();
5488	exporter->SetForcedMaterial(RgbColor(0,0,1));
5489	ExportViewCellGeometry(exporter, testPrVs.mViewCell, NULL, NULL);
5490
5491	exporter->SetForcedMaterial(RgbColor(1,0,0));
5492	exporter->ExportGeometry(objects);
5493
5494	delete exporter;
5495	}
5496	}
5497
5498
5499	int VspBspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
5500	ViewCellContainer &viewCells) const
5501	{
5502	return mVspBspTree->ComputeBoxIntersections(box, viewCells);
5503	}
5504
5505
5506	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
5507	const Vector3 &termination,
5508	ViewCellContainer &viewcells)
5509	{
5510	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
5511	}
5512
5513
5514	bool VspBspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
5515	const Vector3 &termination,
5516	ViewCell *viewCell)
5517	{
5518	return false;
5519	}
5520
5521
5522	void VspBspViewCellsManager::VisualizeWithFromPointQueries()
5523	{
5524	int numSamples;
5525
5526	Environment::GetSingleton()->GetIntValue("RenderSampler.samples", numSamples);
5527	cout << "samples" << numSamples << endl;
5528
5529	vector<RenderCostSample> samples;
5530
5531	if (!mPreprocessor->GetRenderer())
5532	return;
5533
5534	//start the view point queries
5535	long startTime = GetTime();
5536	cout << "starting sampling of render cost ... ";
5537
5538	mPreprocessor->GetRenderer()->SampleRenderCost(numSamples, samples, true);
5539
5540	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
5541
5542
5543	// for each sample:
5544	// find view cells associated with the samples
5545	// store the sample pvs with the pvs associated with the view cell
5546	//
5547	// for each view cell:
5548	// compute difference point sampled pvs - view cell pvs
5549	// export geometry with color coded pvs difference
5550
5551	std::map<ViewCell *, ObjectPvs> sampleMap;
5552
5553	vector<RenderCostSample>::const_iterator rit, rit_end = samples.end();
5554
5555	for (rit = samples.begin(); rit != rit_end; ++ rit)
5556	{
5557	RenderCostSample sample = *rit;
5558
5559	ViewCell *vc = GetViewCell(sample.mPosition);
5560
5561	std::map<ViewCell *, ObjectPvs>::iterator it = sampleMap.find(vc);
5562
5563	if (it == sampleMap.end())
5564	{
5565	sampleMap[vc] = sample.mPvs;
5566	}
5567	else
5568	{
5569	(*it).second.MergeInPlace(sample.mPvs);
5570	}
5571	}
5572
5573	// visualize the view cells
5574	std::map<ViewCell *, ObjectPvs>::const_iterator vit, vit_end = sampleMap.end();
5575
5576	Material m;//= RandomMaterial();
5577
5578	for (vit = sampleMap.begin(); vit != vit_end; ++ vit)
5579	{
5580	ViewCell vc = (vit).first;
5581
5582	const int pvsVc = mViewCellsTree->GetPvsEntries(vc);
5583	const int pvsPtSamples = (*vit).second.GetSize();
5584
5585	m.mDiffuseColor.r = (float) (pvsVc - pvsPtSamples);
5586	m.mDiffuseColor.b = 1.0f;
5587	//exporter->SetForcedMaterial(m);
5588	//ExportViewCellGeometry(exporter, vc, mClipPlaneForViz);
5589
5590	/* // counting the pvss
5591	for (rit = samples.begin(); rit != rit_end; ++ rit)
5592	{
5593	RenderCostSample sample = *rit;
5594	ViewCell *vc = GetViewCell(sample.mPosition);
5595
5596	AxisAlignedBox3 box(sample.mPosition - Vector3(1, 1, 1), sample.mPosition + Vector3(1, 1, 1));
5597	Mesh *hMesh = CreateMeshFromBox(box);
5598
5599	DEL_PTR(hMesh);
5600	}
5601	*/
5602	}
5603	}
5604
5605
5606	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
5607	ViewCell *vc,
5608	const AxisAlignedBox3 *sceneBox,
5609	const AxisAlignedPlane *clipPlane
5610	) const
5611	{
5612	if (clipPlane)
5613	{
5614	const Plane3 plane = clipPlane->GetPlane();
5615
5616	ViewCellContainer leaves;
5617	mViewCellsTree->CollectLeaves(vc, leaves);
5618	ViewCellContainer::const_iterator it, it_end = leaves.end();
5619
5620	for (it = leaves.begin(); it != it_end; ++ it)
5621	{
5622	BspNodeGeometry geom;
5623	BspNodeGeometry front;
5624	BspNodeGeometry back;
5625
5626	mVspBspTree->ConstructGeometry(*it, geom);
5627
5628	const float eps = 0.0001f;
5629	const int cf = geom.Side(plane, eps);
5630
5631	if (cf == -1)
5632	{
5633	exporter->ExportPolygons(geom.GetPolys());
5634	}
5635	else if (cf == 0)
5636	{
5637	geom.SplitGeometry(front,
5638	back,
5639	plane,
5640	mViewSpaceBox,
5641	eps);
5642
5643	if (back.Valid())
5644	{
5645	exporter->ExportPolygons(back.GetPolys());
5646	}
5647	}
5648	}
5649	}
5650	else
5651	{
5652	// export mesh if available
5653	// TODO: some bug here?
5654	if (1 && vc->GetMesh())
5655	{
5656	exporter->ExportMesh(vc->GetMesh());
5657	}
5658	else
5659	{
5660	BspNodeGeometry geom;
5661	mVspBspTree->ConstructGeometry(vc, geom);
5662	exporter->ExportPolygons(geom.GetPolys());
5663	}
5664	}
5665	}
5666
5667
5668	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
5669	{
5670	ViewCellContainer leaves;
5671	mViewCellsTree->CollectLeaves(vc, leaves);
5672
5673	int maxDist = 0;
5674
5675	// compute max height difference
5676	for (int i = 0; i < (int)leaves.size(); ++ i)
5677	{
5678	for (int j = 0; j < (int)leaves.size(); ++ j)
5679	{
5680	BspLeaf leaf = static_cast<BspViewCell >(leaves[i])->mLeaves[0];
5681
5682	if (i != j)
5683	{
5684	BspLeaf leaf2 =static_cast<BspViewCell >(leaves[j])->mLeaves[0];
5685	const int dist = mVspBspTree->TreeDistance(leaf, leaf2);
5686
5687	if (dist > maxDist)
5688	maxDist = dist;
5689	}
5690	}
5691	}
5692
5693	return maxDist;
5694	}
5695
5696
5697	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point, const bool active) const
5698	{
5699	if (!ViewCellsConstructed())
5700	return NULL;
5701
5702	if (!mViewSpaceBox.IsInside(point))
5703	return NULL;
5704
5705	return mVspBspTree->GetViewCell(point, active);
5706	}
5707
5708
5709	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
5710	{
5711	BspNodeGeometry geom;
5712	mVspBspTree->ConstructGeometry(vc, geom);
5713
5714	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
5715
5716	IncludeNodeGeomInMesh(geom, *mesh);
5717	mesh->ComputeBoundingBox();
5718
5719	vc->SetMesh(mesh);
5720	}
5721
5722
5723	int VspBspViewCellsManager::CastBeam(Beam &beam)
5724	{
5725	return mVspBspTree->CastBeam(beam);
5726	}
5727
5728
5729	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
5730	const bool createMesh)
5731	{
5732	float area = 0;
5733	float volume = 0;
5734
5735	ViewCellContainer leaves;
5736	mViewCellsTree->CollectLeaves(viewCell, leaves);
5737
5738	ViewCellContainer::const_iterator it, it_end = leaves.end();
5739
5740	for (it = leaves.begin(); it != it_end; ++ it)
5741	{
5742	BspNodeGeometry geom;
5743	mVspBspTree->ConstructGeometry(*it, geom);
5744
5745	const float lVol = geom.GetVolume();
5746	const float lArea = geom.GetArea();
5747
5748	area += lArea;
5749	volume += lVol;
5750
5751	if (createMesh)
5752	CreateMesh(*it);
5753	}
5754
5755	viewCell->SetVolume(volume);
5756	viewCell->SetArea(area);
5757	}
5758
5759
5760	void VspBspViewCellsManager::TestSubdivision()
5761	{
5762	ViewCellContainer leaves;
5763	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), leaves);
5764
5765	ViewCellContainer::const_iterator it, it_end = leaves.end();
5766
5767	const float vol = mViewSpaceBox.GetVolume();
5768	float subdivVol = 0;
5769	float newVol = 0;
5770
5771	for (it = leaves.begin(); it != it_end; ++ it)
5772	{
5773	BspNodeGeometry geom;
5774	mVspBspTree->ConstructGeometry(*it, geom);
5775
5776	const float lVol = geom.GetVolume();
5777
5778	newVol += lVol;
5779	subdivVol += (*it)->GetVolume();
5780
5781	float thres = 0.9f;
5782	if ((lVol < ((it)->GetVolume() thres)) \|\| (lVol * thres > ((*it)->GetVolume())))
5783	Debug << "warning: " << lVol << " " << (*it)->GetVolume() << endl;
5784	}
5785
5786	Debug << "exact volume: " << vol << endl;
5787	Debug << "subdivision volume: " << subdivVol << endl;
5788	Debug << "new volume: " << newVol << endl;
5789	}
5790
5791
5792	void VspBspViewCellsManager::PrepareLoadedViewCells()
5793	{
5794	// TODO: do I still need this here?
5795	if (0) mVspBspTree->RepairViewCellsLeafLists();
5796	}
5797
5798
5799
5800	/************************************************************************/
5801	/* VspOspViewCellsManager implementation */
5802	/************************************************************************/
5803
5804
5805	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree *vcTree,
5806	const string &hierarchyType)
5807	: ViewCellsManager(vcTree)
5808	{
5809	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5810
5811	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5812
5813	Debug << "compressing objects: " << mCompressObjects << endl;
5814	cout << "compressing objects: " << mCompressObjects << endl;
5815
5816	mHierarchyManager = CreateHierarchyManager(hierarchyType);
5817	mHierarchyManager->SetViewCellsManager(this);
5818	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5819	}
5820
5821
5822	VspOspViewCellsManager::VspOspViewCellsManager(ViewCellsTree vcTree, HierarchyManager hm)
5823	: ViewCellsManager(vcTree), mHierarchyManager(hm)
5824	{
5825	Environment::GetSingleton()->GetIntValue("Hierarchy.Construction.samples", mInitialSamples);
5826	Environment::GetSingleton()->GetBoolValue("ViewCells.compressObjects", mCompressObjects);
5827
5828	Debug << "compressing objects: " << mCompressObjects << endl;
5829	cout << "compressing objects: " << mCompressObjects << endl;
5830
5831	mHierarchyManager->SetViewCellsManager(this);
5832	mHierarchyManager->SetViewCellsTree(mViewCellsTree);
5833	}
5834
5835
5836	Intersectable *
5837	VspOspViewCellsManager::GetIntersectable(const VssRay &ray, const bool isTermination) const
5838	{
5839	if (mUseKdPvs)
5840	{
5841	return ViewCellsManager::GetIntersectable(ray, isTermination);
5842	}
5843	else
5844	{
5845	return mHierarchyManager->GetIntersectable(ray, isTermination);
5846	}
5847	}
5848
5849
5850	HierarchyManager *VspOspViewCellsManager::CreateHierarchyManager(const string &hierarchyType)
5851	{
5852	HierarchyManager *hierarchyManager;
5853
5854	if (strcmp(hierarchyType.c_str(), "osp") == 0)
5855	{
5856	Debug << "hierarchy manager: osp" << endl;
5857	hierarchyManager = new HierarchyManager(HierarchyManager::KD_BASED_OBJ_SUBDIV);
5858	}
5859	else if (strcmp(hierarchyType.c_str(), "bvh") == 0)
5860	{
5861	Debug << "hierarchy manager: bvh" << endl;
5862	hierarchyManager = new HierarchyManager(HierarchyManager::BV_BASED_OBJ_SUBDIV);
5863	}
5864	else // only view space partition
5865	{
5866	Debug << "hierarchy manager: obj" << endl;
5867	hierarchyManager = new HierarchyManager(HierarchyManager::NO_OBJ_SUBDIV);
5868	}
5869
5870	return hierarchyManager;
5871	}
5872
5873
5874	VspOspViewCellsManager::~VspOspViewCellsManager()
5875	{
5876	DEL_PTR(mHierarchyManager);
5877	}
5878
5879
5880	float VspOspViewCellsManager::GetProbability(ViewCell *viewCell)
5881	{
5882	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
5883	}
5884
5885
5886	void VspOspViewCellsManager::CollectViewCells()
5887	{
5888	// view cells tree constructed
5889	if (!ViewCellsTreeConstructed())
5890	{
5891	mHierarchyManager->GetVspTree()->CollectViewCells(mViewCells, false);
5892	}
5893	else
5894	{ // we can use the view cells tree hierarchy to get the right set
5895	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
5896	}
5897	}
5898
5899
5900	bool VspOspViewCellsManager::ViewCellsConstructed() const
5901	{
5902	return mHierarchyManager->GetVspTree()->GetRoot() != NULL;
5903	}
5904
5905
5906	ViewCell VspOspViewCellsManager::GenerateViewCell(Mesh mesh) const
5907	{
5908	return new VspViewCell(mesh);
5909	}
5910
5911
5912	int VspOspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
5913	const VssRayContainer &rays)
5914	{
5915	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
5916
5917	// skip rest if view cells were already constructed
5918	if (ViewCellsConstructed())
5919	return 0;
5920
5921	int sampleContributions = 0;
5922	VssRayContainer sampleRays;
5923
5924	int limit = min (mInitialSamples, (int)rays.size());
5925
5926	VssRayContainer constructionRays;
5927	VssRayContainer savedRays;
5928
5929	Debug << "samples used for vsp bsp subdivision: " << mInitialSamples
5930	<< ", actual rays: " << (int)rays.size() << endl;
5931
5932	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
5933
5934	Debug << "initial rays used for construction: " << (int)constructionRays.size() << endl;
5935	Debug << "saved rays: " << (int)savedRays.size() << endl;
5936
5937	mHierarchyManager->Construct(constructionRays, objects, &mViewSpaceBox);
5938
5939	#if TEST_EVALUATION
5940	VssRayContainer::const_iterator tit, tit_end = constructionRays.end();
5941	for (tit = constructionRays.begin(); tit != tit_end; ++ tit)
5942	{
5943	storedRays.push_back(new VssRay((tit)));
5944	}
5945	#endif
5946
5947	/////////////////////////
5948	//-- print satistics for subdivision and view cells
5949
5950	Debug << endl << endl << *mHierarchyManager << endl;
5951
5952	ResetViewCells();
5953	Debug << "\nView cells after construction:\n" << mCurrentViewCellsStats << endl;
5954
5955	//////////////
5956	//-- recast rest of rays
5957
5958	const long startTime = GetTime();
5959	cout << "Computing remaining ray contributions ... ";
5960
5961	if (SAMPLE_AFTER_SUBDIVISION)
5962	ComputeSampleContributions(savedRays, true, false);
5963
5964	Debug << "finished computing remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
5965	<< " secs" << endl;
5966
5967	if (0)
5968	{
5969	// real meshes are constructed at this stage
5970	cout << "finalizing view cells ... ";
5971	FinalizeViewCells(true);
5972	cout << "finished" << endl;
5973	}
5974
5975	return sampleContributions;
5976	}
5977
5978
5979	int VspOspViewCellsManager::PostProcess(const ObjectContainer &objects,
5980	const VssRayContainer &rays)
5981	{
5982	if (!ViewCellsConstructed())
5983	{
5984	Debug << "post process error: no view cells constructed" << endl;
5985	return 0;
5986	}
5987
5988	// if view cells were already constructed before post processing step
5989	// (e.g., because they were loaded), we are finished
5990	if (mViewCellsFinished)
5991	{
5992	FinalizeViewCells(true);
5993	EvaluateViewCellsStats();
5994
5995	return 0;
5996	}
5997
5998	// check if new view cells turned invalid
5999	int minPvs, maxPvs;
6000
6001	if (0)
6002	{
6003	minPvs = mMinPvsSize;
6004	maxPvs = mMaxPvsSize;
6005	}
6006	else
6007	{
6008	// problem matt: why did I start here from zero?
6009	minPvs = 0;
6010	maxPvs = mMaxPvsSize;
6011	}
6012
6013	Debug << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
6014	cout << "setting validity, min: " << minPvs << " max: " << maxPvs << endl;
6015
6016	SetValidity(minPvs, maxPvs);
6017
6018
6019	// area is not up to date, has to be recomputed
6020	mTotalAreaValid = false;
6021	VssRayContainer postProcessRays;
6022	GetRaySets(rays, mPostProcessSamples, postProcessRays);
6023
6024	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
6025
6026
6027	// compute tree by merging the nodes of the spatial hierarchy
6028	ViewCell *root = ConstructSpatialMergeTree(mHierarchyManager->GetVspTree()->GetRoot());
6029	mViewCellsTree->SetRoot(root);
6030
6031	//////////////////////////
6032	//-- update pvs up to the root of the hierarchy
6033
6034	ObjectPvs pvs;
6035	UpdatePvsForEvaluation(root, pvs);
6036
6037
6038	//////////////////////
6039	//-- render simulation after merge + refine
6040
6041	cout << "\nview cells partition render time before compress" << endl << endl;
6042	static_cast<RenderSimulator *>(mRenderer)->RenderScene();
6043	SimulationStatistics ss;
6044	static_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
6045	cout << ss << endl;
6046
6047
6048	mHierarchyManager->CreateUniqueObjectIds();
6049
6050	///////////
6051	//-- compression
6052
6053	if (0) CompressViewCells();
6054
6055	/////////////
6056	//-- some tasks still to do on the view cells:
6057	//-- Compute meshes from view cell geometry, evaluate volume and / or area
6058
6059	if (1) FinalizeViewCells(true);
6060
6061	return 0;
6062	}
6063
6064
6065	int VspOspViewCellsManager::GetType() const
6066	{
6067	return VSP_OSP;
6068	}
6069
6070
6071	ViewCell VspOspViewCellsManager::ConstructSpatialMergeTree(VspNode root)
6072	{
6073	// terminate recursion
6074	if (root->IsLeaf())
6075	{
6076	VspLeaf leaf = static_cast<VspLeaf >(root);
6077	leaf->GetViewCell()->SetMergeCost(0.0f);
6078	return leaf->GetViewCell();
6079	}
6080
6081	VspInterior interior = static_cast<VspInterior >(root);
6082	ViewCellInterior *viewCellInterior = new ViewCellInterior();
6083
6084	// evaluate merge cost for priority traversal
6085	const float mergeCost = -(float)root->mTimeStamp;
6086	viewCellInterior->SetMergeCost(mergeCost);
6087
6088	float volume = 0;
6089
6090	VspNode *front = interior->GetFront();
6091	VspNode *back = interior->GetBack();
6092
6093	ObjectPvs frontPvs, backPvs;
6094
6095	/////////
6096	//-- recursivly compute child hierarchies
6097
6098	ViewCell *backVc = ConstructSpatialMergeTree(back);
6099	ViewCell *frontVc = ConstructSpatialMergeTree(front);
6100
6101	viewCellInterior->SetupChildLink(backVc);
6102	viewCellInterior->SetupChildLink(frontVc);
6103
6104	volume += backVc->GetVolume();
6105	volume += frontVc->GetVolume();
6106
6107	viewCellInterior->SetVolume(volume);
6108
6109	return viewCellInterior;
6110	}
6111
6112
6113	bool VspOspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
6114	{
6115	if (!ViewCellsConstructed())
6116	return ViewCellsManager::GetViewPoint(viewPoint);
6117
6118	// TODO: set reasonable limit
6119	const int limit = 20;
6120
6121	for (int i = 0; i < limit; ++ i)
6122	{
6123	viewPoint = mViewSpaceBox.GetRandomPoint();
6124
6125	if (mHierarchyManager->GetVspTree()->ViewPointValid(viewPoint))
6126	{
6127	return true;
6128	}
6129	}
6130
6131	Debug << "failed to find valid view point, taking " << viewPoint << endl;
6132	return false;
6133	}
6134
6135
6136	void VspOspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
6137	ViewCell *vc,
6138	const AxisAlignedBox3 *sceneBox,
6139	const AxisAlignedPlane *clipPlane
6140	) const
6141	{
6142	ViewCellContainer leaves;
6143	mViewCellsTree->CollectLeaves(vc, leaves);
6144	ViewCellContainer::const_iterator it, it_end = leaves.end();
6145
6146	Plane3 plane;
6147	if (clipPlane)
6148	{
6149	// arbitrary plane definition
6150	plane = clipPlane->GetPlane();
6151	}
6152
6153	for (it = leaves.begin(); it != it_end; ++ it)
6154	{
6155	VspViewCell vspVc = static_cast<VspViewCell >(*it);
6156	VspLeaf *l = vspVc->mLeaves[0];
6157
6158	const AxisAlignedBox3 box =
6159	mHierarchyManager->GetVspTree()->GetBoundingBox(vspVc->mLeaves[0]);
6160
6161	if (sceneBox && !Overlap(*sceneBox, box))
6162	continue;
6163
6164	if (clipPlane)
6165	{
6166	if (box.Side(plane) == -1)
6167	{
6168	exporter->ExportBox(box);
6169	}
6170	else if (box.Side(plane) == 0)
6171	{
6172	// intersection
6173	AxisAlignedBox3 fbox, bbox;
6174	box.Split(clipPlane->mAxis, clipPlane->mPosition, fbox, bbox);
6175	exporter->ExportBox(bbox);
6176	}
6177	}
6178	else
6179	{
6180	exporter->ExportBox(box);
6181	}
6182	}
6183	}
6184
6185
6186	bool VspOspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
6187	{
6188	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
6189	// validy update in preprocessor for all managers)
6190	return ViewCellsManager::ViewPointValid(viewPoint);
6191
6192	// return mViewSpaceBox.IsInside(viewPoint) &&
6193	// mVspTree->ViewPointValid(viewPoint);
6194	}
6195
6196
6197	float VspOspViewCellsManager::UpdateObjectCosts()
6198	{
6199	float maxRenderCost = 0;
6200
6201	cout << "updating object pvs cost ... ";
6202	const long startTime = GetTime();
6203
6204	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
6205
6206	Intersectable::NewMail();
6207
6208	const float invViewSpaceVol = 1.0f / GetViewSpaceBox().GetVolume();
6209
6210	for (vit = mViewCells.begin(); vit != vit_end; ++ vit)
6211	{
6212	ViewCell vc = vit;
6213
6214	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
6215
6216	// output PVS of view cell
6217	while (pit.HasMoreEntries())
6218	{
6219	ObjectPvsEntry entry = pit.Next();
6220
6221	BvhNode node = static_cast<BvhNode >(entry.mObject);
6222
6223	// hack!!
6224	if (!node->IsLeaf())
6225	{
6226	cout << "error, can only do leaves" << endl;
6227	return 0;
6228	}
6229
6230	if (!node->Mailed())
6231	{
6232	node->Mail();
6233	node->mRenderCost = 0;
6234	}
6235
6236	const float rc = (float)((BvhLeaf *)node)->mObjects.size();
6237
6238	node->mRenderCost += rc * vc->GetVolume() * invViewSpaceVol;
6239
6240	if (node->mRenderCost > maxRenderCost)
6241	maxRenderCost = node->mRenderCost;
6242	}
6243	}
6244
6245	cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
6246
6247	return maxRenderCost;
6248	}
6249
6250
6251	void VspOspViewCellsManager::Visualize(const ObjectContainer &objects,
6252	const VssRayContainer &sampleRays)
6253	{
6254	if (!ViewCellsConstructed())
6255	return;
6256
6257	VssRayContainer visRays;
6258	GetRaySets(sampleRays, mVisualizationSamples, visRays);
6259
6260	////////////
6261	//-- export final view cells
6262
6263	Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl");
6264
6265	//Vector3 scale(0.9f, 0.9f, 0.9f);
6266	Vector3 scale(1.0f, 1.0f, 1.0f);
6267
6268	if (exporter)
6269	{
6270	if (CLAMP_TO_BOX)
6271	{
6272	exporter->mClampToBox = true;
6273	}
6274
6275	EvaluateViewCellsStats();
6276
6277	const long starttime = GetTime();
6278	cout << "exporting final view cells (after initial construction + post process) ... " << endl;
6279
6280	// matt: hack for clamping scene
6281	AxisAlignedBox3 bbox = mViewSpaceBox;
6282	bbox.Scale(scale);
6283
6284	if (1 && mExportRays)
6285	{
6286	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
6287	}
6288
6289	// hack color code
6290	const int savedColorCode = mColorCode;
6291
6292	const float maxRenderCost = UpdateObjectCosts();
6293	cout << "maxRenderCost: " << maxRenderCost << endl;
6294	mColorCode = 0; // 0 = random, 1 = export pvs
6295
6296	if (0)
6297	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
6298	CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
6299
6300
6301	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6302	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
6303
6304	delete exporter;
6305
6306	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6307	mColorCode = savedColorCode;
6308	}
6309
6310	exporter = Exporter::GetExporter("final_object_partition.wrl");
6311
6312	if (exporter)
6313	{
6314	if (CLAMP_TO_BOX)
6315	{
6316	exporter->mClampToBox = true;
6317	}
6318
6319	EvaluateViewCellsStats();
6320
6321	const long starttime = GetTime();
6322	cout << "exporting final objects (after initial construction + post process) ... ";
6323
6324	// matt: hack for clamping scene
6325	AxisAlignedBox3 bbox = mViewSpaceBox;
6326	bbox.Scale(scale);
6327
6328	// hack color code (show pvs size)
6329	const int savedColorCode = mColorCode;
6330
6331	mColorCode = 1; // 0 = random, 1 = export pvs
6332	// don't visualize render cost
6333	const float maxRenderCost = -1;
6334
6335	if (1)
6336	mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects,
6337	CLAMP_TO_BOX ? &bbox : NULL, maxRenderCost, false);
6338
6339
6340	//ExportViewCellsForViz(exporter, CLAMP_TO_BOX ? &bbox : NULL, mColorCode, GetClipPlane());
6341	if (0)
6342	ExportViewCellsForViz(exporter, NULL, mColorCode, GetClipPlane());
6343
6344	delete exporter;
6345
6346	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3f << " secs" << endl;
6347	mColorCode = savedColorCode;
6348	}
6349
6350	// visualization of the merged view cells
6351	if (0)
6352	{
6353	ExportMergedViewCells(objects);
6354	}
6355
6356	// export some view cells
6357	int leafOut;
6358	Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut);
6359
6360	const bool sortViewCells = false;
6361	const bool exportPvs = true;
6362	const bool exportRays = true;
6363	const int raysOut = 100;
6364
6365	ExportSingleViewCells(objects,
6366	leafOut,
6367	sortViewCells,
6368	exportPvs,
6369	exportRays,
6370	raysOut,
6371	"");
6372	}
6373
6374
6375	void VspOspViewCellsManager::ExportSingleViewCells(const ObjectContainer &objects,
6376	const int maxViewCells,
6377	const bool sortViewCells,
6378	const bool exportPvs,
6379	const bool exportRays,
6380	const int maxRays,
6381	const string prefix,
6382	VssRayContainer *visRays)
6383	{
6384	if (sortViewCells)
6385	{
6386	// sort view cells to visualize the view cells with highest render cost
6387	sort(mViewCells.begin(), mViewCells.end(), ViewCell::LargerRenderCost);
6388	}
6389
6390	ViewCell::NewMail();
6391	const int limit = min(maxViewCells, (int)mViewCells.size());
6392
6393	cout << "\nExporting " << limit << " single view cells: " << endl;
6394
6395	for (int i = 0; i < limit; ++ i)
6396	{
6397	cout << "creating output for view cell " << i << " ... ";
6398
6399	// largest view cell pvs first of random view cell
6400	ViewCell *vc = sortViewCells ?
6401	mViewCells[i] : mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
6402
6403	if (vc->Mailed()) // view cell already processed
6404	continue;
6405
6406	vc->Mail();
6407
6408	ObjectPvs pvs;
6409	mViewCellsTree->GetPvs(vc, pvs);
6410
6411	char s[64]; sprintf(s, "%sviewcell%04d.wrl", prefix.c_str(), i);
6412	Exporter *exporter = Exporter::GetExporter(s);
6413
6414	cout << "view cell " << vc->GetId() << ": pvs cost=" << mViewCellsTree->GetPvsCost(vc) << endl;
6415
6416	if (exportPvs)
6417	{
6418	Material m;
6419
6420	Intersectable::NewMail();
6421
6422	ObjectPvsIterator pit = pvs.GetIterator();
6423
6424	// output PVS of view cell
6425	while (pit.HasMoreEntries())
6426	{
6427	ObjectPvsEntry entry = pit.Next();
6428
6429	Intersectable *intersect = entry.mObject;
6430
6431	if (!intersect->Mailed())
6432	{
6433	m = RandomMaterial();
6434	exporter->SetForcedMaterial(m);
6435
6436	exporter->ExportIntersectable(intersect);
6437	intersect->Mail();
6438	}
6439	}
6440	}
6441
6442	if (exportRays)
6443	{
6444	////////////
6445	//-- export the sample rays
6446
6447	// output rays stored with the view cells during subdivision
6448	VssRayContainer vcRays;
6449	VssRayContainer collectRays;
6450
6451	// collect intial view cells
6452	ViewCellContainer leaves;
6453	mViewCellsTree->CollectLeaves(vc, leaves);
6454
6455	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
6456
6457	for (vit = leaves.begin(); vit != vit_end; ++ vit)
6458	{
6459	VspLeaf vcLeaf = static_cast<VspViewCell >(*vit)->mLeaves[0];
6460	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
6461
6462	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
6463	{
6464	collectRays.push_back(*rit);
6465	}
6466	}
6467
6468	const int raysOut = min((int)collectRays.size(), maxRays);
6469
6470	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
6471
6472	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
6473	{
6474	const float p = RandomValue(0.0f, (float)collectRays.size());
6475
6476	if (p < raysOut)
6477	vcRays.push_back(*rit);
6478	}
6479
6480	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
6481	}
6482
6483
6484	/////////////////
6485	//-- export view cell geometry
6486
6487	exporter->SetWireframe();
6488
6489	Material m;
6490	m.mDiffuseColor = RgbColor(0, 1, 0);
6491	exporter->SetForcedMaterial(m);
6492
6493	ExportViewCellGeometry(exporter, vc, NULL, NULL);
6494	exporter->SetFilled();
6495
6496	DEL_PTR(exporter);
6497	cout << "finished" << endl;
6498	}
6499
6500	cout << endl;
6501	}
6502
6503
6504	int VspOspViewCellsManager::ComputeBoxIntersections(const AxisAlignedBox3 &box,
6505	ViewCellContainer &viewCells) const
6506	{
6507	return mHierarchyManager->GetVspTree()->ComputeBoxIntersections(box, viewCells);
6508	}
6509
6510
6511	int VspOspViewCellsManager::CastLineSegment(const Vector3 &origin,
6512	const Vector3 &termination,
6513	ViewCellContainer &viewcells)
6514	{
6515	return mHierarchyManager->
6516	GetVspTree()->CastLineSegment(origin, termination, viewcells);
6517	}
6518
6519
6520	bool VspOspViewCellsManager::LineSegmentIntersects(const Vector3 &origin,
6521	const Vector3 &termination,
6522	ViewCell *viewCell)
6523	{
6524	return mHierarchyManager->
6525	GetVspTree()->LineSegmentIntersects(origin, termination, viewCell);
6526	}
6527
6528
6529	bool VspOspViewCellsManager::ExportViewCells(const string filename,
6530	const bool exportPvs,
6531	const ObjectContainer &objects)
6532	{
6533	if (!ViewCellsConstructed() \|\| !ViewCellsTreeConstructed())
6534	return false;
6535
6536	const long starttime = GetTime();
6537	cout << "exporting view cells to xml ... ";
6538
6539	OUT_STREAM stream(filename.c_str());
6540
6541	// for output we need unique ids for each view cell
6542	CreateUniqueViewCellIds();
6543
6544	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
6545	stream << "<VisibilitySolution>" << endl;
6546
6547	// §§ tmp matt: for storage cost
6548	if (0 && exportPvs)
6549	{
6550	///////////////
6551	//-- export bounding boxes
6552	//-- The bounding boxes are used to identify
6553	//-- the objects in the rendering engine
6554	mHierarchyManager->ExportBoundingBoxes(stream, objects);
6555	}
6556
6557	//////////////////////////
6558	//-- export the view cells and the pvs
6559
6560	const int numViewCells = mCurrentViewCellsStats.viewCells;
6561
6562	stream << "<ViewCells number=\"" << numViewCells << "\" >" << endl;
6563	mViewCellsTree->Export(stream, exportPvs);
6564	stream << "</ViewCells>" << endl;
6565
6566	//////////////////////
6567	//-- export the view space hierarchy
6568
6569	stream << "<ViewSpaceHierarchy type=\"vsp\""
6570	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
6571	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\">" << endl;
6572
6573	mHierarchyManager->GetVspTree()->Export(stream);
6574	stream << "</ViewSpaceHierarchy>" << endl;
6575
6576	//////////////////////
6577	//-- export the object space partition
6578
6579	mHierarchyManager->ExportObjectSpaceHierarchy(stream);
6580
6581	stream << "</VisibilitySolution>" << endl;
6582	stream.close();
6583
6584	cout << "finished in " << TimeDiff(starttime, GetTime()) * 1e-3 << " secs" << endl;
6585	return true;
6586	}
6587
6588
6589
6590	ViewCell *VspOspViewCellsManager::GetViewCell(const Vector3 &point,
6591	const bool active) const
6592	{
6593	if (!ViewCellsConstructed())
6594	return NULL;
6595
6596	if (!mViewSpaceBox.IsInside(point))
6597	return NULL;
6598
6599	return mHierarchyManager->GetVspTree()->GetViewCell(point, active);
6600	}
6601
6602
6603	void VspOspViewCellsManager::CreateMesh(ViewCell *vc)
6604	{
6605	Mesh *mesh = MeshManager::GetSingleton()->CreateResource();
6606
6607	ViewCellContainer leaves;
6608	mViewCellsTree->CollectLeaves(vc, leaves);
6609
6610	ViewCellContainer::const_iterator it, it_end = leaves.end();
6611
6612	for (it = leaves.begin(); it != it_end; ++ it)
6613	{
6614	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6615	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6616	IncludeBoxInMesh(box, *mesh);
6617	}
6618
6619	mesh->ComputeBoundingBox();
6620
6621	vc->SetMesh(mesh);
6622	}
6623
6624
6625	int VspOspViewCellsManager::CastBeam(Beam &beam)
6626	{
6627	// matt: TODO
6628	return 0;
6629	}
6630
6631
6632	void VspOspViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
6633	{
6634	float area = 0;
6635	float volume = 0;
6636
6637	ViewCellContainer leaves;
6638	mViewCellsTree->CollectLeaves(viewCell, leaves);
6639
6640	ViewCellContainer::const_iterator it, it_end = leaves.end();
6641
6642	for (it = leaves.begin(); it != it_end; ++ it)
6643	{
6644	VspLeaf leaf = static_cast<VspViewCell >(*it)->mLeaves[0];
6645
6646	const AxisAlignedBox3 box = mHierarchyManager->GetVspTree()->GetBoundingBox(leaf);
6647
6648	const float lVol = box.GetVolume();
6649	const float lArea = box.SurfaceArea();
6650
6651	area += lArea;
6652	volume += lVol;
6653
6654	CreateMesh(*it);
6655	}
6656
6657	viewCell->SetVolume(volume);
6658	viewCell->SetArea(area);
6659	}
6660
6661
6662	void VspOspViewCellsManager::PrepareLoadedViewCells()
6663	{
6664	// TODO
6665	}
6666
6667
6668	static void PrintCompressionStats(HierarchyManager *hm, const int pvsEntries)
6669	{
6670	float mem = (float)pvsEntries * ObjectPvs::GetEntrySize();
6671
6672	float fullmem = mem +
6673	(hm->GetVspTree()->GetStatistics().Leaves() * 16 +
6674	hm->mBvHierarchy->GetStatistics().Leaves() * 16) / float(1024 * 1024);
6675
6676	cout << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6677	Debug << "entries: " << pvsEntries << ", mem=" << mem << ", fullmem=" << fullmem <<endl;
6678	}
6679
6680
6681	void VspOspViewCellsManager::CompressViewCells()
6682	{
6683	if (!(ViewCellsTreeConstructed() && mCompressViewCells))
6684	return;
6685
6686	////////////
6687	//-- compression
6688
6689	int pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6690
6691	cout << "before compression: " << endl;
6692	Debug << "before compression: " << endl;
6693
6694	PrintCompressionStats(mHierarchyManager, pvsEntries);
6695
6696	if (mCompressObjects)
6697	{
6698	cout << "compressing in the objects: " << endl;
6699	Debug << "compressing in the objects: " << endl;
6700
6701	pvsEntries = mHierarchyManager->CompressObjectSpace();
6702	}
6703	else
6704	{
6705	cout << "compressing in the view space: " << endl;
6706	Debug << "compressing in the view space: " << endl;
6707
6708	mViewCellsTree->SetViewCellsStorage(ViewCellsTree::COMPRESSED);
6709	pvsEntries = mViewCellsTree->CountStoredPvsEntries(mViewCellsTree->GetRoot());
6710	}
6711
6712	PrintCompressionStats(mHierarchyManager, pvsEntries);
6713	}
6714
6715
6716	ViewCellsManager *VspOspViewCellsManager::LoadViewCells(const string &filename,
6717	ObjectContainer *objects,
6718	const bool finalizeViewCells,
6719	BoundingBoxConverter *bconverter)
6720
6721	{
6722	ViewCellsManager *vm =
6723	ViewCellsManager::LoadViewCells(filename, objects, finalizeViewCells, bconverter);
6724
6725	return vm;
6726	}
6727
6728
6729	void
6730	VspOspViewCellsManager::CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects)
6731	{
6732	mHierarchyManager->CollectObjects(box, objects);
6733	}
6734
6735
6736	#if 1
6737
6738	void VspOspViewCellsManager::EvalViewCellPartition()
6739	{
6740	int samplesPerPass;
6741	int numSamples;
6742	int castSamples = 0;
6743	int oldSamples = 0;
6744	int samplesForStats;
6745	char statsPrefix[100];
6746	char suffix[100];
6747	int splitsStepSize;
6748
6749	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesPerPass", samplesPerPass);
6750	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samplesForStats", samplesForStats);
6751	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.samples", numSamples);
6752	Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.statsPrefix", statsPrefix);
6753	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.stepSize", splitsStepSize);
6754
6755	bool useHisto;
6756	int histoMem;
6757
6758	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6759	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoMem", histoMem);
6760
6761	Debug << "step size: " << splitsStepSize << endl;
6762	Debug << "view cell evaluation samples per pass: " << samplesPerPass << endl;
6763	Debug << "view cell evaluation samples: " << numSamples << endl;
6764	Debug << "view cell stats prefix: " << statsPrefix << endl;
6765
6766	cout << "reseting pvs ... ";
6767
6768	// reset pvs and start over from zero
6769	mViewCellsTree->ResetPvs();
6770
6771	cout << "finished" << endl;
6772	cout << "Evaluating view cell partition ... " << endl;
6773
6774	vector<int> evalStrats;
6775
6776	// mix of sampling strategies
6777	if (0)
6778	{
6779	evalStrats.push_back(SamplingStrategy::OBJECT_DIRECTION_BASED_DISTRIBUTION);
6780	}
6781	else
6782	{
6783	/*evalStrats.push_back(SamplingStrategy::OBJECT_BASED_DISTRIBUTION);
6784	evalStrats.push_back(SamplingStrategy::REVERSE_VIEWSPACE_BORDER_BASED_DISTRIBUTION);
6785	evalStrats.push_back(SamplingStrategy::REVERSE_OBJECT_BASED_DISTRIBUTION);
6786	*/
6787	evalStrats.push_back(SamplingStrategy::SPATIAL_BOX_BASED_DISTRIBUTION);
6788	}
6789
6790	Debug << "casting eval strategies: ";
6791	for (int i = 0; i < (int)evalStrats.size(); ++ i)
6792	Debug << evalStrats[i] << " ";
6793	Debug << endl;
6794
6795	cout << "casting eval strategies: ";
6796	for (int i = 0; i < (int)evalStrats.size(); ++ i)
6797	cout << evalStrats[i] << " ";
6798	cout << endl;
6799
6800	int pass = 0;
6801
6802	while (castSamples < numSamples)
6803	{
6804	///////////////
6805	//-- we have to use uniform sampling strategy for construction rays
6806
6807	VssRayContainer evaluationSamples;
6808	const int samplingType = mEvaluationSamplingType;
6809
6810	long startTime = GetTime();
6811
6812	cout << "casting " << samplesPerPass << " samples ... ";
6813	Debug << "casting " << samplesPerPass << " samples ... ";
6814
6815	if (1)
6816	{
6817	CastPassSamples(samplesPerPass, evalStrats, evaluationSamples);
6818	}
6819	else
6820	{
6821	// use mixed distributions
6822	CastPassSamples2(samplesPerPass, evaluationSamples);
6823	}
6824
6825	castSamples += samplesPerPass;
6826
6827	Real timeDiff = TimeDiff(startTime, GetTime());
6828
6829	cout << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6830	cout << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6831
6832	Debug << "finished in " << timeDiff * 1e-3f << " secs" << endl;
6833	Debug << "computing sample contributions of " << (int)evaluationSamples.size() << " samples ... ";
6834
6835	startTime = GetTime();
6836
6837	ComputeSampleContributions(evaluationSamples, true, false);
6838
6839	timeDiff = TimeDiff(startTime, GetTime());
6840	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6841	Debug << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6842
6843	if ((castSamples >= samplesForStats + oldSamples) \|\|
6844	(castSamples >= numSamples))
6845	{
6846	oldSamples += samplesForStats;
6847
6848	///////////
6849	//-- output stats
6850
6851	sprintf(suffix, "-%09d-eval.log", castSamples);
6852	const string filename = string(statsPrefix) + string(suffix);
6853
6854	startTime = GetTime();
6855
6856	cout << "compute new statistics ... " << endl;
6857
6858	ofstream ofstr(filename.c_str());
6859	mHierarchyManager->EvaluateSubdivision2(ofstr, splitsStepSize, false, useHisto, histoMem, pass);
6860
6861	timeDiff = TimeDiff(startTime, GetTime());
6862	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6863	cout << "*************************************" << endl;
6864
6865	Debug << "statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6866
6867	#if 0
6868	//////////////
6869	// filtered stats
6870
6871	sprintf(suffix, "-%09d-eval-filter.log", castSamples);
6872	const string filename2 = string(statsPrefix) + string(suffix);
6873
6874	startTime = GetTime();
6875
6876	cout << "compute new statistics for filtered pvs ... " << endl;
6877
6878	ofstream ofstr2(filename2.c_str());
6879	mHierarchyManager->EvaluateSubdivision2(ofstr2, splitsStepSize, true);
6880
6881	timeDiff = TimeDiff(startTime, GetTime());
6882	cout << "finished in " << timeDiff * 1e-3 << " secs" << endl;
6883	cout << "*************************************" << endl;
6884	Debug << "filtered statistics computed in " << timeDiff * 1e-3 << " secs" << endl;
6885	#endif
6886
6887	// only for debugging purpose
6888	if (0)
6889	{
6890	ViewCellContainer viewCells;
6891	mViewCellsTree->CollectLeaves(mViewCellsTree->GetRoot(), viewCells);
6892
6893	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
6894	int pvsSize = 0;
6895
6896	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
6897	{
6898	pvsSize += (*vit)->GetPvs().GetSize();
6899	}
6900
6901	cout << "debug entries: " << pvsSize << ", memcost: "
6902	<< (float)pvsSize * ObjectPvs::GetEntrySize() << endl;
6903	}
6904	++ pass;
6905	}
6906
6907	disposeRays(evaluationSamples, NULL);
6908	}
6909
6910	////////////
6911	//-- histogram
6912	#if 1
6913	const int numLeaves = mViewCellsTree->GetNumInitialViewCells(mViewCellsTree->GetRoot());
6914	int histoStepSize;
6915
6916	Environment::GetSingleton()->GetBoolValue("ViewCells.Evaluation.histogram", useHisto);
6917	Environment::GetSingleton()->GetIntValue("ViewCells.Evaluation.histoStepSize", histoStepSize);
6918
6919	if (useHisto)
6920	{
6921	// evaluate view cells in a histogram
6922	char str[64];
6923
6924	// hack: just show final view cells
6925	int pass = (int)mViewCells.size();
6926	//for (int pass = histoStepSize; pass <= numLeaves; pass += histoStepSize)
6927	if (1)
6928	{
6929	string filename;
6930
6931	cout << "computing histogram for " << pass << " view cells" << endl;
6932
6933	//////////////////////////////////////////
6934	//-- evaluate histogram for pvs size
6935
6936	cout << "computing pvs histogram for " << pass << " view cells" << endl;
6937
6938	sprintf(str, "-%09d-histo-pvs2.log", pass);
6939	filename = string(statsPrefix) + string(str);
6940
6941	EvalViewCellHistogramForPvsSize(filename, pass);
6942	}
6943	}
6944	#endif
6945	}
6946
6947	#endif
6948
6949
6950
6951	}

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

Download in other formats: