path: Add gsk_path_add_circle()

Adds a circle contour, too.

4 files changed, 419 insertions, 0 deletions

diff --git a/gsk/gskpath.c b/gsk/gskpath.c
index a16b9f7c49..e5b89be7d9 100644
--- a/gsk/gskpath.c
+++ b/gsk/gskpath.c
@@ -109,6 +109,10 @@ gsk_contour_get_size_default (const GskContour *contour)
   return contour->klass->struct_size;
 }
 
+static GskContour *
+gsk_path_builder_add_contour_by_klass (GskPathBuilder        *builder,
+                                       const GskContourClass *klass);
+
 /* RECT CONTOUR */
 
 typedef struct _GskRectContour GskRectContour;
@@ -298,6 +302,201 @@ 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_init (GskContour             *contour,
+                         const graphene_point_t *center,
+                         float                   radius,
+                         float                   start_angle,
+                         float                   end_angle);
+
+static void
+gsk_circle_contour_add_segment (const GskContour *contour,
+                                GskPathBuilder   *builder,
+                                gpointer          measure_data,
+                                float             start,
+                                float             end)
+{
+  const GskCircleContour *self = (const GskCircleContour *) contour;
+  float delta = self->end_angle - self->start_angle;
+  float length = self->radius * DEG_TO_RAD (delta);
+  GskContour *segment;
+
+  segment = gsk_path_builder_add_contour_by_klass (builder, contour->klass);
+
+  gsk_circle_contour_init (segment,
+                           &self->center, self->radius,
+                           self->start_angle + start/length * delta,
+                           self->start_angle + end/length * delta);
+}
+
+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 +1720,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__ */