[gtk/path-stroke: 8/13] Implement stroking
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/path-stroke: 8/13] Implement stroking
- Date: Sun, 20 Dec 2020 23:30:49 +0000 (UTC)
commit 885edae2ef2ec6c3f488afbb4d7a19b3560062e8
Author: Matthias Clasen <mclasen redhat com>
Date: Fri Nov 27 14:05:25 2020 -0500
Implement stroking
Implement gsk_contour_default_add_stroke, which takes a contour
and stroke parameters, and adds contours to a path builder for
the outline that woul be produced by stroking the path with these
parameters.
The current implementation does not try to handle short segments
in the vicinity of sharp joins in any special way, so there can
be some artifacts in that situation.
gsk/gskcontour.c | 5 +
gsk/gskpath.c | 4 +
gsk/gskpathmeasure.c | 2 +-
gsk/gskpathstroke.c | 1179 +++++++++++++++++++++++++++++++++++++++++++
gsk/meson.build | 1 +
testsuite/gsk/meson.build | 1 +
testsuite/gsk/path-stroke.c | 67 +++
7 files changed, 1258 insertions(+), 1 deletion(-)
---
diff --git a/gsk/gskcontour.c b/gsk/gskcontour.c
index e0a1df709a..ce4dcc64d2 100644
--- a/gsk/gskcontour.c
+++ b/gsk/gskcontour.c
@@ -527,6 +527,8 @@ gsk_rect_contour_add_stroke (const GskContour *contour,
rect.size.width = - rect.size.width;
gsk_path_builder_add_rect (builder, &rect);
}
+ else
+ gsk_contour_default_add_stroke (contour, builder, stroke);
}
static const GskContourClass GSK_RECT_CONTOUR_CLASS =
@@ -922,6 +924,8 @@ gsk_circle_contour_add_stroke (const GskContour *contour,
self->start_angle);
gsk_path_builder_add_contour (builder, c);
}
+ else
+ gsk_contour_default_add_stroke (contour, builder, stroke);
}
static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS =
@@ -1634,6 +1638,7 @@ gsk_standard_contour_add_stroke (const GskContour *contour,
GskPathBuilder *builder,
GskStroke *stroke)
{
+ gsk_contour_default_add_stroke (contour, builder, stroke);
}
static const GskContourClass GSK_STANDARD_CONTOUR_CLASS =
diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index ec4fe8e71f..5d07f831e5 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -24,6 +24,10 @@
#include "gskcurveprivate.h"
#include "gskpathbuilder.h"
+#include "gskstrokeprivate.h"
+
+#include "gdk/gdk-private.h"
+
/**
* SECTION:gskpath
* @Title: Path
diff --git a/gsk/gskpathmeasure.c b/gsk/gskpathmeasure.c
index 3a181eb0ab..20fb4ff81b 100644
--- a/gsk/gskpathmeasure.c
+++ b/gsk/gskpathmeasure.c
@@ -20,6 +20,7 @@
#include "config.h"
#include "gskpathmeasure.h"
+#include "gskpathbuilder.h"
#include "gskpathbuilder.h"
#include "gskpathprivate.h"
@@ -625,4 +626,3 @@ gsk_path_builder_add_segment (GskPathBuilder *self,
gsk_path_builder_close (self);
}
}
-
diff --git a/gsk/gskpathstroke.c b/gsk/gskpathstroke.c
new file mode 100644
index 0000000000..5a4181da84
--- /dev/null
+++ b/gsk/gskpathstroke.c
@@ -0,0 +1,1179 @@
+/*
+ * Copyright © 2020 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Matthias Clasen <mclasen redhat com>
+ */
+
+#include "gskpathprivate.h"
+
+#include "gskpathbuilder.h"
+
+#include "gskstrokeprivate.h"
+#include "gskcurveprivate.h"
+#include "gskpathdashprivate.h"
+#include "gskpathopprivate.h"
+
+#define STROKE_DEBUG
+
+#define RAD_TO_DEG(r) ((r)*180.0/M_PI)
+#define DEG_TO_RAD(d) ((d)*M_PI/180.0)
+
+/* {{{ graphene utilities */
+
+static void
+get_tangent (const graphene_point_t *p0,
+ const graphene_point_t *p1,
+ graphene_vec2_t *t)
+{
+ graphene_vec2_init (t, p1->x - p0->x, p1->y - p0->y);
+ graphene_vec2_normalize (t, t);
+}
+
+static void
+get_normal (const graphene_point_t *p0,
+ const graphene_point_t *p1,
+ graphene_vec2_t *n)
+{
+ graphene_vec2_init (n, p0->y - p1->y, p1->x - p0->x);
+ graphene_vec2_normalize (n, n);
+}
+
+/* Return the angle between t1 and t2 in radians, such that
+ * 0 means straight continuation
+ * < 0 means right turn
+ * > 0 means left turn
+ */
+static float
+angle_between (const graphene_vec2_t *t1,
+ const graphene_vec2_t *t2)
+{
+ float angle = atan2 (graphene_vec2_get_y (t2), graphene_vec2_get_x (t2))
+ - atan2 (graphene_vec2_get_y (t1), graphene_vec2_get_x (t1));
+
+ if (angle > M_PI)
+ angle -= 2 * M_PI;
+ if (angle < - M_PI)
+ angle += 2 * M_PI;
+
+ return angle;
+}
+
+/* Set p to the intersection of the lines a + t * ab * and
+ * c + s * cd. Return 1 if the lines intersect, 0 otherwise.
+ */
+static int
+line_intersect (const graphene_point_t *a,
+ const graphene_vec2_t *ab,
+ const graphene_point_t *c,
+ const graphene_vec2_t *cd,
+ graphene_point_t *p)
+{
+ float a1 = graphene_vec2_get_y (ab);
+ float b1 = - graphene_vec2_get_x (ab);
+ float c1 = a1 * a->x + b1 * a->y;
+
+ float a2 = graphene_vec2_get_y (cd);
+ float b2 = - graphene_vec2_get_x (cd);
+ float c2 = a2 * c->x + b2 * c->y;
+
+ float det = a1 * b2 - a2 * b1;
+
+ if (fabs (det) <= 0.001)
+ return 0;
+
+ p->x = (b2 * c1 - b1 * c2) / det;
+ p->y = (a1 * c2 - a2 * c1) / det;
+
+ return 1;
+}
+
+/* }}} */
+ /* {{{ GskPathBuilder utilities */
+
+static void
+path_builder_move_to_point (GskPathBuilder *builder,
+ const graphene_point_t *point)
+{
+ gsk_path_builder_move_to (builder, point->x, point->y);
+}
+
+static void
+path_builder_line_to_point (GskPathBuilder *builder,
+ const graphene_point_t *point)
+{
+ gsk_path_builder_line_to (builder, point->x, point->y);
+}
+
+/* Assumes that the current point of the builder is
+ * the start point of the curve
+ */
+static void
+path_builder_add_curve (GskPathBuilder *builder,
+ const GskCurve *curve)
+{
+ const graphene_point_t *p;
+
+ switch (curve->op)
+ {
+ case GSK_PATH_LINE:
+ p = curve->line.points;
+ gsk_path_builder_line_to (builder, p[1].x, p[1].y);
+ break;
+
+ case GSK_PATH_CURVE:
+ p = curve->curve.points;
+ gsk_path_builder_curve_to (builder, p[1].x, p[1].y,
+ p[2].x, p[2].y,
+ p[3].x, p[3].y);
+ break;
+
+ case GSK_PATH_CONIC:
+ p = curve->conic.points;
+ gsk_path_builder_conic_to (builder, p[1].x, p[1].y,
+ p[3].x, p[3].y,
+ p[2].x);
+ break;
+
+ case GSK_PATH_MOVE:
+ case GSK_PATH_CLOSE:
+ default:
+ g_assert_not_reached ();
+ }
+}
+
+static gboolean
+add_op (GskPathOperation op,
+ const graphene_point_t *pts,
+ gsize n_pts,
+ float weight,
+ gpointer user_data)
+{
+ GskCurve c;
+ GskCurve *curve;
+ GList **ops = user_data;
+
+ if (op == GSK_PATH_MOVE)
+ return TRUE;
+
+ gsk_curve_init_foreach (&c, op, pts, n_pts, weight);
+ curve = g_new0 (GskCurve, 1);
+ gsk_curve_reverse (&c, curve);
+
+ *ops = g_list_prepend (*ops, curve);
+
+ return TRUE;
+}
+
+static void
+path_builder_add_reverse_path (GskPathBuilder *builder,
+ GskPath *path)
+{
+ GList *l, *ops;
+
+ ops = NULL;
+ gsk_path_foreach (path,
+ GSK_PATH_FOREACH_ALLOW_CURVE | GSK_PATH_FOREACH_ALLOW_CONIC,
+ add_op,
+ &ops);
+ for (l = ops; l; l = l->next)
+ {
+ GskCurve *curve = l->data;
+ path_builder_add_curve (builder, curve);
+ }
+ g_list_free_full (ops, g_free);
+}
+
+/* }}} */
+/* {{{ GskCurve utilities */
+
+static gboolean
+cubic_is_simple (const GskCurve *curve)
+{
+ const graphene_point_t *pts = curve->curve.points;
+ float a1, a2, s;
+ graphene_vec2_t t1, t2, t3;
+ graphene_vec2_t n1, n2;
+
+ get_tangent (&pts[0], &pts[1], &t1);
+ get_tangent (&pts[1], &pts[2], &t2);
+ get_tangent (&pts[2], &pts[3], &t3);
+ a1 = angle_between (&t1, &t2);
+ a2 = angle_between (&t2, &t3);
+
+ if ((a1 < 0 && a2 > 0) || (a1 > 0 && a2 < 0))
+ return FALSE;
+
+ get_normal (&pts[0], &pts[1], &n1);
+ get_normal (&pts[2], &pts[3], &n2);
+
+ s = graphene_vec2_dot (&n1, &n2);
+
+ if (fabs (acos (s)) >= M_PI / 3.f)
+ return FALSE;
+
+ return TRUE;
+}
+
+static gboolean
+curve_is_degenerate (const GskCurve *curve)
+{
+ if (curve->op == GSK_PATH_CURVE)
+ {
+ const graphene_point_t *pts = curve->curve.points;
+ float a1, a2;
+ graphene_vec2_t t1, t2, t3;
+
+ get_tangent (&pts[0], &pts[1], &t1);
+ get_tangent (&pts[1], &pts[2], &t2);
+ get_tangent (&pts[2], &pts[3], &t3);
+ a1 = angle_between (&t1, &t2);
+ a2 = angle_between (&t2, &t3);
+
+ if (a1 < 0)
+ a1 += M_PI;
+ if (a2 < 0)
+ a2 += M_PI;
+
+ if (MIN (fabs (M_PI - a1), fabs (a1)) < DEG_TO_RAD (3) &&
+ MIN (fabs (M_PI - a2), fabs (a2)) < DEG_TO_RAD (3))
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+static void
+align_points (const graphene_point_t *p,
+ const graphene_point_t *a,
+ const graphene_point_t *b,
+ graphene_point_t *q,
+ int n)
+{
+ graphene_vec2_t n1;
+ float angle;
+ float s, c;
+
+ get_tangent (a, b, &n1);
+ angle = - atan2 (graphene_vec2_get_y (&n1), graphene_vec2_get_x (&n1));
+ sincosf (angle, &s, &c);
+
+ for (int i = 0; i < n; i++)
+ {
+ q[i].x = (p[i].x - a->x) * c - (p[i].y - a->y) * s;
+ q[i].y = (p[i].x - a->x) * s + (p[i].y - a->y) * c;
+ }
+}
+
+static int
+get_cubic_extrema (float pa, float pb, float pc, float pd, float t[2])
+{
+ float a, b, c;
+ float d, tt;
+ int n = 0;
+
+ a = 3 * (pd - 3*pc + 3*pb - pa);
+ b = 6 * (pc - 2*pb + pa);
+ c = 3 * (pb - pa);
+
+ if (fabs (a) > 0.0001)
+ {
+ if (b*b > 4*a*c)
+ {
+ d = sqrt (b*b - 4*a*c);
+ tt = (-b + d)/(2*a);
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ tt = (-b - d)/(2*a);
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ }
+ else
+ {
+ tt = -b / (2*a);
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ }
+ }
+ else if (fabs (b) > 0.0001)
+ {
+ tt = -c / b;
+ if (0 < tt && tt < 1)
+ t[n++] = tt;
+ }
+
+ return n;
+}
+
+/* For degenerate curves, find interior points
+ * where the function has a cusp. We do that by
+ * aligning the control points to be all on the
+ * x axis, and then looking for the t where x
+ * has the min/max value.
+ */
+static int
+find_turning_points (const GskCurve *curve,
+ float t[2])
+{
+ const graphene_point_t *pts = curve->curve.points;
+ graphene_point_t p[4];
+
+ align_points (pts, &pts[0], &pts[1], p, 4);
+
+ return get_cubic_extrema (p[0].x, p[1].x, p[2].x, p[3].x, t);
+}
+
+/* Get the points where the curvature of curve is
+ * zero, or a maximum or minimum, inside the open
+ * interval from 0 to 1.
+ */
+static int
+cubic_curvature_points (const GskCurve *curve,
+ float t[3])
+{
+ const graphene_point_t *pts = curve->curve.points;
+ graphene_point_t p[4];
+ float a, b, c, d;
+ float x, y, z;
+ float u2, u, tt;
+ int n_roots = 0;
+
+ align_points (pts, &pts[0], &pts[3], p, 4);
+
+ a = p[2].x * p[1].y;
+ b = p[3].x * p[1].y;
+ c = p[1].x * p[2].y;
+ d = p[3].x * p[2].y;
+
+ x = - 3*a + 2*b + 3*c - d;
+ y = 3*a - b - 3*c;
+ z = c - a;
+
+ if (fabs (x) >= 0.001)
+ {
+ tt = -y / (2*x);
+ if (0 < tt && tt < 1)
+ t[n_roots++] = tt;
+
+ u2 = y*y - 4*x*z;
+ if (u2 > 0.001)
+ {
+ u = sqrt (u2);
+
+ tt = (-y + u) / (2*x);
+ if (0 < tt && tt < 1)
+ t[n_roots++] = tt;
+
+ tt = (-y - u) / (2*x);
+ if (0 < tt && tt < 1)
+ t[n_roots++] = tt;
+ }
+ }
+
+ return n_roots;
+}
+
+/* }}} */
+/* {{{ Stroke helpers */
+
+static void
+add_line_join (GskPathBuilder *builder,
+ GskLineJoin line_join,
+ float line_width,
+ float miter_limit,
+ const graphene_point_t *c,
+ const graphene_point_t *a,
+ const graphene_vec2_t *ta,
+ const graphene_point_t *b,
+ const graphene_vec2_t *tb,
+ float angle)
+{
+ switch (line_join)
+ {
+ case GSK_LINE_JOIN_MITER:
+ case GSK_LINE_JOIN_MITER_CLIP:
+ {
+ graphene_point_t p;
+
+ if (line_intersect (a, ta, b, tb, &p))
+ {
+ graphene_vec2_t tam;
+
+ graphene_vec2_negate (ta, &tam);
+
+ /* Check that 1 / sin (psi / 2) <= miter_limit,
+ * where psi is the angle between ta and tb
+ */
+ if (2 <= miter_limit * miter_limit * (1 - graphene_vec2_dot (&tam, tb)))
+ {
+ path_builder_line_to_point (builder, &p);
+ path_builder_line_to_point (builder, b);
+ }
+ else if (line_join == GSK_LINE_JOIN_MITER_CLIP)
+ {
+ graphene_point_t q, a1, b1;
+ graphene_vec2_t n;
+
+ q.x = (c->x + p.x) / 2;
+ q.y = (c->y + p.y) / 2;
+ get_normal (c, &p, &n);
+
+ line_intersect (a, ta, &q, &n, &a1);
+ line_intersect (b, tb, &q, &n, &b1);
+
+ path_builder_line_to_point (builder, &a1);
+ path_builder_line_to_point (builder, &b1);
+ path_builder_line_to_point (builder, b);
+ }
+ else
+ {
+ path_builder_line_to_point (builder, b);
+ }
+ }
+ }
+ break;
+
+ case GSK_LINE_JOIN_ROUND:
+ gsk_path_builder_svg_arc_to (builder,
+ line_width / 2, line_width / 2,
+ 0, 0, angle > 0 ? 1 : 0,
+ b->x, b->y);
+ break;
+
+ case GSK_LINE_JOIN_BEVEL:
+ path_builder_line_to_point (builder, b);
+ break;
+
+ default:
+ g_assert_not_reached ();
+ }
+}
+
+static void
+add_line_cap (GskPathBuilder *builder,
+ GskLineCap line_cap,
+ float line_width,
+ const graphene_point_t *s,
+ const graphene_point_t *e)
+{
+ switch (line_cap)
+ {
+ case GSK_LINE_CAP_BUTT:
+ path_builder_line_to_point (builder, e);
+ break;
+
+ case GSK_LINE_CAP_ROUND:
+ gsk_path_builder_svg_arc_to (builder,
+ line_width / 2, line_width / 2,
+ 0, 1, 0,
+ e->x, e->y);
+ break;
+
+ case GSK_LINE_CAP_SQUARE:
+ {
+ float cx = (s->x + e->x) / 2;
+ float cy = (s->y + e->y) / 2;
+ float dx = s->y - cy;
+ float dy = - s->x + cx;
+
+ gsk_path_builder_line_to (builder, s->x + dx, s->y + dy);
+ gsk_path_builder_line_to (builder, e->x + dx, e->y + dy);
+ path_builder_line_to_point (builder, e);
+ }
+ break;
+
+ default:
+ g_assert_not_reached ();
+ break;
+ }
+}
+
+/* }}} */
+
+/* The general theory of operation for the stroker:
+ *
+ * We walk the segments of the path, offsetting each segment
+ * to the left and right, and collect the offset segments in
+ * a left and a right contour.
+ *
+ * When the segment is too curvy, we subdivide it before we
+ * add the pieces.
+ *
+ * Whenever we add a segment, we need to decide if the join
+ * is a smooth connection, a right turn, or a left turn. For
+ * the smooth connections, we just connect the end points of
+ * the offset curves with line segments. For sharp turns, we
+ * add a line join on the one side, and intersect the offset
+ * curves on the other.
+ *
+ * Since the intersection shortens both segments, we have to
+ * delay adding the previous segments to the outlines until
+ * we've handled the join at their end. We also need to hold
+ * off on adding the initial segment to the outlines until
+ * we've seen the end of the current contour of the path, to
+ * handle the join at before the initial segment for closed
+ * contours.
+ *
+ * If the contour turns out to not be closed when we reach
+ * the end, we collect the pending segments, reverse the
+ * left contour, and connect the right and left contour
+ * with end caps, closing the resulting outline.
+ *
+ * If the path isn't done after we've finished handling the
+ * outlines of the current contour, we start over with
+ * collecting offset segments of the next contour.
+ *
+ * We rely on the ability to offset, subdivide, intersect
+ * and reverse curves.
+ */
+typedef struct
+{
+ GskPathBuilder *builder; // builder that collects the stroke
+ GskStroke *stroke; // stroke parameters
+
+ GskPathBuilder *left; // accumulates the left contour
+ GskPathBuilder *right; // accumulates the right contour
+
+ gboolean has_current_point; // r0, l0 have been set from a move
+ gboolean has_current_curve; // c, l, r are set from a curve
+ gboolean is_first_curve; // if c, l, r are the first segments we've seen
+
+ GskCurve c; // previous segment of the path
+ GskCurve l; // candidate for left contour of c
+ GskCurve r; // candidate for right contour of c
+
+ GskCurve c0; // first segment of the path
+ GskCurve l0; // first segment of left contour
+ GskCurve r0; // first segment of right contour
+
+#ifdef STROKE_DEBUG
+ GskPathBuilder *debug;
+#endif
+} StrokeData;
+
+static void
+append_right (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ if (stroke_data->is_first_curve)
+ {
+ stroke_data->r0 = *curve;
+ path_builder_move_to_point (stroke_data->right, gsk_curve_get_end_point (curve));
+ }
+ else
+ path_builder_add_curve (stroke_data->right, curve);
+}
+
+static void
+append_left (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ if (stroke_data->is_first_curve)
+ {
+ stroke_data->l0 = *curve;
+ path_builder_move_to_point (stroke_data->left, gsk_curve_get_end_point (curve));
+ }
+ else
+ path_builder_add_curve (stroke_data->left, curve);
+}
+
+/* Add the previous segments, stroke_data->l and ->r, and the join between
+ * stroke_data->c and curve and update stroke_data->l, ->r and ->c to point
+ * to the given curves.
+ *
+ * If stroke_data->c is the first segment of the contour, we don't add it
+ * yet, but save it in stroke_data->c0, ->r0 and ->l0 for later when we
+ * know if the contour is closed or not.
+ */
+static void
+add_segments (StrokeData *stroke_data,
+ const GskCurve *curve,
+ GskCurve *r,
+ GskCurve *l,
+ gboolean force_round_join)
+{
+ float angle;
+ float t1, t2;
+ graphene_vec2_t tangent1, tangent2;
+ graphene_point_t p;
+
+ if (!stroke_data->has_current_curve)
+ {
+ stroke_data->c0 = *curve;
+ stroke_data->r0 = *r;
+ stroke_data->l0 = *l;
+ path_builder_move_to_point (stroke_data->right, gsk_curve_get_start_point (r));
+ path_builder_move_to_point (stroke_data->left, gsk_curve_get_start_point (l));
+
+ stroke_data->c = *curve;
+ stroke_data->r = *r;
+ stroke_data->l = *l;
+
+ stroke_data->has_current_curve = TRUE;
+ stroke_data->is_first_curve = TRUE;
+ return;
+ }
+
+ gsk_curve_get_end_tangent (&stroke_data->c, &tangent1);
+ gsk_curve_get_start_tangent (curve, &tangent2);
+ angle = angle_between (&tangent1, &tangent2);
+
+ if (fabs (angle) < DEG_TO_RAD (5))
+ {
+ /* Close enough to a straight line */
+ append_right (stroke_data, &stroke_data->r);
+ path_builder_line_to_point (stroke_data->right, gsk_curve_get_start_point (r));
+
+ append_left (stroke_data, &stroke_data->l);
+ path_builder_line_to_point (stroke_data->left, gsk_curve_get_start_point (l));
+ }
+ else if (angle > 0)
+ {
+ /* Right turn */
+ if (gsk_curve_intersect (&stroke_data->r, r, &t1, &t2, &p, 1) > 0)
+ {
+ GskCurve c1, c2;
+
+ gsk_curve_split (&stroke_data->r, t1, &c1, &c2);
+ stroke_data->r = c1;
+ gsk_curve_split (r, t2, &c1, &c2);
+ *r = c2;
+
+ append_right (stroke_data, &stroke_data->r);
+ }
+ else
+ {
+ append_right (stroke_data, &stroke_data->r);
+ path_builder_line_to_point (stroke_data->right, gsk_curve_get_start_point (r));
+ }
+
+ append_left (stroke_data, &stroke_data->l);
+
+ add_line_join (stroke_data->left,
+ force_round_join ? GSK_LINE_JOIN_ROUND
+ : stroke_data->stroke->line_join,
+ stroke_data->stroke->line_width,
+ stroke_data->stroke->miter_limit,
+ gsk_curve_get_start_point (curve),
+ gsk_curve_get_end_point (&stroke_data->l),
+ &tangent1,
+ gsk_curve_get_start_point (l),
+ &tangent2,
+ angle);
+ }
+ else
+ {
+ /* Left turn */
+ append_right (stroke_data, &stroke_data->r);
+
+ add_line_join (stroke_data->right,
+ force_round_join ? GSK_LINE_JOIN_ROUND
+ : stroke_data->stroke->line_join,
+ stroke_data->stroke->line_width,
+ stroke_data->stroke->miter_limit,
+ gsk_curve_get_start_point (curve),
+ gsk_curve_get_end_point (&stroke_data->r),
+ &tangent1,
+ gsk_curve_get_start_point (r),
+ &tangent2,
+ angle);
+
+ if (gsk_curve_intersect (&stroke_data->l, l, &t1, &t2, &p, 1) > 0)
+ {
+ GskCurve c1, c2;
+
+ gsk_curve_split (&stroke_data->l, t1, &c1, &c2);
+ stroke_data->l = c1;
+ gsk_curve_split (l, t2, &c1, &c2);
+ *l = c2;
+
+ append_left (stroke_data, &stroke_data->l);
+ }
+ else
+ {
+ append_left (stroke_data, &stroke_data->l);
+ path_builder_line_to_point (stroke_data->left, gsk_curve_get_start_point (l));
+ }
+ }
+
+ stroke_data->c = *curve;
+ stroke_data->r = *r;
+ stroke_data->l = *l;
+ stroke_data->is_first_curve = FALSE;
+}
+
+#ifdef STROKE_DEBUG
+static void
+add_debug (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ const graphene_point_t *p;
+
+ if (g_getenv ("STROKE_DEBUG"))
+ {
+ switch (curve->op)
+ {
+ case GSK_PATH_LINE:
+ case GSK_PATH_CLOSE:
+ p = curve->line.points;
+ gsk_path_builder_add_circle (stroke_data->debug, &p[0], 3);
+ gsk_path_builder_add_circle (stroke_data->debug, &p[1], 3);
+ break;
+ case GSK_PATH_CURVE:
+ p = curve->curve.points;
+ gsk_path_builder_add_circle (stroke_data->debug, &p[0], 3);
+ gsk_path_builder_add_circle (stroke_data->debug, &p[3], 3);
+ break;
+ case GSK_PATH_CONIC:
+ p = curve->conic.points;
+ gsk_path_builder_add_circle (stroke_data->debug, &p[0], 3);
+ gsk_path_builder_add_circle (stroke_data->debug, &p[3], 3);
+ break;
+ case GSK_PATH_MOVE:
+ default:
+ g_assert_not_reached ();
+ }
+ }
+}
+#endif
+
+
+/* Add a curve to the in-progress stroke. We look at the angle between
+ * the previous curve and this one to determine on which side we need
+ * to intersect the curves, and on which to add a join.
+ */
+static void
+add_curve (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ GskCurve l, r;
+
+#ifdef STROKE_DEBUG
+ add_debug (stroke_data, curve);
+#endif
+
+ gsk_curve_offset (curve, - stroke_data->stroke->line_width / 2, &l);
+ gsk_curve_offset (curve, stroke_data->stroke->line_width / 2, &r);
+
+ add_segments (stroke_data, curve, &r, &l, FALSE);
+}
+
+static void
+add_curve_round_join (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ GskCurve l, r;
+
+#ifdef STROKE_DEBUG
+ add_debug (stroke_data, curve);
+#endif
+
+ gsk_curve_offset (curve, - stroke_data->stroke->line_width / 2, &l);
+ gsk_curve_offset (curve, stroke_data->stroke->line_width / 2, &r);
+
+ add_segments (stroke_data, curve, &r, &l, TRUE);
+}
+
+static int
+cmpfloat (const void *p1, const void *p2)
+{
+ const float *f1 = p1;
+ const float *f2 = p2;
+ return *f1 < *f2 ? -1 : (*f1 > *f2 ? 1 : 0);
+}
+
+static void
+add_degenerate_curve (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ float t[3];
+ int n;
+ GskCurve c;
+ graphene_point_t p[2];
+
+ n = find_turning_points (curve, t);
+
+ if (n == 0)
+ add_curve (stroke_data, curve);
+ else if (n == 1)
+ {
+ p[0] = *gsk_curve_get_start_point (curve);
+ gsk_curve_get_point (curve, t[0], &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve (stroke_data, &c);
+
+ p[0] = p[1];
+ p[1] = *gsk_curve_get_end_point (curve);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
+ }
+ else
+ {
+ qsort (t, n, sizeof (float), cmpfloat);
+
+ p[0] = *gsk_curve_get_start_point (curve);
+ gsk_curve_get_point (curve, t[0], &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve (stroke_data, &c);
+
+ p[0] = p[1];
+ gsk_curve_get_point (curve, t[1], &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
+
+ p[0] = p[1];
+ p[1] = *gsk_curve_get_end_point (curve);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
+ }
+}
+
+static void
+add_degenerate_conic (StrokeData *stroke_data,
+ const GskCurve *curve)
+{
+ GskCurve c;
+ graphene_point_t p[2];
+
+ p[0] = *gsk_curve_get_start_point (curve);
+ gsk_curve_get_point (curve, 0.5, &p[1]);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve (stroke_data, &c);
+
+ p[0] = p[1];
+ p[1] = *gsk_curve_get_end_point (curve);
+ gsk_curve_init_foreach (&c, GSK_PATH_LINE, p, 2, 0);
+ add_curve_round_join (stroke_data, &c);
+}
+
+#define MAX_SUBDIVISION 8
+
+static void
+subdivide_and_add_curve (StrokeData *stroke_data,
+ const GskCurve *curve,
+ int level)
+{
+ if (level == MAX_SUBDIVISION && curve_is_degenerate (curve))
+ add_degenerate_curve (stroke_data, curve);
+ else if (level == 0 || (level < MAX_SUBDIVISION && cubic_is_simple (curve)))
+ add_curve (stroke_data, curve);
+ else
+ {
+ float t[5];
+ int n = 0;
+
+ t[n++] = 0;
+ t[n++] = 1;
+
+ if (level == MAX_SUBDIVISION)
+ {
+ n += cubic_curvature_points (curve, &t[n]);
+ qsort (t, n, sizeof (float), cmpfloat);
+ }
+
+ if (n == 2)
+ {
+ GskCurve c1, c2;
+
+ gsk_curve_split (curve, 0.5, &c1, &c2);
+ subdivide_and_add_curve (stroke_data, &c1, level - 1);
+ subdivide_and_add_curve (stroke_data, &c2, level - 1);
+ }
+ else
+ {
+ GskCurve c;
+ for (int i = 0; i + 1 < n; i++)
+ {
+ gsk_curve_segment (curve, t[i], t[i+1], &c);
+ subdivide_and_add_curve (stroke_data, &c, level - 1);
+ }
+ }
+ }
+}
+
+static gboolean
+conic_is_simple (const GskCurve *curve)
+{
+ const graphene_point_t *pts = curve->conic.points;
+ graphene_vec2_t n1, n2;
+ float s;
+
+ get_normal (&pts[0], &pts[1], &n1);
+ get_normal (&pts[1], &pts[3], &n2);
+
+ s = graphene_vec2_dot (&n1, &n2);
+
+ if (fabs (acos (s)) >= M_PI / 3.f)
+ return FALSE;
+
+ return TRUE;
+}
+
+static gboolean
+conic_is_degenerate (const GskCurve *curve)
+{
+ if (curve->op == GSK_PATH_CONIC)
+ {
+ const graphene_point_t *pts = curve->curve.points;
+ float a;
+ graphene_vec2_t t1, t2;
+
+ get_tangent (&pts[0], &pts[1], &t1);
+ get_tangent (&pts[1], &pts[3], &t2);
+ a = angle_between (&t1, &t2);
+
+ if (a < 0)
+ a += M_PI;
+
+ if (fabs (a) < DEG_TO_RAD (3))
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+static void
+subdivide_and_add_conic (StrokeData *stroke_data,
+ const GskCurve *curve,
+ int level)
+{
+ if (level == MAX_SUBDIVISION && conic_is_degenerate (curve))
+ add_degenerate_conic (stroke_data, curve);
+ else if (level == 0 || (level < MAX_SUBDIVISION && conic_is_simple (curve)))
+ add_curve (stroke_data, curve);
+ else
+ {
+ GskCurve c1, c2;
+
+ gsk_curve_split (curve, 0.5, &c1, &c2);
+ subdivide_and_add_conic (stroke_data, &c1, level - 1);
+ subdivide_and_add_conic (stroke_data, &c2, level - 1);
+ }
+}
+
+/* Create a single closed contour and add it to
+ * stroke_data->builder, by connecting the right and the
+ * reversed left contour with caps.
+ *
+ * After this call, stroke_data->left and ->right are NULL.
+ */
+static void
+cap_and_connect_contours (StrokeData *stroke_data)
+{
+ GskPath *path;
+ const graphene_point_t *r0, *l0, *r1, *l1;
+
+ r1 = r0 = gsk_curve_get_start_point (&stroke_data->r0);
+ l1 = l0 = gsk_curve_get_start_point (&stroke_data->l0);
+
+ if (stroke_data->has_current_curve)
+ {
+ path_builder_add_curve (stroke_data->right, &stroke_data->r);
+ path_builder_add_curve (stroke_data->left, &stroke_data->l);
+
+ r1 = gsk_curve_get_end_point (&stroke_data->r);
+ l1 = gsk_curve_get_end_point (&stroke_data->l);
+ }
+ else
+ path_builder_move_to_point (stroke_data->right, r1);
+
+ add_line_cap (stroke_data->right,
+ stroke_data->stroke->line_cap,
+ stroke_data->stroke->line_width,
+ r1, l1);
+
+ if (stroke_data->has_current_curve)
+ {
+ GskCurve c;
+
+ path = gsk_path_builder_free_to_path (stroke_data->left);
+ path_builder_add_reverse_path (stroke_data->right, path);
+ gsk_path_unref (path);
+
+ if (!stroke_data->is_first_curve)
+ {
+ /* Add the first segment that wasn't added initially */
+ gsk_curve_reverse (&stroke_data->l0, &c);
+ path_builder_add_curve (stroke_data->right, &c);
+ }
+ }
+
+ add_line_cap (stroke_data->right,
+ stroke_data->stroke->line_cap,
+ stroke_data->stroke->line_width,
+ l0, r0);
+
+ if (stroke_data->has_current_curve)
+ {
+ if (!stroke_data->is_first_curve)
+ {
+ /* Add the first segment that wasn't added initially */
+ path_builder_add_curve (stroke_data->right, &stroke_data->r0);
+ }
+ }
+
+ gsk_path_builder_close (stroke_data->right);
+
+ path = gsk_path_builder_free_to_path (stroke_data->right);
+ gsk_path_builder_add_path (stroke_data->builder, path);
+ gsk_path_unref (path);
+
+ stroke_data->left = NULL;
+ stroke_data->right = NULL;
+}
+
+/* Close the left and the right contours and add them to
+ * stroke_data->builder.
+ *
+ * After this call, stroke_data->left and ->right are NULL.
+ */
+static void
+close_contours (StrokeData *stroke_data)
+{
+ GskPath *path;
+
+ if (stroke_data->has_current_curve)
+ {
+ /* add final join and first segment */
+ add_segments (stroke_data, &stroke_data->c0, &stroke_data->r0, &stroke_data->l0, FALSE);
+ path_builder_add_curve (stroke_data->right, &stroke_data->r);
+ path_builder_add_curve (stroke_data->left, &stroke_data->l);
+ }
+
+ gsk_path_builder_close (stroke_data->right);
+ gsk_path_builder_close (stroke_data->left);
+
+ path = gsk_path_builder_free_to_path (stroke_data->right);
+ gsk_path_builder_add_path (stroke_data->builder, path);
+ gsk_path_unref (path);
+
+ path = gsk_path_builder_free_to_path (stroke_data->left);
+ gsk_path_builder_add_path (stroke_data->builder, path);
+ gsk_path_unref (path);
+
+ stroke_data->left = NULL;
+ stroke_data->right = NULL;
+}
+
+static gboolean
+stroke_op (GskPathOperation op,
+ const graphene_point_t *pts,
+ gsize n_pts,
+ float weight,
+ gpointer user_data)
+{
+ StrokeData *stroke_data = user_data;
+ GskCurve curve;
+
+ switch (op)
+ {
+ case GSK_PATH_MOVE:
+ if (stroke_data->has_current_point)
+ cap_and_connect_contours (stroke_data);
+
+ gsk_curve_init_foreach (&curve,
+ GSK_PATH_LINE,
+ (const graphene_point_t[]) { pts[0], GRAPHENE_POINT_INIT (pts[0].x + 1,
pts[0].y) },
+ 2, 0.f);
+ gsk_curve_offset (&curve, stroke_data->stroke->line_width / 2, &stroke_data->r0);
+ gsk_curve_offset (&curve, - stroke_data->stroke->line_width / 2, &stroke_data->l0);
+
+ stroke_data->right = gsk_path_builder_new ();
+ stroke_data->left = gsk_path_builder_new ();
+
+ stroke_data->has_current_point = TRUE;
+ stroke_data->has_current_curve = FALSE;
+ break;
+
+ case GSK_PATH_CLOSE:
+ if (stroke_data->has_current_point)
+ {
+ if (!graphene_point_near (&pts[0], &pts[1], 0.001))
+ {
+ gsk_curve_init_foreach (&curve, GSK_PATH_LINE, pts, n_pts, weight);
+ add_curve (stroke_data, &curve);
+ }
+ close_contours (stroke_data);
+ }
+
+ stroke_data->has_current_point = FALSE;
+ stroke_data->has_current_curve = FALSE;
+ break;
+
+ case GSK_PATH_LINE:
+ gsk_curve_init_foreach (&curve, op, pts, n_pts, weight);
+ add_curve (stroke_data, &curve);
+ break;
+
+ case GSK_PATH_CURVE:
+ gsk_curve_init_foreach (&curve, op, pts, n_pts, weight);
+ subdivide_and_add_curve (stroke_data, &curve, MAX_SUBDIVISION);
+ break;
+
+ case GSK_PATH_CONIC:
+ gsk_curve_init_foreach (&curve, op, pts, n_pts, weight);
+ subdivide_and_add_conic (stroke_data, &curve, MAX_SUBDIVISION);
+ break;
+
+ default:
+ g_assert_not_reached ();
+ }
+
+ return TRUE;
+}
+
+/*
+ * gsk_contour_default_add_stroke:
+ * @contour: the GskContour to stroke
+ * @builder: a GskPathBuilder to add the results to
+ * @stroke: stroke parameters
+ *
+ * Strokes @contour according to the parameters given in @stroke,
+ * and adds the resulting curves to @builder. Note that stroking
+ * a contour will in general produce multiple contours - either
+ * because @contour is closed and has a left and right outline,
+ * or because @stroke requires dashes.
+ */
+void
+gsk_contour_default_add_stroke (const GskContour *contour,
+ GskPathBuilder *builder,
+ GskStroke *stroke)
+{
+ StrokeData stroke_data;
+
+ memset (&stroke_data, 0, sizeof (StrokeData));
+ stroke_data.builder = builder;
+ stroke_data.stroke = stroke;
+
+#ifdef STROKE_DEBUG
+ stroke_data.debug = gsk_path_builder_new ();
+#endif
+
+ if (stroke->dash_length <= 0)
+ gsk_contour_foreach (contour, GSK_PATH_TOLERANCE_DEFAULT, stroke_op, &stroke_data);
+ else
+ gsk_contour_dash (contour, stroke, GSK_PATH_TOLERANCE_DEFAULT, stroke_op, &stroke_data);
+
+ if (stroke_data.has_current_point)
+ cap_and_connect_contours (&stroke_data);
+
+#ifdef STROKE_DEBUG
+ GskPath *path = gsk_path_builder_free_to_path (stroke_data.debug);
+ gsk_path_builder_add_path (builder, path);
+ gsk_path_unref (path);
+#endif
+}
+
+/* vim:set foldmethod=marker expandtab: */
diff --git a/gsk/meson.build b/gsk/meson.build
index 4f28b03d73..6ba45c6eff 100644
--- a/gsk/meson.build
+++ b/gsk/meson.build
@@ -28,6 +28,7 @@ gsk_public_sources = files([
'gskpathbuilder.c',
'gskpathdash.c',
'gskpathmeasure.c',
+ 'gskpathstroke.c',
'gskrenderer.c',
'gskrendernode.c',
'gskrendernodeimpl.c',
diff --git a/testsuite/gsk/meson.build b/testsuite/gsk/meson.build
index 2efe5f70ed..aa7a663263 100644
--- a/testsuite/gsk/meson.build
+++ b/testsuite/gsk/meson.build
@@ -199,6 +199,7 @@ tests = [
['curve-performance', ['../../gsk/gskcurve.c', '../../gsk/gskcurveintersect.c'], ['-DGTK_COMPILATION']],
['path'],
['path-special-cases'],
+ ['path-stroke'],
['rounded-rect'],
['transform'],
['shader'],
diff --git a/testsuite/gsk/path-stroke.c b/testsuite/gsk/path-stroke.c
new file mode 100644
index 0000000000..bf40707f59
--- /dev/null
+++ b/testsuite/gsk/path-stroke.c
@@ -0,0 +1,67 @@
+/*
+ * Copyright © 2020 Red Hat, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors: Matthias Clasen <mclasen redhat com>
+ */
+
+#include <gtk/gtk.h>
+
+/* Test that single-point contours don't crash the stroker */
+static void
+test_point_to_stroke (void)
+{
+ GskPathBuilder *builder;
+ GskPath *path;
+ GskStroke *stroke;
+ GskPath *path1;
+ char *string;
+
+ builder = gsk_path_builder_new ();
+ gsk_path_builder_move_to (builder, 100, 100);
+ gsk_path_builder_curve_to (builder, 190, 110,
+ 200, 120,
+ 210, 210);
+ gsk_path_builder_curve_to (builder, 220, 210,
+ 230, 200,
+ 230, 100);
+ gsk_path_builder_move_to (builder, 200, 200);
+
+ path = gsk_path_builder_free_to_path (builder);
+
+ string = gsk_path_to_string (path);
+ g_assert_cmpstr (string, ==, "M 100 100 C 190 110, 200 120, 210 210 C 220 210, 230 200, 230 100 M 200
200");
+ g_free (string);
+
+ stroke = gsk_stroke_new (20.f);
+ path1 = gsk_path_stroke (path, stroke);
+ gsk_stroke_free (stroke);
+
+ g_assert_nonnull (path1);
+ gsk_path_unref (path1);
+
+ gsk_path_unref (path);
+}
+
+int
+main (int argc,
+ char *argv[])
+{
+ gtk_test_init (&argc, &argv, NULL);
+
+ g_test_add_func ("/path/point_to_stroke", test_point_to_stroke);
+
+ return g_test_run ();
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
