Sign in to follow this  
Days

Sphere-Plane (box) collision

Recommended Posts

I am having an issue with a sphere to plane (represented as a box) algorithm. The algorithm works in all cases but one, and I am sure I am just missing one vital step, but for the life of me, I can't figure out how to fix it. Here is an image of what is happening, and the steps I am taking. Image hosted by Photobucket.com Ok basically, I am getting a list of the faces that I am potentially colliding with from the box, and processing them one by one. The first test gets the closest point on the sphere that will collide with the plane, then uses the velocity vector to determine where the sphere will actually collide with the box. Thus my problem, it never collides with the triangle if I am coming in at a 45 degree angle. The next step is to repeat this for all triangles, which when it comes to the next tri to collide with, the algorithm fails again for the same reason. It works great when I am colliding with any other angle, but when I am approaching anywhere near that 45 degree, all of my detections fail, and I pass straight through it. I hope I conveyed my problem well without using source, but I can provide if necessary. Also, I have gone over many tutorials on the net, which never seem to answer this specific problem. TIA Shane

Share this post


Link to post
Share on other sites
Doing sphere-plane tests isn't enough. If the sphere misses the box sides, it may still collide with other features, i.e. an edge or corner. For these you need to solve the appropriate quadratics to determine intersection. In 2d this isn't too hard, but in 3d there are quite a few cases to handle.

Intersecting a moving sphere and box is also equivalent to raytracing against a 'rounded' box. You can look at this as raytracing against the CSO of the box and sphere, or as simply another way of expressing the various sweep tests involved. I happen to be re-writing a bunch of my raytracing code at the moment, including raytracing against medial-structure objects such as spheres, capsules, lozenges, and rounded boxes. The code isn't ready yet, but if you're still stuck on this in a few days, let me know and I'll be glad to post it.

(Btw, does anyone know a more formal geometric name for a 'rounded box'?)

Share this post


Link to post
Share on other sites
The "rounded box" is also known as the "Minkowski sum of a box and a sphere" :-)

The traditional test for a box is to first test all six sides (which boils down to overlap tests for the three major axes); then test the 8 corners; then test the 12 edges. Testing the corners is easy: vertex-in-sphere. Testing the edges is a little bit harder, as you have to test line-segment-in-sphere, but one way of formulating that is "vertex in sphere or vertices separated by plane orthogonal to line and passing through sphere center, and that point being within sphere".

Share this post


Link to post
Share on other sites
Quote:
The "rounded box" is also known as the "Minkowski sum of a box and a sphere" :-)
Hehe, I know :-) I'm looking for something a little more succinct, though. Sphere, capsule and lozenge are such nice words - there should be something similar for boxes! :)
Quote:
The traditional test for a box is to first test all six sides (which boils down to overlap tests for the three major axes); then test the 8 corners; then test the 12 edges. Testing the corners is easy: vertex-in-sphere. Testing the edges is a little bit harder, as you have to test line-segment-in-sphere, but one way of formulating that is "vertex in sphere or vertices separated by plane orthogonal to line and passing through sphere center, and that point being within sphere".
Just thought I'd point that the OP appears to be doing a swept rather than static test. The static test is dead simple - find the closest point on the box to the sphere center and build the intersection info from the vector between the two. For the swept test, you could perform 6 quad tests, 8 sphere tests, and 12 cylinder tests and take the minimum, but that obviously won't perform too well. The alternative is to determine what edges or corners to test against based on the results of the quad tests, hence the complexity.

Share this post


Link to post
Share on other sites
Wow, ok well here is the deal. Not all of my objects are perfect AABB's. I researched using the rounded bounding box method, and while it will work flawlessly for AABB's, there is a lot of geometry that does need to be collided with that I cannot pigeonhole with this method.

I am hoping for a hack that will work in most cases, but may not give perfect true to life collisions. I know that is probably a bad thing to ask for on a physics forum.

I am sooo close too. I have it working on the exact 45 degree angle, but now when the ball is moving perpendicular to a side, I can get the sphere to pass through undetected as long as I am not deeper than the radius in... I employed one of the methods in the rounded box method, but it broke the other check.. heh.


()-------> --()---
| | | |
| | = | |
------ -------


I know that if I extend the box, then I can get the check to resolve in a collision, but the problem is, colliding against an object with less/more than a perfect 90 degree angle may not work so well.


The perfect example is the sphere to a ramp mesh.


/|
()--> /-|


the rounded AABB method would just reflect directly back off of the mesh, where the real collision would result in the ball climbing the ramp.

Ugh.. I thought this would be easy when I started, and its proving to be such a bear. I can tell you right now when I make my fast break for the industry, I will NOT be in the physics department.

Thanks again for all the help guys, I really do appreciate it.
Shane

Share this post


Link to post
Share on other sites
Hm, so I guess sphere-box intersection isn't really what you're looking for. I know you mentioned spheres, but I'm actually not clear on whether this is 2d or 3d. So maybe you could give some more detailed info - 2d or 3d, what kind of simulation it is, what sort of objects you're trying to intersect with, etc. Or as ury suggested earlier, maybe you could post some code.

I will say that there are standard solutions for both swept and static circles and spheres vs. line segments, triangles, and meshes. So if you can tell us which of these describes your situation it should be pretty easy to offer more specific advice.

Share this post


Link to post
Share on other sites
Image hosted by Photobucket.com

Top case: ball rolls in at a 45 degree angle, bad stuff happens
Bottom case: any other collision is ok.

Basically, replace the brick I am colliding with, with a ramp, or another convex object, and you can then understand my delimma.

I am working now implementing a sphere to ray test, to test against the geometry's lines. I found a very well documented solution to the quatratic equation problem here. Now I just have to use the points I get back from that to determine the depth of collision.

I suppose this is the exact same thing as using a point-rounded box intersection, but in a format that is easier for me to visualize and code for.

I'll be working on my solution. If you have any insight please let me know.

Oh, and sorry about not pasting code.. it is incredibly embarrasing right now, due to the implemntation and de-implementation of different methods over the course of 3 days. I have more code commented out than I have working at the moment.

Shane

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this