Context Navigation

source: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp @ 517

Revision 517, 60.0 KB checked in by mattausch, 19 years ago (diff)

Rev	Line
[408]	1
	2	// ================================================================
	3	// $Id: lsds_kdtree.cpp,v 1.18 2005/04/16 09:34:21 bittner Exp $
	4	// ****************************************************************
	5	/**
	6	The KD tree based LSDS
	7	*/
	8	// Initial coding by
	9	/**
	10	@author Jiri Bittner
	11	*/
	12
	13	// Standard headers
[406]	14	#include <stack>
[408]	15	#include <queue>
[406]	16	#include <algorithm>
[408]	17	#include <fstream>
	18	#include <string>
	19
	20	#include "VspKdTree.h"
	21
[406]	22	#include "Environment.h"
[408]	23	#include "VssRay.h"
	24	#include "Intersectable.h"
	25	#include "Ray.h"
[420]	26	#include "RayInfo.h"
[453]	27	#include "ViewCellsManager.h"
[462]	28	#include "ViewCellBsp.h"
[406]	29
[418]	30	// Static variables
[462]	31	int VspKdLeaf::sMailId = 0;
	32	int MergeCandidate::sMaxPvsSize = 150;
[472]	33	float MergeCandidate::sOverallCost = Limits::Small;
[428]	34	#define USE_FIXEDPOINT_T 0
	35
[420]	36	/// Adds object to the pvs of the front and back node
[409]	37	inline void AddObject2Pvs(Intersectable *object,
	38	const int side,
	39	int &pvsBack,
	40	int &pvsFront)
[406]	41	{
[408]	42	if (!object)
	43	return;
[465]	44
	45	if (side <= 0)
[409]	46	{
[465]	47	if (!object->Mailed() && !object->Mailed(2))
[409]	48	{
	49	++ pvsBack;
	50
[408]	51	if (object->Mailed(1))
	52	object->Mail(2);
	53	else
	54	object->Mail();
	55	}
	56	}
[465]	57
[428]	58	if (side >= 0)
[409]	59	{
[465]	60	if (!object->Mailed(1) && !object->Mailed(2))
[409]	61	{
	62	++ pvsFront;
[428]	63
[408]	64	if (object->Mailed())
	65	object->Mail(2);
	66	else
	67	object->Mail(1);
	68	}
	69	}
[406]	70	}
	71
[418]	72	/**************************************************************/
[462]	73	/* class VspKdNode implementation */
[420]	74	/**************************************************************/
	75
	76	// Inline constructor
[500]	77	VspKdNode::VspKdNode(VspKdNode *p):
[465]	78	mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
[420]	79	{}
	80
[465]	81	VspKdNode::~VspKdNode()
[480]	82	{
	83	};
[420]	84
[500]	85	inline VspKdNode *VspKdNode::GetParent() const
[420]	86	{
	87	return mParent;
	88	}
	89
[500]	90	inline void VspKdNode::SetParent(VspKdNode *p)
[420]	91	{
	92	mParent = p;
	93	}
	94
[465]	95	bool VspKdNode::IsLeaf() const
	96	{
	97	return mAxis == -1;
[420]	98	}
[465]	99
	100	int VspKdNode::GetAccessTime()
[420]	101	{
	102	return 0x7FFFFFF;
	103	}
	104
	105	/**************************************************************/
[462]	106	/* VspKdInterior implementation */
[418]	107	/**************************************************************/
[408]	108
[462]	109	VspKdInterior::VspKdInterior(VspKdInterior *p):
	110	VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
[418]	111	{
	112	}
	113
[462]	114	int VspKdInterior::GetAccessTime()
[418]	115	{
[419]	116	return mLastAccessTime;
[418]	117	}
	118
[465]	119	void VspKdInterior::SetupChildLinks(VspKdNode b, VspKdNode f)
[418]	120	{
	121	mBack = b;
	122	mFront = f;
[420]	123	b->SetParent(this);
	124	f->SetParent(this);
[418]	125	}
	126
[465]	127	void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,
[500]	128	VspKdNode *newChild)
[418]	129	{
	130	if (mBack == oldChild)
	131	mBack = newChild;
	132	else
	133	mFront = newChild;
	134	}
	135
[465]	136	int VspKdInterior::Type() const
	137	{
	138	return EInterior;
[418]	139	}
[465]	140
[462]	141	VspKdInterior::~VspKdInterior()
[418]	142	{
	143	DEL_PTR(mBack);
	144	DEL_PTR(mFront);
	145	}
[465]	146
	147	void VspKdInterior::Print(ostream &s) const
[418]	148	{
[423]	149	switch (mAxis)
	150	{
	151	case 0:
	152	s << "x "; break;
	153	case 1:
	154	s << "y "; break;
	155	case 2:
	156	s << "z "; break;
	157	}
	158
[419]	159	s << mPosition << " ";
[418]	160
	161	mBack->Print(s);
	162	mFront->Print(s);
	163	}
[465]	164
	165	int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)
[418]	166	{
[419]	167	return rayData.ComputeRayIntersection(mAxis, mPosition, t);
[418]	168	}
	169
[462]	170	VspKdNode *VspKdInterior::GetBack() const
[419]	171	{
	172	return mBack;
	173	}
[418]	174
[462]	175	VspKdNode *VspKdInterior::GetFront() const
[406]	176	{
[419]	177	return mFront;
	178	}
[406]	179
[420]	180
[486]	181	/*******************************************************************/
	182	/* class VspKdLeaf implementation */
	183	/*******************************************************************/
[462]	184
	185
[500]	186	VspKdLeaf::VspKdLeaf(VspKdNode *p,
[472]	187	const int nRays,
	188	const int maxCostMisses):
	189	VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL),
[495]	190	mMaxCostMisses(maxCostMisses), mPvs(NULL), mVolume(0)
[420]	191	{
	192	mRays.reserve(nRays);
	193	}
	194
[465]	195	VspKdLeaf::~VspKdLeaf()
[462]	196	{
[495]	197	DEL_PTR(mPvs);
[462]	198	}
[420]	199
[472]	200
	201	int VspKdLeaf::GetMaxCostMisses()
	202	{
	203	return mMaxCostMisses;
	204	}
	205
	206
[465]	207	int VspKdLeaf::Type() const
	208	{
	209	return ELeaf;
[420]	210	}
	211
[465]	212	void VspKdLeaf::Print(ostream &s) const
[420]	213	{
	214	s << endl << "L: r = " << (int)mRays.size() << endl;
	215	};
	216
[465]	217	void VspKdLeaf::AddRay(const RayInfo &data)
[420]	218	{
	219	mValidPvs = false;
	220	mRays.push_back(data);
	221	data.mRay->Ref();
	222	}
	223
[465]	224	int VspKdLeaf::GetPvsSize() const
[420]	225	{
	226	return mPvsSize;
	227	}
	228
[465]	229	void VspKdLeaf::SetPvsSize(const int s)
[420]	230	{
	231	mPvsSize = s;
	232	}
	233
[462]	234	void VspKdLeaf::Mail()
[465]	235	{
	236	mMailbox = sMailId;
[420]	237	}
	238
[465]	239	void VspKdLeaf::NewMail()
	240	{
	241	++ sMailId;
[420]	242	}
	243
[465]	244	bool VspKdLeaf::Mailed() const
	245	{
	246	return mMailbox == sMailId;
[420]	247	}
	248
[462]	249	bool VspKdLeaf::Mailed(const int mail) const
[420]	250	{
[462]	251	return mMailbox == mail;
[420]	252	}
	253
[462]	254	int VspKdLeaf::GetMailbox() const
[420]	255	{
[462]	256	return mMailbox;
	257	}
	258
[465]	259	float VspKdLeaf::GetAvgRayContribution() const
[462]	260	{
[420]	261	return GetPvsSize() / ((float)mRays.size() + Limits::Small);
	262	}
	263
[465]	264	float VspKdLeaf::GetSqrRayContribution() const
[420]	265	{
	266	return sqr(GetAvgRayContribution());
	267	}
	268
[462]	269	RayInfoContainer &VspKdLeaf::GetRays()
[426]	270	{
	271	return mRays;
	272	}
[428]	273
[462]	274	void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const
[428]	275	{
	276	RayInfoContainer::const_iterator it, it_end = mRays.end();
	277
	278	for (it = mRays.begin(); it != it_end; ++ it)
	279	{
	280	if ((*it).mRay->mTerminationObject)
	281	objects.push_back((*it).mRay->mTerminationObject);
	282	if ((*it).mRay->mOriginObject)
	283	objects.push_back((*it).mRay->mOriginObject);
	284	}
	285	}
	286
[462]	287	void VspKdLeaf::GetRays(VssRayContainer &rays)
[428]	288	{
	289	RayInfoContainer::const_iterator it, it_end = mRays.end();
	290
	291	for (it = mRays.begin(); it != mRays.end(); ++ it)
	292	rays.push_back((*it).mRay);
	293	}
	294
[462]	295	VspKdViewCell *VspKdLeaf::GetViewCell()
[453]	296	{
	297	return mViewCell;
	298	}
	299
[462]	300	void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell)
	301	{
	302	mViewCell = viewCell;
	303	}
	304
	305
	306	void VspKdLeaf::UpdatePvsSize()
	307	{
[465]	308	if (!mValidPvs)
[462]	309	{
	310	Intersectable::NewMail();
	311	int pvsSize = 0;
[465]	312	for(RayInfoContainer::iterator ri = mRays.begin();
[462]	313	ri != mRays.end(); ++ ri)
	314	{
[465]	315	if ((*ri).mRay->IsActive())
[462]	316	{
	317	Intersectable *object;
	318	#if BIDIRECTIONAL_RAY
	319	object = (*ri).mRay->mOriginObject;
[465]	320
	321	if (object && !object->Mailed())
[462]	322	{
	323	++ pvsSize;
	324	object->Mail();
	325	}
	326	#endif
	327	object = (*ri).mRay->mTerminationObject;
[465]	328	if (object && !object->Mailed())
[462]	329	{
	330	++ pvsSize;
	331	object->Mail();
	332	}
	333	}
	334	}
	335
	336	mPvsSize = pvsSize;
	337	mValidPvs = true;
	338	}
	339	}
	340
[420]	341
[500]	342	/***************************************************************/
	343	/* class VspKdIntermediate implementation */
	344	/***************************************************************/
[420]	345
[500]	346
	347	VspKdIntermediate::VspKdIntermediate(VspKdInterior *p):
	348	VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
	349	{
	350	}
	351
	352
	353	VspKdIntermediate::~VspKdIntermediate()
	354	{
	355	DEL_PTR(mFront);
	356	DEL_PTR(mBack);
	357	}
	358
	359
	360	int VspKdIntermediate::Type() const
	361	{
	362	return EIntermediate;
	363	}
	364
	365
	366	VspKdLeaf *VspKdIntermediate::GetBack() const
	367	{
	368	return mBack;
	369	}
	370
	371
	372	VspKdLeaf *VspKdIntermediate::GetFront() const
	373	{
	374	return mFront;
	375	}
	376
	377
	378	void VspKdIntermediate::Print(ostream &s) const
	379	{
	380	s << endl << mSplitPlane << endl;
	381	}
	382
	383
	384	void VspKdIntermediate::SetupChildLinks(VspKdLeaf b, VspKdLeaf f)
	385	{
	386	mBack = b;
	387	mFront = f;
	388
	389	b->SetParent(this);
	390	f->SetParent(this);
	391	}
	392
	393
	394	int VspKdIntermediate::ComputeRayIntersection(const RayInfo &rayData, float &t)
	395	{
	396	return rayData.ComputeRayIntersection(mSplitPlane, t);
	397	}
	398
	399
	400	/*************************************************************/
	401	/* class VspKdTree implementation */
	402	/*************************************************************/
	403
	404
[482]	405	VspKdTree::VspKdTree(): mOnlyDrivingAxis(false)
[465]	406	{
[421]	407	environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
	408	environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
	409	environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
	410	environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
	411	environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
[422]	412	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
[421]	413
[472]	414	environment->GetIntValue("VspKdTree.Termination.missTolerance", mTermMissTolerance);
	415
[421]	416	mTermMinSize = sqr(mTermMinSize);
	417
[422]	418	environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
	419	environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
[465]	420
[422]	421	environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
	422	environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
[465]	423
[422]	424	environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
	425	environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
[408]	426
[465]	427	//environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
[462]	428
[472]	429	environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMergeMinViewCells);
	430	environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
[465]	431	environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
	432	MergeCandidate::sMaxPvsSize);
[462]	433
[485]	434	environment->GetBoolValue("VspKdTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[465]	435
[485]	436	//-- output
[423]	437	Debug << "======= vsp kd tree options ========" << endl;
	438	Debug << "max depth: "<< mTermMaxDepth << endl;
	439	Debug << "min pvs: "<< mTermMinPvs << endl;
	440	Debug << "min rays: "<< mTermMinRays << endl;
	441	Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
[473]	442	Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
	443	Debug << "min size: " << mTermMinSize << endl;
[423]	444
[485]	445	Debug << "split type: ";
	446
	447	//-- split type
	448	char sname[128];
	449	environment->GetStringValue("VspKdTree.splitType", sname);
	450	string name(sname);
	451
[409]	452	if (name.compare("regular") == 0)
[423]	453	{
[485]	454	Debug << "regular split" << endl;
[409]	455	splitType = ESplitRegular;
[423]	456	}
[409]	457	else
	458	{
	459	if (name.compare("heuristic") == 0)
[423]	460	{
[485]	461	Debug << "heuristic split" << endl;
[409]	462	splitType = ESplitHeuristic;
[423]	463	}
[465]	464	else
[409]	465	{
	466	cerr << "Invalid VspKdTree split type " << name << endl;
[408]	467	exit(1);
	468	}
[409]	469	}
[408]	470
[418]	471	mRoot = NULL;
[422]	472	mSplitCandidates = new vector<SortableEntry>;
[406]	473	}
	474
[408]	475
	476	VspKdTree::~VspKdTree()
[406]	477	{
[419]	478	DEL_PTR(mRoot);
[449]	479	DEL_PTR(mSplitCandidates);
[408]	480	}
[406]	481
[418]	482	void VspKdStatistics::Print(ostream &app) const
[408]	483	{
[426]	484	app << "===== VspKdTree statistics ===============\n";
[408]	485
[426]	486	app << "#N_RAYS ( Number of rays )\n"
	487	<< rays << endl;
[465]	488
[426]	489	app << "#N_INITPVS ( Initial PVS size )\n"
	490	<< initialPvsSize << endl;
[465]	491
[426]	492	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
[406]	493
[426]	494	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
[406]	495
[482]	496	app << "#N_SPLITS ( Number of splits in axes x y z\n";
[465]	497
[482]	498	for (int i = 0; i < 3; ++ i)
	499	app << splits[i] << " ";
[426]	500	app << endl;
[406]	501
[426]	502	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
	503	rayRefs << "\n";
[408]	504
[426]	505	app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" <<
	506	rayRefs / (double)rays << "\n";
[408]	507
[426]	508	app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" <<
	509	rayRefs / (double)Leaves() << "\n";
[408]	510
[426]	511	app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" <<
	512	maxRayRefs << "\n";
[408]	513
	514	// app << setprecision(4);
	515
[426]	516	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
	517	maxDepthNodes * 100 / (double)Leaves() << endl;
[408]	518
[426]	519	app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n" <<
	520	minPvsNodes * 100 / (double)Leaves() << endl;
[408]	521
[426]	522	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n" <<
	523	minRaysNodes * 100 / (double)Leaves() << endl;
	524
[408]	525	app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<<
[426]	526	minSizeNodes * 100 / (double)Leaves() << endl;
[408]	527
[426]	528	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n" <<
	529	maxRayContribNodes * 100 / (double)Leaves() << endl;
[408]	530
[482]	531	app << "#N_PMAXRCOSTLEAVES ( Percentage of leaves with maximal cost ratio )\n" <<
	532	maxCostNodes * 100 / (double)Leaves() << endl;
	533
[426]	534	app << "#N_ADDED_RAYREFS ( Number of dynamically added ray references )\n"<<
	535	addedRayRefs << endl;
[408]	536
[426]	537	app << "#N_REMOVED_RAYREFS ( Number of dynamically removed ray references )\n"<<
	538	removedRayRefs << endl;
[408]	539
[426]	540	// app << setprecision(4);
[408]	541
[462]	542	app << "#N_( Maximal PVS size / leaf)\n"
[426]	543	<< maxPvsSize << endl;
[408]	544
[482]	545	app << "#N_( Average PVS size / leaf)\n"
	546	<< (double) accPvsSize / (double)Leaves() << endl;
	547
[426]	548	app << "#N_CTIME ( Construction time [s] )\n"
	549	<< Time() << " \n";
[408]	550
[426]	551	app << "===== END OF VspKdTree statistics ==========\n";
[406]	552	}
	553
[408]	554
[463]	555	void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const
	556	{
	557	stack<VspKdNode *> nodeStack;
	558	nodeStack.push(mRoot);
	559
	560	ViewCell::NewMail();
	561
[465]	562	while (!nodeStack.empty())
[463]	563	{
	564	VspKdNode *node = nodeStack.top();
	565	nodeStack.pop();
	566
[465]	567	if (node->IsLeaf())
[463]	568	{
	569	ViewCell viewCell = dynamic_cast<VspKdLeaf >(node)->mViewCell;
	570
[465]	571	if (!viewCell->Mailed())
[463]	572	{
	573	viewCell->Mail();
	574	viewCells.push_back(viewCell);
	575	}
	576	}
[465]	577	else
[463]	578	{
	579	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
	580
	581	nodeStack.push(interior->GetFront());
	582	nodeStack.push(interior->GetBack());
	583	}
	584	}
[408]	585	}
[406]	586
[462]	587	void VspKdTree::Construct(const VssRayContainer &rays,
	588	AxisAlignedBox3 *forcedBoundingBox)
[452]	589	{
[414]	590	mStat.Start();
[465]	591
[422]	592	mMaxMemory = mMaxStaticMemory;
[419]	593	DEL_PTR(mRoot);
[408]	594
[462]	595	mRoot = new VspKdLeaf(NULL, (int)rays.size());
[408]	596
[423]	597	// first construct a leaf that will get subdivided
[462]	598	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(mRoot);
[465]	599
[414]	600	mStat.nodes = 1;
[448]	601	mBox.Initialize();
[452]	602
[448]	603	//-- compute bounding box
[409]	604	if (forcedBoundingBox)
[419]	605	mBox = *forcedBoundingBox;
[448]	606	else
	607	for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
	608	{
[452]	609	if ((*ri)->mOriginObject)
	610	mBox.Include((*ri)->GetOrigin());
	611	if ((*ri)->mTerminationObject)
[465]	612	mBox.Include((*ri)->GetTermination());
[448]	613	}
[408]	614
[422]	615	Debug << "bbox = " << mBox << endl;
[448]	616
	617	for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
	618	{
	619	//leaf->AddRay(RayInfo(*ri));
[463]	620	VssRay ray = ri;
	621	float minT, maxT;
[482]	622
	623	// TODO: not very efficient to implictly cast between rays types!
[463]	624	if (mBox.GetRaySegment(*ray, minT, maxT))
	625	{
	626	float len = ray->Length();
[465]	627
	628	if (!len)
[463]	629	len = Limits::Small;
[465]	630
	631	leaf->AddRay(RayInfo(ray, minT / len, maxT / len));
[448]	632	}
	633	}
[465]	634
[420]	635	mStat.rays = (int)leaf->mRays.size();
[408]	636	leaf->UpdatePvsSize();
[465]	637
[414]	638	mStat.initialPvsSize = leaf->GetPvsSize();
[465]	639
[409]	640	// Subdivide();
[419]	641	mRoot = Subdivide(TraversalData(leaf, mBox, 0));
[408]	642
[465]	643	if (mSplitCandidates)
[409]	644	{
[422]	645	// force release of this vector
	646	delete mSplitCandidates;
	647	mSplitCandidates = new vector<SortableEntry>;
[409]	648	}
[465]	649
[414]	650	mStat.Stop();
[408]	651
[414]	652	mStat.Print(cout);
[423]	653	Debug << "#Total memory=" << GetMemUsage() << endl;
[408]	654	}
	655
	656
	657
[462]	658	VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata)
[408]	659	{
[462]	660	VspKdNode *result = NULL;
[408]	661
[409]	662	priority_queue<TraversalData> tStack;
[423]	663	//stack<TraversalData> tStack;
[465]	664
[409]	665	tStack.push(tdata);
[406]	666
[409]	667	AxisAlignedBox3 backBox;
	668	AxisAlignedBox3 frontBox;
[465]	669
[408]	670	int lastMem = 0;
[423]	671
[465]	672	while (!tStack.empty())
[409]	673	{
[408]	674	float mem = GetMemUsage();
[465]	675
	676	if (lastMem / 10 != ((int)mem) / 10)
[409]	677	{
[425]	678	Debug << mem << " MB" << endl;
[408]	679	}
	680	lastMem = (int)mem;
[465]	681
	682	if (1 && mem > mMaxMemory)
[409]	683	{
[423]	684	Debug << "memory limit reached: " << mem << endl;
[409]	685	// count statistics on unprocessed leafs
[465]	686	while (!tStack.empty())
[409]	687	{
[408]	688	EvaluateLeafStats(tStack.top());
	689	tStack.pop();
[409]	690	}
	691	break;
	692	}
[465]	693
[409]	694	TraversalData data = tStack.top();
[465]	695	tStack.pop();
	696
[472]	697	VspKdNode node = SubdivideNode(dynamic_cast<VspKdLeaf >(data.mNode),
	698	data.mBox, backBox, frontBox);
[409]	699	if (result == NULL)
	700	result = node;
[465]	701
	702	if (!node->IsLeaf())
[409]	703	{
[462]	704	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
[408]	705
[409]	706	// push the children on the stack
[419]	707	tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1));
	708	tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1));
[465]	709	}
	710	else
[409]	711	{
	712	EvaluateLeafStats(data);
	713	}
	714	}
	715
	716	return result;
[408]	717	}
[406]	718
[408]	719
	720	// returns selected plane for subdivision
[462]	721	int VspKdTree::SelectPlane(VspKdLeaf *leaf,
[424]	722	const AxisAlignedBox3 &box,
	723	float &position,
	724	int &raysBack,
	725	int &raysFront,
	726	int &pvsBack,
	727	int &pvsFront)
