Context Navigation

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

Revision 421, 38.0 KB checked in by mattausch, 19 years ago (diff)
fixed controls for terrain demo fixed member names in vspkdtree

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"
[406]	27
[418]	28	// Static variables
	29	int VspKdTreeLeaf::mailID = 0;
[406]	30
[420]	31	/// Adds object to the pvs of the front and back node
[409]	32	inline void AddObject2Pvs(Intersectable *object,
	33	const int side,
	34	int &pvsBack,
	35	int &pvsFront)
[406]	36	{
[408]	37	if (!object)
	38	return;
	39
[409]	40	if (side <= 0)
	41	{
	42	if (!object->Mailed() && !object->Mailed(2))
	43	{
	44	++ pvsBack;
	45
[408]	46	if (object->Mailed(1))
	47	object->Mail(2);
	48	else
	49	object->Mail();
	50	}
	51	}
	52
[409]	53	if (side >= 0)
	54	{
	55	if (!object->Mailed(1) && !object->Mailed(2))
	56	{
	57	++ pvsFront;
[408]	58	if (object->Mailed())
	59	object->Mail(2);
	60	else
	61	object->Mail(1);
	62	}
	63	}
[406]	64	}
	65
[418]	66	/**************************************************************/
[420]	67	/* class VspKdTreeNode implementation */
	68	/**************************************************************/
	69
	70	// Inline constructor
	71	VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
	72	mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
	73	{}
	74
	75	VspKdTreeNode::~VspKdTreeNode()
	76	{};
	77
	78	inline VspKdTreeInterior *VspKdTreeNode::GetParent() const
	79	{
	80	return mParent;
	81	}
	82
	83	inline void VspKdTreeNode::SetParent(VspKdTreeInterior *p)
	84	{
	85	mParent = p;
	86	}
	87
	88	bool VspKdTreeNode::IsLeaf() const
	89	{
	90	return mAxis == -1;
	91	}
	92
	93	int VspKdTreeNode::GetAccessTime()
	94	{
	95	return 0x7FFFFFF;
	96	}
	97
	98	/**************************************************************/
[419]	99	/* VspKdTreeInterior implementation */
[418]	100	/**************************************************************/
[408]	101
[418]	102	VspKdTreeInterior::VspKdTreeInterior(VspKdTreeInterior *p):
	103	VspKdTreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
	104	{
	105	}
	106
	107	int VspKdTreeInterior::GetAccessTime()
	108	{
[419]	109	return mLastAccessTime;
[418]	110	}
	111
	112	void VspKdTreeInterior::SetupChildLinks(VspKdTreeNode b, VspKdTreeNode f)
	113	{
	114	mBack = b;
	115	mFront = f;
[420]	116	b->SetParent(this);
	117	f->SetParent(this);
[418]	118	}
	119
	120	void VspKdTreeInterior::ReplaceChildLink(VspKdTreeNode oldChild, VspKdTreeNode newChild)
	121	{
	122	if (mBack == oldChild)
	123	mBack = newChild;
	124	else
	125	mFront = newChild;
	126	}
	127
	128	int VspKdTreeInterior::Type() const
	129	{
[419]	130	return EInterior;
[418]	131	}
	132
	133	VspKdTreeInterior::~VspKdTreeInterior()
	134	{
	135	DEL_PTR(mBack);
	136	DEL_PTR(mFront);
	137	}
	138
	139	void VspKdTreeInterior::Print(ostream &s) const
	140	{
[419]	141	if (mAxis == 0)
[418]	142	s << "x ";
	143	else
[419]	144	if (mAxis == 1)
[418]	145	s << "y ";
	146	else
	147	s << "z ";
[419]	148	s << mPosition << " ";
[418]	149
	150	mBack->Print(s);
	151	mFront->Print(s);
	152	}
	153
	154	int VspKdTreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)
	155	{
[419]	156	return rayData.ComputeRayIntersection(mAxis, mPosition, t);
[418]	157	}
	158
[419]	159	VspKdTreeNode *VspKdTreeInterior::GetBack() const
	160	{
	161	return mBack;
	162	}
[418]	163
[419]	164	VspKdTreeNode *VspKdTreeInterior::GetFront() const
[406]	165	{
[419]	166	return mFront;
	167	}
[406]	168
[420]	169
	170	/*********************************************************/
	171	/* class VspKdTreeLeaf implementation */
	172	/*********************************************************/
	173	VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p, const int nRays):
	174	VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false)
	175	{
	176	mRays.reserve(nRays);
	177	}
	178
	179	VspKdTreeLeaf::~VspKdTreeLeaf()
	180	{}
	181
	182	int VspKdTreeLeaf::Type() const
	183	{
	184	return ELeaf;
	185	}
	186
	187	void VspKdTreeLeaf::Print(ostream &s) const
	188	{
	189	s << endl << "L: r = " << (int)mRays.size() << endl;
	190	};
	191
	192	void VspKdTreeLeaf::AddRay(const RayInfo &data)
	193	{
	194	mValidPvs = false;
	195	mRays.push_back(data);
	196	data.mRay->Ref();
	197	}
	198
	199	int VspKdTreeLeaf::GetPvsSize() const
	200	{
	201	return mPvsSize;
	202	}
	203
	204	void VspKdTreeLeaf::SetPvsSize(const int s)
	205	{
	206	mPvsSize = s;
	207	}
	208
	209	void VspKdTreeLeaf::Mail()
	210	{
	211	mMailbox = mailID;
	212	}
	213
	214	void VspKdTreeLeaf::NewMail()
	215	{
	216	++ mailID;
	217	}
	218
	219	bool VspKdTreeLeaf::Mailed() const
	220	{
	221	return mMailbox == mailID;
	222	}
	223
	224	bool VspKdTreeLeaf::Mailed(const int mail)
	225	{
	226	return mMailbox >= mailID + mail;
	227	}
	228
	229	float VspKdTreeLeaf::GetAvgRayContribution() const
	230	{
	231	return GetPvsSize() / ((float)mRays.size() + Limits::Small);
	232	}
	233
	234	float VspKdTreeLeaf::GetSqrRayContribution() const
	235	{
	236	return sqr(GetAvgRayContribution());
	237	}
	238
	239	/*********************************************************/
	240	/* class VspKdTree implementation */
	241	/*********************************************************/
	242
	243
[419]	244	// Constructor
	245	VspKdTree::VspKdTree()
	246	{
[421]	247	environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
	248	environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
	249	environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
	250	environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
	251	environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
	252
	253	environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
	254	mTermMinSize = sqr(mTermMinSize);
	255
[409]	256	environment->GetFloatValue("VspKdTree.epsilon", epsilon);
	257	environment->GetFloatValue("VspKdTree.ct_div_ci", ct_div_ci);
[408]	258
[409]	259	environment->GetFloatValue("VspKdTree.maxTotalMemory", maxTotalMemory);
	260	environment->GetFloatValue("VspKdTree.maxStaticMemory", maxStaticMemory);
[408]	261
	262
[409]	263	environment->GetIntValue("VspKdTree.accessTimeThreshold", accessTimeThreshold);
	264	//= 1000;
	265	environment->GetIntValue("VspKdTree.minCollapseDepth", minCollapseDepth);
	266
[408]	267
[409]	268	// split type
[408]	269	char sname[128];
	270	environment->GetStringValue("VspKdTree.splitType", sname);
[409]	271	string name(sname);
[408]	272
[409]	273	if (name.compare("regular") == 0)
	274	splitType = ESplitRegular;
	275	else
	276	{
	277	if (name.compare("heuristic") == 0)
	278	splitType = ESplitHeuristic;
	279	else
	280	{
	281	cerr << "Invalid VspKdTree split type " << name << endl;
[408]	282	exit(1);
	283	}
[409]	284	}
[408]	285
[418]	286	mRoot = NULL;
[409]	287
	288	splitCandidates = new vector<SortableEntry>;
[406]	289	}
	290
[408]	291
	292	VspKdTree::~VspKdTree()
[406]	293	{
[419]	294	DEL_PTR(mRoot);
[408]	295	}
[406]	296
[418]	297	void VspKdStatistics::Print(ostream &app) const
[408]	298	{
	299	app << "===== VspKdTree statistics ===============\n";
	300
	301	app << "#N_RAYS ( Number of rays )\n"
	302	<< rays <<endl;
[410]	303
	304	app << "#N_INITPVS ( Initial PVS size )\n"
[408]	305	<< initialPvsSize <<endl;
[406]	306
[408]	307	app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
[406]	308
[408]	309	app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
[406]	310
[408]	311	app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
	312	for (int i=0; i<7; i++)
	313	app << splits[i] <<" ";
	314	app <<endl;
[406]	315
[408]	316	app << "#N_RAYREFS ( Number of rayRefs )\n" <<
	317	rayRefs << "\n";
	318
	319	app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" <<
	320	rayRefs/(double)rays << "\n";
	321
	322	app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" <<
	323	rayRefs/(double)Leaves() << "\n";
	324
	325	app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" <<
	326	maxRayRefs << "\n";
	327
	328
	329	// app << setprecision(4);
	330
	331	app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
	332	maxDepthNodes*100/(double)Leaves()<<endl;
	333
	334	app << "#N_PMINPVSLEAVES ( Percentage of leaves with minCost )\n"<<
	335	minPvsNodes*100/(double)Leaves()<<endl;
	336
	337	app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minCost )\n"<<
	338	minRaysNodes*100/(double)Leaves()<<endl;
	339
	340	app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<<
	341	minSizeNodes*100/(double)Leaves()<<endl;
	342
	343	app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n"<<
	344	maxRayContribNodes*100/(double)Leaves()<<endl;
	345
	346	app << "#N_ADDED_RAYREFS (Number of dynamically added ray references )\n"<<
	347	addedRayRefs<<endl;
	348
	349	app << "#N_REMOVED_RAYREFS (Number of dynamically removed ray references )\n"<<
	350	removedRayRefs<<endl;
	351
	352	// app << setprecision(4);
	353
	354	app << "#N_CTIME ( Construction time [s] )\n"
	355	<< Time() << " \n";
	356
	357	app << "===== END OF VspKdTree statistics ==========\n";
	358
[406]	359	}
	360
[408]	361
	362	void
	363	VspKdTreeLeaf::UpdatePvsSize()
[406]	364	{
[409]	365	if (!mValidPvs)
	366	{
[408]	367	Intersectable::NewMail();
	368	int pvsSize = 0;
[420]	369	for(RayInfoContainer::iterator ri = mRays.begin();
	370	ri != mRays.end(); ++ ri)
[409]	371	{
	372	if ((*ri).mRay->IsActive())
	373	{
[408]	374	Intersectable *object;
	375	#if BIDIRECTIONAL_RAY
	376	object = (*ri).mRay->mOriginObject;
[409]	377
	378	if (object && !object->Mailed())
	379	{
	380	++ pvsSize;
[408]	381	object->Mail();
	382	}
	383	#endif
	384	object = (*ri).mRay->mTerminationObject;
[409]	385	if (object && !object->Mailed())
	386	{
	387	++ pvsSize;
[408]	388	object->Mail();
	389	}
	390	}
[409]	391	}
	392
[408]	393	mPvsSize = pvsSize;
	394	mValidPvs = true;
	395	}
	396	}
[406]	397
	398
[408]	399	void
[409]	400	VspKdTree::Construct(VssRayContainer &rays,
	401	AxisAlignedBox3 *forcedBoundingBox)
[408]	402	{
[414]	403	mStat.Start();
[408]	404
	405	maxMemory = maxStaticMemory;
	406
[419]	407	DEL_PTR(mRoot);
[408]	408
[419]	409	mRoot = new VspKdTreeLeaf(NULL, (int)rays.size());
[408]	410
[409]	411	// first construct a leaf that will get subdivide
[419]	412	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(mRoot);
[409]	413
	414
[414]	415	mStat.nodes = 1;
[409]	416
[419]	417	mBox.Initialize();
[409]	418
	419	for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
	420	{
[420]	421	leaf->AddRay(RayInfo(*ri));
[408]	422
[419]	423	mBox.Include((*ri)->GetOrigin());
	424	mBox.Include((*ri)->GetTermination());
[408]	425	}
	426
[409]	427	if (forcedBoundingBox)
[419]	428	mBox = *forcedBoundingBox;
[408]	429
[419]	430	cout << "Bbox = " << mBox << endl;
	431
[420]	432	mStat.rays = (int)leaf->mRays.size();
[408]	433	leaf->UpdatePvsSize();
[409]	434
[414]	435	mStat.initialPvsSize = leaf->GetPvsSize();
[409]	436
	437	// Subdivide();
[419]	438	mRoot = Subdivide(TraversalData(leaf, mBox, 0));
[408]	439
[409]	440	if (splitCandidates)
	441	{
	442	// force realease of this vector
	443	delete splitCandidates;
	444	splitCandidates = new vector<SortableEntry>;
	445	}
[408]	446
[414]	447	mStat.Stop();
[408]	448
[414]	449	mStat.Print(cout);
[409]	450	cout<<"#Total memory=" << GetMemUsage() << endl;
[408]	451	}
	452
	453
	454
