[gtk/wip/matthiasc/lottie-stroke: 55/60] wip: Subdivide curves before stroking
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/matthiasc/lottie-stroke: 55/60] wip: Subdivide curves before stroking
- Date: Mon, 30 Nov 2020 19:40:20 +0000 (UTC)
commit de5434885ce93e6b5a2283abb47d2a22c0fb309f
Author: Matthias Clasen <mclasen redhat com>
Date: Sun Nov 29 22:01:57 2020 -0500
wip: Subdivide curves before stroking
gsk/gskpathstroke.c | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 169 insertions(+), 2 deletions(-)
---
diff --git a/gsk/gskpathstroke.c b/gsk/gskpathstroke.c
index 86c84ba23b..21c71c3dbb 100644
--- a/gsk/gskpathstroke.c
+++ b/gsk/gskpathstroke.c
@@ -151,6 +151,29 @@ three_point_angle (const graphene_point_t *a,
return RAD_TO_DEG (angle);
}
+static gboolean
+cubic_is_simple (const graphene_point_t *pts)
+{
+ float a1, a2, s;
+ graphene_vec2_t n1, n2;
+
+ a1 = three_point_angle (&pts[0], &pts[1], &pts[2]);
+ a2 = three_point_angle (&pts[1], &pts[2], &pts[3]);
+
+ if ((a1 < 180.f && a2 > 180.f) || (a1 > 180.f && a2 < 180.f))
+ return FALSE;
+
+ normal_vector (&pts[0], &pts[1], &n1);
+ normal_vector (&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
acceptable (float t)
{
@@ -307,6 +330,30 @@ get_cubic_extrema (float pa,
return n_roots;
}
+static int
+get_cubic_inflections (float pa,
+ float pb,
+ float pc,
+ float pd,
+ float roots[1])
+{
+ float a, b;
+ float t;
+ int n_roots = 0;
+
+ a = 3 * (pd - 3*pc + 3*pb - pa);
+ b = 6 * (pc - 2*pb + pa);
+
+ if (fabs (a) > 0.0001)
+ {
+ t = -b / (2 * a);
+ if (acceptable (t))
+ roots[n_roots++] = t;
+ }
+
+ return n_roots;
+}
+
/* Compute q = p + d * n */
static void
scale_point (const graphene_point_t *p,
@@ -823,7 +870,7 @@ path_op_data_new (GskPathOperation op,
d->pts[i] = pts[i];
d->n_pts = n_pts;
-#if 1
+#if 0
/* detect uninitialized values */
for (i = 0; i < n_pts; i++)
d->l[i].x = d->l[i].y = d->r[i].x = d->r[i].y = NAN;
@@ -844,6 +891,91 @@ typedef struct
graphene_point_t *start;
} AddOpData;
+static int
+compare_pos (const void *p1, const void *p2)
+{
+ const float *f1 = p1;
+ const float *f2 = p2;
+ return f1 < f2 ? -1 : (f1 > f2 ? 1 : 0);
+}
+
+static void
+subdivide_and_add (const graphene_point_t pts[4],
+ AddOpData *data)
+{
+ float pos[8];
+ int i, k, n = 0;
+ GList *l, *pass1 = NULL;
+ graphene_point_t p[4];
+ graphene_point_t *segment;
+ float t0, t1;
+
+ n += get_cubic_extrema (pts[0].x, pts[1].x, pts[2].x, pts[3].x, &pos[n]);
+ n += get_cubic_extrema (pts[0].y, pts[1].y, pts[2].y, pts[3].y, &pos[n]);
+ n += get_cubic_inflections (pts[0].x, pts[1].x, pts[2].x, pts[3].x, &pos[n]);
+ n += get_cubic_inflections (pts[0].y, pts[1].y, pts[2].y, pts[3].y, &pos[n]);
+
+ qsort (pos, n, sizeof (float), compare_pos);
+
+ for (i = 0; i < 4; i++)
+ p[i] = pts[i];
+
+ pass1 = NULL;
+
+#if 0
+ t0 = 0.1;
+ t1 = 0.9;
+ for (i = 0; i < n; i++)
+ {
+ graphene_point_t left[4];
+ graphene_point_t right[4];
+ float t;
+
+ t = pos[i];
+ if (t < t0 || t > t1)
+ continue;
+
+ split_bezier (p, 4, t, left, right);
+
+ segment = g_new (graphene_point_t, 4);
+ memcpy (segment, left, sizeof (graphene_point_t) * 4);
+ pass1 = g_list_append (pass1, segment);
+
+ for (k = 0; k < 4; k++)
+ p[k] = right[k];
+
+ for (k = i + 1; k < n; k++)
+ pos[k] = (pos[k] - pos[i]) / (1 - pos[i]);
+
+ t0 = 0;
+ t1 = (t1 - pos[i]) / (1 - pos[i]);
+ }
+#endif
+
+ segment = g_new (graphene_point_t, 4);
+ memcpy (segment, pts, sizeof (graphene_point_t) * 4);
+ pass1 = g_list_append (pass1, segment);
+
+ for (l = pass1; l; l = l->next)
+ {
+ segment = l->data;
+ if (cubic_is_simple (segment))
+ data->ops = g_list_prepend (data->ops, path_op_data_new (GSK_PATH_CURVE, segment, 4));
+ else
+ {
+ graphene_point_t left[4];
+ graphene_point_t right[4];
+
+ split_bezier (segment, 4, 0.5, left, right);
+
+ data->ops = g_list_prepend (data->ops, path_op_data_new (GSK_PATH_CURVE, left, 4));
+ data->ops = g_list_prepend (data->ops, path_op_data_new (GSK_PATH_CURVE, right, 4));
+ }
+ }
+
+ g_list_free_full (pass1, g_free);
+}
+
static gboolean
add_op_to_list (GskPathOperation op,
const graphene_point_t *pts,
@@ -865,7 +997,10 @@ add_op_to_list (GskPathOperation op,
break;
case GSK_PATH_CURVE:
- data->ops = g_list_prepend (data->ops, path_op_data_new (op, pts, n_pts));
+ if (g_getenv ("SUBDIVIDE"))
+ subdivide_and_add (pts, data);
+ else
+ data->ops = g_list_prepend (data->ops, path_op_data_new (op, pts, n_pts));
break;
case GSK_PATH_CONIC:
@@ -1092,6 +1227,38 @@ gsk_contour_to_stroke (const GskContour *contour,
}
}
+#if 0
+ /* Subdivide */
+ sops = NULL;
+ for (l = ops; l; l = l->next)
+ {
+ op = l->data;
+
+ switch (op->op)
+ {
+ case GSK_PATH_MOVE:
+ g_assert_not_reached ();
+ break;
+
+ case GSK_PATH_LINE:
+ case GSK_PATH_CLOSE:
+ sops = g_list_prepend (sops, op);
+ break;
+
+ case GSK_PATH_CURVE:
+ subdivide_and_add (op, &sops);
+ g_free (op);
+ break;
+
+ default:
+ g_assert_not_reached ();
+ }
+ }
+
+ g_list_free (ops);
+ ops = g_list_reverse (sops);
+#endif
+
for (l = ops; l; l = l->next)
{
int i;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]