[gtk/curve-ops: 5/10] Add gsk_curve_get_tight_bounds

[Matthias Clasen <matthiasc src gnome org>]

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

    Add gsk_curve_get_tight_bounds
    
    Add a way to get a tight bounding box for the various
    types of curves we use.
    
    This will be used in finding intersections.

 gsk/gskcurve.c        | 170 ++++++++++++++++++++++++++++++++++++++++++++++++--
 gsk/gskcurveprivate.h |   3 +-
 2 files changed, 168 insertions(+), 5 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index ceaeafc1ae..3d5f3e2397 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -48,6 +48,8 @@ struct _GskCurveClass
                                                          graphene_vec2_t        *tangent);
   void                          (* get_end_tangent)     (const GskCurve         *curve,
                                                          graphene_vec2_t        *tangent);
+  void                          (* get_tight_bounds)    (const GskCurve         *curve,
+                                                         graphene_rect_t        *bounds);
 };
 
 /** LINE **/
@@ -161,6 +163,16 @@ gsk_line_curve_get_tangent (const GskCurve  *curve,
   return 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;
+
+  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,
@@ -170,7 +182,8 @@ static const GskCurveClass GSK_LINE_CURVE_CLASS = {
   gsk_line_curve_get_start_point,
   gsk_line_curve_get_end_point,
   gsk_line_curve_get_tangent,
-  gsk_line_curve_get_tangent
+  gsk_line_curve_get_tangent,
+  gsk_line_curve_get_bounds
 };
 
 /** CURVE **/
@@ -183,7 +196,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)
@@ -353,6 +366,80 @@ gsk_curve_curve_get_end_tangent (const GskCurve  *curve,
   return get_tangent (&self->points[2], &self->points[3], tangent);
 }
 
+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_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,
@@ -362,7 +449,8 @@ 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_tight_bounds
 };
 
 /** CONIC **/
@@ -594,6 +682,72 @@ gsk_conic_curve_get_end_tangent (const GskCurve  *curve,
   return get_tangent (&self->points[1], &self->points[3], tangent);
 }
 
+/* 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_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,
@@ -603,7 +757,8 @@ 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_tight_bounds
 };
 
 /** API **/
@@ -688,3 +843,10 @@ gsk_curve_get_end_tangent (const GskCurve  *curve,
 {
   get_class (curve->op)->get_end_tangent (curve, tangent);
 }
+
+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 0f4e89d2c5..a64e8ce736 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -103,7 +103,8 @@ void                    gsk_curve_get_start_tangent             (const GskCurve
 void                    gsk_curve_get_end_tangent               (const GskCurve         *curve,
                                                                  graphene_vec2_t        *tangent);
 
-
+void                    gsk_curve_get_tight_bounds              (const GskCurve         *curve,
+                                                                 graphene_rect_t        *bounds);
 
 
 G_END_DECLS