Context Navigation

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

Revision 2347, 178.7 KB checked in by mattausch, 17 years ago (diff)
debug version

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

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

Download in other formats: