[cairo] performance of cairo in a larger application

[Keith Packard]

Around 8 o'clock on Jul 28, Mathieu Lacage wrote:

> Where does this new code live ? Although I cannot promiss to contribute
> code, I would be definitely be interested in reading it and maybe
> commenting on it.

I'm finishing up the new trapezoids; I've stuck them in my CVS server at 
the moment just to avoid losing bits.  I'm hoping to have them integrated 
into the xserver.freedesktop.org project CVS today.

Let me describe the problem and let people poke holes in it if they like.

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.

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...

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 
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.  

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).

So, in addition to the new trapezoid implementation, we also have a new 
Render request which uses a simpler trapezoid representation.  There isn't 
any difference other than representation, the fill rules remain the same.

-keith


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20040728/d8962d0c/attachment.pgp