[cairo] Re: cusp singularities while stroking

[Eric Hughes]

At 06:15 PM 11/1/2005, Carl Worth wrote:
>I think there's a way to generalize the algorithm to handle non-convex
>pens. But I haven't developed the concept fully yet.

It's not obvious, that's for sure.

To get a handle on non-convex pens, it's useful to consider the Gauss 
map for the pen.  The Gauss map of an n-dimensional surface (in an 
(n+1)-dimensional space) is the map of the unit normal vector of the 
surface to the n-dimensional sphere, considered as the set of all 
unit normal vectors.  Consider pens as a 1-surface (a closed 
contour); the Gauss map is onto the circle (the 1-sphere).

Convex smooth pens have a Gauss map without singular points.  A pen 
with concavities, though, has "folds" in the map.  There are two 
kinds of interesting points here.  The first are bitangent 
points.  Bitangent points generically come in pairs; they have 
parallel tangent directions but also collinear tangent lines, that 
is, there's one tangent line with two tangent points.  Bitangencies 
are generic to concavity; multitangencies higher than 2 are not.  The 
convex hull of a non-convex shape contains all the bitangent points; 
they are the places where the hull joins to and separates from the 
shape itself.

Within the arc defined by a bitangency there's at least one point 
with a normal parallel to those of the bitangency (this is a 
generalization of the mean-value theorem you learned in 
calculus).  Hence concavities generate Gauss maps that multiply 
cover; in the simplest case it's a triple covering.  The boundary 
between single covering and the triple covering happens at the 
folds.  The preimage of the folds happens at inflection points of the 
curve, where the tangent line crosses it.

So why are these significant.  In my previous message, I mentioned 
that for convex pens, only the points of parallel directionless 
tangency to the path are on the boundary of the stroke image.  With a 
convex pen, this corresponds to two anti-parallel (same line, 
opposite signs) normal vectors.  With non-convex pens, there may be 
not two points but more.  Consider the simplest case of a pen with 
one "dent".  That is, there is one concavity, two inflection points, 
and two bitangent points.  There are two generic cases: the ordinary 
one, with two points, and the one where the concavity is relevant, 
with one point in one normal direction and three points in the 
opposite direction.  In such a case, there are three candidates for 
points on the stroke outline, and any or all of them may 
appear.  There is also a special case involving the inflection 
points.  The inflection points are the boundaries between the two 
generic cases.

>And we can easily determine
>which pen vertex is "active" by examining the slope of the path
>segment and comparing it to the incoming and outgoing slopes along the
>pen for each pen vertex.
[...]
>More complex pens with additional "locally convex" vertices would
>cause more difficulties for the algorithm. There, in order to get the
>correct result, the algorithm would have to be augmented with the
>notion of multiple pen vertices being simultaneously active.

This is the essence of how to generalize.  In the degenerate case of 
a polygonal pen, multiple vertices may be active.  This is a 
manifestation of multiple coverings in the Gauss map.  The number of 
vertices that need to be active depends on the covering degree of the 
path direction in question.

Eric