[cairo-commit] 5 commits - src/cairo-gstate.c src/cairoint.h src/cairo-path-stroke.c src/cairo-stroke-style.c test/dash-infinite-loop.c test/dash-offset.c test/dash-offset.ref.png test/Makefile.am test/Makefile.sources
Andrea Canciani
ranma42 at kemper.freedesktop.org
Wed Nov 11 09:25:25 PST 2009
src/cairo-gstate.c | 14 ++---
src/cairo-path-stroke.c | 24 ++++++---
src/cairo-stroke-style.c | 119 ++++++++++++++++++++++++++++++++++++++++++++++
src/cairoint.h | 20 +++++++
test/Makefile.am | 1
test/Makefile.sources | 1
test/dash-infinite-loop.c | 2
test/dash-offset.c | 95 ++++++++++++++++++++++++++++++++++++
test/dash-offset.ref.png |binary
9 files changed, 261 insertions(+), 15 deletions(-)
New commits:
commit 26e9f149063b9e1fdb54fc54fccbefdf04a68190
Author: Andrea Canciani <ranma42 at gmail.com>
Date: Tue Nov 10 23:09:56 2009 +0100
Improve stroking of densely dashed styles
Add some auxiliary functions to cairo-stroke-style to compute
properties of the dashed patterns (period, "on" coverage) and to
generate approximations when the dash pattern is sub-tolerance.
These functions are used in cairo-path-stroke to simplify dash
patterns stroked by cairo.
Fixes dash-infinite-loop
See http://bugs.freedesktop.org/show_bug.cgi?id=24702
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 5c4f4fc..272045a 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -51,6 +51,7 @@ typedef struct _cairo_stroker_dash {
double dash_offset;
const double *dashes;
+ double approximate_dashes[2];
unsigned int num_dashes;
} cairo_stroker_dash_t;
@@ -137,15 +138,25 @@ _cairo_stroker_dash_step (cairo_stroker_dash_t *dash, double step)
static void
_cairo_stroker_dash_init (cairo_stroker_dash_t *dash,
- const cairo_stroke_style_t *style)
+ const cairo_stroke_style_t *style,
+ const cairo_matrix_t *ctm,
+ double tolerance)
{
dash->dashed = style->dash != NULL;
if (! dash->dashed)
return;
- dash->dashes = style->dash;
- dash->num_dashes = style->num_dashes;
- dash->dash_offset = style->dash_offset;
+ if (_cairo_stroke_style_dash_can_approximate (style, ctm, tolerance)) {
+ _cairo_stroke_style_dash_approximate (style, ctm, tolerance,
+ &dash->dash_offset,
+ dash->approximate_dashes,
+ &dash->num_dashes);
+ dash->dashes = dash->approximate_dashes;
+ } else {
+ dash->dashes = style->dash;
+ dash->num_dashes = style->num_dashes;
+ dash->dash_offset = style->dash_offset;
+ }
_cairo_stroker_dash_start (dash);
}
@@ -179,7 +190,7 @@ _cairo_stroker_init (cairo_stroker_t *stroker,
stroker->has_first_face = FALSE;
stroker->has_initial_sub_path = FALSE;
- _cairo_stroker_dash_init (&stroker->dash, stroke_style);
+ _cairo_stroker_dash_init (&stroker->dash, stroke_style, ctm, tolerance);
stroker->add_external_edge = NULL;
@@ -1490,7 +1501,8 @@ _cairo_rectilinear_stroker_init (cairo_rectilinear_stroker_t *stroker,
stroker->segments_size = ARRAY_LENGTH (stroker->segments_embedded);
stroker->num_segments = 0;
- _cairo_stroker_dash_init (&stroker->dash, stroke_style);
+ /* Assume 2*EPSILON tolerance */
+ _cairo_stroker_dash_init (&stroker->dash, stroke_style, ctm, _cairo_fixed_to_double (2 * CAIRO_FIXED_EPSILON));
stroker->has_bounds = FALSE;
}
diff --git a/src/cairo-stroke-style.c b/src/cairo-stroke-style.c
index 3851883..2d1cfe4 100644
--- a/src/cairo-stroke-style.c
+++ b/src/cairo-stroke-style.c
@@ -120,3 +120,122 @@ _cairo_stroke_style_max_distance_from_path (const cairo_stroke_style_t *style,
*dx = style_expansion * hypot (ctm->xx, ctm->xy);
*dy = style_expansion * hypot (ctm->yy, ctm->yx);
}
+
+/*
+ * Computes the period of a dashed stroke style.
+ * Returns 0 for non-dashed styles.
+ */
+double
+_cairo_stroke_style_dash_period (const cairo_stroke_style_t *style)
+{
+ double period;
+ unsigned int i;
+
+ period = 0.0;
+ for (i = 0; i < style->num_dashes; i++)
+ period += style->dash[i];
+
+ if (style->num_dashes & 1)
+ period *= 2.0;
+
+ return period;
+}
+
+/*
+ * Coefficient of the linear approximation (minimizing square difference)
+ * of the surface covered by round caps
+ */
+#define ROUND_MINSQ_APPROXIMATION (9*M_PI/32)
+
+/*
+ * Computes the length of the "on" part of a dashed stroke style,
+ * taking into account also line caps.
+ * Returns 0 for non-dashed styles.
+ */
+double
+_cairo_stroke_style_dash_stroked (const cairo_stroke_style_t *style)
+{
+ double stroked, cap_scale;
+ unsigned int i;
+
+ switch (style->line_cap) {
+ default: ASSERT_NOT_REACHED;
+ case CAIRO_LINE_CAP_BUTT: cap_scale = 0.0; break;
+ case CAIRO_LINE_CAP_ROUND: cap_scale = ROUND_MINSQ_APPROXIMATION; break;
+ case CAIRO_LINE_CAP_SQUARE: cap_scale = 1.0; break;
+ }
+
+ stroked = 0.0;
+ if (style->num_dashes & 1) {
+ /* Each dash element is used both as on and as off. The order in which they are summed is
+ * irrelevant, so sum the coverage of one dash element, taken both on and off at each iteration */
+ for (i = 0; i < style->num_dashes; i++)
+ stroked += style->dash[i] + cap_scale * MIN (style->dash[i], style->line_width);
+ } else {
+ /* Even (0, 2, ...) dashes are on and simply counted for the coverage, odd dashes are off, thus
+ * their coverage is approximated based on the area covered by the caps of adjacent on dases. */
+ for (i = 0; i < style->num_dashes; i+=2)
+ stroked += style->dash[i] + cap_scale * MIN (style->dash[i+1], style->line_width);
+ }
+
+ return stroked;
+}
+
+/*
+ * Verifies if _cairo_stroke_style_dash_approximate should be used to generate
+ * an approximation of the dash pattern in the specified style, when used for
+ * stroking a path with the given CTM and tolerance.
+ * Always FALSE for non-dashed styles.
+ */
+cairo_bool_t
+_cairo_stroke_style_dash_can_approximate (const cairo_stroke_style_t *style,
+ const cairo_matrix_t *ctm,
+ double tolerance)
+{
+ double period;
+
+ if (! style->num_dashes)
+ return FALSE;
+
+ period = _cairo_stroke_style_dash_period (style);
+ return _cairo_matrix_transformed_circle_major_axis (ctm, period) < tolerance;
+}
+
+/*
+ * Create a 2-dashes approximation of a dashed style, by making the "on" and "off"
+ * parts respect the original ratio.
+ */
+void
+_cairo_stroke_style_dash_approximate (const cairo_stroke_style_t *style,
+ const cairo_matrix_t *ctm,
+ double tolerance,
+ double *dash_offset,
+ double *dashes,
+ unsigned int *num_dashes)
+{
+ double coverage, scale, offset;
+ cairo_bool_t on = TRUE;
+ unsigned int i = 0;
+
+ coverage = _cairo_stroke_style_dash_stroked (style) / _cairo_stroke_style_dash_period (style);
+ coverage = MIN (coverage, 1.0);
+ scale = tolerance / _cairo_matrix_transformed_circle_major_axis (ctm, 1.0);
+
+ /* We stop searching for a starting point as soon as the
+ offset reaches zero. Otherwise when an initial dash
+ segment shrinks to zero it will be skipped over. */
+ offset = style->dash_offset;
+ while (offset > 0.0 && offset >= style->dash[i]) {
+ offset -= style->dash[i];
+ on = !on;
+ if (++i == style->num_dashes)
+ i = 0;
+ }
+
+ *num_dashes = 2;
+
+ dashes[0] = scale * coverage;
+ dashes[1] = scale * (1.0 - coverage);
+
+ *dash_offset = on ? 0.0 : dashes[0];
+}
diff --git a/src/cairoint.h b/src/cairoint.h
index 5912173..14a9491 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1749,6 +1749,26 @@ _cairo_stroke_style_max_distance_from_path (const cairo_stroke_style_t *style,
const cairo_matrix_t *ctm,
double *dx, double *dy);
+cairo_private double
+_cairo_stroke_style_dash_period (const cairo_stroke_style_t *style);
+
+cairo_private double
+_cairo_stroke_style_dash_stroked (const cairo_stroke_style_t *style);
+
+cairo_private cairo_bool_t
+_cairo_stroke_style_dash_can_approximate (const cairo_stroke_style_t *style,
+ const cairo_matrix_t *ctm,
+ double tolerance);
+
+cairo_private void
+_cairo_stroke_style_dash_approximate (const cairo_stroke_style_t *style,
+ const cairo_matrix_t *ctm,
+ double tolerance,
+ double *dash_offset,
+ double *dashes,
+ unsigned int *num_dashes);
+
+
/* cairo-surface.c */
cairo_private cairo_surface_t *
commit 9c24288c820069e80b0feb5e99ece4c89e92c0c6
Author: Andrea Canciani <ranma42 at gmail.com>
Date: Wed Nov 11 00:09:08 2009 +0100
Revert "[test] Reorder dash-infinite-loop to not hit a runaway allocation."
The infinite loop problem in _cairo_stroker_dash_start is solved by
commit ee02f3484899527380df94c00f40da87f41660ea, so hitting that
problem is not possible anymore and dash-infinite stroke always
hit the memory intensive loops.
This reverts commit 29432d3d32bc84ec4a2e1815a84e4ac2089138fe.
diff --git a/test/dash-infinite-loop.c b/test/dash-infinite-loop.c
index 5476137..a3d7544 100644
--- a/test/dash-infinite-loop.c
+++ b/test/dash-infinite-loop.c
@@ -68,9 +68,9 @@ draw (cairo_t *cr, int width, int height)
/* The following calls will wedge in various places that try
* to advance the dashing in a loop inside the stroker. */
- do_dash (cr, 30, 30, 1); /* _cairo_stroker_dash_start */
do_dash (cr, 30, 30, 0); /* _cairo_stroker_line_to_dashed */
do_dash (cr, 30, 0, 0); /* _cairo_rectilinear_stroker_line_to_dashed */
+ do_dash (cr, 30, 30, 1); /* _cairo_stroker_dash_start */
return CAIRO_TEST_SUCCESS;
}
commit cc2d2630669b084ec43e415d2806d94af00cf56c
Author: Andrea Canciani <ranma42 at gmail.com>
Date: Tue Nov 10 22:58:59 2009 +0100
Improve stroke offset computation
The stroke offset was forced to be positive because stroking code
wants to be able to decrement it until it finds the first dash to be
drawn. This can lead to long (almost infinite) loops if the offset is
positive but huge compared to the total length of the dash pattern.
Computing the offset this way guarantees that it's always the smallest
non-negative equivalent offset.
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 35934f9..672c2da 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -544,12 +544,10 @@ _cairo_gstate_set_dash (cairo_gstate_t *gstate, const double *dash, int num_dash
if (gstate->stroke_style.num_dashes & 1)
dash_total *= 2;
- /* The dashing code doesn't like a negative offset, so we compute
- * the equivalent positive offset. */
- if (offset < 0)
- offset += ceil (-offset / dash_total + 0.5) * dash_total;
-
- gstate->stroke_style.dash_offset = offset;
+ /* The dashing code doesn't like a negative offset or a big positive
+ * offset, so we compute an equivalent offset which is guaranteed to be
+ * positive and less than twice the pattern length. */
+ gstate->stroke_style.dash_offset = fmod (offset, dash_total) + dash_total;
return CAIRO_STATUS_SUCCESS;
}
commit e436a57c22f2c2a87404cac27e2d5e3c404f8bf9
Author: Andrea Canciani <ranma42 at gmail.com>
Date: Tue Nov 10 13:29:28 2009 +0100
Fix odd length dashing with negative offset
When computing an equivalent offset, a wrong total dash length was
used when the dash elements were odd and more than 1.
Doubling the total dash length whenever they are odd is needed to
correctly compute the new offset.
Fixes dash-offset.
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 86e20bc..35934f9 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -539,9 +539,9 @@ _cairo_gstate_set_dash (cairo_gstate_t *gstate, const double *dash, int num_dash
if (dash_total == 0.0)
return _cairo_error (CAIRO_STATUS_INVALID_DASH);
- /* A single dash value indicate symmetric repeating, so the total
+ /* An odd dash value indicate symmetric repeating, so the total
* is twice as long. */
- if (gstate->stroke_style.num_dashes == 1)
+ if (gstate->stroke_style.num_dashes & 1)
dash_total *= 2;
/* The dashing code doesn't like a negative offset, so we compute
commit b1a76394655793fd698a1281b00a3d049f9e70f5
Author: Andrea Canciani <ranma42 at gmail.com>
Date: Tue Nov 10 13:09:50 2009 +0100
Add dash-offset test
Stroking a dash pattern of odd length with a negative offset is broken
(except when the pattern is composed by a single dash).
diff --git a/test/Makefile.am b/test/Makefile.am
index af91f71..0e0593b 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -312,6 +312,7 @@ REFERENCE_IMAGES = \
dash-curve.xlib.ref.png \
dash-infinite-loop.ref.png \
dash-no-dash.ref.png \
+ dash-offset.ref.png \
dash-offset-negative.ref.png \
dash-scale.ps2.argb32.ref.png \
dash-scale.ps2.rgb24.ref.png \
diff --git a/test/Makefile.sources b/test/Makefile.sources
index 7c05dca..8dff25a 100644
--- a/test/Makefile.sources
+++ b/test/Makefile.sources
@@ -48,6 +48,7 @@ test_sources = \
dash-curve.c \
dash-infinite-loop.c \
dash-no-dash.c \
+ dash-offset.c \
dash-offset-negative.c \
dash-scale.c \
dash-state.c \
diff --git a/test/dash-offset.c b/test/dash-offset.c
new file mode 100644
index 0000000..9fa29a6
--- /dev/null
+++ b/test/dash-offset.c
@@ -0,0 +1,95 @@
+/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright 2009 Andrea Canciani
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is University of Southern
+ * California.
+ *
+ * Contributor(s):
+ * Andrea Canciani <ranma42 at gmail.com>
+ */
+
+#include "cairo-test.h"
+
+#define ARRAY_SIZE(a) (sizeof (a) / sizeof ((a)[0]))
+
+/* Lengths of the dashes of the dash patterns */
+static const double dashes[] = { 2, 2, 4, 4 };
+/* Dash offset in userspace units
+ * They always grow by 2, so the dash pattern is
+ * should be shifted by the same amount each time */
+static const double frac_offset[] = { 0, 2, 4, 6 };
+/* Dash offset relative to the whole dash pattern
+ * This corresponds to the non-inverted part only if
+ * the dash pattern has odd length, so the expected result
+ * is the same for every int_offset if the pattern has
+ * even lenght, and inverted each time (or shifted by half
+ * period, which is the same) if the pattern has odd length. */
+static const double int_offset[] = { -2, -1, 0, 1, 2 };
+
+#define PAD 6
+#define STROKE_LENGTH 32
+#define IMAGE_WIDTH (PAD + (STROKE_LENGTH + PAD) * ARRAY_SIZE(dashes))
+#define IMAGE_HEIGHT (PAD + PAD * ARRAY_SIZE(int_offset) + PAD * ARRAY_SIZE(frac_offset) * ARRAY_SIZE(int_offset))
+
+
+static cairo_test_status_t
+draw (cairo_t *cr, int width, int height)
+{
+ double total;
+ size_t i, j, k;
+
+ cairo_set_source_rgb (cr, 1, 1, 1);
+ cairo_paint (cr);
+
+ cairo_set_source_rgb (cr, 0, 0, 0);
+ cairo_set_line_width (cr, 2);
+
+ total = 0.0;
+ for (k = 0; k < ARRAY_SIZE(dashes); ++k) {
+ total += dashes[k];
+ for (i = 0; i < ARRAY_SIZE(frac_offset); ++i) {
+ for (j = 0; j < ARRAY_SIZE(int_offset); ++j) {
+ cairo_set_dash (cr, dashes, k + 1, frac_offset[i] + total * int_offset[j]);
+ cairo_move_to (cr, (STROKE_LENGTH + PAD) * k + PAD, PAD * (i + j + ARRAY_SIZE(frac_offset) * j + 1));
+ cairo_line_to (cr, (STROKE_LENGTH + PAD) * (k + 1), PAD * (i + j + ARRAY_SIZE(frac_offset) * j + 1));
+ cairo_stroke (cr);
+ }
+ }
+ }
+
+ return CAIRO_TEST_SUCCESS;
+}
+
+CAIRO_TEST (dash_offset,
+ "Tests dashes of different length with various offsets",
+ "stroke, dash", /* keywords */
+ NULL, /* requirements */
+ IMAGE_WIDTH, IMAGE_HEIGHT,
+ NULL, draw)
diff --git a/test/dash-offset.ref.png b/test/dash-offset.ref.png
new file mode 100644
index 0000000..52600c4
Binary files /dev/null and b/test/dash-offset.ref.png differ
More information about the cairo-commit
mailing list