[gtk/path-work-rebased: 64/71] path: Add gsk_path_is_convex
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/path-work-rebased: 64/71] path: Add gsk_path_is_convex
- Date: Fri, 8 Apr 2022 20:45:38 +0000 (UTC)
commit def04f5df3444f9c752f6883c8b4c6007983b4fb
Author: Matthias Clasen <mclasen redhat com>
Date: Tue Mar 22 00:33:09 2022 -0400
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(-)
---
diff --git a/gsk/gskcontour.c b/gsk/gskcontour.c
index 1f40fccda6..359a070153 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 *
@@ -990,6 +999,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),
@@ -1012,6 +1027,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 *
@@ -1046,6 +1062,7 @@ struct _GskStandardContour
GskContour contour;
GskPathFlags flags;
+ GskConvexity convexity;
gsize n_ops;
gsize n_points;
@@ -1820,6 +1837,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),
@@ -1842,6 +1870,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,
@@ -1863,6 +1892,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];
@@ -2065,6 +2095,12 @@ 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);
+}
+
/* }}} */
/* vim:set foldmethod=marker expandtab: */
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 2967569c4f..10f8aff0ce 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 ();
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
