Re: [ft-devel] Signed distance fields: distance from any point to the glyph contours

[Behdad Esfahbod]

On 12-10-31 07:25 AM, Alexei Podtelezhnikov wrote:
> On Tue, Oct 30, 2012 at 6:56 AM, Nicolas Rougier
> <address@hidden> wrote:
> 
>> My question relates to a more direct way to compute the signed distance and 
>> to know if anyone has already coded it by any chance ? Said differently, is 
>> there a quick way to compute the shortest signed distance from any point 
>> (x,y) to the glyph contours ?
> 
> Quick? I do not think so. A glyph outline is a collection of contours
> is a collection of straight segments and Bézier curves.For the
> straight segments it is trivial. It is very difficult but surely
> doable for the conic and cubic curves. No it is not implemented.

Distance to a cubic Bezier involves solving a fifth degree polynomial.  There
are acceptable approximations.  As usual, Jim Blinn has the answer.

My approach in GLyphy (glyphy.org) has been different: I approximate the
Bezier with a circular arc spline and arrange the resulting splines in a grid
for fast random access.  The algorithms involved can be made fast, and are
mathematically very stable.  The arc approximation is part of GLyphy API if
you are interested.

Cheers,
behdad