[cairo] OVER / SOURCE optimization for cairo_paint

[Owen Taylor]

On Tue, 2008-02-19 at 15:11 -0500, Antoine Azar wrote:
> >I was hoping someone else would pick up this topic, but since nobody
> >else has: is this really a legitimate optimization when the
> >source is scaled or transformed?
> >
> >  - It will produce clearly incorrect results unless you replace
> >    EXTEND_NONE with the (not yet implemented?) EXTEND_PAD, since
> >    SOURCE for EXTEND_NONE is going to give 0,0,0,0 pixels outside
> >    the edge.
> 
> Hi Owen,
> You're right about this, and I already fixed this in the latest patch 
> I sent to the list. I'd really appreciate it if you had a look at it 
> and gave me some feedback.

I think there are still issues with the newer version. It's really
hard for me to figure out _cairo_gstate_get_source_extents()

 A) It's full of FIXME's and commented out code
 B) There is no documentation of what it is *supposed* to do. 
    (That's the first thing I'd write for a function like that.)

But assuming that the function is supposed to do something like:

 "Return the bounding rectangle of all areas of device space where
  the drawn result might possibly be affected by the content of 
  the source surface"

I don't think it's even possible to write this function at the
cairo-gstate.c level, since you don't know the pixel grid (or if there
*is* a pixel grid), and even if you knew the pixel grid, you don't know
the details of how the backend is sampling source pixels when a 
transform or scale is involved. You make various attempts to handle
this stuff ... looking at the filter, calling ceil()/floor(), etc, but
it's perfectly legitimate for a backend, say, to use bilinear filtering
when NEAREST is passed in. Filters are best effort.

The place where all the information is available is in pixman. Also,
by drilling the optimizations down to where you are actually banging
pixels around, you'll do a better job at handling different code
paths that end up at the same place. I don't think you currently handle
the case where somebody does 

  cairo_rectangle(); cairo_clip(); cairo_paint();

Even when it results in exactly the same pixels being touched as:

  cairo_rectangle(); cairo_fill();

Another suggestion I'd make is split your work into two pieces:

 - Optimization of SOURCE => OVER when the source pixels are completely
   opaque and completely coming from within the source.

 - Optimization of fill bounds when the operator is bounded
   (see _cairo_operator_is_bounded_by_source())

BTW, take a look at _cairo_surface_fallback_paint() and the usage of
_cairo_pattern_get_extents(). We're using it to do a different thing
computing the extents of the area affected by the drawing operation
so we know what pixels to fix, but it's basically the same thing
as you are trying to do. And has the same problem with filters...

> >In my opinion, optimizations should not change appearance in such a 
> >way ... even if the appearance is better .... because it means
> >that you get discontinuities between the optimized path and when you 
> >can't optimize for one reason or the other.
>
> Agreed. My latest patch shouldn't show any differences, as far as I 
> was able to test it.
> 
> >The other thing I wonder about the patch in general: what's it going 
> >to do for a backend where OVER is normal and SOURCE abnormal? Does the
> >backend have to reverse the optimization? (In other words, the 
> >question is: should this optimization be in the image backend at a 
> >low level or even inside libpixman, rather than in cairo-gstate.c?)
> 
> That's an interesting question, I actually didn't think any backend 
> could perform faster while doing compositing rather than just 
> overwriting the dest with the source pixels. Is it really the case?

There are other people around who know the PS/PDF/SVG backends a lot
better than me, and they'd be in a better position to answer that
question. But in such cases, it's not how fast the code can be 
implemented that matters, as much as "how naturally can this be
mapped to primitives in the underlying system". And OVER is the
"normal" operation for most systems.

- Owen

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://lists.cairographics.org/archives/cairo/attachments/20080219/4d336678/attachment.pgp