[gtk/path-work-rebased: 27/36] curve: Use GskBoundingBox




commit cf793f94acf7694e71a2198b5ec4385ff864371a
Author: Matthias Clasen <mclasen redhat com>
Date:   Mon Mar 21 01:26:51 2022 -0400

    curve: Use GskBoundingBox

 gsk/gskcurve.c          |  49 +++++++---------
 gsk/gskcurveintersect.c |  35 ++++++-----
 gsk/gskcurveprivate.h   |   8 ++-
 testsuite/gsk/curve.c   | 150 ++++++++++++++++++++++++++++++++++++++++++++++--
 4 files changed, 188 insertions(+), 54 deletions(-)
---
diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c
index 1e6673062e..2f1894f297 100644
--- a/gsk/gskcurve.c
+++ b/gsk/gskcurve.c
@@ -64,9 +64,9 @@ struct _GskCurveClass
   void                          (* get_end_tangent)     (const GskCurve         *curve,
                                                          graphene_vec2_t        *tangent);
   void                          (* get_bounds)          (const GskCurve         *curve,
-                                                         graphene_rect_t        *bounds);
+                                                         GskBoundingBox         *bounds);
   void                          (* get_tight_bounds)    (const GskCurve         *curve,
-                                                         graphene_rect_t        *bounds);
+                                                         GskBoundingBox         *bounds);
   void                          (* offset)              (const GskCurve         *curve,
                                                          float                   distance,
                                                          GskCurve               *offset_curve);
@@ -291,13 +291,12 @@ gsk_line_curve_get_start_end_tangent (const GskCurve  *curve,
 
 static void
 gsk_line_curve_get_bounds (const GskCurve  *curve,
-                           graphene_rect_t *bounds)
+                           GskBoundingBox  *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);
+  gsk_bounding_box_init (bounds, &pts[0], &pts[1]);
 }
 
 static void
@@ -598,15 +597,14 @@ gsk_curve_curve_get_end_tangent (const GskCurve  *curve,
 
 static void
 gsk_curve_curve_get_bounds (const GskCurve  *curve,
-                            graphene_rect_t *bounds)
+                            GskBoundingBox  *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);
+  gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
+  gsk_bounding_box_expand (bounds, &pts[1]);
+  gsk_bounding_box_expand (bounds, &pts[2]);
 }
 
 static inline gboolean
@@ -660,15 +658,14 @@ get_cubic_extrema (float pa, float pb, float pc, float pd, float t[2])
 
 static void
 gsk_curve_curve_get_tight_bounds (const GskCurve  *curve,
-                                  graphene_rect_t *bounds)
+                                  GskBoundingBox  *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);
+  gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
 
   n = 0;
   n += get_cubic_extrema (pts[0].x, pts[1].x, pts[2].x, pts[3].x, &t[n]);
@@ -679,7 +676,7 @@ gsk_curve_curve_get_tight_bounds (const GskCurve  *curve,
       graphene_point_t p;
 
       gsk_curve_curve_get_point (curve, t[i], &p);
-      graphene_rect_expand (bounds, &p, bounds);
+      gsk_bounding_box_expand (bounds, &p);
     }
 }
 
@@ -1379,15 +1376,14 @@ gsk_conic_curve_get_end_tangent (const GskCurve  *curve,
 }
 
 static void
