Archived

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

Quake 3 BSP and Collision Detection

This topic is 5589 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
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
Guest Anonymous Poster
Excuse me, I didn''t write well.

What I wanted to say was:

distance = DotProduct(-->SPHERECENTER<--,PlaneNormal) - PlaneDistance
If distance < -radius, the sphere is beyond the plane.
If -radius <= distance <= radius, the sphere is touching the plane.

That''s what I am using in my code, and it seems to be working.

But why???, if you said I need to use a vector from a point in the plane to the sphere, not the sphere''s center directly.

In the other way, I can''t test all the vertices of the sphere against the brush''s planes, just because I don''t have any sphere vertex, just its center and radius.

Share this post


Link to post
Share on other sites
Excuse me, I didn''t write well.

What I wanted to say was:

distance = DotProduct(-->SPHERECENTER<--,PlaneNormal) - PlaneDistance
If distance < -radius, the sphere is beyond the plane.
If -radius <= distance <= radius, the sphere is touching the plane.

That''s what I am using in my code, and it seems to be working.

But why???, if you said I need to use a vector from a point in the plane to the sphere, not the sphere''s center directly.

In the other way, I can''t test all the vertices of the sphere against the brush''s planes, just because I don''t have any sphere vertex, just its center and radius.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
hey, it''s the french anonymous poster...thanx for the advice but can you write your code to find the brushes to test, because i''ve some trouble with it...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by MigPosada
Excuse me, I didn''t write well.

What I wanted to say was:

distance = DotProduct(-->SPHERECENTER<--,PlaneNormal) - PlaneDistance
If distance < -radius, the sphere is beyond the plane.
If -radius <= distance <= radius, the sphere is touching the plane.


That makes sence, sorry, I wasn''t trying to be uptight, I just didn''t understand why you were using the radius.

quote:
Original post by MigPosada
That''s what I am using in my code, and it seems to be working.

But why???, if you said I need to use a vector from a point in the plane to the sphere, not the sphere''s center directly.



Here''s why it works and here''s why you need to correct it. The Plane''s normal can be used on any point on the plane. However, the Normal itself is relative to the plane as local units. What I''m trying to say is that the Vector measures direction. This direction can be measured from any point, but is represented as extending from the (0,0,0) origin. It is represented as extending from this point, any point on the plane is translated to the origin to do this calculation and all we are concerned about is the direction. You can move vectors to any point in space, as long as you keep them pointing in the same direction and same length. The normal is relative to the plane.

Your radius is also measured from the origin, but it is not relative to the plane like the normal vector is. It is relative to the origin. If you drew a vector from the origin to the sphere''s center, then moved it''s vector to be with repect to the plane, it would actually shift the sphere closer or farther to the plane, depending on the plane''s distance from the origin. You have to measure the sphere from plane to get the distance with respect to the plane. After you get this relationship correct, you can move the vector anywhere, and it would represent the direction and displacement the sphere is from the plane.

Your test is passing because your plane runs through or close to the origin. Try using a plane whose equation is y = 20 and then try the calculation. You should see some erradict behavior.

Share this post


Link to post
Share on other sites