[gtk/wip/otte/lottie: 1/42] Implement gsk_path_measure_in_fill

[Benjamin Otte <otte src gnome org>]

commit a593110797aee3245f0f367f794b7972b5d9951d
Author: Matthias Clasen <mclasen redhat com>
Date:   Thu Nov 26 23:15:47 2020 -0500

    Implement gsk_path_measure_in_fill
    
    Implement this in the obvious way, using the decomposed form
    of standard contours. Since the decomposed form is part of the
    measure object, this api moves from gsk_path_in_fill to
    gsk_path_measure_in_fill.

 docs/reference/gsk/gsk4-sections.txt |   1 +
 gsk/gskpath.c                        | 156 ++++++++++++++++++++++++++++++++++-
 gsk/gskpathmeasure.c                 |  43 +++++++++-
 gsk/gskpathmeasure.h                 |   6 ++
 gsk/gskpathprivate.h                 |   4 +
 5 files changed, 206 insertions(+), 4 deletions(-)
---
diff --git a/docs/reference/gsk/gsk4-sections.txt b/docs/reference/gsk/gsk4-sections.txt
index 6cfa58b8f8..bb8c213869 100644
--- a/docs/reference/gsk/gsk4-sections.txt
+++ b/docs/reference/gsk/gsk4-sections.txt
@@ -378,6 +378,7 @@ gsk_path_measure_get_length
 gsk_path_measure_get_point
 gsk_path_measure_get_closest_point
 gsk_path_measure_get_closest_point_full
+gsk_path_measure_in_fill
 gsk_path_measure_add_segment
 <SUBSECTION Private>
 GSK_TYPE_PATH_MEASURE
diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index 21e8857c46..5dc8a09343 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -87,6 +87,10 @@ struct _GskContourClass
                                                  gpointer                measure_data,
                                                  float                   start,
                                                  float                   end);
+  int                   (* get_winding)         (const GskContour       *contour,
+                                                 gpointer                measure_data,
+                                                 const graphene_point_t *point,
+                                                 gboolean               *on_edge);
 };
 
 struct _GskPath
@@ -481,6 +485,23 @@ gsk_rect_contour_add_segment (const GskContour *contour,
     }
 }
 
+static int
+gsk_rect_contour_get_winding (const GskContour       *contour,
+                              gpointer                measure_data,
+                              const graphene_point_t *point,
+                              gboolean               *on_edge)
+{
+  const GskRectContour *self = (const GskRectContour *) contour;
+  graphene_rect_t rect;
+
+  graphene_rect_init (&rect, self->x, self->y, self->width, self->height);
+
+  if (graphene_rect_contains_point (&rect, point))
+    return -1;
+
+  return 0;
+}
+
 static const GskContourClass GSK_RECT_CONTOUR_CLASS =
 {
   sizeof (GskRectContour),
@@ -496,7 +517,8 @@ static const GskContourClass GSK_RECT_CONTOUR_CLASS =
   gsk_rect_contour_get_point,
   gsk_rect_contour_get_closest_point,
   gsk_rect_contour_copy,
-  gsk_rect_contour_add_segment
+  gsk_rect_contour_add_segment,
+  gsk_rect_contour_get_winding
 };
 
 GskContour *
@@ -785,6 +807,50 @@ gsk_circle_contour_add_segment (const GskContour *contour,
   gsk_path_builder_add_contour (builder, segment);
 }
 
