I'm working on a 3D game right now, and my engine is going to need to test collision for a few different collision types. Rays, Spheres, oriented boxes, non-oriented boxes, and cylinders. I'm not asking to be told what code to write for my engine, I just want to know a good starting point for learning to write the code myself. All I'm asking is what key concepts for testing collisions between different shapes, and how to push objects out of each other. I'm familiar with gravity, and force and all that, so that's really not what I need to know. I could easily push two spheres out of each other, and I could probably do the same with non-oriented boxes, but I'm not sure of where to start (as far as mathematics goes) for rays, oriented-boxes, and cylinders.

Thanks.

Start at Geometric Tools for papers and source code on how to do collision detection. Use Gaffer on Games for information on how to do numerical integration correctly for physics.

I think this is great and all, but I'm not looking for source code or tutorials. I just want to know what kind of mathematical concepts I should learn to be able to write algorithms myself.

Well, if you really don't want to use a free physics engine (there are lots there, and chances are yours won't be as good as they are), some things that you need to learn are: Kinematics, Forces, Kinetics, Collisions (detection and response), Vector math.

I know I need to know all these things. I'm not asking what I need to know to make a physics engine, I'm asking what I need to know to be able to write collision detection tests between different collision types. Specifically, what concepts of vector math should I know, and how do I use it? I know there's dot product, cross production and such, but how do I use those together to say, test where a ray collides with a plane? I'm sure I could do something similar to slope, and just project the ray to plane, and get that position, but I'd likely just brute force it. I'm sorry if I'm being confusing, but I'm just not entirely sure of how to ask this question without seeming really inexperienced.

When you know many words, what they mean, and how they can be used in sentences, you are able to create your own, proper, sentences. I'm basically asking what these "words" are, how I can learn what they mean and how to use them in "sentences". I hope that analogy made sense.

Say that you have a triangular pixel:
0 (1)


0 (2) 0 (3)

You need to find the normal of the pixel to use in collision detection, to see what angle an object is coming in from. You can create Two Vectors by taking the difference in the coordinates of the vertices:

0 (1)
a ^
/
0 (2) ------> 0 (3)
b

Take the cross product between "a" and "b" to find a normal (there are two of them).
N = a x b --------> Why?

The cross product has an interesting property which you are exploiting: the cross product between two vectors is always perpendicular (orthogonal) to the two source vectors.

Also: N = a x b = |a| |b| sin(x) x is the angle between the two vectors. You can exploit this too. This also means that if two vectors are parallel to each other, their cross product is zero.


Dot Product:

a * b = |a| |b| cos(x) x is still the angle between the two vectors. This means that if "a" and "b" are perpendicular to one another, their cross product is zero.

These are usually the geometric relations you exploit.


You care about Normals when you're dealing with regular kinematics. If you want to figure out how particles reflect or bounce when they hit a surface; you need to know the direction of the normal for the floor, this determines how the particles get deflected.

Something else: I haven't toyed around with this very much... however, it should be possible that instead of doing tradtional collision detection; you could use fields between the floor and the particles. You could design it such that a field is weak at a distance, but when the particles get very close to the source of the field, they interact; and you can have this dictate the physics of the system.

This idea either isn't used because no one has thought of it before... which is unlikely. Or it isn't used because it may be taxing on the poor cpu... which is more likely.

That's the only nugget I'm giving you tonight. You're bright; you'll figure it out. ;)

What you told is is basically what I was looking for, and I already knew it, but I was hoping for a little more. Things such as rules for checking collision detection between a sphere and an oriented bounding box. My friend and I are going to try to see if we can figure it out ourselves.

Also: What you were saying about fields sounds like it would be very expensive on the CPU, which IS why it wouldn't typically be used. If you're interested in good ways to quickly do collision detection for many objects, I recommend doing some research on quadtrees/octrees. My friend and I are going to be using Octrees in our game to improve efficiency, and it's really amazing what octrees are capable of.

Here's a 2D quadtree that I made to test rendering: http://i.imgur.com/w1dLD.jpg

Hey! That thing is really interesting! I think I'll play with it after I finish my homework. Thanks!

Hey! That thing is really interesting! I think I'll play with it after I finish my homework. Thanks!

I would give you the source code, but I'd rather not give out any othe source code of my unfinished game (even though it's only test code). If you want more information about how to implement a quadtree, send me a message and I'll explain it to you.