[gtk/path-ops: 2/8] path: Implement gsk_path_simplify

[Matthias Clasen <matthiasc src gnome org>]

commit 5576ba82bb72b1403c5f57a32556dc6f549c6ae5
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Mar 20 22:01:05 2022 -0400

    path: Implement gsk_path_simplify
    
    This mostly works.
    
    Still needs some robustness fixes.

 gsk/gskpath.c         |   2 -
 gsk/gskpath.h         |   3 +
 gsk/gskpathsimplify.c | 581 ++++++++++++++++++++++++++++++++++++++++++++++++++
 gsk/meson.build       |   1 +
 4 files changed, 585 insertions(+), 2 deletions(-)
---
diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index 9f24637c0c..15e9283a79 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -1343,5 +1343,3 @@ gsk_path_offset (GskPath     *self,
 
   return gsk_path_builder_free_to_path (builder);
 }
-
-
diff --git a/gsk/gskpath.h b/gsk/gskpath.h
index 0f1ca0b804..60188009aa 100644
--- a/gsk/gskpath.h
+++ b/gsk/gskpath.h
@@ -124,6 +124,9 @@ GskPath *               gsk_path_offset                         (GskPath
                                                                  GskLineJoin             line_join,
                                                                  float                   miter_limit);
 
+GDK_AVAILABLE_IN_ALL
+GskPath *               gsk_path_simplify                       (GskPath                *self);
+
 
 G_END_DECLS
 
diff --git a/gsk/gskpathsimplify.c b/gsk/gskpathsimplify.c
new file mode 100644
index 0000000000..835eca5220
--- /dev/null
+++ b/gsk/gskpathsimplify.c
@@ -0,0 +1,581 @@
+/*
+ * Copyright © 2022 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
+ */
+
+#include "config.h"
+
+#include "gskpathprivate.h"
+
+#include "gskcurveprivate.h"
+#include "gskpathbuilder.h"
+#include "gskpathmeasure.h"
+#include "gskstrokeprivate.h"
+
+#include "gskdebugprivate.h"
+
+#include "gdk/gdk-private.h"
+
+typedef struct
+{
+  graphene_point_t p;
+  GPtrArray *edges;
+} Connection;
+
+static void
+connection_free (Connection *c)
+{
+  g_ptr_array_free (c->edges, TRUE);
+  g_free (c);
+}
+
+typedef struct
+{
+  GskCurve curve;
+  Connection *start;
+  Connection *end;
+  gboolean internal;
+  gboolean collected;
+  char *name;
+} Curve;
+
+static void
+curve_free (Curve *c)
+{
+  g_free (c->name);
+  g_free (c);
+}
+
+typedef struct
+{
+  GList *curves;
+  GList *connections;
+  Curve *start;
+} SimplifyData;
+
+static int collect_num = 0;
+
+static gboolean
+is_stationary_close (GskCurve *curve)
+{
+   return curve->op == GSK_PATH_CLOSE &&
+          graphene_point_near (&curve->line.points[0], &curve->line.points[1], 0.01);
+}
+
+static void
+merge_connections (GList      **connections,
+                   Connection  *c1,
+                   Connection  *c2)
+{
+  g_assert (graphene_point_near (&c1->p, &c2->p, 0.1));
+
+  if (c1 == c2)
+    return;
+
+  for (int i = 0; i < c2->edges->len; i++)
+    {
+      Curve *curve = g_ptr_array_index (c2->edges, i);
+      if (curve->start == c2)
+        curve->start = c1;
+      if (curve->end == c2)
+        curve->end = c1;
+      g_ptr_array_add (c1->edges, curve);
+    }
+
+  *connections = g_list_remove (*connections, c2);
+
+  connection_free (c2);
+}
+
+static gboolean
+simplify_collect_cb (GskPathOperation        op,
+                     const graphene_point_t *pts,
+                     gsize                   n_pts,
+                     float                   weight,
+                     gpointer                user_data)
+{
+  SimplifyData *data = user_data;
+  Curve *curve;
+  Connection *connection;
+  const char *opname[] = { "Move", "Close", "Line", "Curve", "Conic" };
+
+  g_assert (op != GSK_PATH_CONIC);
+
+  curve = g_new0 (Curve, 1);
+
+  if (op == GSK_PATH_MOVE)
+    {
+      if (data->curves)
+        {
+          Curve *prev = data->curves->data;
+          if (prev->curve.op == GSK_PATH_MOVE)
+            {
+              g_free (curve);
+              prev->curve.line.points[0] = pts[0];
+              prev->end->p = pts[0];
+              return TRUE;
+            }
+        }
+
+      connection = g_new (Connection, 1);
+      connection->p = pts[0];
+      connection->edges = g_ptr_array_new ();
+      data->connections = g_list_prepend (data->connections, connection);
+
+      curve->curve.op = GSK_PATH_MOVE;
+      curve->curve.line.points[0] = pts[0];
+      curve->end = connection;
+
+      data->curves = g_list_prepend (data->curves, curve);
+      data->start = curve;
+    }
+  else
+    {
+      gsk_curve_init (&curve->curve, gsk_pathop_encode (op, pts));
+
+      if (is_stationary_close (&curve->curve))
+        {
+          Curve *prev = data->curves->data;
+          merge_connections (&data->connections, data->start->end, prev->end);
+          g_free (curve);
+          return TRUE;
+        }
+
+      if (data->curves)
+        {
+          Curve *prev = data->curves->data;
+          curve->start = prev->end;
+        }
+
+      if (op == GSK_PATH_CLOSE)
+        {
+          connection = data->start->end;
+        }
+      else
+        {
+          connection = g_new (Connection, 1);
+          connection->p = *gsk_curve_get_end_point (&curve->curve);
+          connection->edges = g_ptr_array_new ();
+          data->connections = g_list_prepend (data->connections, connection);
+        }
+
+      curve->end = connection;
+
+      g_ptr_array_add (curve->start->edges, curve);
+      g_ptr_array_add (curve->end->edges, curve);
+
+      data->curves = g_list_prepend (data->curves, curve);
+    }
+
+#ifdef G_ENABLE_DEBUG
+  curve->name = g_strdup_printf ("%s %d", opname[op], collect_num++);
+#endif
+
+  return TRUE;
+}
+
+static void
+gsk_path_builder_append_curve (GskPathBuilder *builder,
+                               GskCurve       *curve)
+{
+  switch (curve->op)
+    {
+    case GSK_PATH_CLOSE:
+      gsk_path_builder_close (builder);
+      break;
+
+    case GSK_PATH_MOVE:
+      gsk_path_builder_move_to (builder, curve->line.points[0].x, curve->line.points[0].y);
+      break;
+
+    case GSK_PATH_LINE:
+      gsk_path_builder_line_to (builder, curve->line.points[1].x, curve->line.points[1].y);
+      break;
+
+    case GSK_PATH_CURVE:
+      gsk_path_builder_curve_to (builder,
+                                 curve->curve.points[1].x, curve->curve.points[1].y,
+                                 curve->curve.points[2].x, curve->curve.points[2].y,
+                                 curve->curve.points[3].x, curve->curve.points[3].y);
+      break;
+
+    case GSK_PATH_CONIC:
+      gsk_path_builder_conic_to (builder,
+                                 curve->conic.points[1].x, curve->conic.points[1].y,
+                                 curve->conic.points[2].x, curve->conic.points[2].y,
+                                 curve->conic.points[3].x);
+      break;
+
+    default:
+      g_assert_not_reached ();
+    }
+}
+
+#define NEAR(f1, f2) (fabs ((f2) - (f1)) < 1e-3)
+
+static gboolean
+curve_is_external (GskCurve       *curve,
+                   GskPathMeasure *measure)
+{
+  graphene_point_t pos, pos1, pos2;
+  graphene_vec2_t normal;
+
+  if (curve->op == GSK_PATH_MOVE || is_stationary_close (curve))
+     return TRUE;
+
+  gsk_curve_get_point (curve, 0.5, &pos);
+  gsk_curve_get_normal (curve, 0.5, &normal);
+
+  pos1.x = pos.x + 5 * graphene_vec2_get_x (&normal);
+  pos1.y = pos.y + 5 * graphene_vec2_get_y (&normal);
+  pos2.x = pos.x - 5 * graphene_vec2_get_x (&normal);
+  pos2.y = pos.y - 5 * graphene_vec2_get_y (&normal);
+
+  return gsk_path_measure_in_fill (measure, &pos1, GSK_FILL_RULE_WINDING) !=
+         gsk_path_measure_in_fill (measure, &pos2, GSK_FILL_RULE_WINDING);
+}
+
+static Curve *
+find_next (Curve *curve)
+{
+  Connection *c = curve->end;
+  Curve *next = NULL;
+
+  g_print ("at %s:\n", curve->name);
+  for (int i = 0; i < c->edges->len; i++)
+    {
+      Curve *n = g_ptr_array_index (c->edges, i);
+      g_print ("\t%s\n", n->name);
+    }
+
+  for (int i = 0; i < c->edges->len; i++)
+    {
+      Curve *n = g_ptr_array_index (c->edges, i);
+
+      if (n->collected || n->internal)
+        continue;
+
+       if (next != NULL && n->curve.op == GSK_PATH_CLOSE)
+         continue;
+
+       if (next != NULL && next->start == c)
+         continue;
+
+       if (next != NULL)
+         g_print ("Two candidates. Do the sorting dance!\n");
+
+       next = n;
+    }
+
+  return next;
+}
+
+static void
+validate_curves (GList    *curves,
+                 gboolean  split)
+{
+#ifdef G_ENABLE_DEBUG
+  Curve *start;
+
+  for (GList *l = curves; l; l = l->next)
+    {
+      Curve *c = l->data;
+
+      GSK_NOTE (PATHS,
+        g_print ("%s%s: ", c->internal ? "(" : "", c->name);
+        if (c->curve.op != GSK_PATH_MOVE)
+          gsk_curve_print (&c->curve);
+        else
+          g_print ("%g %g", c->curve.line.points[0].x, c->curve.line.points[0].y);
+        g_print ("%s\n", c->internal ? ")" : "");
+      );
+
+      if (c->curve.op == GSK_PATH_MOVE)
+        {
+          start = NULL;
+        }
+      else
+        {
+          guint pos;
+
+          if (start == NULL)
+            start = c;
+
+          g_assert (c->start != NULL);
+          g_assert (c->end != NULL);
+          g_assert (graphene_point_near (&c->start->p, gsk_curve_get_start_point (&c->curve), 0.001));
+          g_assert (graphene_point_near (&c->end->p, gsk_curve_get_end_point (&c->curve), 0.001));
+
+          if (split)
+            {
+              g_assert (c->start->edges->len % 2 == 0);
+              g_assert (c->end->edges->len % 2 == 0);
+              g_assert (c->start->edges->len >= 2);
+              g_assert (c->end->edges->len >= 2);
+            }
+          else
+            {
+              g_assert (c->start->edges->len == 2);
+              g_assert (c->end->edges->len == 2);
+            }
+
+          g_assert (g_ptr_array_find (c->start->edges, c, &pos));
+          g_assert (g_ptr_array_find (c->end->edges, c, &pos));
+
+          if (c->curve.op == GSK_PATH_CLOSE)
+            {
+              g_assert (g_ptr_array_find (c->end->edges, start, &pos));
+              g_assert (g_ptr_array_find (start->start->edges, c, &pos));
+            }
+        }
+    }
+#endif
+}
+
+static void
+g_list_insert_after (GList    *l,
+                     gpointer  data)
+{
+  GList *res G_GNUC_UNUSED;
+
+  res = g_list_insert_before (l, l->next, data);
+}
+
+/**
+ * gsk_path_simplify:
+ * @self: a `GskPath`
+ *
+ * Create a new path that describes the area as @self,
+ * without overlapping contours.
+ *
+ * Returns: a new `GskPath`
+ */
+GskPath *
+gsk_path_simplify (GskPath *self)
+{
+  SimplifyData data;
+  GskPathBuilder *builder;
+  GList *l, *ll;
+  GskPathMeasure *measure;
+  gboolean closed;
+
+  /* Special-case convex paths */
+  if (gsk_path_compute_convexity (self) == GSK_CONVEXITY_CONVEX)
+    return gsk_path_ref (self);
+
+  GSK_NOTE (PATHS, g_print ("collecting\n"));
+
+  data.curves = NULL;
+  data.connections = NULL;
+
+  collect_num = 0;
+  gsk_path_foreach (self, GSK_PATH_FOREACH_ALLOW_CURVE, simplify_collect_cb, &data);
+
+  data.curves = g_list_reverse (data.curves);
+  data.connections = g_list_reverse (data.connections);
+
+  validate_curves (data.curves, FALSE);
+
+  GSK_NOTE (PATHS, g_print ("intersecting\n"));
+  l = data.curves;
+  while (l)
+    {
+      Curve *cd1 = l->data;
+
+      while (l && (cd1->curve.op == GSK_PATH_MOVE ||
+                   is_stationary_close (&cd1->curve)))
+        {
+          l = l->next;
+          if (l)
+            cd1 = l->data;
+        }
+
+      if (!l)
+        break;
+
+      ll = l;
+      while (ll)
+        {
+          Curve *cd2 = ll->data;
+          float t1[9], t2[9];
+          graphene_point_t p [9];
+          int n;
+          GList *next;
+          Connection *connection;
+          GskCurve cs, ce;
+          Curve *cd;
+
+          while (ll && (cd2->curve.op == GSK_PATH_MOVE ||
+                        is_stationary_close (&cd2->curve)))
+            {
+              ll = ll->next;
+              if (ll)
+                cd2 = ll->data;
+            }
+
+          if (!ll)
+            break;
+
+          next = ll->next;
+
+          n = gsk_curve_intersect (&cd1->curve, &cd2->curve, t1, t2, p, sizeof (p));
+          for (int i = 0; i < n; i++)
+            {
+              if (NEAR (t1[i], 0))
+                connection = cd1->start;
+              else if (NEAR (t1[i], 1))
+                connection = cd1->end;
+              else
+                {
+                  connection = g_new0 (Connection, 1);
+                  connection->p = p[i];
+                  connection->edges = g_ptr_array_new ();
+
+                  data.connections = g_list_prepend (data.connections, connection);
+
+                  gsk_curve_split (&cd1->curve, t1[i], &cs, &ce);
+                  cd1->curve = cs;
+
+                  cd = g_new0 (Curve, 1);
+                  cd->curve = ce;
+                  cd->end = cd1->end;
+                  g_ptr_array_remove (cd->end->edges, cd1);
+                  g_ptr_array_add (cd->end->edges, cd);
+#ifdef G_ENABLE_DEBUG
+                  cd->name = g_strdup_printf ("%s.%d", cd1->name, i);
+#endif
+
+                  cd1->end = connection;
+                  cd->start = connection;
+
+                  g_list_insert_after (l, cd);
+
+                  g_ptr_array_add (connection->edges, cd1);
+                  g_ptr_array_add (connection->edges, cd);
+                }
+
+              if (NEAR (t2[i], 0))
+                merge_connections (&data.connections, connection, cd2->start);
+              else if (NEAR (t2[i], 1))
+                merge_connections (&data.connections, connection, cd2->end);
+              else
+                {
+                  gsk_curve_split (&cd2->curve, t2[i], &cs, &ce);
+                  cd2->curve = cs;
+
+                  cd = g_new0 (Curve, 1);
+                  cd->curve = ce;
+                  cd->end = cd2->end;
+                  g_ptr_array_remove (cd->end->edges, cd2);
+                  g_ptr_array_add (cd->end->edges, cd);
+#ifdef G_ENABLE_DEBUG
+                  cd->name = g_strdup_printf ("%s.%d", cd2->name, i);
+#endif
+
+                  cd2->end = connection;
+                  cd->start = connection;
+
+                  g_list_insert_after (ll, cd);
+
+                  g_ptr_array_add (connection->edges, cd2);
+                  g_ptr_array_add (connection->edges, cd);
+                }
+            }
+
+          ll = next;
+        }
+
+      l = l->next;
+    }
+
+  GSK_NOTE (PATHS, g_print ("classifying\n"));
+
+  measure = gsk_path_measure_new (self);
+
+  for (l = data.curves; l; l = l->next)
+    {
+       Curve *curve = l->data;
+
+       curve->internal = !curve_is_external (&curve->curve, measure);
+    }
+
+  gsk_path_measure_unref (measure);
+
+  validate_curves (data.curves, TRUE);
+
+  GSK_NOTE (PATHS, g_print ("reassembling\n"));
+
+  builder = gsk_path_builder_new ();
+  closed = TRUE;
+
+  for (l = data.curves; l; l = l->next)
+    {
+      Curve *curve = l->data;
+      const graphene_point_t *p;
+
+      if (curve->collected || curve->internal)
+        continue;
+
+      /* start a new contour */
+      if (!closed)
+        {
+          gsk_path_builder_close (builder);
+          closed = TRUE;
+        }
+
+      g_assert (curve->curve.op != GSK_PATH_CLOSE);
+      g_assert (!curve->internal);
+
+      GSK_NOTE (PATHS, g_print ("start new contour %s\n", curve->name));
+      if (curve->curve.op == GSK_PATH_MOVE)
+        p = &curve->curve.line.points[0];
+      else
+        p = gsk_curve_get_start_point (&curve->curve);
+      gsk_path_builder_move_to (builder, p->x, p->y);
+
+      if (curve->curve.op != GSK_PATH_MOVE)
+        gsk_path_builder_append_curve (builder, &curve->curve);
+
+      curve->collected = TRUE;
+      closed = FALSE;
+
+      /* collect segments, following through connections */
+      for (curve = find_next (curve); curve; curve = find_next (curve))
+        {
+          g_assert (!curve->internal);
+
+          if (curve->collected)
+            break;
+
+          GSK_NOTE (PATHS, g_print ("append %s\n", curve->name));
+          gsk_path_builder_append_curve (builder, &curve->curve);
+          curve->collected = TRUE;
+
+          if (curve->curve.op == GSK_PATH_CLOSE ||
+              curve->curve.op == GSK_PATH_MOVE)
+            {
+              closed = TRUE;
+              break;
+            }
+        }
+    }
+
+  g_list_free_full (data.curves, (GDestroyNotify) curve_free);
+  g_list_free_full (data.connections, (GDestroyNotify) connection_free);
+
+  return gsk_path_builder_free_to_path (builder);
+}
diff --git a/gsk/meson.build b/gsk/meson.build
index b4be720e05..5453dc6d12 100644
--- a/gsk/meson.build
+++ b/gsk/meson.build
@@ -29,6 +29,7 @@ gsk_public_sources = files([
   'gskpathbuilder.c',
   'gskpathdash.c',
   'gskpathmeasure.c',
+  'gskpathsimplify.c',
   'gskpathstroke.c',
   'gskrenderer.c',
   'gskrendernode.c',