[gtk/wip/matthiasc/lottie-stroke: 55/60] wip: Subdivide curves before stroking

[Matthias Clasen <matthiasc src gnome org>]

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;