[cairo] performance of cairo in a larger application

[Mathieu Lacage]

On Wed, 2004-07-28 at 21:19, Keith Packard wrote:

> The original trapezoid specification called for alpha values to be computed
> from analytic pixel coverage -- compute the area of the pixel covered by
> the trapezoid and round that to an alpha value.  The problem with this
> 'obvious' specification is that the 'rounding' dramatically affects the
> resulting alpha values.
> 
> Because the trapezoids are used to incrementally construct the final
> figure, there isn't any memory of previous coverage information aside from
> the alpha values.  Rounding to the nearest alpha value means that a pixel
> completely covered by a million tiny trapezoids will end up with an alpha
> value of zero.  Every other rounding mode has similar problems.
> 
> Considering this example further yields the observation that of those 
> million trapezoids (assuming 8 bits of alpha), no more than 255 of them
> can affect the alpha value at all.  In the limit, you have an infinite 
> number of trapezoids of zero area, 255 of which have non-zero alpha 
> contribution.  This is equivalent to point sampling.

yes.

> 
> Ok, so to incrementally rasterize a figure and get unity alpha for covered 
> pixels, we have to use some kind of point sampling.
> 
> Our previous implementation attempted to work around this and failed in 
> various minor ways.  Examining it more closely, the errors were caused by 
> using point sampling without knowing where the points were, and in fact, 
> having those positions change depending on the specific trapezoid being 
> drawn.  At least the code was horribly complicated...

Although I never that part of the code, that sounds indeed complicated
:)

> 
> Now that we think we understand the problem a bit better, it seems far 
> more sensible to arrange the point samples in regular known locations.
> 
> Right now, I've chosen a very regular grid -- for 255 alpha values, I'm 
> using the traditional 17x15 rectangle, for 15 it's 5x3.  For this release, 
> I'm planning on shipping the simplest fill algorithm possible.  It's very 

Are you saying you are doing a 17x15 sub-pixel sampling with masks ? If
so, since you mention doing point sampling, I wonder why you do not aim
for higher-quality types of filters with tables of filter values indexed
by the subpixel masks ? There exist a number of papers which detail such
techniques. For example, "A new simple and efficient antialiasing with
subpixel masks" or "Efficient alias-free rendering using bit-masks and
lookup tables". Although I am sure you know about these, I am curious to
know why you do only point sampling when such techniques allow better
filters for roughly equivalent computing costs.

> efficient for small trapezoids as the setup cost is low.  A better 
> algorithm for large trapezoids can easily be added in the future as we 
> gain experience with what shape applications generally emit.
> 
> A completely separate problem is that of breaking complex polygons into 
> trapezoids (or triangles).  That's entirely contained in the cairo library 
> and so isn't trapped by the X release schedule, but there is a hidden 
> dependency...
> 
> The current trapezoid specification uses arbitrary lines for the edges of 
> each trapezoid -- the X and Y values of each end are specific 
> independently from the Y values for the top and bottom of the trapezoid.
> 
> This permits long edges of a complex polygon to be consistently represented
> with the precise line, and not approximated by rounding the top and bottom
> edges to the nearest representable X value on the trapezoid.  It would be 
> a fine idea except that no other graphics system on the planet provides 
> this representation.  

yes. I liked that :)

> 
> As a result, the cairo tesselation engine is being fixed to compute
> 'simple' trapezoids.  This is hard, but John Hobby wrote a nice paper
> detailing the precise steps needed to create a working algorithm and Carl
> is making good progress towards an implemetation within cairo.
> 
> Given that cairo will generate simple trapezoids, it makes sense for the 
> Render extension to support that representation; especially as we expect 
> to provide hardware accelerated support for these trapezoids in the near 
> future (hardware which can't support the fancy trapezoids).

I must say I do not see why it is necessary to generate these simple
trapezoids within cairo. Why not convert the fancy trapezoids to their
simple "equivalent" just before accessing the hardware ? Are you
suggesting that the final output will look better if the conversion is
carried on during the tessellation process (using hobby's suggestion on
segment endpoint precision) than if it is carried on independently as an
afterthought ?

Mathieu
-- 
Mathieu Lacage <mathieu.lacage at sophia.inria.fr>