[cairo] Re: cusp singularities while stroking

[Eric Hughes]

At 06:13 PM 11/1/2005, Carl Worth wrote:
> > I wanted to ask you if they were there "on purpose"
> > or as a consequence of your rendering algorithm.
>
>They are a consequence of the rendering algorithm.

These cusps are generic singularities.  Any reasonably good 
algorithm, i.e. not completely ad hoc, is going to have them 
somewhere, even if they don't end up being displayed.

>I'd really rather drawing something else
>instead, (namely the evolute that would be formed by a line of the
>stroke width drawn perpendicular to the path at every point along the
>path).

In the foregoing, I'm going to use the language of continuous 
differential geometry.  This is analytical and precedes 
discretization.  So if I don't talk about pixels, it's not that I 
don't believe in them, but that I'm thinking about a piece of the 
pipeline where they don't apply yet.

If you have a defined "stroke width" that's constant for an entire 
stroke, that implies a circular pen and only a circular pen.  The 
"perpendicular to the path" locus you describe isn't correct, even 
for an elliptical pen.  The correct generic algorithm for convex pens 
of arbitrary shape involves tangent parallels.  At each point on the 
path there's a tangent vector.  To that tangent vector correspond 
exactly two points on the pen outline that have parallel 
tangents.  (There are exactly two because we've assumed the pen is 
convex.)  For a generic point on the path (generic=nothing special 
about it), these two points of tangency are the ones that appear on 
the boundary of the stroke image; all other points on the pen are in 
the interior.

What you're doing currently is picking a single point on a polygonal 
approximation as the "farthest away" point.  This is correct 
according to the preceding algorithm because in polygons may be 
treated as degenerate continuous closed curves.  Consider a generic 
continuous curve and a non-generic (because degenerate) pen.  Given a 
tangent slope and a convex polygon, there tangency is either one 
vertex or on edge and its two vertices .  It's one vertex if the 
tangent direction doesn't appear as the direction of an edge.  It's 
an edge if the tangent direction is also that of an edge.  In this 
case the vertices accumulate almost all the tangent directions.  The 
generic points on the curve in this case (a case with a non-generic 
pen) are those where the tangency to the pen a single vertex.

>  But we haven't yet solved the problem of how to accurately
>compute that evolute.

The difficulty is, as always, with the points that are not 
generic.  For this you need the full geometric apparatus.  The 
easiest important observation is that the mathematics is that of the 
caustics of wave fronts.  The good news is that, mathematically, the 
situation is quite well understood, even if it's something of a specialty.

Consider waves propagating from the surface of an ellipse 
inward.  Near the ellipse, the wave front is also basically 
elliptical.  At some point, the waves begin to self-intersect.  This 
is where caustics begin.  To think about pens and drawing, consider 
the thought experiment of drawing a sequence of strokes on a smooth 
path with a family of pens of identical shape but different 
sizes.  When the pens are small enough, all points on the path are 
generic.  At some pen size, however, there begin to be non-generic 
points on the path.

The essence of the difficulty is what to do about 
self-intersection.  The benefit of singularity theory applied here is 
that singular points allow you to track where self-intersections 
start and stop (roughly).

As a final thing to consider for now, consider the case where the 
point on the path is not in the interior of the pen.  There's 
typically the idea that the path point is on the interior, and even a 
special interior point like the center or centroid.  There's no need 
for such an assumption.  An algorithm that works correctly for 
arbitrary pen shapes will also work when the path point is outside 
the pen.  In such a case, the stroke will generically have loops, 
that is, transverse self-intersections of the local stroke outlines.

>This all sounds very interesting to me. Yes, I'd be glad to see some
>pointers to more information along these lines.

Here are a couple of reference books.

_Catastrophe Theory_, Third, Revised and Expanded Edition, by V. I. 
Arnold.  This little book, small format and only 150 pages, is an 
inspirational gem.  It's not particularly formal, although it's 
serious mathematics.

_Solid Shape_, Jan Koenderink.  This is a primer on differential 
geometry for applications.  It mostly deals with three dimensions, 
but the mathematics is all relevant.

Eric