[408]	728	{
[428]	729	int axis = 0;
	730	float costRatio = 0;
[465]	731
	732	if (splitType == ESplitRegular)
[422]	733	{
[408]	734	costRatio = BestCostRatioRegular(leaf,
[480]	735	box,
[410]	736	axis,
	737	position,
	738	raysBack,
	739	raysFront,
	740	pvsBack,
	741	pvsFront);
[465]	742	}
[423]	743	else if (splitType == ESplitHeuristic)
[410]	744	{
[472]	745	costRatio = BestCostRatioHeuristic(leaf,
[480]	746	box,
[472]	747	axis,
	748	position,
	749	raysBack,
	750	raysFront,
	751	pvsBack,
	752	pvsFront);
[423]	753	}
[465]	754	else
[423]	755	{
	756	cerr << "VspKdTree: Unknown split heuristics\n";
	757	exit(1);
	758	}
[408]	759
[465]	760	if (costRatio > mTermMaxCostRatio)
[410]	761	{
[482]	762	//Debug << "Too big cost ratio " << costRatio << endl;
	763	++ leaf->mMaxCostMisses;
	764	if (leaf->mMaxCostMisses > mTermMissTolerance)
	765	{
	766	++ mStat.maxCostNodes;
	767	return -1;
	768	}
[408]	769	}
	770
[428]	771	if (0)
[465]	772	Debug << "pvs=" << leaf->mPvsSize
	773	<< " rays=" << (int)leaf->mRays.size()
	774	<< " rc=" << leaf->GetAvgRayContribution()
[428]	775	<< " axis=" << axis << endl;
[465]	776
[408]	777	return axis;
[406]	778	}
	779
	780
[465]	781
[462]	782	float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
[480]	783	const AxisAlignedBox3 &box,
[425]	784	const int axis,
	785	const float position,
	786	int &raysBack,
	787	int &raysFront,
	788	int &pvsBack,
	789	int &pvsFront)
[406]	790	{
[408]	791	raysBack = 0;
	792	raysFront = 0;
	793	pvsFront = 0;
	794	pvsBack = 0;
	795
	796	Intersectable::NewMail(3);
[465]	797
[408]	798	// eval pvs size
[482]	799	const int pvsSize = leaf->GetPvsSize();
[408]	800
[419]	801	// this is the main ray classification loop!
[480]	802	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
[463]	803	ri != leaf->mRays.end(); ++ ri)
[480]	804	{
	805	if (!(*ri).mRay->IsActive())
	806	continue;
[465]	807
[480]	808	// determine the side of this ray with respect to the plane
	809	float t;
	810	int side = (*ri).ComputeRayIntersection(axis, position, t);
	811
[419]	812	if (side <= 0)
	813	++ raysBack;
[465]	814
[419]	815	if (side >= 0)
	816	++ raysFront;
[465]	817
[419]	818	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
[465]	819	}
[408]	820
[482]	821	//-- only one of these options should be one
	822
	823	if (0) //-- only pvs
[425]	824	{
[428]	825	const float sum = float(pvsBack + pvsFront);
[482]	826	const float oldCost = (float)pvsSize;
[425]	827
	828	return sum / oldCost;
	829	}
[482]	830
	831	//-- pvs + probability heuristics
	832	float pBack, pFront, pOverall;
	833
	834	if (0)
[428]	835	{
[482]	836	// box length substitute for probability
	837	const float minBox = box.Min(axis);
	838	const float maxBox = box.Max(axis);
[480]	839
[482]	840	pBack = position - minBox;
	841	pFront = maxBox - position;
	842	pOverall = maxBox - minBox;
	843	}
[465]	844
[482]	845	if (1) //-- area substitute for probability
	846	{
[495]	847	pOverall = box.SurfaceArea();
	848
[482]	849	const bool useMidSplit = true;
[495]	850	//const bool useMidSplit = false;
	851
[482]	852	if (!useMidSplit)
	853	{
	854	Vector3 pos = box.Max(); pos[axis] = position;
	855	pBack = AxisAlignedBox3(box.Min(), pos).SurfaceArea();
[480]	856
[482]	857	pos = box.Min(); pos[axis] = position;
	858	pFront = AxisAlignedBox3(pos, box.Max()).SurfaceArea();
	859	}
	860	else
	861	{
	862	//-- simplified computation for mid split
	863	const int axis2 = (axis + 1) % 3;
	864	const int axis3 = (axis + 2) % 3;
[480]	865
[482]	866	const float faceArea =
	867	(box.Max(axis2) - box.Min(axis2)) *
	868	(box.Max(axis3) - box.Min(axis3));
[408]	869
[482]	870	pBack = pFront = pOverall * 0.5f + faceArea;
	871	}
	872	}
[465]	873
[482]	874	//-- ray density substitute for probability
[483]	875	if (0)
[482]	876	{
	877	pBack = (float)raysBack;
	878	pFront = (float)raysFront;
	879	pOverall = (float)leaf->mRays.size();
	880	}
[465]	881
[482]	882	//Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
	883	//Debug << pFront << " " << pBack << " " << pOverall << endl;
	884
	885	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
	886	const float newCost = pvsBack * pBack + pvsFront * pFront;
	887	// float oldCost = leaf->mRays.size();
	888	const float oldCost = (float)pvsSize * pOverall;
	889
	890	return (mCtDivCi + newCost) / oldCost;
[406]	891	}
	892
[491]	893
[462]	894	float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf,
[480]	895	const AxisAlignedBox3 &box,
[422]	896	int &axis,
	897	float &position,
	898	int &raysBack,
	899	int &raysFront,
	900	int &pvsBack,
	901	int &pvsFront)
[408]	902	{
[422]	903	int nRaysBack[3], nRaysFront[3];
	904	int nPvsBack[3], nPvsFront[3];
	905
	906	float nPosition[3];
	907	float nCostRatio[3];
[408]	908	int bestAxis = -1;
[465]	909
[480]	910	//AxisAlignedBox3 sBox = GetBBox(leaf);
	911	const int sAxis = box.Size().DrivingAxis();
[408]	912
[465]	913	for (axis = 0; axis < 3; ++ axis)
[410]	914	{
[465]	915	if (!mOnlyDrivingAxis \|\| axis == sAxis)
[410]	916	{
[465]	917
[480]	918	nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
[465]	919
[408]	920	nCostRatio[axis] = EvalCostRatio(leaf,
[480]	921	box,
[410]	922	axis,
	923	nPosition[axis],
	924	nRaysBack[axis],
	925	nRaysFront[axis],
	926	nPvsBack[axis],
	927	nPvsFront[axis]);
	928	if (bestAxis == -1)
[452]	929	{
[408]	930	bestAxis = axis;
[452]	931	}
	932	else if (nCostRatio[axis] < nCostRatio[bestAxis])
	933	{
[465]	934	/*Debug << "pvs front " << nPvsBack[axis]
[452]	935	<< " pvs back " << nPvsFront[axis]
	936	<< " overall pvs " << leaf->GetPvsSize() << endl;*/
	937	bestAxis = axis;
	938	}
[465]	939
[408]	940	}
	941	}
	942
[428]	943	//-- assign best axis
[408]	944	axis = bestAxis;
	945	position = nPosition[bestAxis];
	946
	947	raysBack = nRaysBack[bestAxis];
	948	raysFront = nRaysFront[bestAxis];
	949
	950	pvsBack = nPvsBack[bestAxis];
	951	pvsFront = nPvsFront[bestAxis];
[465]	952
[408]	953	return nCostRatio[bestAxis];
	954	}
	955
[462]	956	float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf,
[480]	957	const AxisAlignedBox3 &box,
[410]	958	int &axis,
	959	float &position,
	960	int &raysBack,
	961	int &raysFront,
	962	int &pvsBack,
	963	int &pvsFront)
[406]	964	{
[480]	965	//AxisAlignedBox3 box = GetBBox(leaf);
[408]	966	// AxisAlignedBox3 dirBox = GetDirBBox(node);
[465]	967
[408]	968	axis = box.Size().DrivingAxis();
[465]	969
[408]	970	SortSplitCandidates(leaf, axis);
[465]	971
[408]	972	// go through the lists, count the number of objects left and right
	973	// and evaluate the following cost funcion:
	974	// C = ct_div_ci + (qlrl + qrrr)/queries
[465]	975
[420]	976	int rl = 0, rr = (int)leaf->mRays.size();
	977	int pl = 0, pr = leaf->GetPvsSize();
[424]	978
[408]	979	float minBox = box.Min(axis);
	980	float maxBox = box.Max(axis);
	981	float sizeBox = maxBox - minBox;
[465]	982
[419]	983	float minBand = minBox + 0.1f*(maxBox - minBox);
	984	float maxBand = minBox + 0.9f*(maxBox - minBox);
[465]	985
[408]	986	float sum = rr*sizeBox;
[411]	987	float minSum = 1e20f;
[465]	988
[408]	989	Intersectable::NewMail();
[424]	990
[408]	991	// set all object as belonging to the fron pvs
[420]	992	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
[424]	993	ri != leaf->mRays.end(); ++ ri)
[410]	994	{
	995	if ((*ri).mRay->IsActive())
	996	{
[408]	997	Intersectable object = (ri).mRay->mTerminationObject;
[465]	998
[408]	999	if (object)
[465]	1000	if (!object->Mailed())
[410]	1001	{
[408]	1002	object->Mail();
	1003	object->mCounter = 1;
[465]	1004	}
[410]	1005	else
	1006	++ object->mCounter;
[408]	1007	}
[410]	1008	}
[465]	1009
[408]	1010	Intersectable::NewMail();
[465]	1011
[422]	1012	for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
[465]	1013	ci < mSplitCandidates->end(); ++ ci)
[410]	1014	{
[408]	1015	VssRay *ray;
[465]	1016
	1017	switch ((*ci).type)
[410]	1018	{
[465]	1019	case SortableEntry::ERayMin:
[410]	1020	{
	1021	++ rl;
[482]	1022	ray = (*ci).ray;
[410]	1023	Intersectable *object = ray->mTerminationObject;
[465]	1024	if (object && !object->Mailed())
[410]	1025	{
	1026	object->Mail();
	1027	++ pl;
	1028	}
	1029	break;
	1030	}
[465]	1031	case SortableEntry::ERayMax:
[410]	1032	{
	1033	-- rr;
[465]	1034
[482]	1035	ray = (*ci).ray;
[410]	1036	Intersectable *object = ray->mTerminationObject;
[465]	1037
[410]	1038	if (object)
	1039	{
	1040	if (-- object->mCounter == 0)
	1041	-- pr;
	1042	}
[465]	1043
[410]	1044	break;
	1045	}
[408]	1046	}
[465]	1047
	1048	if ((ci).value > minBand && (ci).value < maxBand)
[410]	1049	{
[408]	1050	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
[465]	1051
[410]	1052	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
	1053	// cout<<"cost= "<<sum<<endl;
[465]	1054
	1055	if (sum < minSum)
[410]	1056	{
[408]	1057	minSum = sum;
	1058	position = (*ci).value;
[465]	1059
[408]	1060	raysBack = rl;
	1061	raysFront = rr;
[465]	1062
[408]	1063	pvsBack = pl;
	1064	pvsFront = pr;
[465]	1065
[410]	1066	}
	1067	}
	1068	}
	1069
[419]	1070	float oldCost = (float)leaf->GetPvsSize();
[422]	1071	float newCost = mCtDivCi + minSum / sizeBox;
[410]	1072	float ratio = newCost / oldCost;
[465]	1073
[422]	1074	//Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
	1075	// <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
[465]	1076
[408]	1077	return ratio;
	1078	}
	1079
[462]	1080	void VspKdTree::SortSplitCandidates(VspKdLeaf *node,
[410]	1081	const int axis)
[408]	1082	{
[422]	1083	mSplitCandidates->clear();
[465]	1084
[420]	1085	int requestedSize = 2 * (int)(node->mRays.size());
[410]	1086	// creates a sorted split candidates array
[422]	1087	if (mSplitCandidates->capacity() > 500000 &&
[465]	1088	requestedSize < (int)(mSplitCandidates->capacity()/10) )
[410]	1089	{
[449]	1090	DEL_PTR(mSplitCandidates);
[422]	1091	mSplitCandidates = new vector<SortableEntry>;
[410]	1092	}
[465]	1093
[422]	1094	mSplitCandidates->reserve(requestedSize);
[408]	1095
[465]	1096	// insert all queries
[420]	1097	for(RayInfoContainer::const_iterator ri = node->mRays.begin();
[465]	1098	ri < node->mRays.end(); ++ ri)
[410]	1099	{
	1100	bool positive = (*ri).mRay->HasPosDir(axis);
[465]	1101	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
[482]	1102	(ri).ExtrapOrigin(axis), (ri).mRay));
[465]	1103
[422]	1104	mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
[482]	1105	(ri).ExtrapTermination(axis), (ri).mRay));
[410]	1106	}
[465]	1107
[422]	1108	stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
[406]	1109	}
	1110
[408]	1111
[410]	1112	void VspKdTree::EvaluateLeafStats(const TraversalData &data)
[406]	1113	{
[410]	1114	// the node became a leaf -> evaluate stats for leafs
[462]	1115	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(data.mNode);
[408]	1116
[426]	1117	if (leaf->GetPvsSize() > mStat.maxPvsSize)
	1118	mStat.maxPvsSize = leaf->GetPvsSize();
	1119
	1120	if ((int)(leaf->mRays.size()) > mStat.maxRayRefs)
	1121	mStat.maxRayRefs = (int)leaf->mRays.size();
	1122
[482]	1123	mStat.rays += (int)leaf->mRays.size();
[426]	1124
[421]	1125	if (data.mDepth >= mTermMaxDepth)
[413]	1126	++ mStat.maxDepthNodes;
[465]	1127
[421]	1128	if (leaf->GetPvsSize() < mTermMinPvs)
[413]	1129	++ mStat.minPvsNodes;
[408]	1130
[482]	1131	mStat.accPvsSize += leaf->GetPvsSize();
	1132
[426]	1133	if ((int)leaf->GetRays().size() < mTermMinRays)
[413]	1134	++ mStat.minRaysNodes;
[408]	1135
[426]	1136	if (leaf->GetAvgRayContribution() > mTermMaxRayContribution)
[413]	1137	++ mStat.maxRayContribNodes;
[465]	1138
	1139	if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)
[413]	1140	++ mStat.minSizeNodes;
[408]	1141	}
	1142
	1143
[465]	1144	inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf,
[421]	1145	const AxisAlignedBox3 &box) const
	1146	{
[465]	1147	return ((leaf->GetPvsSize() < mTermMinPvs) \|\|
[426]	1148	(leaf->mRays.size() < mTermMinRays) \|\|
[482]	1149	(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) \|\|
[465]	1150	(leaf->mDepth >= mTermMaxDepth) \|\|
[423]	1151	(SqrMagnitude(box.Size()) <= mTermMinSize));
[421]	1152	}
[408]	1153
[421]	1154
[462]	1155	VspKdNode VspKdTree::SubdivideNode(VspKdLeaf leaf,
[472]	1156	const AxisAlignedBox3 &box,
	1157	AxisAlignedBox3 &backBBox,
	1158	AxisAlignedBox3 &frontBBox)
[408]	1159	{
[421]	1160	if (TerminationCriteriaMet(leaf, box))
[410]	1161	{
[465]	1162	if (1 && leaf->mDepth >= mTermMaxDepth)
[422]	1163	{
[428]	1164	Debug << "Warning: max depth reached depth=" << (int)leaf->mDepth<<" rays=" << (int)leaf->mRays.size() << endl;
	1165	Debug << "Bbox: " << GetBBox(leaf) << endl;
[408]	1166	}
[428]	1167	//Debug << "depth: " << (int)leaf->mDepth << " pvs: " << leaf->GetPvsSize() << " rays: " << leaf->mRays.size() << endl;
[465]	1168
[408]	1169	return leaf;
	1170	}
[465]	1171
[408]	1172	float position;
	1173	// first count ray sides
[410]	1174	int raysBack;
	1175	int raysFront;
[408]	1176	int pvsBack;
	1177	int pvsFront;
[465]	1178
[410]	1179	// select subdivision axis
[425]	1180	const int axis = SelectPlane(leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
[426]	1181	//Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" << pvsFront << endl;
[408]	1182
[465]	1183	if (axis == -1)
[482]	1184	return leaf;
	1185
[413]	1186	mStat.nodes += 2;
[482]	1187	++ mStat.splits[axis];
[408]	1188
[410]	1189	// add the new nodes to the tree
[500]	1190	VspKdInterior *node =
	1191	new VspKdInterior(dynamic_cast<VspKdInterior *>(leaf->mParent));
[406]	1192
[419]	1193	node->mAxis = axis;
	1194	node->mPosition = position;
	1195	node->mBox = box;
[465]	1196
[410]	1197	backBBox = box;
	1198	frontBBox = box;
[406]	1199
[482]	1200	VspKdLeaf *back = new VspKdLeaf(node, raysBack, leaf->GetMaxCostMisses());
[408]	1201	back->SetPvsSize(pvsBack);
[482]	1202	VspKdLeaf *front = new VspKdLeaf(node, raysFront, leaf->GetMaxCostMisses());
[408]	1203	front->SetPvsSize(pvsFront);
[406]	1204
[410]	1205	// replace a link from node's parent
[419]	1206	if (leaf->mParent)
[500]	1207	{
	1208	VspKdInterior parent = dynamic_cast<VspKdInterior >(leaf->mParent);
	1209	parent->ReplaceChildLink(leaf, node);
	1210	}
[501]	1211
[410]	1212	// and setup child links
	1213	node->SetupChildLinks(back, front);
[465]	1214
	1215	if (axis <= VspKdNode::SPLIT_Z)
[410]	1216	{
[408]	1217	backBBox.SetMax(axis, position);
[410]	1218	frontBBox.SetMin(axis, position);
[465]	1219
[420]	1220	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
[465]	1221	ri != leaf->mRays.end(); ++ ri)
[410]	1222	{
[465]	1223	if ((*ri).mRay->IsActive())
[410]	1224	{
[408]	1225	// first unref ray from the former leaf
	1226	(*ri).mRay->Unref();
[463]	1227	float t;
[408]	1228	// determine the side of this ray with respect to the plane
[463]	1229	int side = node->ComputeRayIntersection(*ri, t);
[408]	1230
[465]	1231	if (side == 0)
[410]	1232	{
[465]	1233	if ((*ri).mRay->HasPosDir(axis))
[410]	1234	{
[420]	1235	back->AddRay(RayInfo((*ri).mRay,
	1236	(*ri).mMinT,
[463]	1237	t));
[420]	1238	front->AddRay(RayInfo((*ri).mRay,
[463]	1239	t,
[420]	1240	(*ri).mMaxT));
[465]	1241	}
	1242	else
[410]	1243	{
[420]	1244	back->AddRay(RayInfo((*ri).mRay,
[463]	1245	t,
[420]	1246	(*ri).mMaxT));
	1247	front->AddRay(RayInfo((*ri).mRay,
	1248	(*ri).mMinT,
[463]	1249	t));
[408]	1250	}
[465]	1251	}
[410]	1252	else
[465]	1253	if (side == 1)
[408]	1254	front->AddRay(*ri);
	1255	else
	1256	back->AddRay(*ri);
[410]	1257	} else
[408]	1258	(*ri).mRay->Unref();
[410]	1259	}
[465]	1260	}
	1261	else
[410]	1262	{
	1263	// rays front/back
[465]	1264
[420]	1265	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
[465]	1266	ri != leaf->mRays.end(); ++ ri)
[410]	1267	{
[465]	1268	if ((*ri).mRay->IsActive())
[410]	1269	{
[408]	1270	// first unref ray from the former leaf
	1271	(*ri).mRay->Unref();
	1272
	1273	int side;
	1274	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
	1275	side = 1;
	1276	else
	1277	side = -1;
[465]	1278
[408]	1279	if (side == 1)
	1280	front->AddRay(*ri);
	1281	else
[465]	1282	back->AddRay(*ri);
	1283	}
[410]	1284	else
[408]	1285	(*ri).mRay->Unref();
[410]	1286	}
	1287	}
[465]	1288
[410]	1289	// update stats
[420]	1290	mStat.rayRefs -= (int)leaf->mRays.size();
[414]	1291	mStat.rayRefs += raysBack + raysFront;
[408]	1292
[420]	1293	DEL_PTR(leaf);
	1294
[410]	1295	return node;
[406]	1296	}
	1297
[410]	1298	int VspKdTree::ReleaseMemory(const int time)
	1299	{
[462]	1300	stack<VspKdNode *> tstack;
[406]	1301
[410]	1302	// find a node in the tree which subtree will be collapsed
[422]	1303	int maxAccessTime = time - mAccessTimeThreshold;
[420]	1304	int released = 0;
[406]	1305
[419]	1306	tstack.push(mRoot);
[406]	1307
[423]	1308	while (!tstack.empty())
[410]	1309	{
[462]	1310	VspKdNode *node = tstack.top();
[410]	1311	tstack.pop();
[465]	1312
	1313	if (!node->IsLeaf())
[410]	1314	{
[462]	1315	VspKdInterior in = dynamic_cast<VspKdInterior >(node);
[410]	1316	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
[465]	1317	if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime)
[410]	1318	{
	1319	released = CollapseSubtree(node, time);
	1320	break;
	1321	}
[465]	1322	if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())
[410]	1323	{
[419]	1324	tstack.push(in->GetFront());
	1325	tstack.push(in->GetBack());
[465]	1326	}
	1327	else
[410]	1328	{
[419]	1329	tstack.push(in->GetBack());
	1330	tstack.push(in->GetFront());
[410]	1331	}
	1332	}
	1333	}
[406]	1334
[465]	1335	while (tstack.empty())
[410]	1336	{
	1337	// could find node to collaps...
	1338	// cout<<"Could not find a node to release "<<endl;
	1339	break;
	1340	}
[465]	1341
[410]	1342	return released;
[408]	1343	}
[406]	1344
	1345
[462]	1346	VspKdNode VspKdTree::SubdivideLeaf(VspKdLeaf leaf,
[410]	1347	const float sizeThreshold)
[408]	1348	{
[462]	1349	VspKdNode *node = leaf;
[406]	1350
[410]	1351	AxisAlignedBox3 leafBBox = GetBBox(leaf);
[406]	1352
[408]	1353	static int pass = 0;
[410]	1354	++ pass;
[465]	1355
[410]	1356	// check if we should perform a dynamic subdivision of the leaf
[420]	1357	if (// leaf->mRays.size() > (unsigned)termMinCost &&
[465]	1358	(leaf->GetPvsSize() >= mTermMinPvs) &&
[410]	1359	(SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
	1360	{
[423]	1361	// memory check and release
[465]	1362	if (GetMemUsage() > mMaxTotalMemory)
[410]	1363	ReleaseMemory(pass);
[465]	1364
[410]	1365	AxisAlignedBox3 backBBox, frontBBox;
[406]	1366
[410]	1367	// subdivide the node
	1368	node = SubdivideNode(leaf, leafBBox, backBBox, frontBBox);
	1369	}
	1370	return node;
[406]	1371	}
	1372
	1373
	1374
[423]	1375	void VspKdTree::UpdateRays(VssRayContainer &remove,
	1376	VssRayContainer &add)
[406]	1377	{
[462]	1378	VspKdLeaf::NewMail();
[406]	1379
[410]	1380	// schedule rays for removal
	1381	for(VssRayContainer::const_iterator ri = remove.begin();
[465]	1382	ri != remove.end(); ++ ri)
[410]	1383	{
[465]	1384	(*ri)->ScheduleForRemoval();
[410]	1385	}
[406]	1386
[410]	1387	int inactive = 0;
[406]	1388
[465]	1389	for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)
[410]	1390	{
	1391	if ((*ri)->ScheduledForRemoval())
	1392	// RemoveRay(*ri, NULL, false);
	1393	// !!! BUG - with true it does not work correctly - aggreated delete
	1394	RemoveRay(*ri, NULL, true);
	1395	else
	1396	++ inactive;
	1397	}
[406]	1398
[410]	1399	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
[465]	1400	for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)
[410]	1401	{
	1402	AddRay(*ri);
	1403	}
[406]	1404	}
	1405
	1406
[410]	1407	void VspKdTree::RemoveRay(VssRay *ray,
[462]	1408	vector<VspKdLeaf > affectedLeaves,
[410]	1409	const bool removeAllScheduledRays)
[406]	1410	{
[410]	1411	stack<RayTraversalData> tstack;
[406]	1412
[420]	1413	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
[465]	1414
[410]	1415	RayTraversalData data;
[406]	1416
[410]	1417	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
[465]	1418	while (!tstack.empty())
[410]	1419	{
	1420	data = tstack.top();
	1421	tstack.pop();
[406]	1422
[465]	1423	if (!data.mNode->IsLeaf())
[410]	1424	{
	1425	// split the set of rays in two groups intersecting the
	1426	// two subtrees
	1427	TraverseInternalNode(data, tstack);
[465]	1428	}
	1429	else
[410]	1430	{
	1431	// remove the ray from the leaf
	1432	// find the ray in the leaf and swap it with the last ray...
[462]	1433	VspKdLeaf leaf = (VspKdLeaf )data.mNode;
[465]	1434
	1435	if (!leaf->Mailed())
[410]	1436	{
	1437	leaf->Mail();
[465]	1438
[410]	1439	if (affectedLeaves)
	1440	affectedLeaves->push_back(leaf);
[465]	1441
	1442	if (removeAllScheduledRays)
[410]	1443	{
[420]	1444	int tail = (int)leaf->mRays.size() - 1;
[406]	1445
[465]	1446	for (int i=0; i < (int)(leaf->mRays.size()); ++ i)
[410]	1447	{
[465]	1448	if (leaf->mRays[i].mRay->ScheduledForRemoval())
[410]	1449	{
	1450	// find a ray to replace it with
[465]	1451	while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())
[410]	1452	{
[414]	1453	++ mStat.removedRayRefs;
[420]	1454	leaf->mRays[tail].mRay->Unref();
	1455	leaf->mRays.pop_back();
[465]	1456
[410]	1457	-- tail;
	1458	}
[465]	1459
[410]	1460	if (tail < i)
	1461	break;
[465]	1462
[414]	1463	++ mStat.removedRayRefs;
[465]	1464
[420]	1465	leaf->mRays[i].mRay->Unref();
	1466	leaf->mRays[i] = leaf->mRays[tail];
	1467	leaf->mRays.pop_back();
[410]	1468	-- tail;
	1469	}
	1470	}
	1471	}
	1472	}
[465]	1473
[410]	1474	if (!removeAllScheduledRays)
[465]	1475	for (int i=0; i < (int)leaf->mRays.size(); i++)
[410]	1476	{
[465]	1477	if (leaf->mRays[i].mRay == ray)
[410]	1478	{
[414]	1479	++ mStat.removedRayRefs;
[410]	1480	ray->Unref();
[420]	1481	leaf->mRays[i] = leaf->mRays[leaf->mRays.size() - 1];
	1482	leaf->mRays.pop_back();
[410]	1483	// check this ray again
	1484	break;
	1485	}
	1486	}
	1487	}
[408]	1488	}
	1489
[465]	1490	if (ray->RefCount() != 0)
[410]	1491	{
	1492	cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
	1493	exit(1);
	1494	}
	1495
[406]	1496	}
	1497
[410]	1498	void VspKdTree::AddRay(VssRay *ray)
[406]	1499	{
[410]	1500	stack<RayTraversalData> tstack;
[465]	1501
[420]	1502	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
[465]	1503
[410]	1504	RayTraversalData data;
[465]	1505
	1506	while (!tstack.empty())
[410]	1507	{
	1508	data = tstack.top();
	1509	tstack.pop();
[406]	1510
[465]	1511	if (!data.mNode->IsLeaf())
[410]	1512	{
	1513	TraverseInternalNode(data, tstack);
[465]	1514	}
	1515	else
[410]	1516	{
	1517	// remove the ray from the leaf
[420]	1518	// find the ray in the leaf and swap it with the last ray
[462]	1519	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(data.mNode);
[423]	1520
[419]	1521	leaf->AddRay(data.mRayData);
[413]	1522	++ mStat.addedRayRefs;
[410]	1523	}
	1524	}
[406]	1525	}
	1526
[465]	1527	void VspKdTree::TraverseInternalNode(RayTraversalData &data,
[410]	1528	stack<RayTraversalData> &tstack)
[406]	1529	{
[462]	1530	VspKdInterior in = dynamic_cast<VspKdInterior >(data.mNode);
[465]	1531
	1532	if (in->mAxis <= VspKdNode::SPLIT_Z)
[410]	1533	{
	1534	// determine the side of this ray with respect to the plane
[485]	1535	float t;
	1536	const int side = in->ComputeRayIntersection(data.mRayData, t);
[465]	1537
	1538	if (side == 0)
[410]	1539	{
[465]	1540	if (data.mRayData.mRay->HasPosDir(in->mAxis))
[433]	1541	{
[465]	1542	tstack.push(RayTraversalData(in->GetBack(),
[463]	1543	RayInfo(data.mRayData.mRay, data.mRayData.mMinT, t)));
[465]	1544
[433]	1545	tstack.push(RayTraversalData(in->GetFront(),
[463]	1546	RayInfo(data.mRayData.mRay, t, data.mRayData.mMaxT)));
[465]	1547
	1548	}
	1549	else
[433]	1550	{
	1551	tstack.push(RayTraversalData(in->GetBack(),
	1552	RayInfo(data.mRayData.mRay,
[463]	1553	t,
[433]	1554	data.mRayData.mMaxT)));
	1555	tstack.push(RayTraversalData(in->GetFront(),
	1556	RayInfo(data.mRayData.mRay,
	1557	data.mRayData.mMinT,
[463]	1558	t)));
[433]	1559	}
[410]	1560	}
[433]	1561	else
	1562	if (side == 1)
	1563	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
	1564	else
	1565	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
[465]	1566	}
	1567	else
[410]	1568	{
	1569	// directional split
[419]	1570	if (data.mRayData.mRay->GetDirParametrization(in->mAxis - 3) > in->mPosition)
	1571	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
[408]	1572	else
[419]	1573	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
[410]	1574	}
[406]	1575	}
	1576
[408]	1577
[462]	1578	int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time)
[406]	1579	{
[410]	1580	// first count all rays in the subtree
	1581	// use mail 1 for this purpose
[462]	1582	stack<VspKdNode *> tstack;
[465]	1583
[410]	1584	int rayCount = 0;
	1585	int totalRayCount = 0;
	1586	int collapsedNodes = 0;
[408]	1587
	1588	#if DEBUG_COLLAPSE
[420]	1589	cout << "Collapsing subtree" << endl;
[428]	1590	cout << "accessTime=" << sroot->GetAccessTime() << endl;
[420]	1591	cout << "depth=" << (int)sroot->depth << endl;
[408]	1592	#endif
	1593
[410]	1594	// tstat.collapsedSubtrees++;
	1595	// tstat.collapseDepths += (int)sroot->depth;
	1596	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
	1597	tstack.push(sroot);
	1598	VssRay::NewMail();
[465]	1599
	1600	while (!tstack.empty())
[410]	1601	{
	1602	++ collapsedNodes;
[465]	1603
[462]	1604	VspKdNode *node = tstack.top();
[410]	1605	tstack.pop();
[465]	1606	if (node->IsLeaf())
[410]	1607	{
[462]	1608	VspKdLeaf leaf = (VspKdLeaf ) node;
[465]	1609
[420]	1610	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
[465]	1611	ri != leaf->mRays.end(); ++ ri)
[410]	1612	{
	1613	++ totalRayCount;
[465]	1614
	1615	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed())
[410]	1616	{
[408]	1617	(*ri).mRay->Mail();
[410]	1618	++ rayCount;
[408]	1619	}
[410]	1620	}
[465]	1621	}
	1622	else
[410]	1623	{
[472]	1624	tstack.push(dynamic_cast<VspKdInterior *>(node)->GetFront());
	1625	tstack.push(dynamic_cast<VspKdInterior *>(node)->GetBack());
[410]	1626	}
	1627	}
[465]	1628
[410]	1629	VssRay::NewMail();
[406]	1630
[410]	1631	// create a new node that will hold the rays
[462]	1632	VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
[465]	1633
[500]	1634	VspKdInterior *parent =
	1635	dynamic_cast<VspKdInterior *>(newLeaf->mParent);
	1636
	1637	if (parent)
[472]	1638	{
[500]	1639	parent->ReplaceChildLink(sroot, newLeaf);
[472]	1640	}
[410]	1641	tstack.push(sroot);
[406]	1642
[465]	1643	while (!tstack.empty())
[410]	1644	{
[462]	1645	VspKdNode *node = tstack.top();
[410]	1646	tstack.pop();
[408]	1647
[465]	1648	if (node->IsLeaf())
[410]	1649	{
[462]	1650	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
[408]	1651
[420]	1652	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
[465]	1653	ri != leaf->mRays.end(); ++ ri)
[410]	1654	{
[465]	1655	// unref this ray from the old node
	1656	if ((*ri).mRay->IsActive())
[410]	1657	{
[408]	1658	(*ri).mRay->Unref();
[465]	1659	if (!(*ri).mRay->Mailed())
[410]	1660	{
[408]	1661	(*ri).mRay->Mail();
	1662	newLeaf->AddRay(*ri);
	1663	}
[465]	1664	}
[410]	1665	else
[408]	1666	(*ri).mRay->Unref();
[410]	1667	}
[465]	1668	}
	1669	else
[410]	1670	{
[465]	1671	VspKdInterior *interior =
[462]	1672	dynamic_cast<VspKdInterior *>(node);
[419]	1673	tstack.push(interior->GetBack());
	1674	tstack.push(interior->GetFront());
[410]	1675	}
	1676	}
[465]	1677
[410]	1678	// delete the node and all its children
[420]	1679	DEL_PTR(sroot);
[465]	1680
[462]	1681	// for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
[420]	1682	// ri != newleaf->mRays.end(); ++ ri)
[410]	1683	// (*ri).ray->UnMail(2);
[408]	1684
	1685	#if DEBUG_COLLAPSE
[423]	1686	cout << "Total memory before=" << GetMemUsage() << endl;
[408]	1687	#endif
	1688
[414]	1689	mStat.nodes -= collapsedNodes - 1;
	1690	mStat.rayRefs -= totalRayCount - rayCount;
[465]	1691
[408]	1692	#if DEBUG_COLLAPSE
[410]	1693	cout << "collapsed nodes" << collapsedNodes << endl;
	1694	cout << "collapsed rays" << totalRayCount - rayCount << endl;
	1695	cout << "Total memory after=" << GetMemUsage() << endl;
	1696	cout << "================================" << endl;
[408]	1697	#endif
	1698
	1699	// tstat.collapsedNodes += collapsedNodes;
	1700	// tstat.collapsedRays += totalRayCount - rayCount;
[410]	1701	return totalRayCount - rayCount;
[406]	1702	}
	1703
[408]	1704
[462]	1705	int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const
[406]	1706	{
[462]	1707	stack<VspKdNode *> tstack;
[419]	1708	tstack.push(mRoot);
[408]	1709
	1710	Intersectable::NewMail();
	1711	int pvsSize = 0;
[465]	1712
	1713	while (!tstack.empty())
[410]	1714	{
[462]	1715	VspKdNode *node = tstack.top();
[410]	1716	tstack.pop();
[465]	1717
	1718	if (node->IsLeaf())
[410]	1719	{
[462]	1720	VspKdLeaf leaf = (VspKdLeaf )node;
[420]	1721	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
	1722	ri != leaf->mRays.end(); ++ ri)
[410]	1723	{
[465]	1724	if ((*ri).mRay->IsActive())
[410]	1725	{
[408]	1726	Intersectable *object;
	1727	#if BIDIRECTIONAL_RAY
	1728	object = (*ri).mRay->mOriginObject;
[465]	1729
	1730	if (object && !object->Mailed())
[410]	1731	{
	1732	++ pvsSize;
[408]	1733	object->Mail();
	1734	}
	1735	#endif
	1736	object = (*ri).mRay->mTerminationObject;
[465]	1737	if (object && !object->Mailed())
[410]	1738	{
	1739	++ pvsSize;
[408]	1740	object->Mail();
	1741	}
	1742	}
[465]	1743	}
[410]	1744	}
[465]	1745	else
[410]	1746	{
[462]	1747	VspKdInterior in = dynamic_cast<VspKdInterior >(node);
[465]	1748
	1749	if (in->mAxis < 3)
[410]	1750	{
[419]	1751	if (box.Max(in->mAxis) >= in->mPosition)
	1752	tstack.push(in->GetFront());
[465]	1753
[419]	1754	if (box.Min(in->mAxis) <= in->mPosition)
	1755	tstack.push(in->GetBack());
[465]	1756	}
	1757	else
[410]	1758	{
[408]	1759	// both nodes for directional splits
[419]	1760	tstack.push(in->GetFront());
	1761	tstack.push(in->GetBack());
[408]	1762	}
	1763	}
	1764	}
[410]	1765
[408]	1766	return pvsSize;
[406]	1767	}
	1768
[410]	1769	void VspKdTree::GetRayContributionStatistics(float &minRayContribution,
	1770	float &maxRayContribution,
	1771	float &avgRayContribution)
[406]	1772	{
[462]	1773	stack<VspKdNode *> tstack;
[419]	1774	tstack.push(mRoot);
[465]	1775
[408]	1776	minRayContribution = 1.0f;
	1777	maxRayContribution = 0.0f;
[410]	1778
[408]	1779	float sumRayContribution = 0.0f;
	1780	int leaves = 0;
[406]	1781
[465]	1782	while (!tstack.empty())
[410]	1783	{
[462]	1784	VspKdNode *node = tstack.top();
[410]	1785	tstack.pop();
[465]	1786	if (node->IsLeaf())
[410]	1787	{
[408]	1788	leaves++;
[462]	1789	VspKdLeaf leaf = (VspKdLeaf )node;
[408]	1790	float c = leaf->GetAvgRayContribution();
[410]	1791
[408]	1792	if (c > maxRayContribution)
	1793	maxRayContribution = c;
	1794	if (c < minRayContribution)
	1795	minRayContribution = c;
	1796	sumRayContribution += c;
[465]	1797
	1798	}
[482]	1799	else
	1800	{
[462]	1801	VspKdInterior in = (VspKdInterior )node;
[482]	1802
[419]	1803	tstack.push(in->GetFront());
	1804	tstack.push(in->GetBack());
[408]	1805	}
	1806	}
[465]	1807
[423]	1808	Debug << "sum=" << sumRayContribution << endl;
	1809	Debug << "leaves=" << leaves << endl;
	1810	avgRayContribution = sumRayContribution / (float)leaves;
[406]	1811	}
	1812
	1813
[410]	1814	int VspKdTree::GenerateRays(const float ratioPerLeaf,
	1815	SimpleRayContainer &rays)
[406]	1816	{
[462]	1817	stack<VspKdNode *> tstack;
[419]	1818	tstack.push(mRoot);
[465]	1819
	1820	while (!tstack.empty())
[410]	1821	{
[462]	1822	VspKdNode *node = tstack.top();
[410]	1823	tstack.pop();
[465]	1824
	1825	if (node->IsLeaf())
[410]	1826	{
[462]	1827	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
[423]	1828
[408]	1829	float c = leaf->GetAvgRayContribution();
[411]	1830	int num = (int)(c*ratioPerLeaf + 0.5);
[408]	1831	// cout<<num<<" ";
	1832
[465]	1833	for (int i=0; i < num; i++)
[410]	1834	{
[408]	1835	Vector3 origin = GetBBox(leaf).GetRandomPoint();
[419]	1836	/*Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
[408]	1837	Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
	1838	//cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
[419]	1839	rays.push_back(SimpleRay(origin, direction));*/
[408]	1840	}
[465]	1841
	1842	}
	1843	else
[410]	1844	{
[465]	1845	VspKdInterior *in =
[462]	1846	dynamic_cast<VspKdInterior *>(node);
[482]	1847
[419]	1848	tstack.push(in->GetFront());
	1849	tstack.push(in->GetBack());
[408]	1850	}
[406]	1851	}
	1852
[411]	1853	return (int)rays.size();
[406]	1854	}
	1855
	1856
[410]	1857	float VspKdTree::GetAvgPvsSize()
[406]	1858	{
[462]	1859	stack<VspKdNode *> tstack;
[419]	1860	tstack.push(mRoot);
[406]	1861
[408]	1862	int sumPvs = 0;
	1863	int leaves = 0;
[465]	1864
	1865	while (!tstack.empty())
[410]	1866	{
[462]	1867	VspKdNode *node = tstack.top();
[410]	1868	tstack.pop();
[465]	1869
	1870	if (node->IsLeaf())
[410]	1871	{
[462]	1872	VspKdLeaf leaf = (VspKdLeaf )node;
[408]	1873	// update pvs size
	1874	leaf->UpdatePvsSize();
	1875	sumPvs += leaf->GetPvsSize();
	1876	leaves++;
[465]	1877	}
	1878	else
[410]	1879	{
[462]	1880	VspKdInterior in = (VspKdInterior )node;
[482]	1881
[419]	1882	tstack.push(in->GetFront());
	1883	tstack.push(in->GetBack());
[406]	1884	}
	1885	}
[408]	1886
[410]	1887	return sumPvs / (float)leaves;
[418]	1888	}
	1889
[462]	1890	VspKdNode *VspKdTree::GetRoot() const
[418]	1891	{
	1892	return mRoot;
	1893	}
	1894
[462]	1895	AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
[418]	1896	{
[419]	1897	if (node->mParent == NULL)
	1898	return mBox;
[418]	1899
	1900	if (!node->IsLeaf())
[500]	1901	{
	1902	if (node->Type() == VspKdNode::EIntermediate)
	1903	return (dynamic_cast<VspKdInterior *>(node))->mBox;
	1904	else
	1905	return (dynamic_cast<VspKdIntermediate *>(node))->mBox;
	1906	}
[418]	1907
[500]	1908	VspKdInterior parent = dynamic_cast<VspKdInterior >(node->mParent);
[465]	1909
[500]	1910	if (parent->mAxis >= 3)
	1911	return parent->mBox;
	1912
	1913	AxisAlignedBox3 box(parent->mBox);
	1914	if (parent->GetFront() == node)
	1915	box.SetMin(parent->mAxis, parent->mPosition);
[418]	1916	else
[500]	1917	box.SetMax(parent->mAxis, parent->mPosition);
[419]	1918
	1919	return box;
[418]	1920	}
	1921
[465]	1922	int VspKdTree::GetRootPvsSize() const
[418]	1923	{
	1924	return GetPvsSize(mRoot, mBox);
	1925	}
[419]	1926
[465]	1927	const VspKdStatistics &VspKdTree::GetStatistics() const
[419]	1928	{
	1929	return mStat;
[420]	1930	}
	1931
	1932	void VspKdTree::AddRays(VssRayContainer &add)
	1933	{
	1934	VssRayContainer remove;
	1935	UpdateRays(remove, add);
	1936	}
[465]	1937
[420]	1938	// return memory usage in MB
[465]	1939	float VspKdTree::GetMemUsage() const
[420]	1940	{
[465]	1941	return
	1942	(sizeof(VspKdTree) +
[462]	1943	mStat.Leaves() * sizeof(VspKdLeaf) +
	1944	mStat.Interior() * sizeof(VspKdInterior) +
[420]	1945	mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
	1946	}
[465]	1947
	1948	float VspKdTree::GetRayMemUsage() const
[420]	1949	{
	1950	return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
[425]	1951	}
	1952
[482]	1953
[465]	1954	int VspKdTree::ComputePvsSize(VspKdNode *node,
[426]	1955	const RayInfoContainer &globalRays) const
[425]	1956	{
	1957	int pvsSize = 0;
	1958
	1959	const AxisAlignedBox3 box = GetBBox(node);
	1960
	1961	RayInfoContainer::const_iterator it, it_end = globalRays.end();
	1962
[495]	1963	Intersectable::NewMail();
[482]	1964
[426]	1965	// warning: implicit conversion from VssRay to Ray
[425]	1966	for (it = globalRays.begin(); it != globalRays.end(); ++ it)
[495]	1967	{
	1968	VssRay ray = (it).mRay;
[465]	1969
[495]	1970	// ray intersects node bounding box
	1971	if (box.GetMinMaxT(*ray, NULL, NULL))
	1972	{
	1973	if (ray->mTerminationObject && !ray->mTerminationObject->Mailed())
	1974	{
	1975	ray->mTerminationObject->Mail();
	1976	++ pvsSize;
	1977	}
	1978	}
	1979	}
[425]	1980	return pvsSize;
[428]	1981	}
	1982
[482]	1983
[462]	1984	void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const
[428]	1985	{
[462]	1986	stack<VspKdNode *> nodeStack;
[428]	1987	nodeStack.push(mRoot);
	1988
[465]	1989	while (!nodeStack.empty())
[428]	1990	{
[462]	1991	VspKdNode *node = nodeStack.top();
[465]	1992
[428]	1993	nodeStack.pop();
[465]	1994
	1995	if (node->IsLeaf())
[428]	1996	{
[462]	1997	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
[428]	1998	leaves.push_back(leaf);
[465]	1999	}
	2000	else
[428]	2001	{
[462]	2002	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
[428]	2003
[448]	2004	nodeStack.push(interior->GetBack());
	2005	nodeStack.push(interior->GetFront());
[428]	2006	}
	2007	}
[452]	2008	}
	2009
[503]	2010
[462]	2011	int VspKdTree::FindNeighbors(VspKdLeaf *n,
	2012	vector<VspKdLeaf *> &neighbors,
[452]	2013	bool onlyUnmailed)
	2014	{
[462]	2015	stack<VspKdNode *> nodeStack;
[465]	2016
[452]	2017	nodeStack.push(mRoot);
	2018
	2019	AxisAlignedBox3 box = GetBBox(n);
	2020
[465]	2021	while (!nodeStack.empty())
[452]	2022	{
[462]	2023	VspKdNode *node = nodeStack.top();
[452]	2024	nodeStack.pop();
	2025
[465]	2026	if (node->IsLeaf())
[452]	2027	{
[462]	2028	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
[452]	2029
[465]	2030	if (leaf != n && (!onlyUnmailed \|\| !leaf->Mailed()))
[452]	2031	neighbors.push_back(leaf);
[465]	2032	}
	2033	else
[452]	2034	{
[462]	2035	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
[452]	2036
	2037	if (interior->mPosition > box.Max(interior->mAxis))
	2038	nodeStack.push(interior->mBack);
	2039	else
	2040	{
	2041	if (interior->mPosition < box.Min(interior->mAxis))
	2042	nodeStack.push(interior->mFront);
[465]	2043	else
[452]	2044	{
	2045	// random decision
	2046	nodeStack.push(interior->mBack);
	2047	nodeStack.push(interior->mFront);
	2048	}
	2049	}
	2050	}
	2051	}
	2052
	2053	return (int)neighbors.size();
	2054	}
	2055
[462]	2056
	2057	void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
[452]	2058	{
[462]	2059	mViewCellsManager = vcm;
	2060	}
[452]	2061
[462]	2062
[468]	2063	int VspKdTree::CastLineSegment(const Vector3 &origin,
	2064	const Vector3 &termination,
	2065	vector<ViewCell *> &viewcells)
[462]	2066	{
	2067	int hits = 0;
[465]	2068
[468]	2069	float mint = 0.0f, maxt = 1.0f;
	2070	const Vector3 dir = termination - origin;
[465]	2071
[483]	2072	stack<LineTraversalData> tStack;
[462]	2073
	2074	Intersectable::NewMail();
	2075
[468]	2076	Vector3 entp = origin;
	2077	Vector3 extp = termination;
[465]	2078
[462]	2079	VspKdNode *node = mRoot;
	2080	VspKdNode *farChild;
	2081
	2082	float position;
	2083	int axis;
[465]	2084
	2085	while (1)
[462]	2086	{
[465]	2087	if (!node->IsLeaf())
[462]	2088	{
	2089	VspKdInterior in = dynamic_cast<VspKdInterior >(node);
	2090	position = in->mPosition;
	2091	axis = in->mAxis;
	2092
[465]	2093	if (entp[axis] <= position)
[462]	2094	{
[465]	2095	if (extp[axis] <= position)
[462]	2096	{
	2097	node = in->mBack;
	2098	// cases N1,N2,N3,P5,Z2,Z3
	2099	continue;
[465]	2100	} else
[462]	2101	{
	2102	// case N4
	2103	node = in->mBack;
	2104	farChild = in->mFront;
	2105	}
	2106	}
[465]	2107	else
[462]	2108	{
[465]	2109	if (position <= extp[axis])
[462]	2110	{
	2111	node = in->mFront;
	2112	// cases P1,P2,P3,N5,Z1
	2113	continue;
[465]	2114	}
	2115	else
[462]	2116	{
	2117	node = in->mFront;
	2118	farChild = in->mBack;
	2119	// case P4
	2120	}
	2121	}
	2122
	2123	// $$ modification 3.5.2004 - hints from Kamil Ghais
	2124	// case N4 or P4
[468]	2125	float tdist = (position - origin[axis]) / dir[axis];
[483]	2126	tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
[468]	2127	extp = origin + dir * tdist;
[462]	2128	maxt = tdist;
[465]	2129	}
	2130	else
[462]	2131	{
	2132	// compute intersection with all objects in this leaf
[468]	2133	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
	2134	ViewCell *vc = leaf->GetViewCell();
[465]	2135
[468]	2136	if (!vc->Mailed())
[462]	2137	{
[468]	2138	vc->Mail();
	2139	viewcells.push_back(vc);
[469]	2140	++ hits;
[462]	2141	}
[465]	2142
[485]	2143	if (0) //matt TODO: REMOVE LATER
[483]	2144	leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
	2145
[462]	2146	// get the next node from the stack
	2147	if (tStack.empty())
	2148	break;
[465]	2149
[462]	2150	entp = extp;
	2151	mint = maxt;
[468]	2152
[483]	2153	LineTraversalData &s = tStack.top();
[462]	2154	node = s.mNode;
	2155	extp = s.mExitPoint;
	2156	maxt = s.mMaxT;
	2157	tStack.pop();
	2158	}
	2159	}
[465]	2160
[462]	2161	return hits;
	2162	}
	2163
	2164
	2165	void VspKdTree::GenerateViewCell(VspKdLeaf *leaf)
	2166	{
	2167	RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end();
	2168
	2169	VspKdViewCell vc = dynamic_cast<VspKdViewCell >(mViewCellsManager->GenerateViewCell());
	2170	leaf->SetViewCell(vc);
	2171
[479]	2172	vc->SetVolume(GetBBox(leaf).GetVolume());
	2173	vc->SetArea(GetBBox(leaf).SurfaceArea());
	2174
[469]	2175	vc->mLeaves.push_back(leaf);
[462]	2176
	2177	for (it = leaf->GetRays().begin(); it != it_end; ++ it)
	2178	{
	2179	VssRay ray = (it).mRay;
	2180
[463]	2181	if (ray->mTerminationObject)
[466]	2182	vc->GetPvs().AddSample(ray->mTerminationObject);
[465]	2183
[463]	2184	if (ray->mOriginObject)
[466]	2185	vc->GetPvs().AddSample(ray->mOriginObject);
[462]	2186	}
	2187	}
	2188
	2189
[465]	2190	bool VspKdTree::MergeViewCells(VspKdLeaf l1, VspKdLeaf l2)
	2191	{
[472]	2192	//-- change pointer to view cells of all leaves associated
	2193	//-- with the previous view cells
[465]	2194	VspKdViewCell *fVc = l1->GetViewCell();
	2195	VspKdViewCell *bVc = l2->GetViewCell();
	2196
	2197	VspKdViewCell vc = dynamic_cast<VspKdViewCell >(
	2198	mViewCellsManager->MergeViewCells(fVc, bVc));
	2199
	2200	// if merge was unsuccessful
	2201	if (!vc) return false;
	2202
	2203	// set new size of view cell
[479]	2204	vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
[482]	2205	// new area
	2206	vc->SetArea(fVc->GetArea() + bVc->GetArea());
[465]	2207
[469]	2208	vector<VspKdLeaf *> fLeaves = fVc->mLeaves;
	2209	vector<VspKdLeaf *> bLeaves = bVc->mLeaves;
[465]	2210
	2211	vector<VspKdLeaf *>::const_iterator it;
	2212
	2213	//-- change view cells of all the other leaves the view cell belongs to
	2214	for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
	2215	{
	2216	(*it)->SetViewCell(vc);
[469]	2217	vc->mLeaves.push_back(*it);
[465]	2218	}
	2219
	2220	for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
	2221	{
	2222	(*it)->SetViewCell(vc);
[469]	2223	vc->mLeaves.push_back(*it);
[465]	2224	}
	2225
	2226	vc->Mail();
	2227
	2228	// clean up old view cells
	2229	DEL_PTR(fVc);
	2230	DEL_PTR(bVc);
	2231
[463]	2232	return true;
[462]	2233	}
	2234
[483]	2235	void VspKdTree::CollectMergeCandidates()
[462]	2236	{
[483]	2237	MergeCandidate::sOverallCost = 0;
[462]	2238	vector<VspKdLeaf *> leaves;
[465]	2239
[462]	2240	// collect the leaves, e.g., the "voxels" that will build the view cells
[452]	2241	CollectLeaves(leaves);
	2242
[462]	2243	VspKdLeaf::NewMail();
[452]	2244
[462]	2245	vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end();
[452]	2246
[462]	2247	// generate view cells
[452]	2248	for (it = leaves.begin(); it != it_end; ++ it)
[462]	2249	GenerateViewCell(*it);
	2250
	2251	// find merge candidates and push them into queue
	2252	for (it = leaves.begin(); it != it_end; ++ it)
[452]	2253	{
[462]	2254	VspKdLeaf leaf = it;
[485]	2255	ViewCell *vc = leaf->GetViewCell();
[462]	2256	// no leaf is part of two merge candidates
[485]	2257	leaf->Mail();
	2258	MergeCandidate::sOverallCost +=
	2259	vc->GetVolume() * vc->GetPvs().GetSize();
	2260	vector<VspKdLeaf *> neighbors;
	2261	FindNeighbors(leaf, neighbors, true);
[462]	2262
[485]	2263	vector<VspKdLeaf *>::const_iterator nit,
	2264	nit_end = neighbors.end();
[452]	2265
[485]	2266	for (nit = neighbors.begin(); nit != nit_end; ++ nit)
	2267	{
	2268	mMergeQueue.push(MergeCandidate(leaf, *nit));
[462]	2269	}
	2270	}
[483]	2271	}
[485]	2272	#if 0
[483]	2273	void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
	2274	{
	2275	MergeCandidate::sOverallCost = 0;
	2276
	2277	vector<VspKdIntersection>::const_iterator iit;
[485]	2278	map<BspLeaf , vector<BspLeaf> candidateMap;
[483]	2279
	2280	for (int i = 0; i < (int)rays.size(); ++ i)
	2281	{
	2282	//VspKdLeaf::NewMail();
	2283	VspKdRay *ray = rays[i];
	2284
	2285	// traverse leaves stored in the rays and compare and merge consecutive
	2286	// leaves (i.e., the neighbors in the tree)
	2287	if (ray->intersections.size() < 2)
	2288	continue;
	2289
	2290	iit = ray->intersections.begin();
	2291
	2292	BspLeaf previousLeaf = (iit).mLeaf;
	2293
	2294	++ iit;
	2295
	2296	for (; iit != ray->intersections.end(); ++ iit)
	2297	{
	2298	BspLeaf leaf = (iit).mLeaf;
[485]	2299	leaf->Mail
[483]	2300	// TODO: how to sort out doubles?
	2301	MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
	2302	mMergeQueue.push(mc);
	2303
	2304	MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
	2305	MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
	2306
	2307	previousLeaf = leaf;
	2308	}
	2309	}
	2310	}
[485]	2311	#endif
[483]	2312
[485]	2313	int VspKdTree::MergeViewCells(const VssRayContainer &rays)
[483]	2314	{
[485]	2315	CollectMergeCandidates();
	2316
[462]	2317	int merged = 0;
	2318
[485]	2319	int vcSize = mStat.Leaves();
[462]	2320	// use priority queue to merge leaves
[483]	2321	while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
	2322	(mMergeQueue.top().GetMergeCost() <
[482]	2323	mMergeMaxCostRatio * MergeCandidate::sOverallCost))
[462]	2324	{
[485]	2325	//Debug << "mergecost: " << mergeQueue.top().GetMergeCost() /
	2326	//MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
[483]	2327	MergeCandidate mc = mMergeQueue.top();
	2328	mMergeQueue.pop();
[465]	2329
	2330	// both view cells equal!
[462]	2331	if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
	2332	continue;
	2333
	2334	if (mc.Valid())
	2335	{
[465]	2336	ViewCell::NewMail();
	2337	MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
[462]	2338
	2339	++ merged;
	2340	-- vcSize;
[472]	2341	// increase absolute merge cost
	2342	MergeCandidate::sOverallCost += mc.GetMergeCost();
[452]	2343	}
[462]	2344	// merge candidate not valid, because one of the leaves was already
	2345	// merged with another one
[465]	2346	else
[462]	2347	{
	2348	// validate and reinsert into queue
	2349	mc.SetValid();
[483]	2350	mMergeQueue.push(mc);
[465]	2351	//Debug << "validate " << mc.GetMergeCost() << endl;
[462]	2352	}
[452]	2353	}
[462]	2354
[485]	2355	Debug << "merged " << merged << " of " << mStat.Leaves() << " leaves" << endl;
[465]	2356
[469]	2357	//TODO: should return sample contributions
[462]	2358	return merged;
[452]	2359	}
	2360
	2361
