gsk: Add (private) gsk_rounded_rect_intersection()

The idea is that for a rectangle intersection, each corner of the
result is either entirely part of one original rectangle or it is
an intersection point.

By detecting those 2 cases and treating them differently, we can
simplify the code to compare rounded rectangles.

3 files changed, 289 insertions, 0 deletions

diff --git a/gsk/gskroundedrect.c b/gsk/gskroundedrect.c
index ed1131de83..76efe4d9ae 100644
--- a/gsk/gskroundedrect.c
+++ b/gsk/gskroundedrect.c
@@ -689,6 +689,134 @@ gsk_rounded_rect_intersect_with_rect (const GskRoundedRect  *self,
   return GSK_INTERSECTION_NONEMPTY;
 }
 
+static gboolean
+check_nonintersecting_corner (const GskRoundedRect *out,
+                              const GskRoundedRect *in,
+                              GskCorner             corner,
+                              float                 diff_x,
+                              float                 diff_y,
+                              GskRoundedRect       *result)
+{
+  g_assert (diff_x >= 0);
+  g_assert (diff_y >= 0);
+
+  if (out->corner[corner].width < diff_x ||
+      out->corner[corner].height < diff_y ||
+      (out->corner[corner].width <= in->corner[corner].width + diff_x &&
+       out->corner[corner].height <= in->corner[corner].height + diff_y))
+    {
+      result->corner[corner] = in->corner[corner];
+      return TRUE;
+    }
+
+  if (diff_x > 0 || diff_y > 0)
+    return FALSE;
+
+  if (out->corner[corner].width > in->corner[corner].width &&
+      out->corner[corner].height > in->corner[corner].height)
+    {
+      result->corner[corner] = out->corner[corner];
+      return TRUE;
+    }
+
+  return FALSE;
+}
+
+/* a is outside in x direction, b is outside in y direction */
+static gboolean
+check_intersecting_corner (const GskRoundedRect *a,
+                           const GskRoundedRect *b,
+                           GskCorner             corner,
+                           float                 diff_x,
+                           float                 diff_y,
+                           GskRoundedRect       *result)
+{
+  g_assert (diff_x > 0);
+  g_assert (diff_y > 0);
+
+  if (diff_x < a->corner[corner].width ||
+      diff_x > a->bounds.size.width - a->corner[corner].width - a->corner[OPPOSITE_CORNER_X (corner)].width ||
+      diff_y < b->corner[corner].height ||
+      diff_y > b->bounds.size.height - b->corner[corner].height - b->corner[OPPOSITE_CORNER_Y (corner)].height)
+    return FALSE;
+
+  result->corner[corner] = GRAPHENE_SIZE_INIT (0, 0);
+  return TRUE;
+}
+
+static gboolean
+check_corner (const GskRoundedRect *a,
+              const GskRoundedRect *b,
+              GskCorner             corner,
+              float                 diff_x,
+              float                 diff_y,
+              GskRoundedRect       *result)
+{
+  if (diff_x >= 0)
+    {
+      if (diff_y >= 0)
+        {
+          return check_nonintersecting_corner (a, b, corner, diff_x, diff_y, result);
+        }
+      else if (diff_x == 0)
+        {
+          return check_nonintersecting_corner (b, a, corner, 0, - diff_y, result);
+        }
+      else
+        {
+          return check_intersecting_corner (a, b, corner, diff_x, - diff_y, result);
+        }
+    }
+  else
+    {
+      if (diff_y <= 0)
+        {
+          return check_nonintersecting_corner (b, a, corner, - diff_x, - diff_y, result);
+        }
+      else
+        {
+          return check_intersecting_corner (b, a, corner, - diff_x, diff_y, result);
+        }
+    }
+                    
+}
+
+GskRoundedRectIntersection
+gsk_rounded_rect_intersection (const GskRoundedRect *a,
+                               const GskRoundedRect *b,
+                               GskRoundedRect       *result)
+{
+  float top, left, bottom, right;
+
+  if (!graphene_rect_intersection (&a->bounds, &b->bounds, &result->bounds))
+    return GSK_INTERSECTION_EMPTY;
+
+  left = b->bounds.origin.x - a->bounds.origin.x;
+  top = b->bounds.origin.y - a->bounds.origin.y;
+  right = a->bounds.origin.x + a->bounds.size.width - b->bounds.origin.x - b->bounds.size.width;
+  bottom = a->bounds.origin.y + a->bounds.size.height - b->bounds.origin.y - b->bounds.size.height;
+
+  if (check_corner (a, b,
+                    GSK_CORNER_TOP_LEFT,
+                    left, top,
+                    result) &&
+      check_corner (a, b,
+                    GSK_CORNER_TOP_RIGHT,
+                    right, top,
+                    result) &&
+      check_corner (a, b,
+                    GSK_CORNER_BOTTOM_LEFT,
+                    left, bottom,
+                    result) &&
+      check_corner (a, b,
+                    GSK_CORNER_BOTTOM_RIGHT,
+                    right, bottom,
+                    result))
+    return GSK_INTERSECTION_NONEMPTY;
+
+  return GSK_INTERSECTION_NOT_REPRESENTABLE;
+}
+
 static void
 append_arc (cairo_t *cr, double angle1, double angle2, gboolean negative)
 {
diff --git a/gsk/gskroundedrectprivate.h b/gsk/gskroundedrectprivate.h
index c42906d53a..64c3469df9 100644
--- a/gsk/gskroundedrectprivate.h
+++ b/gsk/gskroundedrectprivate.h
@@ -6,6 +6,24 @@
 
 G_BEGIN_DECLS
 
+#define OPPOSITE_CORNER(corner) ((corner) ^ 2)
+G_STATIC_ASSERT (OPPOSITE_CORNER (GSK_CORNER_TOP_LEFT) == GSK_CORNER_BOTTOM_RIGHT);
+G_STATIC_ASSERT (OPPOSITE_CORNER (GSK_CORNER_TOP_RIGHT) == GSK_CORNER_BOTTOM_LEFT);
+G_STATIC_ASSERT (OPPOSITE_CORNER (GSK_CORNER_BOTTOM_LEFT) == GSK_CORNER_TOP_RIGHT);
+G_STATIC_ASSERT (OPPOSITE_CORNER (GSK_CORNER_BOTTOM_RIGHT) == GSK_CORNER_TOP_LEFT);
+
+#define OPPOSITE_CORNER_X(corner) ((corner) ^ 1)
+G_STATIC_ASSERT (OPPOSITE_CORNER_X (GSK_CORNER_TOP_LEFT) == GSK_CORNER_TOP_RIGHT);
+G_STATIC_ASSERT (OPPOSITE_CORNER_X (GSK_CORNER_TOP_RIGHT) == GSK_CORNER_TOP_LEFT);
+G_STATIC_ASSERT (OPPOSITE_CORNER_X (GSK_CORNER_BOTTOM_LEFT) == GSK_CORNER_BOTTOM_RIGHT);
+G_STATIC_ASSERT (OPPOSITE_CORNER_X (GSK_CORNER_BOTTOM_RIGHT) == GSK_CORNER_BOTTOM_LEFT);
+
+#define OPPOSITE_CORNER_Y(corner) ((corner) ^ 3)
+G_STATIC_ASSERT (OPPOSITE_CORNER_Y (GSK_CORNER_TOP_LEFT) == GSK_CORNER_BOTTOM_LEFT);
+G_STATIC_ASSERT (OPPOSITE_CORNER_Y (GSK_CORNER_TOP_RIGHT) == GSK_CORNER_BOTTOM_RIGHT);
+G_STATIC_ASSERT (OPPOSITE_CORNER_Y (GSK_CORNER_BOTTOM_LEFT) == GSK_CORNER_TOP_LEFT);
+G_STATIC_ASSERT (OPPOSITE_CORNER_Y (GSK_CORNER_BOTTOM_RIGHT) == GSK_CORNER_TOP_RIGHT);
+
 #define GSK_ROUNDED_RECT_INIT_FROM_RECT(_r)   \
   (GskRoundedRect) { .bounds = _r, \
                      .corner = { \
@@ -44,6 +62,9 @@ typedef enum {
 GskRoundedRectIntersection gsk_rounded_rect_intersect_with_rect   (const GskRoundedRect     *self,
                                                                    const graphene_rect_t    *rect,
                                                                    GskRoundedRect           *result) G_GNUC_PURE;
+GskRoundedRectIntersection gsk_rounded_rect_intersection          (const GskRoundedRect     *a,
+                                                                   const GskRoundedRect     *b,
+                                                                   GskRoundedRect           *result);
 
 
 G_END_DECLS
diff --git a/testsuite/gsk/rounded-rect.c b/testsuite/gsk/rounded-rect.c
index 5a72928257..552bed49d9 100644
--- a/testsuite/gsk/rounded-rect.c
+++ b/testsuite/gsk/rounded-rect.c
@@ -241,6 +241,145 @@ test_intersect_with_rect (void)
     }
 }
 
+static void
+test_intersect (void)
+{
+  struct {
+    GskRoundedRect a;
+    GskRoundedRect b;
+    GskRoundedRectIntersection result;
+    GskRoundedRect expected;
+  } test[] = {
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 0),
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(50, 50, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT_UNIFORM(50, 50, 50, 50, 20, 0, 20, 0),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(50, 0, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(50, 0, 50, 100, 20),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(0, 50, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(0, 50, 100, 50, 20),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(-50, -50, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 50, 50, 20, 0, 20, 0),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(0, -50, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(0, 0, 100, 50, 20),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(-50, 0, 100, 100, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(0, 0, 50, 100, 20),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(10, 10, 80, 80, 20),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(10, 10, 80, 80, 20),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 20),
+      ROUNDED_RECT_INIT(10, 10, 80, 80, 10),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT(10, 10, 80, 80, 10),
+    },
+    {
+      ROUNDED_RECT_INIT(0, 0, 100, 100, 40),
+      ROUNDED_RECT_INIT(10, 10, 80, 80, 0),
+      GSK_INTERSECTION_NOT_REPRESENTABLE,
+    },
+    {
+      ROUNDED_RECT_INIT(10, 10, 100, 100, 40),
+      ROUNDED_RECT_INIT(30, 0, 40, 40, 0),
+      GSK_INTERSECTION_NOT_REPRESENTABLE,
+    },
+    {
+      ROUNDED_RECT_INIT(10, 10, 100, 100, 40),
+      ROUNDED_RECT_INIT(0, 0, 100, 20, 0),
+      GSK_INTERSECTION_NOT_REPRESENTABLE,
+    },
+    {
+      ROUNDED_RECT_INIT_UNIFORM(647, 18, 133, 35, 5, 0, 0, 5),
+      ROUNDED_RECT_INIT_UNIFORM(14, 12, 1666, 889, 8, 8, 0, 0),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT_UNIFORM(647, 18, 133, 35, 5, 0, 0, 5),
+    },
+    {
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 100, 100, 100, 0, 0, 0),
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 100, 100, 0, 0, 100, 0),
+      GSK_INTERSECTION_NONEMPTY,
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 100, 100, 100, 0, 100, 0),
+    },
+    {
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 100, 100, 100, 0, 0, 0),
+      ROUNDED_RECT_INIT_UNIFORM(-20, -20, 100, 100, 0, 0, 100, 0),
+      GSK_INTERSECTION_NOT_REPRESENTABLE,
+    },
+    {
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 50, 50, 0, 0, 50, 0),
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 20, 20, 20, 0, 0, 0),
+      GSK_INTERSECTION_NOT_REPRESENTABLE, /* FIXME: should be empty */
+    },
+    {
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 50, 50, 0, 0, 50, 0),
+      ROUNDED_RECT_INIT_UNIFORM(0, 0, 21, 21, 21, 0, 0, 0),
+      GSK_INTERSECTION_NOT_REPRESENTABLE,
+    },
+  };
+  gsize i;
+
+  for (i = 0; i < G_N_ELEMENTS (test); i++)
+    {
+      GskRoundedRect out;
+      GskRoundedRectIntersection res;
+
+      if (g_test_verbose ())
+        g_test_message ("intersection test %zu", i);
+
+      memset (&out, 0, sizeof (GskRoundedRect));
+
+      res = gsk_rounded_rect_intersection (&test[i].a, &test[i].b, &out);
+      g_assert_cmpint (res, ==, test[i].result);
+      if (res == GSK_INTERSECTION_NONEMPTY)
+        {
+          if (!gsk_rounded_rect_equal (&out, &test[i].expected))
+            {
+              char *a = gsk_rounded_rect_to_string (&test[i].a);
+              char *b = gsk_rounded_rect_to_string (&test[i].b);
+              char *expected = gsk_rounded_rect_to_string (&test[i].expected);
+              char *result = gsk_rounded_rect_to_string (&out);
+              g_test_message ("     A = %s\n"
+                              "     B = %s\n"
+                              "expected %s\n"
+                              "     got %s\n",
+                              a, b, expected, result);
+            }
+          g_assert_true (gsk_rounded_rect_equal (&out, &test[i].expected));
+        }
+    }
+}
+
 int
 main (int   argc,
       char *argv[])
@@ -253,6 +392,7 @@ main (int   argc,
   g_test_add_func ("/rounded-rect/is-circular", test_is_circular);
   g_test_add_func ("/rounded-rect/to-float", test_to_float);
   g_test_add_func ("/rounded-rect/intersect-with-rect", test_intersect_with_rect);
+  g_test_add_func ("/rounded-rect/intersect", test_intersect);
 
   return g_test_run ();
 }