Context Navigation

ViewCell.cpp @ 2643

Revision 2643, 61.6 KB checked in by mattausch, 17 years ago (diff)
compiling under release internal

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

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

Context Navigation

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

Download in other formats: