Context Navigation

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

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

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

Download in other formats: