Context Navigation

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

Revision 2588, 61.7 KB checked in by bittner, 17 years ago (diff)
sceneBox bugfix

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

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

Download in other formats: