Context Navigation

source: GTP/trunk/Lib/Vis/Preprocessing/src/VspKdTree.cpp @ 882

Revision 882, 59.5 KB checked in by mattausch, 19 years ago (diff)
added new active view cell concept

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

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

Download in other formats: