[cairo] Where are the stroking (and filling) guts?

[Chris Wilson]

On Wed, 30 Jun 2010 13:22:27 +1200, Lutz Gehlen <lrg_ml at gmx.net> wrote:
> Hello everybody,
> I would like to learn a bit more about stroking and filling is done
> in modern graphics software, mainly out of academic interest. I am
> particularly interested in thick stroking including antialiasing,
> but also in filling.

There are two methods in cairo:

  fill -> polygon -> traps -> pixman rasterise [xrender]
  fill -> polygon -> scanlines [image]

Stroking is basically the same. The current method is a little naive:

  stroke -> [self-intersecting] traps -> tessellate traps -> pixman
  stroke -> polygon -> scanlines

The plan for the future is to implement stroke-to-path and so reduce a
stroke to a fill. Also, the simplification step of using a polygon
[flattening curves to straight lines under the constraint of geometric
tolerance]  may be removed with a more complicated scanline converter.

In order to understand the rasterisation, I would suggest reading,

  cairo-bentley-ottmann.c

This is the classic method for converting a polygon into a set of
trapezoids and conceptually the sweep line is the basis for most of the
other algorithms. The more modern rasterisation techniques simply fold the
generation of opacity data straight from the sweep line (circumventing the
intermediate trap generation and later rasterisation). This is a win since
the same information is computed in order to process the sweep line and
detect intersections as is used for computing the coverage of an edge.
Here there are two examples of scan line converters to read:

  cairo-botor-scan-converter.c

     This is an analytical coverage computer that combines the event
     processing from Bentley-Ottmann with the edge walking from the Tor
     scan converter.

  cairo-tor-scan-converter.c

     This is a subsampling scan converter based around walking along
     active edges by sweeping a line through the geometry.

However, I would thoroughly recommend getting a computational graphics
textbook such as O'Rouke and use that as an introduction to the algorithms
as we claim our implementations neither to be optimal nor very clean. The
BIBLIOGRAPHY should have a few more pointers to books and papers of
interest.

Hope this helps, and you have fun digging into the internals of Cairo --
we do! Anybody who can maintain the pretense of sanity after reading
through the tessellators and scan converters is very welcome to join us!
If you have any quick questions you want answering, don't hesitate to ask
on #cairo.
-- 
Chris Wilson, Intel Open Source Technology Centre