# Collision detection in 2D: moving circle vs bezier curve

This topic is 4112 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'm trying to solve collision detection problem: I have a moving (with constant speed during timestep) circle and a static quadratic Bezier curve (3 control points). I want to know a time of collision, contact point and normal. Can anybody help with solution (other then approximate curve with line segments)?

##### Share on other sites
Using the bezier equation and the sphere motion equation, it looks tricky, like a 6th order equation to solve.

as for moving sphere / segment collision, tink of it instead as a moving point / capsule intersection. The moving point being the sphere centre, the capsule being the segment, with the sphere radius.

Here's a example. look the function SphereSegmentCollision().

##### Share on other sites
Oliii, thanks for reply, but i know how to do moving-circle-to-segment collision. :)
My first thought was to approximate curve with chain of line segments (polyline) and to do a "moving-circle-to-segment" tests with that chain. But this looks slow...
About equation.. Why 6th order? In my case curve is only quadratic...
P = (1 - t) ^ 2 * P0 + 2 * t * (1 - t) * P1 + t ^ 2 * P2

[Edited by - Petelnikov on March 19, 2007 5:32:42 AM]

##### Share on other sites
quadratic, ok then, 4th order :)

P = (1 - t)^2 * P0 + 2 *t*(1 - t) * P1 + t^2 * P2
(developped)
P = P0 + t * (2.P1 - 2.P0) + t^2 * (P0 + P2)

point motion :
Q(t) = Q + V * t

collision condition :
(P - Q(t))^2 = r^2
(developped)
[(P0 - Q) + t * ((2.P1 - 2.P0) - V) + t^2 * (P0 + P2)]^2 - r^2 = 0

4th order equation (Quartic)
a.t^4 + b.t^3 + c.t^2 + d.t + e = 0

##### Share on other sites
Oliii, t in P(t) is not "time", but a parameter for parametric equation. :) So things are definetly tricky. :)

##### Share on other sites
ah crap... And there are no simplifications, u and t are completely unrelated.

if you have a simple way to calculate the distance of a point versus a bezier curve, might be another way. Should not be too tricky, second order equation, to find the minimum, probably using the derivative, my A level maths not that great :). Then you can do the interval reduction thing. Move sphere forward, sphere_vs_bezier distance < radius, track back 1/2 the time. sphere not intersecting, move forward from that point 1/4 time...

That might be better than using segments, maybe, maybe not.

[Edited by - oliii on March 19, 2007 9:53:05 AM]

##### Share on other sites
To find a closest point on curve to some point R, you must solve:
(R - P(t))*P'(t) = 0 (cubic equation)
Then, you must reject roots that not in [0,1], and choose root that gives minimal distance to R (also, you must consider endpoints of the curve).
As for time interval "bisection"... This would work correctly only in case, when the circle intersects a "closest part" of the curve at the end of time interval...
I'll try to find good approximation for the "offset" curve (think, Minkovsky sum of the curve and circle) and do a segment-to-curve test (by Bezier subdivision or Bezier clipping)...

##### Share on other sites
What I've done for my engine is since I have created a list of lines for the vertex buffer anyway, is to do exactly what you suggested by calculating line segment collisions. To make it efficient I broke the curve into bounding boxes to help cut down on collision checks. I take it one step further by first finding the closest point in my vertex buffer (about 50 points to check for each pair of control points). Then I make a line between the points on either side of this point. This is then the line segment I used for my collision testing. You can see this in action at http://www.gameprojects.com/project/?id=34afb2098e

##### Share on other sites
Nick, as I understand, you are using "static" test. But I'm trying to do "dynamic" test... Anyway, we can discuss your method. :)
With such pretty crude penetration depth vector approximation, you definitely need to use polyline with high number of segments to get plausible results... More segments == more calculation. But what is even more important - high memory consumption with this approach. Memory is a bottleneck, cache is a king. :) With ~400 bytes per cubic Bezier portion, high cache miss rate is most probable in "large world with high number of moving objects" scenario.
So, what can be done?
You can use more accurate penetration depth approximation. You must find closest polyline feature. And that includes not only vertices (as in your approach), but also segments. With this, you can get good results with much lower segments count. So, you can use much simplier polyline for collision than for graphics. In example, 8-14 segments for quadratic Bezier gives you good enough accuracy. In addition, you can reduce segments count with more clever polyline construction. Are you sampling a curve regulary in parametric space? De Casteljau construction can give you better results:
http://people.inf.ethz.ch/fischerk/pubs/bez.pdf
Finding only one closest feature per Bezier portion are not enough for good collision response when you have relatively big circles or splines with high curvature sections.

PS: I'll definitely play with circular arc splines. They have many attractive properties...

##### Share on other sites
Did you see the videos on my page? My method has so far worked fine for any shape I've created. The only instances of failure is when making a bowtie shape with a single section. Also what do you mean by "static" test vs. "dynamic" test. You asked for a moving circle and static Bezier curve. That's exactly what I have done with my engine.

I'm not sure what you mean about the rest of it. The memory issue is negligible as I have to save the vertices for the vertex buffer anyway, it is therefore no additional memory requirements. There is of course a slight problem with my method in that particles seem to come to rest in places they might not otherwise because I am essentially turning two segments into one, but I'm in the process of rewriting my algorithm to take this into account.

Overall however, my method works perfectly well for up to around 250 moving particles on a fairly large terrain. I'm working on more improvements in performance of course to boost this number.

1. 1
2. 2
3. 3
4. 4
Rutin
18
5. 5

• 11
• 22
• 12
• 12
• 11
• ### Forum Statistics

• Total Topics
631406
• Total Posts
2999903
×