Jump to content
  • Advertisement
Samuel Wahlberg

Algorithm Moving circle to Aabb collision

Recommended Posts

This is my first post to this forum and I have tried to search for an answer before posting. I do apologize in advance if it has already been answered.  

I am coding a rather simple "breakout" type of game but need rather accurate collision also for fast moving objects. Basically the moving object is always circles and the objects that would change the directions of the circles are always AABB's. I know how to calculate the closest points from a circle to an AABB and I know how to use line segment to AABB (slabs) collision checks. My idea is to from the current circle position add the velocity vector and put a new circle in the new position and use line segment parallel with the velocity vector for the "edges" between original position and displayed position.

However my question is how to get the fraction of the movement to collision accurate so I within the same time step can go to the intersection and for the rest of the movement within that time step move it in the new direction? The player will be able to increase the speed so the movement between time steps might be quite big. With a pure slab test I would get the fraction but it would be hard to describe the circle at the end of the circle with pure line segments without getting to many and getting poor performance. Would it be a decent solution to do a binary search on the velocity vector until it is not colliding but closest point is within an allowed maximum? Is there better algoritms to accomplish this?

CircleAabb.png

Share this post


Link to post
Share on other sites
Advertisement

This is a non-trivial test or at least I am not aware of a simple solution I could explain in reasonable time here. You might be able to use a Minkowski space approach. But to be honest I would just use conservative advancement. I recommend googling for some solution and then come back when you run into more specific problems. Sorry, I cannot be of more help.

PS: I would start looking into C. Ericson "Real-time Collision Detection" or Gino v.d. Bergen book. Alternatively the collision detection part of "Real-time Rendering" is available for free here: http://www.realtimerendering.com/Real-Time_Rendering_4th-Collision_Detection.pdf. "Essential Math for Game Developrs" has also a lot of resources here: https://www.essentialmath.com/

 

Share this post


Link to post
Share on other sites

Thanks for the response. I will look at the litterature you recomended as well as checking out conservative advancement.

C. Ericsons book is really good! The other ones will be interresting to check out.

Share this post


Link to post
Share on other sites
Posted (edited)

 

11 hours ago, Samuel Wahlberg said:

Would it be a decent solution to do a binary search on the velocity vector until it is not colliding but closest point is within an allowed maximum? Is there better algoritms to accomplish this?

Add a 3-rd dimension. By other world add a time as fird axis. As result you will have a 3D AABB alligned to t axe and capsule for circle, Intercection of witch will give accurate coords and time of impact.

Edited by Fulcrum.013

Share this post


Link to post
Share on other sites

If you're still looking for suggestions, here are a couple more ideas to consider.

An exact continuous test for this isn't too impractical. It can be done by intersecting a line segment representing the motion of the center of the circle with the Minkowski sum of the box and the circle (I think Dirk mentioned this approach). The Minkowski sum of a box and a circle is a larger box with rounded corners. A little ways down the page here:

http://allenchou.net/2013/12/game-physics-collision-detection-csos-support-functions/

You can see a nice diagram of what the shape looks like (the original box with a circle centered at each corner and a 'rubber band' stretched around the perimeter forming the rounded box).

The intersection time between a moving circle and a box is the same as the intersection time between a moving point and the Minkowski sum of the box and the circle, which leads to the line segment vs rounded box test I mentioned earlier. Once you have the time of collision, you can move the circle accordingly. Then you can find the closest point on the original box to the circle center, which will give you a contact point and normal.

As is usually the case, there are various numerical precision issues to consider, both with the intersection test and with collision response. A simpler but perhaps less performant solution would be to subdivide the circle's move into multiple steps, the length of each being less than the circle's radius (if I'm not mistaken this is different than the aforementioned conservative advancement, but may have a similar flavor). This eliminates the numerical issues associated with the continuous test. This approach isn't entirely free of issues though (although it should prevent obvious tunneling, the circle can still 'skim by' corners when it shouldn't, which may or may not be a problem, depending on the context).

Share this post


Link to post
Share on other sites

I was so surprised I couldn't find a reasonable simple solution to this problem and I discussed it with some colleagues this morning. The simplest solution we came up is described below. I haven't implemented and tested it yet though.

The key observation is that you can approach this problem per axis. Essentially a dynamic separating axis test. In 2D the first two separating axes are the face normals of the AABB which are simply the global x and y axis. You need to compute the enter and exit times (t_min and t_max) where the distance of the moving sphere center along these axes becomes equal to the sphere radius. If you now inspect the case where the moving spheres hits just a vertex you will notice that these two dynamic separating axes tests are not sufficient. You need to test a third separating axis which in 2D is simply the direction vector of the ray the sphere is moving along.  So in total you will get three intervals (one pair of t_min and t_max per separating axis) and the solution is simply the intersection of the three intervals.

If I find time I might add some sketches and code examples later.

 

HTH,

-Dirk

Share this post


Link to post
Share on other sites

If I remember correctly when I did this in 3D with sphere mesh collision you had to do something like check for collisions with the planes of the triangles, check the collisions with the edges of the triangles and check for collisions with the vertexes. I think in 2D you just have edges and vertexes.

So for the edges I think you can just take the radius of your ball and move the lines of the box out that far. Now you just check for the intersection of two line segments, the path of the center of the ball and moved edges.  You only need to check edges that you are moving towards the front of.  If that fails you move on the the corners. for that you just put a circle with the radius of your ball at each corner and again check the line segment that is the path of the center of your ball with the circles.

I think this is basically the same as the Minkowski stuff that Zakwayda was talking about. It's actually not that hard. It's just a line/line intersection and a line/circle intersection.  It should pretty much never fail.

 

Share this post


Link to post
Share on other sites
Posted (edited)

Th

Quote
39 minutes ago, Gnollrunner said:

If I remember correctly when I did this in 3D with sphere mesh collision you had to do something like check for collisions with the planes of the triangles, check the collisions with the edges of the triangles and check for collisions with the vertexes. I think in 2D you just have edges and vertexes.

 

Well, that is indeed correct and of course you can sweep the sphere against each individual feature (face, edge, or vertex) of the AABB. But this is also the most expensive solution and unpractical in my opinion. 

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites
Posted (edited)
29 minutes ago, Dirk Gregorius said:

 This is also the most expensive solution and unpractical in my opinion.  

Well it's used in hordes of 3D games and it works plenty fast.  I'm not sure why you think it's expensive and unpractical.  For your application it should be a piece of cake, but it's your project.

Edit: Oh sorry thought you were the OP, but In any case my commentary still stands.

Edited by Gnollrunner

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!