Context Navigation

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

Revision 2105, 177.0 KB checked in by bittner, 17 years ago (diff)
simple ray separated

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

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

Download in other formats: