diff options
author | Benjamin Otte <otte@redhat.com> | 2020-11-17 19:04:21 +0100 |
---|---|---|
committer | Benjamin Otte <otte@redhat.com> | 2020-11-26 01:51:26 +0100 |
commit | b7a365ce02970d329d661c93a6f1e61db981d4e6 (patch) | |
tree | b7cd49563d61ef75cad6bc575b01dd1ec4571329 | |
parent | fa4e03caf3ef8b40a5cc02d1a72beffba2ec073d (diff) | |
download | gtk+-b7a365ce02970d329d661c93a6f1e61db981d4e6.tar.gz |
pathmeasure: Implement support for beziers
Instead of treating bezier curves as lines, we properly decompose them
into line segments now so that we can treat those as lines.
-rw-r--r-- | gsk/gskpath.c | 279 | ||||
-rw-r--r-- | gsk/gskpathmeasure.c | 23 | ||||
-rw-r--r-- | gsk/gskpathmeasure.h | 3 | ||||
-rw-r--r-- | gsk/gskpathprivate.h | 1 | ||||
-rw-r--r-- | gsk/gskspline.c | 179 | ||||
-rw-r--r-- | gsk/gsksplineprivate.h | 46 | ||||
-rw-r--r-- | gsk/meson.build | 1 |
7 files changed, 461 insertions, 71 deletions
diff --git a/gsk/gskpath.c b/gsk/gskpath.c index 52cf5181d2..a16b9f7c49 100644 --- a/gsk/gskpath.c +++ b/gsk/gskpath.c @@ -21,6 +21,8 @@ #include "gskpathprivate.h" +#include "gsksplineprivate.h" + /** * SECTION:gskpath * @Title: Path @@ -65,6 +67,7 @@ struct _GskContourClass GskPathForeachFunc func, gpointer user_data); gpointer (* init_measure) (const GskContour *contour, + float tolerance, float *out_length); void (* free_measure) (const GskContour *contour, gpointer measure_data); @@ -173,6 +176,7 @@ gsk_rect_contour_foreach (const GskContour *contour, static gpointer gsk_rect_contour_init_measure (const GskContour *contour, + float tolerance, float *out_length) { const GskRectContour *self = (const GskRectContour *) contour; @@ -451,14 +455,54 @@ gsk_standard_contour_get_bounds (const GskContour *contour, return bounds->size.width > 0 && bounds->size.height > 0; } +typedef struct +{ + float start; + float end; + float start_progress; + float end_progress; + graphene_point_t end_point; + gsize op; +} GskStandardContourMeasure; + +typedef struct +{ + GArray *array; + GskStandardContourMeasure measure; +} LengthDecompose; + +static void +gsk_standard_contour_measure_add_point (const graphene_point_t *from, + const graphene_point_t *to, + float from_progress, + float to_progress, + gpointer user_data) +{ + LengthDecompose *decomp = user_data; + float seg_length; + + seg_length = graphene_point_distance (from, to, NULL, NULL); + decomp->measure.end += seg_length; + decomp->measure.start_progress = from_progress; + decomp->measure.end_progress = to_progress; + decomp->measure.end_point = *to; + + g_array_append_val (decomp->array, decomp->measure); + + decomp->measure.start += seg_length; +} + static gpointer gsk_standard_contour_init_measure (const GskContour *contour, + float tolerance, float *out_length) { const GskStandardContour *self = (const GskStandardContour *) contour; gsize i; - float length; + float length, seg_length; + GArray *array; + array = g_array_new (FALSE, FALSE, sizeof (GskStandardContourMeasure)); length = 0; for (i = 1; i < self->n_ops; i ++) @@ -472,12 +516,27 @@ gsk_standard_contour_init_measure (const GskContour *contour, case GSK_PATH_CLOSE: case GSK_PATH_LINE: - length += graphene_point_distance (&pt[0], &pt[1], NULL, NULL); + seg_length = graphene_point_distance (&pt[0], &pt[1], NULL, NULL); + if (seg_length > 0) + { + g_array_append_vals (array, + &(GskStandardContourMeasure) { + length, + length + seg_length, + 0, 1, + pt[1], + i, + }, 1); + length += seg_length; + } break; case GSK_PATH_CURVE: - g_warning ("i'm not fat!"); - length += graphene_point_distance (&pt[0], &pt[3], NULL, NULL); + { + LengthDecompose decomp = { array, { length, length, 0, 0, pt[0], i } }; + gsk_spline_decompose_cubic (pt, tolerance, gsk_standard_contour_measure_add_point, &decomp); + length = decomp.measure.start; + } break; default: @@ -488,13 +547,14 @@ gsk_standard_contour_init_measure (const GskContour *contour, *out_length = length; - return NULL; + return array; } static void gsk_standard_contour_free_measure (const GskContour *contour, gpointer data) { + g_array_free (data, TRUE); } static void @@ -514,6 +574,21 @@ gsk_standard_contour_copy (const GskContour *contour, gsk_standard_contour_init (dest, self->flags, self->ops, self->n_ops, self->points, self->n_points); } +static int +gsk_standard_contour_find_measure (gconstpointer m, + gconstpointer l) +{ + const GskStandardContourMeasure *measure = m; + float length = *(const float *) l; + + if (measure->start > length) + return 1; + else if (measure->end <= length) + return -1; + else + return 0; +} + static void gsk_standard_contour_add_segment (const GskContour *contour, GskPathBuilder *builder, @@ -522,87 +597,145 @@ gsk_standard_contour_add_segment (const GskContour *contour, float end) { GskStandardContour *self = (GskStandardContour *) contour; + GArray *array = measure_data; + guint start_index, end_index; + float start_progress, end_progress; + GskStandardContourMeasure *start_measure, *end_measure; gsize i; - float length; - for (i = 0; end > 0 && i < self->n_ops; i ++) + if (start > 0) + { + if (!g_array_binary_search (array, (float[1]) { start }, gsk_standard_contour_find_measure, &start_index)) + start_index = array->len - 1; + start_measure = &g_array_index (array, GskStandardContourMeasure, start_index); + start_progress = (start - start_measure->start) / (start_measure->end - start_measure->start); + start_progress = start_measure->start_progress + (start_measure->end_progress - start_measure->start_progress) * start_progress; + g_assert (start_progress >= 0 && start_progress <= 1); + } + else + { + start_measure = NULL; + start_progress = 0.0; + } + + if (g_array_binary_search (array, (float[1]) { end }, gsk_standard_contour_find_measure, &end_index)) + { + end_measure = &g_array_index (array, GskStandardContourMeasure, end_index); + end_progress = (end - end_measure->start) / (end_measure->end - end_measure->start); + end_progress = end_measure->start_progress + (end_measure->end_progress - end_measure->start_progress) * end_progress; + g_assert (end_progress >= 0 && end_progress <= 1); + } + else + { + end_measure = NULL; + end_progress = 1.0; + } + + /* Add the first partial operation, + * taking care that first and last operation might be identical */ + if (start_measure) + { + switch (self->ops[start_measure->op].op) + { + case GSK_PATH_CLOSE: + case GSK_PATH_LINE: + { + graphene_point_t *pts = &self->points[self->ops[start_measure->op].point]; + graphene_point_t point; + + graphene_point_interpolate (&pts[0], &pts[1], start_progress, &point); + gsk_path_builder_move_to (builder, point.x, point.y); + if (end_measure && end_measure->op == start_measure->op) + { + graphene_point_interpolate (&pts[0], &pts[1], end_progress, &point); + gsk_path_builder_line_to (builder, point.x, point.y); + return; + } + gsk_path_builder_line_to (builder, pts[1].x, pts[1].y); + } + break; + + case GSK_PATH_CURVE: + { + graphene_point_t *pts = &self->points[self->ops[start_measure->op].point]; + graphene_point_t curve[4], discard[4]; + + gsk_spline_split_cubic (pts, discard, curve, start_progress); + if (end_measure && end_measure->op == start_measure->op) + { + graphene_point_t tiny[4]; + gsk_spline_split_cubic (curve, tiny, discard, (end_progress - start_progress) / (1 - start_progress)); + gsk_path_builder_move_to (builder, tiny[0].x, tiny[0].y); + gsk_path_builder_curve_to (builder, tiny[1].x, tiny[1].y, tiny[2].x, tiny[2].y, tiny[3].x, tiny[3].y); + return; + } + gsk_path_builder_move_to (builder, curve[0].x, curve[0].y); + gsk_path_builder_curve_to (builder, curve[1].x, curve[1].y, curve[2].x, curve[2].y, curve[3].x, curve[3].y); + } + break; + + case GSK_PATH_MOVE: + default: + g_assert_not_reached(); + return; + } + i = start_measure->op + 1; + } + else + i = 0; + + for (; i < (end_measure ? end_measure->op : self->n_ops); i++) { graphene_point_t *pt = &self->points[self->ops[i].point]; switch (self->ops[i].op) { case GSK_PATH_MOVE: - if (start <= 0.0) - { - gsk_path_builder_move_to (builder, pt[0].x, pt[0].y); - start = -1; - } + gsk_path_builder_move_to (builder, pt[0].x, pt[0].y); break; + case GSK_PATH_LINE: + case GSK_PATH_CLOSE: + gsk_path_builder_line_to (builder, pt[1].x, pt[1].y); + break; + + case GSK_PATH_CURVE: + gsk_path_builder_curve_to (builder, pt[1].x, pt[1].y, pt[2].x, pt[2].y, pt[3].x, pt[3].y); + break; + + default: + g_assert_not_reached(); + return; + } + } + + /* Add the last partial operation */ + if (end_measure) + { + switch (self->ops[end_measure->op].op) + { case GSK_PATH_CLOSE: case GSK_PATH_LINE: - length = graphene_point_distance (&pt[0], &pt[1], NULL, NULL); - if (length <= start) - { - start -= length; - end -= length; - } - else - { - if (start >= 0) - { - graphene_point_t start_pt; - graphene_point_interpolate (&pt[0], &pt[1], start / length, &start_pt); - gsk_path_builder_move_to (builder, start_pt.x, start_pt.y); - start = -1; - } - if (length <= end) - { - gsk_path_builder_line_to (builder, pt[1].x, pt[1].y); - end -= length; - } - else - { - graphene_point_t end_pt; - graphene_point_interpolate (&pt[0], &pt[1], end / length, &end_pt); - gsk_path_builder_line_to (builder, end_pt.x, end_pt.y); - return; - } - } + { + graphene_point_t *pts = &self->points[self->ops[end_measure->op].point]; + graphene_point_t point; + + graphene_point_interpolate (&pts[0], &pts[1], end_progress, &point); + gsk_path_builder_line_to (builder, point.x, point.y); + } break; case GSK_PATH_CURVE: - g_warning ("i'm not fat!"); - length = graphene_point_distance (&pt[0], &pt[3], NULL, NULL); - if (length <= start) - { - start -= length; - end -= length; - } - else - { - if (start >= 0) - { - graphene_point_t start_pt; - graphene_point_interpolate (&pt[0], &pt[3], start / length, &start_pt); - gsk_path_builder_move_to (builder, start_pt.x, start_pt.y); - start = -1; - } - if (length <= end) - { - gsk_path_builder_line_to (builder, pt[3].x, pt[3].y); - end -= length; - } - else - { - graphene_point_t end_pt; - graphene_point_interpolate (&pt[0], &pt[3], end / length, &end_pt); - gsk_path_builder_line_to (builder, end_pt.x, end_pt.y); - return; - } - } + { + graphene_point_t *pts = &self->points[self->ops[end_measure->op].point]; + graphene_point_t curve[4], discard[4]; + + gsk_spline_split_cubic (pts, curve, discard, end_progress); + gsk_path_builder_curve_to (builder, curve[1].x, curve[1].y, curve[2].x, curve[2].y, curve[3].x, curve[3].y); + } break; + case GSK_PATH_MOVE: default: g_assert_not_reached(); return; @@ -686,11 +819,12 @@ gsk_contour_foreach (const GskContour *contour, gpointer gsk_contour_init_measure (GskPath *path, gsize i, + float tolerance, float *out_length) { GskContour *self = path->contours[i]; - return self->klass->init_measure (self, out_length); + return self->klass->init_measure (self, tolerance, out_length); } void @@ -1414,6 +1548,11 @@ gsk_path_builder_line_to (GskPathBuilder *builder, return; } + /* skip the line if it goes to the same point */ + if (graphene_point_equal (&g_array_index (builder->points, graphene_point_t, builder->points->len - 1), + &GRAPHENE_POINT_INIT (x, y))) + return; + gsk_path_builder_append_current (builder, GSK_PATH_LINE, 1, (graphene_point_t[1]) { diff --git a/gsk/gskpathmeasure.c b/gsk/gskpathmeasure.c index 7fd0eeb65d..a0a7574e0a 100644 --- a/gsk/gskpathmeasure.c +++ b/gsk/gskpathmeasure.c @@ -47,6 +47,7 @@ struct _GskPathMeasure guint ref_count; GskPath *path; + float tolerance; float length; gsize n_contours; @@ -75,10 +76,27 @@ G_DEFINE_BOXED_TYPE (GskPathMeasure, gsk_path_measure, GskPathMeasure * gsk_path_measure_new (GskPath *path) { + return gsk_path_measure_new_with_tolerance (path, GSK_PATH_TOLERANCE_DEFAULT); +} + +/** + * gsk_path_measure_new: + * @path: the path to measure + * @tolerance: the tolerance for measuring operations + * + * Creates a measure object for the given @path and @tolerance. + * + * Returns: a new #GskPathMeasure representing @path + **/ +GskPathMeasure * +gsk_path_measure_new_with_tolerance (GskPath *path, + float tolerance) +{ GskPathMeasure *self; gsize i, n_contours; g_return_val_if_fail (path != NULL, NULL); + g_return_val_if_fail (tolerance > 0, NULL); n_contours = gsk_path_get_n_contours (path); @@ -86,11 +104,14 @@ gsk_path_measure_new (GskPath *path) self->ref_count = 1; self->path = gsk_path_ref (path); + self->tolerance = tolerance; self->n_contours = n_contours; for (i = 0; i < n_contours; i++) { - self->measures[i].contour_data = gsk_contour_init_measure (path, i, &self->measures[i].length); + self->measures[i].contour_data = gsk_contour_init_measure (path, i, + self->tolerance, + &self->measures[i].length); self->length += self->measures[i].length; } diff --git a/gsk/gskpathmeasure.h b/gsk/gskpathmeasure.h index abf4202eb6..f38e77302b 100644 --- a/gsk/gskpathmeasure.h +++ b/gsk/gskpathmeasure.h @@ -35,6 +35,9 @@ GDK_AVAILABLE_IN_ALL GType gsk_path_measure_get_type (void) G_GNUC_CONST; GDK_AVAILABLE_IN_ALL GskPathMeasure * gsk_path_measure_new (GskPath *path); +GDK_AVAILABLE_IN_ALL +GskPathMeasure * gsk_path_measure_new_with_tolerance (GskPath *path, + float tolerance); GDK_AVAILABLE_IN_ALL GskPathMeasure * gsk_path_measure_ref (GskPathMeasure *self); diff --git a/gsk/gskpathprivate.h b/gsk/gskpathprivate.h index afee649ce1..6c51d09524 100644 --- a/gsk/gskpathprivate.h +++ b/gsk/gskpathprivate.h @@ -36,6 +36,7 @@ gboolean gsk_path_foreach_with_tolerance (GskPath gpointer gsk_contour_init_measure (GskPath *path, gsize i, + float tolerance, float *out_length); void gsk_contour_free_measure (GskPath *path, gsize i, diff --git a/gsk/gskspline.c b/gsk/gskspline.c new file mode 100644 index 0000000000..03223915bf --- /dev/null +++ b/gsk/gskspline.c @@ -0,0 +1,179 @@ +/* + * Copyright © 2002 University of Southern California + * 2020 Benjamin Otte + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see <http://www.gnu.org/licenses/>. + * + * Authors: Benjamin Otte <otte@gnome.org> + * Carl D. Worth <cworth@cworth.org> + */ + +#include "config.h" + +#include "gsksplineprivate.h" + +typedef struct +{ + graphene_point_t last_point; + float last_progress; + float tolerance_squared; + GskSplineAddPointFunc func; + gpointer user_data; +} GskCubicDecomposition; + +static void +gsk_spline_decompose_add_point (GskCubicDecomposition *decomp, + const graphene_point_t *pt, + float progress) +{ + if (graphene_point_equal (&decomp->last_point, pt)) + return; + + decomp->func (&decomp->last_point, pt, decomp->last_progress, decomp->last_progress + progress, decomp->user_data); + decomp->last_point = *pt; + decomp->last_progress += progress; +} + +void +gsk_spline_split_cubic (const graphene_point_t pts[4], + graphene_point_t result1[4], + graphene_point_t result2[4], + float progress) +{ + graphene_point_t ab, bc, cd; + graphene_point_t abbc, bccd; + graphene_point_t final; + + graphene_point_interpolate (&pts[0], &pts[1], progress, &ab); + graphene_point_interpolate (&pts[1], &pts[2], progress, &bc); + graphene_point_interpolate (&pts[2], &pts[3], progress, &cd); + graphene_point_interpolate (&ab, &bc, progress, &abbc); + graphene_point_interpolate (&bc, &cd, progress, &bccd); + graphene_point_interpolate (&abbc, &bccd, progress, &final); + + memcpy (result1, (graphene_point_t[4]) { pts[0], ab, abbc, final }, sizeof (graphene_point_t[4])); + memcpy (result2, (graphene_point_t[4]) { final, bccd, cd, pts[3] }, sizeof (graphene_point_t[4])); +} + +/* Return an upper bound on the error (squared) that could result from + * approximating a spline as a line segment connecting the two endpoints. */ +static float +gsk_spline_error_squared (const graphene_point_t pts[4]) +{ + float bdx, bdy, berr; + float cdx, cdy, cerr; + + /* We are going to compute the distance (squared) between each of the the b + * and c control points and the segment a-b. The maximum of these two + * distances will be our approximation error. */ + + bdx = pts[1].x - pts[0].x; + bdy = pts[1].y - pts[0].y; + + cdx = pts[2].x - pts[0].x; + cdy = pts[2].y - pts[0].y; + + if (!graphene_point_equal (&pts[0], &pts[3])) + { + float dx, dy, u, v; + + /* Intersection point (px): + * px = p1 + u(p2 - p1) + * (p - px) ∙ (p2 - p1) = 0 + * Thus: + * u = ((p - p1) ∙ (p2 - p1)) / ∥p2 - p1∥²; + */ + + dx = pts[3].x - pts[0].x; + dy = pts[3].y - pts[0].y; + v = dx * dx + dy * dy; + + u = bdx * dx + bdy * dy; + if (u <= 0) + { + /* bdx -= 0; + * bdy -= 0; + */ + } + else if (u >= v) + { + bdx -= dx; + bdy -= dy; + } + else + { + bdx -= u/v * dx; + bdy -= u/v * dy; + } + + u = cdx * dx + cdy * dy; + if (u <= 0) + { + /* cdx -= 0; + * cdy -= 0; + */ + } + else if (u >= v) + { + cdx -= dx; + cdy -= dy; + } + else + { + cdx -= u/v * dx; + cdy -= u/v * dy; + } + } + + berr = bdx * bdx + bdy * bdy; + cerr = cdx * cdx + cdy * cdy; + if (berr > cerr) + return berr; + else + return cerr; +} + +static void +gsk_spline_decompose_into (GskCubicDecomposition *decomp, + const graphene_point_t pts[4], + float progress) +{ + graphene_point_t left[4], right[4]; + + if (gsk_spline_error_squared (pts) < decomp->tolerance_squared) + { + gsk_spline_decompose_add_point (decomp, &pts[3], progress); + return; + } + + gsk_spline_split_cubic (pts, left, right, 0.5); + + gsk_spline_decompose_into (decomp, left, progress / 2); + gsk_spline_decompose_into (decomp, right, progress / 2); +} + +void +gsk_spline_decompose_cubic (const graphene_point_t pts[4], + float tolerance, + GskSplineAddPointFunc add_point_func, + gpointer user_data) +{ + GskCubicDecomposition decomp = { pts[0], 0.0f, tolerance * tolerance, add_point_func, user_data }; + + gsk_spline_decompose_into (&decomp, pts, 1.0f); + + g_assert (graphene_point_equal (&decomp.last_point, &pts[3])); + g_assert (decomp.last_progress == 1.0f || decomp.last_progress == 0.0f); +} + diff --git a/gsk/gsksplineprivate.h b/gsk/gsksplineprivate.h new file mode 100644 index 0000000000..5df41077d3 --- /dev/null +++ b/gsk/gsksplineprivate.h @@ -0,0 +1,46 @@ +/* + * Copyright © 2020 Benjamin Otte + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see <http://www.gnu.org/licenses/>. + * + * Authors: Benjamin Otte <otte@gnome.org> + */ + + +#ifndef __GSK_SPLINE_PRIVATE_H__ +#define __GSK_SPLINE_PRIVATE_H__ + +#include "gskpath.h" + +G_BEGIN_DECLS + +typedef void (* GskSplineAddPointFunc) (const graphene_point_t *from, + const graphene_point_t *to, + float from_progress, + float to_progress, + gpointer user_data); + +void gsk_spline_split_cubic (const graphene_point_t pts[4], + graphene_point_t result1[4], + graphene_point_t result2[4], + float progress); +void gsk_spline_decompose_cubic (const graphene_point_t pts[4], + float tolerance, + GskSplineAddPointFunc add_point_func, + gpointer user_data); + +G_END_DECLS + +#endif /* __GSK_SPLINE_PRIVATE_H__ */ + diff --git a/gsk/meson.build b/gsk/meson.build index a5ee24fb70..a40b7b6e70 100644 --- a/gsk/meson.build +++ b/gsk/meson.build @@ -40,6 +40,7 @@ gsk_private_sources = files([ 'gskdebug.c', 'gskprivate.c', 'gskprofiler.c', + 'gskspline.c', 'gl/gskglshaderbuilder.c', 'gl/gskglprofiler.c', 'gl/gskglglyphcache.c', |