From 924f0bc2c5fe3eb4937d8aa702df9e3324d21c5b Mon Sep 17 00:00:00 2001 From: Benjamin Otte Date: Sun, 6 Dec 2020 18:46:08 +0100 Subject: path: Add GskCurve GskCurve is an abstraction for path operations. It's essentially a collection of vfuncs per GskPathOperation. GskStandardContour has been ported to use it where appropriate. --- gsk/gskcontour.c | 240 ++++------------- gsk/gskcurve.c | 705 +++++++++++++++++++++++++++++++++++++++++++++++++ gsk/gskcurveprivate.h | 108 ++++++++ gsk/gskpath.c | 71 ++--- gsk/gskpathopprivate.h | 1 + gsk/gskpathprivate.h | 1 + gsk/gskspline.c | 378 -------------------------- gsk/gsksplineprivate.h | 32 --- gsk/meson.build | 3 +- 9 files changed, 901 insertions(+), 638 deletions(-) create mode 100644 gsk/gskcurve.c create mode 100644 gsk/gskcurveprivate.h diff --git a/gsk/gskcontour.c b/gsk/gskcontour.c index 359356d838..528540d2ad 100644 --- a/gsk/gskcontour.c +++ b/gsk/gskcontour.c @@ -21,6 +21,7 @@ #include "gskcontourprivate.h" +#include "gskcurveprivate.h" #include "gskpathbuilder.h" #include "gskpathprivate.h" #include "gsksplineprivate.h" @@ -1047,7 +1048,7 @@ typedef struct GskStandardContourMeasure measure; } LengthDecompose; -static void +static gboolean gsk_standard_contour_measure_add_point (const graphene_point_t *from, const graphene_point_t *to, float from_progress, @@ -1058,6 +1059,9 @@ gsk_standard_contour_measure_add_point (const graphene_point_t *from, float seg_length; seg_length = graphene_point_distance (from, to, NULL, NULL); + if (seg_length == 0) + return TRUE; + decomp->measure.end += seg_length; decomp->measure.start_progress = from_progress; decomp->measure.end_progress = to_progress; @@ -1066,6 +1070,8 @@ gsk_standard_contour_measure_add_point (const graphene_point_t *from, g_array_append_val (decomp->array, decomp->measure); decomp->measure.start += seg_length; + + return TRUE; } static gpointer @@ -1075,7 +1081,7 @@ gsk_standard_contour_init_measure (const GskContour *contour, { const GskStandardContour *self = (const GskStandardContour *) contour; gsize i; - float length, seg_length; + float length; GArray *array; array = g_array_new (FALSE, FALSE, sizeof (GskStandardContourMeasure)); @@ -1083,50 +1089,12 @@ gsk_standard_contour_init_measure (const GskContour *contour, for (i = 1; i < self->n_ops; i ++) { - const graphene_point_t *pt = gsk_pathop_points (self->ops[i]); - - switch (gsk_pathop_op (self->ops[i])) - { - case GSK_PATH_MOVE: - break; + GskCurve curve; + LengthDecompose decomp = { array, { length, length, 0, 0, { }, i } }; - case GSK_PATH_CLOSE: - case GSK_PATH_LINE: - 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: - { - 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; - - case GSK_PATH_CONIC: - { - LengthDecompose decomp = { array, { length, length, 0, 0, pt[0], i } }; - gsk_spline_decompose_conic (pt, tolerance, gsk_standard_contour_measure_add_point, &decomp); - length = decomp.measure.start; - } - break; - - default: - g_assert_not_reached(); - return NULL; - } + gsk_curve_init (&curve, self->ops[i]); + gsk_curve_decompose (&curve, tolerance, gsk_standard_contour_measure_add_point, &decomp); + length = decomp.measure.start; } *out_length = length; @@ -1163,35 +1131,11 @@ gsk_standard_contour_measure_get_point (GskStandardContour *self, graphene_point_t *pos, graphene_vec2_t *tangent) { - const graphene_point_t *pts; + GskCurve curve; - pts = gsk_pathop_points (self->ops[op]); - switch (gsk_pathop_op (self->ops[op])) - { - case GSK_PATH_LINE: - case GSK_PATH_CLOSE: - if (pos) - graphene_point_interpolate (&pts[0], &pts[1], progress, pos); - if (tangent) - { - graphene_vec2_init (tangent, pts[1].x - pts[0].x, pts[1].y - pts[0].y); - graphene_vec2_normalize (tangent, tangent); - } - break; - - case GSK_PATH_CURVE: - gsk_spline_get_point_cubic (pts, progress, pos, tangent); - break; - - case GSK_PATH_CONIC: - gsk_spline_get_point_conic (pts, progress, pos, tangent); - break; - - case GSK_PATH_MOVE: - default: - g_assert_not_reached (); - return; - } + gsk_curve_init (&curve, self->ops[op]); + + gsk_curve_eval (&curve, progress, pos, tangent); } static void @@ -1382,144 +1326,52 @@ gsk_standard_contour_add_segment (const GskContour *contour, * taking care that first and last operation might be identical */ if (start_measure) { - switch (gsk_pathop_op (self->ops[start_measure->op])) - { - case GSK_PATH_CLOSE: - case GSK_PATH_LINE: - { - const graphene_point_t *pts = gsk_pathop_points (self->ops[start_measure->op]); - 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; + GskCurve curve, cut; + const graphene_point_t *start_point; - case GSK_PATH_CURVE: - { - const graphene_point_t *pts = gsk_pathop_points (self->ops[start_measure->op]); - 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; + gsk_curve_init (&curve, self->ops[start_measure->op]); - case GSK_PATH_CONIC: - { - const graphene_point_t *pts = gsk_pathop_points (self->ops[start_measure->op]); - graphene_point_t curve[4], discard[4]; - - gsk_spline_split_conic (pts, discard, curve, start_progress); - if (end_measure && end_measure->op == start_measure->op) - { - graphene_point_t tiny[4]; - gsk_spline_split_conic (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_conic_to (builder, tiny[1].x, tiny[1].y, tiny[3].x, tiny[3].y, tiny[2].x); - return; - } - gsk_path_builder_move_to (builder, curve[0].x, curve[0].y); - gsk_path_builder_conic_to (builder, curve[1].x, curve[1].y, curve[3].x, curve[3].y, curve[2].x); - } - break; + gsk_curve_split (&curve, start_progress, NULL, &cut); + start_point = gsk_curve_get_start_point (&cut); + gsk_path_builder_move_to (builder, start_point->x, start_point->y); - case GSK_PATH_MOVE: - default: - g_assert_not_reached(); + if (end_measure && end_measure->op == start_measure->op) + { + GskCurve cut2; + + gsk_curve_split (&cut, (end_progress - start_progress) / (1 - start_progress), &cut2, NULL); + gsk_curve_builder_to (&cut2, builder); return; - } + } + + gsk_curve_builder_to (&cut, builder); i = start_measure->op + 1; } else i = 0; - for (; i < (end_measure ? end_measure->op : self->n_ops); i++) + for (; i < (end_measure ? end_measure->op : self->n_ops - 1); i++) { - const graphene_point_t *pt = gsk_pathop_points (self->ops[i]); - - switch (gsk_pathop_op (self->ops[i])) - { - case GSK_PATH_MOVE: - 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; - - case GSK_PATH_CONIC: - gsk_path_builder_conic_to (builder, pt[1].x, pt[1].y, pt[3].x, pt[3].y, pt[2].x); - break; - - default: - g_assert_not_reached(); - return; - } + gsk_path_builder_pathop_to (builder, self->ops[i]); } /* Add the last partial operation */ if (end_measure) { - switch (gsk_pathop_op (self->ops[end_measure->op])) - { - case GSK_PATH_CLOSE: - case GSK_PATH_LINE: - { - const graphene_point_t *pts = gsk_pathop_points (self->ops[end_measure->op]); - 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; + GskCurve curve, cut; - case GSK_PATH_CURVE: - { - const graphene_point_t *pts = gsk_pathop_points (self->ops[end_measure->op]); - 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_CONIC: - { - const graphene_point_t *pts = gsk_pathop_points (self->ops[end_measure->op]); - graphene_point_t curve[4], discard[4]; + gsk_curve_init (&curve, self->ops[end_measure->op]); - gsk_spline_split_conic (pts, curve, discard, end_progress); - gsk_path_builder_conic_to (builder, curve[1].x, curve[1].y, curve[3].x, curve[3].y, curve[2].x); - } - break; - - case GSK_PATH_MOVE: - default: - g_assert_not_reached(); - return; - } + gsk_curve_split (&curve, end_progress, &cut, NULL); + gsk_curve_builder_to (&cut, builder); + } + else if (i == self->n_ops - 1) + { + gskpathop op = self->ops[i]; + if (gsk_pathop_op (op) == GSK_PATH_CLOSE) + gsk_path_builder_pathop_to (builder, gsk_pathop_encode (GSK_PATH_LINE, gsk_pathop_points (op))); + else + gsk_path_builder_pathop_to (builder, op); } } diff --git a/gsk/gskcurve.c b/gsk/gskcurve.c new file mode 100644 index 0000000000..2ecd3be146 --- /dev/null +++ b/gsk/gskcurve.c @@ -0,0 +1,705 @@ +/* + * 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 . + * + * Authors: Benjamin Otte + */ + +#include "config.h" + +#include "gskcurveprivate.h" + +#define MIN_PROGRESS (1/1024.f) + +typedef struct _GskCurveClass GskCurveClass; + +struct _GskCurveClass +{ + void (* init) (GskCurve *curve, + gskpathop op); + void (* eval) (const GskCurve *curve, + float progress, + graphene_point_t *pos, + graphene_vec2_t *tangent); + void (* split) (const GskCurve *curve, + float progress, + GskCurve *result1, + GskCurve *result2); + gboolean (* decompose) (const GskCurve *curve, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data); + gskpathop (* pathop) (const GskCurve *curve); + const graphene_point_t * (* get_start_point) (const GskCurve *curve); + const graphene_point_t * (* get_end_point) (const GskCurve *curve); +}; + +/** LINE **/ + +static void +gsk_line_curve_init_from_points (GskLineCurve *self, + GskPathOperation op, + const graphene_point_t *start, + const graphene_point_t *end) +{ + self->op = op; + self->points[0] = *start; + self->points[1] = *end; +} + +static void +gsk_line_curve_init (GskCurve *curve, + gskpathop op) +{ + GskLineCurve *self = &curve->line; + const graphene_point_t *pts = gsk_pathop_points (op); + + gsk_line_curve_init_from_points (self, gsk_pathop_op (op), &pts[0], &pts[1]); +} + +static void +gsk_line_curve_eval (const GskCurve *curve, + float progress, + graphene_point_t *pos, + graphene_vec2_t *tangent) +{ + const GskLineCurve *self = &curve->line; + + if (pos) + graphene_point_interpolate (&self->points[0], &self->points[1], progress, pos); + + if (tangent) + { + graphene_vec2_init (tangent, self->points[1].x - self->points[0].x, self->points[1].y - self->points[0].y); + graphene_vec2_normalize (tangent, tangent); + } +} + +static void +gsk_line_curve_split (const GskCurve *curve, + float progress, + GskCurve *start, + GskCurve *end) +{ + const GskLineCurve *self = &curve->line; + graphene_point_t point; + + graphene_point_interpolate (&self->points[0], &self->points[1], progress, &point); + + if (start) + gsk_line_curve_init_from_points (&start->line, GSK_PATH_LINE, &self->points[0], &point); + if (end) + gsk_line_curve_init_from_points (&end->line, GSK_PATH_LINE, &point, &self->points[1]); +} + +static gboolean +gsk_line_curve_decompose (const GskCurve *curve, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data) +{ + const GskLineCurve *self = &curve->line; + + return add_line_func (&self->points[0], &self->points[1], 0.0f, 1.0f, user_data); +} + +static gskpathop +gsk_line_curve_pathop (const GskCurve *curve) +{ + const GskLineCurve *self = &curve->line; + + return gsk_pathop_encode (self->op, self->points); +} + +static const graphene_point_t * +gsk_line_curve_get_start_point (const GskCurve *curve) +{ + const GskLineCurve *self = &curve->line; + + return &self->points[0]; +} + +static const graphene_point_t * +gsk_line_curve_get_end_point (const GskCurve *curve) +{ + const GskLineCurve *self = &curve->line; + + return &self->points[1]; +} + +static const GskCurveClass GSK_LINE_CURVE_CLASS = { + gsk_line_curve_init, + gsk_line_curve_eval, + gsk_line_curve_split, + gsk_line_curve_decompose, + gsk_line_curve_pathop, + gsk_line_curve_get_start_point, + gsk_line_curve_get_end_point, +}; + +/** CURVE **/ + +static void +gsk_curve_curve_init_from_points (GskCurveCurve *self, + const graphene_point_t pts[4]) +{ + self->op = GSK_PATH_CURVE; + self->has_coefficients = FALSE; + memcpy (self->points, pts, sizeof (graphene_point_t) * 4); +} + +static void +gsk_curve_curve_init (GskCurve *curve, + gskpathop op) +{ + GskCurveCurve *self = &curve->curve; + + gsk_curve_curve_init_from_points (self, gsk_pathop_points (op)); +} + +static void +gsk_curve_curve_ensure_coefficients (const GskCurveCurve *curve) +{ + GskCurveCurve *self = (GskCurveCurve *) curve; + const graphene_point_t *pts = &self->points[0]; + + if (self->has_coefficients) + return; + + self->coeffs[0] = GRAPHENE_POINT_INIT (pts[3].x - 3.0f * pts[2].x + 3.0f * pts[1].x - pts[0].x, + pts[3].y - 3.0f * pts[2].y + 3.0f * pts[1].y - pts[0].y); + self->coeffs[1] = GRAPHENE_POINT_INIT (3.0f * pts[2].x - 6.0f * pts[1].x + 3.0f * pts[0].x, + 3.0f * pts[2].y - 6.0f * pts[1].y + 3.0f * pts[0].y); + self->coeffs[2] = GRAPHENE_POINT_INIT (3.0f * pts[1].x - 3.0f * pts[0].x, + 3.0f * pts[1].y - 3.0f * pts[0].y); + self->coeffs[3] = pts[0]; + + self->has_coefficients = TRUE; +} + +static void +gsk_curve_curve_eval (const GskCurve *curve, + float progress, + graphene_point_t *pos, + graphene_vec2_t *tangent) +{ + const GskCurveCurve *self = &curve->curve; + const graphene_point_t *c = self->coeffs; + + gsk_curve_curve_ensure_coefficients (self); + + if (pos) + *pos = GRAPHENE_POINT_INIT (((c[0].x * progress + c[1].x) * progress +c[2].x) * progress + c[3].x, + ((c[0].y * progress + c[1].y) * progress +c[2].y) * progress + c[3].y); + if (tangent) + { + graphene_vec2_init (tangent, + (3.0f * c[0].x * progress + 2.0f * c[1].x) * progress + c[2].x, + (3.0f * c[0].y * progress + 2.0f * c[1].y) * progress + c[2].y); + graphene_vec2_normalize (tangent, tangent); + } +} + +static void +gsk_curve_curve_split (const GskCurve *curve, + float progress, + GskCurve *start, + GskCurve *end) +{ + const GskCurveCurve *self = &curve->curve; + const graphene_point_t *pts = self->points; + 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); + + if (start) + gsk_curve_curve_init_from_points (&start->curve, (graphene_point_t[4]) { pts[0], ab, abbc, final }); + if (end) + gsk_curve_curve_init_from_points (&end->curve, (graphene_point_t[4]) { final, bccd, cd, pts[3] }); +} + +/* taken from Skia, including the very descriptive name */ +static gboolean +gsk_curve_curve_too_curvy (const GskCurveCurve *self, + float tolerance) +{ + const graphene_point_t *pts = self->points; + graphene_point_t p; + + graphene_point_interpolate (&pts[0], &pts[3], 1.0f / 3, &p); + if (ABS (p.x - pts[1].x) + ABS (p.y - pts[1].y) > tolerance) + return TRUE; + + graphene_point_interpolate (&pts[0], &pts[3], 2.0f / 3, &p); + if (ABS (p.x - pts[2].x) + ABS (p.y - pts[2].y) > tolerance) + return TRUE; + + return FALSE; +} + +static gboolean +gsk_curce_curve_decompose_step (const GskCurve *curve, + float start_progress, + float end_progress, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data) +{ + const GskCurveCurve *self = &curve->curve; + GskCurve left, right; + float mid_progress; + + if (!gsk_curve_curve_too_curvy (self, tolerance) || end_progress - start_progress <= MIN_PROGRESS) + return add_line_func (&self->points[0], &self->points[3], start_progress, end_progress, user_data); + + gsk_curve_curve_split ((const GskCurve *) self, 0.5, &left, &right); + mid_progress = (start_progress + end_progress) / 2; + + return gsk_curce_curve_decompose_step (&left, start_progress, mid_progress, tolerance, add_line_func, user_data) + && gsk_curce_curve_decompose_step (&right, mid_progress, end_progress, tolerance, add_line_func, user_data); +} + +static gboolean +gsk_curve_curve_decompose (const GskCurve *curve, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data) +{ + return gsk_curce_curve_decompose_step (curve, 0.0, 1.0, tolerance, add_line_func, user_data); +} + +static gskpathop +gsk_curve_curve_pathop (const GskCurve *curve) +{ + const GskCurveCurve *self = &curve->curve; + + return gsk_pathop_encode (self->op, self->points); +} + +static const graphene_point_t * +gsk_curve_curve_get_start_point (const GskCurve *curve) +{ + const GskCurveCurve *self = &curve->curve; + + return &self->points[0]; +} + +static const graphene_point_t * +gsk_curve_curve_get_end_point (const GskCurve *curve) +{ + const GskCurveCurve *self = &curve->curve; + + return &self->points[3]; +} + +static const GskCurveClass GSK_CURVE_CURVE_CLASS = { + gsk_curve_curve_init, + gsk_curve_curve_eval, + gsk_curve_curve_split, + gsk_curve_curve_decompose, + gsk_curve_curve_pathop, + gsk_curve_curve_get_start_point, + gsk_curve_curve_get_end_point, +}; + +/** CONIC **/ + +static void +gsk_conic_curve_init_from_points (GskConicCurve *self, + const graphene_point_t pts[4]) +{ + self->op = GSK_PATH_CONIC; + self->has_coefficients = FALSE; + + memcpy (self->points, pts, sizeof (graphene_point_t) * 4); +} + +static void +gsk_conic_curve_init (GskCurve *curve, + gskpathop op) +{ + GskConicCurve *self = &curve->conic; + + gsk_conic_curve_init_from_points (self, gsk_pathop_points (op)); +} + +static inline float +gsk_conic_curve_get_weight (const GskConicCurve *self) +{ + return self->points[2].x; +} + +static void +gsk_conic_curve_ensure_coefficents (const GskConicCurve *curve) +{ + GskConicCurve *self = (GskConicCurve *) curve; + float w = gsk_conic_curve_get_weight (self); + const graphene_point_t *pts = self->points; + graphene_point_t pw = GRAPHENE_POINT_INIT (w * pts[1].x, w * pts[1].y); + + if (self->has_coefficients) + return; + + self->num[2] = pts[0]; + self->num[1] = GRAPHENE_POINT_INIT (2 * (pw.x - pts[0].x), + 2 * (pw.y - pts[0].y)); + self->num[0] = GRAPHENE_POINT_INIT (pts[3].x - 2 * pw.x + pts[0].x, + pts[3].y - 2 * pw.y + pts[0].y); + + self->denom[2] = GRAPHENE_POINT_INIT (1, 1); + self->denom[1] = GRAPHENE_POINT_INIT (2 * (w - 1), 2 * (w - 1)); + self->denom[0] = GRAPHENE_POINT_INIT (-self->denom[1].x, -self->denom[1].y); + + self->has_coefficients = TRUE; +} + +static inline void +gsk_curve_eval_quad (const graphene_point_t quad[3], + float progress, + graphene_point_t *result) +{ + *result = GRAPHENE_POINT_INIT ((quad[0].x * progress + quad[1].x) * progress + quad[2].x, + (quad[0].y * progress + quad[1].y) * progress + quad[2].y); +} + +static inline void +gsk_conic_curve_eval_point (const GskConicCurve *self, + float progress, + graphene_point_t *point) +{ + graphene_point_t num, denom; + + gsk_curve_eval_quad (self->num, progress, &num); + gsk_curve_eval_quad (self->denom, progress, &denom); + + *point = GRAPHENE_POINT_INIT (num.x / denom.x, num.y / denom.y); +} + +static void +gsk_conic_curve_eval (const GskCurve *curve, + float progress, + graphene_point_t *pos, + graphene_vec2_t *tangent) +{ + const GskConicCurve *self = &curve->conic; + + gsk_conic_curve_ensure_coefficents (self); + + if (pos) + gsk_conic_curve_eval_point (self, progress, pos); + + if (tangent) + { + graphene_point_t tmp; + float w = gsk_conic_curve_get_weight (self); + const graphene_point_t *pts = self->points; + + /* The tangent will be 0 in these corner cases, just + * treat it like a line here. */ + if ((progress <= 0.f && graphene_point_equal (&pts[0], &pts[1])) || + (progress >= 1.f && graphene_point_equal (&pts[1], &pts[3]))) + { + graphene_vec2_init (tangent, pts[3].x - pts[0].x, pts[3].y - pts[0].y); + return; + } + + gsk_curve_eval_quad ((graphene_point_t[3]) { + GRAPHENE_POINT_INIT ((w - 1) * (pts[3].x - pts[0].x), + (w - 1) * (pts[3].y - pts[0].y)), + GRAPHENE_POINT_INIT (pts[3].x - pts[0].x - 2 * w * (pts[1].x - pts[0].x), + pts[3].y - pts[0].y - 2 * w * (pts[1].y - pts[0].y)), + GRAPHENE_POINT_INIT (w * (pts[1].x - pts[0].x), + w * (pts[1].y - pts[0].y)) + }, + progress, + &tmp); + graphene_vec2_init (tangent, tmp.x, tmp.y); + graphene_vec2_normalize (tangent, tangent); + } +} + +static void +split_bezier3d_recurse (const graphene_point3d_t *p, + int l, + float t, + graphene_point3d_t *left, + graphene_point3d_t *right, + int *lpos, + int *rpos) +{ + if (l == 1) + { + left[*lpos] = p[0]; + right[*rpos] = p[0]; + } + else + { + graphene_point3d_t *np; + int i; + + np = g_alloca (sizeof (graphene_point3d_t) * (l - 1)); + for (i = 0; i < l - 1; i++) + { + if (i == 0) + { + left[*lpos] = p[i]; + (*lpos)++; + } + if (i + 1 == l - 1) + { + right[*rpos] = p[i + 1]; + (*rpos)--; + } + graphene_point3d_interpolate (&p[i], &p[i + 1], t, &np[i]); + } + split_bezier3d_recurse (np, l - 1, t, left, right, lpos, rpos); + } +} + +static void +split_bezier3d (const graphene_point3d_t *p, + int l, + float t, + graphene_point3d_t *left, + graphene_point3d_t *right) +{ + int lpos = 0; + int rpos = l - 1; + split_bezier3d_recurse (p, l, t, left, right, &lpos, &rpos); +} + +static void +gsk_conic_curve_split (const GskCurve *curve, + float progress, + GskCurve *start, + GskCurve *end) +{ + const GskConicCurve *self = &curve->conic; + graphene_point3d_t p[3]; + graphene_point3d_t l[3], r[3]; + graphene_point_t left[4], right[4]; + float w; + + /* do de Casteljau in homogeneous coordinates... */ + w = self->points[2].x; + p[0] = GRAPHENE_POINT3D_INIT (self->points[0].x, self->points[0].y, 1); + p[1] = GRAPHENE_POINT3D_INIT (self->points[1].x * w, self->points[1].y * w, w); + p[2] = GRAPHENE_POINT3D_INIT (self->points[3].x, self->points[3].y, 1); + + split_bezier3d (p, 3, progress, l, r); + + /* then project the control points down */ + left[0] = GRAPHENE_POINT_INIT (l[0].x / l[0].z, l[0].y / l[0].z); + left[1] = GRAPHENE_POINT_INIT (l[1].x / l[1].z, l[1].y / l[1].z); + left[3] = GRAPHENE_POINT_INIT (l[2].x / l[2].z, l[2].y / l[2].z); + + right[0] = GRAPHENE_POINT_INIT (r[0].x / r[0].z, r[0].y / r[0].z); + right[1] = GRAPHENE_POINT_INIT (r[1].x / r[1].z, r[1].y / r[1].z); + right[3] = GRAPHENE_POINT_INIT (r[2].x / r[2].z, r[2].y / r[2].z); + + /* normalize the outer weights to be 1 by using + * the fact that weights w_i and c*w_i are equivalent + * for any nonzero constant c + */ + for (int i = 0; i < 3; i++) + { + l[i].z /= l[0].z; + r[i].z /= r[2].z; + } + + /* normalize the inner weight to be 1 by using + * the fact that w_0*w_2/w_1^2 is a constant for + * all equivalent weights. + */ + left[2] = GRAPHENE_POINT_INIT (l[1].z / sqrt (l[2].z), 0); + right[2] = GRAPHENE_POINT_INIT (r[1].z / sqrt (r[0].z), 0); + + if (start) + gsk_curve_init (start, gsk_pathop_encode (GSK_PATH_CONIC, left)); + if (end) + gsk_curve_init (end, gsk_pathop_encode (GSK_PATH_CONIC, right)); +} + +/* taken from Skia, including the very descriptive name */ +static gboolean +gsk_conic_curve_too_curvy (const graphene_point_t *start, + const graphene_point_t *mid, + const graphene_point_t *end, + float tolerance) +{ + return fabs ((start->x + end->x) * 0.5 - mid->x) > tolerance + || fabs ((start->y + end->y) * 0.5 - mid->y) > tolerance; +} + +static gboolean +gsk_conic_curve_decompose_subdivide (const GskConicCurve *self, + float tolerance, + const graphene_point_t *start, + float start_progress, + const graphene_point_t *end, + float end_progress, + GskCurveAddLineFunc add_line_func, + gpointer user_data) +{ + graphene_point_t mid; + float mid_progress; + + mid_progress = (start_progress + end_progress) / 2; + gsk_conic_curve_eval_point (self, mid_progress, &mid); + + if (end_progress - start_progress <= MIN_PROGRESS || + !gsk_conic_curve_too_curvy (start, &mid, end, tolerance)) + { + return add_line_func (start, end, start_progress, end_progress, user_data); + } + + return gsk_conic_curve_decompose_subdivide (self, tolerance, + start, start_progress, &mid, mid_progress, + add_line_func, user_data) + && gsk_conic_curve_decompose_subdivide (self, tolerance, + &mid, mid_progress, end, end_progress, + add_line_func, user_data); +} + +static gboolean +gsk_conic_curve_decompose (const GskCurve *curve, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data) +{ + const GskConicCurve *self = &curve->conic; + + gsk_conic_curve_ensure_coefficents (self); + + return gsk_conic_curve_decompose_subdivide (self, + tolerance, + &self->points[0], + 0.0f, + &self->points[3], + 1.0f, + add_line_func, + user_data); +} + +static gskpathop +gsk_conic_curve_pathop (const GskCurve *curve) +{ + const GskConicCurve *self = &curve->conic; + + return gsk_pathop_encode (self->op, self->points); +} + +static const graphene_point_t * +gsk_conic_curve_get_start_point (const GskCurve *curve) +{ + const GskConicCurve *self = &curve->conic; + + return &self->points[0]; +} + +static const graphene_point_t * +gsk_conic_curve_get_end_point (const GskCurve *curve) +{ + const GskConicCurve *self = &curve->conic; + + return &self->points[3]; +} + +static const GskCurveClass GSK_CONIC_CURVE_CLASS = { + gsk_conic_curve_init, + gsk_conic_curve_eval, + gsk_conic_curve_split, + gsk_conic_curve_decompose, + gsk_conic_curve_pathop, + gsk_conic_curve_get_start_point, + gsk_conic_curve_get_end_point, +}; + +/** API **/ + +static const GskCurveClass * +get_class (GskPathOperation op) +{ + const GskCurveClass *klasses[] = { + [GSK_PATH_CLOSE] = &GSK_LINE_CURVE_CLASS, + [GSK_PATH_LINE] = &GSK_LINE_CURVE_CLASS, + [GSK_PATH_CURVE] = &GSK_CURVE_CURVE_CLASS, + [GSK_PATH_CONIC] = &GSK_CONIC_CURVE_CLASS, + }; + + g_assert (op < G_N_ELEMENTS (klasses) && klasses[op] != NULL); + + return klasses[op]; +} + +void +gsk_curve_init (GskCurve *curve, + gskpathop op) +{ + get_class (gsk_pathop_op (op))->init (curve, op); +} + +void +gsk_curve_eval (const GskCurve *curve, + float progress, + graphene_point_t *pos, + graphene_vec2_t *tangent) +{ + get_class (curve->op)->eval (curve, progress, pos, tangent); +} + +void +gsk_curve_split (const GskCurve *curve, + float progress, + GskCurve *start, + GskCurve *end) +{ + get_class (curve->op)->split (curve, progress, start, end); +} + +gboolean +gsk_curve_decompose (const GskCurve *curve, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data) +{ + return get_class (curve->op)->decompose (curve, tolerance, add_line_func, user_data); +} + +gskpathop +gsk_curve_pathop (const GskCurve *curve) +{ + return get_class (curve->op)->pathop (curve); +} + +const graphene_point_t * +gsk_curve_get_start_point (const GskCurve *curve) +{ + return get_class (curve->op)->get_start_point (curve); +} + +const graphene_point_t * +gsk_curve_get_end_point (const GskCurve *curve) +{ + return get_class (curve->op)->get_end_point (curve); +} + diff --git a/gsk/gskcurveprivate.h b/gsk/gskcurveprivate.h new file mode 100644 index 0000000000..720ee71f1c --- /dev/null +++ b/gsk/gskcurveprivate.h @@ -0,0 +1,108 @@ +/* + * 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 . + * + * Authors: Benjamin Otte + */ + + +#ifndef __GSK_CURVE_PRIVATE_H__ +#define __GSK_CURVE_PRIVATE_H__ + +#include "gskpathopprivate.h" + +G_BEGIN_DECLS + +typedef gpointer gskpathop; + +typedef union _GskCurve GskCurve; + +typedef struct _GskLineCurve GskLineCurve; +typedef struct _GskCurveCurve GskCurveCurve; +typedef struct _GskConicCurve GskConicCurve; + +struct _GskLineCurve +{ + GskPathOperation op; + + gboolean padding; + + graphene_point_t points[2]; +}; + +struct _GskCurveCurve +{ + GskPathOperation op; + + gboolean has_coefficients; + + graphene_point_t points[4]; + + graphene_point_t coeffs[4]; +}; + +struct _GskConicCurve +{ + GskPathOperation op; + + gboolean has_coefficients; + + graphene_point_t points[4]; + + graphene_point_t num[3]; + graphene_point_t denom[3]; +}; + +union _GskCurve +{ + GskPathOperation op; + GskLineCurve line; + GskCurveCurve curve; + GskConicCurve conic; +}; + +typedef gboolean (* GskCurveAddLineFunc) (const graphene_point_t *from, + const graphene_point_t *to, + float from_progress, + float to_progress, + gpointer user_data); + +void gsk_curve_init (GskCurve *curve, + gskpathop op); + +void gsk_curve_eval (const GskCurve *curve, + float progress, + graphene_point_t *pos, + graphene_vec2_t *tangent); +void gsk_curve_split (const GskCurve *curve, + float progress, + GskCurve *start, + GskCurve *end); +gboolean gsk_curve_decompose (const GskCurve *curve, + float tolerance, + GskCurveAddLineFunc add_line_func, + gpointer user_data); +gskpathop gsk_curve_pathop (const GskCurve *curve); +#define gsk_curve_builder_to(curve, builder) gsk_path_builder_pathop_to ((builder), gsk_curve_pathop (curve)) +const graphene_point_t *gsk_curve_get_start_point (const GskCurve *curve); +const graphene_point_t *gsk_curve_get_end_point (const GskCurve *curve); + + + + +G_END_DECLS + +#endif /* __GSK_CURVE_PRIVATE_H__ */ + diff --git a/gsk/gskpath.c b/gsk/gskpath.c index 1642481ab8..034107ac35 100644 --- a/gsk/gskpath.c +++ b/gsk/gskpath.c @@ -21,8 +21,8 @@ #include "gskpathprivate.h" +#include "gskcurveprivate.h" #include "gskpathbuilder.h" -#include "gsksplineprivate.h" /** * SECTION:gskpath @@ -445,26 +445,22 @@ struct _GskPathForeachTrampoline double tolerance; GskPathForeachFunc func; gpointer user_data; - gboolean retval; }; -static void -gsk_path_foreach_trampoline_add_point (const graphene_point_t *from, - const graphene_point_t *to, - float from_progress, - float to_progress, - gpointer data) +static gboolean +gsk_path_foreach_trampoline_add_line (const graphene_point_t *from, + const graphene_point_t *to, + float from_progress, + float to_progress, + gpointer data) { GskPathForeachTrampoline *trampoline = data; - if (!trampoline->retval) - return; - - trampoline->retval = trampoline->func (GSK_PATH_LINE, - (graphene_point_t[2]) { *from, *to }, - 2, - 0.0f, - trampoline->user_data); + return trampoline->func (GSK_PATH_LINE, + (graphene_point_t[2]) { *from, *to }, + 2, + 0.0f, + trampoline->user_data); } static gboolean @@ -484,25 +480,34 @@ gsk_path_foreach_trampoline (GskPathOperation op, return trampoline->func (op, pts, n_pts, weight, trampoline->user_data); case GSK_PATH_CURVE: - if (trampoline->flags & GSK_PATH_FOREACH_ALLOW_CURVE) - return trampoline->func (op, pts, n_pts, weight, trampoline->user_data); - - gsk_spline_decompose_cubic (pts, - trampoline->tolerance, - gsk_path_foreach_trampoline_add_point, - trampoline); - return trampoline->retval; + { + GskCurve curve; + + if (trampoline->flags & GSK_PATH_FOREACH_ALLOW_CURVE) + return trampoline->func (op, pts, n_pts, weight, trampoline->user_data); + + gsk_curve_init (&curve, gsk_pathop_encode (GSK_PATH_CURVE, pts)); + return gsk_curve_decompose (&curve, + trampoline->tolerance, + gsk_path_foreach_trampoline_add_line, + trampoline); + } case GSK_PATH_CONIC: - if (trampoline->flags & GSK_PATH_FOREACH_ALLOW_CONIC) - return trampoline->func (op, pts, n_pts, weight, trampoline->user_data); + { + GskCurve curve; + + if (trampoline->flags & GSK_PATH_FOREACH_ALLOW_CONIC) + return trampoline->func (op, pts, n_pts, weight, trampoline->user_data); + + /* XXX: decompose into curves if allowed */ + gsk_curve_init (&curve, gsk_pathop_encode (GSK_PATH_CONIC, (graphene_point_t[4]) { pts[0], pts[1], { weight, }, pts[2] } )); + return gsk_curve_decompose (&curve, + trampoline->tolerance, + gsk_path_foreach_trampoline_add_line, + trampoline); + } - /* XXX: decompose into curves if allowed */ - gsk_spline_decompose_conic ((graphene_point_t[4]) { pts[0], pts[1], { weight, }, pts[2] }, - trampoline->tolerance, - gsk_path_foreach_trampoline_add_point, - trampoline); - return trampoline->retval; default: g_assert_not_reached (); @@ -523,7 +528,7 @@ gsk_path_foreach_with_tolerance (GskPath *self, /* If we need to massage the data, set up a trampoline here */ if (flags != (GSK_PATH_FOREACH_ALLOW_CURVE | GSK_PATH_FOREACH_ALLOW_CONIC)) { - trampoline = (GskPathForeachTrampoline) { flags, tolerance, func, user_data, TRUE }; + trampoline = (GskPathForeachTrampoline) { flags, tolerance, func, user_data }; func = gsk_path_foreach_trampoline; user_data = &trampoline; } diff --git a/gsk/gskpathopprivate.h b/gsk/gskpathopprivate.h index 864e97e2ea..da1c3e63e4 100644 --- a/gsk/gskpathopprivate.h +++ b/gsk/gskpathopprivate.h @@ -58,6 +58,7 @@ gsk_pathop_encode (GskPathOperation op, const graphene_point_t *pts) { /* g_assert (op & GSK_PATHOP_OPERATION_MASK == op); */ + g_assert ((GPOINTER_TO_SIZE (pts) & GSK_PATHOP_OPERATION_MASK) == 0); return GSIZE_TO_POINTER (GPOINTER_TO_SIZE (pts) | op); } diff --git a/gsk/gskpathprivate.h b/gsk/gskpathprivate.h index e9d9c386d9..4b403acbd6 100644 --- a/gsk/gskpathprivate.h +++ b/gsk/gskpathprivate.h @@ -24,6 +24,7 @@ #include "gskpath.h" #include "gskcontourprivate.h" +#include "gskpathopprivate.h" G_BEGIN_DECLS diff --git a/gsk/gskspline.c b/gsk/gskspline.c index 711226229c..5590c7f7e0 100644 --- a/gsk/gskspline.c +++ b/gsk/gskspline.c @@ -25,384 +25,6 @@ #include -#define MIN_PROGRESS (1/1024.f) - -typedef struct -{ - graphene_point_t last_point; - float last_progress; - GskSplineAddPointFunc func; - gpointer user_data; -} GskSplineDecompose; - -static void -gsk_spline_decompose_add_point (GskSplineDecompose *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; -} - -static void -gsk_spline_decompose_finish (GskSplineDecompose *decomp, - const graphene_point_t *end_point) -{ - g_assert (graphene_point_equal (&decomp->last_point, end_point)); - g_assert (decomp->last_progress == 1.0f || decomp->last_progress == 0.0f); -} - -typedef struct -{ - GskSplineDecompose decomp; - float tolerance; -} GskCubicDecomposition; - -static void -gsk_spline_cubic_get_coefficients (graphene_point_t coeffs[4], - const graphene_point_t pts[4]) -{ - coeffs[0] = GRAPHENE_POINT_INIT (pts[3].x - 3.0f * pts[2].x + 3.0f * pts[1].x - pts[0].x, - pts[3].y - 3.0f * pts[2].y + 3.0f * pts[1].y - pts[0].y); - coeffs[1] = GRAPHENE_POINT_INIT (3.0f * pts[2].x - 6.0f * pts[1].x + 3.0f * pts[0].x, - 3.0f * pts[2].y - 6.0f * pts[1].y + 3.0f * pts[0].y); - coeffs[2] = GRAPHENE_POINT_INIT (3.0f * pts[1].x - 3.0f * pts[0].x, - 3.0f * pts[1].y - 3.0f * pts[0].y); - coeffs[3] = pts[0]; -} - -void -gsk_spline_get_point_cubic (const graphene_point_t pts[4], - float progress, - graphene_point_t *pos, - graphene_vec2_t *tangent) -{ - graphene_point_t c[4]; - - gsk_spline_cubic_get_coefficients (c, pts); - - if (pos) - *pos = GRAPHENE_POINT_INIT (((c[0].x * progress + c[1].x) * progress +c[2].x) * progress + c[3].x, - ((c[0].y * progress + c[1].y) * progress +c[2].y) * progress + c[3].y); - if (tangent) - { - graphene_vec2_init (tangent, - (3.0f * c[0].x * progress + 2.0f * c[1].x) * progress + c[2].x, - (3.0f * c[0].y * progress + 2.0f * c[1].y) * progress + c[2].y); - graphene_vec2_normalize (tangent, tangent); - } -} - -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])); -} - -#if 0 -/* 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; -} -#endif - -/* taken from Skia, including the very descriptive name */ -static gboolean -gsk_spline_cubic_too_curvy (const graphene_point_t pts[4], - float tolerance) -{ - graphene_point_t p; - - graphene_point_interpolate (&pts[0], &pts[3], 1.0f / 3, &p); - if (ABS (p.x - pts[1].x) + ABS (p.y - pts[1].y) > tolerance) - return TRUE; - - graphene_point_interpolate (&pts[0], &pts[3], 2.0f / 3, &p); - if (ABS (p.x - pts[2].x) + ABS (p.y - pts[2].y) > tolerance) - return TRUE; - - return FALSE; -} - -static void -gsk_spline_cubic_decompose (GskCubicDecomposition *d, - const graphene_point_t pts[4], - float progress) -{ - graphene_point_t left[4], right[4]; - - if (!gsk_spline_cubic_too_curvy (pts, d->tolerance) || progress < MIN_PROGRESS) - { - gsk_spline_decompose_add_point (&d->decomp, &pts[3], progress); - return; - } - - gsk_spline_split_cubic (pts, left, right, 0.5); - - gsk_spline_cubic_decompose (d, left, progress / 2); - gsk_spline_cubic_decompose (d, 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, add_point_func, user_data }, tolerance }; - - gsk_spline_cubic_decompose (&decomp, pts, 1.0f); - - gsk_spline_decompose_finish (&decomp.decomp, &pts[3]); -} - -/* CONIC */ - -typedef struct { - graphene_point_t num[3]; - graphene_point_t denom[3]; -} ConicCoefficients; - -typedef struct -{ - GskSplineDecompose decomp; - float tolerance; - ConicCoefficients c; -} GskConicDecomposition; - - -static void -gsk_spline_conic_get_coefficents (ConicCoefficients *c, - const graphene_point_t pts[4]) -{ - float w = pts[2].x; - graphene_point_t pw = GRAPHENE_POINT_INIT (w * pts[1].x, w * pts[1].y); - - c->num[2] = pts[0]; - c->num[1] = GRAPHENE_POINT_INIT (2 * (pw.x - pts[0].x), - 2 * (pw.y - pts[0].y)); - c->num[0] = GRAPHENE_POINT_INIT (pts[3].x - 2 * pw.x + pts[0].x, - pts[3].y - 2 * pw.y + pts[0].y); - - c->denom[2] = GRAPHENE_POINT_INIT (1, 1); - c->denom[1] = GRAPHENE_POINT_INIT (2 * (w - 1), 2 * (w - 1)); - c->denom[0] = GRAPHENE_POINT_INIT (-c->denom[1].x, -c->denom[1].y); -} - -static inline void -gsk_spline_eval_quad (const graphene_point_t quad[3], - float progress, - graphene_point_t *result) -{ - *result = GRAPHENE_POINT_INIT ((quad[0].x * progress + quad[1].x) * progress + quad[2].x, - (quad[0].y * progress + quad[1].y) * progress + quad[2].y); -} - -static inline void -gsk_spline_eval_conic (const ConicCoefficients *c, - float progress, - graphene_point_t *result) -{ - graphene_point_t num, denom; - - gsk_spline_eval_quad (c->num, progress, &num); - gsk_spline_eval_quad (c->denom, progress, &denom); - *result = GRAPHENE_POINT_INIT (num.x / denom.x, num.y / denom.y); -} - -void -gsk_spline_get_point_conic (const graphene_point_t pts[4], - float progress, - graphene_point_t *pos, - graphene_vec2_t *tangent) -{ - ConicCoefficients c; - - gsk_spline_conic_get_coefficents (&c, pts); - - if (pos) - gsk_spline_eval_conic (&c, progress, pos); - - if (tangent) - { - graphene_point_t tmp; - float w = pts[2].x; - - /* The tangent will be 0 in these corner cases, just - * treat it like a line here. */ - if ((progress <= 0.f && graphene_point_equal (&pts[0], &pts[1])) || - (progress >= 1.f && graphene_point_equal (&pts[1], &pts[3]))) - { - graphene_vec2_init (tangent, pts[3].x - pts[0].x, pts[3].y - pts[0].y); - return; - } - - gsk_spline_eval_quad ((graphene_point_t[3]) { - GRAPHENE_POINT_INIT ((w - 1) * (pts[3].x - pts[0].x), - (w - 1) * (pts[3].y - pts[0].y)), - GRAPHENE_POINT_INIT (pts[3].x - pts[0].x - 2 * w * (pts[1].x - pts[0].x), - pts[3].y - pts[0].y - 2 * w * (pts[1].y - pts[0].y)), - GRAPHENE_POINT_INIT (w * (pts[1].x - pts[0].x), - w * (pts[1].y - pts[0].y)) - }, - progress, - &tmp); - graphene_vec2_init (tangent, tmp.x, tmp.y); - graphene_vec2_normalize (tangent, tangent); - } -} - -void -gsk_spline_split_conic (const graphene_point_t pts[4], - graphene_point_t result1[4], - graphene_point_t result2[4], - float progress) -{ - g_warning ("FIXME: Stop treating conics as lines"); -} - -/* taken from Skia, including the very descriptive name */ -static gboolean -gsk_spline_conic_too_curvy (const graphene_point_t *start, - const graphene_point_t *mid, - const graphene_point_t *end, - float tolerance) -{ - return fabs ((start->x + end->x) * 0.5 - mid->x) > tolerance - || fabs ((start->y + end->y) * 0.5 - mid->y) > tolerance; -} - -static void -gsk_spline_decompose_conic_subdivide (GskConicDecomposition *d, - const graphene_point_t *start, - float start_progress, - const graphene_point_t *end, - float end_progress) -{ - graphene_point_t mid; - float mid_progress; - - mid_progress = (start_progress + end_progress) / 2; - gsk_spline_eval_conic (&d->c, mid_progress, &mid); - - if (end_progress - start_progress < MIN_PROGRESS || - !gsk_spline_conic_too_curvy (start, &mid, end, d->tolerance)) - { - gsk_spline_decompose_add_point (&d->decomp, end, end_progress - start_progress); - return; - } - - gsk_spline_decompose_conic_subdivide (d, start, start_progress, &mid, mid_progress); - gsk_spline_decompose_conic_subdivide (d, &mid, mid_progress, end, end_progress); -} - -void -gsk_spline_decompose_conic (const graphene_point_t pts[4], - float tolerance, - GskSplineAddPointFunc add_point_func, - gpointer user_data) -{ - GskConicDecomposition d = { { pts[0], 0.0f, add_point_func, user_data }, tolerance, }; - - gsk_spline_conic_get_coefficents (&d.c, pts); - - gsk_spline_decompose_conic_subdivide (&d, &pts[0], 0.0f, &pts[3], 1.0f); - - gsk_spline_decompose_finish (&d.decomp, &pts[3]); -} - /* Spline deviation from the circle in radius would be given by: error = sqrt (x**2 + y**2) - 1 diff --git a/gsk/gsksplineprivate.h b/gsk/gsksplineprivate.h index 02556937ce..c9da32734c 100644 --- a/gsk/gsksplineprivate.h +++ b/gsk/gsksplineprivate.h @@ -25,38 +25,6 @@ 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_get_point_cubic (const graphene_point_t pts[4], - float progress, - graphene_point_t *pos, - graphene_vec2_t *tangent); -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); - -void gsk_spline_get_point_conic (const graphene_point_t pts[4], - float progress, - graphene_point_t *pos, - graphene_vec2_t *tangent); -void gsk_spline_split_conic (const graphene_point_t pts[4], - graphene_point_t result1[4], - graphene_point_t result2[4], - float progress); -void gsk_spline_decompose_conic (const graphene_point_t pts[4], - float tolerance, - GskSplineAddPointFunc add_point_func, - gpointer user_data); - typedef gboolean (* GskSplineAddCurveFunc) (const graphene_point_t curve[4], gpointer user_data); gboolean gsk_spline_decompose_arc (const graphene_point_t *center, diff --git a/gsk/meson.build b/gsk/meson.build index 55f37e1c3e..78e3e88876 100644 --- a/gsk/meson.build +++ b/gsk/meson.build @@ -21,8 +21,8 @@ gsk_private_gl_shaders = [ ] gsk_public_sources = files([ - 'gskdiff.c', 'gskcairorenderer.c', + 'gskdiff.c', 'gskglshader.c', 'gskpath.c', 'gskpathbuilder.c', @@ -40,6 +40,7 @@ gsk_public_sources = files([ gsk_private_sources = files([ 'gskcairoblur.c', 'gskcontour.c', + 'gskcurve.c', 'gskdebug.c', 'gskprivate.c', 'gskprofiler.c', -- cgit v1.2.1