[gtk/curve-ops: 16/22] Add gsk_curve_get_bounds

[Matthias Clasen <matthiasc src gnome org>]

commit 93e736db8fffb28e61f41293d55990486ab2149d
Author: Matthias Clasen <mclasen redhat com>
Date:   Mon Dec 7 01:22:39 2020 -0500

    Add gsk_curve_get_bounds
    
    Add getters for bounding boxes of curves.

 gsk/gskcurve.c        | 206 +++++++++++++++++++++++++++++++++++++++++++++++++-
 gsk/gskcurveprivate.h |   6 +-
 2 files changed, 207 insertions(+), 5 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index dce05eeca0..eb6317b060 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -54,6 +54,10 @@ struct _GskCurveClass
                                                          graphene_vec2_t        *tangent);
   void                          (* get_end_tangent)     (const GskCurve         *curve,
                                                          graphene_vec2_t        *tangent);
+  void                          (* get_bounds)          (const GskCurve         *curve,
+                                                         graphene_rect_t        *bounds);
+  void                          (* get_tight_bounds)    (const GskCurve         *curve,
+                                                         graphene_rect_t        *bounds);
 };
 
 static void
@@ -184,6 +188,17 @@ gsk_line_curve_get_start_end_tangent (const GskCurve  *curve,
   get_tangent (&self->points[0], &self->points[1], tangent);
 }
 
+static void
+gsk_line_curve_get_bounds (const GskCurve  *curve,
+                           graphene_rect_t *bounds)
+{
+  const GskLineCurve *self = &curve->line;
+  const graphene_point_t *pts = self->points;
+
+  graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
+  graphene_rect_expand (bounds, &pts[1], bounds);
+}
+
 static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_init,
   gsk_line_curve_get_point,
@@ -195,7 +210,9 @@ static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_get_start_point,
   gsk_line_curve_get_end_point,
   gsk_line_curve_get_start_end_tangent,
-  gsk_line_curve_get_start_end_tangent
+  gsk_line_curve_get_start_end_tangent,
+  gsk_line_curve_get_bounds,
+  gsk_line_curve_get_bounds
 };
 
 /** CURVE **/
@@ -397,6 +414,93 @@ gsk_curve_curve_get_end_tangent (const GskCurve  *curve,
   get_tangent (&self->points[2], &self->points[3], tangent);
 }
 
+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;
+
+  graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
+  graphene_rect_expand (bounds, &pts[1], bounds);
+  graphene_rect_expand (bounds, &pts[2], bounds);
+  graphene_rect_expand (bounds, &pts[3], bounds);
+}
+
+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_tight_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_get_point (curve, t[i], &p);
+      graphene_rect_expand (bounds, &p, bounds);
+    }
+}
+
 static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_init,
   gsk_curve_curve_get_point,
@@ -408,7 +512,9 @@ static const GskCurveClass GSK_CURVE_CURVE_CLASS = {
   gsk_curve_curve_get_start_point,
   gsk_curve_curve_get_end_point,
   gsk_curve_curve_get_start_tangent,
-  gsk_curve_curve_get_end_tangent
+  gsk_curve_curve_get_end_tangent,
+  gsk_curve_curve_get_bounds,
+  gsk_curve_curve_get_tight_bounds
 };
 
 /** CONIC **/
@@ -780,6 +886,84 @@ gsk_conic_curve_get_end_tangent (const GskCurve  *curve,
   get_tangent (&self->points[1], &self->points[3], tangent);
 }
 
+static void
+gsk_conic_curve_get_bounds (const GskCurve  *curve,
+                            graphene_rect_t *bounds)
+{
+  const GskCurveCurve *self = &curve->curve;
+  const graphene_point_t *pts = self->points;
+
+  graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
+  graphene_rect_expand (bounds, &pts[1], bounds);
+  graphene_rect_expand (bounds, &pts[3], bounds);
+}
+
+/* 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_tight_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_get_point (curve, t[i], &p);
+      graphene_rect_expand (bounds, &p, bounds);
+    }
+}
+
 static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_init,
   gsk_conic_curve_get_point,
@@ -791,7 +975,9 @@ static const GskCurveClass GSK_CONIC_CURVE_CLASS = {
   gsk_conic_curve_get_start_point,
   gsk_conic_curve_get_end_point,
   gsk_conic_curve_get_start_tangent,
-  gsk_conic_curve_get_end_tangent
+  gsk_conic_curve_get_end_tangent,
+  gsk_conic_curve_get_bounds,
+  gsk_conic_curve_get_tight_bounds
 };
 
 /** API **/
@@ -892,3 +1078,17 @@ gsk_curve_get_end_tangent (const GskCurve  *curve,
 {
   get_class (curve->op)->get_end_tangent (curve, tangent);
 }
+
+void
+gsk_curve_get_bounds (const GskCurve  *curve,
+                      graphene_rect_t *bounds)
+{
+  get_class (curve->op)->get_bounds (curve, bounds);
+}
+
+void
+gsk_curve_get_tight_bounds (const GskCurve  *curve,
+                            graphene_rect_t *bounds)
+{
+  get_class (curve->op)->get_tight_bounds (curve, bounds);
+}
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index d01f520f07..571c7a7805 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -108,8 +108,10 @@ void                    gsk_curve_get_start_tangent             (const GskCurve
                                                                  graphene_vec2_t        *tangent);
 void                    gsk_curve_get_end_tangent               (const GskCurve         *curve,
                                                                  graphene_vec2_t        *tangent);
-
-
+void                    gsk_curve_get_bounds                    (const GskCurve         *curve,
+                                                                 graphene_rect_t        *bounds);
+void                    gsk_curve_get_tight_bounds              (const GskCurve         *curve,
+                                                                 graphene_rect_t        *bounds);
 
 
 G_END_DECLS