-gsk_conic_curve_get_bounds (const GskCurve  *curve,
-                            graphene_rect_t *bounds)
+gsk_conic_curve_get_bounds (const GskCurve *curve,
+                            GskBoundingBox *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);
+  gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
+  gsk_bounding_box_expand (bounds, &pts[1]);
 }
 
 /* Solve N = 0 where N is the numerator of (P/Q)', with
@@ -1431,8 +1427,8 @@ get_conic_extrema (float a, float b, float c, float w, float t[4])
 }
 
 static void
-gsk_conic_curve_get_tight_bounds (const GskCurve  *curve,
-                                  graphene_rect_t *bounds)
+gsk_conic_curve_get_tight_bounds (const GskCurve *curve,
+                                  GskBoundingBox *bounds)
 {
   const GskConicCurve *self = &curve->conic;
   float w = gsk_conic_curve_get_weight (self);
@@ -1440,8 +1436,7 @@ gsk_conic_curve_get_tight_bounds (const GskCurve  *curve,
   float t[8];
   int n;
 
-  graphene_rect_init (bounds, pts[0].x, pts[0].y, 0, 0);
-  graphene_rect_expand (bounds, &pts[3], bounds);
+  gsk_bounding_box_init (bounds, &pts[0], &pts[3]);
 
   n = 0;
   n += get_conic_extrema (pts[0].x, pts[1].x, pts[3].x, w, &t[n]);
@@ -1452,7 +1447,7 @@ gsk_conic_curve_get_tight_bounds (const GskCurve  *curve,
       graphene_point_t p;
 
       gsk_conic_curve_get_point (curve, t[i], &p);
-      graphene_rect_expand (bounds, &p, bounds);
+      gsk_bounding_box_expand (bounds, &p);
     }
 }
 
@@ -1559,7 +1554,7 @@ gsk_conic_curve_get_curvature (const GskCurve *curve,
   p[2] = curve->conic.points[3];
 
   w1[0] = (1 - t) + t*w;
-  w1[1] = (1 - t)*w + t;
+w1[1] = (1 - t)*w + t;
 
   w2 = (1 - t)*w1[0] + t*w1[1];
 
@@ -1743,14 +1738,14 @@ gsk_curve_get_end_tangent (const GskCurve  *curve,
 
 void
 gsk_curve_get_bounds (const GskCurve  *curve,
-                      graphene_rect_t *bounds)
+                      GskBoundingBox  *bounds)
 {
   get_class (curve->op)->get_bounds (curve, bounds);
 }
 
 void
 gsk_curve_get_tight_bounds (const GskCurve  *curve,
-                            graphene_rect_t *bounds)
+                            GskBoundingBox  *bounds)
 {
   get_class (curve->op)->get_tight_bounds (curve, bounds);
 }
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 1aa4c5b5ce..310ac40e68 100644
--- a/gsk/gskcurveintersect.c
+++ b/gsk/gskcurveintersect.c
@@ -363,7 +363,7 @@ curve_intersect_recurse (const GskCurve   *curve1,
                          int              *pos)
 {
   GskCurve p11, p12, p21, p22;
-  graphene_rect_t b1, b2;
+  GskBoundingBox b1, b2;
   float d1, d2;
 
   if (*pos == n)
@@ -372,14 +372,14 @@ curve_intersect_recurse (const GskCurve   *curve1,
   gsk_curve_get_tight_bounds (curve1, &b1);
   gsk_curve_get_tight_bounds (curve2, &b2);
 
-  if (!graphene_rect_intersection (&b1, &b2, NULL))
+  if (!gsk_bounding_box_intersection (&b1, &b2, NULL))
     return;
 
   d1 = (t1r - t1l) / 2;
   d2 = (t2r - t2l) / 2;
 
-  if (b1.size.width < 0.1 && b1.size.height < 0.1 &&
-      b2.size.width < 0.1 && b2.size.height < 0.1)
+  if (b1.max.x - b1.min.x < 0.1 && b1.max.y - b1.min.y < 0.1 &&
+      b2.max.x - b2.min.x < 0.1 && b2.max.y - b2.min.y < 0.1)
     {
       graphene_point_t c;
       t1[*pos] = t1l + d1;
@@ -426,18 +426,12 @@ static void
 get_bounds (const GskCurve  *curve,
             float            tl,
             float            tr,
-            graphene_rect_t *bounds)
+            GskBoundingBox  *bounds)
 {
   GskCurve c;
 
   gsk_curve_segment (curve, tl, tr, &c);
   gsk_curve_get_tight_bounds (&c, bounds);
-
- /* FIXME this is working around inadequacies of
-  * graphene_rect_t as bounding box
-  */
- bounds->size.width += 0.0001;
- bounds->size.height += 0.0001;
 }
 
 static void
@@ -453,7 +447,7 @@ general_intersect_recurse (const GskCurve   *curve1,
                            int               n,
                            int              *pos)
 {
-  graphene_rect_t b1, b2;
+  GskBoundingBox b1, b2;
   float d1, d2;
 
   if (*pos == n)
@@ -462,14 +456,14 @@ general_intersect_recurse (const GskCurve   *curve1,
   get_bounds (curve1, t1l, t1r, &b1);
   get_bounds (curve2, t2l, t2r, &b2);
 
-  if (!graphene_rect_intersection (&b1, &b2, NULL))
+  if (!gsk_bounding_box_intersection (&b1, &b2, NULL))
     return;
 
   d1 = (t1r - t1l) / 2;
   d2 = (t2r - t2l) / 2;
 
-  if (b1.size.width < 0.1 && b1.size.height < 0.1 &&
-      b2.size.width < 0.1 && b2.size.height < 0.1)
+  if (b1.max.x - b1.min.x < 0.1 && b1.max.y - b1.min.y < 0.1 &&
+      b2.max.x - b2.min.x < 0.1 && b2.max.y - b2.min.y < 0.1)
     {
       graphene_point_t c;
       t1[*pos] = t1l + d1;
@@ -547,24 +541,27 @@ curve_self_intersect (const GskCurve   *curve,
 
   m = gsk_curve_intersect (&cs, &ce, tt, ss, pp, 3);
 
+  g_print ("found %d intersections:", m);
+  for (int i = 0; i < m; i++) g_print (" %f", tt[i]);
+  g_print ("\n");
   if (m > 1)
     {
-      if (tt[0] != 1)
+      if (fabs (tt[0] - 1) > 1e-4)
         {
           t1[0] = t2[0] = tt[0] * s;
           p[0] = pp[0];
         }
-      else if (tt[1] != 1)
+      else if (fabs (tt[1] - 1) > 1e-4)
         {
           t1[0] = t2[0] = tt[1] * s;
           p[0] = pp[1];
         }
-      if (ss[0] != 0)
+      if (fabs (ss[0]) > 1e-4)
         {
           t1[1] = t2[1] = s + ss[0] * (1 - s);
           p[1] = pp[0];
         }
-      else if (ss[1] != 0)
+      else if (fabs (ss[1]) > 1e-4)
         {
           t1[1] = t2[1] = s + ss[1] * (1 - s);
           p[1] = pp[1];
diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h
index 108add18b4..5af65f6fa9 100644
--- a/gsk/gskcurveprivate.h
+++ b/gsk/gskcurveprivate.h
@@ -22,6 +22,7 @@
 #define __GSK_CURVE_PRIVATE_H__
 
 #include "gskpathopprivate.h"
+#include "gskboundingboxprivate.h"
 
 G_BEGIN_DECLS
 
@@ -59,6 +60,9 @@ struct _GskConicCurve
 
   gboolean has_coefficients;
 
+  /* points[0], points[1], points[3] are the control points,
+   * points[2].x is the weight
+   */
   graphene_point_t points[4];
 
   graphene_point_t num[3];
@@ -124,9 +128,9 @@ 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_bounds                    (const GskCurve         *curve,
-                                                                 graphene_rect_t        *bounds);
+                                                                 GskBoundingBox         *bounds);
 void                    gsk_curve_get_tight_bounds              (const GskCurve         *curve,
-                                                                 graphene_rect_t        *bounds);
+                                                                 GskBoundingBox         *bounds);
 
 int                     gsk_curve_intersect                     (const GskCurve         *curve1,
                                                                  const GskCurve         *curve2,
diff --git a/testsuite/gsk/curve.c b/testsuite/gsk/curve.c
index 7bae660ac5..5b6106e377 100644
--- a/testsuite/gsk/curve.c
+++ b/testsuite/gsk/curve.c
@@ -116,6 +116,36 @@ test_curve_points (void)
     }
 }
 
+static void
+test_curve_bounds (void)
+{
+  for (int i = 0; i < 100; i++)
+    {
+      GskCurve c;
+      GskBoundingBox bounds;
+      GskBoundingBox bounds2;
+      graphene_point_t p;
+
+      init_random_curve (&c);
+
+      gsk_curve_get_tight_bounds (&c, &bounds);
+      gsk_curve_get_bounds (&c, &bounds2);
+
+      g_assert_true (gsk_bounding_box_contains_point (&bounds, gsk_curve_get_start_point (&c)));
+      g_assert_true (gsk_bounding_box_contains_point (&bounds, gsk_curve_get_end_point (&c)));
+      g_assert_true (gsk_bounding_box_contains_point (&bounds2, gsk_curve_get_start_point (&c)));
+      g_assert_true (gsk_bounding_box_contains_point (&bounds2, gsk_curve_get_end_point (&c)));
+
+      for (int j = 0; j < 20; j++)
+        {
+          float t = g_test_rand_double_range (0, 1);
+          gsk_curve_get_point (&c, t, &p);
+          g_assert_true (gsk_bounding_box_contains_point (&bounds, &p));
+          g_assert_true (gsk_bounding_box_contains_point (&bounds2, &p));
+        }
+    }
+}
+
 /* at this point the subdivision stops and the decomposer
  * violates tolerance rules
  */
@@ -293,6 +323,31 @@ test_line_line_intersection (void)
   g_assert_true (graphene_point_near (&p, &GRAPHENE_POINT_INIT (10, 10), 0.0001));
 }
 
+static void
+test_line_line_end_intersection (void)
+{
+  GskCurve c1, c2;
+  graphene_point_t p1[2], p2[2];
+  float t1, t2;
+  graphene_point_t p;
+  int n;
+
+  graphene_point_init (&p1[0], 10, 0);
+  graphene_point_init (&p1[1], 10, 100);
+  graphene_point_init (&p2[0], 10, 100);
+  graphene_point_init (&p2[1], 100, 10);
+
+  gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_LINE, p1));
+  gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&c1, &c2, &t1, &t2, &p, 1);
+
+  g_assert_cmpint (n, ==, 1);
+  g_assert_cmpfloat_with_epsilon (t1, 1, 0.0001);
+  g_assert_cmpfloat_with_epsilon (t2, 0, 0.0001);
+  g_assert_true (graphene_point_near (&p, &GRAPHENE_POINT_INIT (10, 100), 0.0001));
+}
+
 static void
 test_line_curve_intersection (void)
 {
@@ -301,7 +356,7 @@ test_line_curve_intersection (void)
   float t1[9], t2[9];
   graphene_point_t p[9];
   int n;
-  graphene_rect_t b;
+  GskBoundingBox b;
 
   graphene_point_init (&p1[0], 0, 100);
   graphene_point_init (&p1[1], 50, 100);
@@ -321,10 +376,37 @@ test_line_curve_intersection (void)
   g_assert_true (graphene_point_near (&p[0], &GRAPHENE_POINT_INIT (50, 50), 0.0001));
 
   gsk_curve_get_tight_bounds (&c1, &b);
-  graphene_rect_contains_point (&b, &p[0]);
+  gsk_bounding_box_contains_point (&b, &p[0]);
 
   gsk_curve_get_tight_bounds (&c2, &b);
-  graphene_rect_contains_point (&b, &p[0]);
+  gsk_bounding_box_contains_point (&b, &p[0]);
+}
+
+static void
+test_line_curve_end_intersection (void)
+{
+  GskCurve c1, c2;
+  graphene_point_t p1[4], p2[2];
+  float t1[9], t2[9];
+  graphene_point_t p[9];
+  int n;
+
+  graphene_point_init (&p1[0], 0, 100);
+  graphene_point_init (&p1[1], 50, 100);
+  graphene_point_init (&p1[2], 50, 0);
+  graphene_point_init (&p1[3], 100, 0);
+  graphene_point_init (&p2[0], 100, 0);
+  graphene_point_init (&p2[1], 100, 100);
+
+  gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+  gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+  n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 1);
+
+  g_assert_cmpint (n, ==, 1);
+  g_assert_cmpfloat_with_epsilon (t1[0], 1, 0.0001);
+  g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.0001);
+  g_assert_true (graphene_point_near (&p[0], &GRAPHENE_POINT_INIT (100, 0), 0.0001));
 }
 
 static void
@@ -360,7 +442,7 @@ test_curve_curve_intersection (void)
   float t1[9], t2[9];
   graphene_point_t p[9];
   int n;
-  graphene_rect_t b;
+  GskBoundingBox b;
 
   graphene_point_init (&p1[0], 0, 0);
   graphene_point_init (&p1[1], 33.333, 100);
@@ -383,10 +465,61 @@ test_curve_curve_intersection (void)
   g_assert_cmpfloat (t2[1], >, 0.5);
 
   gsk_curve_get_tight_bounds (&c1, &b);
-  graphene_rect_contains_point (&b, &p[0]);
+  gsk_bounding_box_contains_point (&b, &p[0]);
 
   gsk_curve_get_tight_bounds (&c2, &b);
-  graphene_rect_contains_point (&b, &p[0]);
+  gsk_bounding_box_contains_point (&b, &p[0]);
+}
+
+static void
+test_curve_curve_end_intersection (void)
+{
+  GskCurve c1, c2;
+  graphene_point_t p1[4], p2[4];
+  float t1[9], t2[9];
+  graphene_point_t p[9];
+  int n;
+
+  graphene_point_init (&p1[0], 0, 0);
+  graphene_point_init (&p1[1], 33.333, 100);
+  graphene_point_init (&p1[2], 66.667, 0);
+  graphene_point_init (&p1[3], 100, 100);
+  graphene_point_init (&p2[0], 100, 100);
+  graphene_point_init (&p2[1], 100, 0);
+  graphene_point_init (&p2[2], 20, 0);
+  graphene_point_init (&p2[3], 10, 0);
+
+  gsk_curve_init (&c1, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+  gsk_curve_init (&c2, gsk_pathop_encode (GSK_PATH_CONIC, p2));
+
+  n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 9);
+
+  g_assert_cmpint (n, ==, 1);
+  g_assert_cmpfloat_with_epsilon (t1[0], 1, 0.0001);
+  g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.0001);
+}
+
+static void
+test_curve_curve_end_intersection2 (void)
+{
+  GskCurve c, c1, c2;
+  graphene_point_t p1[4];
+  float t1[9], t2[9];
+  graphene_point_t p[9];
+  int n;
+
+  graphene_point_init (&p1[0], 200, 100);
+  graphene_point_init (&p1[1], 300, 300);
+  graphene_point_init (&p1[2], 100, 300);
+  graphene_point_init (&p1[3], 300, 100);
+
+  gsk_curve_init (&c, gsk_pathop_encode (GSK_PATH_CURVE, p1));
+
+  gsk_curve_split (&c, 0.5, &c1, &c2);
+
+  n = gsk_curve_intersect (&c1, &c2, t1, t2, p, 9);
+
+  g_assert_cmpint (n, ==, 2);
 }
 
 static void
@@ -682,13 +815,18 @@ main (int argc, char *argv[])
   g_test_init (&argc, &argv, NULL);
 
   g_test_add_func ("/curve/points", test_curve_points);
+  g_test_add_func ("/curve/bounds", test_curve_bounds);
   g_test_add_func ("/curve/tangents", test_curve_tangents);
   g_test_add_func ("/curve/decompose", test_curve_decompose);
   g_test_add_func ("/curve/decompose-curve", test_curve_decompose_curve);
   g_test_add_func ("/curve/intersection/line-line", test_line_line_intersection);
+  g_test_add_func ("/curve/intersection/line-line-end", test_line_line_end_intersection);
   g_test_add_func ("/curve/intersection/line-curve", test_line_curve_intersection);
+  g_test_add_func ("/curve/intersection/line-curve-end", test_line_curve_end_intersection);
   g_test_add_func ("/curve/intersection/line-curve-none", test_line_curve_none_intersection);
   g_test_add_func ("/curve/intersection/curve-curve", test_curve_curve_intersection);
+  g_test_add_func ("/curve/intersection/curve-curve-end", test_curve_curve_end_intersection);
+  g_test_add_func ("/curve/intersection/curve-curve-end2", test_curve_curve_end_intersection2);
   g_test_add_func ("/curve/intersection/curve-curve-max", test_curve_curve_max_intersection);
   g_test_add_func ("/curve/intersection/horizontal-line", test_curve_intersection_horizontal_line);
   g_test_add_func ("/curve/split", test_curve_split);


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]