Context Navigation

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

Revision 2168, 177.2 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: