[gtk/curve-ops: 1/2] Add gsk_curve_get_bounds

[Matthias Clasen <matthiasc src gnome org>]

commit 1c96170eb68c9220268dad7478457ddbff767711
Author: Matthias Clasen <mclasen redhat com>
Date:   Sun Dec 6 20:54:30 2020 -0500

    Add gsk_curve_get_bounds
    
    Add a way to get a bounding box for the various types
    of curves we use.

 gsk/gskcurve.c        | 163 +++++++++++++++++++++++++++++++++++++++++++++++++-
 gsk/gskcurveprivate.h |   3 +-
 2 files changed, 164 insertions(+), 2 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index fa1f1295ba..c5feef335b 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -44,6 +44,8 @@ struct _GskCurveClass
   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);
+  void                          (* get_bounds)          (const GskCurve         *curve,
+                                                         graphene_rect_t        *bounds);
 };
 
 /** LINE **/
@@ -139,6 +141,16 @@ gsk_line_curve_get_end_point (const GskCurve *curve)
   return &self->points[1];
 }
 
+static void
+gsk_line_curve_get_bounds (const GskCurve  *curve,
+                           graphene_rect_t *bounds)
+{
+  const GskLineCurve *self = &curve->line;
+
+  graphene_rect_init (bounds, self->points[0].x, self->points[0].y, 0, 0);
+  graphene_rect_expand (bounds, &self->points[1], bounds);
+}
+
 static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_init,
   gsk_line_curve_eval,
@@ -147,6 +159,7 @@ static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_pathop,
   gsk_line_curve_get_start_point,
   gsk_line_curve_get_end_point,
+  gsk_line_curve_get_bounds
 };
 
 /** CURVE **/
@@ -159,7 +172,7 @@ gsk_curve_curve_init_from_points (GskCurveCurve          *self,
   self->has_coefficients = FALSE;
   memcpy (self->points, pts, sizeof (graphene_point_t) * 4);
 }
-                                  
+
 static void
 gsk_curve_curve_init (GskCurve  *curve,
                       gskpathop  op)
@@ -311,6 +324,80 @@ gsk_curve_curve_get_end_point (const GskCurve *curve)
   return &self->points[3];
 }
 
+static inline gboolean
+acceptable (float t)
+{
+  return 0 <= t && t <= 1;
+}
+
+/* Solve P' = 0 where P is
+ * P = (1-t)^3*pa + 3*t*(1-t)^2*pb + 3*t^2*(1-t)*pc + t^3*pd
+ */
+static int
+get_cubic_extrema (float pa, float pb, float pc, float pd, float t[2])
+{
+  float a, b, c;
+  float d, tt;
+  int n = 0;
+
+  a = 3 * (pd - 3*pc + 3*pb - pa);
+  b = 6 * (pc - 2*pb + pa);
+  c = 3 * (pb - pa);
+
+  if (fabs (a) > 0.0001)
+    {
+      if (b*b > 4*a*c)
+        {
+          d = sqrt (b*b - 4*a*c);
+          tt = (-b + d)/(2*a);
+          if (acceptable (tt))
+            t[n++] = tt;
+          tt = (-b - d)/(2*a);
+          if (acceptable (tt))
+            t[n++] = tt;
+        }
+      else
+        {
+          tt = -b / (2*a);
+          if (acceptable (tt))
+            t[n++] = tt;
+        }
+    }
+  else if (fabs (b) > 0.0001)
+    {
+      tt = -c / b;
+      if (acceptable (tt))
+        t[n++] = tt;
+    }
+
+  return n;
+}
+
+static void
+gsk_curve_curve_get_bounds (const GskCurve  *curve,
+                            graphene_rect_t *bounds)
+{
+  const GskCurveCurve *self = &curve->curve;
+  const graphene_point_t *pts = self->points;
+  float t[4];
+  int n;
+
+  graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
+  graphene_rect_expand (bounds, &pts[3], bounds);
+
+  n = 0;
+  n += get_cubic_extrema (pts[0].x, pts[1].x, pts[2].x, pts[3].x, &t[n]);
+  n += get_cubic_extrema (pts[0].y, pts[1].y, pts[2].y, pts[3].y, &t[n]);
+
+  for (int i = 0; i < n; i++)
+    {
+      graphene_point_t p;
+
+      gsk_curve_curve_eval (curve, t[i], &p, NULL);
+      graphene_rect_expand (bounds, &p, bounds);
+    }
+}
+
 static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_init,
   gsk_curve_curve_eval,
@@ -319,6 +406,7 @@ static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_pathop,
   gsk_curve_curve_get_start_point,
   gsk_curve_curve_get_end_point,
+  gsk_curve_curve_get_bounds
 };
 
 /** CONIC **/
@@ -532,6 +620,72 @@ gsk_conic_curve_get_end_point (const GskCurve *curve)
   return &self->points[3];
 }
 
+/* Solve N = 0 where N is the numerator of (P/Q)', with
+ * P = (1-t)^2*a + 2*t*(1-t)*w*b + t^2*c
+ * Q = (1-t)^2 + 2*t*(1-t)*w + t^2
+ */
+static int
+get_conic_extrema (float a, float b, float c, float w, float t[4])
+{
+  float q, tt;
+  int n = 0;
+  float w2 = w*w;
+  float wac = (w - 1)*(a - c);
+
+  if (wac != 0)
+    {
+      q = - sqrt (a*a - 4*a*b*w2 + 4*a*c*w2 - 2*a*c + 4*b*b*w2 - 4*b*c*w2 + c*c);
+
+      tt = (- q + 2*a*w - a - 2*b*w + c)/(2*wac);
+
+      if (acceptable (tt))
+        t[n++] = tt;
+
+      tt = (q + 2*a*w - a - 2*b*w + c)/(2*wac);
+
+      if (acceptable (tt))
+        t[n++] = tt;
+    }
+
+  if (w * (b - c) != 0 && a == c)
+    t[n++] = 0.5;
+
+  if (w == 1 && a - 2*b + c != 0)
+    {
+      tt = (a - b) / (a - 2*b + c);
+      if (acceptable (tt))
+        t[n++] = tt;
+    }
+
+  return n;
+}
+
+static void
+gsk_conic_curve_get_bounds (const GskCurve  *curve,
+                            graphene_rect_t *bounds)
+{
+  const GskConicCurve *self = &curve->conic;
+  float w = gsk_conic_curve_get_weight (self);
+  const graphene_point_t *pts = self->points;
+  float t[8];
+  int n;
+
+  graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
+  graphene_rect_expand (bounds, &pts[3], bounds);
+
+  n = 0;
+  n += get_conic_extrema (pts[0].x, pts[1].x, pts[3].x, w, &t[n]);
+  n += get_conic_extrema (pts[0].y, pts[1].y, pts[3].y, w, &t[n]);
+
+  for (int i = 0; i < n; i++)
+    {
+      graphene_point_t p;
+
+      gsk_conic_curve_eval (curve, t[i], &p, NULL);
+      graphene_rect_expand (bounds, &p, bounds);
+    }
+}
+
 static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_init,
   gsk_conic_curve_eval,
@@ -540,6 +694,7 @@ static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_pathop,
   gsk_conic_curve_get_start_point,
   gsk_conic_curve_get_end_point,
+  gsk_conic_curve_get_bounds
 };
 
 /** API **/
@@ -611,3 +766,9 @@ gsk_curve_get_end_point (const GskCurve *curve)
   return get_class (curve->op)->get_end_point (curve);
 }
 
+void
+gsk_curve_get_bounds (const GskCurve  *curve,
+                      graphene_rect_t *bounds)
+{
+  get_class (curve->op)->get_bounds (curve, bounds);
+}
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index 720ee71f1c..746e735ecf 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -99,7 +99,8 @@ gskpathop               gsk_curve_pathop                        (const GskCurve
 const graphene_point_t *gsk_curve_get_start_point               (const GskCurve         *curve);
 const graphene_point_t *gsk_curve_get_end_point                 (const GskCurve         *curve);
 
-
+void                    gsk_curve_get_bounds                    (const GskCurve         *curve,
+                                                                 graphene_rect_t        *bounds);
 
 
 G_END_DECLS