From aa722dcfac2ebee7c62a703070aab380f03a46b4 Mon Sep 17 00:00:00 2001 From: Matthias Clasen Date: Tue, 22 Mar 2022 00:33:09 -0400 Subject: path: Add gsk_path_is_convex Add a function to compute whether a path is convex. --- gsk/gskcontour.c | 36 ++++++ gsk/gskcontourprivate.h | 2 + gsk/gskconvexity.c | 286 ++++++++++++++++++++++++++++++++++++++++++++++ gsk/gskconvexityprivate.h | 14 +++ gsk/gskpath.c | 22 ++++ gsk/gskpath.h | 3 + gsk/meson.build | 1 + testsuite/gsk/path.c | 81 ++++++++++++- 8 files changed, 439 insertions(+), 6 deletions(-) create mode 100644 gsk/gskconvexity.c create mode 100644 gsk/gskconvexityprivate.h diff --git a/gsk/gskcontour.c b/gsk/gskcontour.c index f90e4cea21..880d6d8ed7 100644 --- a/gsk/gskcontour.c +++ b/gsk/gskcontour.c @@ -26,6 +26,7 @@ #include "gskpathprivate.h" #include "gsksplineprivate.h" #include "gskstrokeprivate.h" +#include "gskconvexityprivate.h" typedef struct _GskContourClass GskContourClass; @@ -99,6 +100,7 @@ struct _GskContourClass GskLineJoin line_join, float miter_limit); GskContour * (* reverse) (const GskContour *contour); + gboolean (* is_convex) (const GskContour *contour); }; static gsize @@ -576,6 +578,12 @@ gsk_rect_contour_reverse (const GskContour *contour) self->height)); } +static gboolean +gsk_rect_contour_is_convex (const GskContour *contour) +{ + return TRUE; +} + static const GskContourClass GSK_RECT_CONTOUR_CLASS = { sizeof (GskRectContour), @@ -598,6 +606,7 @@ static const GskContourClass GSK_RECT_CONTOUR_CLASS = gsk_rect_contour_add_stroke, gsk_rect_contour_offset, gsk_rect_contour_reverse, + gsk_rect_contour_is_convex, }; GskContour * @@ -989,6 +998,12 @@ gsk_circle_contour_reverse (const GskContour *contour) self->start_angle); } +static gboolean +gsk_circle_contour_is_convex (const GskContour *contour) +{ + return TRUE; +} + static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS = { sizeof (GskCircleContour), @@ -1011,6 +1026,7 @@ static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS = gsk_circle_contour_add_stroke, gsk_circle_contour_offset, gsk_circle_contour_reverse, + gsk_circle_contour_is_convex, }; GskContour * @@ -1044,6 +1060,7 @@ struct _GskStandardContour GskContour contour; GskPathFlags flags; + GskConvexity convexity; gsize n_ops; gsize n_points; @@ -1818,6 +1835,17 @@ gsk_standard_contour_reverse (const GskContour *contour) return res; } +static gboolean +gsk_standard_contour_is_convex (const GskContour *contour) +{ + GskStandardContour *self = (GskStandardContour *) contour; + + if (self->convexity == GSK_CONVEXITY_UNKNOWN) + self->convexity = gsk_contour_compute_convexity (contour); + + return self->convexity == GSK_CONVEXITY_CONVEX; +} + static const GskContourClass GSK_STANDARD_CONTOUR_CLASS = { sizeof (GskStandardContour), @@ -1840,6 +1868,7 @@ static const GskContourClass GSK_STANDARD_CONTOUR_CLASS = gsk_standard_contour_add_stroke, gsk_standard_contour_offset, gsk_standard_contour_reverse, + gsk_standard_contour_is_convex, }; /* You must ensure the contour has enough size allocated, @@ -1861,6 +1890,7 @@ gsk_standard_contour_init (GskContour *contour, self->contour.klass = &GSK_STANDARD_CONTOUR_CLASS; self->flags = flags; + self->convexity = GSK_CONVEXITY_UNKNOWN; self->n_ops = n_ops; self->n_points = n_points; self->points = (graphene_point_t *) &self->ops[n_ops]; @@ -2061,3 +2091,9 @@ gsk_contour_reverse (const GskContour *src) { return src->klass->reverse (src); } + +gboolean +gsk_contour_is_convex (const GskContour *contour) +{ + return contour->klass->is_convex (contour); +} diff --git a/gsk/gskcontourprivate.h b/gsk/gskcontourprivate.h index 842e4e04a1..cf5bf5493c 100644 --- a/gsk/gskcontourprivate.h +++ b/gsk/gskcontourprivate.h @@ -124,6 +124,8 @@ void gsk_contour_default_offset (const GskContou GskLineJoin line_join, float miter_limit); +gboolean gsk_contour_is_convex (const GskContour *contour); + G_END_DECLS #endif /* __GSK_CONTOUR_PRIVATE_H__ */ diff --git a/gsk/gskconvexity.c b/gsk/gskconvexity.c new file mode 100644 index 0000000000..f1c098b91d --- /dev/null +++ b/gsk/gskconvexity.c @@ -0,0 +1,286 @@ +#include "config.h" + +#include "gskconvexityprivate.h" +#include "gskcontourprivate.h" + +typedef enum +{ + GSK_DIR_CHANGE_UNKNOWN, + GSK_DIR_CHANGE_LEFT, + GSK_DIR_CHANGE_RIGHT, + GSK_DIR_CHANGE_STRAIGHT, + GSK_DIR_CHANGE_REVERSE, + GSK_DIR_CHANGE_INVALID, +} GskDirChange; + +typedef enum +{ + GSK_PATH_DIRECTION_UNKNOWN, + GSK_PATH_DIRECTION_CLOCKWISE, + GSK_PATH_DIRECTION_COUNTERCLOCKWISE, +} GskPathDirection; + +typedef struct _GskConvexityChecker GskConvexityChecker; +struct _GskConvexityChecker +{ + graphene_point_t first_point; + graphene_vec2_t first_vec; + graphene_point_t last_point; + graphene_vec2_t last_vec; + GskDirChange expected_direction; + GskPathDirection first_direction; + int reversals; + gboolean finite; + GskConvexity convexity; + int xsign; + int ysign; + int dx; + int dy; +}; + +static float +cross_product (graphene_vec2_t *a, + graphene_vec2_t *b) +{ + float fa[2]; + float fb[2]; + graphene_vec2_to_float (a, fa); + graphene_vec2_to_float (b, fb); + return fa[0] * fb[1] - fa[1] * fb[0]; +} + +static GskDirChange +direction_change (GskConvexityChecker *c, + graphene_vec2_t *v) +{ + float cross = cross_product (&(c->last_vec), v); + if (!finite (cross)) + return GSK_DIR_CHANGE_UNKNOWN; + + if (cross == 0) + return graphene_vec2_dot (&(c->last_vec), v) < 0 + ? GSK_DIR_CHANGE_REVERSE + : GSK_DIR_CHANGE_STRAIGHT; + + return cross > 0 + ? GSK_DIR_CHANGE_RIGHT + : GSK_DIR_CHANGE_LEFT; +} + +static gboolean +add_vec (GskConvexityChecker *c, + graphene_vec2_t *v) +{ + GskDirChange dir; + int sign; + + dir = direction_change (c, v); + switch (dir) + { + case GSK_DIR_CHANGE_LEFT: + case GSK_DIR_CHANGE_RIGHT: + if (c->expected_direction == GSK_DIR_CHANGE_INVALID) + { + c->expected_direction = dir; + c->first_direction = (dir == GSK_DIR_CHANGE_RIGHT) + ? GSK_PATH_DIRECTION_CLOCKWISE + : GSK_PATH_DIRECTION_COUNTERCLOCKWISE; + } + else if (c->expected_direction != dir) + { + c->first_direction = GSK_PATH_DIRECTION_UNKNOWN; + c->convexity = GSK_CONVEXITY_CONCAVE; + return FALSE; + } + graphene_vec2_init_from_vec2 (&c->last_vec, v); + break; + + case GSK_DIR_CHANGE_STRAIGHT: + break; + + case GSK_DIR_CHANGE_REVERSE: + graphene_vec2_init_from_vec2 (&c->last_vec, v); + c->reversals++; + if (c->reversals > 2) + c->convexity = GSK_CONVEXITY_CONCAVE; + return c->reversals < 3; + + case GSK_DIR_CHANGE_UNKNOWN: + c->finite = FALSE; + return FALSE; + + case GSK_DIR_CHANGE_INVALID: + default: + g_assert_not_reached (); + } + + if (graphene_vec2_get_x (v) > 0) + sign = 1; + else if (graphene_vec2_get_x (v) < 0) + sign = -1; + else + sign = 0; + + if (sign != 0) + { + if (c->xsign != 42) + { + if (c->xsign != sign) + c->dx++; + + if (c->dx > 2) + { + c->convexity = GSK_CONVEXITY_CONCAVE; + return FALSE; + } + } + c->xsign = sign; + } + + if (graphene_vec2_get_y (v) > 0) + sign = 1; + else if (graphene_vec2_get_y (v) < 0) + sign = -1; + else + sign = 0; + + if (sign != 0) + { + if (c->ysign != 42) + { + if (c->ysign != sign) + c->dy++; + + if (c->dy > 2) + { + c->convexity = GSK_CONVEXITY_CONCAVE; + return FALSE; + } + } + c->ysign = sign; + } + + return TRUE; +} + +static void +gsk_convexity_checker_init (GskConvexityChecker *c) +{ + c->first_point = GRAPHENE_POINT_INIT(0,0); + c->last_point = GRAPHENE_POINT_INIT(0,0); + graphene_vec2_init (&c->first_vec, 0, 0); + graphene_vec2_init (&c->last_vec, 0, 0); + c->expected_direction = GSK_DIR_CHANGE_INVALID; + c->first_direction = GSK_PATH_DIRECTION_UNKNOWN; + c->reversals = 0; + c->finite = TRUE; + c->convexity = GSK_CONVEXITY_UNKNOWN; + c->xsign = 42; + c->ysign = 42; + c->dx = 0; + c->dy = 0; +} + +static void +gsk_convexity_checker_move (GskConvexityChecker *c, + const graphene_point_t *p) +{ + c->first_point = c->last_point = *p; + c->expected_direction = GSK_DIR_CHANGE_INVALID; + c->convexity = GSK_CONVEXITY_CONVEX; +} + +static gboolean +gsk_convexity_checker_add_point (GskConvexityChecker *c, + const graphene_point_t *p) +{ + graphene_vec2_t v; + + if (graphene_point_equal (&c->last_point, p)) + return TRUE; + + graphene_vec2_init (&v, + p->x - c->last_point.x, + p->y - c->last_point.y); + + if (graphene_point_equal (&c->first_point, &c->last_point) && + c->expected_direction == GSK_DIR_CHANGE_INVALID) + { + graphene_vec2_init_from_vec2 (&c->last_vec, &v); + graphene_vec2_init_from_vec2 (&c->first_vec, &v); + } + else if (!add_vec (c, &v)) + { + c->convexity = GSK_CONVEXITY_CONCAVE; + return FALSE; + } + + c->last_point = *p; + return TRUE; +} + +static gboolean +gsk_convexity_checker_close (GskConvexityChecker *c) +{ + if (!(gsk_convexity_checker_add_point (c, &c->first_point) && + add_vec (c, &c->first_vec))) + { + c->convexity = GSK_CONVEXITY_CONCAVE; + return FALSE; + } + + return TRUE; +} + +static gboolean +convex_cb (GskPathOperation op, + const graphene_point_t *pts, + gsize n_pts, + float weight, + gpointer user_data) +{ + GskConvexityChecker *c = user_data; + + switch (op) + { + case GSK_PATH_MOVE: + gsk_convexity_checker_move (c, &pts[0]); + break; + case GSK_PATH_CLOSE: + if (!gsk_convexity_checker_close (c)) + return FALSE; + break; + case GSK_PATH_LINE: + if (!gsk_convexity_checker_add_point (c, &pts[1])) + return FALSE; + break; + case GSK_PATH_CURVE: + if (!gsk_convexity_checker_add_point (c, &pts[1]) || + !gsk_convexity_checker_add_point (c, &pts[2]) || + !gsk_convexity_checker_add_point (c, &pts[3])) + return FALSE; + break; + case GSK_PATH_CONIC: + if (!gsk_convexity_checker_add_point (c, &pts[1]) || + !gsk_convexity_checker_add_point (c, &pts[3])) + return FALSE; + break; + default: + g_assert_not_reached (); + } + + return TRUE; +} + +GskConvexity +gsk_contour_compute_convexity (const GskContour *contour) +{ + GskConvexityChecker c; + + gsk_convexity_checker_init (&c); + gsk_contour_foreach (contour, 0.001, convex_cb, &c); + + g_assert (c.convexity != GSK_CONVEXITY_UNKNOWN); + + return c.convexity; +} diff --git a/gsk/gskconvexityprivate.h b/gsk/gskconvexityprivate.h new file mode 100644 index 0000000000..d7953c037e --- /dev/null +++ b/gsk/gskconvexityprivate.h @@ -0,0 +1,14 @@ +#pragma once + +#include "gskcontourprivate.h" + +typedef enum +{ + GSK_CONVEXITY_UNKNOWN, + GSK_CONVEXITY_CONVEX, + GSK_CONVEXITY_CONCAVE, +} GskConvexity; + +GskConvexity gsk_contour_compute_convexity (const GskContour *contour); + + diff --git a/gsk/gskpath.c b/gsk/gskpath.c index 1ff80f05a4..0762ceab1e 100644 --- a/gsk/gskpath.c +++ b/gsk/gskpath.c @@ -1268,6 +1268,28 @@ gsk_path_reverse (GskPath *self) return gsk_path_builder_free_to_path (builder); } +/** + * gsk_path_is_convex: + * @self: a `GskPath` + * + * Returns information about whether this path is convex. + * + * A path with more than one contour is never convex. + * + * Returns: `TRUE` if @self is convex + */ +gboolean +gsk_path_is_convex (GskPath *self) +{ + if (self->n_contours == 0) + return TRUE; + + if (self->n_contours > 1) + return FALSE; + + return gsk_contour_is_convex (gsk_path_get_contour (self, 0)); +} + /** * gsk_path_stroke: * @self: a `GskPath` diff --git a/gsk/gskpath.h b/gsk/gskpath.h index a94101fd80..bbc8b39884 100644 --- a/gsk/gskpath.h +++ b/gsk/gskpath.h @@ -103,6 +103,9 @@ gboolean gsk_path_get_stroke_bounds (GskPath const GskStroke *stroke, graphene_rect_t *bounds); +GDK_AVAILABLE_IN_ALL +gboolean gsk_path_is_convex (GskPath *self); + GDK_AVAILABLE_IN_ALL gboolean gsk_path_foreach (GskPath *self, GskPathForeachFlags flags, diff --git a/gsk/meson.build b/gsk/meson.build index cf255c88c4..b4be720e05 100644 --- a/gsk/meson.build +++ b/gsk/meson.build @@ -44,6 +44,7 @@ gsk_private_sources = files([ 'gskboundingbox.c', 'gskcairoblur.c', 'gskcontour.c', + 'gskconvexity.c', 'gskcurve.c', 'gskcurveintersect.c', 'gskdebug.c', diff --git a/testsuite/gsk/path.c b/testsuite/gsk/path.c index 60e45a0941..f260155281 100644 --- a/testsuite/gsk/path.c +++ b/testsuite/gsk/path.c @@ -45,7 +45,7 @@ create_random_degenerate_path (guint max_contours) case 1: /* a single point */ - gsk_path_builder_move_to (builder, + gsk_path_builder_move_to (builder, g_test_rand_double_range (-1000, 1000), g_test_rand_double_range (-1000, 1000)); break; @@ -54,7 +54,7 @@ create_random_degenerate_path (guint max_contours) /* N points */ for (i = 0; i < MIN (10, max_contours); i++) { - gsk_path_builder_move_to (builder, + gsk_path_builder_move_to (builder, g_test_rand_double_range (-1000, 1000), g_test_rand_double_range (-1000, 1000)); } @@ -62,7 +62,7 @@ create_random_degenerate_path (guint max_contours) case 3: /* 1 closed point */ - gsk_path_builder_move_to (builder, + gsk_path_builder_move_to (builder, g_test_rand_double_range (-1000, 1000), g_test_rand_double_range (-1000, 1000)); gsk_path_builder_close (builder); @@ -70,7 +70,7 @@ create_random_degenerate_path (guint max_contours) case 4: /* the same point closed N times */ - gsk_path_builder_move_to (builder, + gsk_path_builder_move_to (builder, g_test_rand_double_range (-1000, 1000), g_test_rand_double_range (-1000, 1000)); for (i = 0; i < MIN (10, max_contours); i++) @@ -440,7 +440,7 @@ path_operation_equal (const PathOperation *p1, } } -static gboolean +static gboolean collect_path_operation_cb (GskPathOperation op, const graphene_point_t *pts, gsize n_pts, @@ -1115,7 +1115,7 @@ test_in_fill_rotated (void) GskFillRule fill_rule = g_random_int_range (0, N_FILL_RULES); float x = g_test_rand_double_range (-1000, 1000); float y = g_test_rand_double_range (-1000, 1000); - + g_assert_cmpint (gsk_path_measure_in_fill (measures[0], &GRAPHENE_POINT_INIT (x, y), fill_rule), ==, gsk_path_measure_in_fill (measures[1], &GRAPHENE_POINT_INIT (y, -x), fill_rule)); @@ -1229,6 +1229,74 @@ test_path_stroke_distance (void) gsk_stroke_free (stroke); } +static void +test_path_convexity (void) +{ + GskPathBuilder *builder; + GskPath *path; + + builder = gsk_path_builder_new (); + gsk_path_builder_add_circle (builder, &GRAPHENE_POINT_INIT (100, 100), 100); + path = gsk_path_builder_free_to_path (builder); + + g_assert_true (gsk_path_is_convex (path)); + + gsk_path_unref (path); + + builder = gsk_path_builder_new (); + gsk_path_builder_add_circle (builder, &GRAPHENE_POINT_INIT (100, 100), 100); + gsk_path_builder_add_circle (builder, &GRAPHENE_POINT_INIT (100, 100), 10); + path = gsk_path_builder_free_to_path (builder); + + g_assert_false (gsk_path_is_convex (path)); + + gsk_path_unref (path); + + builder = gsk_path_builder_new (); + gsk_path_builder_add_rect (builder, &GRAPHENE_RECT_INIT (9, 0, 100, 100)); + path = gsk_path_builder_free_to_path (builder); + + g_assert_true (gsk_path_is_convex (path)); + + gsk_path_unref (path); + + path = gsk_path_parse ("M 100 100 C 150 50 200 50 250 100 C 200 150 150 150 100 100 Z"); + + g_assert_true (gsk_path_is_convex (path)); + + gsk_path_unref (path); + + path = gsk_path_parse ("M 100 100 L 150 50 L 200 100 L 250 50 L 300 100 L 200 200 Z"); + + g_assert_false (gsk_path_is_convex (path)); + + gsk_path_unref (path); + + /* Cantarell M, only turns in one direction, but winds around several times */ + path = gsk_path_parse ("M 185.70745849609375 704 " + "L 282.899658203125 704 " + "L 282.899658203125 150.52880859375 " + "L 265.08203125 156.04779052734375 " + "L 491.34271240234375 596.20440673828125 " + "L 569.83355712890625 596.20440673828125 " + "L 792.276611328125 156.04779052734375 " + "L 780.48101806640625 151.55084228515625 " + "L 780.48101806640625 704 " + "L 877.6732177734375 704 " + "L 877.6732177734375 10 " + "L 778.70745849609375 10 " + "L 507.47491455078125 540.8739013671875 " + "L 561.7674560546875 540.8739013671875 " + "L 287.46881103515625 10 " + "L 185.70745849609375 10 " + "L 185.70745849609375 704 " + "Z"); + + g_assert_false (gsk_path_is_convex (path)); + + gsk_path_unref (path); +} + int main (int argc, char *argv[]) @@ -1247,6 +1315,7 @@ main (int argc, g_test_add_func ("/path/in-fill-union", test_in_fill_union); g_test_add_func ("/path/in-fill-rotated", test_in_fill_rotated); g_test_add_func ("/path/stroke/distance", test_path_stroke_distance); + g_test_add_func ("/path/convexity", test_path_convexity); return g_test_run (); } -- cgit v1.2.1