Sign in to follow this  
Petelnikov

Collision detection in 2D: moving circle vs bezier curve

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
quadratic, ok then, 4th order :)

quadratic :
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

Still, not too bad though.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Nick, in the last lines of my previous message I told about situation (sorry for crude drawing) like this:
problematic situation
If you find only one closest feature of polyline, you can't resolve collision in this situation in one timestep (without iteration).
As for "static" vs "dynamic" test question...
With "static" (or "discrete") you have interpenetration to resolve, and possibility of "tunneling" (with small object or high velocity objects). With "dynamic" (or "continuous") test, you have no interpenetrations and "tunneling", because you get exact time of collision. In "static" test you use only position/orientation of involved objects, but in "dynamic" you additionaly use data about objects movement.
About memory. In general, the more data algorithm touches, the more slowly it works, because memory is slow. In relativly small worlds all frequently used data goes to the caches, but in large worlds probability of cache misses (and therefore performance penalties) is higher. You can read this good presentation:
Memory optimisation

PS: Sorry for my bad english...

Share this post


Link to post
Share on other sites
Quote:
Original post by Petelnikov
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)?
You could try implementing a type of binary search approach by splitting the Bezier curve using de Casteljau's algorithm and then intersect the moving circle against the hull of each part (using the convex hull property of Beziers). When the moving circle does not intersect the hull you skip that part, otherwise you recurse over the piece.

You could also search for "Bezier clipping" to see if that gives you some ideas. Here's some lecture notes that talk about both Bezier subdivision and Bezier clipping: http://cagd.cs.byu.edu/~557/text/ch7.pdf

Glad you found my memory optimization presentation useful, BTW.

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