Context Navigation

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

Revision 1660, 61.2 KB checked in by mattausch, 18 years ago (diff)
added ratio for rc / storage

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

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

Download in other formats: