[cairo] performance of cairo in a larger application
Keith Packard
keithp at keithp.com
Wed Jul 28 12:19:17 PDT 2004
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
More information about the cairo
mailing list