General Collision Detection

[sciwizeh]

I did a brief search of the forums, and didn't find anything on collision detection that was 1) this general, or 2) had this kind of question

I don't want bounding box! every place i look all game tutorials use bounding box, and that is not accurate enough for what i want to do. here is something that is an example i drew:

this is a simple image i drew added to one image twice and rotated 45 deg the second time. the bounding box for the original image is 64 square, the rotated one became 66 square, which is to be expected when rotating an image. with a bounding box collision the yellow dot would be colliding with the image, in a simple game that wouldn't be a problem, but for a more advanced game it would be quite a problem, especially with a more complex character or other in-game being.

if we make the problem 3D it becomes much more complex, say for example we extrude the black shape out of the screen, and make the yellow dot a sphere. bounding box would again be a very imprecise.

most things that i can find on the internet are either language or library specific (eg. allegro uses bit masks for such stuff but that's only 2D) about things like this and i want more general stuff, not even code, just the math/ background behind it.

NOTE: i have not studied calculus yet! (so please try to make it simple :) )

[Clockowl]

I think this comes down to:

Does it cross this line/face.

For a 3D-object you'd have to at least have a bounding box. When an other objects is IN the bounding box (easy to check) check if it hits one of the faces of your 3D object.

In 2D it's the same, but with lines. Use the bounding box to check if there are any objects near, then check the lines if one is being overlapped by another object.

(problems of course occur when the speed of the object that's incoming is so great that it'll "skip" the face/line. This happens in many commercial games too, so I don't think there's an easy solution for that).

[sciwizeh]

i agree that bounding box should be used as a fast check if anything is in the area.

how would using lines/faces work. if say an external library was used for detection how would it know about the actual construction of the objects to be checked,

also how does one check whether faces are colliding? mathematically speaking (again KIS please)

[Clockowl]

Tell them if they are within range...

Do a simulation in your head of 2 cubes having 8 vertices and 6 faces each. See if you can come up with any rules for collision.

PS:
The external library would have to know about the geometry of the object, the location of the object and the location/geometry of the objects it may collide with.

[sciwizeh]

ok, i'm not woring on anything 3D at the moment so i'll do some 2D tests with squares.

one of my main concerns is rotation, both how to detect collisions with rotations, and the physics involved when rotating objects collide (tired of not knowing calculus, without it i don't get the equations) but enough talk, i'll be back with (probably non-working) code that i will be sure to ask questions about

thanks for the advice

[Clockowl]

In 2D it's more or less simple no?

Check if one of the corners (read: vertices) pokes into the area of another square.

You can calculate the location of each vertex when you know the center of the square, it's length and it's rotation.

Do you know how to calculate the location of a vertex with that information?

[MattEvans]

For 2D point-in-convex or point-in-non-convex, see the crossing test on this page: http://www.erichaines.com/ptinpoly/. As its given there, that test will work in 2D only, for a 2D shape embedded in 3D, you have to project the point onto the plane of the shape first, if the projection is impossible, obviously the shapes don't intersect. The same theory should apply for polyhedra, the number of face/edge crossings determines the 'side' ( inside or outside ) that the point is on,

Of course, it becomes more difficult when you start incorporating different shapes to collide with ( i.e. not just polygon-against-point ).

Most shapes can be decomposed into more simple shapes. In your example, the shape could be decomposed into a pair of triangles, and to detect if triangles and other shapes intersect there are a number of popular methods.. If you can decompose into cuboids, spheres, tetrahedra, etc, ( rects, circles and triangles in 2D ) you'll be able to find existing optimized methods.

For generalized convex shapes, see below, but for generalized concave shapes, there aren't any efficient methods ( it's one of those 'difficult problems' in geometry ).

There also aren't effective generalized methods for converting any shape into the simplest decomposition of non-convex shapes, although there are certainly generalized triangulation routines. If you know the shapes involved before hand, you can either preprocess, or manually specify the bounding poly[gons|hedra].

My favorite method, at the moment, is to perform GJK on the Minkowski difference of two shapes... Basically this works with any pair convex shapes, representation of the shapes can be implicit, and it's fast because the alogirthm usually converges very quickly, but.. ( I think ) it only works with convex shapes, so you'd need to perform some kind of decomposition first.

Another generalized method is SAT ( separating axis theorem ). But again, this theorem only holds for convex shapes, so you have to decompose. SAT can get painful when two complex shapes ( with lots of faces ) are very close to each other.. you end up having to test hundreds of axes, but, there are optimizations. SAT with GJK is very, very fast =P

As you said, simple axis-aligned bounding boxes/spheres are generally used for pairwise culling before performing a more costly test, or to define rough periods for some other kind of optimization structure. ( K-tree, spacial hash, tilegrid, dimension reduction technique, etc, etc, etc ).

I'll leave you to work out /research which method(s) you'd prefer, if you want information on a specific method, let me know, I can probably dig up some links.

[MattEvans]

one of my main concerns is rotation, both how to detect collisions with rotations, and the physics involved when rotating objects collide (tired of not knowing calculus, without it i don't get the equations) but enough talk, i'll be back with (probably non-working) code that i will be sure to ask questions about

For rotated objects, you should pick a method that works with arbitrary orientations. For rotating objects, there aren't any general method for detecting the time-of-contact. For translating objects, there are methods for find the exact time of contact, namely conservative advancement for generalized shapes, or specific tests for certain shapes ( moving sphere vs sphere is a very nice algorithm, you can predict time-of-contact upto [ but not including ] a relative speed of "infinity" [ ignoring probable floating point innacuracy at those magnitudes >_> ] ).

A nice theory is as follows.. for any combination of moving shapes, you can treat the linear velocity ( translation ) as relative, that means that any test between one moving and one static object can be used to find time-of-contact for two shapes, by simply subtracting the velocity of one shape from the other.

Interestingly enough, form is relative to, and you can 'subtract the shape of one shape from the other'. This is the essence of the Minkowski difference operation. This means that any test between static shapes can be converted into a test between a point ( at the origin ) and the minkowski difference of the two shapes. Combining that, any test between a pair of moving shapes can be converted into a ray-cast from the origin to the minkowski difference in the direction of relative linear velocity.

Unfortunately, rotation ( angular velocity ) just aint relative in the same way. The best you can do ( apparently ) is constrain both shapes to a screw motion, although I've never tried this personally. I just subdivide time a little depending on the relative angular velocity, and treat relative rotation as short translations in an arc coupled with small instantaneous changes in orientation. Not perfectly accurate.. but, it mostly suficces.

The after rotation collision physics are 'ugly', but you can skirt around calculus since many collision response calculations are impulse-based, you provide the linear + angular velocity at time-of-contact along with some other things ( point of contact, normal of contact, mass, inertia tensor ), and you get back a new linear and angular velocity for the two shapes, it's easier than it sounds, this series is pretty good, but it doesn;t discuss actually detecting collisions anywhere, just the dynamics and kinematics : http://chrishecker.com/Rigid_Body_Dynamics, and see also: http://www.hakenberg.de/diffgeo/collision_resolution.htm ( although! most of the stuff in the second article can be avoided by calculating the angular velocity in terms of linear velocity at the point of contact ).

[sciwizeh]

In 2D it's more or less simple no?

Check if one of the corners (read: vertices) pokes into the area of another square.

You can calculate the location of each vertex when you know the center of the square, it's length and it's rotation.

Do you know how to calculate the location of a vertex with that information?

yes i do, that's just basic trig, although with java's coordinate system, being flipped over the X axis, trig is a little different than that of math class

so far my time has been split between month-before-college-starts stuff (trying to decide to change my schedule, mostly), and all of the other stuff i want to do. the time alloted to programming stuff was spent on an extensive Vector3D class in java. so i don't have much yet

@MattEvans: thanks for the details and links. i have already found http://chrishecker.com/Rigid_Body_Dynamics previously, and found it very interesting, but it is all about calculus, and confused me after a few pages (will be in Calculus this year). i wouldn't have thought of counting the amount of times a vector crosses edges of a shape. i haven't had time to look at the third link, but i will.

i have been trying to get an idea of the physics behind it from MyPhysicsLab and the rigid body collisions page.

if any of this hasn't given a clue, i want to write a good simulation, or even a physics engine (but that's for later) and i just want to get pretty close to accurate

[Clockowl]

Well I'd recommend you to start out simple. Use the bounding box, understand the mechanism behind it and then apply it on other "simple" objects such as spheres, piramids, etc. Once you've done all that, you'll know a lot more and, I think, be readier for finding a method that works with any 3D object.

[sciwizeh]

i can already do bounding box and spheres it's irregular shapes that i am concerned with