Collision detection with curves

Question

I'm working on a 2D game in which I would like to do collision detection between a moving circle and some kind of static curves (maybe Bezier curves).

Currently my game features only straight lines as the static geometry and I'm doing the collision detection by calculating the distance from the circle to the lines, and projecting the circle out of the line in case the distance is less than the circles radius.

How can I do this kind of collision detection in a relative straightforward way? I know for instance that Box2D features collision detection with Bezier curves. I don't need a full featured collision detection mechanism, just something that can do what I've described.

---

UPDATE: Thanks a lot for the great answers! I'll have to read up on Bezier curves to fully understand the method you've described. Then I'll get back to you.

Answer 1

29/09/2012 - 23:20

I created a git Repo here: https://github.com/ArthurWulfWhite/Bezier-Distance/

You are welcome to download the source files as a zip from there. It also includes a demo you can compile using FlashDevelop. To use the demo, open the project in Flash Develop and click 'Test Project'. While running the demo, click the LMB to randomize a new Bezier curve and a new Circle.

Good luck!

The zip link is hard to see - just use Ctrl + F and type zip. This source represents a couple of weeks of reasearch and programming, I hope you enjoy it.

---

If you plan on dividing the bezier recursively into segments and checking for collisions with them, I suggest making a 100,100 array (grid) and placing each segment in the four nearest squares, so you only have to check for collisions with 4 / 10,000 of the segments each frame.

I do think you will benefit from box2d both as a programmer and as a game creator, since there are lots of hidden little hurdles in making a 'simple' physics engine that make the motion seem a little bumpy and less fluid then it could be.

Old answer: The pure way.

You can actually see if a circle is colliding with a Bezier curve, by checking the distance between the distance between the center of the circle and the closest point on the curve.

The equation for the distance (in general)

explained:

Bezier equation:

q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

This can be summed up to (with some algebra) - I will omit .(x,y) for readability (they are still points, not one number)

q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start

The distance from point (x,y) is:

sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)

To find the closest point on the bezier to the ball, you need to derive and find all the points where the derivative equals zero (the roots). It is a polynomial of the third degree so you could use a closed formula but it could be unreliable since the precision of the computer floating point represented fractions may not be sufficient. It is far better to use Newton or something of that nature.

The derivative you need to find the roots for is:

Assuming: a = start b = control c = end d = cirlce center point

The tricky part is multiplying this points, you have to use dot product.

If you like, I have the code for this and I can share it here in the form of a function that simply returns a boolean if there is a collision or not and an angle of collision. Some problems could appear in naive implementation of a collision engine like this for instance a fast moving ball could get caught between two curves.

I recommend avoiding it for now, just sum up the coefficients for the x axis and for the y axis and add them up.

The use any reliable method you may choose like Newton to find the roots, check the distance from the root points on the bezier, 0 <= t <= 1 to the circle center and check the distance for the two ends of the bezier (start and end) to the circle center, whichever one is closest, will tell you if there is a collision.

If the radius is smaller than the minimal distance, there is a collision.

The angle is approximately the one between the center of the circle and the closest point on the bezier.

That being said, if you truly wish to make a game with collision physics, I suggest you just iterate over the bezier

    q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Divide each piece in the middle recursively until it is small enough, lets say 10 pixels or less, then build the bezier roughly from boxes and use Box2d for the physics cause it is possible that writing all this collision detection code will prove to be a great time sink that doesn't enhance the gameplay much. Using Box2d has proven itself in countless projects in the past.

Answer 2

To do this, I would :

• Break the bezier curve into severals line segments and store them.

• Put all these segments in a axis aligned bounding box for the whole curve.

Collision detection :

1) check if sphere is inside the main bounding box. if no, no collision.

2) otherwise, check if any of the individual segments calculated above collide with sphere. See Line–sphere intersection article from Wikipedia.

EDIT : if you need high precision and want good performance, you can also create a main bounding box for the whole curve, then subdivide the curve in two segments (eg : [0.0 - 0.5] and [0.5 - 1.0]). Create a bouding box for each of them, then again subdivide each of these segments in two segments (thus giving [0 - 0.25], [0.25 - 0.5] and [0.5 - 0.75], [0.75 - 1.0]). Continue like this until you reach enough precision. in the end you will have a binary tree of bounding boxes with main curve bounding box at root and line segments at the leaves. searching in in the tree will gave you O(log n) instead of O(n) (where n = number of line segments for the curve)

Answer 3

The intersection between a line and a Bezier curve is achieved mathematically by subdividing the curve. This means relying on the curve's convex hull property and dividing it into smaller arcs with different control polygons in a divide-et-impera-like fashion.

This article covers it upto a point: http://students.cs.byu.edu/~tom/557/text/cic.pdf.

The nice part is that the algorithm works with any line, you just have to apply a rigid transform to the curve so that you can consider your target line as being parallel to the Ox axis.

Similarly, you can check against the circle and the polygon of each such a bezier arc when you subdivide a Bezier arc into two sub-arcs. The circle should intersect the control polygon of an arc for a curve-to-circle test to make sense.