Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.cpp @ 1763

Revision 1763, 59.9 KB checked in by mattausch, 18 years ago (diff)

Line
1	#include <time.h>
2	#include <iomanip>
3	#include <stack>
4
5
6	#include "ViewCell.h"
7	#include "Mesh.h"
8	#include "Intersectable.h"
9	#include "KdTree.h"
10	#include "Triangle3.h"
11	#include "common.h"
12	#include "Environment.h"
13	#include "ViewCellsManager.h"
14	#include "Exporter.h"
15	#include "BvHierarchy.h"
16
17
18
19	namespace GtpVisibilityPreprocessor {
20
21
22
23	template <typename T> class myless
24	{
25	public:
26	bool operator() (T v1, T v2) const
27	{
28	return (v1->GetMergeCost() < v2->GetMergeCost());
29	}
30	};
31
32
33	typedef priority_queue<ViewCell , vector<ViewCell >,
34	myless<vector<ViewCell *>::value_type> > TraversalQueue;
35
36	int ViewCell::sMailId = 10000;//2147483647;
37	int ViewCell::sReservedMailboxes = 1;
38
39
40	float MergeCandidate::sRenderCostWeight = 0;
41
42
43	// pvs penalty can be different from pvs size
44	inline static float EvalPvsPenalty(const float pvs,
45	const float lower,
46	const float upper)
47	{
48	// clamp to minmax values
49	if (pvs < lower)
50	return (float)lower;
51	if (pvs > upper)
52	return (float)upper;
53
54	return (float)pvs;
55	}
56
57	/** Counts contribution of the view cell to the pvs.
58	*/
59	inline int CountPvsContribution(ViewCell *vc)
60	{
61	int count = 0;
62
63	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
64
65	while (pit.HasMoreEntries())
66	{
67	ObjectPvsEntry entry = pit.Next();
68
69	if (!entry.mObject->Mailed())
70	{
71	entry.mObject->Mail();
72	++ count;
73	}
74	}
75
76	return count;
77	}
78
79
80	/// Fast computation of merged pvs size
81	static float ComputeMergedPvsCost(const ObjectPvs &pvs1,
82	const ObjectPvs &pvs2)
83	{
84	// add first pvs
85	float pvs = (float)pvs1.GetSize();
86
87	Intersectable::NewMail();
88
89	// mail all objects in first pvs
90	ObjectPvsIterator pit = pvs1.GetIterator();
91
92	while (pit.HasMoreEntries())
93	{
94	ObjectPvsEntry entry = pit.Next();
95	entry.mObject->Mail();
96	}
97
98	pit = pvs2.GetIterator();
99
100	while (pit.HasMoreEntries())
101	{
102	ObjectPvsEntry entry = pit.Next();
103
104	Intersectable *obj = entry.mObject;
105	if (!obj->Mailed())
106	++ pvs;
107	}
108
109	return pvs;
110	}
111
112
113	ViewCell::ViewCell():
114	MeshInstance(NULL),
115	mArea(-1),
116	mVolume(-1),
117	mValid(true),
118	mParent(NULL),
119	mMergeCost(0),
120	mPvsCost(0),
121	mEntriesInPvs(0),
122	mPvsSizeValid(false)
123	{
124	mId = -100;
125	}
126
127	ViewCell::ViewCell(Mesh *mesh):
128	MeshInstance(mesh),
129	mArea(-1),
130	mVolume(-1),
131	mValid(true),
132	mParent(NULL),
133	mMergeCost(0),
134	mPvsCost(0),
135	mPvsSizeValid(false)
136	//mMailbox(0)
137	{
138	mId = -100;
139	}
140
141
142	ViewCell::~ViewCell()
143	{
144	}
145
146
147	const ObjectPvs &ViewCell::GetPvs() const
148	{
149	return mPvs;
150	}
151
152
153	ObjectPvs &ViewCell::GetPvs()
154	{
155	return mPvs;
156	}
157
158
159	void ViewCell::SetPvs(const ObjectPvs &pvs)
160	{
161	mPvs = pvs;
162	}
163
164
165	int ViewCell::Type() const
166	{
167	return VIEW_CELL;
168	}
169
170
171	float ViewCell::GetVolume() const
172	{
173	return mVolume;
174	}
175
176
177	void ViewCell::SetVolume(float volume)
178	{
179	mVolume = volume;
180	}
181
182
183	void ViewCell::SetMesh(Mesh *mesh)
184	{
185	mMesh = mesh;
186	}
187
188
189	float ViewCell::GetArea() const
190	{
191	return mArea;
192	}
193
194
195	void ViewCell::SetArea(float area)
196	{
197	mArea = area;
198	}
199
200
201	void ViewCell::SetColor(const RgbColor &color)
202	{
203	mColor = color;
204	}
205
206
207	RgbColor ViewCell::GetColor() const
208	{
209	return mColor;
210	}
211
212
213	void ViewCell::SetValid(const bool valid)
214	{
215	mValid = valid;
216	}
217
218
219	bool ViewCell::GetValid() const
220	{
221	return mValid;
222	}
223
224
225	void ViewCell::SetParent(ViewCellInterior *parent)
226	{
227	mParent = parent;
228	}
229
230
231	bool ViewCell::IsRoot() const
232	{
233	return !mParent;
234	}
235
236
237	ViewCellInterior *ViewCell::GetParent() const
238	{
239	return mParent;
240	}
241
242
243	void ViewCell::SetMergeCost(const float mergeCost)
244	{
245	mMergeCost = mergeCost;
246	}
247
248
249	float ViewCell::GetRenderCost() const
250	{
251	return mPvsCost * GetVolume();
252	}
253
254
255	float ViewCell::GetMergeCost() const
256	{
257	return mMergeCost;
258	}
259
260
261	bool ViewCell::AddPvsSample(Intersectable *sample,
262	const float pdf,
263	float &contribution)
264	{
265	const bool result = mPvs.AddSample(sample, pdf, contribution);
266	// have to recompute pvs size
267	mPvsSizeValid = false;
268
269	return result;
270	}
271
272
273
274	/************************************************************************/
275	/* class ViewCellInterior implementation */
276	/************************************************************************/
277
278
279	ViewCellInterior::ViewCellInterior()
280	{
281	}
282
283
284	ViewCellInterior::~ViewCellInterior()
285	{
286	ViewCellContainer::const_iterator it, it_end = mChildren.end();
287
288	for (it = mChildren.begin(); it != it_end; ++ it)
289	{
290	delete (*it);
291	}
292	}
293
294
295	ViewCellInterior::ViewCellInterior(Mesh *mesh):
296	ViewCell(mesh)
297	{
298	}
299
300
301	bool ViewCellInterior::IsLeaf() const
302	{
303	return false;
304	}
305
306
307	void ViewCellInterior::SetupChildLink(ViewCell *vc)
308	{
309	mChildren.push_back(vc);
310	vc->SetParent(this);
311	}
312
313
314	void ViewCellInterior::RemoveChildLink(ViewCell *l)
315	{
316	// erase leaf from old view cell
317	ViewCellContainer::iterator it = mChildren.begin();
318
319	for (; (*it) != l; ++ it);
320	if (it == mChildren.end())
321	Debug << "error" << endl;
322	else
323	mChildren.erase(it);
324	}
325
326
327	void ViewCellInterior::ReplaceChildLink(ViewCell prev, ViewCell cur)
328	{
329	// erase leaf from old view cell
330	ViewCellContainer::iterator it = mChildren.begin();
331
332	for (; (*it) != prev; ++ it);
333	if (it == mChildren.end())
334	{
335	Debug << "error: child link not found" << endl;
336	}
337	else
338	{
339	(*it) = cur;
340	}
341	}
342
343
344
345	/************************************************************************/
346	/* class ViewCellsStatistics implementation */
347	/************************************************************************/
348
349
350	void ViewCellsStatistics::Print(ostream &app) const
351	{
352	app << "=========== View Cells Statistics ===============\n";
353
354	app << setprecision(4);
355
356	//app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
357
358	app << "#N_OVERALLPVS ( cost of the PVS )\n" << pvsCost << endl;
359
360	//app << "#N_PVSENTRIES ( entries in the PVS)\n" << pvsEntries << endl;
361
362	app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
363
364	app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
365
366	app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
367
368	app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
369
370	app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
371
372	app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
373
374	app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
375
376	app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
377
378	app << "========== End of View Cells Statistics ==========\n";
379	}
380
381
382	/*************************************************************************/
383	/* class ViewCellsTree implementation */
384	/*************************************************************************/
385
386
387	ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
388	mRoot(NULL),
389	mUseAreaForPvs(false),
390	mViewCellsManager(vcm),
391	#if 0
392	mViewCellsStorage(PVS_IN_INTERIORS)
393	#else
394	mViewCellsStorage(PVS_IN_LEAVES)
395	#endif
396	{
397	ReadEnvironment();
398	MergeCandidate::sRenderCostWeight = mRenderCostWeight;
399	}
400
401
402	ViewCellsTree::ViewCellsTree():
403	mRoot(NULL),
404	mUseAreaForPvs(false),
405	mViewCellsManager(NULL),
406	#if 0
407	mViewCellsStorage(PVS_IN_INTERIORS)
408	#else
409	mViewCellsStorage(PVS_IN_LEAVES)
410	#endif
411	{
412	ReadEnvironment();
413	MergeCandidate::sRenderCostWeight = mRenderCostWeight;
414	}
415
416
417	void ViewCellsTree::ReadEnvironment()
418	{
419	Environment::GetSingleton()->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
420	Environment::GetSingleton()->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
421
422	//-- merge options
423	Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
424	Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
425	Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
426	Environment::GetSingleton()->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);
427
428	Environment::GetSingleton()->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", mMaxMergesPerPass);
429	Environment::GetSingleton()->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", mAvgCostMaxDeviation);
430
431	Debug << "============= view cell tree options ================\n";
432	Debug << "minimum view cells: " << mMergeMinViewCells << endl;
433	Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
434	Debug << "max memory: " << mMaxMemory << endl;
435	Debug << "refining view cells: " << mRefineViewCells << endl;
436	Debug << "=========== end view cell tree options ===============\n";
437	}
438
439
440	// return memory usage in MB
441	float ViewCellsTree::GetMemUsage() const
442	{
443	// TODO
444	return 0;
445	/*(sizeof(ViewCellsTree) +
446	mBspStats.Leaves() * sizeof(BspLeaf) +
447	mBspStats.Interior() * sizeof(BspInterior) +
448	mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
449	}
450
451
452	int ViewCellsTree::GetNumInitialViewCells(ViewCell *vc) const
453	{
454	int vcSize = 0;
455
456	stack<ViewCell *> tstack;
457
458	tstack.push(vc);
459
460	while (!tstack.empty())
461	{
462	ViewCell *vc = tstack.top();
463	tstack.pop();
464
465	if (vc->IsLeaf())
466	{
467	++ vcSize;
468	}
469	else
470	{
471	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
472
473	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
474
475	for (it = interior->mChildren.begin(); it != it_end; ++ it)
476	{
477	tstack.push(*it);
478	}
479
480	}
481	}
482
483	return vcSize;
484	}
485
486
487	void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
488	{
489	stack<ViewCell *> tstack;
490
491	tstack.push(vc);
492
493	while (!tstack.empty())
494	{
495	ViewCell *vc = tstack.top();
496	tstack.pop();
497
498	if (vc->IsLeaf())
499	{
500	leaves.push_back(vc);
501	}
502	else
503	{
504	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
505	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
506
507	for (it = interior->mChildren.begin(); it != it_end; ++ it)
508	{
509	tstack.push(*it);
510	}
511	}
512	}
513	}
514
515
516	ViewCellsTree::~ViewCellsTree()
517	{
518	DEL_PTR(mRoot);
519	}
520
521
522	int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
523	const ObjectContainer &objects)
524	{
525	mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
526
527	float variance = 0;
528	float totalPvs = 0;
529	float totalRenderCost = 0;
530
531	//-- compute statistics values of initial view cells
532	mViewCellsManager->EvaluateRenderStatistics(totalRenderCost,
533	mExpectedCost,
534	mDeviation,
535	variance,
536	totalPvs,
537	mAvgRenderCost);
538
539
540	//-- fill merge queue
541	vector<MergeCandidate> candidates;
542
543	mViewCellsManager->CollectMergeCandidates(rays, candidates);
544
545	while(!candidates.empty())
546	{
547	MergeCandidate mc = candidates.back();
548	candidates.pop_back();
549	EvalMergeCost(mc);
550	mMergeQueue.push(mc);
551	}
552
553	Debug << "*********************** merge *********************************" << endl;
554	Debug << "deviation: " << mDeviation << endl;
555	Debug << "avg render cost: " << mAvgRenderCost << endl;
556	Debug << "expected cost: " << mExpectedCost << endl;
557
558
559	ViewCellsManager::PvsStatistics pvsStats;
560	mViewCellsManager->GetPvsStatistics(pvsStats);
561
562	//static float expectedValue = pvsStats.avgPvs;
563
564	//-- the current view cells are kept in this container
565	//-- we start with the current view cells from the view cell manager.
566	//-- The active view cells will change with subsequent merges
567
568	// todo: should rather take initial view cells
569	ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
570
571
572	ViewCell::NewMail();
573
574	MergeStatistics mergeStats;
575	mergeStats.Start();
576
577	long startTime = GetTime();
578
579	mergeStats.collectTime = TimeDiff(startTime, GetTime());
580	mergeStats.candidates = (int)mMergeQueue.size();
581	startTime = GetTime();
582
583	// frequency stats are updated
584	const int statsOut = 500;
585
586	// passes are needed for statistics, because we don't want to record
587	// every merge
588	int pass = 0;
589	int mergedPerPass = 0;
590	float realExpectedCost = mExpectedCost;
591	float realAvgRenderCost = mAvgRenderCost;
592	int realNumActiveViewCells = mNumActiveViewCells;
593
594	// maximal ratio of old expected render cost to expected render
595	// when the the render queue has to be reset.
596	int numMergedViewCells = 0;
597
598
599	cout << "actual merge starts now ... " << endl;
600
601	//-- use priority queue to merge leaf pairs
602
603	while (!mMergeQueue.empty())
604	{
605	//-- reset merge queue if the ratio of current expected cost / real expected cost
606	// too small or after a given number of merges
607	if ((mergedPerPass > mMaxMergesPerPass) \|\|
608	(mAvgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
609	{
610	Debug << "********** reset queue ***************\n"
611	<< "ratios: " << mAvgCostMaxDeviation
612	<< " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
613	<< " merged per pass : " << mergedPerPass << " of maximal " << mMaxMergesPerPass << endl;
614
615	Debug << "Values before reset: "
616	<< " erc: " << mExpectedCost
617	<< " avgrc: " << mAvgRenderCost
618	<< " dev: " << mDeviation << endl;
619
620	// adjust render cost
621	++ pass;
622
623	mergedPerPass = 0;
624	mExpectedCost = realExpectedCost;
625	mAvgRenderCost = realAvgRenderCost;
626	mNumActiveViewCells = realNumActiveViewCells;
627
628	const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
629
630	/////////////////
631	//-- reset / refine the view cells
632	//-- priorities are recomputed
633	//-- the candidates are put back into merge queue
634
635	if (mRefineViewCells)
636	RefineViewCells(rays, objects);
637	else
638	ResetMergeQueue();
639
640	Debug << "Values after reset: "
641	<< " erc: " << mExpectedCost
642	<< " avg: " << mAvgRenderCost
643	<< " dev: " << mDeviation << endl;
644
645	if (mExportMergedViewCells)
646	{
647	ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
648	}
649	}
650
651
652	MergeCandidate mc = mMergeQueue.top();
653	mMergeQueue.pop();
654
655	// both view cells equal because of previous merges
656	// NOTE: do I really still need this? probably cannot happen!!
657	if (mc.mLeftViewCell == mc.mRightViewCell)
658	continue;
659
660	if (mc.IsValid())
661	{
662	ViewCell::NewMail();
663
664	//-- update statistical values
665	-- realNumActiveViewCells;
666	++ mergeStats.merged;
667	++ mergedPerPass;
668
669	const float renderCostIncr = mc.GetRenderCost();
670	const float mergeCostIncr = mc.GetMergeCost();
671
672	totalRenderCost += renderCostIncr;
673	mDeviation += mc.GetDeviationIncr();
674
675
676	//-- merge the view cells of leaf1 and leaf2
677	float pvsDiff;
678	ViewCellInterior *mergedVc =
679	MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
680
681	// total render cost and deviation has changed
682	// real expected cost will be larger than expected cost used for the
683	// cost heuristics, but cannot recompute costs on each increase of the
684	// expected cost
685	totalPvs += pvsDiff;
686	realExpectedCost = totalRenderCost / (float)realNumActiveViewCells;
687	realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
688
689	// set merge cost to this node for priority traversal
690	mergedVc->SetMergeCost(totalRenderCost);
691
692	// check if "siblings (back and front node of the same parent)
693	if (0) ++ mergeStats.siblings;
694
695	// set the cost for rendering a view cell
696	mergedVc->SetCost(realExpectedCost);
697
698	if ((mergeStats.merged % statsOut) == 0)
699	cout << "merged " << mergeStats.merged << " view cells" << endl;
700
701	}
702	else
703	{
704	// merge candidate not valid, because one of the leaves was already
705	// merged with another one => validate and reinsert into queue
706	if (ValidateMergeCandidate(mc))
707	{
708	EvalMergeCost(mc);
709	mMergeQueue.push(mc);
710	}
711	}
712
713	}
714
715	// adjust stats and reset queue one final time
716	mExpectedCost = realExpectedCost;
717	mAvgRenderCost = realAvgRenderCost;
718	mNumActiveViewCells = realNumActiveViewCells;
719
720	UpdateActiveViewCells(activeViewCells);
721
722	// refine view cells and reset costs
723	if (mRefineViewCells)
724	RefineViewCells(rays, objects);
725	else
726	ResetMergeQueue();
727
728
729	// create a root node if the merge was not done till root level,
730	// else take the single node as new root
731	if ((int)activeViewCells.size() > 1)
732	{
733	Debug << "creating root of view cell hierarchy for "
734	<< (int)activeViewCells.size() << " view cells" << endl;
735
736	ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
737
738	ViewCellContainer::const_iterator it, it_end = root->mChildren.end();
739
740	for (it = root->mChildren.begin(); it != it_end; ++ it)
741	(*it)->SetParent(root);
742
743	root->SetMergeCost(totalRenderCost);
744	// $$JB keep this 0 temporarilly
745	root->SetCost(0.0f);
746
747	mRoot = root;
748	}
749	// normal case
750	else if (!activeViewCells.empty())
751	{
752	Debug << "setting root of the merge history" << endl;
753	mRoot = activeViewCells[0];
754	}
755	else
756	{
757	Debug << "big error, root is NULL" << endl;
758	}
759
760	//-- empty merge queue just in case
761	while (!mMergeQueue.empty())
762	{
763	mMergeQueue.pop();
764	}
765
766	// test if computed volumes are correct
767	Debug << "volume of the root view cell: " << mRoot->GetVolume()
768	<< " " << mViewCellsManager->GetViewSpaceBox().GetVolume() << endl;
769
770	// TODO: delete because makes no sense here
771	mergeStats.expectedRenderCost = realExpectedCost;
772	mergeStats.deviation = mDeviation;
773
774	// we want to optimize this heuristics
775	mergeStats.heuristics =
776	mDeviation * (1.0f - mRenderCostWeight) +
777	mExpectedCost * mRenderCostWeight;
778
779	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
780	mergeStats.Stop();
781	Debug << mergeStats << endl << endl;
782
783	// assign colors for the view cells so that at least one is always consistent
784	AssignRandomColors();
785
786	//TODO: should return sample contributions?
787	return mergeStats.merged;
788	}
789
790
791	ViewCell *ViewCellsTree::GetRoot() const
792	{
793	return mRoot;
794	}
795
796
797	void ViewCellsTree::ResetMergeQueue()
798	{
799	cout << "reset merge queue ... ";
800
801	vector<MergeCandidate> buf;
802	buf.reserve(mMergeQueue.size());
803
804
805	// store merge candidates in intermediate buffer
806	while (!mMergeQueue.empty())
807	{
808	MergeCandidate mc = mMergeQueue.top();
809	mMergeQueue.pop();
810
811	// recalculate cost
812	if (ValidateMergeCandidate(mc))
813	{
814	EvalMergeCost(mc);
815	buf.push_back(mc);
816	}
817	}
818
819	vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
820
821	// reinsert back into queue
822	for (bit = buf.begin(); bit != bit_end; ++ bit)
823	{
824	mMergeQueue.push(*bit);
825	}
826
827	cout << "finished" << endl;
828	}
829
830
831	float ViewCellsTree::ComputeMergedPvsCost(const ObjectPvs &pvs1,
832	const ObjectPvs &pvs2) const
833	{
834	// computes render cost of merge
835	float renderCost = 0;
836
837	// compute new pvs size
838	Intersectable::NewMail();
839
840	ObjectPvsIterator pit = pvs1.GetIterator();
841
842	// first mail all objects in first pvs
843	while (pit.HasMoreEntries())
844	{
845	ObjectPvsEntry entry = pit.Next();
846
847	Intersectable *obj = entry.mObject;
848
849	obj->Mail();
850	renderCost += mViewCellsManager->EvalRenderCost(obj);
851	}
852
853	ObjectPvsIterator pit2 = pvs2.GetIterator();
854
855	while (pit2.HasMoreEntries())
856	{
857	ObjectPvsEntry entry = pit2.Next();
858	Intersectable *obj = entry.mObject;
859
860	// test if object already considered
861	if (!obj->Mailed())
862	{
863	renderCost += mViewCellsManager->EvalRenderCost(obj);
864	}
865	}
866
867	return renderCost;
868	}
869
870
871	int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
872	{
873	int numMergedViewCells = 0;
874
875	Debug << "updating active vc: " << (int)viewCells.size() << endl;
876
877	// find all already merged view cells and remove them from the
878	// container view cells
879
880	// sort out all view cells which are not active anymore, i.e., they
881	// were already part of a merge
882	int i = 0;
883
884	ViewCell::NewMail();
885
886	while (1)
887	{
888	// remove all merged view cells from end of the vector
889	while (!viewCells.empty() && (viewCells.back()->GetParent()))
890	{
891	viewCells.pop_back();
892	}
893
894	// all merged view cells have been found
895	if (i >= (int)viewCells.size())
896	break;
897
898	// already merged this view cell, put it to end of vector
899	if (viewCells[i]->GetParent())
900	swap(viewCells[i], viewCells.back());
901
902	// mail view cell that it has not been merged
903	viewCells[i]->Mail();
904
905	// increase loop counter
906	++ i;
907	}
908
909
910	// add new view cells to container only if they don't have been
911	// merged in the mean time
912	ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
913
914	for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
915	{
916	ViewCell *vc = mMergedViewCells.back();
917	if (!vc->GetParent() && !vc->Mailed())
918	{
919	vc->Mail();
920	viewCells.push_back(vc);
921	++ numMergedViewCells;
922	}
923	}
924
925	// dispose old merged view cells
926	mMergedViewCells.clear();
927
928	// update standard deviation
929	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
930
931	mDeviation = 0;
932
933	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
934	{
935	const float lower = (float)mViewCellsManager->GetMinPvsSize();
936	const float upper = (float)mViewCellsManager->GetMaxPvsSize();
937
938	const float penalty = EvalPvsPenalty((*vit)->GetPvs().EvalPvsCost(), lower, upper);
939
940	mDeviation += fabs(mAvgRenderCost - penalty);
941	}
942
943	mDeviation /= (float)viewCells.size();
944
945	return numMergedViewCells;
946	}
947
948
949	void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
950	const ObjectContainer &objects,
951	const int numMergedViewCells)
952	{
953
954
955	char s[64];
956
957	sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
958	Exporter *exporter = Exporter::GetExporter(s);
959
960	if (exporter)
961	{
962	cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
963	exporter->ExportGeometry(objects);
964	//Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
965	ViewCellContainer::const_iterator it, it_end = viewCells.end();
966
967	int i = 0;
968	for (it = viewCells.begin(); it != it_end; ++ it)
969	{
970	Material m;
971	// assign special material to new view cells
972	// new view cells are on the back of container
973	if (i ++ >= (viewCells.size() - numMergedViewCells))
974	{
975	//m = RandomMaterial();
976	m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
977	m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
978	m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
979	}
980	else
981	{
982	float col = RandomValue(0.1f, 0.4f);
983	m.mDiffuseColor.r = col;
984	m.mDiffuseColor.g = col;
985	m.mDiffuseColor.b = col;
986	}
987
988	exporter->SetForcedMaterial(m);
989	mViewCellsManager->ExportViewCellGeometry(exporter, *it, NULL, NULL);
990	}
991
992	delete exporter;
993	cout << "finished" << endl;
994	}
995	}
996
997
998	// TODO: should be done in view cells manager
999	ViewCellInterior ViewCellsTree::MergeViewCells(ViewCell left,
1000	ViewCell *right,
1001	float &pvsDiff) //const
1002	{
1003	// create merged view cell
1004	ViewCellInterior *vc =
1005	mViewCellsManager->MergeViewCells(left, right);
1006
1007	// if merge was unsuccessful
1008	if (!vc) return NULL;
1009
1010	// set to the new parent view cell
1011	left->SetParent(vc);
1012	right->SetParent(vc);
1013
1014
1015	if (mUseAreaForPvs)
1016	{
1017	// set new area of view cell
1018	// not not correct, but costly to compute real area!!
1019	vc->SetArea(left->GetArea() + right->GetArea());
1020	}
1021	else
1022	{ // set new volume of view cell
1023	vc->SetVolume(left->GetVolume() + right->GetVolume());
1024	}
1025
1026
1027	// important so other merge candidates sharing this view cell
1028	// are notified that the merge cost must be updated!!
1029	vc->Mail();
1030
1031	const float pvs1 = left->GetPvs().EvalPvsCost();
1032	const float pvs2 = right->GetPvs().EvalPvsCost();
1033
1034
1035	// the new view cells are stored in this container
1036	mMergedViewCells.push_back(vc);
1037
1038	pvsDiff = vc->GetPvs().EvalPvsCost() - pvs1 - pvs2;
1039
1040
1041	// don't store pvs in interior cells, just a scalar
1042	if (mViewCellsStorage == PVS_IN_LEAVES)
1043	{
1044	// set scalars
1045	mViewCellsManager->UpdateScalarPvsSize(left,
1046	left->GetPvs().EvalPvsCost(),
1047	left->GetPvs().GetSize());
1048
1049	// remove pvs, we don't store interior pvss
1050	if (!left->IsLeaf())
1051	{
1052	left->GetPvs().Clear();
1053	}
1054
1055	// set scalars
1056	mViewCellsManager->UpdateScalarPvsSize(right,
1057	right->GetPvs().EvalPvsCost(),
1058	right->GetPvs().GetSize());
1059
1060	right->mPvsSizeValid = true;
1061
1062	// remove pvs, we don't store interior pvss
1063	if (!right->IsLeaf())
1064	{
1065	right->GetPvs().Clear();
1066	}
1067	}
1068
1069	return vc;
1070	}
1071
1072
1073	int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
1074	const ObjectContainer &objects)
1075	{
1076	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
1077
1078	// intermediate buffer for shuffled view cells
1079	vector<MergeCandidate> buf;
1080	buf.reserve(mMergeQueue.size());
1081
1082	// Use priority queue of remaining leaf pairs
1083	// The candidates either share the same view cells or
1084	// are border leaves which share a boundary.
1085	// We test if they can be shuffled, i.e.,
1086	// either one leaf is made part of one view cell or the other
1087	// leaf is made part of the other view cell. It is tested if the
1088	// remaining view cells are "better" than the old ones.
1089
1090	const int numPasses = 3;
1091	int pass = 0;
1092	int passShuffled = 0;
1093	int shuffled = 0;
1094	int shuffledViewCells = 0;
1095
1096	ViewCell::NewMail();
1097
1098	while (!mMergeQueue.empty())
1099	{
1100	MergeCandidate mc = mMergeQueue.top();
1101	mMergeQueue.pop();
1102
1103	// both view cells equal or already shuffled
1104	if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) \|\|
1105	mc.GetLeftViewCell()->IsLeaf() \|\| mc.GetRightViewCell()->IsLeaf())
1106	{
1107	continue;
1108	}
1109
1110	// candidate for shuffling
1111	const bool wasShuffled = ShuffleLeaves(mc);
1112
1113	// shuffled or put into other queue for further refine
1114	if (wasShuffled)
1115	{
1116	++ passShuffled;
1117
1118	if (!mc.GetLeftViewCell()->Mailed())
1119	{
1120	mc.GetLeftViewCell()->Mail();
1121	++ shuffledViewCells;
1122	}
1123	if (!mc.GetRightViewCell()->Mailed())
1124	{
1125	mc.GetRightViewCell()->Mail();
1126	++ shuffledViewCells;
1127	}
1128	}
1129
1130	// put back into intermediate vector
1131	buf.push_back(mc);
1132	}
1133
1134
1135	//-- in the end, the candidates must be in the mergequeue again
1136	// with the correct cost
1137
1138	cout << "reset merge queue ... ";
1139
1140
1141	vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
1142
1143	for (bit = buf.begin(); bit != bit_end; ++ bit)
1144	{
1145	MergeCandidate mc = *bit;
1146	// recalculate cost
1147	if (ValidateMergeCandidate(mc))
1148	{
1149	EvalMergeCost(mc);
1150	mMergeQueue.push(mc);
1151	}
1152	}
1153
1154	cout << "finished" << endl;
1155
1156	return shuffledViewCells;
1157	}
1158
1159
1160	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1161	{
1162	ObjectPvs interPvs;
1163	ObjectPvs::Merge(interPvs, pvs1, pvs2);
1164
1165	return (int)interPvs.GetSize();
1166	}
1167
1168
1169	// recomputes pvs size minus pvs of leaf l
1170	#if 0
1171	inline int SubtractedPvsSize(BspViewCell vc, BspLeaf l, const ObjectPvs &pvs2)
1172	{
1173	ObjectPvs pvs;
1174	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1175	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1176	if (*it != l)
1177	pvs.AddPvs((it)->mPvs);
1178	return pvs.GetSize();
1179	}
1180	#endif
1181
1182
1183	// computes pvs1 minus pvs2
1184	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1185	{
1186	return pvs1.SubtractPvs(pvs2);
1187	}
1188
1189
1190	float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1191	ViewCellInterior *vc1,
1192	ViewCellInterior *vc2) const
1193	{
1194	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1195	const float pvs1 = (float)SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1196	const float pvs2 = (float)AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1197
1198	const float lowerPvsLimit = (float)mViewCellsManager->GetMinPvsSize();
1199	const float upperPvsLimit = (float)mViewCellsManager->GetMaxPvsSize();
1200
1201	const float pvsPenalty1 =
1202	EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1203
1204	const float pvsPenalty2 =
1205	EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1206
1207
1208	// don't shuffle leaves with pvs > max
1209	if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1210	{
1211	return 1e20f;
1212	}
1213
1214	float p1, p2;
1215
1216	if (mUseAreaForPvs)
1217	{
1218	p1 = vc1->GetArea() - leaf->GetArea();
1219	p2 = vc2->GetArea() + leaf->GetArea();
1220	}
1221	else
1222	{
1223	p1 = vc1->GetVolume() - leaf->GetVolume();
1224	p2 = vc2->GetVolume() + leaf->GetVolume();
1225	}
1226
1227	const float renderCost1 = pvsPenalty1 * p1;
1228	const float renderCost2 = pvsPenalty2 * p2;
1229
1230	float dev1, dev2;
1231
1232	if (1)
1233	{
1234	dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1235	dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1236	}
1237	else
1238	{
1239	dev1 = fabs(mExpectedCost - renderCost1);
1240	dev2 = fabs(mExpectedCost - renderCost2);
1241	}
1242
1243	return mRenderCostWeight * (renderCost1 + renderCost2) +
1244	(1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1245	}
1246
1247
1248	void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1249	ViewCellInterior *vc1,
1250	ViewCellInterior *vc2) const
1251	{
1252	// compute new pvs and area
1253	// TODO change
1254	vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1255
1256	ObjectPvs interPvs;
1257	ObjectPvs::Merge(interPvs, vc2->GetPvs(), leaf->GetPvs());
1258	vc2->SetPvs(interPvs);
1259
1260	if (mUseAreaForPvs)
1261	{
1262	vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1263	vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1264	}
1265	else
1266	{
1267	vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1268	vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1269	}
1270
1271
1272	ViewCellInterior p = dynamic_cast<ViewCellInterior >(leaf->GetParent());
1273
1274	p->RemoveChildLink(leaf);
1275	vc2->SetupChildLink(leaf);
1276	}
1277
1278
1279	bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1280	{
1281	float cost1, cost2;
1282
1283	ViewCellInterior vc1 = dynamic_cast<ViewCellInterior >(mc.GetLeftViewCell());
1284	ViewCellInterior vc2 = dynamic_cast<ViewCellInterior >(mc.GetRightViewCell());
1285
1286	ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1287	ViewCell *leaf2 = mc.GetInitialRightViewCell();
1288
1289	//-- first test if shuffling would decrease cost
1290	cost1 = GetCostHeuristics(vc1);
1291	cost2 = GetCostHeuristics(vc2);
1292
1293	const float oldCost = cost1 + cost2;
1294
1295	float shuffledCost1 = Limits::Infinity;
1296	float shuffledCost2 = Limits::Infinity;
1297
1298	if (leaf1)
1299	shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);
1300	if (leaf2)
1301	shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1302
1303	// if cost of shuffle is less than old cost => shuffle
1304	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1305	return false;
1306
1307	if (shuffledCost1 < shuffledCost2)
1308	{
1309	if (leaf1)
1310	ShuffleLeaf(leaf1, vc1, vc2);
1311	mc.mInitialLeftViewCell = NULL;
1312	}
1313	else
1314	{
1315	if (leaf2)
1316	ShuffleLeaf(leaf2, vc2, vc1);
1317	mc.mInitialRightViewCell = NULL;
1318	}
1319
1320	return true;
1321	}
1322
1323
1324	float ViewCellsTree::GetVariance(ViewCell *vc) const
1325	{
1326	const float upper = (float)mViewCellsManager->GetMaxPvsSize();
1327	const float lower = (float)mViewCellsManager->GetMinPvsSize();
1328
1329	if (1)
1330	{
1331	const float penalty =
1332	EvalPvsPenalty(GetPvsCost(vc), lower, upper);
1333
1334	return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) /
1335	(float)mNumActiveViewCells;
1336	}
1337
1338	const float leafCost = GetRenderCost(vc);
1339	return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1340	}
1341
1342
1343	float ViewCellsTree::GetDeviation(ViewCell *vc) const
1344	{
1345	const float upper = (float)mViewCellsManager->GetMaxPvsSize();
1346	const float lower = (float)mViewCellsManager->GetMinPvsSize();
1347
1348	if (1)
1349	{
1350	const float penalty = EvalPvsPenalty(GetPvsCost(vc), lower, upper);
1351	return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1352	}
1353
1354	const float renderCost = GetRenderCost(vc);
1355	return fabs(mExpectedCost - renderCost);
1356	}
1357
1358
1359	float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1360	{
1361	if (mUseAreaForPvs)
1362	{
1363	return vc->GetPvs().EvalPvsCost() * vc->GetArea();
1364	}
1365
1366	return vc->GetPvs().EvalPvsCost() * vc->GetVolume();
1367	}
1368
1369
1370	float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1371	{
1372	return GetRenderCost(vc) * mRenderCostWeight +
1373	GetDeviation(vc) * (1.0f - mRenderCostWeight);
1374	}
1375
1376
1377	bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1378	{
1379	// propagate up so we have only the active view cells
1380	while (mc.mLeftViewCell->mParent)
1381	{
1382	mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1383	}
1384
1385	while (mc.mRightViewCell->mParent)
1386	{
1387	mc.mRightViewCell = mc.mRightViewCell->mParent;
1388	}
1389
1390	// this view cell was already merged
1391	//return mc.mLeftViewCell && (mc.mLeftViewCell != mc.mRightViewCell);
1392	return mc.mLeftViewCell != mc.mRightViewCell;
1393	}
1394
1395
1396	void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1397	{
1398	///////////////////
1399	//-- compute pvs difference
1400
1401	float newPvs;
1402
1403	// not valid if not using const cost per object!!
1404	newPvs = ComputeMergedPvsCost(mc.mLeftViewCell->GetPvs(), mc.mRightViewCell->GetPvs());
1405
1406
1407	const float newPenalty = EvalPvsPenalty(newPvs,
1408	(float)mViewCellsManager->GetMinPvsSize(),
1409	(float)mViewCellsManager->GetMaxPvsSize());
1410
1411	ViewCell *vc1 = mc.mLeftViewCell;
1412	ViewCell *vc2 = mc.mRightViewCell;
1413
1414	//-- compute ratio of old cost
1415	//-- (i.e., added size of left and right view cell times pvs size)
1416	//-- to new rendering cost (i.e, size of merged view cell times pvs size)
1417	const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1418
1419	const float newCost = mUseAreaForPvs ?
1420	(float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1421	(float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1422
1423
1424	// strong penalty if pvs size too large
1425	if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1426	{
1427	mc.mRenderCost = 1e20f;
1428	}
1429	else
1430	{
1431	mc.mRenderCost = (newCost - oldCost) /
1432	mViewCellsManager->GetViewSpaceBox().GetVolume();
1433	}
1434
1435	///////////////////////////
1436	//-- merge cost also takes deviation into account
1437
1438	float newDev, oldDev;
1439
1440	if (1)
1441	newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1442	else
1443	newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1444
1445	oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1446
1447	// compute deviation increase
1448	mc.mDeviationIncr = newDev - oldDev;
1449
1450	//Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1451	//Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1452	}
1453
1454
1455	void ViewCellsTree::SetViewCellsStorage(int stype)
1456	{
1457	if (mViewCellsStorage == stype)
1458	return;
1459
1460	// TODO
1461	switch (stype)
1462	{
1463	case COMPRESSED:
1464	CompressViewCellsPvs(mRoot);
1465	break;
1466	default:
1467	break;
1468	}
1469
1470	mViewCellsStorage = stype;
1471	}
1472
1473
1474	void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1475	{
1476	if (!root->IsLeaf())
1477	{
1478	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
1479
1480	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1481
1482	// compress child sets first
1483	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1484	{
1485	CompressViewCellsPvs(*it);
1486	}
1487
1488	// compress root node
1489	PullUpVisibility(interior);
1490	}
1491	}
1492
1493
1494	void ViewCellsTree::UpdateStats(ofstream &stats,
1495	const ViewCellsTreeStats &vcStats)
1496	{
1497	stats << "#Pass\n" << vcStats.mPass << endl
1498	<< "#Splits\n" << vcStats.mNumViewCells << endl
1499	<< "#RenderCostDecrease\n" << vcStats.mRenderCostDecrease << endl // TODO
1500	<< "#TotalRenderCost\n" << vcStats.mTotalRenderCost << endl
1501	<< "#CurrentPvs\n" << vcStats.mCurrentPvsCost << endl
1502	<< "#ExpectedCost\n" << vcStats.mExpectedCost << endl
1503	<< "#AvgRenderCost\n" << vcStats.mAvgRenderCost << endl
1504	<< "#Deviation\n" << vcStats.mDeviation << endl
1505	<< "#TotalPvs\n" << vcStats.mTotalPvsCost << endl
1506	<< "#TotalEntriesInPvs\n" << vcStats.mEntriesInPvs << endl
1507	<< "#Memory\n" << vcStats.mMemoryCost << endl
1508	<< "#PvsSizeDecrease\n" << vcStats.mPvsSizeDecr << endl
1509	<< "#Volume\n" << vcStats.mVolume << endl
1510	<< endl;
1511	}
1512
1513
1514	void ViewCellsTree::ExportStats(const string &mergeStats)
1515	{
1516	TraversalQueue tqueue;
1517	tqueue.push(mRoot);
1518
1519	ViewCellsTreeStats vcStats;
1520	vcStats.Reset();
1521
1522	//cout << "exporting stats ... " << endl;
1523	vcStats.mNumViewCells = 1;
1524
1525	const AxisAlignedBox3 box = mViewCellsManager->GetViewSpaceBox();
1526	const float vol = box.GetVolume();
1527
1528	const float rootPvs = GetPvsCost(mRoot);
1529	const int rootEntries = GetPvsEntries(mRoot);
1530
1531	vcStats.mTotalPvsCost = rootPvs;
1532	vcStats.mTotalRenderCost = rootPvs;
1533	vcStats.mAvgRenderCost = rootPvs;
1534	vcStats.mExpectedCost = rootPvs;
1535
1536	vcStats.mEntriesInPvs = rootEntries;
1537
1538	ofstream stats;
1539	stats.open(mergeStats.c_str());
1540
1541	vcStats.mMemoryCost = (float)vcStats.mEntriesInPvs * ObjectPvs::GetEntrySize();
1542
1543	/////////////
1544	//-- first view cell
1545
1546	UpdateStats(stats, vcStats);
1547
1548
1549	//-- go through tree in the order of render cost decrease
1550	//-- which is the same order as the view cells were merged
1551	//-- or the reverse order of subdivision for subdivision-only
1552	//-- view cell hierarchies.
1553
1554	while (!tqueue.empty())
1555	{
1556	ViewCell *vc = tqueue.top();
1557	tqueue.pop();
1558
1559	if (!vc->IsLeaf())
1560	{
1561	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1562
1563	const float parentCost = GetPvsCost(interior);
1564	const int parentPvsEntries = GetPvsEntries(interior);
1565	const float parentExpCost = (float)parentCost * interior->GetVolume();
1566
1567	float childExpCost = 0;
1568	float childCost = 0;
1569	int childPvsEntries = 0;
1570
1571	-- vcStats.mNumViewCells;
1572
1573	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1574
1575	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1576	{
1577	ViewCell vc = it;
1578
1579	const float pvsCost = GetPvsCost(vc);
1580	const int pvsEntries = GetPvsEntries(vc);
1581
1582	childExpCost += childCost * vc->GetVolume();
1583	childCost += pvsCost;
1584	childPvsEntries += pvsEntries;
1585
1586	tqueue.push(vc);
1587	++ vcStats.mNumViewCells;
1588	}
1589
1590	// update stats for this view cell
1591	const float costDecr = (parentExpCost - childExpCost) / vol;
1592
1593	vcStats.mTotalRenderCost -= costDecr;
1594	vcStats.mTotalPvsCost += childCost - parentCost;
1595	vcStats.mEntriesInPvs += childPvsEntries - parentPvsEntries;
1596
1597	vcStats.mExpectedCost = vcStats.mTotalRenderCost / (float)vcStats.mNumViewCells;
1598	vcStats.mAvgRenderCost = vcStats.mTotalPvsCost / (float)vcStats.mNumViewCells;
1599
1600	vcStats.mMemoryCost = vcStats.mEntriesInPvs * ObjectPvs::GetEntrySize();
1601
1602	UpdateStats(stats, vcStats);
1603	}
1604	}
1605
1606	stats.close();
1607	}
1608
1609
1610	void ViewCellsTree::SetRoot(ViewCell *root)
1611	{
1612	mRoot = root;
1613	}
1614
1615
1616	void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1617	const int numViewCells)
1618	{
1619	TraversalQueue tqueue;
1620	tqueue.push(mRoot);
1621
1622	while (!tqueue.empty())
1623	{
1624	ViewCell *vc = tqueue.top();
1625	tqueue.pop();
1626
1627	// save the view cells if it is a leaf or if enough view cells have already been traversed
1628	// because of the priority queue, this will be the optimal set of v
1629	if (vc->IsLeaf() \|\| ((viewCells.size() + tqueue.size() + 1) >= numViewCells))
1630	{
1631	viewCells.push_back(vc);
1632	}
1633	else
1634	{
1635	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1636
1637	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1638
1639	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1640	{
1641	tqueue.push(*it);
1642	}
1643	}
1644	}
1645	}
1646
1647
1648	void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
1649	{
1650	Intersectable::NewMail((int)interior->mChildren.size());
1651
1652	ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1653
1654	// mail all objects in the leaf sets
1655	// we are interested in the objects which are present in all leaves
1656	// => count how often an object is part of a child set
1657	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1658	{
1659	ViewCell vc = cit;
1660
1661	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1662
1663	while (pit.HasMoreEntries())
1664	{
1665	ObjectPvsEntry entry = pit.Next();
1666	Intersectable *obj = entry.mObject;
1667
1668	if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1669	{
1670	obj->Mail();
1671	}
1672
1673	int incm = obj->IncMail();
1674	}
1675	}
1676
1677	interior->GetPvs().Clear();
1678
1679	// only the objects which are present in all leaf pvs
1680	// should remain in the parent pvs
1681	// these are the objects which have been mailed in all children
1682	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1683	{
1684	ViewCell vc = cit;
1685
1686	ObjectPvsIterator pit = vc->GetPvs().GetIterator();
1687
1688	while (pit.HasMoreEntries())
1689	{
1690	ObjectPvsEntry entry = pit.Next();
1691
1692	if (entry.mObject->Mailed((int)interior->mChildren.size()))
1693	{
1694	interior->GetPvs().AddSample(entry.mObject, entry.mData.mSumPdf);
1695	}
1696	}
1697	}
1698
1699	// delete all the objects from the leaf sets which were moved to parent pvs
1700	ObjectPvsIterator pit = interior->GetPvs().GetIterator();
1701
1702	while (pit.HasMoreEntries())
1703	{
1704	ObjectPvsEntry entry = pit.Next();
1705
1706	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1707	{
1708	if (!(*cit)->GetPvs().RemoveSample(entry.mObject, Limits::Infinity))
1709	{
1710	Debug << "should not come here!" << endl;
1711	}
1712	}
1713	}
1714	}
1715
1716
1717	// TODO matt: implement this function for different storing methods
1718	void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1719	{
1720	// pvs is stored in each cell => just return pvs
1721	if (mViewCellsStorage == PVS_IN_INTERIORS)
1722	{
1723	pvs = vc->GetPvs();
1724	return;
1725	}
1726
1727	////////////////
1728	//-- pvs is not stored with the interiors => reconstruct
1729	ViewCell *root = vc;
1730
1731	// add pvs from this view cell to root
1732	while (root->GetParent())
1733	{
1734	root = root->GetParent();
1735	pvs.MergeInPlace(root->GetPvs());
1736	}
1737
1738	// add pvs from leaves
1739	stack<ViewCell *> tstack;
1740	tstack.push(vc);
1741
1742	while (!tstack.empty())
1743	{
1744	vc = tstack.top();
1745	tstack.pop();
1746
1747	// add newly found pvs to merged pvs
1748	pvs.MergeInPlace(vc->GetPvs());
1749
1750	if (!vc->IsLeaf()) // interior cells: go down to leaf level
1751	{
1752	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1753	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1754
1755	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1756	{
1757	tstack.push(*it);
1758	}
1759	}
1760	}
1761	}
1762
1763
1764	float ViewCellsTree::GetPvsCostForLeafStorage(ViewCell *vc) const
1765	{
1766	// pvs is always stored directly in leaves
1767	if (vc->IsLeaf())
1768	{
1769	return vc->GetPvs().EvalPvsCost();
1770	}
1771
1772	// interior nodes: pvs is either stored as a
1773	// scalar or has to be reconstructed from the leaves
1774	// the stored pvs size is the valid pvs size => just return scalar
1775	if (vc->mPvsSizeValid)
1776	{
1777	return vc->mPvsCost;
1778	}
1779
1780	// if no valid pvs size stored as a scalar =>
1781	// compute current pvs size of interior from it's leaf nodes
1782	ViewCellContainer leaves;
1783	CollectLeaves(vc, leaves);
1784
1785	ViewCellContainer::const_iterator it, it_end = leaves.end();
1786
1787	ObjectPvs newPvs;
1788
1789	// sum up uniquely found intersectables
1790	for (it = leaves.begin(); it != it_end; ++ it)
1791	{
1792	newPvs.MergeInPlace((*it)->GetPvs());
1793	}
1794
1795	return newPvs.EvalPvsCost();
1796	}
1797
1798
1799	int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1800	{
1801	// pvs is always stored directly in leaves
1802	if (vc->IsLeaf())
1803	{
1804	return vc->GetPvs().GetSize();
1805	}
1806
1807	// interior node
1808
1809	// interior nodes: pvs is either stored as a scalar or
1810	// has to be reconstructed from the leaves
1811
1812	// the stored pvs size is the valid pvs size => just return scalar
1813	if (vc->mPvsSizeValid)
1814	{
1815	return vc->mEntriesInPvs;
1816	}
1817
1818	int pvsSize = 0;
1819
1820	// if no valid pvs size stored as a scalar =>
1821	// compute current pvs size of interior from it's leaf nodes
1822	ViewCellContainer leaves;
1823	CollectLeaves(vc, leaves);
1824
1825	ViewCellContainer::const_iterator it, it_end = leaves.end();
1826	Intersectable::NewMail();
1827
1828	// sum different intersectables
1829	for (it = leaves.begin(); it != it_end; ++ it)
1830	{
1831	ObjectPvsIterator oit = (*it)->GetPvs().GetIterator();
1832
1833	while (oit.HasMoreEntries())
1834	{
1835	ObjectPvsEntry entry = oit.Next();
1836	Intersectable *intersect = entry.mObject;
1837
1838	if (!intersect->Mailed())
1839	{
1840	intersect->Mail();
1841	++ pvsSize;
1842	}
1843	}
1844	}
1845
1846	return pvsSize;
1847	}
1848
1849
1850	float ViewCellsTree::GetPvsCostForCompressedStorage(ViewCell *vc) const
1851	{
1852	float pvsCost = 0;
1853
1854	/////////////
1855	//-- compressed pvs
1856
1857	// the stored pvs size is the valid pvs size => just return scalar
1858	if (vc->mPvsSizeValid)
1859	{
1860	pvsCost = vc->mPvsCost;
1861	}
1862
1863	// if no pvs size stored, compute new one
1864	ViewCell *root = vc;
1865
1866	// also add pvs from this view cell to root
1867	while (root->GetParent())
1868	{
1869	root = root->GetParent();
1870
1871	// matt: bug! must evaluate kd pvss also
1872	pvsCost += CountPvsContribution(root);
1873	}
1874
1875	stack<ViewCell *> tstack;
1876	tstack.push(vc);
1877
1878	while (!tstack.empty())
1879	{
1880	vc = tstack.top();
1881	tstack.pop();
1882
1883	// matt: bug! must evaluate kd pvss also
1884	pvsCost += CountPvsContribution(vc);
1885
1886	if (!vc->IsLeaf())
1887	{
1888	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1889	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1890
1891	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1892	{
1893	tstack.push(*it);
1894	}
1895	}
1896	}
1897
1898	return pvsCost;
1899	}
1900
1901
1902	int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1903	{
1904	int pvsSize = 0;
1905
1906	/////////////////
1907	//-- compressed pvs
1908
1909	// the stored pvs size is the valid pvs size => just return scalar
1910	if (vc->mPvsSizeValid)
1911	{
1912	pvsSize = vc->mEntriesInPvs;
1913	}
1914
1915	// if no pvs size stored, compute new one
1916	ViewCell *root = vc;
1917
1918	// also add pvs from this view cell to root
1919	while (root->GetParent())
1920	{
1921	root = root->GetParent();
1922	// count the pvs entries different from the already found ones
1923	pvsSize += CountPvsContribution(root);
1924	}
1925
1926	stack<ViewCell *> tstack;
1927	tstack.push(vc);
1928
1929	while (!tstack.empty())
1930	{
1931	vc = tstack.top();
1932	tstack.pop();
1933
1934	// count the pvs entries different from the already found ones
1935	pvsSize += CountPvsContribution(vc);
1936
1937	if (!vc->IsLeaf())
1938	{
1939	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1940
1941	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1942
1943	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1944	{
1945	tstack.push(*it);
1946	}
1947	}
1948	}
1949
1950	return pvsSize;
1951	}
1952
1953
1954	float ViewCellsTree::GetPvsCost(ViewCell *vc) const
1955	{
1956	float pvsCost = 0;
1957	Intersectable::NewMail();
1958
1959	////////////////////////////////////////////////
1960	// for interiors, pvs can be stored using different methods
1961	//
1962
1963	switch (mViewCellsStorage)
1964	{
1965	case PVS_IN_LEAVES:
1966	// pvs is stored only in leaves
1967	pvsCost = GetPvsCostForLeafStorage(vc);
1968	break;
1969	case COMPRESSED:
1970	pvsCost = GetPvsCostForCompressedStorage(vc);
1971	break;
1972	case PVS_IN_INTERIORS:
1973	default:
1974	// pvs is stored consistently in the tree up
1975	//to the root just return pvs size
1976	pvsCost = vc->GetPvs().EvalPvsCost();
1977	break;
1978	}
1979
1980	return pvsCost;
1981	}
1982
1983
1984	int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
1985	{
1986	int pvsSize = 0;
1987
1988	Intersectable::NewMail();
1989
1990	////////////////////////////////////////////////
1991	// for interiors, pvs can be stored using different methods
1992
1993	switch (mViewCellsStorage)
1994	{
1995	case PVS_IN_LEAVES:
1996	{
1997	//-- store pvs only in leaves
1998	pvsSize = GetEntriesInPvsForLeafStorage(vc);
1999	break;
2000	}
2001	case COMPRESSED:
2002	{
2003	pvsSize = GetEntriesInPvsForCompressedStorage(vc);
2004	break;
2005	}
2006	case PVS_IN_INTERIORS:
2007	default:
2008	// pvs is stored consistently in the tree up to the root
2009	// just return pvs size
2010	pvsSize = vc->GetPvs().GetSize();
2011	break;
2012	}
2013
2014	return pvsSize;
2015	}
2016
2017
2018	float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2019	{
2020	return (float)CountStoredPvsEntries(vc) * ObjectPvs::GetEntrySize();
2021	}
2022
2023	//#if HAS_TO_BE_REDONE
2024	int ViewCellsTree::CountStoredPvsEntries(ViewCell *root) const
2025	{
2026	int pvsSize = root->GetPvs().GetSize();
2027
2028	// recursivly count leaves
2029	if (!root->IsLeaf())
2030	{
2031	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
2032
2033	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2034
2035	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2036	{
2037	pvsSize += CountStoredPvsEntries(*it);
2038	}
2039	}
2040
2041	return pvsSize;
2042	}
2043	//#endif
2044
2045	int ViewCellsTree::ViewCellsStorage() const
2046	{
2047	return mViewCellsStorage;
2048	}
2049
2050
2051	ViewCell ViewCellsTree::GetActiveViewCell(ViewCellLeaf vc) const
2052	{
2053	return vc->GetActiveViewCell();
2054	}
2055
2056
2057	void ViewCellsTree::PropagatePvs(ViewCell *root)
2058	{
2059	ViewCell *viewCell = root;
2060
2061	// propagate pvs up
2062	while (viewCell->GetParent())
2063	{
2064	ObjectPvs mergedPvs;
2065	viewCell->GetParent()->GetPvs().MergeInPlace(root->GetPvs());
2066
2067	viewCell = viewCell->GetParent();
2068	}
2069
2070	if (root->IsLeaf())
2071	return;
2072
2073	// propagate pvs to the leaves
2074	stack<ViewCell *> tstack;
2075	tstack.push(root);
2076
2077	while (!tstack.empty())
2078	{
2079	ViewCell *viewCell = tstack.top();
2080	tstack.pop();
2081
2082	if (viewCell != root)
2083	{
2084	viewCell->GetPvs().MergeInPlace(root->GetPvs());
2085	}
2086
2087	if (!viewCell->IsLeaf())
2088	{
2089	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2090
2091	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2092
2093	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2094	{
2095	tstack.push(*it);
2096	}
2097	}
2098	}
2099	}
2100
2101
2102	void ViewCellsTree::AssignRandomColors()
2103	{
2104	TraversalQueue tqueue;
2105	tqueue.push(mRoot);
2106
2107	mRoot->SetColor(RandomColor(0.3f, 1.0f));
2108
2109	while (!tqueue.empty())
2110	{
2111	ViewCell *vc = tqueue.top();
2112	tqueue.pop();
2113
2114	// save the view cells if it is a leaf or if enough view cells
2115	// have already been traversed because of the priority queue,
2116	// this will be the optimal set of v
2117	if (!vc->IsLeaf())
2118	{
2119	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2120
2121	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2122
2123	float maxProbability = -1.0f;
2124
2125	ViewCell *maxViewCell = NULL;
2126	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2127	{
2128	ViewCell v = it;
2129
2130	// set random color
2131	v->SetColor(RandomColor(0.3f, 1.0f));
2132
2133	if (v->GetVolume() > maxProbability)
2134	{
2135	maxProbability = v->GetVolume();
2136	maxViewCell = v;
2137	}
2138
2139	if (maxViewCell)
2140	{
2141	maxViewCell->SetColor(vc->GetColor());
2142	}
2143
2144	tqueue.push(v);
2145	}
2146	}
2147	}
2148	}
2149
2150
2151	/** Get costs resulting from each merge step.
2152	*/
2153	void ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2154	{
2155	TraversalQueue tqueue;
2156	tqueue.push(mRoot);
2157
2158	int numViewCells = 1;
2159
2160	const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2161	const float rootPvs = GetPvsCost(mRoot);
2162
2163	float totalRenderCost;
2164
2165	float totalPvsCost = rootPvs;
2166	totalRenderCost = (float)rootPvs;
2167
2168	costFunction.push_back(totalRenderCost);
2169
2170	//-- go through tree in the order of render cost decrease
2171	//-- which is the same order as the view cells were merged
2172	//-- or the reverse order of subdivision for subdivision-only
2173	//-- view cell hierarchies.
2174
2175	while (!tqueue.empty())
2176	{
2177	ViewCell *vc = tqueue.top();
2178	tqueue.pop();
2179
2180	if (!vc->IsLeaf())
2181	{
2182	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2183
2184	const float parentCost = GetPvsCost(interior);
2185	const float parentExpCost = parentCost * interior->GetVolume();
2186
2187	-- numViewCells;
2188
2189	float childExpCost = 0;
2190	float childCost = 0;
2191
2192	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2193
2194	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2195	{
2196	ViewCell vc = it;
2197
2198	const float pvsCost = GetPvsCost(vc);
2199
2200	childExpCost += (float) pvsCost * vc->GetVolume();
2201	childCost += pvsCost;
2202
2203	tqueue.push(vc);
2204	++ numViewCells;
2205	}
2206
2207	// update stats for this view cell
2208	const float costDecr = (parentExpCost - childExpCost) / vol;
2209	totalRenderCost -= costDecr;
2210
2211	costFunction.push_back(totalRenderCost);
2212	}
2213	}
2214	}
2215
2216
2217	/** Get storage costs resulting from each merge step.
2218	*/
2219	void ViewCellsTree::GetStorageFunction(vector<int> &storageFunction)
2220	{
2221	TraversalQueue tqueue;
2222	tqueue.push(mRoot);
2223
2224	int numViewCells = 1;
2225
2226	const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2227	const int rootEntries = GetPvsEntries(mRoot);
2228
2229	int entriesInPvs = rootEntries;
2230	const int entryStorage = sizeof(PvsData) + sizeof(int); // one entry into the pvs
2231
2232	storageFunction.push_back(rootEntries);
2233
2234	////////////
2235	//-- go through tree in the order of render cost decrease
2236	//-- which is the same order as the view cells were merged
2237	//-- or the reverse order of subdivision for subdivision-only
2238	//-- view cell hierarchies.
2239
2240	while (!tqueue.empty())
2241	{
2242	ViewCell *vc = tqueue.top();
2243	tqueue.pop();
2244
2245	if (!vc->IsLeaf())
2246	{
2247	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2248
2249	const float parentPvsCost = GetPvsCost(interior);
2250	const int parentPvsEntries = GetPvsEntries(interior);
2251	const float parentExpCost = (float)parentPvsCost * interior->GetVolume();
2252
2253	float childExpCost = 0;
2254	int childPvs = 0;
2255	int childPvsEntries = 0;
2256
2257	-- numViewCells;
2258
2259	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2260
2261	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2262	{
2263	ViewCell vc = it;
2264
2265	const int pvsEntries = GetPvsEntries(vc);
2266	childPvsEntries += pvsEntries;
2267
2268	tqueue.push(vc);
2269	++ numViewCells;
2270	}
2271
2272	// update stats for this view cell
2273	const float costDecr = (parentExpCost - childExpCost) / vol;
2274
2275	entriesInPvs += childPvsEntries - parentPvsEntries;
2276
2277	const int storageCost = entriesInPvs * entryStorage;
2278	storageFunction.push_back(storageCost);
2279	}
2280	}
2281	}
2282
2283
2284
2285	void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2286	ViewCellsStatistics &vcStat)
2287	{
2288	++ vcStat.viewCells;
2289
2290	const float pvsCost = GetPvsCost(vc);
2291
2292	vcStat.pvsCost += pvsCost;
2293
2294	if (pvsCost < Limits::Small)
2295	++ vcStat.emptyPvs;
2296
2297	if (pvsCost > vcStat.maxPvs)
2298	vcStat.maxPvs = pvsCost;
2299
2300	if (pvsCost < vcStat.minPvs)
2301	vcStat.minPvs = pvsCost;
2302
2303	if (!vc->GetValid())
2304	++ vcStat.invalid;
2305	}
2306
2307
2308	bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2309	{
2310	// export recursivly all view cells from the root
2311	ExportViewCell(mRoot, stream, exportPvs);
2312
2313	return true;
2314	}
2315
2316
2317	void ViewCellsTree::CreateUniqueViewCellsIds()
2318	{
2319	stack<ViewCell *> tstack;
2320
2321	int currentId = 0;
2322
2323	tstack.push(mRoot);
2324
2325	while (!tstack.empty())
2326	{
2327	ViewCell *vc = tstack.top();
2328	tstack.pop();
2329
2330	if (vc->GetId() != -1) // out of bounds
2331	vc->SetId(currentId ++);
2332
2333	if (!vc->IsLeaf())
2334	{
2335	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2336
2337	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2338	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2339	{
2340	tstack.push(*it);
2341	}
2342	}
2343	}
2344	}
2345
2346
2347	void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2348	{
2349	ObjectPvsIterator it = viewCell->GetPvs().GetIterator();
2350
2351	while (it.HasMoreEntries())
2352	{
2353	ObjectPvsEntry entry = it.Next();
2354	Intersectable *obj = entry.mObject;
2355
2356	// hack: just output full pvs
2357	if (obj->Type() == Intersectable::BVH_INTERSECTABLE)
2358	{
2359	ObjectContainer objects;
2360	BvhNode node = dynamic_cast<BvhNode >(obj);
2361	node->CollectObjects(objects);
2362
2363	ObjectContainer::const_iterator oit, oit_end = objects.end();
2364	for (oit = objects.begin(); oit != oit_end; ++ oit)
2365	{
2366	stream << (*oit)->GetId() << " ";
2367	}
2368	}
2369	else
2370	{
2371	stream << entry.mObject->GetId() << " ";
2372	}
2373	}
2374	}
2375
2376
2377	void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2378	OUT_STREAM &stream,
2379	const bool exportPvs)
2380	{
2381	if (viewCell->IsLeaf())
2382	{
2383	stream << "<Leaf ";
2384	stream << "id=\"" << viewCell->GetId() << "\" ";
2385	stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2386	stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2387	stream << "pvs=\"";
2388
2389	//-- export pvs, i.e., the ids of the objects in the pvs
2390	if (exportPvs)
2391	{
2392	ExportPvs(viewCell, stream);
2393	}
2394	stream << "\" />" << endl;
2395	}
2396	else
2397	{
2398	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2399
2400	stream << "<Interior ";
2401	stream << "id=\"" << viewCell->GetId() << "\" ";
2402	stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2403	stream << "pvs=\"";
2404
2405	// NOTE: do not export pvss for interior view cells because
2406	// they can be completely reconstructed from the leaf pvss
2407	// on the other hand: we could store a tag with the compression scheme,
2408	// then some scheme were pvs is in the interiors could be used
2409	if (0) ExportPvs(viewCell, stream);
2410
2411	stream << "\" >" << endl;
2412
2413	//-- recursivly export child view cells
2414	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2415
2416	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2417	{
2418	ExportViewCell(*it, stream, exportPvs);
2419	}
2420
2421	stream << "</Interior>" << endl;
2422	}
2423	}
2424
2425
2426	void ViewCellsTree::ResetPvs()
2427	{
2428	stack<ViewCell *> tstack;
2429
2430	tstack.push(mRoot);
2431
2432	while (!tstack.empty())
2433	{
2434	ViewCell *vc = tstack.top();
2435	tstack.pop();
2436
2437	vc->GetPvs().Clear();
2438
2439	if (!vc->IsLeaf())
2440	{
2441	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2442	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2443
2444	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2445	{
2446	tstack.push(*it);
2447	}
2448	}
2449	}
2450	}
2451
2452
2453	void ViewCellsTree::SetViewCellsManager(ViewCellsManager *vcm)
2454	{
2455	mViewCellsManager = vcm;
2456	}
2457
2458
2459	void ViewCellsTree::SetActiveSetToLeaves()
2460	{
2461	// todo
2462	}
2463
2464
2465	/**************************************************************************/
2466	/* MergeCandidate implementation */
2467	/**************************************************************************/
2468
2469
2470	MergeCandidate::MergeCandidate(ViewCell l, ViewCell r):
2471	mRenderCost(0),
2472	mDeviationIncr(0),
2473	mLeftViewCell(l),
2474	mRightViewCell(r),
2475	mInitialLeftViewCell(l),
2476	mInitialRightViewCell(r)
2477	{
2478	//EvalMergeCost();
2479	}
2480
2481
2482	void MergeCandidate::SetRightViewCell(ViewCell *v)
2483	{
2484	mRightViewCell = v;
2485	}
2486
2487
2488	void MergeCandidate::SetLeftViewCell(ViewCell *v)
2489	{
2490	mLeftViewCell = v;
2491	}
2492
2493
2494	ViewCell *MergeCandidate::GetRightViewCell() const
2495	{
2496	return mRightViewCell;
2497	}
2498
2499
2500	ViewCell *MergeCandidate::GetLeftViewCell() const
2501	{
2502	return mLeftViewCell;
2503	}
2504
2505
2506	ViewCell *MergeCandidate::GetInitialRightViewCell() const
2507	{
2508	return mInitialRightViewCell;
2509	}
2510
2511
2512	ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2513	{
2514	return mInitialLeftViewCell;
2515	}
2516
2517
2518	bool MergeCandidate::IsValid() const
2519	{
2520	// if one has a parent, it was already merged
2521	return !(mLeftViewCell->GetParent() \|\| mRightViewCell->GetParent());
2522	}
2523
2524
2525	float MergeCandidate::GetRenderCost() const
2526	{
2527	return mRenderCost;
2528	}
2529
2530
2531	float MergeCandidate::GetDeviationIncr() const
2532	{
2533	return mDeviationIncr;
2534	}
2535
2536
2537	float MergeCandidate::GetMergeCost() const
2538	{
2539	return mRenderCost * sRenderCostWeight +
2540	mDeviationIncr * (1.0f - sRenderCostWeight);
2541	}
2542
2543
2544
2545	/************************************************************************/
2546	/* MergeStatistics implementation */
2547	/************************************************************************/
2548
2549
2550	void MergeStatistics::Print(ostream &app) const
2551	{
2552	app << "===== Merge statistics ===============\n";
2553
2554	app << setprecision(4);
2555
2556	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2557
2558	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2559
2560	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2561
2562	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2563
2564	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2565
2566	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2567
2568	app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2569
2570	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2571
2572	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2573
2574	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2575
2576	app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2577
2578	app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2579
2580	app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2581
2582
2583	app << "===== END OF BspTree statistics ==========\n";
2584	}
2585
2586
2587	}

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

Download in other formats: