Sign in to follow this  
megizin

Sphere-OBB

Recommended Posts

megizin    126
Ok, so I have heard of the merits of the Separating Axis, but what I don't think it does for me is test for the case where the sphere completely passes the OBB (so it starts on one end, passes through, but in the same step, ends up on the other side). The separating axis would not catch this. So my question is this: without limiting my world physics to avoid such a case, and without encasing my moving object in a collision representation that is stretched along the entire path of motion, is it possible for me to detect and respond to this type of collision (I have sphere-sphere working so that this is covered nicely. For OBB-Sphere or OBB-OBB all I can think of is iterative back off, which seems very costly and possibly inaccurate?) ...sorry for the long post/question. Thinking and writing and coding at the same time :P

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
(I have sphere-sphere working so that this is covered nicely. For OBB-Sphere or OBB-OBB all I can think of is iterative back off, which seems very costly and possibly inaccurate?)
No bisection or iteration is necessary with spheres and boxes; you can formulate a swept test for any combination of these objects. Sphere-sphere is fairly simple and amounts to solving a quadratic - it sounds like you already have that in place. OBB-OBB takes a bit more work, but can be implemented via the aforementioned separating axis test.

A sphere-OBB test can be written in a number of different ways. There are various approaches you can take and optimizations you can use, but I'll just give you the general idea.

Assume that the sphere is not initially intersecting the box, and that the object velocities are adjusted such that the box can be viewed as being stationary.

Depending on where the center of the sphere lies in relation to the box, there is a subset of the box's features (faces, edges, and corners) with which the sphere may possibly collide. You need only test these features for collision with the sphere.

The face test involves sweeping against the plane of the face and determining if the point of intersection lies within the face. Sweeping against a corner involves solving a quadratic similar to that of the swept sphere-sphere test. The edge test involves sweeping against the infinite line that contains the edge (again by solving a quadratic) and determining if the point of intersection lies on the edge.

This is far from a comprehensive description of the algorithm, as again there are different ways to go about the details of it. In the end though it all comes down to pretty much the same thing.

One hint that might be useful is that the sphere-plane, sphere-point, sphere-line, and sphere-segment tests can be formulated as ray-plane, ray-sphere, ray-cylinder, and ray-capsule tests, respectively. I mention this because the ray-object forms are fairly easy to find online.

Share this post


Link to post
Share on other sites
megizin    126
Thanks for the speedy reply! Will this only work for stationary objects or can I have objects with a -not- preset velocity (so the object can teleport beyond another object?

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
Will this only work for stationary objects or can I have objects with a -not- preset velocity (so the object can teleport beyond another object)?
The swept tests I mentioned will handle any reasonable velocities (by 'reasonable' I mean not so high or low as to cause numerical problems). One of the purposes of swept tests is to detect the 'teleporting' cases that you describe, where the velocities are such that the objects pass completely through each other in one step. The swept test will catch this and return the first time at which the objects intersect.

Often for simplicity, swept tests involving two moving objects are adjusted so that one is stationary and the other is moving. This has no impact on the 'outside world'; it's just something done inside the function to make the computations easier. For example, say that the velocities of the objects are V1 and V2. By subtracting V2 from both V1 and V2, V1 becomes V1-V2 and V2 becomes 0; in effect, we've adjusted the problem so that object 1 is moving and object 2 is stationary. But again, the objects' velocities outside the function that performs the swept test are not affected.

Anyway, I haven't been explaining things very well today, so let me know if I can offer any further clarification.

Share this post


Link to post
Share on other sites
megizin    126
I see. It sounds like the solution I am looking for then. I will look into it. Do you have any further reading suggestions on swept collision detection?

Also, while I am it, I wanted to know how big a problem floating point errors will be in collision detection. I have a case where a is use D3DXVec3Transform to transform a point (represented as a D3DXVECTOR3 so all 3 coordinates are floats) using a matrix (again, all floats). The result point should be at (0,0,0) but it lands up at about (-3.145e-5f, 0.0f, 0.0f ). I believe that x coordinate is throwing me off. Should I patch the error by rounding? Or do I have larger problems I need to look into?

Thanks in advance!

Share this post


Link to post
Share on other sites
jyk    2094
Quote:
I see. It sounds like the solution I am looking for then. I will look into it. Do you have any further reading suggestions on swept collision detection?
Here is a good article on swept-sphere/triangle collision, which includes discussion of sphere-vertex and sphere-segment tests. Dave Eberly's site geometrictools.com has information on SAT in general and OBB collision in particular, and I believe code for sphere-box intersection as well. This article (membership to the site required) covers swept spheres and AABBs (but not the sphere-box test). There's also GJK, but from my experience with it so far it's considerably more difficult to implement than the other aforementioned algorithms.
Quote:
Also, while I am it, I wanted to know how big a problem floating point errors will be in collision detection. I have a case where a is use D3DXVec3Transform to transform a point (represented as a D3DXVECTOR3 so all 3 coordinates are floats) using a matrix (again, all floats). The result point should be at (0,0,0) but it lands up at about (-3.145e-5f, 0.0f, 0.0f ). I believe that x coordinate is throwing me off. Should I patch the error by rounding? Or do I have larger problems I need to look into?
I'm not an expert on precision issues, but that degree of error looks typical and within reasonable limits to me.

You're right to be cautious though; robustness is one of the more challenging aspects of implementing a collision detection system. The most typical solution I've seen used in practice is to 'absorb' the error with an appropriate epsilon; what 'appropriate' means depends on the circumstances. For detailed discussion of these issues check out this book and this book; both include chapters devoted to the topic.

Share this post


Link to post
Share on other sites
megizin    126
Thanks so much! All of this really helped!

I'll go through those references and I may have gut my current collision detection system (;o;) but all in the interest of getting something more robust more accurate.

Again, thanks!

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