[PATCH] gl/msaa: Add a fast path for fills that are simple quads

Sending this one to the list because it touches some code used
outside the MSAA compositor.

From e3ec524717225437be3caf1ffa48bd620c30b65a Mon Sep 17 00:00:00 2001
From: Martin Robinson <[email protected]>
Date: Tue, 22 Jan 2013 20:09:01 -0800
Subject: [PATCH] gl/msaa: Add a fast path for fills that are simple quads

Instead of invoking Bentley-Ottman for fills that are simple
quadrilaterals, just pass the geometry straight to OpenGL.
---
 src/cairo-gl-msaa-compositor.c |   44 +++++++++++++--
 src/cairo-path-fixed.c         |  120 +++++++++++++++++++++++++++++++++-------
 src/cairoint.h                 |    4 ++
 3 files changed, 141 insertions(+), 27 deletions(-)

diff --git a/src/cairo-gl-msaa-compositor.c b/src/cairo-gl-msaa-compositor.c
index 5773733..38cdca9 100644
--- a/src/cairo-gl-msaa-compositor.c
+++ b/src/cairo-gl-msaa-compositor.c
@@ -710,6 +710,27 @@ finish:
 }
 
 static cairo_int_status_t
+_draw_simple_quad (cairo_gl_context_t *ctx,
+		   cairo_gl_composite_t *setup,
+		   cairo_point_t points[4])
+{
+    cairo_point_t triangle[3];
+    cairo_int_status_t status;
+
+    triangle[0] = points[0];
+    triangle[1] = points[1];
+    triangle[2] = points[2];
+    status = _cairo_gl_composite_emit_triangle_as_tristrip (ctx, setup, triangle);
+    if (status)
+	return status;
+
+    triangle[0] = points[2];
+    triangle[1] = points[3];
+    triangle[2] = points[0];
+    return _cairo_gl_composite_emit_triangle_as_tristrip (ctx, setup, triangle);
+}
+
+static cairo_int_status_t
 _cairo_gl_msaa_compositor_fill (const cairo_compositor_t	*compositor,
 				cairo_composite_rectangles_t	*composite,
 				const cairo_path_fixed_t	*path,
@@ -723,6 +744,9 @@ _cairo_gl_msaa_compositor_fill (const cairo_compositor_t	*compositor,
     cairo_int_status_t status;
     cairo_traps_t traps;
 
+    cairo_bool_t draw_path_with_traps;
+    cairo_point_t points[4];
+
     if (! can_use_msaa_compositor (dst, antialias))
 	return CAIRO_INT_STATUS_UNSUPPORTED;
 
@@ -747,10 +771,14 @@ _cairo_gl_msaa_compositor_fill (const cairo_compositor_t	*compositor,
 	return _paint_back_unbounded_surface (compositor, composite, surface);
     }
 
-    _cairo_traps_init (&traps);
-    status = _cairo_path_fixed_fill_to_traps (path, fill_rule, tolerance, &traps);
-    if (unlikely (status))
-	goto cleanup_traps;
+    draw_path_with_traps = ! _cairo_path_fixed_is_simple_quad (path, points);
+
+    if (draw_path_with_traps) {
+	_cairo_traps_init (&traps);
+	status = _cairo_path_fixed_fill_to_traps (path, fill_rule, tolerance, &traps);
+	if (unlikely (status))
+	    goto cleanup_traps;
+    }
 
     status = _cairo_gl_composite_init (&setup,
 				       composite->op,
@@ -774,7 +802,10 @@ _cairo_gl_msaa_compositor_fill (const cairo_compositor_t	*compositor,
     if (unlikely (status))
 	goto cleanup_setup;
 
-    status = _draw_traps (ctx, &setup, &traps);
+    if (! draw_path_with_traps)
+	status = _draw_simple_quad (ctx, &setup, points);
+    else
+	status = _draw_traps (ctx, &setup, &traps);
     if (unlikely (status))
         goto cleanup_setup;
 
@@ -785,7 +816,8 @@ cleanup_setup:
 	status = _cairo_gl_context_release (ctx, status);
 
 cleanup_traps:
-    _cairo_traps_fini (&traps);
+    if (draw_path_with_traps)
+	_cairo_traps_fini (&traps);
 
     return status;
 }
diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index c7b1cab..54a9ca5 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -1219,18 +1219,12 @@ _canonical_box (cairo_box_t *box,
     }
 }
 
-/*
- * Check whether the given path contains a single rectangle.
- */
-cairo_bool_t
-_cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
-			  cairo_box_t *box)
+static cairo_bool_t
+_cairo_path_fixed_is_quad (const cairo_path_fixed_t *path,
+			   cairo_point_t points[4])
 {
     const cairo_path_buf_t *buf = cairo_path_head (path);
 
-    if (! path->fill_is_rectilinear)
-	return FALSE;
-
     /* Do we have the right number of ops? */
     if (buf->num_ops < 4 || buf->num_ops > 6)
 	return FALSE;
@@ -1239,8 +1233,7 @@ _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
     if (buf->op[0] != CAIRO_PATH_OP_MOVE_TO ||
 	buf->op[1] != CAIRO_PATH_OP_LINE_TO ||
 	buf->op[2] != CAIRO_PATH_OP_LINE_TO ||
-	buf->op[3] != CAIRO_PATH_OP_LINE_TO)
-    {
+	buf->op[3] != CAIRO_PATH_OP_LINE_TO) {
 	return FALSE;
     }
 
@@ -1265,22 +1258,107 @@ _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
 	}
     }
 
+    points[0] = buf->points[0];
+    points[1] = buf->points[1];
+    points[2] = buf->points[2];
+    points[3] = buf->points[3];
+    return TRUE;
+}
+
+
+/* Determine whether two lines A->B and C->D intersect based on the 
+ * algorithm described here: http://paulbourke.net/geometry/lineline2d/ */
+static cairo_bool_t
+_lines_intersect_or_are_coincident (cairo_point_t a,
+				    cairo_point_t b,
+				    cairo_point_t c,
+				    cairo_point_t d)
+{
+    cairo_fixed_t numerator_a, numerator_b, denominator;
+
+    denominator = _cairo_fixed_mul (d.y - c.y, b.x - a.x) -
+		  _cairo_fixed_mul (d.x - c.x, b.y - a.y);
+    numerator_a = _cairo_fixed_mul (d.x - c.x, a.y - c.y) -
+		  _cairo_fixed_mul (d.y - c.y, a.x - c.x);
+    numerator_b = _cairo_fixed_mul (b.x - a.x, a.y - c.y) -
+		  _cairo_fixed_mul (b.y - a.y, a.x - c.x);
+
+    if (denominator == 0) {
+	/* If the denominator and numerators are both zero,
+	 * the lines are coincident. */
+	if (numerator_a == 0 && numerator_b == 0)
+	    return TRUE;
+
+	/* Otherwise, a zero denominator indicates the lines are
+	*  parallel and never intersect. */
+	return FALSE;
+    }
+
+    /* If either a division would produce a number between 0 and 1, i.e.
+     * the numerator is smaller than the denominator and their signs are
+     * the same, then the lines intersect. */
+    if (numerator_a < denominator &&
+	_cairo_fixed_mul (numerator_a, denominator) > 0) {
+	return TRUE;
+    }
+
+    if (numerator_b < denominator &&
+	_cairo_fixed_mul (numerator_b, denominator) > 0) {
+	return TRUE;
+    }
+
+    return FALSE;
+}
+
+cairo_bool_t
+_cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path,
+				  cairo_point_t points[4])
+{
+    if (! _cairo_path_fixed_is_quad (path, points))
+	return FALSE;
+
+    if (_lines_intersect_or_are_coincident (points[0], points[1],
+					    points[3], points[2]))
+	return FALSE;
+
+    if (_lines_intersect_or_are_coincident (points[0], points[3],
+					    points[1], points[2]))
+	return FALSE;
+
+    return TRUE;
+}
+
+/*
+ * Check whether the given path contains a single rectangle.
+ */
+cairo_bool_t
+_cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
+			  cairo_box_t *box)
+{
+    cairo_point_t points[4];
+
+    if (! path->fill_is_rectilinear)
+	return FALSE;
+
+    if (! _cairo_path_fixed_is_quad (path, points))
+	return FALSE;
+
     /* Ok, we may have a box, if the points line up */
-    if (buf->points[0].y == buf->points[1].y &&
-	buf->points[1].x == buf->points[2].x &&
-	buf->points[2].y == buf->points[3].y &&
-	buf->points[3].x == buf->points[0].x)
+    if (points[0].y == points[1].y &&
+	points[1].x == points[2].x &&
+	points[2].y == points[3].y &&
+	points[3].x == points[0].x)
     {
-	_canonical_box (box, &buf->points[0], &buf->points[2]);
+	_canonical_box (box, &points[0], &points[2]);
 	return TRUE;
     }
 
-    if (buf->points[0].x == buf->points[1].x &&
-	buf->points[1].y == buf->points[2].y &&
-	buf->points[2].x == buf->points[3].x &&
-	buf->points[3].y == buf->points[0].y)
+    if (points[0].x == points[1].x &&
+	points[1].y == points[2].y &&
+	points[2].x == points[3].x &&
+	points[3].y == points[0].y)
     {
-	_canonical_box (box, &buf->points[0], &buf->points[2]);
+	_canonical_box (box, &points[0], &points[2]);
 	return TRUE;
     }
 
diff --git a/src/cairoint.h b/src/cairoint.h
index 861e2f7..4daba78 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1002,6 +1002,10 @@ cairo_private void
 _cairo_path_fixed_transform (cairo_path_fixed_t	*path,
 			     const cairo_matrix_t	*matrix);
 
+cairo_bool_t
+_cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path,
+				  cairo_point_t points[4]);
+
 cairo_private cairo_bool_t
 _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
                           cairo_box_t *box);
-- 
1.7.10.4

-- 
cairo mailing list
[email protected]
http://lists.cairographics.org/mailman/listinfo/cairo