• ### Popular Now

• 12
• 12
• 9
• 10
• 13

#### Archived

This topic is now archived and is closed to further replies.

# finding planes crossed using a BSP tree

This topic is 5390 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've been working on an iterative approach to my BSP collision detection. Right now I am trying to find what planes the start and endpoints span (if they are not in the same leaf). If worse comes to worse I will implement this recursively (which in all honestly does make more sense in this case). However I've put many attempts into this approach and I would like to have some assistance. I'm not trying to 'reinvent the wheel', I've just been implementing it the way I saw the problem. The first step I take is I find the closest ancestor node shared between the starting and end leafs. The ancestor node is the first leaf that is spanned by the start and endpoints(assuming the start and end leafs are not the same). I go from the startleaf up the BSP tree (traversing nodes using precalculated parent node indices) to the ancestor node tagging all of the planes crossed(they are stored in an std::vector). I then go from the endleaf up the bsp tree to the ancestor again tagging the planes that are crossed. I then calculate the fraction from the starting point to the plane (minus EPSILON units) and store these fractions in another std::vector, then sort them in ascending order, then check each move for a collision detection. I know it sounds like I've done a lot of extra traversing and such, but I've trimmed things down so its not as bad as it seems, and Im solely focusing on getting the algorithm working. if anyone can point out any flaws to me, well, you'll be saving me. I'm going to put the relevant code in another post EDIT: EDIT: I've also made a post about it here at gametutorials.com, if you think you see something I've been doing wrong read this post to make sure no one else has already told me about it: http://www.gametutorials.com/forum/topic.asp?TOPIC_ID=6581 [edited by - Shadow12345 on June 18, 2003 12:12:31 PM]

##### Share on other sites
Here is the code that actually finds the planes crossed:

Vector3		BSP::Trace(Vector3 *start, Vector3 *end){	int	i = 0; 	int	w = 0;	int	startleaf = 0;	int	endleaf = 0;	float	startdist = 0;	float	enddist = 0;	bool	ancestorfound = false;		int		ancestor = -1;	float	Fraction;	//finds subtree (ancestor) node as well as start leaf	while(i >= 0)	{		startdist = DotProduct(start, &mpPlanes[mpNodes[i].plane].vNormal) - mpPlanes[mpNodes[i].plane].d;		enddist	  =	DotProduct(end, &mpPlanes[mpNodes[i].plane].vNormal) - mpPlanes[mpNodes[i].plane].d; //wasteful 		if((startdist >= 0 && enddist < 0) || (startdist < 0 && enddist >= 0))		{			if(!ancestorfound)			{				ancestor = i;				ancestorfound = true;			}		}		if(startdist >= 0 )		{			i = mpNodes[i].front;		}		if(startdist < 0)		{			i = mpNodes[i].back;		}	}	startleaf = -(i+1);		if(!ancestorfound) //start and end are in the same leaf	{		endleaf = startleaf;		Fraction = CheckLeafForCollision(startleaf, start, end);		if(Fraction < 1)			return	*start + ((*end - *start) * Fraction);		else			return	*end;	}	else	//start and end are not in the same leaf so they must span some planes (****!)	{		int	i, x;	//counters		float	startdist, enddist;		std::vector<float>		Segments; 		std::vector<int>		PossiblePlanes;					w = mpLeafs[startleaf].parent;		PossiblePlanes.push_back(w);		//this should be ridiculously fast		while(w != ancestor)		{			w = mpNodes[w].parent;			PossiblePlanes.push_back(w);		}			//since we never found it before, we must now find the endleaf		i = ancestor;		while(i >= 0)		{			enddist = DotProduct(end, &mpPlanes[mpNodes[i].plane].vNormal) - mpPlanes[mpNodes[i].plane].d;			if(enddist >= 0)			{				i = mpNodes[i].front;			}			if(enddist < 0)			{				i = mpNodes[i].back;			}		}				endleaf = -(i + 1);		w = mpLeafs[endleaf].parent;		PossiblePlanes.push_back(w);							while(w != ancestor)		{			w = mpNodes[w].parent;			PossiblePlanes.push_back(w);		}		//loop through each possible plane		//if we span the plane, create a segment from start to plane		for( i = 0; i < PossiblePlanes.size(); i++)		{			tBSPNode	*tempNode = &mpNodes[PossiblePlanes[i]];			tBSPPlane	*tempPlane = &mpPlanes[tempNode->plane];			startdist = DotProduct(start, &tempPlane->vNormal) - tempPlane->d;			enddist	  = DotProduct(end, &tempPlane->vNormal)   - tempPlane->d;			//we span this plane			if((startdist >= 0 && enddist < 0) || (startdist < 0 && enddist >= 0))			{					if(startdist < enddist) //startdist is negative				{					float	percent = startdist - EPSILON / (startdist - enddist);					if(percent < 0)						percent = 0;					if(percent > 1)						percent = 1.0f;					Segments.push_back(percent);				} 				else	if(startdist > enddist) //startdist is positive				{					float	percent = startdist + EPSILON / (startdist - enddist);					if(percent < 0)						percent = 0;					if(percent > 1)						percent = 1.0f;					Segments.push_back(percent);				}				else //this can only happen if they are exactly equal to each other				{					float	percent = 1.0f; 					Segments.push_back(percent);				}			}		}		//sort all of the percents in ascending order		int	sm; //smallest element				for(i = 0; i < Segments.size(); i++) 			{				sm = i;				for(x = i; x < Segments.size(); x++)				{					if(Segments[x] < Segments[i])					{						if(Segments[x] < Segments[sm])							sm = x;					}				}					//Swap element i with element small (w) because element i is the smallest in the list 					float	temp = Segments[i];					Segments[i] = Segments[sm];					Segments[sm] = temp;			}			for(i = 0; i < Segments.size(); i++)			{				trace << Segments[i] << "\n";			}			trace << "*" << "\n";	}	return	*end; }

thanks again to anyone who gives me any insight

[edited by - Shadow12345 on June 18, 2003 12:08:50 PM]