[cairo] Optimizing diagonal lines (and more)

Billy Biggs vektor at dumbterm.net
Sun Jul 24 20:39:45 PDT 2005

  I have been looking at the pixman code to see where the time goes when
rendering diagonal lines.  Using libpixman's code, the time is all in
pixman_composite_trapezoids(), split between these major operations:

    - It creates a temporary alpha image to render the trapezoids.
      This surface is the size of the bounding box.
      FbCreateAlphaPicture() memsets this to 0, which takes time.

    - The trapezoids are rasterized to the alpha image using

    - The entire bounding box area is composited to the dest using the
      newly calculated alpha mask and the source picture.

  A single solid-coloured diagonal line seems like the worst case for
this scheme.  The bounding box is huge, making both the memset and the
composite needlessly expensive, and furthermore the mask is rather
heavyweight in the case of disjoint trapezoids, as the compositing could
have been done during rasterization.  The advantage of the current
scheme is that the top-level algorithm is fairly straightforward.

  I think a scanline-based algorithm would be both efficient and still
general enough to be understandable.  The basic algorithm is as follows:

    - Create and clear a single scanline buffer.
    - Foreach scanline in the bounding box:
       =  Rasterize all trapezoids into that scanline buffer, remember
          the first and last pixels touched.
       =  Composite only those pixels, if any.

  Can anyone see any obvious flaws in this proposal?


More information about the cairo mailing list