+static int
+gsk_circle_contour_get_winding (const GskContour       *contour,
+                                gpointer                measure_data,
+                                const graphene_point_t *point,
+                                gboolean               *on_edge)
+{
+  const GskCircleContour *self = (const GskCircleContour *) contour;
+
+  if (graphene_point_distance (point, &self->center, NULL, NULL) >= self->radius)
+    return 0;
+
+  if (fabs (self->start_angle - self->end_angle) >= 360)
+    {
+      return -1;
+    }
+  else
+    {
+      /* Check if the point and the midpoint are on the same side
+       * of the chord through start and end.
+       */
+      double mid_angle = (self->end_angle - self->start_angle) / 2;
+      graphene_point_t start = GRAPHENE_POINT_INIT (self->center.x + cos (DEG_TO_RAD (self->start_angle)) * 
self->radius,
+                                                    self->center.y + sin (DEG_TO_RAD (self->start_angle)) * 
self->radius);
+      graphene_point_t mid = GRAPHENE_POINT_INIT (self->center.x + cos (DEG_TO_RAD (mid_angle)) * 
self->radius,
+                                                  self->center.y + sin (DEG_TO_RAD (mid_angle)) * 
self->radius);
+      graphene_point_t end = GRAPHENE_POINT_INIT (self->center.x + cos (DEG_TO_RAD (self->end_angle)) * 
self->radius,
+                                                  self->center.y + sin (DEG_TO_RAD (self->end_angle)) * 
self->radius);
+
+      graphene_vec2_t n, m;
+      float a, b;
+
+      graphene_vec2_init (&n, start.y - end.y, end.x - start.x);
+      graphene_vec2_init (&m, mid.x, mid.y);
+      a = graphene_vec2_dot (&m, &n);
+      graphene_vec2_init (&m, point->x, point->y);
+      b = graphene_vec2_dot (&m, &n);
+
+      if ((a < 0) != (b < 0))
+        return -1;
+    }
+
+  return 0;
+}
+
 static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS =
 {
   sizeof (GskCircleContour),
@@ -800,7 +866,8 @@ static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS =
   gsk_circle_contour_get_point,
   gsk_circle_contour_get_closest_point,
   gsk_circle_contour_copy,
-  gsk_circle_contour_add_segment
+  gsk_circle_contour_add_segment,
+  gsk_circle_contour_get_winding
 };
 
 GskContour *
@@ -1440,6 +1507,79 @@ gsk_standard_contour_add_segment (const GskContour *contour,
     }
 }
 
+static inline int
+line_get_crossing (const graphene_point_t *p,
+                   const graphene_point_t *p1,
+                   const graphene_point_t *p2,
+                   gboolean               *on_edge)
+{
+  int dir = 1;
+
+  if (p1->x >= p->x && p2->x >= p->x)
+    return 0;
+
+  if (p2->y < p1->y)
+    {
+      const graphene_point_t *tmp;
+      tmp = p1;
+      p1 = p2;
+      p2 = tmp;
+      dir = -1;
+    }
+
+  if ((p1->x >= p->x && p1->y == p->y) ||
+      (p2->x >= p->x && p2->y == p->y))
+    {
+        *on_edge = TRUE;
+        return 0;
+    }
+
+  if (p2->y <= p->y || p1->y > p->y)
+    return 0;
+
+  if (p1->x <= p->x && p2->x <= p->x)
+    return dir;
+
+  if (p->x > p1->x + (p->y - p1->y) * (p2->x - p1->x) / (p2->y - p1->y))
+    return dir;
+
+  return 0;
+}
+
+static int
+gsk_standard_contour_get_winding (const GskContour       *contour,
+                                  gpointer                measure_data,
+                                  const graphene_point_t *point,
+                                  gboolean               *on_edge)
+{
+  GskStandardContour *self = (GskStandardContour *) contour;
+  GArray *array = measure_data;
+  graphene_point_t last_point;
+  int winding;
+  int i;
+
+  if (array->len == 0)
+    return 0;
+
+  winding = 0;
+  last_point = self->points[0];
+  for (i = 0; i < array->len; i++)
+    {
+      GskStandardContourMeasure *measure;
+
+      measure = &g_array_index (array, GskStandardContourMeasure, i);
+      winding += line_get_crossing (point, &last_point, &measure->end_point, on_edge);
+      if (*on_edge)
+        return 0;
+
+      last_point = measure->end_point;
+    }
+
+  winding += line_get_crossing (point, &last_point, &self->points[0], on_edge);
+
+  return winding;
+}
+
 static const GskContourClass GSK_STANDARD_CONTOUR_CLASS =
 {
   sizeof (GskStandardContour),
@@ -1455,7 +1595,8 @@ static const GskContourClass GSK_STANDARD_CONTOUR_CLASS =
   gsk_standard_contour_get_point,
   gsk_standard_contour_get_closest_point,
   gsk_standard_contour_copy,
-  gsk_standard_contour_add_segment
+  gsk_standard_contour_add_segment,
+  gsk_standard_contour_get_winding
 };
 
 /* You must ensure the contour has enough size allocated,
@@ -1591,6 +1732,15 @@ gsk_contour_add_segment (const GskContour *self,
   self->klass->add_segment (self, builder, measure_data, start, end);
 }
 
+int
+gsk_contour_get_winding (const GskContour       *self,
+                         gpointer                measure_data,
+                         const graphene_point_t *point,
+                         gboolean               *on_edge)
+{
+  return self->klass->get_winding (self, measure_data, point, on_edge);
+}
+
 static inline void
 gsk_contour_copy (GskContour       *dest,
                   const GskContour *src)
diff --git a/gsk/gskpathmeasure.c b/gsk/gskpathmeasure.c
index e312eb4143..21f6818687 100644
--- a/gsk/gskpathmeasure.c
+++ b/gsk/gskpathmeasure.c
@@ -374,6 +374,48 @@ gsk_path_measure_get_closest_point_full (GskPathMeasure         *self,
   return result;
 }
 
+/**
+ * gsk_path_measure_in_fill:
+ * @self: a #GskPathMeasure
+ * @point: the point to test
+ * @fill_rule: the fill rule to follow
+ *
+ * Returns whether the given point is inside the area that would be
+ * affected if the path of @self was filled according to @fill_rule.
+ *
+ * Returns: %TRUE if @point is inside
+ */
+gboolean
+gsk_path_measure_in_fill (GskPathMeasure         *self,
+                          const graphene_point_t *point,
+                          GskFillRule             fill_rule)
+{
+  int winding = 0;
+  gboolean on_edge = FALSE;
+  int i;
+
+  for (i = 0; i < self->n_contours; i++)
+    {
+      winding += gsk_contour_get_winding (gsk_path_get_contour (self->path, i),
+                                          self->measures[i].contour_data,
+                                          point,
+                                          &on_edge);
+      if (on_edge)
+        return TRUE;
+    }
+
+  switch (fill_rule)
+    {
+    case GSK_FILL_RULE_EVEN_ODD:
+      return winding & 1;
+    case GSK_FILL_RULE_WINDING:
+      return winding != 0;
+    default:
+      g_assert_not_reached ();
+    }
+}
+
+
 /**
  * gsk_path_measure_add_segment:
  * @self: a #GskPathMeasure
@@ -433,4 +475,3 @@ gsk_path_measure_add_segment (GskPathMeasure *self,
         }
     }
 }
-
diff --git a/gsk/gskpathmeasure.h b/gsk/gskpathmeasure.h
index 64b04753da..c20e79bef1 100644
--- a/gsk/gskpathmeasure.h
+++ b/gsk/gskpathmeasure.h
@@ -69,6 +69,12 @@ void                    gsk_path_measure_add_segment            (GskPathMeasure
                                                                  GskPathBuilder         *builder,
                                                                  float                   start,
                                                                  float                   end);
+
+GDK_AVAILABLE_IN_ALL
+gboolean                gsk_path_measure_in_fill                (GskPathMeasure         *self,
+                                                                 const graphene_point_t *point,
+                                                                 GskFillRule             fill_rule);
+
 G_END_DECLS
 
 #endif /* __GSK_PATH_MEASURE_H__ */
diff --git a/gsk/gskpathprivate.h b/gsk/gskpathprivate.h
index 913c9c759e..6ea2c2c6d3 100644
--- a/gsk/gskpathprivate.h
+++ b/gsk/gskpathprivate.h
@@ -92,6 +92,10 @@ gboolean                gsk_contour_get_closest_point           (GskPath
                                                                  graphene_point_t       *out_pos,
                                                                  float                  *out_offset,
                                                                  graphene_vec2_t        *out_tangent);
+int                     gsk_contour_get_winding                 (const GskContour       *self,
+                                                                 gpointer                measure_data,
+                                                                 const graphene_point_t *point,
+                                                                 gboolean               *on_edge);
 void                    gsk_contour_add_segment                 (const GskContour       *self,
                                                                  GskPathBuilder         *builder,
                                                                  gpointer                measure_data,