[cairo] [PATCH] gl/msaa: Add a fast path for fills that are simple quads
Martin Robinson
mrobinson at igalia.com
Wed Jan 23 14:06:35 PST 2013
On 01/23/2013 12:40 AM, Chris Wilson wrote:
Thanks for the review. I've responded inline and appended the new patch to this email.
>> + points[0] = buf->points[0];
>> + points[1] = buf->points[1];
>> + points[2] = buf->points[2];
>> + points[3] = buf->points[3];
>
> These copies are not required.
You're absolutely correct. I have tried to eliminate all copies in the new version of the patch.
>> +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)
>
> Passing 4x2x4 bytes on the stack, otoh populating a cacheline... However
> your inputs are already in a cacheline...
I tried to counter this by making the function inline. The compiler did not complain about the length.
>> +{
>> + 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);
>
> This and the following computations disregard the precision required.
> Compare and contrast with _cairo_slope_compare(), for a simple example.
> Even there we are effectively limiting the valid precision of our
> inputs, just not as severely as the above.
Thanks for pointing this out. I don't have a great intuition yet for when precision issues will bite, but this makes sense to me. I've switched to using 64-bit integers here instead of cairo_fixed_t.
> I think you may want to do the simple box check first, then simple quad.
> The former being cheaper and more prevalent.
Good idea. This was complicated slightly by the fact that I didn't want to duplicate code and a box is (quad && rectangular) and a simple quad is (quad && maybe rectangular). I've abstracted out another helper to deal with this.
>From 2db77844df4a179db85e898c19c9f332367ebe70 Mon Sep 17 00:00:00 2001
From: Martin Robinson <mrobinson at igalia.com>
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 | 45 +++++++++++--
src/cairo-path-fixed-private.h | 17 +++++
src/cairo-path-fixed.c | 136 ++++++++++++++++++++++++++++++----------
3 files changed, 158 insertions(+), 40 deletions(-)
diff --git a/src/cairo-gl-msaa-compositor.c b/src/cairo-gl-msaa-compositor.c
index 5773733..d41d3f0 100644
--- a/src/cairo-gl-msaa-compositor.c
+++ b/src/cairo-gl-msaa-compositor.c
@@ -45,6 +45,7 @@
#include "cairo-composite-rectangles-private.h"
#include "cairo-compositor-private.h"
#include "cairo-gl-private.h"
+#include "cairo-path-private.h"
#include "cairo-traps-private.h"
static cairo_bool_t
@@ -710,6 +711,29 @@ finish:
}
static cairo_int_status_t
+_draw_simple_quad_path (cairo_gl_context_t *ctx,
+ cairo_gl_composite_t *setup,
+ const cairo_path_fixed_t *path)
+{
+ cairo_point_t triangle[3];
+ cairo_int_status_t status;
+ const cairo_point_t *points;
+
+ points = cairo_path_head (path)->points;
+ 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,
@@ -722,6 +746,7 @@ _cairo_gl_msaa_compositor_fill (const cairo_compositor_t *compositor,
cairo_gl_context_t *ctx = NULL;
cairo_int_status_t status;
cairo_traps_t traps;
+ cairo_bool_t draw_path_with_traps;
if (! can_use_msaa_compositor (dst, antialias))
return CAIRO_INT_STATUS_UNSUPPORTED;
@@ -747,10 +772,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);
+
+ 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 +803,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_path (ctx, &setup, path);
+ else
+ status = _draw_traps (ctx, &setup, &traps);
if (unlikely (status))
goto cleanup_setup;
@@ -785,7 +817,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-private.h b/src/cairo-path-fixed-private.h
index 9b7b403..05904ad 100644
--- a/src/cairo-path-fixed-private.h
+++ b/src/cairo-path-fixed-private.h
@@ -59,6 +59,20 @@ typedef char cairo_path_op_t;
#define CAIRO_PATH_BUF_SIZE ((512 - sizeof (cairo_path_buf_t)) \
/ (2 * sizeof (cairo_point_t) + sizeof (cairo_path_op_t)))
+#define cairo_path_head(path__) (&(path__)->buf.base)
+#define cairo_path_tail(path__) cairo_path_buf_prev (cairo_path_head (path__))
+
+#define cairo_path_buf_next(pos__) \
+ cairo_list_entry ((pos__)->link.next, cairo_path_buf_t, link)
+#define cairo_path_buf_prev(pos__) \
+ cairo_list_entry ((pos__)->link.prev, cairo_path_buf_t, link)
+
+#define cairo_path_foreach_buf_start(pos__, path__) \
+ pos__ = cairo_path_head (path__); do
+#define cairo_path_foreach_buf_end(pos__, path__) \
+ while ((pos__ = cairo_path_buf_next (pos__)) != cairo_path_head (path__))
+
+
typedef struct _cairo_path_buf {
cairo_list_t link;
unsigned int num_ops;
@@ -186,4 +200,7 @@ cairo_private cairo_bool_t
_cairo_path_fixed_is_stroke_box (const cairo_path_fixed_t *path,
cairo_box_t *box);
+cairo_bool_t
+_cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path);
+
#endif /* CAIRO_PATH_FIXED_PRIVATE_H */
diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index c7b1cab..0983af6 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -69,19 +69,6 @@ _cairo_path_buf_add_points (cairo_path_buf_t *buf,
const cairo_point_t *points,
int num_points);
-#define cairo_path_head(path__) (&(path__)->buf.base)
-#define cairo_path_tail(path__) cairo_path_buf_prev (cairo_path_head (path__))
-
-#define cairo_path_buf_next(pos__) \
- cairo_list_entry ((pos__)->link.next, cairo_path_buf_t, link)
-#define cairo_path_buf_prev(pos__) \
- cairo_list_entry ((pos__)->link.prev, cairo_path_buf_t, link)
-
-#define cairo_path_foreach_buf_start(pos__, path__) \
- pos__ = cairo_path_head (path__); do
-#define cairo_path_foreach_buf_end(pos__, path__) \
- while ((pos__ = cairo_path_buf_next (pos__)) != cairo_path_head (path__))
-
void
_cairo_path_fixed_init (cairo_path_fixed_t *path)
{
@@ -1219,18 +1206,11 @@ _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 inline cairo_bool_t
+_path_is_quad (const cairo_path_fixed_t *path)
{
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;
@@ -1265,22 +1245,87 @@ _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
}
}
- /* 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)
- {
+ return TRUE;
+}
+
+static inline cairo_bool_t
+_points_form_rect (const cairo_point_t *points)
+{
+ 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)
+ return TRUE;
+ 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)
+ return TRUE;
+ return FALSE;
+}
+
+/*
+ * 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)
+{
+ const cairo_path_buf_t *buf;
+
+ if (! path->fill_is_rectilinear)
+ return FALSE;
+
+ if (! _path_is_quad (path))
+ return FALSE;
+
+ buf = cairo_path_head (path);
+ if (_points_form_rect (buf->points)) {
_canonical_box (box, &buf->points[0], &buf->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)
- {
- _canonical_box (box, &buf->points[0], &buf->points[2]);
+ return FALSE;
+}
+
+/* Determine whether two lines A->B and C->D intersect based on the
+ * algorithm described here: http://paulbourke.net/geometry/lineline2d/ */
+static inline 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_int64_t numerator_a, numerator_b, denominator;
+
+ denominator = _cairo_int64_sub (_cairo_int32x32_64_mul (d.y - c.y, b.x - a.x),
+ _cairo_int32x32_64_mul (d.x - c.x, b.y - a.y));
+ numerator_a = _cairo_int64_sub (_cairo_int32x32_64_mul (d.x - c.x, a.y - c.y),
+ _cairo_int32x32_64_mul (d.y - c.y, a.x - c.x));
+ numerator_b = _cairo_int64_sub (_cairo_int32x32_64_mul (b.x - a.x, a.y - c.y),
+ _cairo_int32x32_64_mul (b.y - a.y, a.x - c.x));
+
+ if (_cairo_int64_is_zero (denominator)) {
+ /* If the denominator and numerators are both zero,
+ * the lines are coincident. */
+ if (_cairo_int64_is_zero (numerator_a) && _cairo_int64_is_zero (numerator_b))
+ return TRUE;
+
+ /* Otherwise, a zero denominator indicates the lines are
+ * parallel and never intersect. */
+ return FALSE;
+ }
+
+ /* If either 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 (_cairo_int64_lt (numerator_a, denominator) &&
+ _cairo_int64_gt (_cairo_int64_mul (numerator_a, denominator), 0)) {
+ return TRUE;
+ }
+
+ if (_cairo_int64_lt (numerator_b, denominator) &&
+ _cairo_int64_gt (_cairo_int64_mul (numerator_b, denominator), 0)) {
return TRUE;
}
@@ -1288,6 +1333,29 @@ _cairo_path_fixed_is_box (const cairo_path_fixed_t *path,
}
cairo_bool_t
+_cairo_path_fixed_is_simple_quad (const cairo_path_fixed_t *path)
+{
+ const cairo_point_t *points;
+
+ if (! _path_is_quad (path))
+ return FALSE;
+
+ points = cairo_path_head (path)->points;
+ if (_points_form_rect (points))
+ return TRUE;
+
+ 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;
+}
+
+cairo_bool_t
_cairo_path_fixed_is_stroke_box (const cairo_path_fixed_t *path,
cairo_box_t *box)
{
--
1.7.10.4
More information about the cairo
mailing list