Context Navigation

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

Revision 2113, 176.8 KB checked in by mattausch, 17 years ago (diff)
warning: debug version

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

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

Download in other formats: