Context Navigation

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

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

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

Download in other formats: