Bug 694585: Slow rendering of meshes

In the existing code for meshes, we decompose the mesh down into
quads (or triangles) and then call a process routine to actually
do the work. This process routine typically maps each vertexes
position/color and plots it.

As each vertex is used several times by neighbouring patches, this
results in each vertex being processed several times. The fix in
this commit is therefore to break the processing into 'prepare' and
'process' phases. Each vertex is 'prepared' before being used in
the 'process' phase. This cuts the number of prepare operations in
half.

In testing, this reduced the time for a (release build, generating ppm
at default resolution) run from 33.4s to 23.5s.

3 files changed, 63 insertions, 38 deletions

diff --git a/include/mupdf/fitz/shade.h b/include/mupdf/fitz/shade.h
index 6ea198dd..b33b832e 100644
--- a/include/mupdf/fitz/shade.h
+++ b/include/mupdf/fitz/shade.h
@@ -92,18 +92,20 @@ struct fz_vertex_s
 
 typedef struct fz_mesh_processor_s fz_mesh_processor;
 
+typedef void (fz_mesh_prepare_fn)(void *arg, fz_vertex *v);
 typedef void (fz_mesh_process_fn)(void *arg, fz_vertex *av, fz_vertex *bv, fz_vertex *cv);
 
 struct fz_mesh_processor_s {
 	fz_context *ctx;
 	fz_shade *shade;
+	fz_mesh_prepare_fn *prepare;
 	fz_mesh_process_fn *process;
 	void *process_arg;
 	int ncomp;
 };
 
 void fz_process_mesh(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm,
-			fz_mesh_process_fn *process, void *process_arg);
+			fz_mesh_prepare_fn *prepare, fz_mesh_process_fn *process, void *process_arg);
 
 #ifndef NDEBUG
 void fz_print_shade(fz_context *ctx, FILE *out, fz_shade *shade);
diff --git a/source/fitz/draw-mesh.c b/source/fitz/draw-mesh.c
index c0ad45d2..26d496d2 100644
--- a/source/fitz/draw-mesh.c
+++ b/source/fitz/draw-mesh.c
@@ -93,7 +93,7 @@ static inline void step_edge(edge_data *edge, int n)
 }
 
 static void
-fz_paint_triangle(fz_pixmap *pix, float v[3][MAXN], int n, const fz_irect *bbox)
+fz_paint_triangle(fz_pixmap *pix, float *v[3], int n, const fz_irect *bbox)
 {
 	edge_data e0, e1;
 	int top, mid, bot;
@@ -161,44 +161,41 @@ struct paint_tri_data
 	fz_shade *shade;
 	fz_pixmap *dest;
 	const fz_irect *bbox;
+	fz_color_converter cc;
 };
 
 static void
+prepare_vertex(void *arg, fz_vertex *v)
+{
+	struct paint_tri_data *ptd = (struct paint_tri_data *)arg;
+	float local[MAXN];
+	fz_shade *shade = ptd->shade;
+	fz_pixmap *dest = ptd->dest;
+	int i;
+
+	if (shade->use_function)
+		v->c[0] *= 255;
+	else
+	{
+		ptd->cc.convert(&ptd->cc, &local[0], v->c);
+		for (i = 0; i < dest->colorspace->n; i++)
+			v->c[i] = local[i] * 255;
+	}
+}
+
+static void
 do_paint_tri(void *arg, fz_vertex *av, fz_vertex *bv, fz_vertex *cv)
 {
 	struct paint_tri_data *ptd = (struct paint_tri_data *)arg;
-	int i, k;
-	fz_vertex *vertices[3];
-	fz_vertex *v;
-	float *ltri;
-	fz_context *ctx;
-	fz_shade *shade;
+	float *vertices[3];
 	fz_pixmap *dest;
-	float local[3][MAXN];
 
-	vertices[0] = av;
-	vertices[1] = bv;
-	vertices[2] = cv;
+	vertices[0] = (float *)av;
+	vertices[1] = (float *)bv;
+	vertices[2] = (float *)cv;
 
 	dest = ptd->dest;
-	ctx = ptd->ctx;
-	shade = ptd->shade;
-	for (k = 0; k < 3; k++)
-	{
-		v = vertices[k];
-		ltri = &local[k][0];
-		ltri[0] = v->p.x;
-		ltri[1] = v->p.y;
-		if (shade->use_function)
-			ltri[2] = v->c[0] * 255;
-		else
-		{
-			fz_convert_color(ctx, dest->colorspace, &ltri[2], shade->colorspace, v->c);
-			for (i = 0; i < dest->colorspace->n; i++)
-				ltri[i + 2] *= 255;
-		}
-	}
-	fz_paint_triangle(dest, local, 2 + dest->colorspace->n, ptd->bbox);
+	fz_paint_triangle(dest, vertices, 2 + dest->colorspace->n, ptd->bbox);
 }
 
 void
@@ -244,7 +241,8 @@ fz_paint_shade(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz_pixmap
 		ptd.shade = shade;
 		ptd.bbox = bbox;
 
-		fz_process_mesh(ctx, shade, &local_ctm, &do_paint_tri, &ptd);
+		fz_lookup_color_converter(&ptd.cc, ctx, temp->colorspace, shade->colorspace);
+		fz_process_mesh(ctx, shade, &local_ctm, &prepare_vertex, &do_paint_tri, &ptd);
 
 		if (shade->use_function)
 		{
diff --git a/source/fitz/shade.c b/source/fitz/shade.c
index b13dc215..892f1887 100644
--- a/source/fitz/shade.c
+++ b/source/fitz/shade.c
@@ -2,13 +2,13 @@
 
 #define SWAP(a,b) {fz_vertex *t = (a); (a) = (b); (b) = t;}
 
-static void
+static inline void
 paint_tri(fz_mesh_processor *painter, fz_vertex *v0, fz_vertex *v1, fz_vertex *v2)
 {
 	painter->process(painter->process_arg, v0, v1, v2);
 }
 
-static void
+static inline void
 paint_quad(fz_mesh_processor *painter, fz_vertex *v0, fz_vertex *v1, fz_vertex *v2, fz_vertex *v3)
 {
 	/* For a quad with corners (in clockwise or anticlockwise order) are
@@ -64,9 +64,11 @@ fz_process_mesh_type1(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 		fz_transform_point(&v[0].p, &local_ctm);
 		memcpy(v[0].c, p, n*sizeof(float));
 		p += n;
+		painter->prepare(painter->process_arg, &v[0]);
 		v[1].p.x = x; v[1].p.y = yn;
 		fz_transform_point(&v[1].p, &local_ctm);
 		memcpy(v[1].c, p + xdivs*n, n*sizeof(float));
+		painter->prepare(painter->process_arg, &v[1]);
 		for (xx = 0; xx < xdivs; xx++)
 		{
 			x = x0 + (x1 - x0) * (xx + 1) / xdivs;
@@ -75,9 +77,11 @@ fz_process_mesh_type1(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 			fz_transform_point(&vn[0].p, &local_ctm);
 			memcpy(vn[0].c, p, n*sizeof(float));
 			p += n;
+			painter->prepare(painter->process_arg, &vn[0]);
 			vn[1].p.x = x; vn[1].p.y = yn;
 			fz_transform_point(&vn[1].p, &local_ctm);
 			memcpy(vn[1].c, p + xdivs*n, n*sizeof(float));
+			painter->prepare(painter->process_arg, &vn[1]);
 
 			paint_quad(painter, &v[0], &vn[0], &vn[1], &v[1]);
 			SWAP(v,vn);
@@ -127,6 +131,10 @@ fz_process_mesh_type2(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 	v2.c[0] = 0;
 	v3.c[0] = 1;
 
+	painter->prepare(painter->process_arg, &v0);
+	painter->prepare(painter->process_arg, &v1);
+	painter->prepare(painter->process_arg, &v2);
+	painter->prepare(painter->process_arg, &v3);
 	paint_quad(painter, &v0, &v2, &v3, &v1);
 
 	if (shade->u.l_or_r.extend[0])
@@ -139,9 +147,9 @@ fz_process_mesh_type2(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 
 		e0.c[0] = 0;
 		e1.c[0] = 0;
-		v0.c[0] = 0;
-		v2.c[0] = 0;
 
+		painter->prepare(painter->process_arg, &e0);
+		painter->prepare(painter->process_arg, &e1);
 		paint_quad(painter, &e0, &v0, &v2, &e1);
 	}
 
@@ -155,9 +163,9 @@ fz_process_mesh_type2(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 
 		e0.c[0] = 1;
 		e1.c[0] = 1;
-		v1.c[0] = 1;
-		v3.c[0] = 1;
 
+		painter->prepare(painter->process_arg, &e0);
+		painter->prepare(painter->process_arg, &e1);
 		paint_quad(painter, &e0, &v1, &v3, &e1);
 	}
 }
@@ -207,6 +215,14 @@ fz_paint_annulus(const fz_matrix *ctm,
 		b2.c[0] = c1;
 		b3.c[0] = c1;
 
+		painter->prepare(painter->process_arg, &t0);
+		painter->prepare(painter->process_arg, &t1);
+		painter->prepare(painter->process_arg, &t2);
+		painter->prepare(painter->process_arg, &t3);
+		painter->prepare(painter->process_arg, &b0);
+		painter->prepare(painter->process_arg, &b1);
+		painter->prepare(painter->process_arg, &b2);
+		painter->prepare(painter->process_arg, &b3);
 		paint_quad(painter, &t0, &t2, &t3, &t1);
 		paint_quad(painter, &b0, &b2, &b3, &b1);
 	}
@@ -296,6 +312,7 @@ fz_process_mesh_type4(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 			fz_transform_point(&vd->p, ctm);
 			for (i = 0; i < ncomp; i++)
 				vd->c[i] = read_sample(stream, bpcomp, c0[i], c1[i]);
+			painter->prepare(painter->process_arg, vd);
 
 			switch (flag)
 			{
@@ -308,6 +325,7 @@ fz_process_mesh_type4(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 				fz_transform_point(&vb->p, ctm);
 				for (i = 0; i < ncomp; i++)
 					vb->c[i] = read_sample(stream, bpcomp, c0[i], c1[i]);
+				painter->prepare(painter->process_arg, vb);
 
 				fz_read_bits(stream, bpflag);
 				vc->p.x = read_sample(stream, bpcoord, x0, x1);
@@ -315,6 +333,7 @@ fz_process_mesh_type4(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 				fz_transform_point(&vc->p, ctm);
 				for (i = 0; i < ncomp; i++)
 					vc->c[i] = read_sample(stream, bpcomp, c0[i], c1[i]);
+				painter->prepare(painter->process_arg, vc);
 
 				paint_tri(painter, va, vb, vc);
 				break;
@@ -381,6 +400,7 @@ fz_process_mesh_type5(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 				fz_transform_point(&buf[i].p, ctm);
 				for (k = 0; k < ncomp; k++)
 					buf[i].c[k] = read_sample(stream, bpcomp, c0[k], c1[k]);
+				painter->prepare(painter->process_arg, &buf[i]);
 			}
 
 			if (!first)
@@ -431,6 +451,10 @@ triangulate_patch(fz_mesh_processor *painter, tensor_patch p)
 	v3.p = p.pole[3][0];
 	memcpy(v3.c, p.color[3], col_len);
 
+	painter->prepare(painter->process_arg, &v0);
+	painter->prepare(painter->process_arg, &v1);
+	painter->prepare(painter->process_arg, &v2);
+	painter->prepare(painter->process_arg, &v3);
 	paint_quad(painter, &v0, &v1, &v2, &v3);
 }
 
@@ -889,12 +913,13 @@ fz_process_mesh_type7(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm, fz
 
 void
 fz_process_mesh(fz_context *ctx, fz_shade *shade, const fz_matrix *ctm,
-		fz_mesh_process_fn *process, void *process_arg)
+		fz_mesh_prepare_fn *prepare, fz_mesh_process_fn *process, void *process_arg)
 {
 	fz_mesh_processor painter;
 
 	painter.ctx = ctx;
 	painter.shade = shade;
+	painter.prepare = prepare;
 	painter.process = process;
 	painter.process_arg = process_arg;
 	painter.ncomp = (shade->use_function > 0 ? 1 : shade->colorspace->n);