Context Navigation

ViewCell.cpp @ 2643

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

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

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

Context Navigation

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

Download in other formats: