Started by Feb 26 2012 02:36 PM

,
17 replies to this topic

Posted 26 February 2012 - 02:36 PM

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.

Thanks.

Posted 26 February 2012 - 02:56 PM

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.

SlimDX | Shark Eaters for iOS | Ventspace Blog | Twitter | Proud supporter of diversity and inclusiveness in game development

Posted 26 February 2012 - 03:02 PM

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.

Posted 26 February 2012 - 03:21 PM

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.

Posted 26 February 2012 - 03:33 PM

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.

Posted 26 February 2012 - 03:40 PM

This might help: http://www.realtimerendering.com/intersections.html

Posted 26 February 2012 - 06:37 PM

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. ;)

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. ;)

Posted 26 February 2012 - 09:13 PM

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

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

Posted 26 February 2012 - 09:36 PM

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

Posted 26 February 2012 - 10:27 PM

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.

Posted 26 February 2012 - 11:27 PM

To be honest, your question is really vague. There isn't really one answer. You know you need to know vector and matrix math and geometric principles. Everything else pretty much expands on those things. The theorems for collision detection and resolution, the algorithms for broad-phase and narrow-phase collision detection, etc. just build on these basic concepts and ideas, and then use clever understandings of the math and the problem to accomplish the desired goal. There really isn't one answer about knowing how to detect collisions between various types. It's an open field of active research, and there are many correct answers.

Some of the theorems and ideas popularly used to accomplish the things you're desiring are the Separating Axis Theorem, GJK collision detection, Voronoi regions, Minkowski addition, broad-phase collision detection (with things like BSPs, spatial hashing, etc.), etc. These things are just a small sample of things used in various physics engines, and I wouldn't be surprised if you are already aware of this. If you want to know how to detect and handle a collision, I suggest you look up another physics engine, see the algorithm they use, and then research that algorithm. Being able to look at a problem and decompose it into a mathematical formula is also important. Simply googling the type of objects that can collide is also important, and you'll find various answers for various shapes. And I don't think there's one answer that'll solve every problem. Usually, you have to use multiple answers to solve all the problems, as well as decomposing your problems into other problems which can be solved by your chosen method (like with collision detection and concave shapes using SAT or GJK). And then there's the cases you have to deal with where you really can't accurately solve the problem and just have to hack it with an estimation.

If you have a more specific question about one of these aspects, then it's a much easier question to answer. But there isn't really an answer to asking what you need to know in order to write a physics engine, because there's a million ways to do it, each way having it's own million things to know.

But really, I'd suggest using the Separating Axis Theorem. This site is gold for a starting point. Whether you use SAT, GJK, etc. is up to you. With each of these algorithms, there are things you need to know. But first you need to decide on an algorithm before I think anyone can really say what you'll need to know, specifically.

Some of the theorems and ideas popularly used to accomplish the things you're desiring are the Separating Axis Theorem, GJK collision detection, Voronoi regions, Minkowski addition, broad-phase collision detection (with things like BSPs, spatial hashing, etc.), etc. These things are just a small sample of things used in various physics engines, and I wouldn't be surprised if you are already aware of this. If you want to know how to detect and handle a collision, I suggest you look up another physics engine, see the algorithm they use, and then research that algorithm. Being able to look at a problem and decompose it into a mathematical formula is also important. Simply googling the type of objects that can collide is also important, and you'll find various answers for various shapes. And I don't think there's one answer that'll solve every problem. Usually, you have to use multiple answers to solve all the problems, as well as decomposing your problems into other problems which can be solved by your chosen method (like with collision detection and concave shapes using SAT or GJK). And then there's the cases you have to deal with where you really can't accurately solve the problem and just have to hack it with an estimation.

If you have a more specific question about one of these aspects, then it's a much easier question to answer. But there isn't really an answer to asking what you need to know in order to write a physics engine, because there's a million ways to do it, each way having it's own million things to know.

But really, I'd suggest using the Separating Axis Theorem. This site is gold for a starting point. Whether you use SAT, GJK, etc. is up to you. With each of these algorithms, there are things you need to know. But first you need to decide on an algorithm before I think anyone can really say what you'll need to know, specifically.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

Posted 02 March 2012 - 12:36 PM

To be honest, your question is really vague. There isn't really one answer. You know you need to know vector and matrix math and geometric principles. Everything else pretty much expands on those things. The theorems for collision detection and resolution, the algorithms for broad-phase and narrow-phase collision detection, etc. just build on these basic concepts and ideas, and then use clever understandings of the math and the problem to accomplish the desired goal. There really isn't one answer about knowing how to detect collisions between various types. It's an open field of active research, and there are many correct answers. Some of the theorems and ideas popularly used to accomplish the things you're desiring are the Separating Axis Theorem, GJK collision detection, Voronoi regions, Minkowski addition, broad-phase collision detection (with things like BSPs, spatial hashing, etc.), etc. These things are just a small sample of things used in various physics engines, and I wouldn't be surprised if you are already aware of this. If you want to know how to detect and handle a collision, I suggest you look up another physics engine, see the algorithm they use, and then research that algorithm. Being able to look at a problem and decompose it into a mathematical formula is also important. Simply googling the type of objects that can collide is also important, and you'll find various answers for various shapes. And I don't think there's one answer that'll solve every problem. Usually, you have to use multiple answers to solve all the problems, as well as decomposing your problems into other problems which can be solved by your chosen method (like with collision detection and concave shapes using SAT or GJK). And then there's the cases you have to deal with where you really can't accurately solve the problem and just have to hack it with an estimation. If you have a more specific question about one of these aspects, then it's a much easier question to answer. But there isn't really an answer to asking what you need to know in order to write a physics engine, because there's a million ways to do it, each way having it's own million things to know. But really, I'd suggest using the Separating Axis Theorem. This site is gold for a starting point. Whether you use SAT, GJK, etc. is up to you. With each of these algorithms, there are things you need to know. But first you need to decide on an algorithm before I think anyone can really say what you'll need to know, specifically.

Sorry about being vague, I'm just unsure of how to ask the question properly. I've looked at the tutorials on metanetsoftware.com, but I'm just not sure how to use the information on there. From what I've seen, they don't really provide much more information beyond diagrams and descriptions. I feel like I already know everything I need, but I just need a "refresher" so to speak.

I guess to get a better answer, what is likely to be the best book to find information about vector math used in games?

Posted 10 March 2012 - 10:15 AM

To be honest, your question is really vague. There isn't really one answer. You know you need to know vector and matrix math and geometric principles. Everything else pretty much expands on those things. The theorems for collision detection and resolution, the algorithms for broad-phase and narrow-phase collision detection, etc. just build on these basic concepts and ideas, and then use clever understandings of the math and the problem to accomplish the desired goal. There really isn't one answer about knowing how to detect collisions between various types. It's an open field of active research, and there are many correct answers.

Some of the theorems and ideas popularly used to accomplish the things you're desiring are the Separating Axis Theorem, GJK collision detection, Voronoi regions, Minkowski addition, broad-phase collision detection (with things like BSPs, spatial hashing, etc.), etc. These things are just a small sample of things used in various physics engines, and I wouldn't be surprised if you are already aware of this. If you want to know how to detect and handle a collision, I suggest you look up another physics engine, see the algorithm they use, and then research that algorithm. Being able to look at a problem and decompose it into a mathematical formula is also important. Simply googling the type of objects that can collide is also important, and you'll find various answers for various shapes. And I don't think there's one answer that'll solve every problem. Usually, you have to use multiple answers to solve all the problems, as well as decomposing your problems into other problems which can be solved by your chosen method (like with collision detection and concave shapes using SAT or GJK). And then there's the cases you have to deal with where you really can't accurately solve the problem and just have to hack it with an estimation.

If you have a more specific question about one of these aspects, then it's a much easier question to answer. But there isn't really an answer to asking what you need to know in order to write a physics engine, because there's a million ways to do it, each way having it's own million things to know.

But really, I'd suggest using the Separating Axis Theorem. This site is gold for a starting point. Whether you use SAT, GJK, etc. is up to you. With each of these algorithms, there are things you need to know. But first you need to decide on an algorithm before I think anyone can really say what you'll need to know, specifically.

That may not have been what the OP needed but that was an excellent intro to collision detection. Thank you for your post.

To the OP: The basis of all basic math used in describing 3D environments is Linear Algebra. Going through a course in it or reading any good textbook would get you what you need. If you have that background (or a solid physics background) a discreet mathematics textbook would be a possible next step then maybe numerical analysis (although neither is related to collision detection directly...). Most of your introductory game programming/physics modeling books also have all the relevant info.

Posted 10 March 2012 - 11:04 AM

I'm not asking what I need to know to make a physics engine

That may certainly prove to be confusing considering that is the very exact title of your thread.

I, much like the others, can't quite make out what you're asking for. If you want to code the algorithms yourself instead of looking them up, then go read up on basic physics concepts, crank up your math skills, grab a pen and paper and off you go. You should have enough knowledge about the physical relationships between various physical quantities and enough tricks in your math bag that you should be able to not only handle collision detection but collision response. If you do not, then you can find both physics and math tutorials in my signature. That is about as bare as it gets to reinventing the algorithms, without having to reinvent classical physics altogether.

My personal links

- Khan Academy - For all your math needs

- Java API Documentation - For all your Java info needs

- C++ Standard Library Reference - For some of your C++ needs ^.^

Posted 15 March 2012 - 04:11 PM

I'm not asking what I need to know to make a physics engine

That may certainly prove to be confusing considering that is the very exact title of your thread.

I, much like the others, can't quite make out what you're asking for. If you want to code the algorithms yourself instead of looking them up, then go read up on basic physics concepts, crank up your math skills, grab a pen and paper and off you go. You should have enough knowledge about the physical relationships between various physical quantities and enough tricks in your math bag that you should be able to not only handle collision detection but collision response. If you do not, then you can find both physics and math tutorials in my signature. That is about as bare as it gets to reinventing the algorithms, without having to reinvent classical physics altogether.

I apologize for being very confusing. I'm not asking how to make a physics engine, I'm just asking what kinds of concepts I should look into to be able to check collisions. After going off on my own research, I've decided that I know much of what I need to know.

Cross production to get the normal of a face (already knew this)

Dot product (also knew this previously)

Projection (knew of it, but never used it)

Normalization (knew it and used it)

The kind of information I was really hoping to hear about were things like Separating Axis Theorem. Which I've looked into and managed to write my own algorithm to check collision between two convex polygons. Voronoi regions were another thing that I found that I might want to look into.

I wasn't looking for info for how to do complex collision responses (like rotation), I just needed to push the bodies apart.

What I mean by wanting to know the basics, and how to use them is something like how you can use dot production to project vertices onto an axis to check for gaps with SAT. (I figured this out myself after reading up about it).

Everything I've found on the net was really vague about how to do things, and they left parts out, and the equations were hard to understand at times.

I haven't learned anything from this post that I didn't already know about, but that is my own fault for being unable to express what kind of info I'm looking for. I apologize for wasting everyone's time. I'm just going to try to figure out what I need to know myself.

Thanks for at least trying.

Posted 19 March 2012 - 06:44 PM

I also have a question,

does box2d use runge kutta 4 integration?

does box2d use runge kutta 4 integration?

Posted 19 March 2012 - 06:52 PM

I also have a question,

does box2d use runge kutta 4 integration?

I've never heard of using Runge Kutta for straight integration but my experience is from Numerical Analysis so I could just be an idiot.

Posted 19 March 2012 - 08:44 PM

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]