Archived

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

GyCot

collision detection

Recommended Posts

for my collision i am doing the brute force route and checking each individual face (after bouding box checks and the like to clean off the riff raff). Anyway, what i am left with is 3 points in space that make a face, the plane those points make, and the collision point on that plane where my vector tries to cross it. My main problem then, is there a nice easy way to check to see if the point is within the triangle? I first thought about using each edge of the triangle to make a line, which would split the plane in two, and then I could see if the collision point was on the "inner" half of the plane for all three, and thus inside the triangle. This, of course, would be a pain to impliment. Any help would be great. oh yeah, and this is all with direct3d. pity me.

Share this post


Link to post
Share on other sites
ok, originally i planned on doing a huge fatty collision detection where i first make a bounding box and check to see if it goes through it, then i begin checking all the faces by seeing if the face is pointed toward the user or if we are looking at the backside of the plane (and thus don't need to worry), then i see if the user vector actually reaches the plane, and if all that looks like collision, then i check to see if it really connects to the plane of the face in the defined triangle of the face.

SUDDENLY i feel its all too much. Really, what if all I did was make the bounding box, check it, and if a collision is detected, make a bounding box for each face and see if it crosses any of those tiny bounding boxes? The more polygons the longer to check, but also the better precision. sure, its not going to be a perfect collision detection, but it looks like it would run a LOT faster, plus I get to take advantage of those nice function the directx8 SDK came with, like computeboundingbox and boxboundprobe.

Seriously, does this make any sense? or am i only desperate for an easy way out?

now if only i could figure out why the box probe won't work with a plane....

Update: diagonal walls are wusses! I suppose that is the argument against, sure you can do small detail and straight lines, but thats about it, no curved walls, no sloped floors, nada.

Edited by - gycot on October 31, 2001 2:21:50 PM

Share this post


Link to post
Share on other sites
Ive heard of people using spheres to check bounds. Say there is a sphere that contains the object.. say it''s a humanoid... then there would be a sphere that contained each of the body parts. upper arm, lower arm, head, torso etc. and collision detection could be performed on them.

I think D3D8 has a method for computing intersections between a plane/point (not sure) and a point with a radius (definition of a sphere).

Share this post


Link to post
Share on other sites
Spheres are a good way to do collision on your objects because...

1) Fast sphere to sphere collision.
2) Relatively easy to do Sphere to poly checks against landscape.
3) Does not have the mine field of mathematical inaccuracy issues that you can get from poly to poly collision (just think what issues you can get from maths rounding on a plane equation. If your are testing polys - which are infinitly thin - then even the slightest rounding error on a plane equation can provide enough of a gap for an infinately thin poly to slip through).
4) Very few spheres needed to make a good enough shape approximation of your model (a car could be modeled quite well with 10 spheres).
5) Scaleable - One sphere covers the whole model, once collision of this shere is detected then you go to the next level. As many levels as you like.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
> Spheres are a good way to do collision on your objects
> because...

> 1) Fast sphere to sphere collision.
> 2) Relatively easy to do Sphere to poly checks against
> landscape.

Only because it''s a gross simplification of more generalised collision handling. Compare dropping a tennis ball and a ruler on a flat surface. The maths describing the ruler is more complex because the behaviour is more complex. Spheres are only good for very simple objects/situations.

> 3) Does not have the mine field of mathematical inaccuracy
> issues that you can get from poly to poly collision (just
> think what issues you can get from maths rounding on a plane
> equation. If your are testing polys - which are infinitly
> thin - then even the slightest rounding error on a plane
> equation can provide enough of a gap for an infinately thin
> poly to slip through).

This is avoidable with a robust collision detection system. In particular you can avoid such rounding errors by always doing the same sums the same way, e.g. when doing plane-point tests always use the same description of the plane and point: don''t calculate the same point two different ways for two different edges.

> 4) Very few spheres needed to make a good enough shape
> approximation of your model (a car could be modeled quite well
> with 10 spheres).

But this works very poorly. The result is a car with non-straight sides, so if an object hits the car the angle of rebound will seem to randomly depend on where the hit was. Or you could use spheres to draw the car: at least then the collisions will be accurate, but it will look like nothing like a real car.

> 5) Scaleable - One sphere covers the whole model, once
> collision of this shere is detected then you go to the next
> level. As many levels as you like.

You can do this anyway: sort the objects, e.g. into a grid, to determine which are close, then do a quick bounding sphere check to see whether the objects are in range. Only if the bounding sphere''s overlap do tests on the polyhedra.

Share this post


Link to post
Share on other sites
well, there''s a very easy way to find out, if a point is within a triangle(as long as both are in the same plane).

i made a collision-detection which only uses: + - * /
no tan, cos , sin and stuff like this!
but i don''t know how to explain since my english is very bad!
;-)

Share this post


Link to post
Share on other sites
Spheres are perfectly good for the collision resolution you would want from most games.

The maths errors I was refering to were plane equation round-ups. Picture this, you have an infinitly small moving particle (ie, the vertex of a poly say) and you want to test this for collision with the level mesh. Now say you had a cylinder made from tris. Any mathmatical round-up/down at all on the plane equation calc for the tris will generate a gap (very small but a gap all the same). This can lead to snagging - where the particle manages to get through this game, but can not get back out.

This will then lead on to bodges, such as ''fattening'' the particle or boosting the size of the polys by a small factor.

Using spheres for collision could be the difference between 10 drone cars and 30 drone cars on screen.










Share this post


Link to post
Share on other sites