[517]	2362	void VspKdTree::RepairViewCellsLeafLists()
[465]	2363	{
	2364	// list not valid anymore => clear
	2365	stack<VspKdNode *> nodeStack;
	2366	nodeStack.push(mRoot);
	2367
	2368	ViewCell::NewMail();
	2369
	2370	while (!nodeStack.empty())
	2371	{
	2372	VspKdNode *node = nodeStack.top();
	2373	nodeStack.pop();
	2374
	2375	if (node->IsLeaf())
	2376	{
	2377	VspKdLeaf leaf = dynamic_cast<VspKdLeaf >(node);
	2378
	2379	VspKdViewCell *viewCell = leaf->GetViewCell();
	2380
	2381	if (!viewCell->Mailed())
	2382	{
[469]	2383	viewCell->mLeaves.clear();
[465]	2384	viewCell->Mail();
	2385	}
	2386
[469]	2387	viewCell->mLeaves.push_back(leaf);
[465]	2388	}
	2389	else
	2390	{
	2391	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
	2392
	2393	nodeStack.push(interior->GetFront());
	2394	nodeStack.push(interior->GetBack());
	2395	}
	2396	}
	2397	}
	2398
[479]	2399
[501]	2400	VspKdNode VspKdTree::CollapseTree(VspKdNode node, int &collapsed)
[465]	2401	{
[501]	2402	if (node->IsLeaf())
[465]	2403	return node;
	2404
[501]	2405	VspKdInterior interior = dynamic_cast<VspKdInterior >(node);
	2406
	2407	VspKdNode *front = CollapseTree(interior->GetFront(), collapsed);
	2408	VspKdNode *back = CollapseTree(interior->GetBack(), collapsed);
	2409
[465]	2410	if (front->IsLeaf() && back->IsLeaf())
	2411	{
	2412	VspKdLeaf frontLeaf = dynamic_cast<VspKdLeaf >(front);
	2413	VspKdLeaf backLeaf = dynamic_cast<VspKdLeaf >(back);
	2414
	2415	//-- collapse tree
	2416	if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
	2417	{
	2418	VspKdViewCell *vc = frontLeaf->GetViewCell();
	2419
	2420	VspKdLeaf *leaf = new VspKdLeaf(interior->GetParent(), 0);
	2421	leaf->SetViewCell(vc);
[501]	2422	//leaf->SetTreeValid(frontLeaf->TreeValid());
[465]	2423
	2424	// replace a link from node's parent
[501]	2425	if (leaf->mParent)
	2426	{
	2427	// replace a link from node's parent
	2428	VspKdInterior *parent =
	2429	dynamic_cast<VspKdInterior *>(leaf->mParent);
[500]	2430	parent->ReplaceChildLink(node, leaf);
[501]	2431	}
	2432	++ collapsed;
[465]	2433	delete interior;
	2434
	2435	return leaf;
	2436	}
	2437	}
	2438
[495]	2439	return node;
	2440	}
	2441
	2442
[501]	2443	int VspKdTree::CollapseTree()
[495]	2444	{
[501]	2445	int collapsed = 0;
	2446	CollapseTree(mRoot, collapsed);
[485]	2447	// revalidate leaves
[517]	2448	RepairViewCellsLeafLists();
[501]	2449
	2450	return collapsed;
[465]	2451	}
	2452
[501]	2453
[486]	2454	int VspKdTree::RefineViewCells(const VssRayContainer &rays)
[473]	2455	{
[486]	2456	int shuffled = 0;
	2457
	2458	Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
	2459	BspLeaf::NewMail();
	2460
	2461	// Use priority queue of remaining leaf pairs
	2462	// These candidates either share the same view cells or
	2463	// are border leaves which share a boundary.
	2464	// We test if they can be shuffled, i.e.,
	2465	// either one leaf is made part of one view cell or the other
	2466	// leaf is made part of the other view cell. It is tested if the
	2467	// remaining view cells are "better" than the old ones.
	2468	while (!mMergeQueue.empty())
	2469	{
	2470	MergeCandidate mc = mMergeQueue.top();
	2471	mMergeQueue.pop();
	2472
	2473	// both view cells equal or already shuffled
	2474	if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) \|\|
	2475	(mc.GetLeaf1()->Mailed()) \|\| (mc.GetLeaf2()->Mailed()))
	2476	continue;
	2477
	2478	// candidate for shuffling
	2479	const bool wasShuffled = false;
	2480	//ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
[495]	2481	// matt: restore
[486]	2482	//-- stats
	2483	if (wasShuffled)
	2484	++ shuffled;
	2485	}
	2486
	2487	return shuffled;
[473]	2488	}
	2489
	2490
[486]	2491	inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
	2492	{
	2493	return pvs1.AddPvs(pvs2);
	2494	}
	2495
	2496
	2497	inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
	2498	{
	2499	return pvs1.SubtractPvs(pvs2);
	2500	}
	2501
	2502
	2503	float GetShuffledVcCost(VspKdLeaf leaf, VspKdViewCell vc1, VspKdViewCell *vc2)
	2504	{
	2505	const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
	2506	const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
	2507
[495]	2508	const float vol1 = vc1->GetVolume() - leaf->mVolume;
	2509	const float vol2 = vc2->GetVolume() + leaf->mVolume;
[486]	2510
[495]	2511	const float cost1 = pvs1 * vol1;
	2512	const float cost2 = pvs2 * vol2;
[486]	2513
	2514	return cost1 + cost2;
	2515	}
	2516
	2517
	2518	void VspKdTree::ShuffleLeaf(VspKdLeaf *leaf,
	2519	VspKdViewCell *vc1,
	2520	VspKdViewCell *vc2) const
	2521	{
	2522	// compute new pvs and area
	2523	vc1->GetPvs().SubtractPvs(*leaf->mPvs);
	2524	vc2->GetPvs().AddPvs(*leaf->mPvs);
	2525
[495]	2526	vc1->SetArea(vc1->GetVolume() - leaf->mVolume);
	2527	vc2->SetArea(vc2->GetVolume() + leaf->mVolume);
[486]	2528
	2529	/// add to second view cell
	2530	vc2->mLeaves.push_back(leaf);
	2531
	2532	// erase leaf from old view cell
	2533	vector<VspKdLeaf *>::iterator it = vc1->mLeaves.begin();
	2534
	2535	for (; *it != leaf; ++ it);
	2536	vc1->mLeaves.erase(it);
	2537
	2538	leaf->SetViewCell(vc2); // finally change view cell
	2539	}
	2540
	2541
	2542	bool VspKdTree::ShuffleLeaves(VspKdLeaf leaf1, VspKdLeaf leaf2) const
	2543	{
	2544	VspKdViewCell *vc1 = leaf1->GetViewCell();
	2545	VspKdViewCell *vc2 = leaf2->GetViewCell();
	2546
	2547	const float cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
	2548	const float cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
	2549
	2550	const float oldCost = cost1 + cost2;
	2551
	2552	float shuffledCost1 = Limits::Infinity;
	2553	float shuffledCost2 = Limits::Infinity;
	2554
	2555	// the view cell should not be empty after the shuffle
	2556	if (vc1->mLeaves.size() > 1)
	2557	shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
	2558	if (vc2->mLeaves.size() > 1)
	2559	shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
	2560
	2561	// shuffling unsuccessful
	2562	if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
	2563	return false;
	2564
	2565	if (shuffledCost1 < shuffledCost2)
	2566	{
	2567	ShuffleLeaf(leaf1, vc1, vc2);
	2568	leaf1->Mail();
	2569	}
	2570	else
	2571	{
	2572	ShuffleLeaf(leaf2, vc2, vc1);
	2573	leaf2->Mail();
	2574	}
	2575
	2576	return true;
	2577	}
	2578
	2579
	2580
	2581
[452]	2582	/*********************************************************************/
	2583	/* MergeCandidate implementation */
	2584	/*********************************************************************/
	2585
	2586
[462]	2587	MergeCandidate::MergeCandidate(VspKdLeaf l1, VspKdLeaf l2):
	2588	mMergeCost(0),
	2589	mLeaf1(l1),
	2590	mLeaf2(l2),
	2591	mLeaf1Id(l1->GetViewCell()->mMailbox),
	2592	mLeaf2Id(l2->GetViewCell()->mMailbox)
	2593	{
	2594	EvalMergeCost();
	2595	}
[452]	2596
[472]	2597	float MergeCandidate::GetLeaf1Cost() const
	2598	{
	2599	VspKdViewCell *vc = mLeaf1->GetViewCell();
	2600	return vc->GetPvs().GetSize() * vc->GetVolume();
	2601	}
[462]	2602
[472]	2603	float MergeCandidate::GetLeaf2Cost() const
	2604	{
	2605	VspKdViewCell *vc = mLeaf2->GetViewCell();
	2606	return vc->GetPvs().GetSize() * vc->GetVolume();
	2607	}
	2608
[462]	2609	void MergeCandidate::EvalMergeCost()
[452]	2610	{
[465]	2611	//-- compute pvs difference
[463]	2612	VspKdViewCell *vc1 = mLeaf1->GetViewCell();
[462]	2613	VspKdViewCell *vc2 = mLeaf2->GetViewCell();
[452]	2614
[463]	2615	const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
[462]	2616	const int vcPvs = diff1 + vc1->GetPvs().GetSize();
[453]	2617
[465]	2618	//-- compute ratio of old cost
[462]	2619	//-- (added size of left and right view cell times pvs size)
	2620	//-- to new rendering cost (size of merged view cell times pvs size)
[472]	2621	const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
	2622
[465]	2623	const float newCost =
[469]	2624	(float)vcPvs * (vc1->GetVolume() + vc2->GetVolume());
[453]	2625
[465]	2626	mMergeCost = newCost - oldCost;
[462]	2627
[465]	2628	// if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
	2629	// mMergeCost += 1.0;
[462]	2630	}
	2631
	2632	void MergeCandidate::SetLeaf1(VspKdLeaf *l)
	2633	{
	2634	mLeaf1 = l;
	2635	}
	2636
	2637	void MergeCandidate::SetLeaf2(VspKdLeaf *l)
	2638	{
	2639	mLeaf2 = l;
	2640	}
	2641
[482]	2642
[462]	2643	VspKdLeaf *MergeCandidate::GetLeaf1()
	2644	{
	2645	return mLeaf1;
	2646	}
	2647
[482]	2648
[462]	2649	VspKdLeaf *MergeCandidate::GetLeaf2()
	2650	{
	2651	return mLeaf2;
	2652	}
	2653
[482]	2654
[462]	2655	bool MergeCandidate::Valid() const
[465]	2656	{
	2657	return
	2658	(mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
[462]	2659	(mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
	2660	}
	2661
[482]	2662
[462]	2663	float MergeCandidate::GetMergeCost() const
	2664	{
	2665	return mMergeCost;
	2666	}
	2667
[482]	2668
[462]	2669	void MergeCandidate::SetValid()
	2670	{
	2671	mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
	2672	mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
[465]	2673
[462]	2674	EvalMergeCost();
[463]	2675	}

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

Download in other formats: