Context Navigation

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

Revision 649, 83.8 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include "ViewCellsManager.h"
2	#include "RenderSimulator.h"
3	#include "Mesh.h"
4	#include "Triangle3.h"
5	#include "ViewCell.h"
6	#include "Environment.h"
7	#include "X3dParser.h"
8	#include "ViewCellBsp.h"
9	#include "KdTree.h"
10	#include "VspKdTree.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
18	#define SAMPLE_AFTER_SUBDIVISION 0
19
20
21	ViewCellsManager::ViewCellsManager():
22	mRenderer(NULL),
23	mInitialSamples(0),
24	mConstructionSamples(0),
25	mPostProcessSamples(0),
26	mVisualizationSamples(0),
27	mTotalAreaValid(false),
28	mTotalArea(0.0f),
29	mViewCellsFinished(false),
30	mMaxPvsSize(9999999),
31	mMinPvsSize(0), // one means only empty view cells are invalid
32	mMaxPvsRatio(1.0)
33	{
34	mViewSpaceBox.Initialize();
35	ParseEnvironment();
36
37	mViewCellsTree = new ViewCellsTree(this);
38	}
39
40
41	void ViewCellsManager::ParseEnvironment()
42	{
43	// visualization stuff
44	environment->GetBoolValue("ViewCells.Visualization.exportRays", mExportRays);
45	environment->GetBoolValue("ViewCells.Visualization.exportGeometry", mExportGeometry);
46	environment->GetFloatValue("ViewCells.maxPvsRatio", mMaxPvsRatio);
47	bool emptyViewCells = false;
48	environment->GetBoolValue("ViewCells.pruneEmptyViewCells", emptyViewCells);
49	environment->GetBoolValue("ViewCells.processOnlyValidViewCells", mOnlyValidViewCells);
50
51	environment->GetIntValue("ViewCells.Construction.samples", mConstructionSamples);
52	environment->GetIntValue("ViewCells.PostProcess.samples", mPostProcessSamples);
53	environment->GetBoolValue("ViewCells.PostProcess.useRaysForMerge", mUseRaysForMerge);
54
55	environment->GetIntValue("ViewCells.Visualization.samples", mVisualizationSamples);
56
57	environment->GetIntValue("ViewCells.Construction.samplesPerPass", mSamplesPerPass);
58	environment->GetBoolValue("ViewCells.exportToFile", mExportViewCells);
59
60
61	environment->GetIntValue("ViewCells.active", mNumActiveViewCells);
62	environment->GetBoolValue("ViewCells.PostProcess.compress", mCompressViewCells);
63	environment->GetBoolValue("ViewCells.Visualization.useCuttingPlane", mUseCuttingPlaneForViz);
64
65	environment->GetBoolValue("ViewCells.PostProcess.merge", mMergeViewCells);
66
67	mMinPvsSize = emptyViewCells ? 1 : 0;
68
69	char buf[50];
70	environment->GetStringValue("ViewCells.Visualization.colorCode", buf);
71
72	if (strcmp(buf, "PVS") == 0)
73	mColorCode = 1;
74	else if (strcmp(buf, "MergedLeaves") == 0)
75	mColorCode = 2;
76	else if (strcmp(buf, "MergedTreeDiff") == 0)
77	mColorCode = 3;
78	else
79	mColorCode = 0;
80
81	Debug << "colorCode: " << mColorCode << endl;
82	}
83
84
85	ViewCellsManager::~ViewCellsManager()
86	{
87	DEL_PTR(mRenderer);
88
89	if (!ViewCellsTreeConstructed())
90	CLEAR_CONTAINER(mViewCells);
91	else
92	DEL_PTR(mViewCellsTree);
93
94	CLEAR_CONTAINER(mMeshContainer);
95	}
96
97
98	int ViewCellsManager::CastPassSamples(const int samplesPerPass,
99	const int sampleType,
100	VssRayContainer &passSamples) const
101	{
102	SimpleRayContainer simpleRays;
103
104	preprocessor->GenerateRays(samplesPerPass,
105	sampleType,
106	simpleRays);
107
108	// shoot simple ray and add it to importance samples
109	preprocessor->CastRays(simpleRays, passSamples);
110
111	return (int)passSamples.size();
112	}
113
114
115
116	/// helper function which destroys rays or copies them into the output ray container
117	inline void disposeRays(VssRayContainer &rays, VssRayContainer *outRays)
118	{
119	cout << "disposing samples ... ";
120	long startTime = GetTime();
121	int n = (int)rays.size();
122
123	if (outRays)
124	{
125	VssRayContainer::const_iterator it, it_end = rays.end();
126
127	for (it = rays.begin(); it != it_end; ++ it)
128	{
129	outRays->push_back(*it);
130	}
131	}
132	else
133	{
134	VssRayContainer::const_iterator it, it_end = rays.end();
135
136	for (it = rays.begin(); it != it_end; ++ it)
137	{
138	//(*it)->Unref();
139	if (!(*it)->IsActive())
140	delete (*it);
141	}
142	}
143
144	cout << "finished" << endl;
145	Debug << "disposed " << n << " samples in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
146	}
147
148
149	int ViewCellsManager::Construct(Preprocessor preprocessor, VssRayContainer outRays)
150	{
151	int numSamples = 0;
152	SimpleRayContainer simpleRays;
153
154	VssRayContainer initialSamples;
155
156	cout << "view cell construction: casting " << mInitialSamples << " initial samples ... ";
157	//-- construction rays => we use uniform samples for this
158	CastPassSamples(mInitialSamples,
159	//Preprocessor::DIRECTION_BASED_DISTRIBUTION,
160	Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION,
161	initialSamples);
162
163	cout << "finished" << endl;
164
165	// construct view cells
166	const int numInitialSamples =
167	ConstructSubdivision(preprocessor->mObjects, initialSamples);
168
169	numSamples += numInitialSamples;
170
171	// rays can be passed or deleted
172	disposeRays(initialSamples, outRays);
173
174
175	//-- guided rays are used for further sampling
176	const int n = mConstructionSamples; //+initialSamples;
177
178	bool dirSamples = false;
179
180	while (numSamples < n)
181	{
182	cout << "casting " << mSamplesPerPass << " samples of " << n << " ... ";
183	VssRayContainer constructionSamples;
184
185	const int samplingType =
186	dirSamples ?
187	Preprocessor::DIRECTION_BASED_DISTRIBUTION :
188	Preprocessor::SPATIAL_BOX_BASED_DISTRIBUTION;
189
190	if (0)
191	dirSamples = !dirSamples; // toggle sampling method
192	numSamples += CastPassSamples(mSamplesPerPass,
193	samplingType,
194	constructionSamples);
195
196	cout << "finished" << endl;
197
198	cout << "computing sample contribution for " << (int)constructionSamples.size() << " samples ... ";
199
200	// TODO: leak?
201	if (SAMPLE_AFTER_SUBDIVISION)
202	ComputeSampleContributions(constructionSamples, true, false);
203	cout << "finished" << endl;
204
205
206	disposeRays(constructionSamples, outRays);
207
208	cout << "total samples: " << numSamples << endl;
209	}
210
211
212	//-- post processing
213	VssRayContainer postProcessSamples;
214
215	//-- construction rays => we use uniform samples for this
216	CastPassSamples(mPostProcessSamples,
217	Preprocessor::DIRECTION_BASED_DISTRIBUTION,
218	postProcessSamples);
219
220	cout << "starting post processing and visualization" << endl;
221
222	// store viewCells for postprocessing
223	const bool storeViewCells = true;
224
225	if (SAMPLE_AFTER_SUBDIVISION)
226	ComputeSampleContributions(postProcessSamples, true, storeViewCells);
227	// merge the view cells
228	PostProcess(preprocessor->mObjects, postProcessSamples);
229
230
231	//-- visualization
232	VssRayContainer visualizationSamples;
233
234	//-- construction rays => we use uniform samples for this
235	CastPassSamples(mVisualizationSamples,
236	Preprocessor::DIRECTION_BASED_DISTRIBUTION,
237	visualizationSamples);
238
239	if (SAMPLE_AFTER_SUBDIVISION)
240	ComputeSampleContributions(visualizationSamples, true, storeViewCells);
241
242	//Debug << "visualizationsamples: " << mVisualizationSamples << " " << visualizationSamples.size() << endl;
243	// different visualizations
244	Visualize(preprocessor->mObjects, visualizationSamples);
245
246	disposeRays(visualizationSamples, outRays);
247
248	return numSamples;
249	}
250
251
252	bool ViewCellsManager::CheckValidity(ViewCell *vc,
253	int minPvsSize,
254	int maxPvsSize) const
255	{
256
257	if ((vc->GetPvs().GetSize() > maxPvsSize) \|\|
258	(vc->GetPvs().GetSize() < minPvsSize))
259	{
260	return false;
261	}
262
263	return true;
264	}
265
266
267	bool ViewCellsManager::ViewCellsTreeConstructed() const
268	{
269	return mViewCellsTree->GetRoot();
270	}
271
272
273	void ViewCellsManager::SetValidity(ViewCell *vc,
274	int minPvs,
275	int maxPvs) const
276	{
277	vc->SetValid(CheckValidity(vc, minPvs, maxPvs));
278	}
279
280
281	void
282	ViewCellsManager::SetValidity(
283	int minPvsSize,
284	int maxPvsSize) const
285	{
286	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
287
288	for (it = mViewCells.begin(); it != it_end; ++ it) {
289	SetValidity(*it, minPvsSize, maxPvsSize);
290	}
291	}
292
293	void
294	ViewCellsManager::SetValidityPercentage(
295	const float minValid,
296	const float maxValid
297	)
298	{
299	sort(mViewCells.begin(), mViewCells.end(), ViewCell::SmallerPvs);
300
301	int start = mViewCells.size()*minValid;
302	int end = mViewCells.size()*maxValid;
303
304	for (int i=0; i < mViewCells.size(); i++)
305	mViewCells[i]->SetValid(i >= start && i <= end);
306	}
307
308	int
309	ViewCellsManager::CountValidViewcells() const
310	{
311	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
312	int valid = 0;
313	for (it = mViewCells.begin(); it != it_end; ++ it) {
314	if ((*it)->GetValid())
315	valid++;
316	}
317	return valid;
318	}
319
320
321	bool ViewCellsManager::LoadViewCellsGeometry(const string filename)
322	{
323	X3dParser parser;
324
325	environment->GetFloatValue("ViewCells.height", parser.mViewCellHeight);
326
327	bool success = parser.ParseFile(filename, *this);
328	Debug << (int)mViewCells.size() << " view cells loaded" << endl;
329
330	return success;
331	}
332
333
334	bool ViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
335	{
336	viewPoint = mViewSpaceBox.GetRandomPoint();
337
338	return true;
339	}
340
341
342	float ViewCellsManager::GetViewSpaceVolume()
343	{
344	return mViewSpaceBox.GetVolume() * (2.0f * sqr((float)M_PI));
345	}
346
347
348	bool ViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
349	{
350	if (!ViewCellsConstructed())
351	return mViewSpaceBox.IsInside(viewPoint);
352	else {
353	if (!mViewSpaceBox.IsInside(viewPoint))
354	return false;
355	ViewCell *viewcell = GetViewCell(viewPoint);
356	if (!viewcell \|\| !viewcell->GetValid())
357	return false;
358	}
359	return true;
360	}
361
362
363	float
364	ViewCellsManager::ComputeSampleContributions(const VssRayContainer &rays,
365	const bool addRays,
366	const bool storeViewCells
367	)
368	{
369	// view cells not yet constructed
370	if (!ViewCellsConstructed())
371	return 0.0f;
372
373	VssRayContainer::const_iterator it, it_end = rays.end();
374
375	float sum = 0.0f;
376	for (it = rays.begin(); it != it_end; ++ it) {
377	sum += ComputeSampleContributions((it), addRays, storeViewCells);
378	//ComputeSampleContributions((it), addRays);
379	// sum += (*it)->mPvsContribution;
380	}
381	return sum;
382	}
383
384
385	void ViewCellsManager::EvaluateViewCellsStats()
386	{
387	mViewCellsStats.Reset();
388
389	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
390
391	for (it = mViewCells.begin(); it != it_end; ++ it)
392	{
393	mViewCellsTree->UpdateViewCellsStats(*it, mViewCellsStats);
394	}
395	}
396
397
398	void ViewCellsManager::EvaluateRenderStatistics(float &totalRenderCost,
399	float &expectedRenderCost,
400	float &deviation,
401	float &variance,
402	int &totalPvs,
403	float &avgRenderCost)
404	{
405	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
406
407
408	//-- compute expected value
409
410	totalRenderCost = 0;
411	totalPvs = 0;
412
413	for (it = mViewCells.begin(); it != it_end; ++ it)
414	{
415	ViewCell vc = it;
416	totalRenderCost += vc->GetPvs().GetSize() * vc->GetVolume();
417	totalPvs += (int)vc->GetPvs().GetSize();
418	}
419
420	// normalize with view space box
421	totalRenderCost /= mViewSpaceBox.GetVolume();
422	expectedRenderCost = totalRenderCost / (float)mViewCells.size();
423	avgRenderCost = totalPvs / (float)mViewCells.size();
424
425
426	//-- compute standard defiation
427	variance = 0;
428	deviation = 0;
429
430	for (it = mViewCells.begin(); it != it_end; ++ it)
431	{
432	ViewCell vc = it;
433
434	float renderCost = vc->GetPvs().GetSize() * vc->GetVolume();
435	float dev;
436
437	if (1)
438	dev = fabs(avgRenderCost - (float)vc->GetPvs().GetSize());
439	else
440	dev = fabs(expectedRenderCost - renderCost);
441
442	deviation += dev;
443	variance += dev * dev;
444	}
445
446	variance /= (float)mViewCells.size();
447	deviation /= (float)mViewCells.size();
448	}
449
450
451
452	void ViewCellsManager::AddViewCell(ViewCell *viewCell)
453	{
454	mViewCells.push_back(viewCell);
455	}
456
457
458	float ViewCellsManager::GetArea(ViewCell *viewCell) const
459	{
460	return viewCell->GetArea();
461	}
462
463
464	float ViewCellsManager::GetVolume(ViewCell *viewCell) const
465	{
466	return viewCell->GetVolume();
467	}
468
469
470	void ViewCellsManager::DeriveViewCells(const ObjectContainer &objects,
471	ViewCellContainer &viewCells,
472	const int maxViewCells) const
473	{
474	// maximal max viewcells
475	int limit = maxViewCells > 0 ?
476	Min((int)objects.size(), maxViewCells) : (int)objects.size();
477
478	for (int i = 0; i < limit; ++ i)
479	{
480	Intersectable *object = objects[i];
481
482	// extract the mesh instances
483	if (object->Type() == Intersectable::MESH_INSTANCE)
484	{
485	MeshInstance inst = dynamic_cast<MeshInstance >(object);
486
487	ViewCell *viewCell = GenerateViewCell(inst->GetMesh());
488	viewCells.push_back(viewCell);
489	}
490	//TODO: transformed meshes
491	}
492	}
493
494
495	ViewCell *ViewCellsManager::ExtrudeViewCell(const Triangle3 &baseTri,
496	const float height) const
497	{
498	// one mesh per view cell
499	Mesh *mesh = new Mesh();
500
501	//-- construct prism
502
503	// bottom
504	mesh->mFaces.push_back(new Face(2,1,0));
505	// top
506	mesh->mFaces.push_back(new Face(3,4,5));
507	// sides
508	mesh->mFaces.push_back(new Face(1, 4, 3, 0));
509	mesh->mFaces.push_back(new Face(2, 5, 4, 1));
510	mesh->mFaces.push_back(new Face(3, 5, 2, 0));
511
512	//--- extrude new vertices for top of prism
513	Vector3 triNorm = baseTri.GetNormal();
514
515	Triangle3 topTri;
516
517	// add base vertices and calculate top vertices
518	for (int i = 0; i < 3; ++ i)
519	mesh->mVertices.push_back(baseTri.mVertices[i]);
520
521	// add top vertices
522	for (int i = 0; i < 3; ++ i)
523	mesh->mVertices.push_back(baseTri.mVertices[i] + height * triNorm);
524
525	mesh->Preprocess();
526
527	return GenerateViewCell(mesh);
528	}
529
530
531	void ViewCellsManager::FinalizeViewCells(const bool createMesh)
532	{
533	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
534	for (it = mViewCells.begin(); it != it_end; ++ it)
535	{
536	Finalize(*it, createMesh);
537	}
538
539	mTotalAreaValid = false;
540	}
541
542
543	void ViewCellsManager::Finalize(ViewCell *viewCell, const bool createMesh)
544	{
545	// implemented in subclasses
546	}
547
548
549	ViewCellInterior ViewCellsManager::MergeViewCells(ViewCell left, ViewCell *right) const
550	{
551	// generate parent view cell
552	ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();
553
554	vc->GetPvs() = left->GetPvs();
555	// merge pvs
556	vc->GetPvs().Merge(right->GetPvs());
557
558	//-- merge ray sets
559	if (0)
560	{
561	stable_sort(left->mPiercingRays.begin(), left->mPiercingRays.end());
562	stable_sort(right->mPiercingRays.begin(), right->mPiercingRays.end());
563
564	std::merge(left->mPiercingRays.begin(), left->mPiercingRays.end(),
565	right->mPiercingRays.begin(), right->mPiercingRays.end(),
566	vc->mPiercingRays.begin());
567	}
568
569
570	vc->SetupChildLink(left);
571	vc->SetupChildLink(right);
572
573
574	return vc;
575	}
576
577
578	ViewCellInterior *ViewCellsManager::MergeViewCells(ViewCellContainer &children) const
579	{
580	ViewCellInterior *vc = new ViewCellInterior();//GenerateViewCell();
581
582	ViewCellContainer::const_iterator it, it_end = children.end();
583
584	for (it = children.begin(); it != it_end; ++ it)
585	{
586	// merge pvs
587	vc->GetPvs().Merge((*it)->GetPvs());
588
589	vc->SetupChildLink(*it);
590	}
591
592	return vc;
593	}
594
595
596	void ViewCellsManager::SetRenderer(Renderer *renderer)
597	{
598	mRenderer = renderer;
599	}
600
601
602	ViewCellsTree *ViewCellsManager::GetViewCellsTree()
603	{
604	return mViewCellsTree;
605	}
606
607
608	void ViewCellsManager::SetVisualizationSamples(const int visSamples)
609	{
610	mVisualizationSamples = visSamples;
611	}
612
613
614	void ViewCellsManager::SetConstructionSamples(const int constructionSamples)
615	{
616	mConstructionSamples = constructionSamples;
617	}
618
619
620	void ViewCellsManager::SetInitialSamples(const int initialSamples)
621	{
622	mInitialSamples = initialSamples;
623	}
624
625
626	void ViewCellsManager::SetPostProcessSamples(const int postProcessSamples)
627	{
628	mPostProcessSamples = postProcessSamples;
629	}
630
631
632	int ViewCellsManager::GetVisualizationSamples() const
633	{
634	return mVisualizationSamples;
635	}
636
637
638	int ViewCellsManager::GetConstructionSamples() const
639	{
640	return mConstructionSamples;
641	}
642
643
644	int ViewCellsManager::GetPostProcessSamples() const
645	{
646	return mPostProcessSamples;
647	}
648
649
650	void ViewCellsManager::GetPvsStatistics(PvsStatistics &stat)
651	{
652	ViewCellContainer::const_iterator it = mViewCells.begin();
653	stat.viewcells = 0;
654	stat.minPvs = 100000000;
655	stat.maxPvs = 0;
656	stat.avgPvs = 0.0f;
657
658	for (; it != mViewCells.end(); ++it) {
659	ViewCell viewcell = it;
660	int pvsSize = viewcell->GetPvs().GetSize();
661	if ( pvsSize < stat.minPvs)
662	stat.minPvs = pvsSize;
663	if (pvsSize > stat.maxPvs)
664	stat.maxPvs = pvsSize;
665	stat.avgPvs += pvsSize;
666	stat.viewcells++;
667	}
668	if (stat.viewcells)
669	stat.avgPvs/=stat.viewcells;
670	}
671
672
673	void ViewCellsManager::PrintPvsStatistics(ostream &s)
674	{
675	s<<"############# Viewcell PVS STAT ##################\n";
676	PvsStatistics pvsStat;
677	GetPvsStatistics(pvsStat);
678	s<<"#AVG_PVS\n"<<pvsStat.avgPvs<<endl;
679	s<<"#MAX_PVS\n"<<pvsStat.maxPvs<<endl;
680	s<<"#MIN_PVS\n"<<pvsStat.minPvs<<endl;
681	}
682
683
684	int ViewCellsManager::CastBeam(Beam &beam)
685	{
686	return 0;
687	}
688
689
690	ViewCellContainer &ViewCellsManager::GetViewCells()
691	{
692	return mViewCells;
693	}
694
695
696	void ViewCellsManager::SetViewSpaceBox(const AxisAlignedBox3 &box)
697	{
698	mViewSpaceBox = box;
699
700	CreateCuttingPlane();
701
702	mTotalAreaValid = false;
703	}
704
705
706	void ViewCellsManager::CreateCuttingPlane()
707	{
708	int axis = 0;
709
710	const float factor = 0.65;
711	Vector3 point = mViewSpaceBox.Min() + mViewSpaceBox.Size() * factor;
712
713	if (mUseCuttingPlaneForViz)
714	environment->GetIntValue("ViewCells.Visualization.cuttingPlaneAxis", axis);
715
716	Vector3 normal(0,0,0);
717	normal[axis] = 1;
718
719	mCuttingPlane = Plane3(normal, point);
720	}
721
722
723	AxisAlignedBox3 ViewCellsManager::GetViewSpaceBox() const
724	{
725	return mViewSpaceBox;
726	}
727
728
729	void ViewCellsManager::ResetViewCells()
730	{
731	mViewCells.clear();
732
733	CollectViewCells();
734
735	mViewCellsStats.Reset();
736	EvaluateViewCellsStats();
737
738	// has to be recomputed
739	mTotalAreaValid = false;
740	}
741
742
743	int ViewCellsManager::GetMaxPvsSize() const
744	{
745	return mMaxPvsSize;
746	}
747
748
749	void
750	ViewCellsManager::AddSampleContributions(const VssRayContainer &rays)
751	{
752	if (!ViewCellsConstructed())
753	return;
754
755	VssRayContainer::const_iterator it, it_end = rays.end();
756
757	for (it = rays.begin(); it != it_end; ++ it) {
758	AddSampleContributions((it));
759	}
760	}
761
762
763	int ViewCellsManager::GetMinPvsSize() const
764	{
765	return mMinPvsSize;
766	}
767
768
769
770	float ViewCellsManager::GetMaxPvsRatio() const
771	{
772	return mMaxPvsRatio;
773	}
774
775
776	void
777	ViewCellsManager::AddSampleContributions(VssRay &ray)
778	{
779	// assumes viewcells have been stored...
780	ViewCellContainer *viewcells = &ray.mViewCells;
781	ViewCellContainer::const_iterator it;
782	for (it = viewcells->begin(); it != viewcells->end(); ++it) {
783	ViewCell viewcell = it;
784	if (viewcell->GetValid()) {
785	// if ray not outside of view space
786	viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
787	}
788	}
789	}
790
791
792	float ViewCellsManager::ComputeSampleContributions(VssRay &ray,
793	const bool addRays,
794	const bool storeViewCells)
795	{
796	ViewCellContainer viewcells;
797
798	ray.mPvsContribution = 0;
799	ray.mRelativePvsContribution = 0.0f;
800
801	static Ray hray;
802	hray.Init(ray);
803	//hray.mFlags \|= Ray::CULL_BACKFACES;
804	//Ray hray(ray);
805
806	float tmin = 0, tmax = 1.0;
807
808	if (!GetViewSpaceBox().GetRaySegment(hray, tmin, tmax) \|\| (tmin > tmax))
809	return 0;
810
811	Vector3 origin = hray.Extrap(tmin);
812	Vector3 termination = hray.Extrap(tmax);
813
814	CastLineSegment(origin, termination, viewcells);
815	//Debug << "constribution: " << (int)viewcells.size() << endl;
816
817	// copy viewcells memory efficiently
818	//const bool storeViewcells = !addRays;
819
820	if (storeViewCells)
821	{
822	ray.mViewCells.reserve(viewcells.size());
823	ray.mViewCells = viewcells;
824	}
825
826	ViewCellContainer::const_iterator it = viewcells.begin();
827
828
829	for (; it != viewcells.end(); ++it) {
830	ViewCell viewcell = it;
831	if (viewcell->GetValid()) {
832	// if ray not outside of view space
833	float contribution;
834	if (viewcell->GetPvs().GetSampleContribution(ray.mTerminationObject,
835	ray.mPdf,
836	contribution
837	))
838	ray.mPvsContribution++;
839	ray.mRelativePvsContribution += contribution;
840	}
841	}
842
843	if (addRays)
844	for (it = viewcells.begin(); it != viewcells.end(); ++it) {
845	ViewCell viewcell = it;
846	if (viewcell->GetValid()) {
847	// if ray not outside of view space
848	viewcell->GetPvs().AddSample(ray.mTerminationObject, ray.mPdf);
849	}
850	}
851
852	return ray.mRelativePvsContribution;
853	}
854
855
856	void ViewCellsManager::GetRaySets(const VssRayContainer &sourceRays,
857	const int maxSize,
858	VssRayContainer &usedRays,
859	VssRayContainer *savedRays) const
860	{
861	const int limit = min(maxSize, (int)sourceRays.size());
862	const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small);
863
864	VssRayContainer::const_iterator it, it_end = sourceRays.end();
865	for (it = sourceRays.begin(); it != it_end; ++ it)
866	{
867	if (Random(1.0f) < prop)
868	usedRays.push_back(*it);
869	else if (savedRays)
870	savedRays->push_back(*it);
871	}
872	}
873
874
875	float ViewCellsManager::GetRendercost(ViewCell *viewCell, float objRendercost) const
876	{
877	return mViewCellsTree->GetPvsSize(viewCell) * objRendercost;
878	}
879
880
881	float ViewCellsManager::GetAccVcArea()
882	{
883	// if already computed
884	if (mTotalAreaValid)
885	return mTotalArea;
886
887	mTotalArea = 0;
888	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
889
890	for (it = mViewCells.begin(); it != it_end; ++ it)
891	{
892	//Debug << "area: " << GetArea(*it);
893	mTotalArea += GetArea(*it);
894	}
895
896	mTotalAreaValid = true;
897
898	return mTotalArea;
899	}
900
901
902	void ViewCellsManager::PrintStatistics(ostream &s) const
903	{
904	s << mViewCellsStats << endl;
905	}
906
907
908	void ViewCellsManager::CreateUniqueViewCellIds()
909	{
910	for (int i = 0; i < (int)mViewCells.size(); ++ i)
911	mViewCells[i]->SetId(i);
912	}
913
914
915	void ViewCellsManager::ExportViewCellsForViz(Exporter *exporter) const
916	{
917	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
918
919	for (it = mViewCells.begin(); it != it_end; ++ it)
920	{
921	if (!mOnlyValidViewCells \|\| (*it)->GetValid())
922	{
923	ExportColor(exporter, *it);
924	ExportViewCellGeometry(exporter, *it,
925	mUseCuttingPlaneForViz ? &mCuttingPlane : NULL);
926	}
927	}
928
929	}
930
931
932	void ViewCellsManager::CreateViewCellMeshes()
933	{
934	// convert to meshes
935	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
936
937	for (it = mViewCells.begin(); it != it_end; ++ it)
938	{
939	if (!(*it)->GetMesh())
940	CreateMesh(*it);
941	}
942	}
943
944
945	bool ViewCellsManager::ExportViewCells(const string filename)
946	{
947	return false;
948	}
949
950
951	void ViewCellsManager::CollectViewCells(const int n)
952	{
953	mNumActiveViewCells = n;
954	mViewCells.clear();
955	CollectViewCells();
956	}
957
958
959
960	/**********************************************************************/
961	/* BspViewCellsManager implementation */
962	/**********************************************************************/
963
964
965	BspViewCellsManager::BspViewCellsManager(BspTree *bspTree):
966	ViewCellsManager(), mBspTree(bspTree)
967	{
968	environment->GetIntValue("BspTree.Construction.samples", mInitialSamples);
969	mBspTree->SetViewCellsManager(this);
970	mBspTree->mViewCellsTree = mViewCellsTree;
971	}
972
973
974	bool BspViewCellsManager::ViewCellsConstructed() const
975	{
976	return mBspTree->GetRoot() != NULL;
977	}
978
979
980	ViewCell BspViewCellsManager::GenerateViewCell(Mesh mesh) const
981	{
982	return new BspViewCell(mesh);
983	}
984
985
986	int BspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
987	const VssRayContainer &rays)
988	{
989	// if view cells were already constructed
990	if (ViewCellsConstructed())
991	return 0;
992
993	int sampleContributions = 0;
994
995	// construct view cells using the collected samples
996	RayContainer constructionRays;
997	VssRayContainer savedRays;
998
999	const int limit = min(mInitialSamples, (int)rays.size());
1000
1001	VssRayContainer::const_iterator it, it_end = rays.end();
1002
1003	const float prop = (float)limit / ((float)rays.size() + Limits::Small);
1004
1005	for (it = rays.begin(); it != it_end; ++ it)
1006	{
1007	if (Random(1.0f) < prop)
1008	constructionRays.push_back(new Ray((it)));
1009	else
1010	savedRays.push_back(*it);
1011	}
1012
1013	if (mViewCells.empty())
1014	{
1015	// no view cells loaded
1016	mBspTree->Construct(objects, constructionRays, &mViewSpaceBox);
1017	// collect final view cells
1018	mBspTree->CollectViewCells(mViewCells);
1019	}
1020	else
1021	{
1022	mBspTree->Construct(mViewCells);
1023	}
1024
1025	// destroy rays created only for construction
1026	CLEAR_CONTAINER(constructionRays);
1027
1028	Debug << mBspTree->GetStatistics() << endl;
1029
1030	//EvaluateViewCellsStats();
1031	Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
1032
1033	// recast rest of the rays
1034	if (SAMPLE_AFTER_SUBDIVISION)
1035	ComputeSampleContributions(savedRays, true, false);
1036
1037
1038	ResetViewCells();
1039
1040	Debug << "\nView cells after " << (int)savedRays.size()
1041	<< " samples:\n" << mViewCellsStats << endl;
1042
1043	if (1) // export initial view cells
1044	{
1045	cout << "exporting initial view cells (=leaves) ... ";
1046	Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
1047
1048	if (exporter)
1049	{
1050
1051	if (0 && mExportRays)
1052	exporter->ExportRays(rays, RgbColor(1, 1, 1));
1053
1054
1055	if (mExportGeometry)
1056	exporter->ExportGeometry(objects);
1057
1058	//exporter->SetWireframe();
1059	exporter->SetFilled();
1060	ExportViewCellsForViz(exporter);
1061
1062
1063	delete exporter;
1064	}
1065	cout << "finished" << endl;
1066	}
1067
1068
1069	return sampleContributions;
1070	}
1071
1072
1073	void BspViewCellsManager::CollectViewCells()
1074	{
1075	// view cells tree constructed
1076	if (!ViewCellsTreeConstructed())
1077	{
1078	mBspTree->CollectViewCells(mViewCells);
1079	}
1080	else
1081	{
1082	// we can use the view cells tree hierarchy to get the right set
1083	mViewCellsTree->CollectBestViewCellSet(mViewCells,
1084	mNumActiveViewCells);
1085	}
1086	}
1087
1088
1089	float BspViewCellsManager::GetProbability(ViewCell *viewCell)
1090	{
1091	// compute view cell area as subsititute for probability
1092	if (1)
1093	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
1094	else
1095	return GetArea(viewCell) / GetAccVcArea();
1096	}
1097
1098
1099
1100	int BspViewCellsManager::CastLineSegment(const Vector3 &origin,
1101	const Vector3 &termination,
1102	ViewCellContainer &viewcells)
1103	{
1104	return mBspTree->CastLineSegment(origin, termination, viewcells);
1105	}
1106
1107
1108	int BspViewCellsManager::PostProcess(const ObjectContainer &objects,
1109	const VssRayContainer &rays)
1110	{
1111	if (!ViewCellsConstructed())
1112	{
1113	Debug << "view cells not constructed" << endl;
1114	return 0;
1115	}
1116
1117
1118	// view cells already finished before post processing step (i.e. because they were loaded)
1119	if (mViewCellsFinished)
1120	{
1121	FinalizeViewCells(true);
1122	EvaluateViewCellsStats();
1123
1124	return 0;
1125	}
1126
1127	//-- post processing of bsp view cells
1128
1129	int vcSize = 0;
1130	int pvsSize = 0;
1131
1132	EvaluateViewCellsStats();
1133	Debug << "\noriginal view cell partition:\n" << mViewCellsStats << endl;
1134
1135	mRenderer->RenderScene();
1136	SimulationStatistics ss;
1137	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
1138
1139	Debug << ss << endl;
1140
1141
1142
1143	//-- merge view cells
1144	int merged;
1145
1146	cout << "starting post processing using " << mPostProcessSamples << " samples ... ";
1147	long startTime = GetTime();
1148
1149	VssRayContainer postProcessRays;
1150	GetRaySets(rays, mPostProcessSamples, postProcessRays);
1151
1152	if (mMergeViewCells)
1153	{
1154	Debug << "constructing visibility based merge tree" << endl;
1155	merged = mViewCellsTree->ConstructMergeTree(rays, objects);
1156	}
1157	else
1158	{
1159	Debug << "constructing spatial merge tree" << endl;
1160	// create spatial merge hierarchy
1161	merged = ConstructSpatialMergeTree();
1162	}
1163
1164	//-- stats and visualizations
1165	cout << "finished" << endl;
1166	cout << "merged " << merged << " view cells in "
1167	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
1168
1169	Debug << "Postprocessing: Merged " << merged << " view cells in "
1170	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
1171
1172
1173	// reset view cells and stats
1174	ResetViewCells();
1175	Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
1176
1177	int savedColorCode = mColorCode;
1178
1179	//BspLeaf::NewMail();
1180	if (1) // export merged view cells
1181	{
1182	mColorCode = 0;
1183
1184	Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
1185
1186
1187	cout << "exporting view cells after merge ... ";
1188
1189	if (exporter)
1190	{
1191	if (mExportGeometry)
1192	exporter->ExportGeometry(objects);
1193
1194	//exporter->SetWireframe();
1195	exporter->SetFilled();
1196	ExportViewCellsForViz(exporter);
1197
1198
1199	delete exporter;
1200	}
1201	cout << "finished" << endl;
1202	}
1203
1204	if (1) // export merged view cells
1205	{
1206	mColorCode = 1;
1207
1208	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
1209
1210	cout << "exporting view cells after merge (pvs size) ... ";
1211
1212	if (exporter)
1213	{
1214	//exporter->SetWireframe();
1215
1216	if (mExportGeometry)
1217	exporter->ExportGeometry(objects);
1218
1219	//exporter->SetWireframe();
1220	exporter->SetFilled();
1221	ExportViewCellsForViz(exporter);
1222
1223	delete exporter;
1224	}
1225	cout << "finished" << endl;
1226	}
1227
1228	mColorCode = savedColorCode;
1229
1230	FinalizeViewCells(true);
1231
1232	// write view cells to disc
1233	if (mExportViewCells)
1234	{
1235	char buff[100];
1236	environment->GetStringValue("ViewCells.filename", buff);
1237	string vcFilename(buff);
1238
1239	ExportViewCells(buff);
1240	}
1241
1242	return merged;
1243	}
1244
1245
1246	BspViewCellsManager::~BspViewCellsManager()
1247	{
1248	}
1249
1250
1251	int BspViewCellsManager::GetType() const
1252	{
1253	return BSP;
1254	}
1255
1256
1257	void BspViewCellsManager::Visualize(const ObjectContainer &objects,
1258	const VssRayContainer &sampleRays)
1259	{
1260	if (!ViewCellsConstructed())
1261	return;
1262
1263	int savedColorCode = mColorCode;
1264
1265
1266
1267	if (1) // export final view cells
1268	{
1269	mColorCode = 1;
1270
1271	Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
1272
1273	cout << "exporting view cells after merge (pvs size) ... ";
1274
1275	if (exporter)
1276	{
1277	//exporter->SetWireframe();
1278
1279	if (mExportGeometry)
1280	exporter->ExportGeometry(objects);
1281
1282	//exporter->SetWireframe();
1283	exporter->SetFilled();
1284	ExportViewCellsForViz(exporter);
1285
1286	delete exporter;
1287	}
1288	cout << "finished" << endl;
1289	}
1290
1291	mColorCode = savedColorCode;
1292
1293	//-- visualization of the BSP splits
1294	bool exportSplits = false;
1295	environment->GetBoolValue("BspTree.Visualization.exportSplits", exportSplits);
1296
1297	if (exportSplits)
1298	{
1299	cout << "exporting splits ... ";
1300	ExportSplits(objects);
1301	cout << "finished" << endl;
1302	}
1303
1304	// export single view cells
1305	ExportBspPvs(objects);
1306	}
1307
1308
1309	inline bool vc_gt(ViewCell a, ViewCell b)
1310	{
1311	return a->GetPvs().GetSize() > b->GetPvs().GetSize();
1312	}
1313
1314
1315	void BspViewCellsManager::ExportSplits(const ObjectContainer &objects)
1316	{
1317	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
1318
1319	if (exporter)
1320	{
1321	//exporter->SetFilled();
1322
1323	if (mExportGeometry)
1324	exporter->ExportGeometry(objects);
1325
1326	Material m;
1327	m.mDiffuseColor = RgbColor(1, 0, 0);
1328	exporter->SetForcedMaterial(m);
1329	exporter->SetWireframe();
1330
1331	exporter->ExportBspSplits(*mBspTree, true);
1332
1333	//NOTE: take forced material, else big scenes cannot be viewed
1334	m.mDiffuseColor = RgbColor(0, 1, 0);
1335	exporter->SetForcedMaterial(m);
1336	//exporter->ResetForcedMaterial();
1337
1338	delete exporter;
1339	}
1340	}
1341
1342
1343	void BspViewCellsManager::ExportBspPvs(const ObjectContainer &objects)
1344	{
1345	const int leafOut = 10;
1346
1347	ViewCell::NewMail();
1348
1349	//-- some rays for output
1350	const int raysOut = min((int)mBspRays.size(), mVisualizationSamples);
1351
1352	cout << "visualization using " << mVisualizationSamples << " samples" << endl;
1353	Debug << "\nOutput view cells: " << endl;
1354
1355	// sort view cells to get largest view cells
1356	if (0)
1357	stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
1358
1359	int limit = min(leafOut, (int)mViewCells.size());
1360
1361	for (int i = 0; i < limit; ++ i)
1362	{
1363	cout << "creating output for view cell " << i << " ... ";
1364	VssRayContainer vcRays;
1365	Intersectable::NewMail();
1366	ViewCell *vc;
1367
1368	if (0)
1369	vc = mViewCells[i];
1370	else
1371	vc = mViewCells[Random((int)mViewCells.size())];
1372
1373	cout << "creating output for view cell " << i << " ... ";
1374
1375	if(0)
1376	{
1377	// check whether we can add the current ray to the output rays
1378	for (int k = 0; k < raysOut; ++ k)
1379	{
1380	BspRay *ray = mBspRays[k];
1381	for (int j = 0; j < (int)ray->intersections.size(); ++ j)
1382	{
1383	BspLeaf *leaf = ray->intersections[j].mLeaf;
1384	if (vc == leaf->GetViewCell())
1385	vcRays.push_back(ray->vssRay);
1386	}
1387	}
1388	}
1389
1390	//bspLeaves[j]->Mail();
1391	char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
1392
1393	Exporter *exporter = Exporter::GetExporter(s);
1394
1395	exporter->SetWireframe();
1396
1397	Material m;//= RandomMaterial();
1398	m.mDiffuseColor = RgbColor(0, 1, 0);
1399	exporter->SetForcedMaterial(m);
1400
1401	ExportViewCellGeometry(exporter, vc);
1402
1403	// export rays piercing this view cell
1404	exporter->ExportRays(vcRays, RgbColor(0, 1, 0));
1405
1406	m.mDiffuseColor = RgbColor(1, 0, 0);
1407	exporter->SetForcedMaterial(m);
1408
1409	ObjectPvsMap::const_iterator it,
1410	it_end = vc->GetPvs().mEntries.end();
1411
1412	exporter->SetFilled();
1413
1414	// output PVS of view cell
1415	for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
1416	{
1417	Intersectable intersect = (it).first;
1418
1419	if (!intersect->Mailed())
1420	{
1421	Material m = RandomMaterial();
1422	exporter->SetForcedMaterial(m);
1423
1424	exporter->ExportIntersectable(intersect);
1425	intersect->Mail();
1426	}
1427	}
1428
1429	DEL_PTR(exporter);
1430	cout << "finished" << endl;
1431	}
1432
1433	Debug << endl;
1434	}
1435
1436
1437	void BspViewCellsManager::ExportColor(Exporter *exporter,
1438	ViewCell *vc) const
1439	{
1440	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
1441
1442	float importance = 0;
1443	static Material m;
1444
1445	switch (mColorCode)
1446	{
1447	case 0: // Random
1448	{
1449	if (vcValid)
1450	{
1451	m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
1452	m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
1453	m.mDiffuseColor.b = 0.5f + RandomValue(0.0f, 0.5f);
1454	}
1455	else
1456	{
1457	m.mDiffuseColor.r = 0.0f;
1458	m.mDiffuseColor.g = 1.0f;
1459	m.mDiffuseColor.b = 0.0f;
1460	}
1461
1462	exporter->SetForcedMaterial(m);
1463	return;
1464	}
1465
1466	case 1: // pvs
1467	{
1468	importance = (float)vc->GetPvs().GetSize() /
1469	(float)mViewCellsStats.maxPvs;
1470
1471	}
1472	break;
1473	case 2: // merges
1474	{
1475	int lSize = mViewCellsTree->GetSize(vc);
1476	importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
1477	}
1478	//break;
1479	case 3: // merge tree differene
1480	{
1481	// TODO
1482	//importance = (float)GetMaxTreeDiff(vc) /
1483	// (float)(mVspBspTree->GetStatistics().maxDepth * 2);
1484
1485	}
1486	break;
1487	default:
1488	break;
1489	}
1490
1491	// special color code for invalid view cells
1492	m.mDiffuseColor.r = importance;
1493	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
1494	m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
1495
1496	//Debug << "importance: " << importance << endl;
1497	exporter->SetForcedMaterial(m);
1498	}
1499
1500
1501	void BspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
1502	ViewCell *vc,
1503	const Plane3 *cuttingPlane) const
1504	{
1505	if (vc->GetMesh())
1506	{
1507	exporter->ExportMesh(vc->GetMesh());
1508	return;
1509	}
1510
1511	BspNodeGeometry geom;
1512	mBspTree->ConstructGeometry(vc, geom);
1513
1514
1515	if (cuttingPlane)
1516	{
1517	BspNodeGeometry front;
1518	BspNodeGeometry back;
1519
1520	geom.SplitGeometry(front,
1521	back,
1522	*cuttingPlane,
1523	mViewSpaceBox,
1524	0.0001f);
1525
1526	if ((int)back.mPolys.size() >= 3)
1527	exporter->ExportPolygons(back.mPolys);
1528	}
1529	else
1530	{
1531
1532	exporter->ExportPolygons(geom.mPolys);
1533	}
1534	}
1535
1536
1537	void BspViewCellsManager::CreateMesh(ViewCell *vc)
1538	{
1539	if (vc->GetMesh())
1540	delete vc->GetMesh();
1541
1542	BspNodeGeometry geom;
1543
1544	mBspTree->ConstructGeometry(vc, geom);
1545
1546	Mesh *mesh = new Mesh();
1547	geom.AddToMesh(*mesh);
1548	vc->SetMesh(mesh);
1549	mMeshContainer.push_back(mesh);
1550	}
1551
1552
1553	void BspViewCellsManager::Finalize(ViewCell *viewCell,
1554	const bool createMesh)
1555	{
1556	CreateMesh(viewCell);
1557
1558	float area = 0;
1559	float volume = 0;
1560
1561	ViewCellContainer leaves;
1562	mViewCellsTree->CollectLeaves(viewCell, leaves);
1563
1564	ViewCellContainer::const_iterator it, it_end = leaves.end();
1565
1566	for (it = leaves.begin(); it != it_end; ++ it)
1567	{
1568	BspNodeGeometry geom;
1569	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
1570	mBspTree->ConstructGeometry(leaf, geom);
1571
1572	area += geom.GetArea();
1573	volume += geom.GetVolume();
1574	}
1575
1576	viewCell->SetVolume(volume);
1577	viewCell->SetArea(area);
1578	}
1579
1580
1581	ViewCell *BspViewCellsManager::GetViewCell(const Vector3 &point) const
1582	{
1583	if (!mBspTree)
1584	return NULL;
1585
1586	if (!mViewSpaceBox.IsInside(point))
1587	return NULL;
1588
1589	return mBspTree->GetViewCell(point);
1590	}
1591
1592
1593	void BspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
1594	vector<MergeCandidate> &candidates)
1595	{
1596	cout << "collecting merge candidates ... " << endl;
1597
1598	if (mUseRaysForMerge)
1599	{
1600	mBspTree->CollectMergeCandidates(rays, candidates);
1601	}
1602	else
1603	{
1604	vector<BspLeaf *> leaves;
1605	mBspTree->CollectLeaves(leaves);
1606	mBspTree->CollectMergeCandidates(leaves, candidates);
1607	}
1608
1609	cout << "fininshed collecting candidates" << endl;
1610	}
1611
1612
1613
1614	bool BspViewCellsManager::ExportViewCells(const string filename)
1615	{
1616	cout << "exporting view cells to xml ... ";
1617	std::ofstream stream;
1618
1619	// for output we need unique ids for each view cell
1620	CreateUniqueViewCellIds();
1621
1622
1623	stream.open(filename.c_str());
1624	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
1625	stream << "<Visibility_Solution>" << endl;
1626
1627	//-- the view space bounding box
1628	stream << "<ViewSpaceBox"
1629	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
1630	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
1631
1632	//-- the type of the view cells hierarchy
1633	//stream << "<Hierarchy name=\"bspTree\" />" << endl;
1634	stream << "<Hierarchy name=\"vspBspTree\" />" << endl; // write vsp bsp here because can use same tree and is bug free
1635	//-- load the view cells itself, i.e., the ids and the pvs
1636	stream << "<ViewCells>" << endl;
1637
1638	#if 0
1639
1640	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1641
1642	for (it = mViewCells.begin(); it != it_end; ++ it)
1643	ExportViewCell(*it, stream);
1644	#else
1645	mViewCellsTree->Export(stream);
1646	#endif
1647
1648	stream << "</ViewCells>" << endl;
1649
1650	//-- load the hierarchy
1651	stream << "<Hierarchy>" << endl;
1652	mBspTree->Export(stream);
1653	stream << endl << "</Hierarchy>" << endl;
1654
1655	stream << "</Visibility_Solution>" << endl;
1656	stream.close();
1657
1658	cout << "finished" << endl;
1659
1660	return true;
1661	}
1662
1663
1664	void BspViewCellsManager::AddCurrentViewCellsToHierarchy()
1665	{
1666	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
1667	for (it = mViewCells.begin(); it != it_end; ++ it)
1668	{
1669	ViewCell vc = it;
1670	ViewCellContainer leaves;
1671	mViewCellsTree->CollectLeaves(vc, leaves);
1672
1673	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
1674
1675	for (lit = leaves.begin(); lit != lit_end; ++ lit)
1676	{
1677	BspViewCell bspVc = dynamic_cast<BspViewCell >(*lit);
1678	bspVc->mLeaf->SetViewCell(vc);
1679	}
1680	}
1681	}
1682
1683
1684	int BspViewCellsManager::ConstructSpatialMergeTree()
1685	{
1686	TraversalQueue tQueue;
1687
1688	tQueue.push(TraversalData(mBspTree->GetRoot(), NULL));
1689
1690	int merged = 0;
1691
1692	int numViewCells = (int)mViewCells.size();
1693
1694	float var = 0;
1695	float dev = 0;
1696	int totalPvs = 0;
1697	float totalRenderCost = 0;
1698	float avgRenderCost = 0;
1699	float expCost = 0;
1700
1701	//-- compute statistics values of initial view cells
1702	EvaluateRenderStatistics(totalRenderCost,
1703	expCost,
1704	dev,
1705	var,
1706	totalPvs,
1707	avgRenderCost);
1708
1709	Debug/mStats/ << "#Pass\n" << 0 << endl
1710	<< "#Merged\n" << merged << endl
1711	<< "#ViewCells\n" << numViewCells << endl
1712	<< "#RenderCostIncrease\n" << 0 << endl
1713	<< "#TotalRenderCost\n" << totalRenderCost << endl
1714	<< "#CurrentPvs\n" << 0 << endl
1715	<< "#ExpectedCost\n" << expCost << endl
1716	<< "#AvgRenderCost\n" << avgRenderCost << endl
1717	<< "#Deviation\n" << dev << endl
1718	<< "#TotalPvs\n" << totalPvs << endl
1719	<< "#PvsSizeDecrease\n0" << endl
1720	<< "#Volume\n0" << endl
1721	//<< "#Siblings\n" << mergeStats.siblings << endl
1722	<< endl;
1723
1724
1725	while (!tQueue.empty())
1726	{
1727	TraversalData tData = tQueue.top();
1728	tQueue.pop();
1729
1730	if (tData.mNode->IsLeaf())
1731	{
1732	ViewCell viewCell = dynamic_cast<BspLeaf >(tData.mNode)->GetViewCell();
1733	viewCell->SetMergeCost((float)tData.mNode->mTimeStamp);
1734
1735	Debug << "leaf time stamp: " << tData.mNode->mTimeStamp << endl;
1736
1737	if (tData.mParentViewCell)
1738	{
1739	tData.mParentViewCell->SetupChildLink(viewCell);
1740	// propagate up pvs: could be redone as propagepvs, which propagates pvs up and down
1741	mViewCellsTree->PropagateUpPvs(viewCell);
1742	}
1743	}
1744	else
1745	{
1746	BspInterior interior = dynamic_cast<BspInterior >(tData.mNode);
1747	ViewCellInterior *viewCellInterior = new ViewCellInterior();
1748
1749	++ merged;
1750	-- numViewCells;
1751
1752	avgRenderCost = totalPvs / numViewCells;
1753
1754	Debug//mStats
1755	<< "#Pass\n" << 0 << endl
1756	<< "#Merged\n" << merged << endl
1757	<< "#ViewCells\n" << numViewCells << endl
1758	<< "#RenderCostIncrease\n" << 0 << endl
1759	<< "#TotalRenderCost\n" << totalRenderCost << endl
1760	<< "#CurrentPvs\n" << 0 << endl
1761	<< "#ExpectedCost\n" << 0 << endl
1762	<< "#AvgRenderCost\n" << avgRenderCost << endl
1763	<< "#Deviation\n" << dev << endl
1764	<< "#TotalPvs\n" << totalPvs << endl
1765	<< "#PvsSizeDecrease\n" << 0 << endl
1766	<< "#Volume\n" << 0 << endl
1767	<< endl;
1768
1769	Debug << "interior time stamp: " << tData.mNode->mTimeStamp << endl;
1770
1771	viewCellInterior->SetMergeCost((float)tData.mNode->mTimeStamp);
1772
1773
1774	tQueue.push(TraversalData(interior->GetBack(), viewCellInterior));
1775	tQueue.push(TraversalData(interior->GetFront(), viewCellInterior));
1776
1777	if (tData.mParentViewCell)
1778	tData.mParentViewCell->SetupChildLink(viewCellInterior);
1779	}
1780	}
1781
1782	return merged;
1783	}
1784
1785	/************************************************************************/
1786	/* KdViewCellsManager implementation */
1787	/************************************************************************/
1788
1789
1790
1791	KdViewCellsManager::KdViewCellsManager(KdTree *kdTree):
1792	ViewCellsManager(), mKdTree(kdTree), mKdPvsDepth(100)
1793	{
1794	}
1795
1796
1797	float KdViewCellsManager::GetProbability(ViewCell *viewCell)
1798	{
1799	// compute view cell area / volume as subsititute for probability
1800	if (0)
1801	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
1802	else
1803	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
1804	}
1805
1806
1807
1808
1809	void KdViewCellsManager::CollectViewCells()
1810	{
1811	//mKdTree->CollectViewCells(mViewCells); TODO
1812	}
1813
1814
1815	int KdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
1816	const VssRayContainer &rays)
1817	{
1818	// if view cells already constructed
1819	if (ViewCellsConstructed())
1820	return 0;
1821
1822	mKdTree->Construct();
1823
1824	mTotalAreaValid = false;
1825	// create the view cells
1826	mKdTree->CreateAndCollectViewCells(mViewCells);
1827
1828	// cast rays
1829	ComputeSampleContributions(rays, true, false);
1830
1831	EvaluateViewCellsStats();
1832	Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
1833
1834	return 0;
1835	}
1836
1837
1838	bool KdViewCellsManager::ViewCellsConstructed() const
1839	{
1840	return mKdTree->GetRoot() != NULL;
1841	}
1842
1843	int KdViewCellsManager::PostProcess(const ObjectContainer &objects,
1844	const VssRayContainer &rays)
1845	{
1846	return 0;
1847	}
1848
1849	void KdViewCellsManager::Visualize(const ObjectContainer &objects,
1850	const VssRayContainer &sampleRays)
1851	{
1852	if (!ViewCellsConstructed())
1853	return;
1854
1855	// using view cells instead of the kd PVS of objects
1856	const bool useViewCells = true;
1857	bool exportRays = false;
1858
1859	int limit = min(mVisualizationSamples, (int)sampleRays.size());
1860	const int pvsOut = min((int)objects.size(), 10);
1861	VssRayContainer *rays = new VssRayContainer[pvsOut];
1862
1863	if (useViewCells)
1864	{
1865	const int leafOut = 10;
1866
1867	ViewCell::NewMail();
1868
1869	//-- some rays for output
1870	const int raysOut = min((int)sampleRays.size(), mVisualizationSamples);
1871	Debug << "visualization using " << raysOut << " samples" << endl;
1872
1873	//-- some random view cells and rays for output
1874	vector<KdLeaf *> kdLeaves;
1875
1876	for (int i = 0; i < leafOut; ++ i)
1877	kdLeaves.push_back(dynamic_cast<KdLeaf *>(mKdTree->GetRandomLeaf()));
1878
1879	for (int i = 0; i < kdLeaves.size(); ++ i)
1880	{
1881	KdLeaf *leaf = kdLeaves[i];
1882	RayContainer vcRays;
1883
1884	cout << "creating output for view cell " << i << " ... ";
1885	#if 0
1886	// check whether we can add the current ray to the output rays
1887	for (int k = 0; k < raysOut; ++ k)
1888	{
1889	Ray *ray = sampleRays[k];
1890
1891	for (int j = 0; j < (int)ray->bspIntersections.size(); ++ j)
1892	{
1893	BspLeaf *leaf2 = ray->bspIntersections[j].mLeaf;
1894
1895	if (leaf->GetViewCell() == leaf2->GetViewCell())
1896	{
1897	vcRays.push_back(ray);
1898	}
1899	}
1900	}
1901	#endif
1902	Intersectable::NewMail();
1903
1904	ViewCell *vc = leaf->mViewCell;
1905
1906	//bspLeaves[j]->Mail();
1907	char s[64]; sprintf(s, "kd-pvs%04d.x3d", i);
1908
1909	Exporter *exporter = Exporter::GetExporter(s);
1910	exporter->SetFilled();
1911
1912	exporter->SetWireframe();
1913	//exporter->SetFilled();
1914
1915	Material m;//= RandomMaterial();
1916	m.mDiffuseColor = RgbColor(1, 1, 0);
1917	exporter->SetForcedMaterial(m);
1918
1919	AxisAlignedBox3 box = mKdTree->GetBox(leaf);
1920	exporter->ExportBox(box);
1921
1922	// export rays piercing this view cell
1923	exporter->ExportRays(vcRays, 1000, RgbColor(0, 1, 0));
1924
1925	m.mDiffuseColor = RgbColor(1, 0, 0);
1926	exporter->SetForcedMaterial(m);
1927
1928	// exporter->SetWireframe();
1929	exporter->SetFilled();
1930
1931	ObjectPvsMap::iterator it, it_end = vc->GetPvs().mEntries.end();
1932	// output PVS of view cell
1933	for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
1934	{
1935	Intersectable intersect = (it).first;
1936	if (!intersect->Mailed())
1937	{
1938	exporter->ExportIntersectable(intersect);
1939	intersect->Mail();
1940	}
1941	}
1942
1943	DEL_PTR(exporter);
1944	cout << "finished" << endl;
1945	}
1946
1947	DEL_PTR(rays);
1948	}
1949	else // using kd PVS of objects
1950	{
1951	for (int i = 0; i < limit; ++ i)
1952	{
1953	VssRay *ray = sampleRays[i];
1954
1955	// check whether we can add this to the rays
1956	for (int j = 0; j < pvsOut; j++)
1957	{
1958	if (objects[j] == ray->mTerminationObject)
1959	{
1960	rays[j].push_back(ray);
1961	}
1962	}
1963	}
1964
1965	if (exportRays)
1966	{
1967	Exporter *exporter = NULL;
1968	exporter = Exporter::GetExporter("sample-rays.x3d");
1969	exporter->SetWireframe();
1970	exporter->ExportKdTree(*mKdTree);
1971
1972	for (i=0; i < pvsOut; i++)
1973	exporter->ExportRays(rays[i], RgbColor(1, 0, 0));
1974
1975	exporter->SetFilled();
1976
1977	delete exporter;
1978	}
1979
1980	for (int k=0; k < pvsOut; k++)
1981	{
1982	Intersectable *object = objects[k];
1983	char s[64];
1984	sprintf(s, "sample-pvs%04d.x3d", k);
1985
1986	Exporter *exporter = Exporter::GetExporter(s);
1987	exporter->SetWireframe();
1988
1989	KdPvsMap::iterator i = object->mKdPvs.mEntries.begin();
1990	Intersectable::NewMail();
1991
1992	// avoid adding the object to the list
1993	object->Mail();
1994	ObjectContainer visibleObjects;
1995
1996	for (; i != object->mKdPvs.mEntries.end(); i++)
1997	{
1998	KdNode node = (i).first;
1999	exporter->ExportBox(mKdTree->GetBox(node));
2000
2001	mKdTree->CollectObjects(node, visibleObjects);
2002	}
2003
2004	exporter->ExportRays(rays[k], RgbColor(0, 1, 0));
2005	exporter->SetFilled();
2006
2007	for (int j = 0; j < visibleObjects.size(); j++)
2008	exporter->ExportIntersectable(visibleObjects[j]);
2009
2010	Material m;
2011	m.mDiffuseColor = RgbColor(1, 0, 0);
2012	exporter->SetForcedMaterial(m);
2013	exporter->ExportIntersectable(object);
2014
2015	delete exporter;
2016	}
2017	}
2018	}
2019
2020
2021	void KdViewCellsManager::ExportColor(Exporter *exporter,
2022	ViewCell *vc) const
2023	{
2024	// TODO
2025	}
2026
2027	ViewCell KdViewCellsManager::GenerateViewCell(Mesh mesh) const
2028	{
2029	return new KdViewCell(mesh);
2030	}
2031
2032
2033	void KdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
2034	ViewCell *vc,
2035	const Plane3 *cuttingPlane) const
2036	{
2037	ViewCellContainer leaves;
2038
2039	mViewCellsTree->CollectLeaves(vc, leaves);
2040	ViewCellContainer::const_iterator it, it_end = leaves.end();
2041
2042	for (it = leaves.begin(); it != it_end; ++ it)
2043	{
2044	KdViewCell kdVc = dynamic_cast<KdViewCell >(*it);
2045
2046	exporter->ExportBox(mKdTree->GetBox(kdVc->mLeaf));
2047	}
2048	}
2049
2050
2051	int KdViewCellsManager::GetType() const
2052	{
2053	return ViewCellsManager::KD;
2054	}
2055
2056
2057
2058	KdNode KdViewCellsManager::GetNodeForPvs(KdLeaf leaf)
2059	{
2060	KdNode *node = leaf;
2061
2062	while (node->mParent && node->mDepth > mKdPvsDepth)
2063	node = node->mParent;
2064	return node;
2065	}
2066
2067	int KdViewCellsManager::CastLineSegment(const Vector3 &origin,
2068	const Vector3 &termination,
2069	ViewCellContainer &viewcells)
2070	{
2071	return mKdTree->CastLineSegment(origin, termination, viewcells);
2072	}
2073
2074
2075	void KdViewCellsManager::CreateMesh(ViewCell *vc)
2076	{
2077	// TODO
2078	}
2079
2080
2081
2082	void KdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2083	vector<MergeCandidate> &candidates)
2084	{
2085	// TODO
2086	}
2087
2088
2089	/**********************************************************************/
2090	/* VspKdViewCellsManager implementation */
2091	/**********************************************************************/
2092
2093
2094	VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree):
2095	ViewCellsManager(), mVspKdTree(vspKdTree)
2096	{
2097	environment->GetIntValue("VspKdTree.Construction.samples", mInitialSamples);
2098	mVspKdTree->SetViewCellsManager(this);
2099	}
2100
2101	float VspKdViewCellsManager::GetProbability(ViewCell *viewCell)
2102	{
2103	// compute view cell area / volume as subsititute for probability
2104	if (0)
2105	return GetArea(viewCell) / GetViewSpaceBox().SurfaceArea();
2106	else
2107	return GetVolume(viewCell) / GetViewSpaceBox().GetVolume();
2108	}
2109
2110
2111
2112
2113	void VspKdViewCellsManager::CollectViewCells()
2114	{
2115	mVspKdTree->CollectViewCells(mViewCells);
2116	}
2117
2118
2119	int VspKdViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2120	const VssRayContainer &rays)
2121	{
2122	// if view cells already constructed
2123	if (ViewCellsConstructed())
2124	return 0;
2125
2126	VssRayContainer constructionRays;
2127	VssRayContainer savedRays;
2128
2129	GetRaySets(rays,
2130	mInitialSamples,
2131	constructionRays,
2132	&savedRays);
2133
2134	Debug << "constructing vsp kd tree using "
2135	<< (int)constructionRays.size() << " samples" << endl;
2136
2137	mVspKdTree->Construct(constructionRays, &mViewSpaceBox);
2138	Debug << mVspKdTree->GetStatistics() << endl;
2139
2140	// export leaf building blocks
2141	ExportLeaves(objects, rays);
2142
2143	// finally merge kd leaf building blocks to view cells
2144	const int merged = mVspKdTree->MergeViewCells(rays);
2145
2146	// collapse siblings belonging to the same view cell
2147	mVspKdTree->RefineViewCells(rays);
2148
2149	// collapse siblings belonging to the same view cell
2150	mVspKdTree->CollapseTree();
2151
2152	// evaluale view cell stats
2153	ResetViewCells();
2154
2155	Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
2156
2157	long startTime = GetTime();
2158	// recast rest of rays
2159	ComputeSampleContributions(savedRays, true, false);
2160
2161	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
2162	<< " secs" << endl;
2163
2164	return merged;
2165	}
2166
2167	bool VspKdViewCellsManager::ViewCellsConstructed() const
2168	{
2169	return mVspKdTree->GetRoot() != NULL;
2170	}
2171
2172
2173	ViewCell VspKdViewCellsManager::GenerateViewCell(Mesh mesh) const
2174	{
2175	return new VspKdViewCell(mesh);
2176	}
2177
2178	int VspKdViewCellsManager::PostProcess(const ObjectContainer &objects,
2179	const VssRayContainer &rays)
2180	{
2181	if (!ViewCellsConstructed())
2182	return 0;
2183
2184	// recalculate stats
2185	EvaluateViewCellsStats();
2186
2187	return 0;
2188	}
2189
2190
2191	void VspKdViewCellsManager::ExportLeaves(const ObjectContainer &objects,
2192	const VssRayContainer &sampleRays)
2193	{
2194	if (!ViewCellsConstructed())
2195	return;
2196
2197	//-- export leaf building blocks
2198	Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d");
2199	if (!exporter)
2200	return;
2201
2202	if (mExportGeometry)
2203	exporter->ExportGeometry(objects);
2204
2205	//exporter->SetWireframe();
2206	//exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize);
2207	exporter->ExportVspKdTree(*mVspKdTree);
2208
2209	if (mExportRays)
2210	{
2211	const float prob = (float)mVisualizationSamples
2212	/ ((float)sampleRays.size() + Limits::Small);
2213
2214	exporter->SetWireframe();
2215
2216	//-- collect uniformly distributed rays
2217	VssRayContainer rays;
2218
2219	for (int i = 0; i < sampleRays.size(); ++ i)
2220	{
2221	if (RandomValue(0,1) < prob)
2222	rays.push_back(sampleRays[i]);
2223	}
2224	exporter->ExportRays(rays, RgbColor(1, 0, 0));
2225	}
2226
2227	delete exporter;
2228	}
2229
2230	void VspKdViewCellsManager::Visualize(const ObjectContainer &objects,
2231	const VssRayContainer &sampleRays)
2232	{
2233	if (!ViewCellsConstructed())
2234	return;
2235
2236	//-- export single view cells
2237	for (int i = 0; i < 10; ++ i)
2238	{
2239	char s[64];
2240	sprintf(s, "vsp_viewcell%04d.x3d", i);
2241	Exporter *exporter = Exporter::GetExporter(s);
2242	const int idx =
2243	(int)RandomValue(0.0, (Real)((int)mViewCells.size() - 1));
2244
2245	VspKdViewCell vc = dynamic_cast<VspKdViewCell >(mViewCells[idx]);
2246
2247	//-- export geometry
2248	Material m;
2249	m.mDiffuseColor = RgbColor(0, 1, 1);
2250
2251	exporter->SetForcedMaterial(m);
2252	exporter->SetWireframe();
2253
2254	ExportViewCellGeometry(exporter, vc);
2255
2256	//-- export stored rays
2257
2258	if (mExportRays)
2259	{
2260	ViewCellContainer leaves;
2261	mViewCellsTree->CollectLeaves(vc, leaves);
2262
2263	ViewCellContainer::const_iterator it,
2264	it_end = leaves.end();
2265
2266	for (it = leaves.begin(); it != it_end; ++ it)
2267	{
2268	VspKdViewCell vspKdVc = dynamic_cast<VspKdViewCell >(*it);
2269	VspKdLeaf *leaf = vspKdVc->mLeaf;
2270	AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf);
2271
2272	VssRayContainer vssRays;
2273
2274	VssRayContainer castRays;
2275	VssRayContainer initRays;
2276
2277	leaf->GetRays(vssRays);
2278
2279	VssRayContainer::const_iterator it, it_end = vssRays.end();
2280	const float prop = 200.0f / (float)vssRays.size();
2281
2282	for (it = vssRays.begin(); it != it_end; ++ it)
2283	{
2284	if (Random(1) < prop)
2285	if ((*it)->mTerminationObject == NULL)
2286	castRays.push_back(*it);
2287	else
2288	initRays.push_back(*it);
2289	}
2290
2291	exporter->ExportRays(castRays, RgbColor(1, 0, 0));
2292	exporter->ExportRays(initRays, RgbColor(0, 1, 0));
2293	}
2294	}
2295
2296	//-- output PVS of view cell
2297	m.mDiffuseColor = RgbColor(1, 0, 0);
2298	exporter->SetForcedMaterial(m);
2299
2300	Intersectable::NewMail();
2301
2302	ObjectPvsMap::const_iterator it,
2303	it_end = vc->GetPvs().mEntries.end();
2304
2305	exporter->SetFilled();
2306
2307	for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
2308	{
2309	Intersectable intersect = (it).first;
2310
2311	if (!intersect->Mailed())
2312	{
2313	Material m = RandomMaterial();
2314	exporter->SetForcedMaterial(m);
2315
2316	exporter->ExportIntersectable(intersect);
2317	intersect->Mail();
2318	}
2319	}
2320
2321	delete exporter;
2322	}
2323
2324	//-- export final view cells
2325	Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d");
2326
2327	//if (exportGeometry) exporter->SetWireframe();
2328	//else exporter->SetFilled();
2329
2330	ExportViewCellsForViz(exporter);
2331
2332	if (mExportGeometry)
2333	{
2334	exporter->SetFilled();
2335	exporter->ExportGeometry(objects);
2336	}
2337
2338	if (mExportRays)
2339	{
2340	const float prob = (float)mVisualizationSamples
2341	/ ((float)sampleRays.size() + Limits::Small);
2342
2343	exporter->SetWireframe();
2344
2345	VssRayContainer rays;
2346
2347	for (int i = 0; i < sampleRays.size(); ++ i)
2348	{
2349	if (RandomValue(0,1) < prob)
2350	rays.push_back(sampleRays[i]);
2351	}
2352	exporter->ExportRays(rays, RgbColor(1, 0, 0));
2353	}
2354
2355	delete exporter;
2356	}
2357
2358	int VspKdViewCellsManager::GetType() const
2359	{
2360	return VSP_KD;
2361	}
2362
2363
2364	int VspKdViewCellsManager::CastLineSegment(const Vector3 &origin,
2365	const Vector3 &termination,
2366	ViewCellContainer &viewcells)
2367	{
2368	return mVspKdTree->CastLineSegment(origin, termination, viewcells);
2369	}
2370
2371
2372	void VspKdViewCellsManager::ExportColor(Exporter *exporter,
2373	ViewCell *vc) const
2374	{
2375	if (mColorCode == 0) // Random color
2376	return;
2377
2378	float importance = 0;
2379
2380	switch (mColorCode)
2381	{
2382	case 1: // pvs
2383	{
2384	importance = (float)vc->GetPvs().GetSize() /
2385	(float)mViewCellsStats.maxPvs;
2386	}
2387	break;
2388	case 2: // merged leaves
2389	{
2390	int lSize = mViewCellsTree->GetSize(vc);
2391	importance = (float)lSize /
2392	(float)mViewCellsStats.maxLeaves;
2393	}
2394	break;
2395	case 3: // merged tree depth difference
2396	{
2397	//importance = (float)GetMaxTreeDiff(vc) /
2398	// (float)(mVspBspTree->GetStatistics().maxDepth * 2);
2399	}
2400	break;
2401	default:
2402	break;
2403	}
2404
2405	Material m;
2406	m.mDiffuseColor.b = 1.0f;
2407	m.mDiffuseColor.r = importance;
2408	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
2409	//Debug << "importance: " << importance << endl;
2410	exporter->SetForcedMaterial(m);
2411	}
2412
2413
2414	void VspKdViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
2415	ViewCell *vc,
2416	const Plane3 *cuttingPlane) const
2417	{
2418	VspKdViewCell kdVc = dynamic_cast<VspKdViewCell >(vc);
2419
2420	Mesh m;
2421
2422	ViewCellContainer leaves;
2423	mViewCellsTree->CollectLeaves(vc, leaves);
2424
2425	ViewCellContainer::const_iterator it, it_end = leaves.end();
2426
2427	for (it = leaves.begin(); it != it_end; ++ it)
2428	{
2429	VspKdLeaf l = dynamic_cast<VspKdViewCell >(*it)->mLeaf;
2430	mVspKdTree->GetBBox(l).AddBoxToMesh(&m);
2431	}
2432
2433	exporter->ExportMesh(&m);
2434	}
2435
2436
2437	void VspKdViewCellsManager::CreateMesh(ViewCell *vc)
2438	{
2439	//TODO
2440	}
2441
2442
2443	void VspKdViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
2444	vector<MergeCandidate> &candidates)
2445	{
2446	// TODO
2447	}
2448
2449
2450	/**************************************************************************/
2451	/* VspBspViewCellsManager implementation */
2452	/**************************************************************************/
2453
2454
2455	VspBspViewCellsManager::VspBspViewCellsManager(VspBspTree *vspBspTree):
2456	ViewCellsManager(), mVspBspTree(vspBspTree)
2457	{
2458	environment->GetIntValue("VspBspTree.Construction.samples", mInitialSamples);
2459	mVspBspTree->SetViewCellsManager(this);
2460	mVspBspTree->mViewCellsTree = mViewCellsTree;
2461	}
2462
2463
2464	VspBspViewCellsManager::~VspBspViewCellsManager()
2465	{
2466	}
2467
2468
2469	float VspBspViewCellsManager::GetProbability(ViewCell *viewCell)
2470	{
2471	if (0 && mVspBspTree->mUseAreaForPvs)
2472	return GetArea(viewCell) / GetAccVcArea();
2473	else
2474	return GetVolume(viewCell) / mViewSpaceBox.GetVolume();
2475	}
2476
2477
2478	void VspBspViewCellsManager::CollectViewCells()
2479	{
2480	// view cells tree constructed
2481	if (!ViewCellsTreeConstructed())
2482	{
2483	mVspBspTree->CollectViewCells(mViewCells, false);
2484	}
2485	else
2486	{
2487	// we can use the view cells tree hierarchy to get the right set
2488	mViewCellsTree->CollectBestViewCellSet(mViewCells, mNumActiveViewCells);
2489	}
2490
2491	}
2492
2493
2494
2495	bool VspBspViewCellsManager::ViewCellsConstructed() const
2496	{
2497	return mVspBspTree->GetRoot() != NULL;
2498	}
2499
2500
2501	ViewCell VspBspViewCellsManager::GenerateViewCell(Mesh mesh) const
2502	{
2503	return new BspViewCell(mesh);
2504	}
2505
2506
2507	/void VspBspViewCellsManager::CollectNodes(ViewCell vc, vector<BspNode *>nodes)
2508	{
2509	void ViewCellsTree::CollectLeaves(ViewCell vc, vector<BspNode > &nodes) const
2510
2511	if (vc->IsLeaf())
2512	{
2513	BspViewCell bvc = dynamic_cast<BspViewCell >(vc);
2514	nodes->push_back(bvc->mLeaf);
2515	}
2516	else
2517	{
2518	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2519
2520	for (it = interior->mChildren.begin; it != it_end; ++ it)
2521	{
2522	vector<BspNode *> mynodes;
2523	CollectNodes(*it, mynodes);
2524
2525	if (mynodes[0]->GetParent() && (mynodes[0]->GetParent() == mynodes[1]->GetParent()))
2526	{
2527	nodes.push_back(nodes[0]->GetParent());
2528	}
2529
2530	}
2531	}
2532	}*/
2533
2534
2535	int VspBspViewCellsManager::ConstructSubdivision(const ObjectContainer &objects,
2536	const VssRayContainer &rays)
2537	{
2538	// if view cells were already constructed
2539	if (ViewCellsConstructed())
2540	return 0;
2541
2542	Debug << "Constructing bsp view cells" << endl;
2543
2544	int sampleContributions = 0;
2545
2546	VssRayContainer sampleRays;
2547
2548	int limit = min (mInitialSamples, (int)rays.size());
2549
2550	VssRayContainer constructionRays;
2551	VssRayContainer savedRays;
2552
2553	Debug << "samples used for subdivision: " << mInitialSamples
2554	<< " rays: " << (int)rays.size() << endl;
2555
2556	GetRaySets(rays, mInitialSamples, constructionRays, &savedRays);
2557
2558	Debug << "initial rays: " << (int)constructionRays.size() << endl;
2559	Debug << "saved rays: " << (int)savedRays.size() << endl;
2560
2561	mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
2562
2563	mVspBspTree->Construct(constructionRays, &mViewSpaceBox);
2564
2565	Debug << mVspBspTree->GetStatistics() << endl;
2566
2567	// collapse invalid regions
2568	cout << "collapsing invalid tree regions ... ";
2569	long startTime = GetTime();
2570	int collapsedLeaves = mVspBspTree->CollapseTree();
2571	Debug << "collapsed in " << TimeDiff(startTime, GetTime()) * 1e-3
2572	<< " seconds" << endl;
2573
2574	cout << "finished" << endl;
2575
2576	cout << "reseting view cell stats ... ";
2577	ResetViewCells();
2578	cout << "finished" << endl;
2579
2580	Debug << "\nView cells after construction:\n" << mViewCellsStats << endl;
2581
2582	if (0) // export initial view cells
2583	{
2584	cout << "exporting initial view cells (=leaves) ... ";
2585	Exporter *exporter = Exporter::GetExporter("view_cells.x3d");
2586
2587	if (exporter)
2588	{
2589	if (0 && mExportRays)
2590	exporter->ExportRays(rays, RgbColor(1, 1, 1));
2591
2592	if (mExportGeometry)
2593	exporter->ExportGeometry(objects);
2594
2595	//exporter->SetWireframe();
2596	exporter->SetFilled();
2597	ExportViewCellsForViz(exporter);
2598
2599	delete exporter;
2600	}
2601	cout << "finished" << endl;
2602	}
2603
2604	startTime = GetTime();
2605
2606	// reset view cells and stats
2607	ResetViewCells();
2608
2609	cout << "Computing remaining ray contributions ... ";
2610
2611	// recast rest of rays
2612	if (SAMPLE_AFTER_SUBDIVISION)
2613	ComputeSampleContributions(savedRays, true, false);
2614	cout << "finished" << endl;
2615
2616	Debug << "Computed remaining ray contribution in " << TimeDiff(startTime, GetTime()) * 1e-3
2617	<< " secs" << endl;
2618
2619	cout << "construction finished" << endl;
2620
2621	return sampleContributions;
2622	}
2623
2624
2625	void VspBspViewCellsManager::MergeViewCells(const VssRayContainer &rays,
2626	const ObjectContainer &objects)
2627	{
2628	//-- post processing of bsp view cells
2629	int vcSize = 0;
2630	int pvsSize = 0;
2631
2632	mRenderer->RenderScene();
2633	SimulationStatistics ss;
2634	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
2635	Debug << ss << endl;
2636
2637	//-- merge or subdivide view cells
2638	int merged = 0;
2639	if (mMergeViewCells)
2640	{
2641	cout << "starting merge using " << mPostProcessSamples << " samples ... " << endl;
2642	long startTime = GetTime();
2643
2644
2645	// TODO: should be done BEFORE the ray casting
2646	merged = mViewCellsTree->ConstructMergeTree(rays, objects);
2647
2648	//-- stats and visualizations
2649	cout << "finished merging" << endl;
2650	cout << "merged " << merged << " view cells in "
2651	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
2652
2653	Debug << "Postprocessing: Merged " << merged << " view cells in "
2654	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
2655	}
2656
2657	int savedColorCode = mColorCode;
2658
2659	//BspLeaf::NewMail();
2660	if (0) // export merged view cells
2661	{
2662	mColorCode = 0;
2663	cout << "reseting view cells ... ";
2664	ResetViewCells();
2665
2666	cout << "finished" << endl;
2667
2668	Exporter *exporter = Exporter::GetExporter("merged_view_cells.x3d");
2669	Debug << "\nView cells after merge:\n" << mViewCellsStats << endl;
2670
2671	cout << "exporting view cells after merge ... ";
2672
2673	if (exporter)
2674	{
2675	if (0)
2676	exporter->SetWireframe();
2677	else
2678	exporter->SetFilled();
2679
2680	ExportViewCellsForViz(exporter);
2681
2682	if (mExportGeometry)
2683	{
2684	Material m;
2685	m.mDiffuseColor = RgbColor(0, 1, 0);
2686	exporter->SetForcedMaterial(m);
2687	exporter->SetFilled();
2688
2689	exporter->ExportGeometry(objects);
2690	}
2691
2692	delete exporter;
2693	}
2694	cout << "finished" << endl;
2695	}
2696
2697	if (0) // export merged view cells using pvs coding
2698	{
2699	mColorCode = 1;
2700
2701	Exporter *exporter = Exporter::GetExporter("merged_view_cells_pvs.x3d");
2702
2703	cout << "exporting view cells after merge (pvs size) ... ";
2704
2705	if (exporter)
2706	{
2707	if (0)
2708	exporter->SetWireframe();
2709	else
2710	exporter->SetFilled();
2711
2712	ExportViewCellsForViz(exporter);
2713
2714	if (mExportGeometry)
2715	{
2716	Material m;
2717	m.mDiffuseColor = RgbColor(0, 1, 0);
2718	exporter->SetForcedMaterial(m);
2719	exporter->SetFilled();
2720
2721	exporter->ExportGeometry(objects);
2722	}
2723
2724	delete exporter;
2725	}
2726	cout << "finished" << endl;
2727	}
2728
2729	mColorCode = savedColorCode;
2730
2731	}
2732
2733
2734	bool VspBspViewCellsManager::EqualToSpatialNode(ViewCell *viewCell) const
2735	{
2736	return GetSpatialNode(viewCell) != NULL;
2737	}
2738
2739
2740	BspNode VspBspViewCellsManager::GetSpatialNode(ViewCell viewCell) const
2741	{
2742	if (!viewCell->IsLeaf())
2743	{
2744	BspViewCell bspVc = dynamic_cast<BspViewCell >(viewCell);
2745
2746	return bspVc->mLeaf;
2747	}
2748	else
2749	{
2750	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2751
2752	// cannot be node of binary tree
2753	if (interior->mChildren.size() != 2)
2754	return NULL;
2755
2756	ViewCell *left = interior->mChildren[0];
2757	ViewCell *right = interior->mChildren[1];
2758
2759	BspNode *leftNode = GetSpatialNode(left);
2760	BspNode *rightNode = GetSpatialNode(right);
2761
2762	if (leftNode && rightNode && leftNode->IsSibling(rightNode))
2763	{
2764	return leftNode->GetParent();
2765	}
2766	}
2767
2768	return NULL;
2769	}
2770
2771
2772	void VspBspViewCellsManager::RefineViewCells(const VssRayContainer &rays,
2773	const ObjectContainer &objects)
2774	{
2775	Debug << "render time before refine:" << endl;
2776	mRenderer->RenderScene();
2777	SimulationStatistics ss;
2778	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
2779	Debug << ss << endl;
2780
2781	cout << "Refining the merged view cells ... ";
2782	long startTime = GetTime();
2783
2784	// refining the merged view cells
2785	const int refined = mViewCellsTree->RefineViewCells(rays, objects);
2786
2787	//-- stats and visualizations
2788	cout << "finished" << endl;
2789	cout << "refined " << refined << " view cells in "
2790	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl;
2791
2792	Debug << "Postprocessing: refined " << refined << " view cells in "
2793	<< TimeDiff(startTime, GetTime()) *1e-3 << " secs" << endl << endl;
2794	}
2795
2796
2797	int VspBspViewCellsManager::PostProcess(const ObjectContainer &objects,
2798	const VssRayContainer &rays)
2799	{
2800	if (!ViewCellsConstructed())
2801	{
2802	Debug << "postprocess error: no view cells constructed" << endl;
2803	return 0;
2804	}
2805
2806
2807	// view cells already finished before post processing step
2808	// (i.e. because they were loaded)
2809	if (mViewCellsFinished)
2810	{
2811	FinalizeViewCells(true);
2812	EvaluateViewCellsStats();
2813
2814	return 0;
2815	}
2816
2817
2818	// check if new view cells turned invalid
2819	SetValidity(mMinPvsSize, mMaxPvsSize);
2820	// update valid view space according to valid view cells
2821	mVspBspTree->ValidateTree();
2822
2823	// recompute view cell statistics
2824	mViewCellsStats.Reset();
2825	EvaluateViewCellsStats();
2826
2827	// has to be recomputed
2828	mTotalAreaValid = false;
2829
2830
2831	VssRayContainer postProcessRays;
2832
2833	GetRaySets(rays, mPostProcessSamples, postProcessRays);
2834
2835	Debug << "post processing using " << (int)postProcessRays.size() << " samples" << endl;
2836
2837	Debug << "\nview cell partition after sampling:\n" << mViewCellsStats << endl << endl;
2838
2839	// should maybe be done here to allow merge working with area or volume
2840	// and to correct the rendering statistics
2841	if (0)
2842	{
2843	FinalizeViewCells(false);
2844	}
2845
2846	//-- merge the individual view cells
2847	MergeViewCells(postProcessRays, objects);
2848
2849
2850	//-- refines the merged view cells
2851	if (0)
2852	RefineViewCells(postProcessRays, objects);
2853
2854	//-- render simulation after merge
2855	cout << "\nevaluating bsp view cells render time before compress ... ";
2856	dynamic_cast<RenderSimulator *>(mRenderer)->RenderScene();
2857	SimulationStatistics ss;
2858	dynamic_cast<RenderSimulator *>(mRenderer)->GetStatistics(ss);
2859
2860
2861	cout << " finished" << endl;
2862	cout << ss << endl;
2863	Debug << ss << endl;
2864
2865
2866
2867	//-- compression
2868
2869	if (ViewCellsTreeConstructed() && mCompressViewCells)
2870	{
2871	int pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
2872	Debug << "number of entries before compress: " << pvsEntries << endl;
2873
2874	mViewCellsTree->CompressViewCellsPvs();
2875
2876	pvsEntries = mViewCellsTree->GetNumPvsEntries(mViewCellsTree->GetRoot());
2877	Debug << "number of entries after compress: " << pvsEntries << endl;
2878	}
2879
2880	// collapse sibling leaves that share the same view cell
2881	if (0)
2882	mVspBspTree->CollapseTree();
2883
2884	// recompute view cell list and statistics
2885	ResetViewCells();
2886
2887	// real meshes are only contructed only at this stage
2888	FinalizeViewCells(true);
2889
2890	// write view cells to disc
2891	if (mExportViewCells)
2892	{
2893	char buff[100];
2894	environment->GetStringValue("ViewCells.filename", buff);
2895	string vcFilename(buff);
2896
2897	ExportViewCells(buff);
2898	}
2899
2900	return 0;
2901	}
2902
2903
2904	int VspBspViewCellsManager::GetType() const
2905	{
2906	return VSP_BSP;
2907	}
2908
2909
2910	int VspBspViewCellsManager::ConstructSpatialMergeTree()
2911	{
2912	TraversalQueue tQueue;
2913	tQueue.push(TraversalData(mVspBspTree->GetRoot(), NULL));
2914
2915	int merged = 0;
2916
2917	while (!tQueue.empty())
2918	{
2919	TraversalData tData = tQueue.top();
2920	tQueue.pop();
2921
2922	if (tData.mNode->IsLeaf())
2923	{
2924	ViewCell viewCell = dynamic_cast<BspLeaf >(tData.mNode)->GetViewCell();
2925
2926	if (tData.mParentViewCell)
2927	{
2928	tData.mParentViewCell->SetupChildLink(viewCell);
2929	// probagate up pvs
2930	mViewCellsTree->PropagateUpPvs(viewCell);
2931	}
2932	}
2933	else
2934	{
2935	BspInterior interior = dynamic_cast<BspInterior >(tData.mNode);
2936	ViewCellInterior *viewCellInterior = new ViewCellInterior();
2937	++ merged;
2938
2939	tQueue.push(TraversalData(interior->GetBack(), viewCellInterior));
2940	tQueue.push(TraversalData(interior->GetFront(), viewCellInterior));
2941
2942	if (tData.mParentViewCell)
2943	tData.mParentViewCell->SetupChildLink(viewCellInterior);
2944	}
2945	}
2946	return merged;
2947	}
2948
2949
2950	bool VspBspViewCellsManager::GetViewPoint(Vector3 &viewPoint) const
2951	{
2952	if (!ViewCellsConstructed())
2953	return ViewCellsManager::GetViewPoint(viewPoint);
2954
2955	// TODO: set reasonable limit
2956	const int limit = 20;
2957
2958	for (int i = 0; i < limit; ++ i)
2959	{
2960	viewPoint = mViewSpaceBox.GetRandomPoint();
2961	if (mVspBspTree->ViewPointValid(viewPoint))
2962	{
2963	return true;
2964	}
2965	}
2966	Debug << "failed to find valid view point, taking " << viewPoint << endl;
2967	return false;
2968	}
2969
2970
2971	bool VspBspViewCellsManager::ViewPointValid(const Vector3 &viewPoint) const
2972	{
2973	// $$JB -> implemented in viewcellsmanager (slower, but allows dynamic
2974	// validy update in preprocessor for all managers)
2975	return ViewCellsManager::ViewPointValid(viewPoint);
2976
2977	// return mViewSpaceBox.IsInside(viewPoint) &&
2978	// mVspBspTree->ViewPointValid(viewPoint);
2979	}
2980
2981
2982	void VspBspViewCellsManager::Visualize(const ObjectContainer &objects,
2983	const VssRayContainer &sampleRays)
2984	{
2985	if (!ViewCellsConstructed())
2986	return;
2987
2988	VssRayContainer visRays;
2989	GetRaySets(sampleRays, mVisualizationSamples, visRays);
2990
2991
2992	if (0) // export view cells
2993	{ // hack pvs
2994	int savedColorCode = mColorCode;
2995	mColorCode = 1;
2996	Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d");
2997
2998	if (exporter)
2999	{
3000	cout << "exporting view cells after post process ... ";
3001
3002	if (0)
3003	{
3004	exporter->SetWireframe();
3005	exporter->ExportBox(mViewSpaceBox);
3006	exporter->SetFilled();
3007	}
3008
3009	if (mExportGeometry)
3010	{
3011	exporter->ExportGeometry(objects);
3012	}
3013
3014	// export rays
3015	if (mExportRays)
3016	{
3017	exporter->ExportRays(visRays, RgbColor(0, 1, 0));
3018	}
3019
3020	ExportViewCellsForViz(exporter);
3021	delete exporter;
3022	cout << "finished" << endl;
3023	}
3024
3025	mColorCode = savedColorCode;
3026	}
3027
3028	if (0)
3029	{
3030	cout << "exporting depth map ... ";
3031
3032	Exporter *exporter = Exporter::GetExporter("depth_map.x3d");
3033	if (exporter)
3034	{
3035	if (1)
3036	{
3037	exporter->SetWireframe();
3038	exporter->ExportBox(mViewSpaceBox);
3039	exporter->SetFilled();
3040	}
3041
3042	if (mExportGeometry)
3043	{
3044	exporter->ExportGeometry(objects);
3045	}
3046
3047	const int maxDepth = mVspBspTree->mBspStats.maxDepth;
3048
3049	ViewCellContainer::const_iterator vit, vit_end = mViewCells.end();
3050
3051	for (vit = mViewCells.begin(); vit != mViewCells.end(); ++ vit)
3052	{
3053	ViewCell vc = vit;
3054
3055	ViewCellContainer leaves;
3056	mViewCellsTree->CollectLeaves(vc, leaves);
3057
3058	ViewCellContainer::const_iterator lit, lit_end = leaves.end();
3059
3060	for (lit = leaves.begin(); lit != lit_end; ++ lit)
3061	{
3062	BspLeaf leaf = dynamic_cast<BspViewCell >(*lit)->mLeaf;
3063
3064	Material m;
3065
3066	float relDepth = (float)leaf->GetDepth() / (float)maxDepth;
3067	m.mDiffuseColor.r = relDepth;
3068	m.mDiffuseColor.g = 0.0f;
3069	m.mDiffuseColor.b = 1.0f - relDepth;
3070
3071	exporter->SetForcedMaterial(m);
3072
3073
3074	BspNodeGeometry geom;
3075	mVspBspTree->ConstructGeometry(leaf, geom);
3076	exporter->ExportPolygons(geom.mPolys);
3077	}
3078	}
3079
3080	delete exporter;
3081	}
3082
3083
3084	cout << "finished" << endl;
3085	}
3086
3087	//-- visualization of the BSP splits
3088	bool exportSplits = false;
3089	environment->GetBoolValue("VspBspTree.Visualization.exportSplits", exportSplits);
3090
3091	if (exportSplits)
3092	{
3093	cout << "exporting splits ... ";
3094	ExportSplits(objects, visRays);
3095	cout << "finished" << endl;
3096	}
3097
3098	//-- export single view cells
3099	ExportBspPvs(objects, visRays);
3100	}
3101
3102
3103	void VspBspViewCellsManager::ExportSplits(const ObjectContainer &objects,
3104	const VssRayContainer &rays)
3105	{
3106	Exporter *exporter = Exporter::GetExporter("bsp_splits.x3d");
3107
3108	if (exporter)
3109	{
3110	Material m;
3111	m.mDiffuseColor = RgbColor(1, 0, 0);
3112	exporter->SetForcedMaterial(m);
3113	exporter->SetWireframe();
3114
3115	exporter->ExportBspSplits(*mVspBspTree, true);
3116
3117	// take forced material, else big scenes cannot be viewed
3118	m.mDiffuseColor = RgbColor(0, 1, 0);
3119	exporter->SetForcedMaterial(m);
3120	exporter->SetFilled();
3121
3122	exporter->ResetForcedMaterial();
3123
3124	// export rays
3125	if (mExportRays)
3126	exporter->ExportRays(rays, RgbColor(1, 1, 0));
3127
3128	if (mExportGeometry)
3129	exporter->ExportGeometry(objects);
3130
3131	delete exporter;
3132	}
3133	}
3134
3135
3136	void VspBspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
3137	const VssRayContainer &rays)
3138	{
3139	const int leafOut = 20;
3140
3141	ViewCell::NewMail();
3142
3143	cout << "visualization using " << (int)rays.size() << " samples" << endl;
3144	Debug << "visualization using " << (int)rays.size() << " samples" << endl;
3145	Debug << "\nOutput view cells: " << endl;
3146
3147	// sort view cells to visualize the largest view cells
3148	if (0)
3149	stable_sort(mViewCells.begin(), mViewCells.end(), vc_gt);
3150
3151	int limit = min(leafOut, (int)mViewCells.size());
3152
3153	int raysOut = 0;
3154
3155	//-- some rays for output
3156	for (int i = 0; i < limit; ++ i)
3157	{
3158	cout << "creating output for view cell " << i << " ... ";
3159
3160
3161	ViewCell *vc;
3162
3163	if (0) // largest view cell pvs first
3164	vc = mViewCells[i];
3165	else
3166	vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
3167
3168	//bspLeaves[j]->Mail();
3169	char s[64]; sprintf(s, "bsp-pvs%04d.x3d", i);
3170	Exporter *exporter = Exporter::GetExporter(s);
3171
3172	Debug << i << ": pvs size=" << (int)mViewCellsTree->GetPvsSize(vc) << endl;
3173
3174	if (1 \|\| mExportRays)
3175	{
3176	if (0)
3177	{
3178	VssRayContainer vcRays;
3179	VssRayContainer collectRays;
3180
3181	raysOut = min((int)rays.size(), 100);
3182
3183	// collect intial view cells
3184	ViewCellContainer leaves;
3185	mViewCellsTree->CollectLeaves(vc, leaves);
3186
3187	ViewCellContainer::const_iterator vit, vit_end = leaves.end();
3188
3189	for (vit = leaves.begin(); vit != vit_end; ++ vit)
3190	{
3191	BspLeaf vcLeaf = dynamic_cast<BspViewCell >(*vit)->mLeaf;
3192
3193	VssRayContainer::const_iterator rit, rit_end = vcLeaf->mVssRays.end();
3194
3195	for (rit = vcLeaf->mVssRays.begin(); rit != rit_end; ++ rit)
3196	{
3197	collectRays.push_back(*rit);
3198	}
3199	}
3200
3201	VssRayContainer::const_iterator rit, rit_end = collectRays.end();
3202
3203	for (rit = collectRays.begin(); rit != rit_end; ++ rit)
3204	{
3205	float p = RandomValue(0.0f, (float)collectRays.size());
3206
3207	if (p < raysOut)
3208	vcRays.push_back(*rit);
3209	}
3210	//-- export rays piercing this view cell
3211	exporter->ExportRays(vcRays, RgbColor(1, 1, 1));
3212	}
3213
3214
3215
3216	if (1)
3217	{
3218	VssRayContainer vcRays;
3219	raysOut = min((int)rays.size(), mVisualizationSamples);
3220	// check whether we can add the current ray to the output rays
3221	for (int k = 0; k < raysOut; ++ k)
3222	{
3223	VssRay *ray = rays[k];
3224	for (int j = 0; j < (int)ray->mViewCells.size(); ++ j)
3225	{
3226	ViewCell *rayvc = ray->mViewCells[j];
3227
3228	if (rayvc == vc)
3229	vcRays.push_back(ray);
3230	}
3231	}
3232
3233	//-- export rays piercing this view cell
3234	exporter->ExportRays(vcRays, RgbColor(1, 1, 0));
3235	}
3236
3237	}
3238
3239
3240
3241
3242	exporter->SetWireframe();
3243
3244	Material m;//= RandomMaterial();
3245	m.mDiffuseColor = RgbColor(0, 1, 0);
3246	exporter->SetForcedMaterial(m);
3247
3248	ExportViewCellGeometry(exporter, vc);
3249
3250	exporter->SetFilled();
3251
3252
3253	if (1)
3254	{
3255	ObjectPvsMap::const_iterator oit,
3256	oit_end = vc->GetPvs().mEntries.end();
3257
3258
3259	exporter->SetFilled();
3260
3261	Intersectable::NewMail();
3262
3263	// output PVS of view cell
3264	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
3265	{
3266	Intersectable intersect = (oit).first;
3267
3268	if (!intersect->Mailed())
3269	{
3270	m = RandomMaterial();
3271	exporter->SetForcedMaterial(m);
3272
3273	exporter->ExportIntersectable(intersect);
3274	intersect->Mail();
3275	}
3276	}
3277	}
3278	else
3279	{
3280	m.mDiffuseColor = RgbColor(1, 0, 0);
3281	exporter->SetForcedMaterial(m);
3282
3283	exporter->ExportGeometry(objects);
3284	}
3285
3286	DEL_PTR(exporter);
3287	cout << "finished" << endl;
3288	}
3289
3290	Debug << endl;
3291	}
3292
3293
3294	int VspBspViewCellsManager::CastLineSegment(const Vector3 &origin,
3295	const Vector3 &termination,
3296	ViewCellContainer &viewcells)
3297	{
3298	return mVspBspTree->CastLineSegment(origin, termination, viewcells);
3299	}
3300
3301
3302	void VspBspViewCellsManager::ExportColor(Exporter *exporter,
3303	ViewCell *vc) const
3304	{
3305	const bool vcValid = CheckValidity(vc, mMinPvsSize, mMaxPvsSize);
3306
3307	float importance = 0;
3308	static Material m;
3309
3310	switch (mColorCode)
3311	{
3312	case 0: // Random
3313	{
3314	if (vcValid)
3315	{
3316	m.mDiffuseColor.r = 0.5f + RandomValue(0.0f, 0.5f);
3317	m.mDiffuseColor.g = 0.5f + RandomValue(0.0f, 0.5f);
3318	m.mDiffuseColor.b = 0.5f + RandomValue(0.f, 0.5f);
3319	}
3320	else
3321	{
3322	m.mDiffuseColor.r = 0.0f;
3323	m.mDiffuseColor.g = 1.0f;
3324	m.mDiffuseColor.b = 0.0f;
3325	}
3326
3327	exporter->SetForcedMaterial(m);
3328	return;
3329	}
3330
3331	case 1: // pvs
3332	{
3333	importance = (float)vc->GetPvs().GetSize() /
3334	(float)mViewCellsStats.maxPvs;
3335
3336	}
3337	break;
3338	case 2: // merges
3339	{
3340	int lSize = mViewCellsTree->GetSize(vc);
3341	importance = (float)lSize / (float)mViewCellsStats.maxLeaves;
3342	}
3343	break;
3344	case 3: // merge tree differene
3345	{
3346	importance = (float)GetMaxTreeDiff(vc) /
3347	(float)(mVspBspTree->GetStatistics().maxDepth * 2);
3348
3349	}
3350	break;
3351	default:
3352	break;
3353	}
3354
3355	// special color code for invalid view cells
3356	m.mDiffuseColor.r = importance;
3357	m.mDiffuseColor.g = 1.0f - m.mDiffuseColor.r;
3358	m.mDiffuseColor.b = vcValid ? 1.0f : 0.0f;
3359
3360	//Debug << "importance: " << importance << endl;
3361	exporter->SetForcedMaterial(m);
3362	}
3363
3364
3365	void VspBspViewCellsManager::ExportViewCellGeometry(Exporter *exporter,
3366	ViewCell *vc,
3367	const Plane3 *cuttingPlane) const
3368	{
3369	if (vc->GetMesh())
3370	{
3371	exporter->ExportMesh(vc->GetMesh());
3372
3373	return;
3374	}
3375
3376
3377	if (cuttingPlane)
3378	{
3379	ViewCellContainer leaves;
3380	mViewCellsTree->CollectLeaves(vc, leaves);
3381	ViewCellContainer::const_iterator it, it_end = leaves.end();
3382
3383	for (it = leaves.begin(); it != it_end; ++ it)
3384	{
3385	BspNodeGeometry geom;
3386
3387	BspNodeGeometry front;
3388	BspNodeGeometry back;
3389
3390
3391	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
3392
3393	mVspBspTree->ConstructGeometry(leaf, geom);
3394
3395	geom.SplitGeometry(front,
3396	back,
3397	*cuttingPlane,
3398	mViewSpaceBox,
3399	0.0001f);
3400
3401	if ((int)back.mPolys.size() >= 3)
3402	exporter->ExportPolygons(back.mPolys);
3403	}
3404	}
3405	else
3406	{
3407	BspNodeGeometry geom;
3408	mVspBspTree->ConstructGeometry(vc, geom);
3409
3410	exporter->ExportPolygons(geom.mPolys);
3411	}
3412	}
3413
3414
3415	int VspBspViewCellsManager::GetMaxTreeDiff(ViewCell *vc) const
3416	{
3417	ViewCellContainer leaves;
3418	mViewCellsTree->CollectLeaves(vc, leaves);
3419
3420	int maxDist = 0;
3421
3422	// compute max height difference
3423	for (int i = 0; i < (int)leaves.size(); ++ i)
3424	for (int j = 0; j < (int)leaves.size(); ++ j)
3425	{
3426	BspLeaf leaf = dynamic_cast<BspViewCell >(leaves[i])->mLeaf;
3427
3428	if (i != j)
3429	{
3430	BspLeaf leaf2 =dynamic_cast<BspViewCell >(leaves[j])->mLeaf;
3431	int dist = mVspBspTree->TreeDistance(leaf, leaf2);
3432	if (dist > maxDist)
3433	maxDist = dist;
3434	}
3435	}
3436
3437	return maxDist;
3438	}
3439
3440
3441	ViewCell *VspBspViewCellsManager::GetViewCell(const Vector3 &point) const
3442	{
3443	if (!mVspBspTree)
3444	return NULL;
3445
3446	if (!mViewSpaceBox.IsInside(point))
3447	return NULL;
3448
3449	return mVspBspTree->GetViewCell(point);
3450	}
3451
3452
3453	void VspBspViewCellsManager::CreateMesh(ViewCell *vc)
3454	{
3455	if (vc->GetMesh())
3456	delete vc->GetMesh();
3457
3458
3459	BspNodeGeometry geom;
3460
3461	mVspBspTree->ConstructGeometry(vc, geom);
3462
3463	Mesh *mesh = new Mesh();
3464	geom.AddToMesh(*mesh);
3465	vc->SetMesh(mesh);
3466	mMeshContainer.push_back(mesh);
3467	}
3468
3469
3470	ViewCellsManager *ViewCellsManager::LoadViewCells(const string filename,
3471	ObjectContainer *objects)
3472	{
3473	ViewCellsParser parser;
3474
3475	ViewCellsManager *vm = NULL;
3476
3477	if (parser.ParseFile(filename, &vm, objects))
3478	{
3479	//vm->PrepareLoadedViewCells();
3480	vm->ResetViewCells();
3481
3482	vm->mViewCellsFinished = true;
3483	vm->mMaxPvsSize = (int)objects->size();
3484
3485	vm->FinalizeViewCells(true);
3486
3487	Debug << (int)vm->mViewCells.size() << " view cells loaded" << endl;
3488	}
3489	else
3490	{
3491	Debug << "failed loading view cells" << endl;
3492	DEL_PTR(vm);
3493	}
3494
3495
3496	return vm;
3497	}
3498
3499
3500	inline bool ilt(Intersectable obj1, Intersectable obj2)
3501	{
3502	return obj1->mId < obj2->mId;
3503	}
3504
3505
3506	bool VspBspViewCellsManager::ExportViewCells(const string filename)
3507	{
3508	cout << "exporting view cells to xml ... ";
3509	std::ofstream stream;
3510
3511	// for output we need unique ids for each view cell
3512	CreateUniqueViewCellIds();
3513
3514
3515	stream.open(filename.c_str());
3516	stream << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"<<endl;
3517	stream << "<Visibility_Solution>" << endl;
3518
3519	//-- the view space bounding box
3520	stream << "<ViewSpaceBox"
3521	<< " min=\"" << mViewSpaceBox.Min().x << " " << mViewSpaceBox.Min().y << " " << mViewSpaceBox.Min().z << "\""
3522	<< " max=\"" << mViewSpaceBox.Max().x << " " << mViewSpaceBox.Max().y << " " << mViewSpaceBox.Max().z << "\" />" << endl;
3523
3524	//-- the type of the view cells hierarchy
3525	stream << "<Hierarchy name=\"vspBspTree\" />" << endl;
3526
3527	//-- load the view cells itself, i.e., the ids and the pvs
3528	stream << "<ViewCells>" << endl;
3529
3530	#if 0
3531
3532	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3533
3534	for (it = mViewCells.begin(); it != it_end; ++ it)
3535	ExportViewCell(*it, stream);
3536	#else
3537	mViewCellsTree->Export(stream);
3538	#endif
3539
3540	stream << "</ViewCells>" << endl;
3541
3542	//-- load the hierarchy
3543	stream << "<Hierarchy>" << endl;
3544	mVspBspTree->Export(stream);
3545	stream << endl << "</Hierarchy>" << endl;
3546
3547	stream << "</Visibility_Solution>" << endl;
3548	stream.close();
3549
3550	cout << "finished" << endl;
3551
3552	return true;
3553	}
3554
3555
3556	int VspBspViewCellsManager::CastBeam(Beam &beam)
3557	{
3558	return mVspBspTree->CastBeam(beam);
3559	}
3560
3561
3562	void VspBspViewCellsManager::Finalize(ViewCell *viewCell,
3563	const bool createMesh)
3564	{
3565	CreateMesh(viewCell);
3566
3567	float area = 0;
3568	float volume = 0;
3569
3570	ViewCellContainer leaves;
3571	mViewCellsTree->CollectLeaves(viewCell, leaves);
3572
3573	ViewCellContainer::const_iterator it, it_end = leaves.end();
3574
3575	for (it = leaves.begin(); it != it_end; ++ it)
3576	{
3577	BspNodeGeometry geom;
3578	BspLeaf leaf = dynamic_cast<BspViewCell >(*it)->mLeaf;
3579	mVspBspTree->ConstructGeometry(leaf, geom);
3580
3581	area += geom.GetArea();
3582	volume += geom.GetVolume();
3583	}
3584
3585	viewCell->SetVolume(volume);
3586	viewCell->SetArea(area);
3587	}
3588
3589
3590	void VspBspViewCellsManager::PrepareLoadedViewCells()
3591	{
3592	// TODO: do I still need this here?
3593	if (0)
3594	mVspBspTree->RepairViewCellsLeafLists();
3595	}
3596
3597
3598
3599	void VspBspViewCellsManager::CollectMergeCandidates(const VssRayContainer &rays,
3600	vector<MergeCandidate> &candidates)
3601	{
3602	cout << "collecting merge candidates ... " << endl;
3603
3604	if (mUseRaysForMerge)
3605	{
3606	mVspBspTree->CollectMergeCandidates(rays, candidates);
3607	}
3608	else
3609	{
3610	vector<BspLeaf *> leaves;
3611	mVspBspTree->CollectLeaves(leaves);
3612	mVspBspTree->CollectMergeCandidates(leaves, candidates);
3613	}
3614
3615	cout << "fininshed collecting candidates" << endl;
3616	}
3617
3618
3619	void VspBspViewCellsManager::AddCurrentViewCellsToHierarchy()
3620	{
3621	ViewCellContainer::const_iterator it, it_end = mViewCells.end();
3622	for (it = mViewCells.begin(); it != it_end; ++ it)
3623	{
3624	}
3625	}
3626
3627	//////////////////////////////////
3628	ViewCellsManager *ViewCellsManagerFactory::Create(const string mName)
3629	{
3630	//TODO
3631	return NULL;// new VspBspViewCellsManager();
3632	}
3633

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

Download in other formats: