[cairo] proper butt-capped line ends

[Simon Budig]

PARENTAL ADVISORY:
This post has excess length and contains math language.


EXECUTIVE SUMMARY:
Cairo fails to properly draw specific butt-capped line ends. This mail
describes my investigations from last night on how to resolve this and
how to hopefully resolve the issue.



Hi all.

At Guadec I had a delightful discussion with Carl about the butt-capped
line ends and how cairo fails to draw them properly.

The problem shows up with butt-capped lines that have a big change of
direction towards an end:
   
   http://www.home.unix-ag.org/simon/files/cairo-lineends1.png

This is a bezier segment drawn with a line width of 0.4 and
    cairo_move_to (-0.8, -0.8);
    cairo_curve_to (-0.7, -0.8, 0.7, 1.05, 0.7, 0.7)

As you can see both ends happen to expose artefacts, although the lower
end does go into the endpoint pretty straight. However, its tanget
differs a lot from the direction the segment comes from.

If one knows how cairo constructs the outline of a stroke, this result
is perfectly easy to explain, however, if you show this to
$ramdom_person they pretty much immediately see that this result is not
really expected.

So when discussing this with Carl we had to figure out what we expect
here, and we had a consensus pretty fast: the mental model for the butt
ended stroke is moving a 1-dimensional "pen" of a certain width along
the line such that it is always orthogonal to the bezier segment:

   http://www.home.unix-ag.org/simon/files/cairo-lineends2.png

here the blue lines are some "dabs" of the pen with some spacing
inbetween. Note how there are areas covered by the pen that are not
covered by the current stroking algorithm - the blue lines on the
background color.

Rinse, repeat, do lots of dabs:

   http://www.home.unix-ag.org/simon/files/cairo-lineends3.png

Ok, I consider this the desired result.

If you look at the line ends you'll notice that the ends are not
straight lines, they are curved in a nontrivial manner. So last night I
sat down and tried to figure out what happens there.

Have a look at the upper end of the bezier segment:

   http://www.home.unix-ag.org/simon/files/cairo-lineends4.png

With the blue dabs at a low density an interesting pattern emerges,
apparently there is an "interesting point" where lots of dabs seem to
kind of meet and fan out into the to-be-filled artefact. It is no
coincidence that this happens somewhat symmetrically to the point where
the curvature of the bezier segment is big. It turns out, that this
interesting point is the center of the osculating circle of the
most-curvatured point on the bezier-segement (the radius of the
osculating circle is the inverse of the curvature).

Thinking from there reveals, that the ends of the "fan" are the centers
of the osculating circles with the radius equal to the stroke radius
(i.e. half the stroke width), it took me a while to realize that in fact
the curve we're interested in - the curve describing our desired shape -
is actually the trace of the center of the osculating circles:

   http://www.home.unix-ag.org/simon/files/cairo-lineends5.png

Here the centers of the osculating circles are marked as red dots, note
how they match the desired shape perfectly.

Ok. So we have an idea what is supposed to happen there, but
unfortunately the curvature of a parametric curve is not exactly easy to
handle:

           x'(t) y"(t) - x"(t) y'(t)
   c(t) = ---------------------------
	    (x'(t)² + y'(t)²)^(3/2)

the radius of the osculating circle then is   or(t) = 1/c(t)

Granted, most of these values are already calculated when traversing the
bezier segment, but still it would mean a lot of usually unneeded
calculation - note that we only need this when or(t) turns out to be
smaller than the stroke radius, which is usually not the case.

So how do we detect if that kind of situation happens? I believe it is
not actually *that* hard (But pleae bear in mind, that I am not
familiar with cairo internals, so things might be a bit different than
described).

If I understood Carl correctly cairo basically calculates the endpoints
of my blue "dabs" and inserts additional points if it turns out that the
angles from one to the next differ too much and would result in a
outline with unwanted polygonal edges.

So when constructing the endpoints of the blue dabs and traversing along
the bezier segment we could detect, if the new dab intersects with the
previous (I think this can be done cheaply). If this is the case we ran
into a situation where the curvature becomes too big. We then can either
calculate the proper center of the osculating circle or just take the
intersection point. Although this would need some stress testing I
strongly suspect, that the latter already works good enough for our
purposes.

I have not yet implemented all of this, although the math is nearly
there. The python based testbed I used for the graphics is available at

    http://www.home.unix-ag.org/simon/files/cairo-linetest.py

Some usage hints:
   - the bezier coordinates are hardcoded at the beginning of the
     expose_event() function.
   - 'q' quits the program
   - 'f' toggles fullscreen
   - '+' increases the number of dabs
   - '-' decreases the number of dabs
   - 'z' cycles between full view and zoom to the endpoints.

The code contains some comments regarding the math.

So, comments? thoughts? Is this feasible to implement in cairo?

Bye,
        Simon


PS: I am always stunned, when examining that kind of stuff results in
amazing pictures one could create a screensaver from... I love the
beautiful rendering of cairo and there are not enough 2d-cairo
screensavers out there.

-- 
              simon at budig.de              http://simon.budig.de/