• Advertisement

Archived

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

Collision detection - what's so difficult?

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

Hi! I''ve seen in the tutorial request topic that many people want a tutorial on collision detection. But I think collision isn''t too hard. Imagine you have a brush (a closed 3d object with several polys), for example a cylinder. Now you just calculate the plane for every polygon of your brush. Your plane has 4 paramters: A, B, C, D A, B and C are the components of the plane''s normal, D is the distance of the plane along this normal. You want to check now, if a player in a 3d shooter is walking into this brush. That''s really simple now: The player has a bounding sphere. The center of this sphere is just the player''s position. Then you need to define a radius for the sphere which describes the player''s size. Ok, now you simply check the distance of the sphere''s center to every plane by calculating: d = A*sx + B*sy + C*sz + D If the distance to any of the planes is < -radius then the sphere is colliding with the brush. Hope that helps you cu

Share this post


Link to post
Share on other sites
Advertisement
Yes, it is simple if you use a brute-force method and collision spheres. The difficult part is implementing real-time polygon-accurate collision, which returns the collision point for the physics simulation.

-Jussi

Share this post


Link to post
Share on other sites
Yes, might be that''s brute force, but it works. And even Quake 3 uses this technique. If you want a ray-poly collision detection
then please look at the new topic I''ve posted.

cu

Share this post


Link to post
Share on other sites
hi,
i''ve tried months ago to implement a collision detection based on a sphere-plane collision, but i ran into a big problem : the formula d=Ax+By+Cz+D is the formula of an infinite plane... and poly are not infinite plane. How do you perform this test?!!
btw i prefer bounding boxes because you can easily make a hierarchical tree with acurate collision. For example let''s take a group of monsters. Those monsters have bodies : they have heads, chests, arms and legs. First perform a test for the whole group. If we detect a collision, perform a test for each monster. For the first we detect the collision, perform the test for each part of his body.
This method is easy to implement, fast and enough acurate for games (but not for medical simulation )
lunasol

Share this post


Link to post
Share on other sites
quote:
Original post by LaBasX2
Yes, might be that''s brute force, but it works. And even Quake 3 uses this technique.


Well, where did you hear that one from?

-Jussi

Share this post


Link to post
Share on other sites
Hi!

If you look at the q3 bsp file structure you can find a lump
called brushes (check out www.planetquake.com/aftershock). These brushes contain a list of planes. When I coded a little q3 map viewer I tried to handle the brushes as I described in my first
post. And it worked perfectly, even for curved surfaces. So that''s why I think (well, actually I''m quite sure) that q3 uses
this technique. Furthermore I''ve seen several quake2 viewers which use brushes in the same way.

cu
LaBasX2

Share this post


Link to post
Share on other sites
hi lunasol,

I''ve read your question. In fact, planes are infinite. That''s why you have to use brushes. A brush is an object and it needs
to be closed, that means you can''t look into the object from
outside. This object consists of planes. And I guess you know,
when 2 planes are not coplanar, they will intersect. If you take
all the intersections of the planes defining a brush, you can find an object. The intersection points of the planes are the vertices used to convert a brush to polygons. So you can make
a limited objet out of a set of infinite planes. And that''s why
the collision test works.
Well, that''s a little difficult to explain so excuse me if I can''t help you more.

cu

Share this post


Link to post
Share on other sites
Unless you are doing something more than calculating the distance of the sphere to the planes, your technique does NOT work.
You have to take into account the real boundaries of the polygons, and not just their planes.


Give me one more medicated peaceful moment.
~ (V)^|) |<é!t|-| ~
ERROR: Your beta-version of Life1.0 has expired. Please upgrade to the full version. All important social functions will be disabled from now on.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Well I don''t know why this technique shouldn''t work. I''ve read about it in several tutorials and as I mentioned quake2 and
quake3 are using it, too. I think that''s the fastest and best
way of checking if the player runs into a wall. Checking every polygon for a ray-collision is much too slow. I tried it in one of my engines and it costed me some frames! And why do you think are precalculations of lightmaps so slow? It''s just because of these damn slow ray-tri intersection tests, I got to know that when writing a lightmap compiler. Disabling the test speeds it up a hundred times.

So what do you think doesn''t work? All I can say is that I tried it and for me it worked. I was walking through a quake3 level with my viewer and using the brush technique I didn''t manage to walk into any wall! So if you have a better and faster way of collision detection, tell me.

cu

Share this post


Link to post
Share on other sites
the thing is we should call it like it is and thats collision + response. its no good knowing youve collided without knowiung what u have to do afterwards

Share this post


Link to post
Share on other sites
What about if you want to do a collision detection with a wall? I don''t really want to store every little pixle in a map and I want more accuracy than just a couple of spheres, or is that how it is done, the vertcies of a wall then calculate every 20 or so pixels and chuck in an invusible sphere?

-Owen

Share this post


Link to post
Share on other sites
hi!

Why should you have to store every pixel of a wall? You just
have to store the polygons and the planes of the polygons.

What is a wall in a usual 3d-shooter? Mostly it''s some sort of
a block. So you can define this wall with 6 planes. Now you just check the distance of a point to every plane. If it is always smaller than zero, this point is sure to be in the block.

You don''t have to involve any pixels! Of course you can''t use this technique for a raytracer, but for a shooter à la quake, where you want to know if the player is running into a wall, this thing works like hell!

cu

Share this post


Link to post
Share on other sites
quote:
You don''t have to involve any pixels! Of course you can''t use this technique for a raytracer, but for a shooter à la quake, where you want to know if the player is running into a wall, this thing works like hell!


Exactly, it only works for FPS-type games. Most of us are not making those.

-Jussi

Share this post


Link to post
Share on other sites
quote:
Original post by LaBasX2
What is a wall in a usual 3d-shooter? Mostly it''s some sort of
a block. So you can define this wall with 6 planes. Now you just check the distance of a point to every plane. If it is always smaller than zero, this point is sure to be in the block.



That sounds correct, however, that''s not how you described it in your original message .
This technique would work fine for collision detection with polygonal objects.




Give me one more medicated peaceful moment.
~ (V)^|) |<é!t|-| ~
ERROR: Your beta-version of Life1.0 has expired. Please upgrade to the full version. All important social functions will be disabled from now on.

Share this post


Link to post
Share on other sites
The example of LaBasX2 is good but as lunasol said, is good to check the infinite plane collision detection of a triangle.
I used it im my engine some weeks ago and it works correctly but the problem is that the collision did occur also if I''m passing trought a wall that is finished! This means that the code check the collision for a sphere with an ipotetical infinite plane of a triangle and this is not good at all!
LaBasX2 in response of the problem explained by lunasol, wrote the meaning of why it works anyway but I really didn''t understand it at all.
What I know is that once a sphere-infinite plane collision did occur, we have to build three perpendicular planes from the three edges of the triangle and the calculate the distance from the sphere to these three new planes and if the sphere is inside ALL of them then a REAL collision did occur.

Share this post


Link to post
Share on other sites
<tr valign="top">
<td bgcolor="#333333">
Selkrank
</td>
<td bgcolor="#333333">

quote:
Original post by LaBasX2
If you take all the intersections of the planes defining a brush, you can find an object. The intersection points of the planes are the vertices used to convert a brush to polygons. So you can make
a limited objet out of a set of infinite planes>

Ok i get it. If i understand i have to perform this for each poly and for each frame (let''s say that''s the objects can move) mmmh... it seems to me that this is a very CPU-intensive method. Let''s go buying a PIII-733

lunasol



</td>

Share this post


Link to post
Share on other sites
hi!

As I see we can all come together by saying that the technique I described is only suitable for FPS-games.

Lunalsol said the speed would be to slow...
Well if you want to check a hundred of spheres that''s true. But you can easily speed up things by organizing your polygon data with bsp-trees or octrees (I prefer them). Using trees should reduce your tests to some polygons.

cu
LaBasX2

Share this post


Link to post
Share on other sites
yes it''s can be very simple say like this but
for the dummies like me, some code with explains
could be very useful .
ciao
al

Share this post


Link to post
Share on other sites
Add me to the dummie group. I can do 2D collision, 3D bounding spheres, but when it comes to BSP, Portal, I''m lost. I''d like to post a note about this because YES, I get tons of requests on this topic. If someone is willing to write a very easy to understand, commented collision demo that works (no sliding through walls, etc), using the code from my site as base code, I will pay $50 for the code. I know it''s not much, but it''s out of my pocket, and the could would help everyone out! I''ll convert it into a tutorial once I''ve had a chance to go through the code, and figure it out


Share this post


Link to post
Share on other sites
Quake3 didnt use sphere collision detection, it uses bounding box hull checks..sphere detection is pretty ugly when it comes to walking around on ledges and over uneven geometery - check system shock 2 or thief - horrible physics feel there (good games though)

If you jump about in Quake1-3 and Half Life you can pull pixel perfect accurate jumps and ''bunnyhop'' about the place from jump to jump - with sphere collision games u can often become ''stuck'' in geometery and have to wiggle your way out by randomly spamming the jump button and moving in all directions - my 2d engine so far uses raycasting to check the movement and collision of objects (and correct them) and it feels pretty fluid at the moment

Share this post


Link to post
Share on other sites
It''s not often a boundingsphere, or even a convex hull test is usefull for anything but an early rejection. Once you get a collision for the spheres, you still need to get down on a per-polygon level. You''d also want to have the exact feature-set of the collision, and the penetration-depth. And this is where the hard part comes in.
Gino van der Bergen wrote a very good book on the subject.

Share this post


Link to post
Share on other sites

  • Advertisement