Collisions in 3d: Sanity Check
by Mark Storer · in Technical Issues · 08/30/2005 (1:02 pm) · 5 replies
I've been taking a 3d game programming class, and we've started by covering all the Very Basic Math underlying The Wonderful World of 3d Graphics. Dot products, cross products, matrices (which are pretty familiar to me thanks to PDF), planes, rays, all that jazz.
So now I'm taking that knowledge, and reconsiling it with all the stuff I've read (but didn't really "get") in the past: "use convex objects for collisions", BSPs, all that good stuff.
Let me see if I've got this stuff right:
1) The reason BSPs are so great is because its easy to tell which side of a plane a given point is on: just take the dot product of that point and the plane, and you've got your answer, positive, negative, or co-planar.
2) Convex objects are easy to check: If a given point is on the negative side (or positive depending on your winding I guess) of every triangle's plane, it's inside that convex object.
3) Splitting a convex object along any plane gives you two convex objects. So in generating a BSP, the trick comes in picking the right plane. Quite a trick by the looks of things.
4) Listening to Ren & Stimpy sound clips while trying to think about 3d math is a Bad Idea. "SPACE MADNESS!!!"
Questions:
*Is all that stuff right? Or do I need to go do some more reading, head scratching, and Deep Meditation (while listening to more REN & STIMPY you bloated sack of protoplasm!)?
*Dang it. What was my other question?! Ah! How much more difficult is it to collide with a ray than with a point? It seems to me that the "passed through something solid because Thing A was moving too fast relative to Thing B" bugs could be eliminated if you compared with a ray going from the last position to the current one rather than just the current one. This isn't likely to be a New Thought, so someone who knows better must have considered the idea and rejected it. Why?
Admittedly, casting rays for every vertex of every object to see where exactly they ran into the ground is probably Not A Good Idea. Projectile collisions on the other hand... that's one ray being tested against a bunch of vertices rather than a bunch of verts tested against a bunch of verts.
Possible optimization: All the back-faces relative to the ray could be ignored. You're only looking for a point of intersection on the facing surfaces. Hurray for surface normals. More hurrays for having calculated & stored them before hand.
Hmm. Collision between a ray and a triangle. I've got an equation for collision between a ray and a plane. So get the point on the plane and compare that to "whats in the tringle". Okay, but how? Create more planes representing each of the triangle's edge? Oy vey. So you'd have to create (or store) 3 planes and do 4 plane dot-products per triangle, along with the whole "where on plane X does ray Y impact".
Which would handily explain why it isn't used more often.
I don't know much about shaders yet, but this smells like something that could be done in a vertex shader. Or could it? They're "vertex shaders" not "triangle shaders". Humph. Sounds like it might still be possible, but there'd be some flaming hoops to jump through to get there.
Doing a bit of googling (on the web, not here on GG), there IS a chapter called "Collision Shaders" in a book entitled "Shader X^2 Programming". Hmmm. Sounds like its been done. And THEY CALLED ME CRAZY! I'LL SHOW THEM ALL!!!
(all I wanted was a pepsi, and she wouldn't give it to me!)
So now I'm taking that knowledge, and reconsiling it with all the stuff I've read (but didn't really "get") in the past: "use convex objects for collisions", BSPs, all that good stuff.
Let me see if I've got this stuff right:
1) The reason BSPs are so great is because its easy to tell which side of a plane a given point is on: just take the dot product of that point and the plane, and you've got your answer, positive, negative, or co-planar.
2) Convex objects are easy to check: If a given point is on the negative side (or positive depending on your winding I guess) of every triangle's plane, it's inside that convex object.
3) Splitting a convex object along any plane gives you two convex objects. So in generating a BSP, the trick comes in picking the right plane. Quite a trick by the looks of things.
4) Listening to Ren & Stimpy sound clips while trying to think about 3d math is a Bad Idea. "SPACE MADNESS!!!"
Questions:
*Is all that stuff right? Or do I need to go do some more reading, head scratching, and Deep Meditation (while listening to more REN & STIMPY you bloated sack of protoplasm!)?
*Dang it. What was my other question?! Ah! How much more difficult is it to collide with a ray than with a point? It seems to me that the "passed through something solid because Thing A was moving too fast relative to Thing B" bugs could be eliminated if you compared with a ray going from the last position to the current one rather than just the current one. This isn't likely to be a New Thought, so someone who knows better must have considered the idea and rejected it. Why?
Admittedly, casting rays for every vertex of every object to see where exactly they ran into the ground is probably Not A Good Idea. Projectile collisions on the other hand... that's one ray being tested against a bunch of vertices rather than a bunch of verts tested against a bunch of verts.
Possible optimization: All the back-faces relative to the ray could be ignored. You're only looking for a point of intersection on the facing surfaces. Hurray for surface normals. More hurrays for having calculated & stored them before hand.
Hmm. Collision between a ray and a triangle. I've got an equation for collision between a ray and a plane. So get the point on the plane and compare that to "whats in the tringle". Okay, but how? Create more planes representing each of the triangle's edge? Oy vey. So you'd have to create (or store) 3 planes and do 4 plane dot-products per triangle, along with the whole "where on plane X does ray Y impact".
Which would handily explain why it isn't used more often.
I don't know much about shaders yet, but this smells like something that could be done in a vertex shader. Or could it? They're "vertex shaders" not "triangle shaders". Humph. Sounds like it might still be possible, but there'd be some flaming hoops to jump through to get there.
Doing a bit of googling (on the web, not here on GG), there IS a chapter called "Collision Shaders" in a book entitled "Shader X^2 Programming". Hmmm. Sounds like its been done. And THEY CALLED ME CRAZY! I'LL SHOW THEM ALL!!!
(all I wanted was a pepsi, and she wouldn't give it to me!)
About the author
#2
- i'm sure google would have something to say, but it seems to me that you could:
given the 3 triangle points A,B,C, the triangle normal N, and the point P you want to test.
also assume counter-clockwise point ordering for the triangle.
basically test to see if P is to the right of any triangle edge.
if so, it's outside the triangle.
for edge AB, calculate a perpendicular-to-the-right vector for AB.
i'll call this an "edge normal", even tho you shouldn't bother making it unit length.
edgeNormalAB = (B-A) cross N.
now dot the edge normal with the vector from A to P:
dp = (P-A) dot edgeNormalAB
if (dp > 0)
then P is on the right-hand side of edge AB, and so outside the triangle.
else
test P against BC, and then against CA.
.. this seems like a lot of work, and i think it is,
so try to optimize your way out of actually doing it as much as possible.
also, if your triangle is not changing size/shape, you can pre-calculate those edge normals,
which reduces the work to just a vector subtract and a dot product per edge.
i haven't actually implemented this, but i'm pretty sure the jist is right.
08/30/2005 (2:05 pm)
I'm not so familiar with BSPs, but your summary sounds right.Quote:
Hmm. Collision between a ray and a triangle. I've got an equation for collision between a ray and a plane. So get the point on the plane and compare that to "whats in the tringle". Okay, but how? Create more planes representing each of the triangle's edge? Oy vey. So you'd have to create (or store) 3 planes and do 4 plane dot-products per triangle, along with the whole "where on plane X does ray Y impact".
- i'm sure google would have something to say, but it seems to me that you could:
given the 3 triangle points A,B,C, the triangle normal N, and the point P you want to test.
also assume counter-clockwise point ordering for the triangle.
basically test to see if P is to the right of any triangle edge.
if so, it's outside the triangle.
for edge AB, calculate a perpendicular-to-the-right vector for AB.
i'll call this an "edge normal", even tho you shouldn't bother making it unit length.
edgeNormalAB = (B-A) cross N.
now dot the edge normal with the vector from A to P:
dp = (P-A) dot edgeNormalAB
if (dp > 0)
then P is on the right-hand side of edge AB, and so outside the triangle.
else
test P against BC, and then against CA.
.. this seems like a lot of work, and i think it is,
so try to optimize your way out of actually doing it as much as possible.
also, if your triangle is not changing size/shape, you can pre-calculate those edge normals,
which reduces the work to just a vector subtract and a dot product per edge.
i haven't actually implemented this, but i'm pretty sure the jist is right.
#3
EDIT: It occurs to me that even the "ray" thing isn't 100% accurate, when the mesh being tested against has moved. You'd be testing "the space Point X went through between the last frame and the current one" vs "the space mesh Y is no Right Now". Not terribly consistent...
I suppose you could extrude each triangle into a prism-looking thing, and test to see if the ray intersected that prism, but even that could result in false positives (but no false negatives). I suppose you could Take Steps to avoid that too, but that's a Whole Hell of a Lot of computation just to see if X ran into Y.
Throw in a high angular velocity on that mesh, and the extruded prism (is there a more technical term?) could be wildly inaccurate. Think about something spinning so fast it's made a complete 360 since the last frame, and moved 2 units in some axis. An accurate 3d solid representing the path of that triangle would be this streamer-looking thing, like something out of a froofy gymnastic event... not a prism with the current and last location as its end-caps.
But now we're talking about a Truely Insane amount of processing (and some even heavier math) just to test one lousy triangle. Thanks but no thanks.
But I still like the ray idea.
08/30/2005 (2:58 pm)
@J: Chill?! Some people just can't handle a good, wholesome cartoon. At least I wasn't rambling on about frozen yogurt.EDIT: It occurs to me that even the "ray" thing isn't 100% accurate, when the mesh being tested against has moved. You'd be testing "the space Point X went through between the last frame and the current one" vs "the space mesh Y is no Right Now". Not terribly consistent...
I suppose you could extrude each triangle into a prism-looking thing, and test to see if the ray intersected that prism, but even that could result in false positives (but no false negatives). I suppose you could Take Steps to avoid that too, but that's a Whole Hell of a Lot of computation just to see if X ran into Y.
Throw in a high angular velocity on that mesh, and the extruded prism (is there a more technical term?) could be wildly inaccurate. Think about something spinning so fast it's made a complete 360 since the last frame, and moved 2 units in some axis. An accurate 3d solid representing the path of that triangle would be this streamer-looking thing, like something out of a froofy gymnastic event... not a prism with the current and last location as its end-caps.
But now we're talking about a Truely Insane amount of processing (and some even heavier math) just to test one lousy triangle. Thanks but no thanks.
But I still like the ray idea.
#4
you'd have to test the ray against a prism,
or (i _think_ this should be possible)
project the motion of the triangle onto the ray
so that the ray becomes a swept ray of some sort.
(probably not a planar object, note)
i think compensating for inter-frame non-linear motion of the triangle
(ie curving) is pretty well above & beyond the call of duty.
if it's spinning that fast, you've got bigger problems on the plate.
ie do the collision from the triangle's point of view,
where the triangle ain't moving but the ray is.
check out this other thread for more torque-specific stuff:
www.garagegames.com/mg/forums/result.thread.php?qt=33981
08/30/2005 (4:26 pm)
You're absolutely right,you'd have to test the ray against a prism,
or (i _think_ this should be possible)
project the motion of the triangle onto the ray
so that the ray becomes a swept ray of some sort.
(probably not a planar object, note)
i think compensating for inter-frame non-linear motion of the triangle
(ie curving) is pretty well above & beyond the call of duty.
if it's spinning that fast, you've got bigger problems on the plate.
ie do the collision from the triangle's point of view,
where the triangle ain't moving but the ray is.
check out this other thread for more torque-specific stuff:
www.garagegames.com/mg/forums/result.thread.php?qt=33981
#5
"No sir, it was THIS triangle, honest!"
08/30/2005 (4:50 pm)
On the up-side, with that much angular momentum between frames, anyone watching is going to have a REALLY HARD TIME catching you if you're wrong. :P"No sir, it was THIS triangle, honest!"
Torque Owner J. Alan Atherton