[gtk/wip/otte/lottie: 14/23] path: Add gsk_path_add_circle()
- From: Benjamin Otte <otte src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/otte/lottie: 14/23] path: Add gsk_path_add_circle()
- Date: Thu, 26 Nov 2020 00:51:40 +0000 (UTC)
commit 9ed234f96fdbf171344715237271bac10584b75b
Author: Benjamin Otte <otte redhat com>
Date: Thu Nov 19 06:42:58 2020 +0100
path: Add gsk_path_add_circle()
Adds a circle contour, too.
gsk/gskpath.c | 201 +++++++++++++++++++++++++++++++++++++++++++++++++
gsk/gskpath.h | 4 +
gsk/gskspline.c | 183 ++++++++++++++++++++++++++++++++++++++++++++
gsk/gsksplineprivate.h | 10 +++
4 files changed, 398 insertions(+)
---
diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index a16b9f7c49..76a71d2d1b 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -298,6 +298,184 @@ gsk_rect_contour_init (GskContour *contour,
self->height = height;
}
+/* CIRCLE CONTOUR */
+
+#define DEG_TO_RAD(x) ((x) * (G_PI / 180.f))
+
+typedef struct _GskCircleContour GskCircleContour;
+struct _GskCircleContour
+{
+ GskContour contour;
+
+ graphene_point_t center;
+ float radius;
+ float start_angle; /* in degrees */
+ float end_angle; /* start_angle +/- 360 */
+};
+
+static GskPathFlags
+gsk_circle_contour_get_flags (const GskContour *contour)
+{
+ const GskCircleContour *self = (const GskCircleContour *) contour;
+
+ /* XXX: should we explicitly close paths? */
+ if (fabs (self->start_angle - self->end_angle) >= 360)
+ return GSK_PATH_CLOSED;
+ else
+ return 0;
+}
+
+static void
+gsk_circle_contour_print (const GskContour *contour,
+ GString *string)
+{
+ const GskCircleContour *self = (const GskCircleContour *) contour;
+ graphene_point_t start = GRAPHENE_POINT_INIT (cos (DEG_TO_RAD (self->start_angle)) * self->radius,
+ sin (DEG_TO_RAD (self->start_angle)) * self->radius);
+ graphene_point_t end = GRAPHENE_POINT_INIT (cos (DEG_TO_RAD (self->end_angle)) * self->radius,
+ sin (DEG_TO_RAD (self->end_angle)) * self->radius);
+
+ g_string_append_printf (string, "M %g %g A %g %g 0 %u %u %g %g",
+ self->center.x + start.x, self->center.y + start.y,
+ self->radius, self->radius,
+ fabs (self->start_angle - self->end_angle) > 180 ? 1 : 0,
+ self->start_angle < self->end_angle ? 0 : 1,
+ self->center.x + end.x, self->center.y + end.y);
+}
+
+static gboolean
+gsk_circle_contour_get_bounds (const GskContour *contour,
+ graphene_rect_t *rect)
+{
+ const GskCircleContour *self = (const GskCircleContour *) contour;
+
+ /* XXX: handle partial circles */
+ graphene_rect_init (rect,
+ self->center.x - self->radius,
+ self->center.y - self->radius,
+ 2 * self->radius,
+ 2 * self->radius);
+
+ return TRUE;
+}
+
+typedef struct
+{
+ GskPathForeachFunc func;
+ gpointer user_data;
+} ForeachWrapper;
+
+static gboolean
+gsk_circle_contour_curve (const graphene_point_t curve[4],
+ gpointer data)
+{
+ ForeachWrapper *wrapper = data;
+
+ return wrapper->func (GSK_PATH_CURVE, curve, 4, wrapper->user_data);
+}
+
+static gboolean
+gsk_circle_contour_foreach (const GskContour *contour,
+ float tolerance,
+ GskPathForeachFunc func,
+ gpointer user_data)
+{
+ const GskCircleContour *self = (const GskCircleContour *) contour;
+ graphene_point_t start = GRAPHENE_POINT_INIT (self->center.x + cos (DEG_TO_RAD (self->start_angle)) *
self->radius,
+ self->center.y + sin (DEG_TO_RAD (self->start_angle)) *
self->radius);
+
+ if (!func (GSK_PATH_MOVE, &start, 1, user_data))
+ return FALSE;
+
+ if (!gsk_spline_decompose_arc (&self->center,
+ self->radius,
+ tolerance,
+ DEG_TO_RAD (self->start_angle),
+ DEG_TO_RAD (self->end_angle),
+ gsk_circle_contour_curve,
+ &(ForeachWrapper) { func, user_data }))
+ return FALSE;
+
+ if (fabs (self->start_angle - self->end_angle) >= 360)
+ {
+ if (!func (GSK_PATH_CLOSE, (graphene_point_t[2]) { start, start }, 2, user_data))
+ return FALSE;
+ }
+
+ return TRUE;
+}
+
+static gpointer
+gsk_circle_contour_init_measure (const GskContour *contour,
+ float tolerance,
+ float *out_length)
+{
+ const GskCircleContour *self = (const GskCircleContour *) contour;
+
+ *out_length = DEG_TO_RAD (fabs (self->start_angle - self->end_angle)) * self->radius;
+
+ return NULL;
+}
+
+static void
+gsk_circle_contour_free_measure (const GskContour *contour,
+ gpointer data)
+{
+}
+
+static void
+gsk_circle_contour_copy (const GskContour *contour,
+ GskContour *dest)
+{
+ const GskCircleContour *self = (const GskCircleContour *) contour;
+ GskCircleContour *target = (GskCircleContour *) dest;
+
+ *target = *self;
+}
+
+static void
+gsk_circle_contour_add_segment (const GskContour *contour,
+ GskPathBuilder *builder,
+ gpointer measure_data,
+ float start,
+ float end)
+{
+ g_warning ("FIXME");
+}
+
+static const GskContourClass GSK_CIRCLE_CONTOUR_CLASS =
+{
+ sizeof (GskCircleContour),
+ "GskCircleContour",
+ gsk_contour_get_size_default,
+ gsk_circle_contour_get_flags,
+ gsk_circle_contour_print,
+ gsk_circle_contour_get_bounds,
+ gsk_circle_contour_foreach,
+ gsk_circle_contour_init_measure,
+ gsk_circle_contour_free_measure,
+ gsk_circle_contour_copy,
+ gsk_circle_contour_add_segment
+};
+
+static void
+gsk_circle_contour_init (GskContour *contour,
+ const graphene_point_t *center,
+ float radius,
+ float start_angle,
+ float end_angle)
+{
+ GskCircleContour *self = (GskCircleContour *) contour;
+
+ g_assert (fabs (start_angle - end_angle) <= 360);
+
+ self->contour.klass = &GSK_CIRCLE_CONTOUR_CLASS;
+ self->center = *center;
+ self->radius = radius;
+ self->start_angle = start_angle;
+ self->end_angle = end_angle;
+}
+
/* STANDARD CONTOUR */
typedef struct _GskStandardOperation GskStandardOperation;
@@ -1521,6 +1699,29 @@ gsk_path_builder_add_rect (GskPathBuilder *builder,
gsk_rect_contour_init (contour, x, y, width, height);
}
+/**
+ * gsk_path_builder_add_circle:
+ * @builder: a #GskPathBuilder
+ * @center: the center of the circle
+ * @radius: the radius of the circle
+ *
+ * Adds a circle with the @center and @radius.
+ **/
+void
+gsk_path_builder_add_circle (GskPathBuilder *builder,
+ const graphene_point_t *center,
+ float radius)
+{
+ GskContour *contour;
+
+ g_return_if_fail (builder != NULL);
+ g_return_if_fail (center != NULL);
+ g_return_if_fail (radius > 0);
+
+ contour = gsk_path_builder_add_contour_by_klass (builder, &GSK_CIRCLE_CONTOUR_CLASS);
+ gsk_circle_contour_init (contour, center, radius, 0, 360);
+}
+
void
gsk_path_builder_move_to (GskPathBuilder *builder,
float x,
diff --git a/gsk/gskpath.h b/gsk/gskpath.h
index 8011aba4eb..f2010d5397 100644
--- a/gsk/gskpath.h
+++ b/gsk/gskpath.h
@@ -112,6 +112,10 @@ void gsk_path_builder_add_rect (GskPathBuilder
float width,
float height);
GDK_AVAILABLE_IN_ALL
+void gsk_path_builder_add_circle (GskPathBuilder *builder,
+ const graphene_point_t *center,
+ float radius);
+GDK_AVAILABLE_IN_ALL
void gsk_path_builder_move_to (GskPathBuilder *builder,
float x,
float y);
diff --git a/gsk/gskspline.c b/gsk/gskspline.c
index 03223915bf..4ccf4cf6d2 100644
--- a/gsk/gskspline.c
+++ b/gsk/gskspline.c
@@ -23,6 +23,8 @@
#include "gsksplineprivate.h"
+#include <math.h>
+
typedef struct
{
graphene_point_t last_point;
@@ -177,3 +179,184 @@ gsk_spline_decompose_cubic (const graphene_point_t pts[4],
g_assert (decomp.last_progress == 1.0f || decomp.last_progress == 0.0f);
}
+/* Spline deviation from the circle in radius would be given by:
+
+ error = sqrt (x**2 + y**2) - 1
+
+ A simpler error function to work with is:
+
+ e = x**2 + y**2 - 1
+
+ From "Good approximation of circles by curvature-continuous Bezier
+ curves", Tor Dokken and Morten Daehlen, Computer Aided Geometric
+ Design 8 (1990) 22-41, we learn:
+
+ abs (max(e)) = 4/27 * sin**6(angle/4) / cos**2(angle/4)
+
+ and
+ abs (error) =~ 1/2 * e
+
+ Of course, this error value applies only for the particular spline
+ approximation that is used in _cairo_gstate_arc_segment.
+*/
+static float
+arc_error_normalized (float angle)
+{
+ return 2.0/27.0 * pow (sin (angle / 4), 6) / pow (cos (angle / 4), 2);
+}
+
+static float
+arc_max_angle_for_tolerance_normalized (float tolerance)
+{
+ float angle, error;
+ guint i;
+
+ /* Use table lookup to reduce search time in most cases. */
+ struct {
+ float angle;
+ float error;
+ } table[] = {
+ { G_PI / 1.0, 0.0185185185185185036127 },
+ { G_PI / 2.0, 0.000272567143730179811158 },
+ { G_PI / 3.0, 2.38647043651461047433e-05 },
+ { G_PI / 4.0, 4.2455377443222443279e-06 },
+ { G_PI / 5.0, 1.11281001494389081528e-06 },
+ { G_PI / 6.0, 3.72662000942734705475e-07 },
+ { G_PI / 7.0, 1.47783685574284411325e-07 },
+ { G_PI / 8.0, 6.63240432022601149057e-08 },
+ { G_PI / 9.0, 3.2715520137536980553e-08 },
+ { G_PI / 10.0, 1.73863223499021216974e-08 },
+ { G_PI / 11.0, 9.81410988043554039085e-09 },
+ };
+
+ for (i = 0; i < G_N_ELEMENTS (table); i++)
+ {
+ if (table[i].error < tolerance)
+ return table[i].angle;
+ }
+
+ i++;
+ do {
+ angle = G_PI / i++;
+ error = arc_error_normalized (angle);
+ } while (error > tolerance);
+
+ return angle;
+}
+
+static guint
+arc_segments_needed (float angle,
+ float radius,
+ float tolerance)
+{
+ float max_angle;
+
+ /* the error is amplified by at most the length of the
+ * major axis of the circle; see cairo-pen.c for a more detailed analysis
+ * of this. */
+ max_angle = arc_max_angle_for_tolerance_normalized (tolerance / radius);
+
+ return ceil (fabs (angle) / max_angle);
+}
+
+/* We want to draw a single spline approximating a circular arc radius
+ R from angle A to angle B. Since we want a symmetric spline that
+ matches the endpoints of the arc in position and slope, we know
+ that the spline control points must be:
+
+ (R * cos(A), R * sin(A))
+ (R * cos(A) - h * sin(A), R * sin(A) + h * cos (A))
+ (R * cos(B) + h * sin(B), R * sin(B) - h * cos (B))
+ (R * cos(B), R * sin(B))
+
+ for some value of h.
+
+ "Approximation of circular arcs by cubic polynomials", Michael
+ Goldapp, Computer Aided Geometric Design 8 (1991) 227-238, provides
+ various values of h along with error analysis for each.
+
+ From that paper, a very practical value of h is:
+
+ h = 4/3 * R * tan(angle/4)
+
+ This value does not give the spline with minimal error, but it does
+ provide a very good approximation, (6th-order convergence), and the
+ error expression is quite simple, (see the comment for
+ _arc_error_normalized).
+*/
+static gboolean
+gsk_spline_decompose_arc_segment (const graphene_point_t *center,
+ float radius,
+ float angle_A,
+ float angle_B,
+ GskSplineAddCurveFunc curve_func,
+ gpointer user_data)
+{
+ float r_sin_A, r_cos_A;
+ float r_sin_B, r_cos_B;
+ float h;
+
+ r_sin_A = radius * sin (angle_A);
+ r_cos_A = radius * cos (angle_A);
+ r_sin_B = radius * sin (angle_B);
+ r_cos_B = radius * cos (angle_B);
+
+ h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
+
+ return curve_func ((graphene_point_t[4]) {
+ GRAPHENE_POINT_INIT (
+ center->x + r_cos_A,
+ center->y + r_sin_A
+ ),
+ GRAPHENE_POINT_INIT (
+ center->x + r_cos_A - h * r_sin_A,
+ center->y + r_sin_A + h * r_cos_A
+ ),
+ GRAPHENE_POINT_INIT (
+ center->x + r_cos_B + h * r_sin_B,
+ center->y + r_sin_B - h * r_cos_B
+ ),
+ GRAPHENE_POINT_INIT (
+ center->x + r_cos_B,
+ center->y + r_sin_B
+ )
+ },
+ user_data);
+}
+
+gboolean
+gsk_spline_decompose_arc (const graphene_point_t *center,
+ float radius,
+ float tolerance,
+ float start_angle,
+ float end_angle,
+ GskSplineAddCurveFunc curve_func,
+ gpointer user_data)
+{
+ float step = start_angle - end_angle;
+ guint i, n_segments;
+
+ /* Recurse if drawing arc larger than pi */
+ if (ABS (step) > G_PI)
+ {
+ float mid_angle = (start_angle + end_angle) / 2.0;
+
+ return gsk_spline_decompose_arc (center, radius, tolerance, start_angle, mid_angle, curve_func,
user_data)
+ && gsk_spline_decompose_arc (center, radius, tolerance, mid_angle, end_angle, curve_func,
user_data);
+ }
+ else if (ABS (step) < tolerance)
+ {
+ return TRUE;
+ }
+
+ n_segments = arc_segments_needed (ABS (step), radius, tolerance);
+ step = (end_angle - start_angle) / n_segments;
+
+ for (i = 0; i < n_segments - 1; i++, start_angle += step)
+ {
+ if (!gsk_spline_decompose_arc_segment (center, radius, start_angle, start_angle + step, curve_func,
user_data))
+ return FALSE;
+ }
+ return gsk_spline_decompose_arc_segment (center, radius, start_angle, end_angle, curve_func, user_data);
+}
+
diff --git a/gsk/gsksplineprivate.h b/gsk/gsksplineprivate.h
index 5df41077d3..a266b0d1a1 100644
--- a/gsk/gsksplineprivate.h
+++ b/gsk/gsksplineprivate.h
@@ -40,6 +40,16 @@ void gsk_spline_decompose_cubic (const graphene_
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,
+ float radius,
+ float tolerance,
+ float start_angle,
+ float end_angle,
+ GskSplineAddCurveFunc curve_func,
+ gpointer user_data);
+
G_END_DECLS
#endif /* __GSK_SPLINE_PRIVATE_H__ */
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
