Context Navigation

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

Revision 2542, 64.0 KB checked in by mattausch, 17 years ago (diff)

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

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

Download in other formats: