Sign in to follow this  

Quake3-style sphere-brush collision issue

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

In my engine I can load quake 3 .bsp files, and I implemented sphere-brush collision detection with the help of this tutorial: http://www.devmaster.net/articles/quake3collision/ I am discarding all the BSP stuff and just storing the brushes in a big array. My system seemed to work with all of the quake 3 levels I tested. Now I downloaded GTKRadiant, created some simple geometry, and discovered a big problem I have with my system. Say that I have two brushes: a cube, and an adjacent prism, so I can reach the top of the cube walking on the prism. This is a side view of it:
  
   ______
  /|     |
 / |     |
/__|_____|
I discovered that if I try to get to the cube walking from left to right, I cannot reach the top of the cube: i remain strucked at the end of the prism, just a bit before reaching the cube. This is what goes on: The player goes right, I detect the collision with the prism and slide the player velocity along the plane, so it is going up-right now, then I check all the brushes again and this time I detect a collision with the left plane of the cube, that stops the player. In theory I should not collide with the cube when I modify my velocity sliding on the prism, but I do, because basically when I check for a collision with a brush, I'm actually testing a ray against an "inflated" brush, extending all the planes by the sphere radius (This is what the tutorial does, anyway). But doing this, I'm detecting non-existant collisions with, for example, a cube edge! If you aren't following me, think of a cube: if I inflate it by 1 unit, this means that I move the up plane by 1 and the left plane by 1, but the top-left corner was actually moved by ~1.4! The proper way, I think, would be to use a cylinder for brush edges and a sphere for brush corners, but this is not possible due to the structure of brush data, wich is just an array of planes. I wonder if and how Quake3 solves this problem, I'm probably going to take a look at the source code. This is my source:
bool CBrush::TraceSphere( const D3DXVECTOR3& Start, const D3DXVECTOR3& End,
						 float SphereRadius, float* pDistance, D3DXPLANE* pPlane )
{
	float EnterDistance = -1.0f;	// Farthest distance the line enters a plane [-1, 1]
	float LeaveDistance = 1.0f;		// Closest distance the line exits a plane [-1, 1]

	for( unsigned int i = 0; i < m_Planes.size(); ++i )
	{
		float StartDistance = D3DXPlaneDotCoord( &m_Planes[ i ], &Start ) - SphereRadius;
		float EndDistance = D3DXPlaneDotCoord( &m_Planes[ i ], &End ) - SphereRadius;

		// If both Start and End are outside the plane, the line is not intersecting
		if( ( StartDistance > 0.0f ) && ( EndDistance > 0.0f ) )
		{
			return false;
		}

		// If both Start and End are inside the plane, ignore the plane
		if( ( StartDistance <= 0.0f ) && ( EndDistance <= 0.0f ) )
		{
			continue;
		}

		// If we get here the line is intersecting the plane

		// Check if we are entering the plane
		if( StartDistance > EndDistance )
		{
			// Compute the distance until we enter the plane [-1,1]
			float Dist = StartDistance / ( StartDistance - EndDistance );

			if( Dist > EnterDistance )
			{
				EnterDistance = Dist;
				if( pPlane )
				{
					( *pPlane ) = m_Planes[ i ];
				}
			}
		}
		else
		{
			// Compute the distance until we leave the plane [-1,1]
			float Dist = StartDistance / ( StartDistance - EndDistance );

			if( Dist < LeaveDistance )
			{
				LeaveDistance = Dist;
			}
		}
	}

	if( LeaveDistance < EnterDistance )
	{
		// We leave the brush before entering it. No collision.
		return false;
	}
	else
	{
		// Output the distance until the line touches the brush
		if( pDistance )
		{
			( *pDistance ) = EnterDistance;
		}
		return true;
	}
}



Share this post


Link to post
Share on other sites
Quote:

float StartDistance = D3DXPlaneDotCoord( &m_Planes[ i ], &Start ) - SphereRadius;
float EndDistance = D3DXPlaneDotCoord( &m_Planes[ i ], &End ) - SphereRadius;


Subtract the plane's distance to accurately compute the distance to the plane.

Share this post


Link to post
Share on other sites
Quote:
Original post by tthibault

Subtract the plane's distance to accurately compute the distance to the plane.


The plane equation is ( ax + by + cz + dw = 0 ), and D3DXPlaneDotCoord() computes ( a*x + b*y + c*z + d*1 ), so I'm already doing this.


This is an image that tries to show the problem. By just adding the sphere radius to the plane distances, I'm actually testing a ray against the red and green brushes, and I get struck in the top left red corner..
Anyway I'm wondering why I don't get struck in the top green corner when I move backwards from the top of the cube..

clicky

[Edited by - Arcibald Wearlot on September 29, 2006 12:02:36 PM]

Share this post


Link to post
Share on other sites
I don't know about Quake3, but the earlier versions of the Quake engine generated the inflated collision hull using a bounding box. Imagine replacing each vertex of the brush with a cube and then connecting these cubes, rather than just moving each face out by some amount. In the case of your triangular brush it'd create a five-sided collision brush with axis-aligned facets on top (at the same level as the top of the cube's collision brush) and left.

Edit: If you're going to use a sphere, then using cylinders for the edges and spheres for the corners would indeed be the correct solution. I suppose the easiest place to find source code that generates this data from the brush planes is the level editor (Q3radiant), as it needs to do that in order to display/edit the brushes.

Share this post


Link to post
Share on other sites
I believe this is because technically just extruding the brushes by some amount and then checking against a point is not the correct way to detect collisions ( its fast however ). I guess they just solved it in quake by designing the levels with this in mind. Maybe their stepping code can also prevent getting stuck somewhere.
I never implemented this correctly, but I heard the "Minkowski Sum" plays a role there. Google for it if you are interested ;)

Edit: Ahh I just found the paper where I read this: http://www.melax.com/bsp/melaxbsp.pdf

Share this post


Link to post
Share on other sites
Indeed, the brushes in Quake levels have been extruded assuming the player is represented as an axis aligned cube. In fact, the bevel planes are part of the Minkowski sum between cube and convex brush, so this mtehod creates an explicit representation of the Minkowski-sum between the brush and a cube. If you want to use a sphere, or other convex primitive you will need to refine this method. Creating all bevel planes for a sphere is impossible (unless you tesselate the sphere, but that would easily result in a very high number of bevel planes).

I provide an open source implementation of a general solution to this problem. In the Bullet collision detection library there is a BspDemo that loads Quake .bsp files, and converts the brushes into convex hulls. All kind of collision shapes can collide (using rigid body dynamics) or slide (using the continuous collision detection query that returns the time-of-impact).

This paper by Gino van den Bergen explains this concept:
http://www.dtecta.com/papers/jgt04raycast.pdf
The Bullet library includes the implementation between arbitrary pairs of convex objects, including cylinder, convex polyhedron, cone, sphere etc.
See http://www.continuousphysics.com/Bullet/BulletFull/classbtSubsimplexConvexCast.html
However, this might look like overkil when doing sphere-against-quake level. An easier approach is to convert all to triangles, and do the much easier sphere-versus-triangle.

Erwin
http://bullet.sf.net

[Edited by - erwincoumans on October 1, 2006 1:03:09 PM]

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this