Context Navigation

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

Revision 1695, 61.0 KB checked in by mattausch, 18 years ago (diff)

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

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

Download in other formats: