[gtk/curve-ops: 8/10] Implement gsk_conic_curve_split

[Matthias Clasen <matthiasc src gnome org>]

commit b36234854a411bc7fe7dd3531adf861deb9661a7
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Dec 6 22:09:48 2020 -0500

    Implement gsk_conic_curve_split
    
    This will be used in finding intersections of curves.

 gsk/gskcurve.c        | 94 +++++++++++++++++++++++++++++++++++++++++++++++++--
 gsk/gskcurveprivate.h |  6 ++++
 2 files changed, 98 insertions(+), 2 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index 1523f07362..e45851cadb 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -586,14 +586,104 @@ gsk_conic_curve_eval (const GskCurve   *curve,
     }
 }
 
+static void
+split_bezier3d_recurse (const graphene_point3d_t *p,
+                        int                       l,
+                        float                     t,
+                        graphene_point3d_t       *left,
+                        graphene_point3d_t       *right,
+                        int                      *lpos,
+                        int                      *rpos)
+{
+  if (l == 1)
+    {
+      left[*lpos] = p[0];
+      right[*rpos] = p[0];
+    }
+  else
+    {
+      graphene_point3d_t *np;
+      int i;
+
+      np = g_alloca (sizeof (graphene_point3d_t) * (l - 1));
+      for (i = 0; i < l - 1; i++)
+        {
+          if (i == 0)
+            {
+              left[*lpos] = p[i];
+              (*lpos)++;
+            }
+          if (i + 1 == l - 1)
+            {
+              right[*rpos] = p[i + 1];
+              (*rpos)--;
+            }
+          graphene_point3d_interpolate (&p[i], &p[i + 1], t, &np[i]);
+        }
+      split_bezier3d_recurse (np, l - 1, t, left, right, lpos, rpos);
+    }
+}
+
+static void
+split_bezier3d (const graphene_point3d_t *p,
+                int                       l,
+                float                     t,
+                graphene_point3d_t       *left,
+                graphene_point3d_t       *right)
+{
+  int lpos = 0;
+  int rpos = l - 1;
+  split_bezier3d_recurse (p, l, t, left, right, &lpos, &rpos);
+}
+
 static void
 gsk_conic_curve_split (const GskCurve   *curve,
                        float             progress,
                        GskCurve         *start,
                        GskCurve         *end)
 {
-  //const GskConicCurve *self = &curve->conic;
-  g_warning ("FIXME: Stop treating conics as lines");
+  const GskConicCurve *self = &curve->conic;
+  graphene_point3d_t p[3];
+  graphene_point3d_t l[3], r[3];
+  graphene_point_t left[4], right[4];
+  float w;
+
+  /* do de Casteljau in homogeneous coordinates... */
+  w = self->points[2].x;
+  p[0] = GRAPHENE_POINT3D_INIT (self->points[0].x, self->points[0].y, 1);
+  p[1] = GRAPHENE_POINT3D_INIT (self->points[1].x * w, self->points[1].y * w, w);
+  p[2] = GRAPHENE_POINT3D_INIT (self->points[3].x, self->points[3].y, 1);
+
+  split_bezier3d (p, 3, progress, l, r);
+
+  /* then project the control points down */
+  left[0] = GRAPHENE_POINT_INIT (l[0].x / l[0].z, l[0].y / l[0].z);
+  left[1] = GRAPHENE_POINT_INIT (l[1].x / l[1].z, l[1].y / l[1].z);
+  left[3] = GRAPHENE_POINT_INIT (l[2].x / l[2].z, l[2].y / l[2].z);
+
+  right[0] = GRAPHENE_POINT_INIT (r[0].x / r[0].z, r[0].y / r[0].z);
+  right[1] = GRAPHENE_POINT_INIT (r[1].x / r[1].z, r[1].y / r[1].z);
+  right[3] = GRAPHENE_POINT_INIT (r[2].x / r[2].z, r[2].y / r[2].z);
+
+  /* normalize the outer weights to be 1 by using
+   * the fact that weights w_i and c*w_i are equivalent
+   * for any nonzero constant c
+   */
+  for (int i = 0; i < 3; i++)
+    {
+      l[i].z /= l[0].z;
+      r[i].z /= r[2].z;
+    }
+
+  /* normalize the inner weight to be 1 by using
+   * the fact that w_0*w_2/w_1^2 is a constant for
+   * all equivalent weights.
+   */
+  left[2] = GRAPHENE_POINT_INIT (l[1].z / sqrt (l[2].z), 0);
+  right[2] = GRAPHENE_POINT_INIT (r[1].z / sqrt (r[0].z), 0);
+
+  gsk_curve_init (start, gsk_pathop_encode (GSK_PATH_CONIC, left));
+  gsk_curve_init (end, gsk_pathop_encode (GSK_PATH_CONIC, right));
 }
 
 /* taken from Skia, including the very descriptive name */
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index 838841ad68..56d2864d24 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -107,6 +107,12 @@ void                    gsk_curve_get_bounds                    (const GskCurve
 void                    gsk_curve_get_tight_bounds              (const GskCurve         *curve,
                                                                  graphene_rect_t        *bounds);
 
+int                     gsk_curve_intersect                     (const GskCurve         *curve1,
+                                                                 const GskCurve         *curve2,
+                                                                 float                  *t1,
+                                                                 float                  *t2,
+                                                                 graphene_point_t       *p,
+                                                                 int                     n);
 
 G_END_DECLS