Context Navigation

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

Revision 2560, 64.2 KB checked in by mattausch, 17 years ago (diff)
added functionality for visualization

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

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

Download in other formats: