Context Navigation

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

Revision 703, 99.3 KB checked in by mattausch, 19 years ago (diff)
started implementation of visibility filter

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

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

Download in other formats: