Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp @ 590

Revision 590, 39.5 KB checked in by mattausch, 18 years ago (diff)
implemented some code for merge history loading

Line
1	#include "ViewCell.h"
2	#include "Mesh.h"
3	#include "Intersectable.h"
4	#include "MeshKdTree.h"
5	#include "Triangle3.h"
6	#include "common.h"
7	#include "Environment.h"
8	#include "ViewCellsManager.h"
9	#include "Exporter.h"
10
11	#include <time.h>
12	#include <iomanip>
13	#include <stack>
14
15
16
17	template <typename T> class myless
18	{
19	public:
20
21	//bool operator() (HierarchyNode v1, HierarchyNode v2) const
22	bool operator() (T v1, T v2) const
23	{
24	return (v1->GetTimeStamp() < v2->GetTimeStamp());
25	}
26	};
27
28
29	typedef priority_queue<ViewCell , vector<ViewCell >, myless<vector<ViewCell *>::value_type> > TraversalQueue;
30
31	int ViewCell::sMailId = 21843194198;
32	int ViewCell::sReservedMailboxes = 1;
33
34	//int upperPvsLimit = 120;
35	//int lowerPvsLimit = 5;
36
37	float MergeCandidate::sRenderCostWeight = 0;
38
39
40	// pvs penalty can be different from pvs size
41	inline float EvalPvsPenalty(const int pvs,
42	const int lower,
43	const int upper)
44	{
45	// clamp to minmax values
46	if (pvs < lower)
47	return (float)lower;
48	if (pvs > upper)
49	return (float)upper;
50
51	return (float)pvs;
52	}
53
54
55
56
57	inline int CountDiffPvs(ViewCell *vc)
58	{
59	int count = 0;
60
61	ObjectPvsMap::const_iterator it, it_end = vc->GetPvs().mEntries.end();
62	for (it = vc->GetPvs().mEntries.begin(); it != it_end; ++ it)
63	{
64	if (!(*it).first->Mailed())
65	{
66	(*it).first->Mail();
67	++ count;
68	}
69	}
70
71	return count;
72	}
73
74
75	int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
76	{
77	int pvs = pvs1.GetSize();
78
79	// compute new pvs size
80	ObjectPvsMap::const_iterator it, it_end = pvs1.mEntries.end();
81
82	Intersectable::NewMail();
83
84	for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
85	{
86	(*it).first->Mail();
87	}
88
89	it_end = pvs2.mEntries.end();
90
91	for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
92	{
93	Intersectable obj = (it).first;
94	if (!obj->Mailed())
95	++ pvs;
96	}
97
98	return pvs;
99	}
100
101
102	ViewCell::ViewCell():
103	MeshInstance(NULL),
104	mPiercingRays(0),
105	mArea(-1),
106	mVolume(-1),
107	mValid(true),
108	mParent(NULL),
109	mTimeStamp(0),
110	mIsActive(false)
111	{
112	}
113
114	ViewCell::ViewCell(Mesh *mesh):
115	MeshInstance(mesh),
116	mPiercingRays(0),
117	mArea(-1),
118	mVolume(-1),
119	mValid(true),
120	mParent(NULL),
121	mTimeStamp(0),
122	mIsActive(false)
123	{
124	}
125
126
127	const ObjectPvs &ViewCell::GetPvs() const
128	{
129	return mPvs;
130	}
131
132	ObjectPvs &ViewCell::GetPvs()
133	{
134	return mPvs;
135	}
136
137
138	int ViewCell::Type() const
139	{
140	return VIEW_CELL;
141	}
142
143
144	float ViewCell::GetVolume() const
145	{
146	return mVolume;
147	}
148
149
150	void ViewCell::SetVolume(float volume)
151	{
152	mVolume = volume;
153	}
154
155
156	void ViewCell::SetMesh(Mesh *mesh)
157	{
158	mMesh = mesh;
159	}
160
161
162	void ViewCell::UpdateViewCellsStats(ViewCellsStatistics &vcStat)
163	{
164	++ vcStat.viewCells;
165
166	const int pvsSize = mPvs.GetSize();
167
168	vcStat.pvs += pvsSize;
169
170	if (pvsSize == 0)
171	++ vcStat.emptyPvs;
172
173	if (pvsSize > vcStat.maxPvs)
174	vcStat.maxPvs = pvsSize;
175
176	if (pvsSize < vcStat.minPvs)
177	vcStat.minPvs = pvsSize;
178
179	if (!mValid)
180	++ vcStat.invalid;
181	}
182
183
184	float ViewCell::GetArea() const
185	{
186	return mArea;
187	}
188
189
190	void ViewCell::SetArea(float area)
191	{
192	mArea = area;
193	}
194
195
196	void ViewCell::SetValid(const bool valid)
197	{
198	mValid = valid;
199	}
200
201
202	bool ViewCell::GetValid() const
203	{
204	return mValid;
205	}
206
207
208	/*bool ViewCell::IsLeaf() const
209	{
210	return true;
211	}*/
212
213
214	void ViewCell::SetParent(ViewCellInterior *parent)
215	{
216	mParent = parent;
217	}
218
219
220	bool ViewCell::IsRoot() const
221	{
222	return !mParent;
223	}
224
225
226	ViewCellInterior *ViewCell::GetParent() const
227	{
228	return mParent;
229	}
230
231
232	void ViewCell::SetTimeStamp(const int timeStamp)
233	{
234	mTimeStamp = timeStamp;
235	}
236
237
238	int ViewCell::GetTimeStamp() const
239	{
240	return mTimeStamp;
241	}
242
243
244
245	/************************************************************************/
246	/* class ViewCellInterior implementation */
247	/************************************************************************/
248
249
250	ViewCellInterior::ViewCellInterior()
251	{
252	}
253
254
255	ViewCellInterior::~ViewCellInterior()
256	{
257	ViewCellContainer::const_iterator it, it_end = mChildren.end();
258
259	for (it = mChildren.begin(); it != it_end; ++ it)
260	delete (*it);
261	}
262
263
264	ViewCellInterior::ViewCellInterior(Mesh *mesh):
265	ViewCell(mesh)
266	{
267	}
268
269
270	bool ViewCellInterior::IsLeaf() const
271	{
272	return false;
273	}
274
275
276	void ViewCellInterior::SetupChildLink(ViewCell *l)
277	{
278	mChildren.push_back(l);
279	l->mParent = this;
280	}
281
282
283	void ViewCellInterior::RemoveChildLink(ViewCell *l)
284	{
285	// erase leaf from old view cell
286	ViewCellContainer::iterator it = mChildren.begin();
287
288	for (; (*it) != l; ++ it);
289	if (it == mChildren.end())
290	Debug << "error" << endl;
291	else
292	mChildren.erase(it);
293	}
294
295	/************************************************************************/
296	/* class ViewCellsStatistics implementation */
297	/************************************************************************/
298
299
300
301
302	void ViewCellsStatistics::Print(ostream &app) const
303	{
304	app << "=========== View Cells Statistics ===============\n";
305
306	app << setprecision(4);
307
308	//app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
309
310	app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;
311
312	app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;
313
314	app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;
315
316	app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;
317
318	app << "#N_PEMPTYPVS ( view cells with empty PVS )\n" << emptyPvs << endl;
319
320	app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;
321
322	app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl;
323
324	app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl;
325
326	app << "#N_INVALID ( number of invalid view cells )\n" << invalid << endl;
327
328	app << "========== End of View Cells Statistics ==========\n";
329	}
330
331
332	/*************************************************************************/
333	/* class ViewCellsTree implementation */
334	/*************************************************************************/
335
336
337	ViewCellsTree::ViewCellsTree(ViewCellsManager *vcm):
338	mRoot(NULL),
339	mUseAreaForPvs(false),
340	mViewCellsManager(vcm),
341	mIsCompressed(false)
342	{
343	environment->GetBoolValue("ViewCells.Visualization.exportMergedViewCells", mExportMergedViewCells);
344	environment->GetFloatValue("ViewCells.maxStaticMemory", mMaxMemory);
345
346	//-- merge options
347	environment->GetFloatValue("ViewCells.PostProcess.renderCostWeight", mRenderCostWeight);
348	environment->GetIntValue("ViewCells.PostProcess.minViewCells", mMergeMinViewCells);
349	environment->GetFloatValue("ViewCells.PostProcess.maxCostRatio", mMergeMaxCostRatio);
350	environment->GetBoolValue("ViewCells.PostProcess.refine", mRefineViewCells);
351
352
353	Debug << "========= view cell tree options ================\n";
354	Debug << "minimum view cells: " << mMergeMinViewCells << endl;
355	Debug << "max cost ratio: " << mMergeMaxCostRatio << endl;
356	Debug << "max memory: " << mMaxMemory << endl;
357	Debug << "refining view cells: " << mRefineViewCells << endl;
358
359	MergeCandidate::sRenderCostWeight = mRenderCostWeight;
360
361	mStats.open("mergeStats.log");
362	}
363
364
365	// return memory usage in MB
366	float ViewCellsTree::GetMemUsage() const
367	{
368	return 0;
369	/*(sizeof(ViewCellsTree) +
370	mBspStats.Leaves() * sizeof(BspLeaf) +
371	mBspStats.Interior() * sizeof(BspInterior) +
372	mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);*/
373	}
374
375
376	int ViewCellsTree::GetSize(ViewCell *vc) const
377	{
378	int vcSize = 0;
379
380	stack<ViewCell *> tstack;
381
382	tstack.push(vc);
383
384	while (!tstack.empty())
385	{
386	ViewCell *vc = tstack.top();
387	tstack.pop();
388
389	if (vc->IsLeaf())
390	{
391	++ vcSize;
392	}
393	else
394	{
395	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
396	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
397	for (it = interior->mChildren.begin(); it != it_end; ++ it)
398	tstack.push(*it);
399
400	}
401	}
402
403	return vcSize;
404	}
405
406
407	void ViewCellsTree::CollectLeaves(ViewCell *vc, ViewCellContainer &leaves) const
408	{
409	stack<ViewCell *> tstack;
410
411	tstack.push(vc);
412
413	while (!tstack.empty())
414	{
415	ViewCell *vc = tstack.top();
416	tstack.pop();
417
418	if (vc->IsLeaf())
419	{
420	leaves.push_back(vc);
421	}
422	else
423	{
424	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
425	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
426	for (it = interior->mChildren.begin(); it != it_end; ++ it)
427	tstack.push(*it);
428
429	}
430	}
431	}
432
433
434	ViewCellsTree::~ViewCellsTree()
435	{
436	DEL_PTR(mRoot);
437	}
438
439
440	int ViewCellsTree::ConstructMergeTree(const VssRayContainer &rays,
441	const ObjectContainer &objects)
442	{
443	mNumActiveViewCells = (int)mViewCellsManager->GetViewCells().size();
444
445	float variance = 0;
446	int totalPvs = 0;
447	float totalCost = 0;
448
449	//-- compute statistics values of initial view cells
450	mViewCellsManager->EvaluateRenderStatistics(totalCost,
451	mExpectedCost,
452	mDeviation,
453	variance,
454	totalPvs,
455	mAvgRenderCost);
456
457
458	//-- fill merge queue
459	vector<MergeCandidate> candidates;
460
461	mViewCellsManager->CollectMergeCandidates(rays, candidates);
462	while(!candidates.empty())
463	{
464	MergeCandidate mc = candidates.back();
465	candidates.pop_back();
466	EvalMergeCost(mc);
467	mMergeQueue.push(mc);
468	}
469
470	Debug << "*********************** merge *********************************" << endl;
471	Debug << "deviation: " << mDeviation << endl;
472	Debug << "avg render cost: " << mAvgRenderCost << endl;
473	Debug << "expected cost: " <<mExpectedCost << endl;
474
475
476	ViewCellsManager::PvsStatistics pvsStats;
477	mViewCellsManager->GetPvsStatistics(pvsStats);
478
479	static float expectedValue = pvsStats.avgPvs;
480
481	// the current view cells are kept in this container
482	// we start with the current view cells from the
483	// view cell manager. They will change with
484	// subsequent merges
485	ViewCellContainer &activeViewCells = mViewCellsManager->GetViewCells();
486
487
488	ViewCell::NewMail();
489
490	MergeStatistics mergeStats;
491	mergeStats.Start();
492
493	long startTime = GetTime();
494
495	mergeStats.collectTime = TimeDiff(startTime, GetTime());
496	mergeStats.candidates = (int)mMergeQueue.size();
497	startTime = GetTime();
498
499	// frequency stats are updated
500	const int statsOut = 100;
501
502	// passes are needed for statistics, because we don't want to record
503	// every merge
504	int pass = 0;
505	int mergedPerPass = 0;
506	float realExpectedCost = mExpectedCost;
507	float realAvgRenderCost = mAvgRenderCost;
508	int realNumActiveViewCells = mNumActiveViewCells;
509
510	// maximal ratio of old expected render cost to expected render
511	// when the the render queue has to be reset.
512	float avgCostMaxDeviation;
513	int maxMergesPerPass;
514	int numMergedViewCells = 0;
515
516	environment->GetIntValue("ViewCells.PostProcess.maxMergesPerPass", maxMergesPerPass);
517	environment->GetFloatValue("ViewCells.PostProcess.avgCostMaxDeviation", avgCostMaxDeviation);
518
519	cout << "actual merge starts now ... " << endl;
520
521
522	//-- use priority queue to merge leaf pairs
523
524	while (!mMergeQueue.empty())// && (realNumActiveViewCells > mMergeMinViewCells))
525	{
526	//-- reset merge queue if the ratio of current expected cost / real expected cost
527	// too small or after a given number of merges
528	if ((mergedPerPass > maxMergesPerPass) \|\|
529	(avgCostMaxDeviation > mAvgRenderCost / realAvgRenderCost))
530	{
531	Debug << "********** reset queue ***************\n"
532	<< "ratios: " << avgCostMaxDeviation
533	<< " real avg render cost " << realAvgRenderCost << " average render cost " << mAvgRenderCost
534	<< " merged per pass : " << mergedPerPass << " of maximal " << maxMergesPerPass << endl;
535
536	Debug << "Values before reset: "
537	<< " erc: " << mExpectedCost
538	<< " avgrc: " << mAvgRenderCost
539	<< " dev: " << mDeviation << endl;
540
541	// adjust render cost
542	++ pass;
543
544	mergedPerPass = 0;
545	mExpectedCost = realExpectedCost;
546	mAvgRenderCost = realAvgRenderCost;
547	mNumActiveViewCells = realNumActiveViewCells;
548
549	const int numMergedViewCells = UpdateActiveViewCells(activeViewCells);
550
551	// refines the view cells
552	// then priorities are recomputed
553	// and the candidates are put back into merge queue
554	if (mRefineViewCells)
555	RefineViewCells(rays, objects);
556	else
557	ResetMergeQueue();
558
559
560	Debug << "Values after reset: "
561	<< " erc: " << mExpectedCost
562	<< " avg: " << mAvgRenderCost
563	<< " dev: " << mDeviation << endl;
564
565	if (mExportMergedViewCells)
566	{
567	ExportMergedViewCells(activeViewCells, objects, numMergedViewCells);
568	}
569	}
570
571	#ifdef _DEBUG
572	Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() <<
573	<< " rel mergecost: " << mMergeQueue.top().GetRenderCost() / mExpectedCost <<
574	<< " max ratio: " << mMergeMaxCostRatio << endl
575	<< " expected value: " << realExpectedCost << endl;
576	#endif
577
578
579	MergeCandidate mc = mMergeQueue.top();
580	mMergeQueue.pop();
581
582	// both view cells equal
583	// NOTE: do I really still need this? probably cannot happen!!
584	if (mc.mLeftViewCell == mc.mRightViewCell)
585	continue;
586
587	if (mc.IsValid())
588	{
589	ViewCell::NewMail();
590
591	-- realNumActiveViewCells;
592	++ mergeStats.merged;
593	++ mergedPerPass;
594
595
596	//-- update statistical values
597
598	// total render cost and deviation has changed
599	// real expected cost will be larger than expected cost used for the
600	// cost heuristics, but cannot recompute costs on each increase of the
601	// expected cost
602
603	totalCost += mc.GetRenderCost();
604	mDeviation += mc.GetDeviationIncr();
605
606	realExpectedCost = totalCost / (float)realNumActiveViewCells;
607
608	const float currentMergeCost = mc.GetMergeCost();
609
610	// merge the view cells of leaf1 and leaf2
611	int pvsDiff;
612	ViewCellInterior *mergedVc =
613	MergeViewCells(mc.mLeftViewCell, mc.mRightViewCell, pvsDiff);
614
615	totalPvs += pvsDiff;
616
617	// set timestamp
618	mergedVc->SetTimeStamp(mergeStats.merged);
619
620	realAvgRenderCost = (float)totalPvs / (float)realNumActiveViewCells;
621	#if VC_HISTORY
622	if (mc.mLeftViewCell->IsSibling(mc.mRightViewCell))
623	++ mergeStats.siblings;
624	#endif
625	if (((mergeStats.merged % statsOut) == 0) \|\|
626	(realNumActiveViewCells == mMergeMinViewCells))
627	{
628	cout << "merged " << mergeStats.merged << " view cells" << endl;
629
630	mStats
631	<< "#Pass\n" << pass << endl
632	<< "#Merged\n" << mergeStats.merged << endl
633	<< "#Viewcells\n" << realNumActiveViewCells << endl
634	<< "#CurrentCost\n" << currentMergeCost << endl
635	<< "#RelativeCost\n" << currentMergeCost / mOverallCost << endl
636	<< "#CurrentPvs\n" << mc.GetLeftViewCell()->GetPvs().GetSize() << endl
637	<< "#MergedSiblings\n" << mergeStats.siblings << endl
638	<< "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
639	<< "#UsedExpectedCost\n" << mExpectedCost << endl
640	<< "#RealExpectedCost\n" << realExpectedCost << endl
641	<< "#RealAvgRenderCost\n" << realAvgRenderCost << endl
642	<< "#AvgRenderCost\n" << mAvgRenderCost << endl
643	<< "#expectedCostRatio\n" << mExpectedCost / realExpectedCost << endl
644	<< "#Deviation\n" << mDeviation / (float)realNumActiveViewCells << endl
645	<< "#TotalDeviation\n" << mDeviation<< endl;
646	}
647	}
648	else
649	{
650	// merge candidate not valid, because one of the leaves was already
651	// merged with another one => validate and reinsert into queue
652	if (ValidateMergeCandidate(mc))
653	{
654	EvalMergeCost(mc);
655	mMergeQueue.push(mc);
656	}
657	}
658	}
659
660	// adjust stats and reset queue one final time
661	mExpectedCost = realExpectedCost;
662	mAvgRenderCost = realAvgRenderCost;
663	mNumActiveViewCells = realNumActiveViewCells;
664
665	UpdateActiveViewCells(activeViewCells);
666
667	// refine view cells and reset costs
668	if (mRefineViewCells)
669	RefineViewCells(rays, objects);
670	else
671	ResetMergeQueue();
672
673	// create a root node if the merge was not done till root level,
674	// else take the single node as new root
675	if ((int)activeViewCells.size() > 1)
676	{
677	Debug << "creating root of view cell hierarchy for "
678	<< (int)activeViewCells.size() << " view cells" << endl;
679	/*for (int i = 0; i < activeViewCells.size(); ++ i){
680	Debug << "parent " << activeViewCells[i]->GetParent() << endl;
681	Debug << "viewcell " << activeViewCells[i] << endl;
682	}*/
683	ViewCellInterior *root = mViewCellsManager->MergeViewCells(activeViewCells);
684
685	root->SetTimeStamp(mergeStats.merged + 1);
686	mRoot = root;
687	}
688	else if ((int)activeViewCells.size() == 1)
689	{
690	Debug << "setting root of the merge history" << endl;
691	mRoot = activeViewCells[0];
692	}
693
694	// TODO delete because makes no sense here
695	mergeStats.expectedRenderCost = realExpectedCost;
696	mergeStats.deviation = mDeviation;
697
698	// we want to optimize this heuristics
699	mergeStats.heuristics =
700	mDeviation * (1.0f - mRenderCostWeight) +
701	mExpectedCost * mRenderCostWeight;
702
703	mergeStats.mergeTime = TimeDiff(startTime, GetTime());
704	mergeStats.Stop();
705
706	Debug << mergeStats << endl << endl;
707
708
709	//TODO: should return sample contributions?
710	return mergeStats.merged;
711	}
712
713
714	ViewCell *ViewCellsTree::GetRoot() const
715	{
716	return mRoot;
717	}
718
719
720	void ViewCellsTree::ResetMergeQueue()
721	{
722	cout << "reset merge queue ... ";
723
724	vector<MergeCandidate> buf;
725	buf.reserve(mMergeQueue.size());
726
727
728	// store merge candidates in intermediate buffer
729	while (!mMergeQueue.empty())
730	{
731	MergeCandidate mc = mMergeQueue.top();
732	mMergeQueue.pop();
733
734	// recalculate cost
735	if (ValidateMergeCandidate(mc))
736	{
737	EvalMergeCost(mc);
738	buf.push_back(mc);
739	}
740	}
741
742	vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
743
744	// reinsert back into queue
745	for (bit = buf.begin(); bit != bit_end; ++ bit)
746	{
747	mMergeQueue.push(*bit);
748	}
749
750	cout << "finished" << endl;
751	}
752
753
754	int ViewCellsTree::UpdateActiveViewCells(ViewCellContainer &viewCells)
755	{
756	int numMergedViewCells = 0;
757
758	Debug << "updating active vc: " << (int)viewCells.size() << endl;
759	// find all already merged view cells and remove them from view cells
760
761	// sort out all view cells which are not active anymore, i.e., they
762	// were already part of a merge
763	int i = 0;
764
765	ViewCell::NewMail();
766
767	while (1)
768	{
769	// remove all merged view cells from end of the vector
770	while (!viewCells.empty() && (viewCells.back()->GetParent()))
771	{
772	viewCells.pop_back();
773	}
774
775	// all merged view cells have been found
776	if (i >= viewCells.size())
777	break;
778
779	// already merged view cell, put it to end of vector
780	if (viewCells[i]->GetParent())
781	swap(viewCells[i], viewCells.back());
782
783	viewCells[i ++]->Mail();
784	}
785
786
787	// add new view cells to container only if they don't have been
788	// merged in the mean time
789	ViewCellContainer::const_iterator ait, ait_end = mMergedViewCells.end();
790	for (ait = mMergedViewCells.begin(); ait != ait_end; ++ ait)
791	{
792	ViewCell *vc = mMergedViewCells.back();
793	if (!vc->GetParent() && !vc->Mailed())
794	{
795	vc->Mail();
796	viewCells.push_back(vc);
797	++ numMergedViewCells;
798	}
799	}
800
801	mMergedViewCells.clear();
802
803	// update standard deviation
804	ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
805
806	mDeviation = 0;
807
808	for (vit = viewCells.begin(); vit != vit_end; ++ vit)
809	{
810	int lower = mViewCellsManager->GetMinPvsSize();
811	int upper = mViewCellsManager->GetMaxPvsSize();
812	float penalty = EvalPvsPenalty((*vit)->GetPvs().GetSize(), lower, upper);
813
814	mDeviation += fabs(mAvgRenderCost - penalty);
815	}
816
817	mDeviation /= (float)viewCells.size();
818
819	return numMergedViewCells;
820	}
821
822
823	void ViewCellsTree::ExportMergedViewCells(ViewCellContainer &viewCells,
824	const ObjectContainer &objects,
825	const int numMergedViewCells)
826	{
827
828
829	char s[64];
830
831	sprintf(s, "merged_viewcells%07d.x3d", (int)viewCells.size());
832	Exporter *exporter = Exporter::GetExporter(s);
833
834	if (exporter)
835	{
836	cout << "exporting " << (int)viewCells.size() << " merged view cells ... ";
837	exporter->ExportGeometry(objects);
838	//Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
839	ViewCellContainer::const_iterator it, it_end = viewCells.end();
840
841	int i = 0;
842	for (it = viewCells.begin(); it != it_end; ++ it)
843	{
844	Material m;
845	// assign special material to new view cells
846	// new view cells are on the back of container
847	if (i ++ >= (viewCells.size() - numMergedViewCells))
848	{
849	//m = RandomMaterial();
850	m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
851	m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
852	m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
853	}
854	else
855	{
856	float col = RandomValue(0.1f, 0.4f);
857	m.mDiffuseColor.r = col;
858	m.mDiffuseColor.g = col;
859	m.mDiffuseColor.b = col;
860	}
861
862	exporter->SetForcedMaterial(m);
863	mViewCellsManager->ExportViewCellGeometry(exporter, *it);
864	}
865	delete exporter;
866	cout << "finished" << endl;
867	}
868	}
869
870
871	// TODO: should be done in view cells manager
872	ViewCellInterior ViewCellsTree::MergeViewCells(ViewCell l,
873	ViewCell *r,
874	int &pvsDiff) //const
875	{
876	ViewCellInterior *vc = mViewCellsManager->MergeViewCells(l, r);
877
878	// if merge was unsuccessful
879	if (!vc) return NULL;
880
881	// set new size of view cell
882	if (mUseAreaForPvs)
883	vc->SetArea(l->GetArea() + l->GetArea());
884	else
885	vc->SetVolume(r->GetVolume() + r->GetVolume());
886
887	// important so other merge candidates sharing this view cell
888	// are notified that the merge cost must be updated!!
889	vc->Mail();
890
891	const int pvs1 = l->GetPvs().GetSize();
892	const int pvs2 = r->GetPvs().GetSize();
893
894
895	// new view cells are stored in this vector
896	mMergedViewCells.push_back(vc);
897
898	pvsDiff = vc->GetPvs().GetSize() - pvs1 - pvs2;
899
900	return vc;
901	}
902
903
904
905	int ViewCellsTree::RefineViewCells(const VssRayContainer &rays,
906	const ObjectContainer &objects)
907	{
908	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
909
910	// intermediate buffer for shuffled view cells
911	vector<MergeCandidate> buf;
912	buf.reserve(mMergeQueue.size());
913
914	// Use priority queue of remaining leaf pairs
915	// The candidates either share the same view cells or
916	// are border leaves which share a boundary.
917	// We test if they can be shuffled, i.e.,
918	// either one leaf is made part of one view cell or the other
919	// leaf is made part of the other view cell. It is tested if the
920	// remaining view cells are "better" than the old ones.
921
922	const int numPasses = 3;
923	int pass = 0;
924	int passShuffled = 0;
925	int shuffled = 0;
926	int shuffledViewCells = 0;
927
928	ViewCell::NewMail();
929
930	while (!mMergeQueue.empty())
931	{
932	MergeCandidate mc = mMergeQueue.top();
933	mMergeQueue.pop();
934
935	// both view cells equal or already shuffled
936	if ((mc.GetLeftViewCell() == mc.GetRightViewCell()) \|\|
937	mc.GetLeftViewCell()->IsLeaf() \|\| mc.GetRightViewCell()->IsLeaf())
938	{
939	continue;
940	}
941
942	// candidate for shuffling
943	const bool wasShuffled = ShuffleLeaves(mc);
944
945	// shuffled or put into other queue for further refine
946	if (wasShuffled)
947	{
948	++ passShuffled;
949
950	if (!mc.GetLeftViewCell()->Mailed())
951	{
952	mc.GetLeftViewCell()->Mail();
953	++ shuffledViewCells;
954	}
955	if (!mc.GetRightViewCell()->Mailed())
956	{
957	mc.GetRightViewCell()->Mail();
958	++ shuffledViewCells;
959	}
960	}
961
962	// put back into intermediate vector
963	buf.push_back(mc);
964	}
965
966
967	//-- in the end, the candidates must be in the mergequeue again
968	// with the correct cost
969
970	cout << "reset merge queue ... ";
971
972
973	vector<MergeCandidate>::const_iterator bit, bit_end = buf.end();
974
975	for (bit = buf.begin(); bit != bit_end; ++ bit)
976	{
977	MergeCandidate mc = *bit;
978	// recalculate cost
979	if (ValidateMergeCandidate(mc))
980	{
981	EvalMergeCost(mc);
982	mMergeQueue.push(mc);
983	}
984	}
985
986	cout << "finished" << endl;
987
988	return shuffledViewCells;
989	}
990
991
992
993
994	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
995	{
996	return pvs1.AddPvs(pvs2);
997	}
998
999
1000	// recomputes pvs size minus pvs of leaf l
1001	#if 0
1002	inline int SubtractedPvsSize(BspViewCell vc, BspLeaf l, const ObjectPvs &pvs2)
1003	{
1004	ObjectPvs pvs;
1005	vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
1006	for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
1007	if (*it != l)
1008	pvs.AddPvs((it)->mPvs);
1009	return pvs.GetSize();
1010	}
1011	#endif
1012
1013
1014	// computes pvs1 minus pvs2
1015	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
1016	{
1017	return pvs1.SubtractPvs(pvs2);
1018	}
1019
1020
1021	float ViewCellsTree::EvalShuffleCost(ViewCell *leaf,
1022	ViewCellInterior *vc1,
1023	ViewCellInterior *vc2) const
1024	{
1025	//const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
1026	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), leaf->GetPvs());
1027	const int pvs2 = AddedPvsSize(vc2->GetPvs(), leaf->GetPvs());
1028
1029	const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1030	const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1031
1032	const float pvsPenalty1 =
1033	EvalPvsPenalty(pvs1, lowerPvsLimit, upperPvsLimit);
1034
1035	const float pvsPenalty2 =
1036	EvalPvsPenalty(pvs2, lowerPvsLimit, upperPvsLimit);
1037
1038
1039	// don't shuffle leaves with pvs > max
1040	if (0 && (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize()))
1041	{
1042	return 1e20f;
1043	}
1044
1045	float p1, p2;
1046
1047	if (mUseAreaForPvs)
1048	{
1049	p1 = vc1->GetArea() - leaf->GetArea();
1050	p2 = vc2->GetArea() + leaf->GetArea();
1051	}
1052	else
1053	{
1054	p1 = vc1->GetVolume() - leaf->GetVolume();
1055	p2 = vc2->GetVolume() + leaf->GetVolume();
1056	}
1057
1058	const float renderCost1 = pvsPenalty1 * p1;
1059	const float renderCost2 = pvsPenalty2 * p2;
1060
1061	float dev1, dev2;
1062
1063	if (1)
1064	{
1065	dev1 = fabs(mAvgRenderCost - pvsPenalty1);
1066	dev2 = fabs(mAvgRenderCost - pvsPenalty2);
1067	}
1068	else
1069	{
1070	dev1 = fabs(mExpectedCost - renderCost1);
1071	dev2 = fabs(mExpectedCost - renderCost2);
1072	}
1073
1074	return mRenderCostWeight * (renderCost1 + renderCost2) +
1075	(1.0f - mRenderCostWeight) * (dev1 + dev2) / (float)mNumActiveViewCells;
1076	}
1077
1078
1079	void ViewCellsTree::ShuffleLeaf(ViewCell *leaf,
1080	ViewCellInterior *vc1,
1081	ViewCellInterior *vc2) const
1082	{
1083	// compute new pvs and area
1084	// TODO change
1085	vc1->GetPvs().SubtractPvs(leaf->GetPvs());
1086	vc2->GetPvs().AddPvs(leaf->GetPvs());
1087
1088	if (mUseAreaForPvs)
1089	{
1090	vc1->SetArea(vc1->GetArea() - leaf->GetArea());
1091	vc2->SetArea(vc2->GetArea() + leaf->GetArea());
1092	}
1093	else
1094	{
1095	vc1->SetVolume(vc1->GetVolume() - leaf->GetVolume());
1096	vc2->SetVolume(vc2->GetVolume() + leaf->GetVolume());
1097	}
1098
1099
1100	ViewCellInterior p = dynamic_cast<ViewCellInterior >(leaf->GetParent());
1101
1102	p->RemoveChildLink(leaf);
1103	vc2->SetupChildLink(leaf);
1104	}
1105
1106
1107	bool ViewCellsTree::ShuffleLeaves(MergeCandidate &mc) const
1108	{
1109	float cost1, cost2;
1110
1111	ViewCellInterior vc1 = dynamic_cast<ViewCellInterior >(mc.GetLeftViewCell());
1112	ViewCellInterior vc2 = dynamic_cast<ViewCellInterior >(mc.GetRightViewCell());
1113
1114	ViewCell *leaf1 = mc.GetInitialLeftViewCell();
1115	ViewCell *leaf2 = mc.GetInitialRightViewCell();
1116
1117	//-- first test if shuffling would decrease cost
1118	cost1 = GetCostHeuristics(vc1);
1119	cost2 = GetCostHeuristics(vc2);
1120
1121	const float oldCost = cost1 + cost2;
1122
1123	float shuffledCost1 = Limits::Infinity;
1124	float shuffledCost2 = Limits::Infinity;
1125
1126	if (leaf1)
1127	shuffledCost1 = EvalShuffleCost(leaf1, vc1, vc2);
1128	if (leaf2)
1129	shuffledCost2 = EvalShuffleCost(leaf2, vc2, vc1);
1130
1131	// if cost of shuffle is less than old cost => shuffle
1132	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
1133	return false;
1134
1135	if (shuffledCost1 < shuffledCost2)
1136	{
1137	if (leaf1)
1138	ShuffleLeaf(leaf1, vc1, vc2);
1139	mc.mInitialLeftViewCell = NULL;
1140	}
1141	else
1142	{
1143	if (leaf2)
1144	ShuffleLeaf(leaf2, vc2, vc1);
1145	mc.mInitialRightViewCell = NULL;
1146	}
1147
1148	return true;
1149	}
1150
1151
1152	float ViewCellsTree::GetVariance(ViewCell *vc) const
1153	{
1154	const int upper = mViewCellsManager->GetMaxPvsSize();
1155	const int lower = mViewCellsManager->GetMinPvsSize();
1156
1157	if (1)
1158	{
1159	const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1160	return (mAvgRenderCost - penalty) * (mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1161	}
1162
1163	const float leafCost = GetRenderCost(vc);
1164	return (mExpectedCost - leafCost) * (mExpectedCost - leafCost);
1165	}
1166
1167
1168	float ViewCellsTree::GetDeviation(ViewCell *vc) const
1169	{
1170	const int upper = mViewCellsManager->GetMaxPvsSize();
1171	const int lower = mViewCellsManager->GetMinPvsSize();
1172
1173	if (1)
1174	{
1175	const float penalty = EvalPvsPenalty(vc->GetPvs().GetSize(), lower, upper);
1176	return fabs(mAvgRenderCost - penalty) / (float)mNumActiveViewCells;
1177	}
1178
1179	const float renderCost = GetRenderCost(vc);
1180	return fabs(mExpectedCost - renderCost);
1181	}
1182
1183
1184
1185	float ViewCellsTree::GetRenderCost(ViewCell *vc) const
1186	{
1187	if (mUseAreaForPvs)
1188	return vc->GetPvs().GetSize() * vc->GetArea();
1189
1190	return vc->GetPvs().GetSize() * vc->GetVolume();
1191	}
1192
1193
1194	float ViewCellsTree::GetCostHeuristics(ViewCell *vc) const
1195	{
1196	return GetRenderCost(vc) * mRenderCostWeight +
1197	GetDeviation(vc) * (1.0f - mRenderCostWeight);
1198	}
1199
1200
1201	bool ViewCellsTree::ValidateMergeCandidate(MergeCandidate &mc) const
1202	{
1203	while (mc.mLeftViewCell->mParent)
1204	{
1205	mc.mLeftViewCell = mc.mLeftViewCell->mParent;
1206	}
1207
1208	while (mc.mRightViewCell->mParent)
1209	{
1210	mc.mRightViewCell = mc.mRightViewCell->mParent;
1211	}
1212
1213	return mc.mLeftViewCell != mc.mRightViewCell;
1214	}
1215
1216
1217	void ViewCellsTree::EvalMergeCost(MergeCandidate &mc) const
1218	{
1219	//-- compute pvs difference
1220	const int newPvs =
1221	ComputeMergedPvsSize(mc.mLeftViewCell->GetPvs(),
1222	mc.mRightViewCell->GetPvs());
1223
1224	const float newPenalty =
1225	EvalPvsPenalty(newPvs,
1226	mViewCellsManager->GetMinPvsSize(),
1227	mViewCellsManager->GetMaxPvsSize());
1228
1229	ViewCell *vc1 = mc.mLeftViewCell;
1230	ViewCell *vc2 = mc.mRightViewCell;
1231
1232	//-- compute ratio of old cost
1233	// (i.e., added size of left and right view cell times pvs size)
1234	// to new rendering cost (i.e, size of merged view cell times pvs size)
1235	const float oldCost = GetRenderCost(vc1) + GetRenderCost(vc2);
1236
1237	const float newCost = mUseAreaForPvs ?
1238	(float)newPenalty * (vc1->GetArea() + vc2->GetArea()) :
1239	(float)newPenalty * (vc1->GetVolume() + vc2->GetVolume());
1240
1241
1242	// strong penalty if pvs size too large
1243	if (0 && (newPvs > mViewCellsManager->GetMaxPvsSize()))
1244	{
1245	mc.mRenderCost = 1e20f;
1246	}
1247	else
1248	{
1249	mc.mRenderCost = (newCost - oldCost) /
1250	mViewCellsManager->GetViewSpaceBox().GetVolume();
1251	}
1252
1253
1254	//-- merge cost also takes deviation into account
1255	float newDev, oldDev;
1256
1257	if (1)
1258	newDev = fabs(mAvgRenderCost - newPenalty) / (float)mNumActiveViewCells;
1259	else
1260	newDev = fabs(mExpectedCost - newCost) / (float)mNumActiveViewCells;
1261
1262	oldDev = GetDeviation(vc1) + GetDeviation(vc2);
1263
1264	// compute deviation increase
1265	mc.mDeviationIncr = newDev - oldDev;
1266
1267	//Debug << "render cost: " << mc.mRenderCost * mRenderCostWeight << endl;
1268	//Debug << "standard deviation: " << mc.mDeviationIncr * mRenderCostWeight << endl;
1269	}
1270
1271	void ViewCellsTree::CompressViewCellsPvs()
1272	{
1273	if (!mIsCompressed)
1274	{
1275	mIsCompressed = true;
1276	CompressViewCellsPvs(mRoot);
1277	}
1278	}
1279
1280	void ViewCellsTree::CompressViewCellsPvs(ViewCell *root)
1281	{
1282	if (!root->IsLeaf())
1283	{
1284	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(root);
1285
1286	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1287
1288	// compress child sets first
1289	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1290	{
1291	CompressViewCellsPvs(*it);
1292	}
1293
1294	// compress root node
1295	PropagateUpVisibility(interior);
1296	}
1297	}
1298
1299
1300	void ViewCellsTree::CollectBestViewCellSet(ViewCellContainer &viewCells,
1301	const int numViewCells)
1302	{
1303	TraversalQueue tqueue;
1304	tqueue.push(mRoot);
1305
1306	while (!tqueue.empty())
1307	{
1308	ViewCell *vc = tqueue.top();
1309
1310	// save the view cells if it is a leaf or if enough view cells have already been traversed
1311	// because of the priority queue, this will be the optimal set of v
1312	if (vc->IsLeaf() \|\| ((viewCells.size() + tqueue.size()) >= numViewCells))
1313	{
1314	// todo: should be done with a function taking the active flag and some
1315	// time stamp so I don't have to reset view cells, this also means that
1316	// the leaf view cells can be set active fist
1317	vc->mIsActive = true;
1318	viewCells.push_back(vc);
1319	}
1320	else
1321	{
1322	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1323
1324	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1325
1326	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1327	{
1328	tqueue.push(*it);
1329	}
1330	}
1331
1332	tqueue.pop();
1333	}
1334	}
1335
1336
1337	void ViewCellsTree::PropagateUpVisibility(ViewCellInterior *interior)
1338	{
1339	Intersectable::NewMail((int)interior->mChildren.size());
1340
1341	ViewCellContainer::const_iterator cit, cit_end = interior->mChildren.end();
1342
1343	ObjectPvsMap::const_iterator oit;
1344
1345	// mail all objects in the leaf sets
1346	// we are interested in the objects which are present in all leaves
1347	// => count how often an object is part of a child set
1348	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1349	{
1350	ViewCell vc = cit;
1351
1352	ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1353
1354	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1355	{
1356	Intersectable obj = (oit).first;
1357	if ((cit == interior->mChildren.begin()) && !obj->Mailed())
1358	obj->Mail();
1359
1360	int incm = obj->IncMail();
1361	}
1362	}
1363
1364	interior->GetPvs().mEntries.clear();
1365
1366
1367	// only the objects which are present in all leaf pvs
1368	// should remain in the parent pvs
1369	// these are the objects which have been mailed in all children
1370	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1371	{
1372	ViewCell vc = cit;
1373
1374	ObjectPvsMap::const_iterator oit_end = vc->GetPvs().mEntries.end();
1375
1376	for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1377	{
1378	if ((*oit).first->Mailed((int)interior->mChildren.size()))
1379	{
1380	interior->GetPvs().AddSample((oit).first, (oit).second.mSumPdf);
1381	}
1382	}
1383	}
1384
1385
1386
1387	// delete all the objects from the leaf sets which were moved to parent pvs
1388	ObjectPvsMap::const_iterator oit_end = interior->GetPvs().mEntries.end();
1389
1390	for (oit = interior->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
1391	{
1392	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1393	{
1394	if (!(cit)->GetPvs().RemoveSample((oit).first, Limits::Infinity))
1395	Debug << "should not come here!" << endl;
1396	}
1397	}
1398
1399	int dummy = interior->GetPvs().GetSize();
1400
1401	for (cit = interior->mChildren.begin(); cit != cit_end; ++ cit)
1402	{
1403	dummy += (*cit)->GetPvs().GetSize();
1404	}
1405
1406	}
1407
1408
1409
1410	void ViewCellsTree::GetPvs(ViewCell *vc, ObjectPvs &pvs) const
1411	{
1412	Intersectable::NewMail();
1413
1414	if (!mIsCompressed)
1415	pvs = vc->GetPvs();
1416
1417	int pvsSize = 0;
1418	ViewCell *root = vc;
1419
1420	// also add pvs from this view cell to root
1421	while (root->GetParent())
1422	{
1423	root = root->GetParent();
1424	pvs.AddPvs(root->GetPvs());
1425	}
1426
1427	stack<ViewCell *> tstack;
1428	tstack.push(vc);
1429
1430	while (!tstack.empty())
1431	{
1432	vc = tstack.top();
1433	tstack.pop();
1434
1435	pvs.AddPvs(vc->GetPvs());
1436
1437	if (!vc->IsLeaf())
1438	{
1439	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1440
1441	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1442
1443	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1444	{
1445	tstack.push(*it);
1446	}
1447	}
1448	}
1449	}
1450
1451
1452	int ViewCellsTree::GetPvsSize(ViewCell *vc) const
1453	{
1454	Intersectable::NewMail();
1455
1456	if (!mIsCompressed)
1457	return vc->GetPvs().GetSize();
1458
1459	int pvsSize = 0;
1460	ViewCell *root = vc;
1461
1462	// also add pvs from this view cell to root
1463	while (root->GetParent())
1464	{
1465	root = root->GetParent();
1466	pvsSize += CountDiffPvs(root);
1467	}
1468
1469	stack<ViewCell *> tstack;
1470	tstack.push(vc);
1471
1472	Debug << "current size: " << pvsSize << endl;
1473
1474	while (!tstack.empty())
1475	{
1476	vc = tstack.top();
1477	tstack.pop();
1478
1479	pvsSize += CountDiffPvs(vc);
1480
1481	if (!vc->IsLeaf())
1482	{
1483	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1484
1485	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1486
1487	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1488	{
1489	tstack.push(*it);
1490	}
1491	}
1492	}
1493
1494	return pvsSize;
1495
1496	}
1497
1498
1499	float ViewCellsTree::GetMemoryCost(ViewCell *vc) const
1500	{
1501	const float entrySize =
1502	sizeof(PvsData<Intersectable >) + sizeof(Intersectable );
1503
1504	return (float)GetNumPvsEntries(vc) * entrySize;
1505	}
1506
1507
1508	int ViewCellsTree::GetNumPvsEntries(ViewCell *vc) const
1509	{
1510	int pvsSize = 0;
1511	// only count leaves for uncompressed method for fairness
1512	if (mIsCompressed \|\| vc->IsLeaf())
1513	pvsSize = vc->GetPvs().GetSize();
1514
1515	if (!vc->IsLeaf())
1516	{
1517	ViewCellInterior interior = dynamic_cast<ViewCellInterior >(vc);
1518
1519	ViewCellContainer::const_iterator it, it_end = interior->mChildren.end();
1520
1521	for (it = interior->mChildren.begin(); it != it_end; ++ it)
1522	{
1523	pvsSize += GetNumPvsEntries(*it);
1524	}
1525	}
1526
1527	return pvsSize;
1528	}
1529
1530
1531	bool ViewCellsTree::IsCompressed() const
1532	{
1533	return mIsCompressed;
1534	}
1535
1536
1537	ViewCell ViewCellsTree::GetActiveViewCell(ViewCell vc) const
1538	{
1539	while (vc->GetParent() && !vc->mIsActive)
1540	{
1541	vc = vc->GetParent();
1542	}
1543
1544	return vc;
1545	}
1546
1547
1548	/**************************************************************************/
1549	/* MergeCandidate implementation */
1550	/**************************************************************************/
1551
1552
1553	MergeCandidate::MergeCandidate(ViewCell l, ViewCell r):
1554	mRenderCost(0),
1555	mDeviationIncr(0),
1556	mLeftViewCell(l),
1557	mRightViewCell(r),
1558	mInitialLeftViewCell(l),
1559	mInitialRightViewCell(r)
1560	{
1561	//EvalMergeCost();
1562	}
1563
1564
1565	void MergeCandidate::SetRightViewCell(ViewCell *v)
1566	{
1567	mRightViewCell = v;
1568	}
1569
1570
1571	void MergeCandidate::SetLeftViewCell(ViewCell *v)
1572	{
1573	mLeftViewCell = v;
1574	}
1575
1576
1577	ViewCell *MergeCandidate::GetRightViewCell() const
1578	{
1579	return mRightViewCell;
1580	}
1581
1582
1583	ViewCell *MergeCandidate::GetLeftViewCell() const
1584	{
1585	return mLeftViewCell;
1586	}
1587
1588
1589	ViewCell *MergeCandidate::GetInitialRightViewCell() const
1590	{
1591	return mInitialRightViewCell;
1592	}
1593
1594
1595	ViewCell *MergeCandidate::GetInitialLeftViewCell() const
1596	{
1597	return mInitialLeftViewCell;
1598	}
1599
1600
1601	bool MergeCandidate::IsValid() const
1602	{
1603	return !(mLeftViewCell->mParent \|\| mRightViewCell->mParent);
1604	}
1605
1606
1607	float MergeCandidate::GetRenderCost() const
1608	{
1609	return mRenderCost;
1610	}
1611
1612
1613	float MergeCandidate::GetDeviationIncr() const
1614	{
1615	return mDeviationIncr;
1616	}
1617
1618
1619	float MergeCandidate::GetMergeCost() const
1620	{
1621	return mRenderCost * sRenderCostWeight +
1622	mDeviationIncr * (1.0f - sRenderCostWeight);
1623	}
1624
1625
1626	/************************************************************************/
1627	/* MergeStatistics implementation */
1628	/************************************************************************/
1629
1630
1631	void MergeStatistics::Print(ostream &app) const
1632	{
1633	app << "===== Merge statistics ===============\n";
1634
1635	app << setprecision(4);
1636
1637	app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
1638
1639	app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
1640
1641	app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
1642
1643	app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
1644
1645	app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
1646
1647	app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
1648
1649	app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
1650
1651	app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
1652
1653	app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
1654
1655	app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
1656
1657	app << "#EXPECTEDCOST ( expected render cost )\n" << expectedRenderCost << "\n";
1658
1659	app << "#DEVIATION ( deviation )\n" << deviation << "\n";
1660
1661	app << "#HEURISTICS ( heuristics )\n" << heuristics << "\n";
1662
1663
1664	app << "===== END OF BspTree statistics ==========\n";
1665	}

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

Download in other formats: