Sign in to follow this  
RPTD

Moving Sphere against AABB Collision

Recommended Posts

Looks like my SphereMoveHitsBox code has a bug yielding false positives. Looking around the net though I could not find a working example of a moving sphere against AABB collision test. Anybody knows how this can be done if it can be done?

Share this post


Link to post
Share on other sites
Of course it can be done :) (Check geometrictools.com for an example implementation.)

Share this post


Link to post
Share on other sites
I've checked this place already. There is no "moving" sphere-aabb test only a static sphere-aabb test... unless I overlocked something.

Share this post


Link to post
Share on other sites
You can either step the sphere along the path, ie a swept sphere, or possibly use the sphere's displacement as a ray and see if it intersects the box.

Ericson's Real Time Collision Detection is excellent and I think has some examples of a swept sphere.

Share this post


Link to post
Share on other sites
A stepped sphere is not an option, I need correct TOI (Time Of Impact). What's this "Ericson's Real Time Collision Detection"?

Share this post


Link to post
Share on other sites
Quote:
Original post by RPTD
I've checked this place already. There is no "moving" sphere-aabb test only a static sphere-aabb test... unless I overlocked something.
Take another look at the 'intersection' section (there's a section with the heading 'Intersection of boxes and spheres (3D). Includes the cases of moving spheres and boxes.').
Quote:
Original post by RPTD
What's this "Ericson's Real Time Collision Detection"?
It's a book by Christer Ericson. (I don't have it in front of me right now, but IIRC it doesn't cover the specific case of moving sphere-vs.-box. Again though, I'm not looking at it right now, so don't hold me to that. If you want to know for sure, you could probably find the TOC online somewhere.)

Share this post


Link to post
Share on other sites
I could be blind but there is no entry under "Intersection" even remotely matching the suggested name. The only thing I found is "Intersection of Convex Objects: The Method of Separating Axes" which also contains SAT for moving objects. Unfortunately this doesn't seem to properly work with sphere versus a box. I implemented this one and it works in some cases but the simple case of a sphere moving along a box axis towards an edge without hitting it results in incorrect early collision. Most probably incomplete axis set but I really have no idea anymore what else I could include (I'm using box axis x/y/z, moving direction and moving direction cross box axis x/y/z).

Share this post


Link to post
Share on other sites
Ah, found it now. I always looked under the "documentation" place as this is where the papers are located. Thanks for the tip.

Share this post


Link to post
Share on other sites
Took a look at the sources. From what I get they use something similar to mine just with the problem that this is not correctly working. An important border case is not handled which is exactly the one causing me to look for a better algorithm. Shoot... looks like their code example won't be of help as it is incomplete as mine.

Share this post


Link to post
Share on other sites
Could you explain said border case? (I haven't bothered looking at the link)

What you're asking for should be pretty straightforward. I can only really invision three collision cases:
  • sphere with side
  • sphere with edge
  • sphere with corner


The first is very similar to testing for AABB collisions, and the last is almost identical to sphere-sphere. The second is a little trickier I guess, I'd be projecting to a plane to which the edge is normal (for AABBs that's effectively just ignoring a co-ordinate) to effectively turn it into a 2D circle-point problem.

If you provide a little more detail on motion (obviously the nature of motion of objects involved is typically very important in a priori), I might be able to give a better response.

Share this post


Link to post
Share on other sites
I'd be a little surprised if the code you found there was incomplete. What's the border case you refer to?

Share this post


Link to post
Share on other sites
The problem is a sphere near an edge with a velocity aligned with a box axis. In my case I had a tilted box connecting to another non-oriented box (sort of ramp up to a plateau). Getting close to the plateau-box collision acts weird detecting collisions too soon leading to the player (the sphere) making a motion like moving over a bump at the edge.

From my look through the code though I think I see what they try to do. To my understanding all three cases should be doable with a closed solution. I've to calculate this through on a piece of paper then I know more.

Share this post


Link to post
Share on other sites
Well, that sounds like an ill-conditioned numerical solution. This stuff is always a bit of a bitch.

I imagine you should have sphere-edge down to circle-point, no? Looking back on some working I did on this stuff a while ago, circle-point (or hypersphere-hypersphere in general) is a quartic problem under constant acceleration, or a quadratic problem under no acceleration. I know of situations in which quadratic closed forms can go ill numerically, and I know of work-arounds to that; but quartics and other means are another kettle of fish entirely.

Could you be more specific about which (regardless of whether or not it's either of these) your situation is? I cbf looking at jyk's code, especially given it may or may not be relevant to your problem.

Share this post


Link to post
Share on other sites
Got it working now using my own code with closed solutions. Quite a bit shorter than the version mentioned on that page and so far stable and working correctly in my tests. Boils down to testing at max 3 faces (sphere-AArect), 3 edges (sphere-AAedge) and 1 vertex (sphere-vertex). All of them closed solutions including one simple quadratic equation for each edge test. The code is actually quite simple and should (from my judging) not be affected much by numerical instability even if used with float instead of double. Runs smooth and stable here. For me that's enough.

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