Context Navigation

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

Revision 1633, 60.7 KB checked in by mattausch, 18 years ago (diff)
worked on gradient method for vsposp

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 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:
2017	{
2018	//-- store pvs only in leaves
2019	pvsSize = GetEntriesInPvsForLeafStorage(vc);
2020	break;
2021	}
2022	case COMPRESSED:
2023	{
2024	pvsSize = GetEntriesInPvsForCompressedStorage(vc);
2025	break;
2026	}
2027	case PVS_IN_INTERIORS:
2028	default:
2029	// pvs is stored consistently in the tree up to the root
2030	// just return pvs size
2031	pvsSize = vc->GetPvs().GetSize();
2032	break;
2033	}
2034
2035	return pvsSize;
2036	}
2037
2038
2039	float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
2040	{
2041	const float entrySize =
2042	sizeof(PvsData) + sizeof(Intersectable *);
2043
2044	return (float)CountStoredPvsEntries(vc) * entrySize;
2045	}
2046
2047	//#if HAS_TO_BE_REDONE
2048	int ViewCellsTree::CountStoredPvsEntries(ViewCell *root) const
2049	{
2050	int pvsSize = root->GetPvs().GetSize();
2051
2052	// recursivly count leaves
2053	if (!root->IsLeaf())
2054	{
2055	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
2056
2057	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2058
2059	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2060	{
2061	pvsSize += CountStoredPvsEntries(*it);
2062	}
2063	}
2064
2065	return pvsSize;
2066	}
2067	//#endif
2068
2069	int ViewCellsTree::ViewCellsStorage() const
2070	{
2071	return mViewCellsStorage;
2072	}
2073
2074
2075	ViewCell ViewCellsTree::GetActiveViewCell(ViewCellLeaf vc) const
2076	{
2077	return vc->GetActiveViewCell();
2078	}
2079
2080
2081	void ViewCellsTree::PropagatePvs(ViewCell *vc)
2082	{
2083	ViewCell *viewCell = vc;
2084
2085	// propagate pvs up
2086	while (viewCell->GetParent())
2087	{
2088	viewCell->GetParent()->GetPvs().Merge(vc->GetPvs());
2089	viewCell = viewCell->GetParent();
2090	}
2091
2092	if (vc->IsLeaf())
2093	return;
2094
2095	// propagate pvs to the leaves
2096	stack<ViewCell *> tstack;
2097	tstack.push(vc);
2098
2099	while (!tstack.empty())
2100	{
2101	ViewCell *viewCell = tstack.top();
2102	tstack.pop();
2103
2104	if (viewCell != vc)
2105	{
2106	viewCell->GetPvs().Merge(vc->GetPvs());
2107	}
2108
2109	if (!viewCell->IsLeaf())
2110	{
2111	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2112
2113	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2114
2115	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2116	{
2117	tstack.push(*it);
2118	}
2119	}
2120	}
2121	}
2122
2123
2124	void ViewCellsTree::AssignRandomColors()
2125	{
2126	TraversalQueue tqueue;
2127
2128	tqueue.push(mRoot);
2129
2130	mRoot->SetColor(RandomColor(0.3f, 1.0f));
2131
2132	while (!tqueue.empty())
2133	{
2134	ViewCell *vc = tqueue.top();
2135	tqueue.pop();
2136
2137	// save the view cells if it is a leaf or if enough view cells have already been traversed
2138	// because of the priority queue, this will be the optimal set of v
2139	if (!vc->IsLeaf())
2140	{
2141	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2142
2143	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2144
2145	float maxProbability = -1.0f;
2146
2147	ViewCell *maxViewCell = NULL;
2148	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2149	{
2150	ViewCell v = it;
2151
2152	// set random color
2153	v->SetColor(RandomColor(0.3f, 1.0f));
2154
2155	if (v->GetVolume() > maxProbability)
2156	{
2157	maxProbability = v->GetVolume();
2158	maxViewCell = v;
2159	}
2160
2161	if (maxViewCell)
2162	{
2163	maxViewCell->SetColor(vc->GetColor());
2164	}
2165
2166	tqueue.push(v);
2167	}
2168	}
2169	}
2170	}
2171
2172
2173	/** Get costs resulting from each merge step.
2174	*/
2175	void ViewCellsTree::GetCostFunction(vector<float> &costFunction)
2176	{
2177	TraversalQueue tqueue;
2178	tqueue.push(mRoot);
2179
2180	int numViewCells = 1;
2181
2182	const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2183	const int rootPvs = GetPvsSize(mRoot);
2184
2185	float totalRenderCost;
2186
2187	int totalPvs = rootPvs;
2188	totalRenderCost = (float)rootPvs;
2189
2190	costFunction.push_back(totalRenderCost);
2191
2192	//-- go through tree in the order of render cost decrease
2193	//-- which is the same order as the view cells were merged
2194	//-- or the reverse order of subdivision for subdivision-only
2195	//-- view cell hierarchies.
2196
2197	while (!tqueue.empty())
2198	{
2199	ViewCell *vc = tqueue.top();
2200	tqueue.pop();
2201
2202	if (!vc->IsLeaf())
2203	{
2204	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2205
2206	const int parentPvs = GetPvsSize(interior);
2207	const float parentCost = (float)parentPvs * interior->GetVolume();
2208
2209	-- numViewCells;
2210
2211	float childCost = 0;
2212	int childPvs = 0;
2213
2214	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2215
2216	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2217	{
2218	ViewCell vc = it;
2219
2220	const int pvsSize = GetPvsSize(vc);
2221
2222	childCost += (float) pvsSize * vc->GetVolume();
2223	childPvs += pvsSize;
2224
2225	tqueue.push(vc);
2226	++ numViewCells;
2227	}
2228
2229	// update stats for this view cell
2230	const float costDecr = (parentCost - childCost) / vol;
2231	totalRenderCost -= costDecr;
2232	const float expectedCost = totalRenderCost ;/// (float)numViewCells;
2233
2234	costFunction.push_back(expectedCost);
2235	}
2236	}
2237	}
2238
2239
2240	/** Get storage costs resulting from each merge step.
2241	*/
2242	void ViewCellsTree::GetStorageFunction(vector<int> &storageFunction)
2243	{
2244	TraversalQueue tqueue;
2245	tqueue.push(mRoot);
2246
2247	int numViewCells = 1;
2248
2249	const float vol = mViewCellsManager->GetViewSpaceBox().GetVolume();
2250	const int rootEntries = GetPvsEntries(mRoot);
2251
2252	int entriesInPvs = rootEntries;
2253	const int entryStorage = sizeof(PvsData) + sizeof(int); // one entry into the pvs
2254
2255	storageFunction.push_back(rootEntries);
2256
2257	////////////
2258	//-- go through tree in the order of render cost decrease
2259	//-- which is the same order as the view cells were merged
2260	//-- or the reverse order of subdivision for subdivision-only
2261	//-- view cell hierarchies.
2262
2263	while (!tqueue.empty())
2264	{
2265	ViewCell *vc = tqueue.top();
2266	tqueue.pop();
2267
2268	if (!vc->IsLeaf())
2269	{
2270	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2271
2272	const int parentPvs = GetPvsSize(interior);
2273	const int parentPvsEntries = GetPvsEntries(interior);
2274	const float parentCost = (float)parentPvs * interior->GetVolume();
2275
2276	float childCost = 0;
2277	int childPvs = 0;
2278	int childPvsEntries = 0;
2279
2280	-- numViewCells;
2281
2282	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2283
2284	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2285	{
2286	ViewCell vc = it;
2287
2288	//const int pvsSize = GetPvsSize(vc);
2289	const int pvsEntries = GetPvsEntries(vc);
2290
2291	//childPvs += pvsSize;
2292	childPvsEntries += pvsEntries;
2293
2294	tqueue.push(vc);
2295	++ numViewCells;
2296	}
2297
2298	// update stats for this view cell
2299	const float costDecr = (parentCost - childCost) / vol;
2300
2301	//totalPvs += childPvs - parentPvs;
2302	entriesInPvs += childPvsEntries - parentPvsEntries;
2303
2304	const int storageCost = entriesInPvs * entryStorage;
2305	storageFunction.push_back(storageCost);
2306	}
2307	}
2308	}
2309
2310
2311
2312	void ViewCellsTree::UpdateViewCellsStats(ViewCell *vc,
2313	ViewCellsStatistics &vcStat)
2314	{
2315	++ vcStat.viewCells;
2316
2317	const int pvsSize = GetPvsSize(vc);
2318
2319	vcStat.pvsSize += pvsSize;
2320
2321	if (pvsSize == 0)
2322	++ vcStat.emptyPvs;
2323
2324	if (pvsSize > vcStat.maxPvs)
2325	vcStat.maxPvs = pvsSize;
2326
2327	if (pvsSize < vcStat.minPvs)
2328	vcStat.minPvs = pvsSize;
2329
2330	if (!vc->GetValid())
2331	++ vcStat.invalid;
2332	}
2333
2334
2335	bool ViewCellsTree::Export(OUT_STREAM &stream, const bool exportPvs)
2336	{
2337	// export recursivly all view cells from the root
2338	ExportViewCell(mRoot, stream, exportPvs);
2339
2340	return true;
2341	}
2342
2343
2344	void ViewCellsTree::CreateUniqueViewCellsIds()
2345	{
2346	stack<ViewCell *> tstack;
2347
2348	int currentId = 0;
2349
2350	tstack.push(mRoot);
2351
2352	while (!tstack.empty())
2353	{
2354	ViewCell *vc = tstack.top();
2355	tstack.pop();
2356
2357	if (vc->GetId() != -1) // out of bounds
2358	vc->SetId(currentId ++);
2359
2360	if (!vc->IsLeaf())
2361	{
2362	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2363
2364	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2365	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2366	{
2367	tstack.push(*it);
2368	}
2369	}
2370	}
2371	}
2372
2373
2374	void ViewCellsTree::ExportPvs(ViewCell *viewCell, OUT_STREAM &stream)
2375	{
2376	ObjectPvsMap::iterator it, it_end = viewCell->GetPvs().mEntries.end();
2377
2378	for (it = viewCell->GetPvs().mEntries.begin(); it != it_end; ++ it)
2379	{
2380	Intersectable obj = (it).first;
2381	// hack: just output full pvs
2382	if (obj->Type() == Intersectable::BVH_INTERSECTABLE)
2383	{
2384	ObjectContainer objects;
2385	BvhNode node = dynamic_cast<BvhIntersectable >(obj)->GetItem();
2386	node->CollectObjects(objects);
2387
2388	ObjectContainer::const_iterator oit, oit_end = objects.end();
2389	for (oit = objects.begin(); oit != oit_end; ++ oit)
2390	{
2391	stream << (*oit)->GetId() << " ";
2392	}
2393	}
2394	else
2395	{
2396	stream << (*it).first->GetId() << " ";
2397	}
2398	}
2399	}
2400
2401
2402	void ViewCellsTree::ExportViewCell(ViewCell *viewCell,
2403	OUT_STREAM &stream,
2404	const bool exportPvs)
2405	{
2406	if (viewCell->IsLeaf())
2407	{
2408	stream << "<Leaf ";
2409	stream << "id=\"" << viewCell->GetId() << "\" ";
2410	stream << "active=\"" << dynamic_cast<ViewCellLeaf *>(viewCell)->GetActiveViewCell()->GetId() << "\" ";
2411	stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2412	stream << "pvs=\"";
2413
2414	//-- export pvs, i.e., the ids of the objects in the pvs
2415	if (exportPvs)
2416	{
2417	ExportPvs(viewCell, stream);
2418	}
2419	stream << "\" />" << endl;
2420	}
2421	else
2422	{
2423	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(viewCell);
2424
2425	stream << "<Interior ";
2426	stream << "id=\"" << viewCell->GetId() << "\" ";
2427	stream << "mergecost=\"" << viewCell->GetMergeCost() << "\" ";
2428	stream << "pvs=\"";
2429
2430	// NOTE: do not export pvss for interior view cells because
2431	// they can be completely reconstructed from the leaf pvss
2432	// on the other hand: we could store a tag with the compression scheme,
2433	// then some scheme were pvs is in the interiors could be used
2434	if (0) ExportPvs(viewCell, stream);
2435
2436	stream << "\" >" << endl;
2437
2438	//-- recursivly export child view cells
2439	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2440
2441	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2442	{
2443	ExportViewCell(*it, stream, exportPvs);
2444	}
2445
2446	stream << "</Interior>" << endl;
2447	}
2448	}
2449
2450
2451	void ViewCellsTree::ResetPvs()
2452	{
2453	stack<ViewCell *> tstack;
2454
2455	tstack.push(mRoot);
2456
2457	while (!tstack.empty())
2458	{
2459	ViewCell *vc = tstack.top();
2460	tstack.pop();
2461
2462	vc->GetPvs().Clear();
2463
2464	if (!vc->IsLeaf())
2465	{
2466	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
2467	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
2468
2469	for (it = interior->mChildren.begin(); it != it_end; ++ it)
2470	{
2471	tstack.push(*it);
2472	}
2473	}
2474	}
2475	}
2476
2477
2478	void ViewCellsTree::SetViewCellsManager(ViewCellsManager *vcm)
2479	{
2480	mViewCellsManager = vcm;
2481	}
2482
2483
2484	void ViewCellsTree::SetActiveSetToLeaves()
2485	{
2486	// todo
2487	}
2488
2489
2490
2491	/**************************************************************************/
2492	/* MergeCandidate implementation */
2493	/**************************************************************************/
2494
2495
2496	MergeCandidate::MergeCandidate(ViewCell l, ViewCell r):
2497	mRenderCost(0),
2498	mDeviationIncr(0),
2499	mLeftViewCell(l),
2500	mRightViewCell(r),
2501	mInitialLeftViewCell(l),
2502	mInitialRightViewCell(r)
2503	{
2504	//EvalMergeCost();
2505	}
2506
2507
2508	void MergeCandidate::SetRightViewCell(ViewCell *v)
2509	{
2510	mRightViewCell = v;
2511	}
2512
2513
2514	void MergeCandidate::SetLeftViewCell(ViewCell *v)
2515	{
2516	mLeftViewCell = v;
2517	}
2518
2519
2520	ViewCell *MergeCandidate::GetRightViewCell() const
2521	{
2522	return mRightViewCell;
2523	}
2524
2525
2526	ViewCell *MergeCandidate::GetLeftViewCell() const
2527	{
2528	return mLeftViewCell;
2529	}
2530
2531
2532	ViewCell *MergeCandidate::GetInitialRightViewCell() const
2533	{
2534	return mInitialRightViewCell;
2535	}
2536
2537
2538	ViewCell *MergeCandidate::GetInitialLeftViewCell() const
2539	{
2540	return mInitialLeftViewCell;
2541	}
2542
2543
2544	bool MergeCandidate::IsValid() const
2545	{
2546	// if one has a parent, it was already merged
2547	return !(mLeftViewCell->GetParent() \|\| mRightViewCell->GetParent());
2548	}
2549
2550
2551	float MergeCandidate::GetRenderCost() const
2552	{
2553	return mRenderCost;
2554	}
2555
2556
2557	float MergeCandidate::GetDeviationIncr() const
2558	{
2559	return mDeviationIncr;
2560	}
2561
2562
2563	float MergeCandidate::GetMergeCost() const
2564	{
2565	return mRenderCost * sRenderCostWeight +
2566	mDeviationIncr * (1.0f - sRenderCostWeight);
2567	}
2568
2569
2570
2571	/************************************************************************/
2572	/* MergeStatistics implementation */
2573	/************************************************************************/
2574
2575
2576	void MergeStatistics::Print(ostream &app) const
2577	{
2578	app << "===== Merge statistics ===============\n";
2579
2580	app << setprecision(4);
2581
2582	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
2583
2584	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
2585
2586	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
2587
2588	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
2589
2590	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
2591
2592	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
2593
2594	app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
2595
2596	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
2597
2598	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
2599
2600	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
2601
2602	app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
2603
2604	app << "#DEVIATION ( deviation )\n" << deviation << "\n";
2605
2606	app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
2607
2608
2609	app << "===== END OF BspTree statistics ==========\n";
2610	}
2611
2612	}

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

Download in other formats: