Collision detection between moving Sphere & moving and rotating Box
Author
How to collide a moving sphere and a transforming (moving & rotating) box?
Timing is important, can a sweep test be used here?
Rotations bring a whole new level of complexity. They are best avoided. If you want simplicity and yet relative accuracy, you can try splitting the time into small intervals recursively until the sphere/box distance reaches a given tolerance. For example, split the box and sphere motion so that the rotation during the sub-interval is less than a given degree (say, 5 degrees). You can also use a linear sphere/box swept test through the sub-intervals for extra accuracy.
Dave Eberly also has some docs on his website about collisions between boxes and triangles with rotational motion. You can have a look if you want, for inspiration, but it's not easy.
Dave Eberly also has some docs on his website about collisions between boxes and triangles with rotational motion. You can have a look if you want, for inspiration, but it's not easy.
Author
Quote:Original post by oliii
Dave Eberly also has some docs on his website about collisions between boxes and triangles with rotational motion. You can have a look if you want, for inspiration, but it's not easy.
Thanks for your suggestion. Is this the website that you are refferign to?
http://www.geometrictools.com/Documentation/Documentation.html
Am going through the papers. Thanks.
Yes. I was thinking of that doc in particular
Intersection of Objects with Linear and Angular Velocities using Oriented Bounding Boxes
Intersection of Objects with Linear and Angular Velocities using Oriented Bounding Boxes
This might be a little confusing and I might be way off here on what you're trying to accomplish but I'll add some of my own findings and practices here.
If This Object Were a Charactor:
If the bounding box were to serve as a charactors main bounding box, then the main bounding box shouldn't rotate, you'd just keep the dynamic bounding box point values updated to match the lowest and maximum XYZ range values combined with the charactors current position. Setting an objects start position to always be a 0,0,0 when first loaded you can easily calculate or generate/get the first bounding box values for your charactor. Then as the charactor moves throughout the environment keep those dynamic values updated and re-calculate the bounding box size only when the charactor rotates along the Y-Axis, normally the bounding box will always face the same direction and never rotate even though the charactor rotates, this enables for simpler collision calculations.
For instance, if you fired a projectile at a charactor for performance you'd only want to test only mesh bounding box's which are closest to the projectiles position vector, test for collision against the surface of the box or simply check to see if the projectiles position point or sphere radius is within or colliding with the box, if so, perform a Sphere to Polygon collision detection on each polygon of the mesh inside the bounding box, this will be the mesh that's associated with the bounding box you checked.
Some Steps I Use For Charactor and Objects Moving or Not:
Make sure the bounding box faces the same direction all the time and doesn't rotate with the mesh but keeps the dynamic bounding box information updated on objects that move in an environment and match this to the objects current position. (You'd only need to use 2 vector3's to represent a bounding box, 1 Vector3 to contain the Nearest and Lowest XYZ point of the bounding box, and the Furthest and Highest XYZ point of the bounding box.)
Perform Point to Bounding Box collision check for inside and outside bounding box to determine weither or not to perform more detailed check on the mesh associated with that particular bounding box.
Perform Sphere to Polygon collision check on each polygon on a mesh when inside the bounding box to determine area of mesh or the mesh surface that has been collided with.
For higher accuracy and sensitivity you can use Sphere to Bounding Box collision check on the bounding box's polygons instead of Point to Bounding Box just as you would the mesh, it's basically the Sphere to Polygon collision check only you are assuming the Bounding Box as mesh geometry made up of triangles only and not quads and the same exact test you'd perform on only the mesh is first performed on the bounding box to determine weither or not to check the mesh that's associated with the bounding box for further intersection. You can also use the Sphere to Polygon against bounding box's to determine when to check meshs and perform more detailed collision checks, this can also easily tell you which mesh(s) to check, hope that makes sense.
To perform Point to Sphere or Point to Bounding Box collision check just use the Sphere to Polygon check but remove the radius part as you're only checking a point not a sizable radius range for collision.
For a Charactor/Object That's Animated:
You'd calculate the bounding box for each frame of the animation.
Something Extra:
If you want the point of intersection to use for things like physics and to reset an object like a charactor or camera to just before an object collided with a mesh or bounding box, such as a wall, it's the position when the collision check took place when it found the intersection, to reset this you'd simply decrement the position when the collision took place with the amount that you moved to get to that point, in other words if your speed was 0.1F you'd subtract the current position XYZ where the collision occured by 0.1F. Of coarse the simplest thing you could do is just save the last position of an object and just re-add that as the current position to an object, that way there's no need to re-calculate anything.
For More Detailed Physics Type Check:
Perform solid rigid body physics, you'd check each point of for instance a projectile's mesh with the charactor mesh for intersection. The individual points would be checked. You could do Sphere to Sphere, Sphere to Polygon, and Point to Sphere, where in this case you'd create a version of the mesh to check against that had a mass/volume madeup of points that had a given sphere radius for each point throughout the meshes surfaces. Imagine a grid of microscopic bubbles that madeup a meshes surface, or even simpler, bubble wrap packaging you'd use to send a package at the post office, those bubbles are point spheres (points which have and are surrounded by a sphere radius to fill in the gaps). if you add more points spheres/bubbles to represent a physical surface you can get greater detail but a bit slower to calculate, bigger or flatter disk shaped spheres could help.
If This Object Were a Charactor:
If the bounding box were to serve as a charactors main bounding box, then the main bounding box shouldn't rotate, you'd just keep the dynamic bounding box point values updated to match the lowest and maximum XYZ range values combined with the charactors current position. Setting an objects start position to always be a 0,0,0 when first loaded you can easily calculate or generate/get the first bounding box values for your charactor. Then as the charactor moves throughout the environment keep those dynamic values updated and re-calculate the bounding box size only when the charactor rotates along the Y-Axis, normally the bounding box will always face the same direction and never rotate even though the charactor rotates, this enables for simpler collision calculations.
For instance, if you fired a projectile at a charactor for performance you'd only want to test only mesh bounding box's which are closest to the projectiles position vector, test for collision against the surface of the box or simply check to see if the projectiles position point or sphere radius is within or colliding with the box, if so, perform a Sphere to Polygon collision detection on each polygon of the mesh inside the bounding box, this will be the mesh that's associated with the bounding box you checked.
Some Steps I Use For Charactor and Objects Moving or Not:
Make sure the bounding box faces the same direction all the time and doesn't rotate with the mesh but keeps the dynamic bounding box information updated on objects that move in an environment and match this to the objects current position. (You'd only need to use 2 vector3's to represent a bounding box, 1 Vector3 to contain the Nearest and Lowest XYZ point of the bounding box, and the Furthest and Highest XYZ point of the bounding box.)
Perform Point to Bounding Box collision check for inside and outside bounding box to determine weither or not to perform more detailed check on the mesh associated with that particular bounding box.
Perform Sphere to Polygon collision check on each polygon on a mesh when inside the bounding box to determine area of mesh or the mesh surface that has been collided with.
For higher accuracy and sensitivity you can use Sphere to Bounding Box collision check on the bounding box's polygons instead of Point to Bounding Box just as you would the mesh, it's basically the Sphere to Polygon collision check only you are assuming the Bounding Box as mesh geometry made up of triangles only and not quads and the same exact test you'd perform on only the mesh is first performed on the bounding box to determine weither or not to check the mesh that's associated with the bounding box for further intersection. You can also use the Sphere to Polygon against bounding box's to determine when to check meshs and perform more detailed collision checks, this can also easily tell you which mesh(s) to check, hope that makes sense.
To perform Point to Sphere or Point to Bounding Box collision check just use the Sphere to Polygon check but remove the radius part as you're only checking a point not a sizable radius range for collision.
For a Charactor/Object That's Animated:
You'd calculate the bounding box for each frame of the animation.
Something Extra:
If you want the point of intersection to use for things like physics and to reset an object like a charactor or camera to just before an object collided with a mesh or bounding box, such as a wall, it's the position when the collision check took place when it found the intersection, to reset this you'd simply decrement the position when the collision took place with the amount that you moved to get to that point, in other words if your speed was 0.1F you'd subtract the current position XYZ where the collision occured by 0.1F. Of coarse the simplest thing you could do is just save the last position of an object and just re-add that as the current position to an object, that way there's no need to re-calculate anything.
For More Detailed Physics Type Check:
Perform solid rigid body physics, you'd check each point of for instance a projectile's mesh with the charactor mesh for intersection. The individual points would be checked. You could do Sphere to Sphere, Sphere to Polygon, and Point to Sphere, where in this case you'd create a version of the mesh to check against that had a mass/volume madeup of points that had a given sphere radius for each point throughout the meshes surfaces. Imagine a grid of microscopic bubbles that madeup a meshes surface, or even simpler, bubble wrap packaging you'd use to send a package at the post office, those bubbles are point spheres (points which have and are surrounded by a sphere radius to fill in the gaps). if you add more points spheres/bubbles to represent a physical surface you can get greater detail but a bit slower to calculate, bigger or flatter disk shaped spheres could help.
Author
Quote:Original post by oliii
Dave Eberly also has some docs on his website about collisions between boxes and triangles with rotational motion. You can have a look if you want, for inspiration, but it's not easy.
Yes Oliii, you were correct. those are some advanced algorithms. I got as far as colliding OBB's with linear velocity. Angular velocities seems to take the collision problem to a completely different level (boss level ;)) - and would require a lot of time and effort. But its nice to know that a solution already exists.
Knight Chat X,
Thank you for your excellent detailed reply.
This is what I'm trying to achieve;
Currently working on a Cricket game (somewhat similar to baseball), the Bat (bounding box) would typically rotate and translate just before it hits the Ball (sphere), hence the requirement of moving sphere v/s transforming OBB collision.
Timing requirement because of the low fps (~11-13) on the mobile device (OpenglES) that I'm working with. This requirement could be removed using an iterative approach for overlap test with small time steps (3 iterations can be thought of effectively tripling the fps, and reducing probability of a valid collision being missed be a factor of 1/3). But this would require lot of computations and the possibility of a valid collision being missed would still be there.
Thats the reason I thought (or hoped) that a sweep test would require lesser computational effort. But it seems that the sweep test would require lot more cpu time - not entirely sure about this !??
Maybe a fake collison / response system could get the job done. Treating the bat as a swept ellipse - checking for collision/proximity between ellipse & circle (in the bats object space)!!??
Quote:Original post by chand81
I got as far as colliding OBB's with linear velocity. Angular velocities seems to take the collision problem to a completely different level (boss level ;)) - and would require a lot of time and effort.
If you have _constant_ linear velocities and _constant_ (nonzero) angular velocities, the method of separating axes reduces to the problem of solving transcendental equations (in time t) involving polynomial terms in and sinusoidal terms in two different frequencies (the angular speeds of the OBBs). These equations do not have closed-form solutions, so you have to resort to numerical methods to solve the equations.
The PDF that oliii referred to takes a different approach. The equations of motion are used to produce approximations to the paths of the OBBs. The approximate paths are piecewise linear in the sense that along one segment, the OBBs (approximately) travel with constant linear velocity and _zero_ angular velocity. This allows you to use the closed-form solution for determining when two OBBs intersect when both are traveling with only constant linear velocity. This is, of course, only an approximation. But so is whatever you get from the numerical root finder for the transcendental equations.
When the linear and angular velocites vary in time but are not constant in time, then you have the most general problem, one which is best handled using numerical ODE solvers applied to the equations of motion.
"boss level" is an understatement. Implementing a fast computational physics engine using floating-point arithmetic is not trivial.
Quote:Original post by chand81Quote:Original post by oliii
Dave Eberly also has some docs on his website about collisions between boxes and triangles with rotational motion. You can have a look if you want, for inspiration, but it's not easy.
Yes Oliii, you were correct. those are some advanced algorithms. I got as far as colliding OBB's with linear velocity. Angular velocities seems to take the collision problem to a completely different level (boss level ;)) - and would require a lot of time and effort. But its nice to know that a solution already exists.
Knight Chat X,
Thank you for your excellent detailed reply.
This is what I'm trying to achieve;
Currently working on a Cricket game (somewhat similar to baseball), the Bat (bounding box) would typically rotate and translate just before it hits the Ball (sphere), hence the requirement of moving sphere v/s transforming OBB collision.
Timing requirement because of the low fps (~11-13) on the mobile device (OpenglES) that I'm working with. This requirement could be removed using an iterative approach for overlap test with small time steps (3 iterations can be thought of effectively tripling the fps, and reducing probability of a valid collision being missed be a factor of 1/3). But this would require lot of computations and the possibility of a valid collision being missed would still be there.
Thats the reason I thought (or hoped) that a sweep test would require lesser computational effort. But it seems that the sweep test would require lot more cpu time - not entirely sure about this !??
Maybe a fake collison / response system could get the job done. Treating the bat as a swept ellipse - checking for collision/proximity between ellipse & circle (in the bats object space)!!??
Putting it in context help. The swept test are computationally more expensive, but much more accurate. The static + sub sampling tests can be computationally expensive too, depending on the accuracy you want.
I've never worked on a game such as this, let alone, played one, but given the scope of a cricket game on a mobile platform :
- you could fake it by using the slow motion excuse. Reduce the frame rate and show a slow motion of the shot when the ball gets near the bat, thus reducing the frame time step and increasing the accuracy :) Can get annoying pretty quick though.
- The box/sphere intersection is extremely fast. all you need to do is find the closest point on the box from the sphere centre. So sub-sampling can be a viable solution.
- I'm not sure it's the way those sort of games work (tennis / Cricket / Baseball). I don't know for sure, but the controls are usually simple, and the collision detection faked in some way. Meaning, the result of the shot is already pre-determined when the user selected his inputs. Work out the probability of missing the shot or making the shot, and the accuracy of the shot, depending on many factors (user inputs, bowler's special skills, spin). Then the collision becomes relatively irrelevant, and you can fake a contact / miss.
Say the batsman basically selects where to strike the ball in front of him using the 8-directional keypad (and key 5 for covering the wicket). He thinks the ball will be a low left shot, and presses low left keys and that will play a low-left animation of the batsman. But the shot was a high right spin ball. too bad.
Now same inputs, but the shot is a fast low-left ball, and the user pressed low left too late. It's gonna be a shot to the ground and there is collision between the bat and the ball to be faked. You select a point along the ball trajectory where it will be hit, something relatively close to the batsman because of the late strike, and you play the most accurate batting animation so that the bat and the ball will roughly meet at that moment and position in time. Using simple inverse kinematics if you have the power, you can make the bat and ball meet accurately. Else, I guess it would be like arcade tennis games of old.
Basically, I wouldn't do an accurate collision test. I would fake the game mechanics so it looks correct, and pre-determine the outcome of the hit and the final shot so I would be in total control over the gameplay. Using pure physics can produce unwanted emergent behavior, espcially at low framerate and on a platform as restrictive as a mobile device, and it can be very expensive computationally.
my two cents.
Author
Appologies for not being able to reply earlier. Wanted to have something working first, but like a typical software dev proj, the release date was very slippary.
We have finally released our first mobile game product.
http://www.galular.com/Cricet3DDownload.htm
Thanks for your valuable inputs Dave. Although I have not yet implemented collision detection for rotating objects, I will have to before implementing rigid body physics. I've purchased your book on "Game Physcs", am sure its going to be a valuable resource.
Thanks Oliii, you were correct, subsampling is a viable solution. Especially when using step interpolation for the animated characters. I'm using 5 subsamples per frame for the batsman and ball animations and there is hardly any drop in fps.
But the outcome of the shot is not predetermined, yes this could lead to unwanted behaviour as you suggested, but the unpredictability gives a nice boost to the game play - so far no annoying behaviour has come up in our testing results.
We have finally released our first mobile game product.
http://www.galular.com/Cricet3DDownload.htm
Quote:Original post by Dave Eberly
The PDF that oliii referred to takes a different approach. The equations of motion are used to produce approximations to the paths of the OBBs. The approximate paths are piecewise linear in the sense that along one segment, the OBBs (approximately) travel with constant linear velocity and _zero_ angular velocity. This allows you to use the closed-form solution for determining when two OBBs intersect when both are traveling with only constant linear velocity. This is, of course, only an approximation. But so is whatever you get from the numerical root finder for the transcendental equations.
Thanks for your valuable inputs Dave. Although I have not yet implemented collision detection for rotating objects, I will have to before implementing rigid body physics. I've purchased your book on "Game Physcs", am sure its going to be a valuable resource.
Quote:Original post by oliii
- The box/sphere intersection is extremely fast. all you need to do is find the closest point on the box from the sphere centre. So sub-sampling can be a viable solution.
Basically, I wouldn't do an accurate collision test. I would fake the game mechanics so it looks correct, and pre-determine the outcome of the hit and the final shot so I would be in total control over the gameplay. Using pure physics can produce unwanted emergent behavior, espcially at low framerate and on a platform as restrictive as a mobile device, and it can be very expensive computationally.
my two cents.
Thanks Oliii, you were correct, subsampling is a viable solution. Especially when using step interpolation for the animated characters. I'm using 5 subsamples per frame for the batsman and ball animations and there is hardly any drop in fps.
But the outcome of the shot is not predetermined, yes this could lead to unwanted behaviour as you suggested, but the unpredictability gives a nice boost to the game play - so far no annoying behaviour has come up in our testing results.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
