[cairo] Gradient mesh rasterizer

[Jeff Muizelaar]

On Tue, Jul 14, 2009 at 02:12:34PM +0200, Andrea Canciani wrote:
> I'm working on extending cairo patterns to handle tensor product
> shading patterns (type 7 in pdf reference).
> Right now I can rasterize them, but my code isn't fast and clean as it
> should, anyway Adrian Johnson suggested me to post it here as there
> are performance expert reading this list.
> In the comments I tried to point out known performance problems and
> possible solutions.
> The code should be linked to cairo and libm. Please pay attantion when
> running it because it overwrites the file "mesh.png" in the current
> directory with a rendering of a gradient mesh (hardcoded in the main
> function).

I'm not sure if you planned to do this anyways, but the following patch
brings the runtime on my machine from 0.430s to .358s. The interesting
part is moving the multiplications used to compute ca out of the
innermost loop. You could do something similar for cr,cg,cb.

I expect that the double to integer conversions are expensive and, once
the multiplications are eliminated from the inner loop, will dominate
the time spent in that loop. Therefore, it might be worth while to
investigate using an integer fixed point representation for the inner
loop computations.

It may also be worth keeping a reference implementation that is easier
to understand than the optimized version but not as performant. Such an
implementation could be useful for doing algorithmic optimizations.

-Jeff

diff --git a/pattern.c b/pattern.c
index ddf0089..46657fc 100644
--- a/pattern.c
+++ b/pattern.c
@@ -51,7 +51,7 @@ up (bezier_t f[4])
   f[3] *= 8;
 }
 
-static void
+static inline void
 down (bezier_t f[4])
 {
   f[3] /= 8;
@@ -59,7 +59,7 @@ down (bezier_t f[4])
   f[1] = (f[1] - f[2]) / 2;
 }
 
-static void
+static inline void
 fwd (bezier_t f[4])
 {
   f[0] += f[1];
@@ -141,17 +141,22 @@ _paint_gradient_mesh (unsigned char *data, int width, int height, int stride,
     }
 
     tmp = 1.0 / (1L << (ushift + vshift));
+    double ca = ((vsteps - v) * usteps * a[0] + v * usteps * a[2])*tmp*255 + .5;
+    double va3_1 = (v*a[3] + (vsteps-v)*a[1])*tmp*255;
+    double va2_0 = (v*a[2] + (vsteps-v)*a[0])*tmp*255;
     for (u = 0; u < usteps; ++u) {
       x = (int) xu[0];
       y = (int) yu[0];
+
       if (0 <= x && 0 <= y && x < width && y < height) {
-	double ca = ( (vsteps - v) * ( (usteps - u) * a[0] + u * a[1]) + v * ( (usteps - u) * a[2] + u * a[3])) * tmp * 255.0 + .5;
 	int cr = ( (vsteps - v) * ( (usteps - u) * r[0] + u * r[1]) + v * ( (usteps - u) * r[2] + u * r[3])) * tmp * ca;
 	int cg = ( (vsteps - v) * ( (usteps - u) * g[0] + u * g[1]) + v * ( (usteps - u) * g[2] + u * g[3])) * tmp * ca;
 	int cb = ( (vsteps - v) * ( (usteps - u) * b[0] + u * b[1]) + v * ( (usteps - u) * b[2] + u * b[3])) * tmp * ca;
 	int ica = ca;
 	* ( (uint32_t*) (data + y*stride + 4*x)) = (ica << 24) | (cr << 16) | (cg << 8) | cb;
       }
+      ca += va3_1;
+      ca -= va2_0;
       fwd (xu);
       fwd (yu);
     }