Wednesday, August 26, 2009

Distance to a Quadratic bezier curve

Recently, after viewing this illuminating animated GIFs, I realized that finding the closest point on a quadratic Bezier curve to a given point M might be not so difficult ...and very useful for detecting collision between a disk and a quadratic curve.

Quadratic Bezier curves are familiar to flash programmers, because these are the curves they draw with functions like Movieclip.moveTo() and Movieclip.curveTo().

Such Bezier curve is defined by 3 points: P0, P1, P2.
P0 and P1 are the extreme points, and P1 is a middle point determining curvature.

The curve can be parametrized with the formula:

P(t) = (1-t)²P0 + 2t(1-t)P1 +t²P2.
t is a parameter variable walking from 0 to 1. When t = 0, you are at point P0, and when t = 1, u're at P2.Each point of the curve has a corresponding "t".
The above-mentioned animated GIFs greatly help to "geometrically" grasp not only the quadratic curves, but also higher order Bezier curves .

Now, the key step is to get the derivative (back to school!! ) of P(t):
dP/dt(t) = -2(1-t)P0 + 2(1-2t)P1 + 2tP2
which can be rewritten as:
dP/dt(t) = 2(A+Bt)
where A = (P1-P0) and B = (P2-P1-A)
(note: A and B have a geometric signification: they are the diagonals of the parallelogram defined by P0,P1,P2 and a fourth point kind of "opposite" from P1)

The derivative is a vector representing the "speed" at point defined by P(t). It also has the property to be a tangent to the curve at point P(t).

Now let M(x,y) be our point (which can be anywhere) and we want to find out a point P' (defined by t') on Bezier curve that is the closest possible to M.

P(t') will meet the condition:

MP.dP/dt = 0
(where "." is the dot product of 2 vectors)
that is, MP will be orthogonal to the tangent at P.
Rewritting this condition yields:
(M - (1-t)²P0 + 2t(1-t)P1 +t²P2).(A+Bt) = 0

...After a (boring ) calculus you get a third degree equation (ouch!! ):
at3 + bt² + ct + d = 0,
where a = B², b = 3A.B, c = 2A²+M'.B, d = M'.A, (and M' = P0-M)

If we can solve this equation, we get 3 possible solutions for t !!
How to solve a third degree equation is explained here (in french).
Now we have a maximum of 3 solutions t0, t1, t2 and find the one fitting in [0,1] and minimizing dist(M, P(t)) is easy !!

Here is a demo:

Drag the circled dots
P0 and P2 are the blue points, P1 is green , M is red.
T
he yellow dot is the closest point, the orange dot indicates the normal to M.

After this, I realized that Andre Michelle had already posted a ball collision detection on his blog a long time ago. But the source wasn't available (at least I didn't work for nothing )...

The source code (AS2, FLA CS3 + Bezier.as).
Translating it into as3 should be no problem .

[UPDATE 2012/08/06] I fixed the issue pointed by makc3d. Now the end points are included as a possible solution, which is more consistent. I added a flad "onCurve" indicating if the closest point is on the curve itself (true), or one of the end points (false). The "oriented distance" is negative when the point is on the right of the path formed by [P0,P1,P2]. For backward compatibility, I kept this info in the variable "orientedDist", but it loses its meaning when the closest point is not on the curve.

Thursday, August 20, 2009

"Contour following" !!

"Contour following" is fashionable these days !!
ScoreLight is a musical device using a "tactile" laser trying to follow the contours of the shapes it lightens.
This video speaks for itself:


"There is no camera nor projector: a laser spot explores the shape as a pick-up head would search for sound over the surface of a vinyl record - with the significant difference that the groove is generated by the contours of the drawing itself", says the ScoreLight project page.

StickyLight, a previous version, also explored some possibilities of "contour following":
http://www.todayandtomorrow.net/2009/08/03/sticky-light-scorelight/
I like the way these tiny luminous globules move on the surface of purely graphic shapes... so sensual ... Although deterministic, they seem almost alive. It also conduce interesting reflections about perception: quoting StickLight project page, "By moving on the drawing, the light spot attracts the attention of the viewer. It actually forces our sight to follow the dynamic path taken by the light".

Another "contour following" behavior recently appeared in "Spider: The Secret of Bryce Manor", an iPhone game. As a regular spider, you stick to walls and objects (and thus "follow contours"), but the game seems to focus more on jumping, capturing insects, and web weaving.


There is no official page about this game, but Tiger Style studio gave interviews for PocketGamer and TouchArcade.

"Contour following" will also occur in my Microbe game , currently in production (more info on "Microbe" project" soon !!).
Some years ago, I made a Flash prototype for testing a contour following algorithm on boolean shapes:

(click near a shape to stick the robot. Blue and White shapes can be drag&dropped)

Although "Microbe" game will not necessarily use the same algorithm (aah.. these good ol' 2002 actionscript 1 ), "sticking" will be a core mechanic of the gameplay!

If you know other "contour following" (2D) applications, don't hesitate to add a comment !

(Thx to Lolo and Magicfred for sending ScoreLight and Spider URLS)

Saturday, August 15, 2009

Goswf integration in your blog

Test:


Yess, it works !!!

In 2008, I released Goswf, a light-weight viewer for displaying Go games on websites (forums, blogs, etc., ...).

Goswf can now be displayed in vertical format, which is much more suitable for blogs.
I've also simplified color management for more esthetic integration in hosting websites.

Check this tutorial for integrating in your blog.

[EDIT: this method only works with a Blogger blog (example here). If you use a different blog system, you have to host goswf.swf and SGF files either on this system, either on your own server. In the example above, goswf and the SGF file are located on my server at www.gludion.com]



© Gludion/Olivier Besson - 2007