[cairo] Cairo in Google Summer of Code

[Jeremy Lea]

Hi,

On Wed, Mar 19, 2008 at 11:13:06AM +0100, Behdad Esfahbod wrote:
> > [Hard] Adjacent-polygon fix. Lots of users try to draw a mesh of 
> > polygons with their edges touching in order to fill the plane with a 
> > colored image. Attempting this on Cairo produces artifacts because the 
> > edges are antialiased and the image has very thin cracks between the 
> > polygons. A huge number of graphics produced popular proprietary and 
> > open-source programs are this way and it is impractical to fix them to 
> > overlapping shapes. Come up with a solution to this.
> 
> Throwing problems we cairo developers have no solution for at students
> and hoping that they come up with a solution for it doesn't work.

This could be done by some sort of RLE encoding of the polygons, if they
were done by scanline (removing the tesselation?).  If you took the
input, once it was in device space, converting it to a list of scan
lines (with a specified start corner from a bounding box - which is
useful anyway - stored in the main structure along with the paint). 
Each line would have series of 'pixels' and advances.  Each pixel would
store the entrance and exit side and point along the side, on a 8x8
grid.  If the entrance and exit points are the same, that would be a
code to say that the next byte encodes the number of interior points,
which would follow, with a final exit side and point.  A special code
could also be used to mean horizontal or vertical, on a 256 point grid.

The advance would then be used to move over as many pixels as needed,
until the bounding box was reached.  A zero advance would mean you still
had more to draw in the pixel.

This would be stored instead of an intermediate raster image of the
polygon.  When the polygon was rendered, you could walk over the lines
and convert them to pixel color levels very quickly.

An example: a single dot in the middle of four pixels...

 +-------+-------+
 |       |       |
 |   ********    |
 |   ********    |
 +---********----+
 |   ********    |
 |   ********    |
 |       |       |
 +-------+-------+

might be encoded as:
 line 1: enter: side 0,4 exit: 0,4 points: 1 (4,4) exit: side 3,4
          advance 1
         enter: side 1,4 exit: 1,4 points: 1 (4,4) exit: side 0,4
          advance 1 (end)
 line 2: enter: side 2,4 exit: 2,4 points: 1 (4,4) exit: side 3,4
          advance 1
         enter: side 1,4 exit: 1,4 points: 1 (4,4) exit: side 2,4
          advance 1 (end)

One would have to spend a lot of time figuring out all the edge cases
and rules for filling... and some time figuring out the most compact way
to encode the data.  By having a codes for 'empty', 'full',
'horizontal', 'vertical' and 'general', you could use a full range of
(0,8)x(0,8) or (0,256) making 4,4 or 128 be the middle of the pixel.

Most scan lines would consist of an advance of empty pixels, a single
complex pixel, an advance of one, a solid pixel with some advance,
another complex pixel, a clear pixel with an advance to the other edge.

If you have multiple polygons, you can merge these quickly, and you
still have enough subpixel information to compute actual coverage
without seams.  This would require a rendering mode were you were
drawing a bunch of polygons to a surface without any intermediate stuff
(like drawing text or getting the image data for a filter).  They could
all be stored in this RLE format, and then the final composite done as a
group.  Masking/clipping could also be done with this RLE format.

Just some random thoughts.

But, this is not a SoC project.

Regards,
  -Jeremy

-- 
FreeBSD - Because the best things in life are free...
                                           http://www.freebsd.org/