Context Navigation

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

Revision 2206, 178.3 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: