Context Navigation

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

Revision 1614, 60.7 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 = 1;//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 int pvsSizeDecr,
1504	const float volume)
1505	{
1506	stats << "#Pass\n" << pass << endl
1507	<< "#ViewCells\n" << viewCells << endl
1508	<< "#RenderCostDecrease\n" << renderCostDecrease << endl // TODO
1509	<< "#TotalRenderCost\n" << totalRenderCost << endl
1510	<< "#CurrentPvs\n" << currentPvs << endl
1511	<< "#ExpectedCost\n" << expectedCost << endl
1512	<< "#AvgRenderCost\n" << avgRenderCost << endl
1513	<< "#Deviation\n" << deviation << endl
1514	<< "#TotalPvs\n" << totalPvs << endl
1515	<< "#TotalEntriesInPvs\n" << entriesInPvs << endl
1516	<< "#PvsSizeDecrease\n" << pvsSizeDecr << endl // TODO
1517	<< "#Volume\n" << volume << endl
1518	<< endl;
1519	}
1520
1521
1522	void ViewCellsTree::ExportStats(const string &mergeStats)
1523	{
1524	TraversalQueue tqueue;
1525
1526	tqueue.push(mRoot);
1527	int numViewCells = 1;
1528
1529	const AxisAlignedBox3 box = mViewCellsManager->GetViewSpaceBox();
1530	const float vol = box.GetVolume();
1531
1532	const int rootPvs = GetPvsSize(mRoot);
1533	const int rootEntries = GetPvsEntries(mRoot);
1534
1535	Debug << "****** Export stats ********" << endl;
1536
1537	float totalRenderCost, avgRenderCost, expectedCost;
1538
1539	float deviation = 0;
1540	int totalPvs = rootPvs;
1541	int entriesInPvs = rootEntries;
1542
1543	totalRenderCost = avgRenderCost = expectedCost = (float)rootPvs;
1544
1545	ofstream stats;
1546	stats.open(mergeStats.c_str());
1547
1548	/////////////
1549	//-- first view cell
1550
1551	UpdateStats(stats,
1552	0, numViewCells, 0, totalRenderCost,
1553	rootPvs, expectedCost, avgRenderCost, deviation,
1554	totalPvs, entriesInPvs, 0, mRoot->GetVolume());
1555
1556
1557	//-- go through tree in the order of render cost decrease
1558	//-- which is the same order as the view cells were merged
1559	//-- or the reverse order of subdivision for subdivision-only
1560	//-- view cell hierarchies.
1561
1562	while (!tqueue.empty())
1563	{
1564	ViewCell *vc = tqueue.top();
1565	tqueue.pop();
1566
1567	if (!vc->IsLeaf())
1568	{
1569	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1570
1571	const int parentPvs = GetPvsSize(interior);
1572	const int parentPvsEntries = GetPvsEntries(interior);
1573	const float parentCost = (float)parentPvs * interior->GetVolume();
1574
1575	float childCost = 0;
1576	int childPvs = 0;
1577	int childPvsEntries = 0;
1578
1579	-- numViewCells;
1580
1581	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1582
1583	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1584	{
1585	ViewCell vc = it;
1586
1587	const int pvsSize = GetPvsSize(vc);
1588	const int pvsEntries = GetPvsEntries(vc);
1589
1590	childCost += (float) pvsSize * vc->GetVolume();
1591	childPvs += pvsSize;
1592	childPvsEntries += pvsEntries;
1593
1594	tqueue.push(vc);
1595	++ numViewCells;
1596	}
1597
1598	// update stats for this view cell
1599	const float costDecr = (parentCost - childCost) / vol;
1600
1601	totalRenderCost -= costDecr;
1602	totalPvs += childPvs - parentPvs;
1603	entriesInPvs += childPvsEntries - parentPvsEntries;
1604
1605	expectedCost = totalRenderCost / (float)numViewCells;
1606	avgRenderCost = (float)totalPvs / (float)numViewCells;
1607
1608	UpdateStats(stats,
1609	0, numViewCells, costDecr, totalRenderCost,
1610	parentPvs, expectedCost, avgRenderCost, deviation,
1611	totalPvs, entriesInPvs, childPvs - parentPvs,
1612	vc->GetVolume());
1613
1614	}
1615	}
1616
1617	stats.close();
1618	}
1619
1620
1621	void ViewCellsTree::SetRoot(ViewCell *root)
1622	{
1623	mRoot = root;
1624	}
1625
1626
1627	void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1628	const int numViewCells)
1629	{
1630	TraversalQueue tqueue;
1631	tqueue.push(mRoot);
1632
1633	while (!tqueue.empty())
1634	{
1635	ViewCell *vc = tqueue.top();
1636	tqueue.pop();
1637
1638	// save the view cells if it is a leaf or if enough view cells have already been traversed
1639	// because of the priority queue, this will be the optimal set of v
1640	if (vc->IsLeaf() \|\| ((viewCells.size() + tqueue.size() + 1) >= numViewCells))
1641	{
1642	viewCells.push_back(vc);
1643	}
1644	else
1645	{
1646	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1647
1648	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1649
1650	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1651	{
1652	tqueue.push(*it);
1653	}
1654	}
1655	}
1656	}
1657
1658
1659	void ViewCellsTree::PullUpVisibility(ViewCellInterior *interior)
1660	{
1661	Intersectable::NewMail((int)interior->mChildren.size());
1662
1663	ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1664
1665	ObjectPvsMap::const_iterator oit;
1666
1667	// mail all objects in the leaf sets
1668	// we are interested in the objects which are present in all leaves
1669	// => count how often an object is part of a child set
1670	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1671	{
1672	ViewCell vc = cit;
1673
1674	ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1675
1676	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1677	{
1678	Intersectable obj = (oit).first;
1679	if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1680	obj->Mail();
1681
1682	int incm = obj->IncMail();
1683	}
1684	}
1685
1686	interior->GetPvs().Clear();
1687
1688
1689	// only the objects which are present in all leaf pvs
1690	// should remain in the parent pvs
1691	// these are the objects which have been mailed in all children
1692	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1693	{
1694	ViewCell vc = cit;
1695
1696	ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1697
1698	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1699	{
1700	if ((*oit).first->Mailed((int)interior->mChildren.size()))
1701	{
1702	interior->GetPvs().AddSample((oit).first, (oit).second.mSumPdf);
1703	}
1704	}
1705	}
1706
1707
1708	// delete all the objects from the leaf sets which were moved to parent pvs
1709	ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1710
1711	for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1712	{
1713	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1714	{
1715	if (!(cit)->GetPvs().RemoveSample((oit).first, Limits::Infinity))
1716	{
1717	Debug << "should not come here!" << endl;
1718	}
1719	}
1720	}
1721	}
1722
1723
1724	// TODO matt: implement this function for different storing methods
1725	void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1726	{
1727	// pvs is stored in each cell => just return pvs
1728	if (mViewCellsStorage == PVS_IN_INTERIORS)
1729	{
1730	pvs = vc->GetPvs();
1731	return;
1732	}
1733
1734
1735	//-- pvs is not stored with the interiors => reconstruct
1736	Intersectable::NewMail();
1737
1738	int pvsSize = 0;
1739	ViewCell *root = vc;
1740
1741	// add pvs from this view cell to root
1742	while (root->GetParent())
1743	{
1744	root = root->GetParent();
1745	pvs.AddPvs(root->GetPvs());
1746	}
1747
1748	// add pvs from leaves
1749	stack<ViewCell *> tstack;
1750	tstack.push(vc);
1751
1752	while (!tstack.empty())
1753	{
1754	vc = tstack.top();
1755	tstack.pop();
1756
1757	// add newly found pvs to merged pvs
1758	pvs.AddPvs(vc->GetPvs());
1759
1760	if (!vc->IsLeaf()) // interior cells: go down to leaf level
1761	{
1762	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1763
1764	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1765
1766	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1767	{
1768	tstack.push(*it);
1769	}
1770	}
1771	}
1772	}
1773
1774
1775	int ViewCellsTree::GetPvsSizeForLeafStorage(ViewCell *vc) const
1776	{
1777	// pvs is always stored directly in leaves
1778	if (vc->IsLeaf())
1779	{
1780	return vc->GetPvs().CountObjectsInPvs();
1781	}
1782
1783	// interior nodes: pvs is either stored as a scalar or
1784	// has to be reconstructed from the leaves
1785	// the stored pvs size is the valid pvs size => just return scalar
1786	if (vc->mPvsSizeValid)
1787	{
1788	return vc->mPvsSize;
1789	}
1790
1791	// if no valid pvs size stored as a scalar =>
1792	// compute current pvs size of interior from it's leaf nodes
1793	ViewCellContainer leaves;
1794	CollectLeaves(vc, leaves);
1795
1796	ViewCellContainer::const_iterator it, it_end = leaves.end();
1797
1798	Intersectable::NewMail();
1799	ObjectPvs newPvs;
1800
1801	// sum up uniquely found intersectables
1802	for (it = leaves.begin(); it != it_end; ++ it)
1803	{
1804	ObjectPvsMap::iterator oit, oit_end = (*it)->GetPvs().mEntries.end();
1805
1806	for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1807	{
1808	Intersectable intersect = (oit).first;
1809
1810	if (!intersect->Mailed())
1811	{
1812	intersect->Mail();
1813	newPvs.AddSample(intersect, (*oit).second.mSumPdf);
1814	}
1815	}
1816	}
1817
1818	return newPvs.CountObjectsInPvs();
1819	}
1820
1821
1822	int ViewCellsTree::GetEntriesInPvsForLeafStorage(ViewCell *vc) const
1823	{
1824	// pvs is always stored directly in leaves
1825	if (vc->IsLeaf())
1826	{
1827	return vc->GetPvs().GetSize();
1828	}
1829
1830	// interior node
1831
1832	// interior nodes: pvs is either stored as a scalar or
1833	// has to be reconstructed from the leaves
1834
1835	// the stored pvs size is the valid pvs size => just return scalar
1836	if (vc->mPvsSizeValid)
1837	{
1838	return vc->mEntriesInPvs;
1839	}
1840
1841	int pvsSize = 0;
1842
1843	// if no valid pvs size stored as a scalar =>
1844	// compute current pvs size of interior from it's leaf nodes
1845	ViewCellContainer leaves;
1846	CollectLeaves(vc, leaves);
1847
1848	ViewCellContainer::const_iterator it, it_end = leaves.end();
1849	Intersectable::NewMail();
1850
1851	// sum different intersectables
1852	for (it = leaves.begin(); it != it_end; ++ it)
1853	{
1854	ObjectPvsMap::iterator oit, oit_end = (*it)->GetPvs().mEntries.end();
1855
1856	for (oit = (*it)->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1857	{
1858	Intersectable intersect = (oit).first;
1859
1860	if (!intersect->Mailed())
1861	{
1862	intersect->Mail();
1863	++ pvsSize;
1864	}
1865	}
1866	}
1867
1868	return pvsSize;
1869	}
1870
1871
1872	int ViewCellsTree::GetPvsSizeForCompressedStorage(ViewCell *vc) const
1873	{
1874	int pvsSize = 0;
1875
1876	/////////////
1877	//-- compressed pvs
1878
1879	// the stored pvs size is the valid pvs size => just return scalar
1880	if (vc->mPvsSizeValid)
1881	{
1882	pvsSize = vc->mPvsSize;
1883	}
1884
1885	// if no pvs size stored, compute new one
1886	ViewCell *root = vc;
1887
1888	// also add pvs from this view cell to root
1889	while (root->GetParent())
1890	{
1891	root = root->GetParent();
1892
1893	// matt: bug! must evaluate kd pvss also
1894	pvsSize += CountPvsContribution(root);
1895	}
1896
1897	stack<ViewCell *> tstack;
1898	tstack.push(vc);
1899
1900	while (!tstack.empty())
1901	{
1902	vc = tstack.top();
1903	tstack.pop();
1904	// matt: bug! must evaluate kd pvss also
1905	pvsSize += CountPvsContribution(vc);
1906
1907	if (!vc->IsLeaf())
1908	{
1909	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1910
1911	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1912
1913	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1914	{
1915	tstack.push(*it);
1916	}
1917	}
1918	}
1919
1920	return pvsSize;
1921	}
1922
1923
1924	int ViewCellsTree::GetEntriesInPvsForCompressedStorage(ViewCell *vc) const
1925	{
1926	int pvsSize = 0;
1927
1928	/////////////////
1929	//-- compressed pvs
1930
1931	// the stored pvs size is the valid pvs size => just return scalar
1932	if (vc->mPvsSizeValid)
1933	{
1934	pvsSize = vc->mEntriesInPvs;
1935	}
1936
1937	// if no pvs size stored, compute new one
1938	ViewCell *root = vc;
1939
1940	// also add pvs from this view cell to root
1941	while (root->GetParent())
1942	{
1943	root = root->GetParent();
1944	// count the pvs entries different from the already found ones
1945	pvsSize += CountPvsContribution(root);
1946	}
1947
1948	stack<ViewCell *> tstack;
1949	tstack.push(vc);
1950
1951	while (!tstack.empty())
1952	{
1953	vc = tstack.top();
1954	tstack.pop();
1955
1956	// count the pvs entries different from the already found ones
1957	pvsSize += CountPvsContribution(vc);
1958
1959	if (!vc->IsLeaf())
1960	{
1961	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1962
1963	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1964
1965	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1966	{
1967	tstack.push(*it);
1968	}
1969	}
1970	}
1971
1972	return pvsSize;
1973	}
1974
1975
1976	int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1977	{
1978	int pvsSize = 0;
1979	Intersectable::NewMail();
1980
1981	////////////////////////////////////////////////
1982	// for interiors, pvs can be stored using different methods
1983	//
1984
1985	switch (mViewCellsStorage)
1986	{
1987	case PVS_IN_LEAVES: //-- store pvs only in leaves
1988	pvsSize = GetPvsSizeForLeafStorage(vc);
1989	break;
1990	case COMPRESSED:
1991	pvsSize = GetPvsSizeForCompressedStorage(vc);
1992	break;
1993	case PVS_IN_INTERIORS:
1994	default:
1995	// pvs is stored consistently in the tree up to the root
1996	// just return pvs size
1997	pvsSize = vc->GetPvs().CountObjectsInPvs();
1998	break;
1999	}
2000
2001	return pvsSize;
2002	}
2003
2004
2005	int ViewCellsTree::GetPvsEntries(ViewCell *vc) const
2006	{
2007	int pvsSize = 0;
2008
2009	Intersectable::NewMail();
2010
2011	////////////////////////////////////////////////
2012	// for interiors, pvs can be stored using different methods
2013
2014	switch (mViewCellsStorage)
2015	{
2016	case PVS_IN_LEAVES: //-- store pvs only in leaves
2017	{
2018	pvsSize = GetEntriesInPvsForLeafStorage(vc);
2019	break;
2020	}
2021	case COMPRESSED:
2022	{
2023	pvsSize = GetEntriesInPvsForCompressedStorage(vc);
2024	break;
2025	}
2026	case PVS_IN_INTERIORS:
2027	default:
2028	// pvs is stored consistently in the tree up to the root
2029	// just return pvs size
2030	pvsSize = vc->GetPvs().GetSize();
2031	break;
2032	}
2033
2034	return pvsSize;
2035	}
2036
2037
2038	float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2039	{
2040	const float entrySize =
2041	sizeof(PvsData) + sizeof(Intersectable *);
2042
2043	return (float)CountStoredPvsEntries(vc) * entrySize;
2044	}
2045
2046	//#if HAS_TO_BE_REDONE
2047	int ViewCellsTree::CountStoredPvsEntries(ViewCell *root) const
2048	{
2049	int pvsSize = root->GetPvs().GetSize();
2050
2051	// recursivly count leaves
2052	if (!root->IsLeaf())
2053	{
2054	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
2055
2056	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2057
2058	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2059	{
2060	pvsSize += CountStoredPvsEntries(*it);
2061	}
2062	}
2063
2064	return pvsSize;
2065	}
2066	//#endif
2067
2068	int ViewCellsTree::ViewCellsStorage() const
2069	{
2070	return mViewCellsStorage;
2071	}
2072
2073
2074	ViewCell ViewCellsTree::GetActiveViewCell(ViewCellLeaf vc) const
2075	{
2076	return vc->GetActiveViewCell();
2077	}
2078
2079
2080	void ViewCellsTree::PropagatePvs(ViewCell *vc)
2081	{
2082	ViewCell *viewCell = vc;
2083
2084	// propagate pvs up
2085	while (viewCell->GetParent())
2086	{
2087	viewCell->GetParent()->GetPvs().Merge(vc->GetPvs());
2088	viewCell = viewCell->GetParent();
2089	}
2090
2091	if (vc->IsLeaf())
2092	return;
2093
2094	// propagate pvs to the leaves
2095	stack<ViewCell *> tstack;
2096	tstack.push(vc);
2097
2098	while (!tstack.empty())
2099	{
2100	ViewCell *viewCell = tstack.top();
2101	tstack.pop();
2102
2103	if (viewCell != vc)
2104	{
2105	viewCell->GetPvs().Merge(vc->GetPvs());
2106	}
2107
2108	if (!viewCell->IsLeaf())
2109	{
2110	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2111
2112	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2113
2114	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2115	{
2116	tstack.push(*it);
2117	}
2118	}
2119	}
2120	}
2121
2122
2123	void ViewCellsTree::AssignRandomColors()
2124	{
2125	TraversalQueue tqueue;
2126
2127	tqueue.push(mRoot);
2128
2129	mRoot->SetColor(RandomColor(0.3f, 1.0f));
2130
2131	while (!tqueue.empty())
2132	{
2133	ViewCell *vc = tqueue.top();
2134	tqueue.pop();
2135
2136	// save the view cells if it is a leaf or if enough view cells have already been traversed
2137	// because of the priority queue, this will be the optimal set of v
2138	if (!vc->IsLeaf())
2139	{
2140	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2141
2142	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2143
2144	float maxProbability = -1.0f;
2145
2146	ViewCell *maxViewCell = NULL;
2147	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2148	{
2149	ViewCell v = it;
2150
2151	// set random color
2152	v->SetColor(RandomColor(0.3f, 1.0f));
2153
2154	if (v->GetVolume() > maxProbability)
2155	{
2156	maxProbability = v->GetVolume();
2157	maxViewCell = v;
2158	}
2159
2160	if (maxViewCell)
2161	{
2162	maxViewCell->SetColor(vc->GetColor());
2163	}
2164
2165	tqueue.push(v);
2166	}
2167	}
2168	}
2169	}
2170
2171
2172	/** Get costs resulting from each merge step.
2173	*/
2174	void ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2175	{
2176	TraversalQueue tqueue;
2177	tqueue.push(mRoot);
2178
2179	int numViewCells = 1;
2180
2181	const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2182	const int rootPvs = GetPvsSize(mRoot);
2183
2184	float totalRenderCost;
2185
2186	int totalPvs = rootPvs;
2187	totalRenderCost = (float)rootPvs;
2188
2189	costFunction.push_back(totalRenderCost);
2190
2191	//-- go through tree in the order of render cost decrease
2192	//-- which is the same order as the view cells were merged
2193	//-- or the reverse order of subdivision for subdivision-only
2194	//-- view cell hierarchies.
2195
2196	while (!tqueue.empty())
2197	{
2198	ViewCell *vc = tqueue.top();
2199	tqueue.pop();
2200
2201	if (!vc->IsLeaf())
2202	{
2203	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2204
2205	const int parentPvs = GetPvsSize(interior);
2206	const float parentCost = (float)parentPvs * interior->GetVolume();
2207
2208	-- numViewCells;
2209
2210	float childCost = 0;
2211	int childPvs = 0;
2212
2213	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2214
2215	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2216	{
2217	ViewCell vc = it;
2218
2219	const int pvsSize = GetPvsSize(vc);
2220
2221	childCost += (float) pvsSize * vc->GetVolume();
2222	childPvs += pvsSize;
2223
2224	tqueue.push(vc);
2225	++ numViewCells;
2226	}
2227
2228	// update stats for this view cell
2229	const float costDecr = (parentCost - childCost) / vol;
2230	totalRenderCost -= costDecr;
2231	const float expectedCost = totalRenderCost ;/// (float)numViewCells;
2232
2233	costFunction.push_back(expectedCost);
2234	}
2235	}
2236	}
2237
2238
2239	/** Get storage costs resulting from each merge step.
2240	*/
2241	void ViewCellsTree::GetStorageFunction(vector<int> &storageFunction)
2242	{
2243	TraversalQueue tqueue;
2244	tqueue.push(mRoot);
2245
2246	int numViewCells = 1;
2247
2248	const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2249	const int rootEntries = GetPvsEntries(mRoot);
2250
2251	int entriesInPvs = rootEntries;
2252	const int entryStorage = sizeof(PvsData) + sizeof(int); // one entry into the pvs
2253
2254	storageFunction.push_back(rootEntries);
2255
2256	////////////
2257	//-- go through tree in the order of render cost decrease
2258	//-- which is the same order as the view cells were merged
2259	//-- or the reverse order of subdivision for subdivision-only
2260	//-- view cell hierarchies.
2261
2262	while (!tqueue.empty())
2263	{
2264	ViewCell *vc = tqueue.top();
2265	tqueue.pop();
2266
2267	if (!vc->IsLeaf())
2268	{
2269	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2270
2271	const int parentPvs = GetPvsSize(interior);
2272	const int parentPvsEntries = GetPvsEntries(interior);
2273	const float parentCost = (float)parentPvs * interior->GetVolume();
2274
2275	float childCost = 0;
2276	int childPvs = 0;
2277	int childPvsEntries = 0;
2278
2279	-- numViewCells;
2280
2281	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2282
2283	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2284	{
2285	ViewCell vc = it;
2286
2287	//const int pvsSize = GetPvsSize(vc);
2288	const int pvsEntries = GetPvsEntries(vc);
2289
2290	//childPvs += pvsSize;
2291	childPvsEntries += pvsEntries;
2292
2293	tqueue.push(vc);
2294	++ numViewCells;
2295	}
2296
2297	// update stats for this view cell
2298	const float costDecr = (parentCost - childCost) / vol;
2299
2300	//totalPvs += childPvs - parentPvs;
2301	entriesInPvs += childPvsEntries - parentPvsEntries;
2302
2303	const int storageCost = entriesInPvs * entryStorage;
2304	storageFunction.push_back(storageCost);
2305	}
2306	}
2307	}
2308
2309
2310
2311	void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2312	ViewCellsStatistics &vcStat)
2313	{
2314	++ vcStat.viewCells;
2315
2316	const int pvsSize = GetPvsSize(vc);
2317
2318	vcStat.pvsSize += pvsSize;
2319
2320	if (pvsSize == 0)
2321	++ vcStat.emptyPvs;
2322
2323	if (pvsSize > vcStat.maxPvs)
2324	vcStat.maxPvs = pvsSize;
2325
2326	if (pvsSize < vcStat.minPvs)
2327	vcStat.minPvs = pvsSize;
2328
2329	if (!vc->GetValid())
2330	++ vcStat.invalid;
2331	}
2332
2333
2334	bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2335	{
2336	// export recursivly all view cells from the root
2337	ExportViewCell(mRoot, stream, exportPvs);
2338
2339	return true;
2340	}
2341
2342
2343	void ViewCellsTree::CreateUniqueViewCellsIds()
2344	{
2345	stack<ViewCell *> tstack;
2346
2347	int currentId = 0;
2348
2349	tstack.push(mRoot);
2350
2351	while (!tstack.empty())
2352	{
2353	ViewCell *vc = tstack.top();
2354	tstack.pop();
2355
2356	if (vc->GetId() != -1) // out of bounds
2357	vc->SetId(currentId ++);
2358
2359	if (!vc->IsLeaf())
2360	{
2361	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2362
2363	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2364	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2365	{
2366	tstack.push(*it);
2367	}
2368	}
2369	}
2370	}
2371
2372
2373	void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2374	{
2375	ObjectPvsMap::iterator it, it_end = viewCell->GetPvs().mEntries.end();
2376
2377	for (it = viewCell->GetPvs().mEntries.begin(); it != it_end; ++ it)
2378	{
2379	Intersectable obj = (it).first;
2380	// hack: just output full pvs
2381	if (obj->Type() == Intersectable::BVH_INTERSECTABLE)
2382	{
2383	ObjectContainer objects;
2384	BvhNode node = dynamic_cast<BvhIntersectable >(obj)->GetItem();
2385	node->CollectObjects(objects);
2386
2387	ObjectContainer::const_iterator oit, oit_end = objects.end();
2388	for (oit = objects.begin(); oit != oit_end; ++ oit)
2389	{
2390	stream << (*oit)->GetId() << " ";
2391	}
2392	}
2393	else
2394	{
2395	stream << (*it).first->GetId() << " ";
2396	}
2397	}
2398	}
2399
2400
2401	void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2402	OUT_STREAM &stream,
2403	const bool exportPvs)
2404	{
2405	if (viewCell->IsLeaf())
2406	{
2407	stream << "<Leaf ";
2408	stream << "id=\"" << viewCell->GetId() << "\" ";
2409	stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2410	stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2411	stream << "pvs=\"";
2412
2413	//-- export pvs, i.e., the ids of the objects in the pvs
2414	if (exportPvs)
2415	{
2416	ExportPvs(viewCell, stream);
2417	}
2418	stream << "\" />" << endl;
2419	}
2420	else
2421	{
2422	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2423
2424	stream << "<Interior ";
2425	stream << "id=\"" << viewCell->GetId() << "\" ";
2426	stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2427	stream << "pvs=\"";
2428
2429	// NOTE: do not export pvss for interior view cells because
2430	// they can be completely reconstructed from the leaf pvss
2431	// on the other hand: we could store a tag with the compression scheme,
2432	// then some scheme were pvs is in the interiors could be used
2433	if (0) ExportPvs(viewCell, stream);
2434
2435	stream << "\" >" << endl;
2436
2437	//-- recursivly export child view cells
2438	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2439
2440	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2441	{
2442	ExportViewCell(*it, stream, exportPvs);
2443	}
2444
2445	stream << "</Interior>" << endl;
2446	}
2447	}
2448
2449
2450	void ViewCellsTree::ResetPvs()
2451	{
2452	stack<ViewCell *> tstack;
2453
2454	tstack.push(mRoot);
2455
2456	while (!tstack.empty())
2457	{
2458	ViewCell *vc = tstack.top();
2459	tstack.pop();
2460
2461	vc->GetPvs().Clear();
2462
2463	if (!vc->IsLeaf())
2464	{
2465	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2466	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2467
2468	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2469	{
2470	tstack.push(*it);
2471	}
2472	}
2473	}
2474	}
2475
2476
2477	void ViewCellsTree::SetViewCellsManager(ViewCellsManager *vcm)
2478	{
2479	mViewCellsManager = vcm;
2480	}
2481
2482
2483	void ViewCellsTree::SetActiveSetToLeaves()
2484	{
2485	// todo
2486	}
2487
2488
2489
2490	/**************************************************************************/
2491	/* MergeCandidate implementation */
2492	/**************************************************************************/
2493
2494
2495	MergeCandidate::MergeCandidate(ViewCell l, ViewCell r):
2496	mRenderCost(0),
2497	mDeviationIncr(0),
2498	mLeftViewCell(l),
2499	mRightViewCell(r),
2500	mInitialLeftViewCell(l),
2501	mInitialRightViewCell(r)
2502	{
2503	//EvalMergeCost();
2504	}
2505
2506
2507	void MergeCandidate::SetRightViewCell(ViewCell *v)
2508	{
2509	mRightViewCell = v;
2510	}
2511
2512
2513	void MergeCandidate::SetLeftViewCell(ViewCell *v)
2514	{
2515	mLeftViewCell = v;
2516	}
2517
2518
2519	ViewCell *MergeCandidate::GetRightViewCell() const
2520	{
2521	return mRightViewCell;
2522	}
2523
2524
2525	ViewCell *MergeCandidate::GetLeftViewCell() const
2526	{
2527	return mLeftViewCell;
2528	}
2529
2530
2531	ViewCell *MergeCandidate::GetInitialRightViewCell() const
2532	{
2533	return mInitialRightViewCell;
2534	}
2535
2536
2537	ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2538	{
2539	return mInitialLeftViewCell;
2540	}
2541
2542
2543	bool MergeCandidate::IsValid() const
2544	{
2545	// if one has a parent, it was already merged
2546	return !(mLeftViewCell->GetParent() \|\| mRightViewCell->GetParent());
2547	}
2548
2549
2550	float MergeCandidate::GetRenderCost() const
2551	{
2552	return mRenderCost;
2553	}
2554
2555
2556	float MergeCandidate::GetDeviationIncr() const
2557	{
2558	return mDeviationIncr;
2559	}
2560
2561
2562	float MergeCandidate::GetMergeCost() const
2563	{
2564	return mRenderCost * sRenderCostWeight +
2565	mDeviationIncr * (1.0f - sRenderCostWeight);
2566	}
2567
2568
2569
2570	/************************************************************************/
2571	/* MergeStatistics implementation */
2572	/************************************************************************/
2573
2574
2575	void MergeStatistics::Print(ostream &app) const
2576	{
2577	app << "===== Merge statistics ===============\n";
2578
2579	app << setprecision(4);
2580
2581	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2582
2583	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2584
2585	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2586
2587	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2588
2589	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2590
2591	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2592
2593	app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2594
2595	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2596
2597	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2598
2599	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2600
2601	app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2602
2603	app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2604
2605	app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2606
2607
2608	app << "===== END OF BspTree statistics ==========\n";
2609	}
2610
2611	}

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

Download in other formats: