[cairo] Survey of polygon rasterization techniques

[David Turner]

There is another reason why Flash needs a specific rasterizer: bezier tesselation
might break the non-intersection nature of the original shapes. For example, consider
the following shape made of concentric circles, that could be described by the
following pseudo-code:

  for n in 1..200:
      circle( xcenter=n, ycenter=0, radius=n, color=random() )

all the circles overlap at a single point location, which is (0,0), apart from that
they are not self-intersecting. let's say these circles are defined as bezier arcs
in the Flash file, the rasterizer will need to convert them to line segments and in
some rare cases, you can have intersections appearing.

each edge in Flash has a "left" and "right" color, in the normal case, when you compute
edge intersections on a given scanline, you will have something like:

(x1,left1,right1)  (x2,left2,right2)   (x3,left3,right3)

with right1==left2 and right2 == left3, for example:

(x1, BLUE, GREEN)  (x2, GREEN, RED)   (x3, RED, BLUE)    x1 < x2 < x3

which is pretty trivial to fill in the non-anti-aliased case. However, when the
bezier decomposition creates segment intersections, you end up with something like:

(x1, BLUE, GREEN)  (x3, RED, BLUE)    (x2, GREEN, RED)

if you use a "naive" rasterizer, suddenly, a horrible red horizontal span appears to the
right of your shape, instead of the expected blue, unless the rasterizer is capable of
detecting these cases and applying some re-ordering logic to get things working properly.

these "rendering bugs" are rare, but still pretty common in some alternative Flash renderers.

they do not appear if you use a "paint" backend like Cairo (where you're going to render each
closed shape independently), but this will be significantly slower than using a rasterizer
optimized for this task. And then you have the problem that 50% BLUE + 50% RED on a 100% WHITE
background will not generate a PINK pixel (B=50% R=50%) but a LIGHT PINK one.

Very frankly, I would seriously *not* recommend trying to use Cairo for fast Flash rendering
unless you want to sacrifice both speed and correctness.

Write a specific rasterizer, and use this instead.

Hope this helps,

- David


On Tue, 31 Jul 2007 16:38:27 +0900, "Bill Baxter" <wbaxter at gmail.com> said:
> > agg
> >         - coverage based antialiasing from freetype
> >         - compute edge flags for all edges into a list of cells
> >         - quick sorts cells into pixel order
> >         - scanline rasterize the cells
> >         - O(p log p) : p is the number of pixels on edges
> 
> AGG also supports a different rasterizer made specifically for
> implementing Flash more accurately.  It's called
> agg_compound_rasterizer or something like that.  The problem as I
> understand it is that in order to properly rasterize and adjacent
> fills with anti-aliasing, you need a rasterizer that is aware of the
> color on the "both sides of the fence".  This is because the
> compositing used for implementing edge anti-aliasing is
> order-dependent.  Usual techniques treat a half covered pixel as a
> fully covered pixel that is half transparent.  If you come back and
> exactly fill the other half with a different color the result should
> be 0.5 c1 + 0.5 c2.   But that's not what you get.  You get a 50% c2
> over 50% c1 over background compositing operation which is not the
> same value.
> 
> --bb
> _______________________________________________
> cairo mailing list
> cairo at cairographics.org
> http://lists.cairographics.org/mailman/listinfo/cairo