Context Navigation

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

Revision 2023, 175.6 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: