[cairo] Re: cusp singularities while stroking
eh-cairo at narthex.us
Tue Nov 1 20:02:54 PST 2005
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
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
>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.
More information about the cairo