[gtk/path-work-rebased: 32/71] curve: Add gsk_curve_decompose_curve

[Matthias Clasen <matthiasc src gnome org>]

commit a9c36f8ba9bc5139bac60670fe6f955bb5c84aa5
Author: Matthias Clasen <mclasen redhat com>
Date:   Wed Dec 9 17:46:31 2020 -0500

    curve: Add gsk_curve_decompose_curve
    
    This is mainly useful for decomposing a conic into
    cubics. The criterion here for terminating the
    subdivision is very improvised.

 gsk/gskcurve.c        | 128 ++++++++++++++++++++++++++++++++++++++++++++++++++
 gsk/gskcurveprivate.h |   7 +++
 2 files changed, 135 insertions(+)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index 32431f9dc4..06b6fce81a 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -52,6 +52,10 @@ struct _GskCurveClass
                                                          float                   tolerance,
                                                          GskCurveAddLineFunc     add_line_func,
                                                          gpointer                user_data);
+  gboolean                      (* decompose_curve)     (const GskCurve         *curve,
+                                                         float                   tolerance,
+                                                         GskCurveAddCurveFunc    add_curve_func,
+                                                         gpointer                user_data);
   gskpathop                     (* pathop)              (const GskCurve         *curve);
   const graphene_point_t *      (* get_start_point)     (const GskCurve         *curve);
   const graphene_point_t *      (* get_end_point)       (const GskCurve         *curve);
@@ -174,6 +178,23 @@ gsk_line_curve_decompose (const GskCurve      *curve,
   return add_line_func (&self->points[0], &self->points[1], 0.0f, 1.0f, user_data);
 }
 
+static gboolean
+gsk_line_curve_decompose_curve (const GskCurve       *curve,
+                                float                 tolerance,
+                                GskCurveAddCurveFunc  add_curve_func,
+                                gpointer              user_data)
+{
+  const GskLineCurve *self = &curve->line;
+  graphene_point_t p[4];
+
+  p[0] = self->points[0];
+  p[3] = self->points[1];
+  graphene_point_interpolate (&p[0], &p[3], 1/3.0, &p[1]);
+  graphene_point_interpolate (&p[0], &p[3], 2/3.0, &p[2]);
+
+  return add_curve_func (p, user_data);
+}
+
 static gskpathop
 gsk_line_curve_pathop (const GskCurve *curve)
 {
@@ -225,6 +246,7 @@ static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_split,
   gsk_line_curve_segment,
   gsk_line_curve_decompose,
+  gsk_line_curve_decompose_curve,
   gsk_line_curve_pathop,
   gsk_line_curve_get_start_point,
   gsk_line_curve_get_end_point,
@@ -406,6 +428,17 @@ gsk_curve_curve_decompose (const GskCurve      *curve,
   return gsk_curce_curve_decompose_step (curve, 0.0, 1.0, tolerance, add_line_func, user_data);
 }
 
+static gboolean
+gsk_curve_curve_decompose_curve (const GskCurve       *curve,
+                                 float                 tolerance,
+                                 GskCurveAddCurveFunc  add_curve_func,
+                                 gpointer              user_data)
+{
+  const GskCurveCurve *self = &curve->curve;
+
+  return add_curve_func (self->points, user_data);
+}
+
 static gskpathop
 gsk_curve_curve_pathop (const GskCurve *curve)
 {
@@ -541,6 +574,7 @@ static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_split,
   gsk_curve_curve_segment,
   gsk_curve_curve_decompose,
+  gsk_curve_curve_decompose_curve,
   gsk_curve_curve_pathop,
   gsk_curve_curve_get_start_point,
   gsk_curve_curve_get_end_point,
@@ -909,6 +943,90 @@ gsk_conic_curve_decompose (const GskCurve      *curve,
                                               user_data);
 }
 
+/* See Floater, M: An analysis of cubic approximation schemes
+ * for conic sections
+ */
+static void
+cubic_approximation (const GskCurve *curve,
+                     GskCurve       *cubic)
+{
+  const GskConicCurve *self = &curve->conic;
+  graphene_point_t p[4];
+  float w = self->points[2].x;
+  float w2 = w*w;
+  float lambda;
+
+  lambda = 2 * (6*w2 + 1 - sqrt (3*w2 + 1)) / (12*w2 + 3);
+
+  p[0] = self->points[0];
+  p[3] = self->points[3];
+  graphene_point_interpolate (&self->points[0], &self->points[1], lambda, &p[1]);
+  graphene_point_interpolate (&self->points[3], &self->points[1], lambda, &p[2]);
+
+  gsk_curve_init (cubic, gsk_pathop_encode (GSK_PATH_CURVE, p));
+}
+
+static gboolean
+gsk_conic_is_close_to_cubic (const GskCurve *conic,
+                             const GskCurve *cubic,
+                             float           tolerance)
+{
+  float t[] = { 0.1, 0.5, 0.9 };
+  graphene_point_t p0, p1;
+
+  for (int i = 0; i < G_N_ELEMENTS (t); i++)
+    {
+      gsk_curve_get_point (conic, t[i], &p0);
+      gsk_curve_get_point (cubic, t[i], &p1);
+      if (graphene_point_distance (&p0, &p1, NULL, NULL) > tolerance)
+        return FALSE;
+    }
+
+  return TRUE;
+}
+
+static gboolean gsk_conic_curve_decompose_curve (const GskCurve       *curve,
+                                                 float                 tolerance,
+                                                 GskCurveAddCurveFunc  add_curve_func,
+                                                 gpointer              user_data);
+
+static gboolean
+gsk_conic_curve_decompose_or_add (const GskCurve       *curve,
+                                  const GskCurve       *cubic,
+                                  float                 tolerance,
+                                  GskCurveAddCurveFunc  add_curve_func,
+                                  gpointer              user_data)
+{
+  if (gsk_conic_is_close_to_cubic (curve, cubic, tolerance))
+    return add_curve_func (cubic->curve.points, user_data);
+  else
+    {
+      GskCurve c1, c2;
+      GskCurve cc1, cc2;
+
+      gsk_conic_curve_split (curve, 0.5, &c1, &c2);
+
+      cubic_approximation (&c1, &cc1);
+      cubic_approximation (&c2, &cc2);
+
+      return gsk_conic_curve_decompose_or_add (&c1, &cc1, tolerance, add_curve_func, user_data) &&
+             gsk_conic_curve_decompose_or_add (&c2, &cc2, tolerance, add_curve_func, user_data);
+    }
+}
+
+static gboolean
+gsk_conic_curve_decompose_curve (const GskCurve       *curve,
+                                 float                 tolerance,
+                                 GskCurveAddCurveFunc  add_curve_func,
+                                 gpointer              user_data)
+{
+  GskCurve c;
+
+  cubic_approximation (curve, &c);
+
+  return gsk_conic_curve_decompose_or_add (curve, &c, tolerance, add_curve_func, user_data);
+}
+
 static gskpathop
 gsk_conic_curve_pathop (const GskCurve *curve)
 {
@@ -1035,6 +1153,7 @@ static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_split,
   gsk_conic_curve_segment,
   gsk_conic_curve_decompose,
+  gsk_conic_curve_decompose_curve,
   gsk_conic_curve_pathop,
   gsk_conic_curve_get_start_point,
   gsk_conic_curve_get_end_point,
@@ -1128,6 +1247,15 @@ gsk_curve_decompose (const GskCurve      *curve,
   return get_class (curve->op)->decompose (curve, tolerance, add_line_func, user_data);
 }
 
+gboolean
+gsk_curve_decompose_curve (const GskCurve       *curve,
+                           float                 tolerance,
+                           GskCurveAddCurveFunc  add_curve_func,
+                           gpointer              user_data)
+{
+  return get_class (curve->op)->decompose_curve (curve, tolerance, add_curve_func, user_data);
+}
+
 gskpathop
 gsk_curve_pathop (const GskCurve *curve)
 {
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index f2d9659449..e194f52886 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -83,6 +83,9 @@ typedef gboolean (* GskCurveAddLineFunc) (const graphene_point_t *from,
                                           float                   to_progress,
                                           gpointer                user_data);
 
+typedef gboolean (* GskCurveAddCurveFunc) (const graphene_point_t points[4],
+                                           gpointer                user_data);
+
 void                    gsk_curve_init                          (GskCurve               *curve,
                                                                  gskpathop               op);
 void                    gsk_curve_init_foreach                  (GskCurve               *curve,
@@ -109,6 +112,10 @@ gboolean                gsk_curve_decompose                     (const GskCurve
                                                                  float                   tolerance,
                                                                  GskCurveAddLineFunc     add_line_func,
                                                                  gpointer                user_data);
+gboolean                gsk_curve_decompose_curve               (const GskCurve         *curve,
+                                                                 float                   tolerance,
+                                                                 GskCurveAddCurveFunc    add_curve_func,
+                                                                 gpointer                user_data);
 gskpathop               gsk_curve_pathop                        (const GskCurve         *curve);
 #define gsk_curve_builder_to(curve, builder) gsk_path_builder_pathop_to ((builder), gsk_curve_pathop (curve))
 const graphene_point_t *gsk_curve_get_start_point               (const GskCurve         *curve);