[409]	455	VspKdTreeNode *VspKdTree::Subdivide(const TraversalData &tdata)
[408]	456	{
[409]	457	VspKdTreeNode *result = NULL;
[408]	458
[409]	459	priority_queue<TraversalData> tStack;
	460	// stack<TraversalData> tStack;
[406]	461
[409]	462	tStack.push(tdata);
[406]	463
[409]	464	AxisAlignedBox3 backBox;
	465	AxisAlignedBox3 frontBox;
[406]	466
[408]	467	int lastMem = 0;
[409]	468	while (!tStack.empty())
	469	{
[408]	470	float mem = GetMemUsage();
	471
[409]	472	if ( lastMem/10 != ((int)mem)/10)
	473	{
	474	cout << mem << " MB" << endl;
[408]	475	}
	476	lastMem = (int)mem;
	477
[409]	478	if ( mem > maxMemory )
	479	{
	480	// count statistics on unprocessed leafs
	481	while (!tStack.empty())
	482	{
[408]	483	EvaluateLeafStats(tStack.top());
	484	tStack.pop();
[409]	485	}
	486	break;
	487	}
[408]	488
[409]	489	TraversalData data = tStack.top();
	490	tStack.pop();
[406]	491
[409]	492
[419]	493	VspKdTreeNode node = SubdivideNode((VspKdTreeLeaf ) data.mNode,
	494	data.mBox, backBox, frontBox);
[409]	495	if (result == NULL)
	496	result = node;
[406]	497
[409]	498	if (!node->IsLeaf())
	499	{
	500	VspKdTreeInterior interior = (VspKdTreeInterior ) node;
[408]	501
[409]	502	// push the children on the stack
[419]	503	tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1));
	504	tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1));
[409]	505	}
	506	else
	507	{
	508	EvaluateLeafStats(data);
	509	}
	510	}
	511
	512	return result;
[408]	513	}
[406]	514
[408]	515
	516	// returns selected plane for subdivision
	517	int
[409]	518	VspKdTree::SelectPlane(VspKdTreeLeaf *leaf,
	519	const AxisAlignedBox3 &box,
	520	float &position,
	521	int &raysBack,
	522	int &raysFront,
	523	int &pvsBack,
	524	int &pvsFront)
[408]	525	{
[410]	526	int minDirDepth = 6;
	527	int axis;
[408]	528	float costRatio;
	529
[410]	530	if (splitType == ESplitRegular) {
[408]	531	costRatio = BestCostRatioRegular(leaf,
[410]	532	axis,
	533	position,
	534	raysBack,
	535	raysFront,
	536	pvsBack,
	537	pvsFront);
[408]	538
[410]	539	}
	540	else
	541	{
	542	if (splitType == ESplitHeuristic)
	543	costRatio = BestCostRatioHeuristic(leaf,
	544	axis,
	545	position,
	546	raysBack,
	547	raysFront,
	548	pvsBack,
	549	pvsFront);
[408]	550	else {
[410]	551	cerr << "VspKdTree: Unknown split heuristics\n";
[408]	552	exit(1);
	553	}
	554	}
	555
[421]	556	if (costRatio > mTermMaxCostRatio)
[410]	557	{
[408]	558	// cout<<"Too big cost ratio "<<costRatio<<endl;
	559	return -1;
	560	}
	561
	562	#if 0
	563	cout<<
	564	"pvs="<<leaf->mPvsSize<<
[420]	565	" rays="<<leaf->mRays.size()<<
[408]	566	" rc="<<leaf->GetAvgRayContribution()<<
	567	" axis="<<axis<<endl;
	568	#endif
	569
	570	return axis;
[406]	571	}
	572
	573
[408]	574
[406]	575
[408]	576	float
[410]	577	VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf,
	578	const int axis,
	579	const float position,
	580	int &raysBack,
	581	int &raysFront,
	582	int &pvsBack,
	583	int &pvsFront)
[406]	584	{
[408]	585	raysBack = 0;
	586	raysFront = 0;
	587	pvsFront = 0;
	588	pvsBack = 0;
	589
	590	float newCost;
	591
	592	Intersectable::NewMail(3);
	593
	594	// eval pvs size
	595	int pvsSize = leaf->GetPvsSize();
	596
	597	Intersectable::NewMail(3);
	598
[419]	599	// this is the main ray classification loop!
[420]	600	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
	601	ri != leaf->mRays.end(); ri++)
[419]	602	{
	603	if (!(*ri).mRay->IsActive())
	604	continue;
[410]	605
[419]	606	// determine the side of this ray with respect to the plane
	607	int side = (ri).ComputeRayIntersection(axis, position, (ri).mRay->mT);
	608	// (*ri).mRay->mSide = side;
	609
	610	if (side <= 0)
	611	++ raysBack;
[408]	612
[419]	613	if (side >= 0)
	614	++ raysFront;
[408]	615
[419]	616	AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
	617	}
[408]	618
[419]	619	AxisAlignedBox3 box = GetBBox(leaf);
[410]	620
[419]	621	float minBox = box.Min(axis);
	622	float maxBox = box.Max(axis);
	623	float sizeBox = maxBox - minBox;
[408]	624
[419]	625	// float sum = raysBack(position - minBox) + raysFront(maxBox - position);
	626	float sum = pvsBack(position - minBox) + pvsFront(maxBox - position);
[408]	627
[419]	628	newCost = ct_div_ci + sum/sizeBox;
	629
[408]	630	// cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl;
[420]	631	// float oldCost = leaf->mRays.size();
[419]	632	float oldCost = (float)pvsSize;
[410]	633
	634	float ratio = newCost / oldCost;
[408]	635	// cout<<"ratio="<<ratio<<endl;
	636	return ratio;
[406]	637	}
	638
[408]	639	float
[410]	640	VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf,
	641	int &axis,
	642	float &position,
	643	int &raysBack,
	644	int &raysFront,
	645	int &pvsBack,
	646	int &pvsFront)
[408]	647	{
	648	int nRaysBack[6], nRaysFront[6];
	649	int nPvsBack[6], nPvsFront[6];
	650	float nPosition[6];
	651	float nCostRatio[6];
	652	int bestAxis = -1;
	653
	654	AxisAlignedBox3 sBox = GetBBox(leaf);
[410]	655
[408]	656	// int sAxis = box.Size().DrivingAxis();
	657	int sAxis = sBox.Size().DrivingAxis();
[419]	658
[408]	659	bool onlyDrivingAxis = true;
	660
[410]	661	for (axis = 0; axis < 6; ++ axis)
	662	{
[419]	663	if (!onlyDrivingAxis \|\| axis == sAxis)
[410]	664	{
[419]	665	nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f;
	666
[408]	667	nCostRatio[axis] = EvalCostRatio(leaf,
[410]	668	axis,
	669	nPosition[axis],
	670	nRaysBack[axis],
	671	nRaysFront[axis],
	672	nPvsBack[axis],
	673	nPvsFront[axis]);
[408]	674
[410]	675	if (bestAxis == -1)
[408]	676	bestAxis = axis;
	677	else
[410]	678	if (nCostRatio[axis] < nCostRatio[bestAxis])
[408]	679	bestAxis = axis;
	680	}
	681	}
	682
	683	axis = bestAxis;
	684	position = nPosition[bestAxis];
	685
	686	raysBack = nRaysBack[bestAxis];
	687	raysFront = nRaysFront[bestAxis];
	688
	689	pvsBack = nPvsBack[bestAxis];
	690	pvsFront = nPvsFront[bestAxis];
	691
	692	return nCostRatio[bestAxis];
	693	}
	694
[410]	695	float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf,
	696	int &axis,
	697	float &position,
	698	int &raysBack,
	699	int &raysFront,
	700	int &pvsBack,
	701	int &pvsFront)
[406]	702	{
[408]	703	AxisAlignedBox3 box = GetBBox(leaf);
	704	// AxisAlignedBox3 dirBox = GetDirBBox(node);
	705
	706	axis = box.Size().DrivingAxis();
	707
	708	SortSplitCandidates(leaf, axis);
[406]	709
[408]	710	// go through the lists, count the number of objects left and right
	711	// and evaluate the following cost funcion:
	712	// C = ct_div_ci + (qlrl + qrrr)/queries
	713
[420]	714	int rl = 0, rr = (int)leaf->mRays.size();
	715	int pl = 0, pr = leaf->GetPvsSize();
[408]	716	float minBox = box.Min(axis);
	717	float maxBox = box.Max(axis);
	718	float sizeBox = maxBox - minBox;
	719
[419]	720	float minBand = minBox + 0.1f*(maxBox - minBox);
	721	float maxBand = minBox + 0.9f*(maxBox - minBox);
[408]	722
	723	float sum = rr*sizeBox;
[411]	724	float minSum = 1e20f;
[408]	725
	726	Intersectable::NewMail();
	727	// set all object as belonging to the fron pvs
[420]	728	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
	729	ri != leaf->mRays.end(); ++ ri)
[410]	730	{
	731	if ((*ri).mRay->IsActive())
	732	{
[408]	733	Intersectable object = (ri).mRay->mTerminationObject;
[410]	734
[408]	735	if (object)
[410]	736	if (!object->Mailed())
	737	{
[408]	738	object->Mail();
	739	object->mCounter = 1;
[410]	740	}
	741	else
	742	++ object->mCounter;
[408]	743	}
[410]	744	}
[408]	745
	746	Intersectable::NewMail();
	747
[410]	748	for (vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
	749	ci < splitCandidates->end(); ++ ci)
	750	{
[408]	751	VssRay *ray;
[410]	752
	753	switch ((*ci).type)
	754	{
	755	case SortableEntry::ERayMin:
	756	{
	757	++ rl;
	758	ray = (VssRay ) (ci).data;
	759	Intersectable *object = ray->mTerminationObject;
	760	if (object && !object->Mailed())
	761	{
	762	object->Mail();
	763	++ pl;
	764	}
	765	break;
	766	}
	767	case SortableEntry::ERayMax:
	768	{
	769	-- rr;
	770
	771	ray = (VssRay ) (ci).data;
	772	Intersectable *object = ray->mTerminationObject;
	773
	774	if (object)
	775	{
	776	if (-- object->mCounter == 0)
	777	-- pr;
	778	}
	779
	780	break;
	781	}
[408]	782	}
	783
[410]	784	if ((ci).value > minBand && (ci).value < maxBand)
	785	{
[408]	786	sum = pl((ci).value - minBox) + pr(maxBox - (ci).value);
[410]	787
	788	// cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
	789	// cout<<"cost= "<<sum<<endl;
[408]	790
[410]	791	if (sum < minSum)
	792	{
[408]	793	minSum = sum;
	794	position = (*ci).value;
[410]	795
[408]	796	raysBack = rl;
	797	raysFront = rr;
[410]	798
[408]	799	pvsBack = pl;
	800	pvsFront = pr;
	801
[410]	802	}
	803	}
	804	}
	805
[419]	806	float oldCost = (float)leaf->GetPvsSize();
[410]	807	float newCost = ct_div_ci + minSum / sizeBox;
	808	float ratio = newCost / oldCost;
[408]	809
[410]	810	// cout<<"===================="<<endl;
	811	// cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
	812	// <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl;
	813
[408]	814	return ratio;
	815	}
	816
[410]	817	void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node,
	818	const int axis)
[408]	819	{
[410]	820	splitCandidates->clear();
[408]	821
[420]	822	int requestedSize = 2 * (int)(node->mRays.size());
[410]	823	// creates a sorted split candidates array
	824	if (splitCandidates->capacity() > 500000 &&
	825	requestedSize < (int)(splitCandidates->capacity()/10) )
	826	{
	827	delete splitCandidates;
	828	splitCandidates = new vector<SortableEntry>;
	829	}
[408]	830
[410]	831	splitCandidates->reserve(requestedSize);
[408]	832
[410]	833	// insert all queries
[420]	834	for(RayInfoContainer::const_iterator ri = node->mRays.begin();
	835	ri < node->mRays.end(); ++ ri)
[410]	836	{
	837	bool positive = (*ri).mRay->HasPosDir(axis);
	838	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
	839	(ri).ExtrapOrigin(axis), (void )&*ri));
[408]	840
[410]	841	splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
	842	(ri).ExtrapTermination(axis), (void )&*ri));
	843	}
[408]	844
[410]	845	stable_sort(splitCandidates->begin(), splitCandidates->end());
[406]	846	}
	847
[408]	848
[410]	849	void VspKdTree::EvaluateLeafStats(const TraversalData &data)
[406]	850	{
[410]	851	// the node became a leaf -> evaluate stats for leafs
[419]	852	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(data.mNode);
[408]	853
[421]	854	if (data.mDepth >= mTermMaxDepth)
[413]	855	++ mStat.maxDepthNodes;
[406]	856
[420]	857	// if ( (int)(leaf->mRays.size()) < termMinCost)
[408]	858	// stat.minCostNodes++;
[421]	859	if (leaf->GetPvsSize() < mTermMinPvs)
[413]	860	++ mStat.minPvsNodes;
[408]	861
[421]	862	if (leaf->GetPvsSize() < mTermMinRays)
[413]	863	++ mStat.minRaysNodes;
[408]	864
[421]	865	if (0 && leaf->GetAvgRayContribution() > mTermMaxRayContribution)
[413]	866	++ mStat.maxRayContribNodes;
[408]	867
[421]	868	if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)
[413]	869	++ mStat.minSizeNodes;
[408]	870
[420]	871	// if ((int)(leaf->mRays.size()) > stat.maxRayRefs)
	872	// mStat.maxRayRefs = (int)leaf->mRays.size();
[408]	873	}
	874
	875
[421]	876	inline bool VspKdTree::TerminationCriteriaMet(const VspKdTreeLeaf *leaf,
	877	const AxisAlignedBox3 &box) const
	878	{
	879	return ((leaf->GetPvsSize() < mTermMinPvs) \|\| (leaf->mRays.size() < mTermMinRays) \|\|
	880	// (leaf->GetAvgRayContribution() > termMaxRayContribution ) \|\|
	881	(leaf->mDepth >= mTermMaxDepth) \|\| SqrMagnitude(box.Size()) <= mTermMinSize);
	882	}
[408]	883
[421]	884
[410]	885	VspKdTreeNode VspKdTree::SubdivideNode(VspKdTreeLeaf leaf,
	886	const AxisAlignedBox3 &box,
	887	AxisAlignedBox3 &backBBox,
	888	AxisAlignedBox3 &frontBBox)
[408]	889	{
[421]	890	if (TerminationCriteriaMet(leaf, box))
[410]	891	{
[408]	892
	893	#if 0
[419]	894	if (leaf->mDepth >= termMaxDepth) {
[420]	895	cout<<"Warning: max depth reached depth="<<(int)leaf->mDepth<<" rays="<<leaf->mRays.size()<<endl;
[408]	896	cout<<"Bbox: "<<GetBBox(leaf)<<" dirbbox:"<<GetDirBBox(leaf)<<endl;
	897	}
	898	#endif
	899
	900	return leaf;
	901	}
	902
	903	float position;
	904	// first count ray sides
[410]	905	int raysBack;
	906	int raysFront;
[408]	907	int pvsBack;
	908	int pvsFront;
	909
[410]	910	// select subdivision axis
	911	int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
[406]	912
[408]	913	// cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<<
	914	// pvsFront<<endl;
	915
[410]	916	if (axis == -1)
	917	{
	918	return leaf;
	919	}
[406]	920
[413]	921	mStat.nodes += 2;
	922	//++ mStat.splits[axis];
[408]	923
[410]	924	// add the new nodes to the tree
[419]	925	VspKdTreeInterior *node = new VspKdTreeInterior(leaf->mParent);
[406]	926
[419]	927	node->mAxis = axis;
	928	node->mPosition = position;
	929	node->mBox = box;
	930
[410]	931	backBBox = box;
	932	frontBBox = box;
[406]	933
[410]	934	VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
[408]	935	back->SetPvsSize(pvsBack);
[410]	936	VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
[408]	937	front->SetPvsSize(pvsFront);
[406]	938
[410]	939	// replace a link from node's parent
[419]	940	if (leaf->mParent)
	941	leaf->mParent->ReplaceChildLink(leaf, node);
[410]	942	// and setup child links
	943	node->SetupChildLinks(back, front);
[408]	944
[410]	945	if (axis <= VspKdTreeNode::SPLIT_Z)
	946	{
[408]	947	backBBox.SetMax(axis, position);
[410]	948	frontBBox.SetMin(axis, position);
[408]	949
[420]	950	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
	951	ri != leaf->mRays.end(); ++ ri)
[410]	952	{
	953	if ((*ri).mRay->IsActive())
	954	{
[408]	955	// first unref ray from the former leaf
	956	(*ri).mRay->Unref();
[406]	957
[408]	958	// determine the side of this ray with respect to the plane
	959	int side = node->ComputeRayIntersection(ri, (ri).mRay->mT);
	960
[410]	961	if (side == 0)
	962	{
	963	if ((*ri).mRay->HasPosDir(axis))
	964	{
[420]	965	back->AddRay(RayInfo((*ri).mRay,
	966	(*ri).mMinT,
	967	(*ri).mRay->mT));
	968	front->AddRay(RayInfo((*ri).mRay,
	969	(*ri).mRay->mT,
	970	(*ri).mMaxT));
[410]	971	}
	972	else
	973	{
[420]	974	back->AddRay(RayInfo((*ri).mRay,
	975	(*ri).mRay->mT,
	976	(*ri).mMaxT));
	977	front->AddRay(RayInfo((*ri).mRay,
	978	(*ri).mMinT,
	979	(*ri).mRay->mT));
[408]	980	}
[410]	981	}
	982	else
[408]	983	if (side == 1)
	984	front->AddRay(*ri);
	985	else
	986	back->AddRay(*ri);
[410]	987	} else
[408]	988	(*ri).mRay->Unref();
[410]	989	}
	990	}
	991	else
	992	{
	993	// rays front/back
[406]	994
[420]	995	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
	996	ri != leaf->mRays.end(); ++ ri)
[410]	997	{
	998	if ((*ri).mRay->IsActive())
	999	{
[408]	1000	// first unref ray from the former leaf
	1001	(*ri).mRay->Unref();
	1002
	1003	int side;
	1004	if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
	1005	side = 1;
	1006	else
	1007	side = -1;
	1008
	1009	if (side == 1)
	1010	front->AddRay(*ri);
	1011	else
[410]	1012	back->AddRay(*ri);
	1013	}
	1014	else
[408]	1015	(*ri).mRay->Unref();
[410]	1016	}
	1017	}
[408]	1018
[410]	1019	// update stats
[420]	1020	mStat.rayRefs -= (int)leaf->mRays.size();
[414]	1021	mStat.rayRefs += raysBack + raysFront;
[408]	1022
[420]	1023	DEL_PTR(leaf);
	1024
[410]	1025	return node;
[406]	1026	}
	1027
[410]	1028	int VspKdTree::ReleaseMemory(const int time)
	1029	{
	1030	stack<VspKdTreeNode *> tstack;
[406]	1031
[410]	1032	// find a node in the tree which subtree will be collapsed
	1033	int maxAccessTime = time - accessTimeThreshold;
[420]	1034	int released = 0;
[406]	1035
[419]	1036	tstack.push(mRoot);
[406]	1037
[410]	1038	while (!tstack.empty())
	1039	{
	1040	VspKdTreeNode *node = tstack.top();
	1041	tstack.pop();
[408]	1042
[410]	1043	if (!node->IsLeaf())
	1044	{
[419]	1045	VspKdTreeInterior in = dynamic_cast<VspKdTreeInterior >(node);
[410]	1046	// cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
[419]	1047	if (in->mDepth >= minCollapseDepth && in->mLastAccessTime <= maxAccessTime)
[410]	1048	{
	1049	released = CollapseSubtree(node, time);
	1050	break;
	1051	}
[420]	1052	if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())
[410]	1053	{
[419]	1054	tstack.push(in->GetFront());
	1055	tstack.push(in->GetBack());
[410]	1056	}
	1057	else
	1058	{
[419]	1059	tstack.push(in->GetBack());
	1060	tstack.push(in->GetFront());
[410]	1061	}
	1062	}
	1063	}
[406]	1064
[410]	1065	while (tstack.empty())
	1066	{
	1067	// could find node to collaps...
	1068	// cout<<"Could not find a node to release "<<endl;
	1069	break;
	1070	}
[408]	1071
[410]	1072	return released;
[408]	1073	}
[406]	1074
	1075
	1076
	1077
[410]	1078	VspKdTreeNode VspKdTree::SubdivideLeaf(VspKdTreeLeaf leaf,
	1079	const float sizeThreshold)
[408]	1080	{
[410]	1081	VspKdTreeNode *node = leaf;
[406]	1082
[410]	1083	AxisAlignedBox3 leafBBox = GetBBox(leaf);
[406]	1084
[408]	1085	static int pass = 0;
[410]	1086	++ pass;
[408]	1087
[410]	1088	// check if we should perform a dynamic subdivision of the leaf
[420]	1089	if (// leaf->mRays.size() > (unsigned)termMinCost &&
[421]	1090	(leaf->GetPvsSize() >= mTermMinPvs) &&
[410]	1091	(SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
	1092	{
	1093	// memory check and realese...
	1094	if (GetMemUsage() > maxTotalMemory)
	1095	ReleaseMemory(pass);
	1096
	1097	AxisAlignedBox3 backBBox, frontBBox;
[406]	1098
[410]	1099	// subdivide the node
	1100	node = SubdivideNode(leaf, leafBBox, backBBox, frontBBox);
	1101	}
	1102	return node;
[406]	1103	}
	1104
	1105
	1106
	1107	void
[408]	1108	VspKdTree::UpdateRays(VssRayContainer &remove,
[410]	1109	VssRayContainer &add)
[406]	1110	{
[410]	1111	VspKdTreeLeaf::NewMail();
[406]	1112
[410]	1113	// schedule rays for removal
	1114	for(VssRayContainer::const_iterator ri = remove.begin();
	1115	ri != remove.end(); ++ ri)
	1116	{
	1117	(*ri)->ScheduleForRemoval();
	1118	}
[406]	1119
[410]	1120	int inactive = 0;
[406]	1121
[410]	1122	for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)
	1123	{
	1124	if ((*ri)->ScheduledForRemoval())
	1125	// RemoveRay(*ri, NULL, false);
	1126	// !!! BUG - with true it does not work correctly - aggreated delete
	1127	RemoveRay(*ri, NULL, true);
	1128	else
	1129	++ inactive;
	1130	}
[406]	1131
[410]	1132	// cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
[406]	1133
[410]	1134	for(VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)
	1135	{
	1136	AddRay(*ri);
	1137	}
[406]	1138	}
	1139
	1140
[410]	1141	void VspKdTree::RemoveRay(VssRay *ray,
	1142	vector<VspKdTreeLeaf > affectedLeaves,
	1143	const bool removeAllScheduledRays)
[406]	1144	{
[410]	1145	stack<RayTraversalData> tstack;
[406]	1146
[420]	1147	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
[406]	1148
[410]	1149	RayTraversalData data;
[406]	1150
[410]	1151	// cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
	1152	while (!tstack.empty())
	1153	{
	1154	data = tstack.top();
	1155	tstack.pop();
[406]	1156
[419]	1157	if (!data.mNode->IsLeaf())
[410]	1158	{
	1159	// split the set of rays in two groups intersecting the
	1160	// two subtrees
	1161	TraverseInternalNode(data, tstack);
	1162	}
	1163	else
	1164	{
	1165	// remove the ray from the leaf
	1166	// find the ray in the leaf and swap it with the last ray...
[419]	1167	VspKdTreeLeaf leaf = (VspKdTreeLeaf )data.mNode;
[408]	1168
[410]	1169	if (!leaf->Mailed())
	1170	{
	1171	leaf->Mail();
	1172
	1173	if (affectedLeaves)
	1174	affectedLeaves->push_back(leaf);
[406]	1175
[410]	1176	if (removeAllScheduledRays)
	1177	{
[420]	1178	int tail = (int)leaf->mRays.size() - 1;
[406]	1179
[420]	1180	for (int i=0; i < (int)(leaf->mRays.size()); ++ i)
[410]	1181	{
[420]	1182	if (leaf->mRays[i].mRay->ScheduledForRemoval())
[410]	1183	{
	1184	// find a ray to replace it with
[420]	1185	while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())
[410]	1186	{
[414]	1187	++ mStat.removedRayRefs;
[420]	1188	leaf->mRays[tail].mRay->Unref();
	1189	leaf->mRays.pop_back();
[410]	1190
	1191	-- tail;
	1192	}
	1193
	1194	if (tail < i)
	1195	break;
[408]	1196
[414]	1197	++ mStat.removedRayRefs;
[410]	1198
[420]	1199	leaf->mRays[i].mRay->Unref();
	1200	leaf->mRays[i] = leaf->mRays[tail];
	1201	leaf->mRays.pop_back();
[410]	1202	-- tail;
	1203	}
	1204	}
	1205	}
	1206	}
[406]	1207
[410]	1208	if (!removeAllScheduledRays)
[420]	1209	for (int i=0; i < (int)leaf->mRays.size(); i++)
[410]	1210	{
[420]	1211	if (leaf->mRays[i].mRay == ray)
[410]	1212	{
[414]	1213	++ mStat.removedRayRefs;
[410]	1214	ray->Unref();
[420]	1215	leaf->mRays[i] = leaf->mRays[leaf->mRays.size() - 1];
	1216	leaf->mRays.pop_back();
[410]	1217	// check this ray again
	1218	break;
	1219	}
	1220	}
	1221	}
[408]	1222	}
	1223
[410]	1224	if (ray->RefCount() != 0)
	1225	{
	1226	cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
	1227	exit(1);
	1228	}
	1229
[406]	1230	}
	1231
[410]	1232	void VspKdTree::AddRay(VssRay *ray)
[406]	1233	{
[410]	1234	stack<RayTraversalData> tstack;
[406]	1235
[420]	1236	tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
[406]	1237
[410]	1238	RayTraversalData data;
[406]	1239
[410]	1240	while (!tstack.empty())
	1241	{
	1242	data = tstack.top();
	1243	tstack.pop();
[406]	1244
[419]	1245	if (!data.mNode->IsLeaf())
[410]	1246	{
	1247	TraverseInternalNode(data, tstack);
	1248	}
	1249	else
	1250	{
	1251	// remove the ray from the leaf
[420]	1252	// find the ray in the leaf and swap it with the last ray
	1253	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(data.mNode);
[419]	1254	leaf->AddRay(data.mRayData);
[413]	1255	++ mStat.addedRayRefs;
[410]	1256	}
	1257	}
[406]	1258	}
	1259
[410]	1260	void VspKdTree::TraverseInternalNode(RayTraversalData &data,
	1261	stack<RayTraversalData> &tstack)
[406]	1262	{
[419]	1263	VspKdTreeInterior in = (VspKdTreeInterior ) data.mNode;
[408]	1264
[419]	1265	if (in->mAxis <= VspKdTreeNode::SPLIT_Z)
[410]	1266	{
	1267	// determine the side of this ray with respect to the plane
[419]	1268	int side = in->ComputeRayIntersection(data.mRayData, data.mRayData.mRay->mT);
[408]	1269
[410]	1270	if (side == 0)
	1271	{
[419]	1272	if (data.mRayData.mRay->HasPosDir(in->mAxis))
[410]	1273	{
[419]	1274	tstack.push(RayTraversalData(in->GetBack(),
[420]	1275	RayInfo(data.mRayData.mRay, data.mRayData.mMinT, data.mRayData.mRay->mT)));
[408]	1276
[419]	1277	tstack.push(RayTraversalData(in->GetFront(),
[420]	1278	RayInfo(data.mRayData.mRay, data.mRayData.mRay->mT, data.mRayData.mMaxT)));
[408]	1279
[410]	1280	}
	1281	else
	1282	{
[419]	1283	tstack.push(RayTraversalData(in->GetBack(),
[420]	1284	RayInfo(data.mRayData.mRay,
	1285	data.mRayData.mRay->mT,
	1286	data.mRayData.mMaxT)));
[419]	1287	tstack.push(RayTraversalData(in->GetFront(),
[420]	1288	RayInfo(data.mRayData.mRay,
	1289	data.mRayData.mMinT,
	1290	data.mRayData.mRay->mT)));
[410]	1291	}
	1292	}
	1293	else
	1294	if (side == 1)
[419]	1295	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
[410]	1296	else
[419]	1297	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
[410]	1298	}
	1299	else
	1300	{
	1301	// directional split
[419]	1302	if (data.mRayData.mRay->GetDirParametrization(in->mAxis - 3) > in->mPosition)
	1303	tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
[408]	1304	else
[419]	1305	tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
[410]	1306	}
[406]	1307	}
	1308
[408]	1309
[410]	1310	int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
[406]	1311	{
[410]	1312	// first count all rays in the subtree
	1313	// use mail 1 for this purpose
	1314	stack<VspKdTreeNode *> tstack;
	1315
	1316	int rayCount = 0;
	1317	int totalRayCount = 0;
	1318	int collapsedNodes = 0;
[408]	1319
	1320	#if DEBUG_COLLAPSE
[420]	1321	cout << "Collapsing subtree" << endl;
	1322	cout << "acessTime=" << sroot->GetAccessTime() << endl;
	1323	cout << "depth=" << (int)sroot->depth << endl;
[408]	1324	#endif
	1325
[410]	1326	// tstat.collapsedSubtrees++;
	1327	// tstat.collapseDepths += (int)sroot->depth;
	1328	// tstat.collapseAccessTimes += time - sroot->GetAccessTime();
	1329	tstack.push(sroot);
	1330	VssRay::NewMail();
[408]	1331
[410]	1332	while (!tstack.empty())
	1333	{
	1334	++ collapsedNodes;
	1335
	1336	VspKdTreeNode *node = tstack.top();
	1337	tstack.pop();
	1338	if (node->IsLeaf())
	1339	{
	1340	VspKdTreeLeaf leaf = (VspKdTreeLeaf ) node;
	1341
[420]	1342	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
	1343	ri != leaf->mRays.end(); ++ ri)
[410]	1344	{
	1345	++ totalRayCount;
[408]	1346
[410]	1347	if ((ri).mRay->IsActive() && !(ri).mRay->Mailed())
	1348	{
[408]	1349	(*ri).mRay->Mail();
[410]	1350	++ rayCount;
[408]	1351	}
[410]	1352	}
	1353	}
	1354	else
	1355	{
[419]	1356	tstack.push(((VspKdTreeInterior *)node)->GetFront());
	1357	tstack.push(((VspKdTreeInterior *)node)->GetBack());
[410]	1358	}
	1359	}
[406]	1360
[410]	1361	VssRay::NewMail();
[406]	1362
[410]	1363	// create a new node that will hold the rays
[419]	1364	VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount);
[410]	1365
[419]	1366	if (newLeaf->mParent)
	1367	newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
[406]	1368
[410]	1369	tstack.push(sroot);
[406]	1370
[410]	1371	while (!tstack.empty())
	1372	{
	1373	VspKdTreeNode *node = tstack.top();
	1374	tstack.pop();
[408]	1375
[410]	1376	if (node->IsLeaf())
	1377	{
[419]	1378	VspKdTreeLeaf leaf = dynamic_cast<VspKdTreeLeaf >(node);
[408]	1379
[420]	1380	for(RayInfoContainer::iterator ri = leaf->mRays.begin();
	1381	ri != leaf->mRays.end(); ++ ri)
[410]	1382	{
	1383	// unref this ray from the old node
	1384	if ((*ri).mRay->IsActive())
	1385	{
[408]	1386	(*ri).mRay->Unref();
[410]	1387	if (!(*ri).mRay->Mailed())
	1388	{
[408]	1389	(*ri).mRay->Mail();
	1390	newLeaf->AddRay(*ri);
	1391	}
[410]	1392	}
	1393	else
[408]	1394	(*ri).mRay->Unref();
[410]	1395	}
	1396	}
	1397	else
	1398	{
[419]	1399	VspKdTreeInterior *interior =
	1400	dynamic_cast<VspKdTreeInterior *>(node);
	1401	tstack.push(interior->GetBack());
	1402	tstack.push(interior->GetFront());
[410]	1403	}
	1404	}
[406]	1405
[410]	1406	// delete the node and all its children
[420]	1407	DEL_PTR(sroot);
[408]	1408
[420]	1409	// for(VspKdTreeNode::SRayContainer::iterator ri = newleaf->mRays.begin();
	1410	// ri != newleaf->mRays.end(); ++ ri)
[410]	1411	// (*ri).ray->UnMail(2);
[408]	1412
	1413	#if DEBUG_COLLAPSE
[410]	1414	cout<<"Total memory before="<<GetMemUsage()<<endl;
[408]	1415	#endif
	1416
[414]	1417	mStat.nodes -= collapsedNodes - 1;
	1418	mStat.rayRefs -= totalRayCount - rayCount;
[408]	1419
	1420	#if DEBUG_COLLAPSE
[410]	1421	cout << "collapsed nodes" << collapsedNodes << endl;
	1422	cout << "collapsed rays" << totalRayCount - rayCount << endl;
	1423	cout << "Total memory after=" << GetMemUsage() << endl;
	1424	cout << "================================" << endl;
[408]	1425	#endif
	1426
	1427	// tstat.collapsedNodes += collapsedNodes;
	1428	// tstat.collapsedRays += totalRayCount - rayCount;
[410]	1429	return totalRayCount - rayCount;
[406]	1430	}
	1431
[408]	1432
[410]	1433	int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
[406]	1434	{
[408]	1435	stack<VspKdTreeNode *> tstack;
[419]	1436	tstack.push(mRoot);
[408]	1437
	1438	Intersectable::NewMail();
	1439	int pvsSize = 0;
	1440
[410]	1441	while (!tstack.empty())
	1442	{
	1443	VspKdTreeNode *node = tstack.top();
	1444	tstack.pop();
[408]	1445
[410]	1446	if (node->IsLeaf())
	1447	{
[408]	1448	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
[420]	1449	for (RayInfoContainer::iterator ri = leaf->mRays.begin();
	1450	ri != leaf->mRays.end(); ++ ri)
[410]	1451	{
	1452	if ((*ri).mRay->IsActive())
	1453	{
[408]	1454	Intersectable *object;
	1455	#if BIDIRECTIONAL_RAY
	1456	object = (*ri).mRay->mOriginObject;
[410]	1457
	1458	if (object && !object->Mailed())
	1459	{
	1460	++ pvsSize;
[408]	1461	object->Mail();
	1462	}
	1463	#endif
	1464	object = (*ri).mRay->mTerminationObject;
[410]	1465	if (object && !object->Mailed())
	1466	{
	1467	++ pvsSize;
[408]	1468	object->Mail();
	1469	}
	1470	}
[410]	1471	}
	1472	}
	1473	else
	1474	{
[419]	1475	VspKdTreeInterior in = dynamic_cast<VspKdTreeInterior >(node);
[410]	1476
[419]	1477	if (in->mAxis < 3)
[410]	1478	{
[419]	1479	if (box.Max(in->mAxis) >= in->mPosition)
	1480	tstack.push(in->GetFront());
[408]	1481
[419]	1482	if (box.Min(in->mAxis) <= in->mPosition)
	1483	tstack.push(in->GetBack());
[410]	1484	}
	1485	else
	1486	{
[408]	1487	// both nodes for directional splits
[419]	1488	tstack.push(in->GetFront());
	1489	tstack.push(in->GetBack());
[408]	1490	}
	1491	}
	1492	}
[410]	1493
[408]	1494	return pvsSize;
[406]	1495	}
	1496
[410]	1497	void VspKdTree::GetRayContributionStatistics(float &minRayContribution,
	1498	float &maxRayContribution,
	1499	float &avgRayContribution)
[406]	1500	{
[408]	1501	stack<VspKdTreeNode *> tstack;
[419]	1502	tstack.push(mRoot);
[408]	1503
	1504	minRayContribution = 1.0f;
	1505	maxRayContribution = 0.0f;
[410]	1506
[408]	1507	float sumRayContribution = 0.0f;
	1508	int leaves = 0;
[406]	1509
[410]	1510	while (!tstack.empty())
	1511	{
	1512	VspKdTreeNode *node = tstack.top();
	1513	tstack.pop();
	1514	if (node->IsLeaf())
	1515	{
[408]	1516	leaves++;
	1517	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
	1518	float c = leaf->GetAvgRayContribution();
[410]	1519
[408]	1520	if (c > maxRayContribution)
	1521	maxRayContribution = c;
	1522	if (c < minRayContribution)
	1523	minRayContribution = c;
	1524	sumRayContribution += c;
	1525
[410]	1526	}
	1527	else {
[408]	1528	VspKdTreeInterior in = (VspKdTreeInterior )node;
	1529	// both nodes for directional splits
[419]	1530	tstack.push(in->GetFront());
	1531	tstack.push(in->GetBack());
[408]	1532	}
	1533	}
	1534
[419]	1535	cout << "sum=" << sumRayContribution << endl;
	1536	cout << "leaves=" << leaves << endl;
[408]	1537	avgRayContribution = sumRayContribution/(float)leaves;
[406]	1538	}
	1539
	1540
[410]	1541	int VspKdTree::GenerateRays(const float ratioPerLeaf,
	1542	SimpleRayContainer &rays)
[406]	1543	{
[408]	1544	stack<VspKdTreeNode *> tstack;
[419]	1545	tstack.push(mRoot);
[408]	1546
[410]	1547	while (!tstack.empty())
	1548	{
	1549	VspKdTreeNode *node = tstack.top();
	1550	tstack.pop();
[408]	1551
[410]	1552	if (node->IsLeaf())
	1553	{
[408]	1554	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
	1555	float c = leaf->GetAvgRayContribution();
[411]	1556	int num = (int)(c*ratioPerLeaf + 0.5);
[408]	1557	// cout<<num<<" ";
	1558
[410]	1559	for (int i=0; i < num; i++)
	1560	{
[408]	1561	Vector3 origin = GetBBox(leaf).GetRandomPoint();
[419]	1562	/*Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
[408]	1563	Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
	1564	//cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
[419]	1565	rays.push_back(SimpleRay(origin, direction));*/
[408]	1566	}
	1567
[410]	1568	}
	1569	else
	1570	{
[419]	1571	VspKdTreeInterior *in =
	1572	dynamic_cast<VspKdTreeInterior *>(node);
[408]	1573	// both nodes for directional splits
[419]	1574	tstack.push(in->GetFront());
	1575	tstack.push(in->GetBack());
[408]	1576	}
[406]	1577	}
	1578
[411]	1579	return (int)rays.size();
[406]	1580	}
	1581
	1582
[410]	1583	float VspKdTree::GetAvgPvsSize()
[406]	1584	{
[408]	1585	stack<VspKdTreeNode *> tstack;
[419]	1586	tstack.push(mRoot);
[406]	1587
[408]	1588	int sumPvs = 0;
	1589	int leaves = 0;
[410]	1590
	1591	while (!tstack.empty())
	1592	{
	1593	VspKdTreeNode *node = tstack.top();
	1594	tstack.pop();
[408]	1595
[410]	1596	if (node->IsLeaf())
	1597	{
[408]	1598	VspKdTreeLeaf leaf = (VspKdTreeLeaf )node;
	1599	// update pvs size
	1600	leaf->UpdatePvsSize();
	1601	sumPvs += leaf->GetPvsSize();
	1602	leaves++;
[410]	1603	}
	1604	else
	1605	{
[408]	1606	VspKdTreeInterior in = (VspKdTreeInterior )node;
	1607	// both nodes for directional splits
[419]	1608	tstack.push(in->GetFront());
	1609	tstack.push(in->GetBack());
[406]	1610	}
	1611	}
[408]	1612
[410]	1613	return sumPvs / (float)leaves;
[418]	1614	}
	1615
	1616	VspKdTreeNode *VspKdTree::GetRoot() const
	1617	{
	1618	return mRoot;
	1619	}
	1620
[419]	1621	AxisAlignedBox3 VspKdTree::GetBBox(VspKdTreeNode *node) const
[418]	1622	{
[419]	1623	if (node->mParent == NULL)
	1624	return mBox;
[418]	1625
	1626	if (!node->IsLeaf())
[419]	1627	return (dynamic_cast<VspKdTreeInterior *>(node))->mBox;
[418]	1628
[419]	1629	if (node->mParent->mAxis >= 3)
	1630	return node->mParent->mBox;
[418]	1631
[419]	1632	AxisAlignedBox3 box(node->mParent->mBox);
	1633	if (node->mParent->mFront == node)
	1634	box.SetMin(node->mParent->mAxis, node->mParent->mPosition);
[418]	1635	else
[419]	1636	box.SetMax(node->mParent->mAxis, node->mParent->mPosition);
	1637
	1638	return box;
[418]	1639	}
	1640
	1641	int VspKdTree::GetRootPvsSize() const
	1642	{
	1643	return GetPvsSize(mRoot, mBox);
	1644	}
[419]	1645
	1646	const VspKdStatistics &VspKdTree::GetStatistics() const
	1647	{
	1648	return mStat;
[420]	1649	}
	1650
	1651	void VspKdTree::AddRays(VssRayContainer &add)
	1652	{
	1653	VssRayContainer remove;
	1654	UpdateRays(remove, add);
	1655	}
	1656
	1657	// return memory usage in MB
	1658	float VspKdTree::GetMemUsage() const
	1659	{
	1660	return
	1661	(sizeof(VspKdTree) +
	1662	mStat.Leaves() * sizeof(VspKdTreeLeaf) +
	1663	mStat.Interior() * sizeof(VspKdTreeInterior) +
	1664	mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
	1665	}
	1666
	1667	float VspKdTree::GetRayMemUsage() const
	1668	{
	1669	return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
[419]	1670	}

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

Download in other formats: