Jump to content
  • Advertisement

Archived

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

MigPosada

Quake 3 BSP and Collision Detection

This topic is 5894 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

I am trying to make a FPS using my own engine (still at works), but using Quake 3 BSP and MD3 model files. Because I was not sure of how Id people did the collision detection using the brushes stored in the BSP file, i took an easy solution: to use an external library. I liked the easiness of the ColDet free library, and worked fine creating a big Collision Model for the entire map. Then i move to the next step: collision response. The first thing i wanted was to slide (i''m not sure of how to describe it) through the walls and not just stick on them. I found a nice algorithm to do this using the plane equation of the wall/floor, but i found a problem!: ColDet only returns me a single triangle after the collision detection (i''m using spheres), so i have problems when colliding against more than one plane!. 1) Must I check the collision detection (and then the response) against each face in the BSP map?? 2) Or how does it work with the brushes? 3) Each brush only stores the plane equation of each side, is it really the only thing needed to do collision detection??? 4) If it is, how do I know WHICH side of the brush must be used to compute the response?

Share this post


Link to post
Share on other sites
Advertisement
Hey!!, what''s happening on here???
I am not clear (i speak spanish, not english).
OR
Nobody wants (or knows) how to help me.

Please let me know, at least, why I don''t have any answer in this forum.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
sorry but i can''t answer your question, but maybe you can help me... i''m trying to understand what brushes are, and how to use them in collision detection, but i don''t understand very well how to use them(i''m french and bad at english)

if you can explain me some of this, it would help....
for your problem, here is a link with a paper about detecting collision and sliding(sphere detection) and it works well

http://www.fluidstudios.com/publications.html

bye!

Share this post


Link to post
Share on other sites
In answer to question 3 the plane is all that you need to do collision detection. I have never done this myself so Im not sure how id go about doing it but I think this is one way to do it:

Use Bounding Cylinders/Spheres for your players (something with a radius anyway) The use the plane equation like so

Distance = Ax + By + Cz + D;

where A,B and C are the planes normal, D is the distance from the origin(I think) and x,y and z are the coordinates of the center of the bounding sphere. If distance is less than or equal to the radius of your bounding cylinder then there is a collision.

There could be mistakes in there as like I said I have never done it and my maths isnt that great anyway.

Hope you find this helpful

Share this post


Link to post
Share on other sites
Thanks Grambo. I have been testing, and yes, the plane is the only thing i need to detect collisions that way.

As an answer for Anonymous Poster, each brush is just a convex shape (a box, for example), but in the BSP file only the numbers of the plane equation (Ax + By + Cz -D = 0) of each side are stored, not more.

What i had to do was to check the center of the sphere against each plane, getting the distance from it. If the distance < 0, the sphere passed through the plane; if the distance > radius (in any plane) then the sphere is not colliding at all with the entire brush.

I have written something like this:


    
// Sphere Collision with a brush

bool SphereInBrush(Vector * center, float radius, BSPBrush * brush)
{
BSPBrushSide * side;
BSPPlane * plane;
int count = brush->numOfBrushSides;
// Goes down from numOfBrushSides to 0.

while( count-- )
{
side = &BrushSides[brush->brushSide + count];
plane = &Planes[side->plane];
if( plane->normal.x * center->x +
plane->normal.y * center->y +
plane->normal.z * center->z -
plane->d > radius )
return false;
}
return true;
}


But i still have a problem. If i'm colliding with the brush, how do i know which plane (side) must be used to bounce from it??

[edited by - MigPosada on August 28, 2002 1:23:56 PM]

[edited by - MigPosada on August 28, 2002 1:25:59 PM]

Share this post


Link to post
Share on other sites
Im not sure if I am right but in that code you posted it looks like it would return after testing only one plane. Not only that but it would return after it found a plane that the player isnt colliding with.

Could be my mistake but I thought Id point it out in case I am right.

Anyway as for how to tell whitch plane you have to use to bounce off of, why dont you just have your detection function return a pointer to the plane that you were intersecting with and return NULL when no intersections were found, that way any you could still use an if to tell if there was a collision and then if one was found you could do all the calculations using the pointer that you got from the function.

Well, Im not sure if I understood your question right but if I did then that is what I would probably do.

Share this post


Link to post
Share on other sites
I am not checking if the sphere is colliding against one single plane.
A brush is a convex shape, defined by planes "surrounding" it. It is not enough to check if i''m colliding against one plane (remember, it''s an infinite plane, and the brush is in only one section of the world).
What i was doing is to see if the sphere is "beyond" or very near to the brush.

Please let me know if I''m wrong:
distance = DotProduct(SphereRadius,PlaneNormal) - PlaneDistance
If distance < -radius, the sphere is beyond the plane.
If -radius <= distance <= radius, the sphere is touching the plane.

So,
If my sphere is beyond (or touching) all the planes in the brush, the sphere is inside the brush.

My conclusion was: if I had only one plane in front of my sphere, but far enough (distance > radius), the sphere is not colliding with the brush at all, and neither is inside it.

Share this post


Link to post
Share on other sites
Well, I kind of forgot that planes were infinite so your code might not be wrong after all, sorry about that.

As for your problem, its late now and I cant really think much about anything right now, I might give it a bit of thought tommorow though if someone else doesnt come up with a response

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by MigPosada
Please let me know if I''m wrong:
distance = DotProduct(SphereRadius,PlaneNormal) - PlaneDistance
If distance < -radius, the sphere is beyond the plane.
If -radius <= distance <= radius, the sphere is touching the plane.

The Dot Product takes two vectors as inputs and spits out a scalar quantity. You can use this process to tell which side of the plane a point is this way:

Use the plane''s normal and dot it with a vector formed from a point on the plane and the closest vertex or point on the sphere to the plane. (or simply test all of the sphere''s verticies which would be easier and faster than calculating closest point)

* = Dot Product operator:
Dot(Vector1, Vector2) = ||Vector1|| * ||Vector2|| * Cos(Theta)

The Angle theta is measured from the normal as the 0 degree position. The COS is positive in the first and fourth Quandrants (both on face side of triangle) and the 2nd and 3rd quadrants yield a negative Cos(theta).

Zero is when the point is 90 degrees of the normal vector, or on the plane.

Since both the magnitudes of the vectors are always positive, the only number that can change the sign of the Dot product is the cosine of the angle. So if the dot product between the vector normal of the plane and a vector drawn from a point on the plane is positive, it hasn''t peirced the plane. If it is negative, it has. If it is zero, it is on the plane.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
correction:
* != Dot Product operator: it equals multiply
|| || = magnatude of the vector inside

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!