[gtk/wip/matthiasc/lottie-stroke: 8/10] wip: Subdivide curves before stroking

[Matthias Clasen <matthiasc src gnome org>]

commit d7290fafcd91198fcd63372700258cb705c777bb
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Nov 29 22:01:57 2020 -0500

    wip: Subdivide curves before stroking

 gsk/gskpathstroke.c | 129 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 128 insertions(+), 1 deletion(-)
---
diff --git a/gsk/gskpathstroke.c b/gsk/gskpathstroke.c
index 86c84ba23b..2761d963dd 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,
@@ -844,6 +891,83 @@ 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;
+
+  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;
+
+  for (i = 0; i < n; i++)
+    {
+      graphene_point_t left[4];
+      graphene_point_t right[4];
+      float t;
+
+      t = pos[i];
+      if (t < 0.1 || t > 0.9)
+        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] / (1 - pos[i]);
+    }
+
+  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 +989,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: