[cairo] [RFC] cairo_stroke_to_path implementation
Carlos Garcia Campos
carlosgc at gnome.org
Fri Jan 29 02:39:28 PST 2010
Excerpts from Jeff Muizelaar's message of vie ene 29 07:16:41 +0100 2010:
> Here's my current stroke-to-path work. Algorithmically it's basically
> where I want it to be, however it's still a bit messy, especially
> cairo-stroke-to-path.c. I welcome any comments about what needs to be
> done, stylistically and otherwise, before we can add commit this.
I can't comment on the code or algorithms, but from a user point of
view I have to say it works perfectly for me. I've used it to
implement clipToStrokePath() in poppler cairo backend and it fixes all
of the test cases affected by the lack of such method. See poppler bug
https://bugs.freedesktop.org/show_bug.cgi?id=11719
Thank you very much Jeff, really great work! :-)
> -Jeff
> diff --git a/BIBLIOGRAPHY b/BIBLIOGRAPHY
> index 90a6cef..e3081da 100644
> --- a/BIBLIOGRAPHY
> +++ b/BIBLIOGRAPHY
> @@ -44,6 +44,31 @@ Now, "convolve" the "tracing" of the pen with the tracing of
> the path:
> 24th IEEE Annual Symposium on Foundations of Computer Science
> (FOCS), November 1983, 100-111.
>
> +An alternative method involves computing an 'offset path' for the
> +convolution of the pen along the path.
> +
> + A good introduction is given by:
> +
> + "Comparing Offset Curve Approximation Methods"
> + Gershon Elber, In-Kwon Lee and Myung-Soo Kim
> + http://visualcomputing.yonsei.ac.kr/papers/1997/compare.pdf
> +
> + The algorithm suggested by this paper is:
> +
> + "Offsets of Two-Dimensional Profiles"
> + Wayne Tiller and Eric G. Hanson
> + IEEE Computer Graphics & Application, Vol 4. pp. 36-46
> +
> + The development of the symbolic global error
> + and iterative refinement is given by:
> +
> + "Free Form Surface Analysis using a Hybrid of Symbolic and Numeric
> + Computation."
> + Gershon Elber, 1992
> + http://www.cs.utah.edu/gdc/publications/papers/elber_thesis.pdf
> +
> +
> +
> The result of the convolution is a polygon that must be filled. A fill
> operations begins here. We use a very conventional Bentley-Ottmann
> pass for computing the intersections, informed by some hints on robust
> diff --git a/src/Makefile.sources b/src/Makefile.sources
> index 3cd6c48..75f9729 100644
> --- a/src/Makefile.sources
> +++ b/src/Makefile.sources
> @@ -157,7 +157,9 @@ cairo_sources = \
> cairo-slope.c \
> cairo-spans.c \
> cairo-spline.c \
> + cairo-spline-offset.c \
> cairo-stroke-style.c \
> + cairo-stroke-to-path.c \
> cairo-surface.c \
> cairo-surface-fallback.c \
> cairo-surface-clipper.c \
> diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
> index be071d1..0c1a916 100644
> --- a/src/cairo-path-fixed.c
> +++ b/src/cairo-path-fixed.c
> @@ -176,6 +176,7 @@ _cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
> return CAIRO_STATUS_SUCCESS;
> }
>
> +
> unsigned long
> _cairo_path_fixed_hash (const cairo_path_fixed_t *path)
> {
> @@ -926,6 +927,23 @@ _cairo_path_fixed_append (cairo_path_fixed_t
> *path,
> &closure);
> }
>
> +cairo_status_t
> +_cairo_path_fixed_init_flat_copy (cairo_path_fixed_t *path,
> + const cairo_path_fixed_t *other,
> + double tolerance)
> +{
> +
> + _cairo_path_fixed_init (path);
> + return _cairo_path_fixed_interpret_flat (other,
> + CAIRO_DIRECTION_FORWARD,
> + _append_move_to,
> + _append_line_to,
> + _append_close_path,
> + path,
> + tolerance);
> +}
> +
> +
> static void
> _cairo_path_fixed_offset_and_scale (cairo_path_fixed_t *path,
> cairo_fixed_t offx,
> diff --git a/src/cairo-path-private.h b/src/cairo-path-private.h
> index a24eaa4..53a0fa4 100644
> --- a/src/cairo-path-private.h
> +++ b/src/cairo-path-private.h
> @@ -54,4 +54,8 @@ cairo_private cairo_status_t
> _cairo_path_append_to_context (const cairo_path_t *path,
> cairo_t *cr);
>
> +cairo_private cairo_path_t *
> +_cairo_stroked_path_create (cairo_path_fixed_t *path_fixed,
> + cairo_gstate_t *gstate);
> +
> #endif /* CAIRO_PATH_DATA_PRIVATE_H */
> diff --git a/src/cairo-path.c b/src/cairo-path.c
> index 29c968e..129059d 100644
> --- a/src/cairo-path.c
> +++ b/src/cairo-path.c
> @@ -360,6 +360,58 @@ _cairo_path_create_internal (cairo_path_fixed_t
> *path_fixed,
> return path;
> }
>
> +cairo_path_t *
> +_cairo_stroked_path_create (cairo_path_fixed_t *path_fixed,
> + cairo_gstate_t *gstate)
> +{
> + cairo_path_t *path;
> +
> + path = malloc (sizeof (cairo_path_t));
> + if (unlikely (path == NULL)) {
> + _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
> + return (cairo_path_t*) &_cairo_path_nil;
> + }
> +
> + cairo_path_fixed_t stroke_path;
> +
> + _cairo_path_fixed_init (&stroke_path);
> +
> + _cairo_path_stroke_to_path (path_fixed,
> + &gstate->stroke_style,
> + &stroke_path,
> + &gstate->ctm,
> + &gstate->ctm_inverse,
> + gstate->tolerance);
> +
> + path->num_data = _cairo_path_count (path, &stroke_path,
> + gstate->tolerance,
> + FALSE);
> + if (path->num_data < 0) {
> + free (path);
> + _cairo_path_fixed_fini (&stroke_path);
> + return (cairo_path_t*) &_cairo_path_nil;
> + }
> +
> + if (path->num_data) {
> + path->data = _cairo_malloc_ab (path->num_data,
> + sizeof (cairo_path_data_t));
> + if (unlikely (path->data == NULL)) {
> + free (path);
> + _cairo_error_throw (CAIRO_STATUS_NO_MEMORY);
> + return (cairo_path_t*) &_cairo_path_nil;
> + }
> +
> + path->status = _cairo_path_populate (path, &stroke_path,
> + gstate, FALSE);
> + } else {
> + path->data = NULL;
> + path->status = CAIRO_STATUS_SUCCESS;
> + }
> + _cairo_path_fixed_fini (&stroke_path);
> +
> + return path;
> +}
> +
> /**
> * cairo_path_destroy:
> * @path: a path previously returned by either cairo_copy_path() or
> diff --git a/src/cairo-spline-offset.c b/src/cairo-spline-offset.c
> new file mode 100644
> index 0000000..283ed37
> --- /dev/null
> +++ b/src/cairo-spline-offset.c
> @@ -0,0 +1,945 @@
> +/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
> +/* cairo - a vector graphics library with display and print output
> + *
> + * Copyright © 2009 Mozilla Foundation
> + * Copyright © 2010 Jeff Muizelaar
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it either under the terms of the GNU Lesser General Public
> + * License version 2.1 as published by the Free Software Foundation
> + * (the "LGPL") or, at your option, under the terms of the Mozilla
> + * Public License Version 1.1 (the "MPL"). If you do not alter this
> + * notice, a recipient may use your version of this file under either
> + * the MPL or the LGPL.
> + *
> + * You should have received a copy of the LGPL along with this library
> + * in the file COPYING-LGPL-2.1; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
> + * You should have received a copy of the MPL along with this library
> + * in the file COPYING-MPL-1.1
> + *
> + * The contents of this file are subject to the Mozilla Public License
> + * Version 1.1 (the "License"); you may not use this file except in
> + * compliance with the License. You may obtain a copy of the License at
> + * http://www.mozilla.org/MPL/
> + *
> + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
> + * OF ANY KIND, either express or implied. See the LGPL or the MPL for
> + * the specific language governing rights and limitations.
> + *
> + * The Original Code is the cairo graphics library.
> + *
> + * The Initial Developer of the Original Code is Jeff Muizelaar
> + *
> + */
> +
> +#define _GNU_SOURCE
> +
> +#include "cairoint.h"
> +
> +#include <math.h>
> +#include <stdio.h>
> +#include <assert.h>
> +#include <stdlib.h>
> +
> +#if _XOPEN_SOURCE >= 600 || defined (_ISOC99_SOURCE)
> +#define ISFINITE(x) isfinite (x)
> +#else
> +#define ISFINITE(x) ((x) * (x) >= 0.) /* check for NaNs */
> +#endif
> +
> +#include "cairoint.h"
> +#include "cairo-spline-offset.h"
> +
> +static void
> +_lerp (const point_t *a, const point_t *b, point_t *result, double t)
> +{
> + result->x = (1-t)*a->x + t*b->x;
> + result->y = (1-t)*a->y + t*b->y;
> +}
> +
> +/* returns false if there could be a discontinuity
> + * between the split curves */
> +static cairo_bool_t
> +_de_casteljau_t (knots_t *k1, knots_t *k2, double t)
> +{
> + point_t ab, bc, cd;
> + point_t abbc, bccd;
> + point_t final;
> +
> + _lerp (&k1->a, &k1->b, &ab, t);
> + _lerp (&k1->b, &k1->c, &bc, t);
> + _lerp (&k1->c, &k1->d, &cd, t);
> + _lerp (&ab, &bc, &abbc, t);
> + _lerp (&bc, &cd, &bccd, t);
> + _lerp (&abbc, &bccd, &final, t);
> +
> + k2->a = final;
> + k2->b = bccd;
> + k2->c = cd;
> + k2->d = k1->d;
> +
> + k1->b = ab;
> + k1->c = abbc;
> + k1->d = final;
> +
> + /* we can test whether the split curve will have a cusp
> + * inbetween the two parts by checking the length of the
> + * line abbc-bccd. If this line has a non-zero length
> + * then the two curves will share a common normal
> + * at the points where they meet. Therefore the
> + * length must be zero for the normals to be different.
> + * However this condition is necessary but not sufficient.
> + * XXX: does this matter and how should we deal with it if it does? */
> + return abbc.x != final.x || abbc.y != final.y;
> +}
> +
> +typedef point_t vector_t;
> +
> +static vector_t
> +begin_tangent (knots_t c)
> +{
> + vector_t t;
> + if (c.a.x != c.b.x || c.a.y != c.b.y) {
> + t.x = c.b.x - c.a.x;
> + t.y = c.b.y - c.a.y;
> + return t;
> + }
> + if (c.a.x != c.c.x || c.a.y != c.c.y) {
> + t.x = c.c.x - c.a.x;
> + t.y = c.c.y - c.a.y;
> + return t;
> + }
> + t.x = c.d.x - c.a.x;
> + t.y = c.d.y - c.a.y;
> + return t;
> +}
> +
> +static vector_t
> +end_tangent (knots_t c)
> +{
> + vector_t t;
> + if (c.d.x != c.c.x || c.d.y != c.c.y) {
> + t.x = c.d.x - c.c.x;
> + t.y = c.d.y - c.c.y;
> + return t;
> + }
> + if (c.d.x != c.b.x || c.d.y != c.b.y) {
> + t.x = c.d.x - c.b.x;
> + t.y = c.d.y - c.b.y;
> + return t;
> + }
> + t.x = c.d.x - c.a.x;
> + t.y = c.d.y - c.a.y;
> + return t;
> +}
> +
> +static void
> +ensure_finite (knots_t k)
> +{
> +
> + if (!(
> + isfinite(k.a.x) &&
> + isfinite(k.a.y) &&
> + isfinite(k.b.x) &&
> + isfinite(k.b.y) &&
> + isfinite(k.c.x) &&
> + isfinite(k.c.y) &&
> + isfinite(k.d.x) &&
> + isfinite(k.d.y))) {
> + print_knot(k);
> + assert(0);
> + }
> +}
> +
> +#if 0
> +static void ensure_smoothness (knots_t a, knots_t b)
> +{
> + double dist_len = hypot(a.d.x - b.a.x, a.d.y - b.a.y);
> + print_knot(a);
> + print_knot(b);
> + printf("dist: %f\n", dist_len);
> + vector_t in_norm = end_tangent(a);
> + vector_t out_norm = begin_tangent(b);
> + double in_a = atan2 (in_norm.y, in_norm.x);
> + double out_a = atan2 (out_norm.y, out_norm.x);
> + if (in_a < out_a)
> + in_a += 2*M_PI;
> + double diff = in_a - out_a;
> + if (diff > M_PI)
> + diff -= M_PI*2;
> + if (!(fabs(diff) < 0.001) && !(fabs(diff - M_PI) < 0.001) && !(fabs(diff +
> M_PI) < 0.001)) {
> + /* The angle difference between normals can be either 0 or +-M_PI for
> a change in direction.
> + * The change in direction can occur in a region of high curvature
> with a large offset direction.
> + * We move in reverse if the offset distance exceeds the radius of
> curvature. Note: that you need to
> + * use signed curvature for this too work out properly. Because we
> only encounter this phenomenom in
> + * the convex areas of the curve.
> + *
> + * XXX: explain why... */
> + printf("angle diff: %f %f %f\n", diff, in_a, out_a);
> + print_knot(a);
> + print_knot(b);
> + assert(0);
> + }
> + if (fabs(dist_len) > 0.01) {
> + printf("distlen: %f\n", dist_len);
> + print_knot(a);
> + print_knot(b);
> + assert(0);
> + }
> +}
> +
> +static void
> +ensure_smoothness2 (knots_t a, knots_t b, cairo_bool_t ccw) {
> + vector_t in_norm = end_tangent(a);
> + vector_t out_norm = begin_tangent(b);
> + if (!ccw) {
> + in_norm = end_tangent(a);
> + out_norm = begin_tangent(b);
> + }
> + double in_a = atan2 (in_norm.y, in_norm.x);
> + double out_a = atan2 (out_norm.y, out_norm.x);
> + if (in_a < out_a)
> + in_a += 2*M_PI;
> + double diff = in_a - out_a;
> + if (diff > M_PI)
> + diff -= M_PI*2;
> + if (fabs(diff) > 0.01) {
> + printf("gangle diff: %f\n", diff);
> + print_knot(a);
> + print_knot(b);
> + }
> +}
> +#endif
> +
> +static inline vector_t
> +flip (vector_t a)
> +{
> + vector_t ar;
> + ar.x = -a.x;
> + ar.y = -a.y;
> + return ar;
> +}
> +
> +static vector_t
> +perp (vector_t v)
> +{
> + vector_t p = {-v.y, v.x};
> + return p;
> +}
> +
> +static inline double
> +dot (vector_t a, vector_t b)
> +{
> + return a.x * b.x + a.y * b.y;
> +}
> +
> +static vector_t
> +normalize (vector_t v)
> +{
> + double len = hypot(v.x, v.y);
> + v.x /= len;
> + v.y /= len;
> + return v;
> +}
> +
> +/* given a normal rotate the vector 90 degrees to the right clockwise
> + * This function has a period of 4. e.g. swap(swap(swap(swap(x) == x */
> +static vector_t
> +swap (vector_t a)
> +{
> + vector_t ar;
> + /* one of these needs to be negative. We choose a.x so that we rotate to
> the right instead of negating */
> + ar.x = a.y;
> + ar.y = -a.x;
> + return ar;
> +}
> +
> +static vector_t
> +unperp (vector_t a)
> +{
> + return swap (a);
> +}
> +
> +typedef struct {
> + double t1;
> + double t2;
> +} inflection_points_t;
> +
> +/* Find the inflection points for a knots_t.
> + * The lower inflection point is returned in t1, the higher one in t2.
> + *
> + * This method for computing inflections points is from:
> + * "Fast, precise flattening of cubic Bezier path and offset curves", Hain et.
> al */
> +static inflection_points_t
> +inflection_points (knots_t s)
> +{
> + inflection_points_t ret;
> +
> + point_t a = {x: -s.a.x + 3*s.b.x - 3*s.c.x + s.d.x, -s.a.y + 3*s.b.y -
> 3*s.c.y + s.d.y};
> + point_t b = {x: 3*s.a.x - 6*s.b.x + 3*s.c.x, 3*s.a.y - 6*s.b.y +
> 3*s.c.y};
> + point_t c = {x:-3*s.a.x + 3*s.b.x, -3*s.a.y + 3*s.b.y};
> + /* we don't need 'd'
> + point_t d = {x: s.a.x, s.a.y};
> + */
> +
> + /* we're solving for the roots of this equation:
> + dx/dt * d2y/dt2 - d2x/dt2 * dy/dt
> + == 6*(a.y*b.x - a.x*b.y)*t^2 +6*(a.y*c.x-a.x*c.y)*t + 2*(b.y*c.x -
> b.x*c.y)
> + */
> + double t_cusp = (-1./2)*((a.y*c.x - a.x*c.y)/(a.y*b.x - a.x*b.y));
> + double t_inner = (t_cusp*t_cusp - ((b.y*c.x - b.x*c.y)/(a.y*b.x -
> a.x*b.y))/3);
> +
> + if (t_inner > 0) {
> + double t_adj = sqrt (t_inner);
> + ret.t1 = t_cusp - t_adj;
> + ret.t2 = t_cusp + t_adj;
> + } else {
> + ret.t1 = ret.t2 = t_cusp;
> + }
> + return ret;
> +}
> +
> +/* this function could use some tests.
> + I believe it only works for angles from 0 to pi. It will always use the
> smaller arc between the two vectors? */
> +static knots_t
> +arc_segment_cart (point_t start, point_t end, double radius, vector_t a,
> vector_t b)
> +{
> + knots_t arc;
> + double r_sin_A = radius * a.y;
> + double r_cos_A = radius * a.x;
> + double r_sin_B = radius * b.y;
> + double r_cos_B = radius * b.x;
> +
> + point_t mid, mid2;
> + double l, h;
> +
> + mid.x = a.x + b.x;
> + mid.y = a.y + b.y;
> + if (dot (a, b) < 0) {
> + /* otherwise, we can flip a, add it
> + * and then use the perpendicular of the result */
> + a = flip (a);
> + mid.x = a.x + b.x;
> + mid.y = a.y + b.y;
> + if (dot (a, perp(b)) <= 0) {
> + mid = unperp (mid);
> + } else {
> + mid = perp(mid);
> + }
> + }
> + /* normalize */
> + l = sqrt(mid.x*mid.x + mid.y*mid.y);
> + mid.x /= l;
> + mid.y /= l;
> +
> + mid2.x = a.x + mid.x;
> + mid2.y = a.y + mid.y;
> +
> + h = (4./3.)*dot(perp(a), mid2)/dot(a, mid2);
> +
> + arc.a.x = start.x;
> + arc.a.y = start.y;
> +
> + arc.b.x = start.x - h * r_sin_A;
> + arc.b.y = start.y + h * r_cos_A;
> +
> + arc.c.x = end.x + h * r_sin_B;
> + arc.c.y = end.y - h * r_cos_B;
> +
> + arc.d.x = end.x;
> + arc.d.y = end.y;
> +
> + return arc;
> +}
> +
> +static knots_t
> +quarter_circle (double xc, double yc, double radius, vector_t normal)
> +{
> + double r_sin_A, r_cos_A;
> + double r_sin_B, r_cos_B;
> + double h;
> + knots_t arc;
> +
> + r_sin_A = radius * normal.y;
> + r_cos_A = radius * normal.x;
> + r_sin_B = radius * -normal.x; /* sin (angle_B); */
> + r_cos_B = radius * normal.y; /* cos (angle_B); */
> +
> + h = -0.55228474983079345; /* 4.0/3.0 * tan ((-M_PI/2) / 4.0); */
> +
> + arc.a.x = xc + r_cos_A;
> + arc.a.y = yc + r_sin_A;
> +
> + arc.b.x = xc + r_cos_A - h * r_sin_A;
> + arc.b.y = yc + r_sin_A + h * r_cos_A;
> +
> + arc.c.x = xc + r_cos_B + h * r_sin_B;
> + arc.c.y = yc + r_sin_B - h * r_cos_B;
> +
> + arc.d.x = xc + r_cos_B;
> + arc.d.y = yc + r_sin_B;
> +
> + return arc;
> +}
> +
> +static void semi_circle (double xc, double yc, double radius, vector_t
> out_normal, void (*curve_fn)(void *, knots_t), void *closure)
> +{
> + double len = hypot (out_normal.y, out_normal.x);
> + vector_t mid_normal;
> +
> + out_normal.x /= len;
> + out_normal.y /= len;
> +
> + mid_normal.x = out_normal.y; /* we need to rotate by -M_PI/2 */
> + mid_normal.y = -out_normal.x;
> +
> + curve_fn(closure, quarter_circle (xc, yc, radius, out_normal));
> + curve_fn(closure, quarter_circle (xc, yc, radius, mid_normal));
> +}
> +
> +static cairo_bool_t
> +is_knot_flat (knots_t c)
> +{
> + /*
> + A well-known flatness test is both cheaper and more reliable
> + than the ones you have tried. The essential observation is that
> + when the curve is a uniform speed straight line from end to end,
> + the control points are evenly spaced from beginning to end.
> + Therefore, our measure of how far we deviate from that ideal
> + uses distance of the middle controls, not from the line itself,
> + but from their ideal *arrangement*. Point 2 should be halfway
> + between points 1 and 3; point 3 should be halfway between points
> + 2 and 4.
> + This, too, can be improved. Yes, we can eliminate the square roots
> + in the distance tests, retaining the Euclidean metric; but the
> + taxicab metric is faster, and also safe. The length of displacement
> + (x,y) in this metric is |x|+|y|.
> + */
> +
> + /* XXX: this isn't necessarily the best test because it
> + tests for flatness instead of smallness.
> + however, flat things will be offseted easily so we sort of implicitly
> do the right thing
> + */
> + /* this value should be much less than the tolerance because we only want
> to deal with situations where
> + * the curvature is extreme. */
> + double stop_value = 0.05;
> + double error = 0;
> + error += fabs((c.c.x - c.b.x) - (c.b.x - c.a.x));
> + error += fabs((c.c.y - c.b.y) - (c.b.y - c.a.y));
> + error += fabs((c.c.x - c.b.x) - (c.d.x - c.c.x));
> + error += fabs((c.c.y - c.b.y) - (c.d.y - c.c.y));
> + return error <= stop_value;
> +}
> +
> +/* Finds the coefficient with the maximum error. This should be
> + * the coefficient closest to area of maximum error.
> + * This returns an upper bound of the error. */
> +static cairo_bool_t
> +is_curvy_t (double *bezier, int degree, double stop_value, double *t)
> +{
> + double highest_error = .5;
> + double error = 0;
> + int i=0;
> + assert(degree == 6);
> + for (i=0; i<=degree; i++) {
> + if (fabs(bezier[i]) > error) {
> + error = fabs(bezier[i]);
> + highest_error = i/(double)degree;
> + }
> + }
> + *t = highest_error;
> +
> + /* we shouldn't ever split at the edges because the approximation
> + * should be perfect there. XXX: we might be able to take
> + * advantage of this when computing the error polynomial. */
> +#if 0
> + if (*t == 0 || *t == 1) {
> + for (i=0; i<=degree; i++) {
> + error = fabs(bezier[i]);
> + printf("error: %f\n", error);
> + }
> + assert(0);
> + }
> +#endif
> + /* *t = 0.5; */
> + return error >= stop_value;
> +}
> +
> +static cairo_bool_t
> +error_within_bounds_elber (knots_t bz1, knots_t bz_offset_approx,
> + double desired_offset,
> + double max_error,
> + double *t)
> +{
> + double bzprod[3+3 +1] = {};
> +
> + /* Elber and Cohnen propose the following method of computing the
> + error between an curve and it's offset:
> + e(t) = || C(t) - Coffset_approx(t) ||^2 - offset^2
> +
> + It is important to note that this function doesn't represent a unique
> offset curve.
> + For example, it's possible for the offset curve to cross the original
> spline
> + provided it stays the appropriate distance away:
> +
> + xxx
> + x
> + ****
> + **x
> + * x
> + * x
> + * x
> + **
> + ****
> + x
> + xxx
> +
> + "Planar Curve Offset Base on Circle Approximation" suggests further
> problems
> + with this error measure. They give the following example: C(t) + (r, 0)
> will
> + have an error mesaure of 0, but is not even close to the actual offset
> curve.
> +
> + This paper suggests using the angle between the difference vector and
> the normal
> + at point t, but doesn't go into much detail.
> + */
> +
> + /* Now we compute this error function.
> + * First, subtract the approx */
> + bz1.a.x -= bz_offset_approx.a.x;
> + bz1.a.y -= bz_offset_approx.a.y;
> + bz1.b.x -= bz_offset_approx.b.x;
> + bz1.b.y -= bz_offset_approx.b.y;
> + bz1.c.x -= bz_offset_approx.c.x;
> + bz1.c.y -= bz_offset_approx.c.y;
> + bz1.d.x -= bz_offset_approx.d.x;
> + bz1.d.y -= bz_offset_approx.d.y;
> +/*
> + Next we compute the dot product of bz1 with itself This involves squaring
> + the x and y polynomials and adding the result together.
> +
> + However, we want to multiply the coefficients so that we can treat the
> + result as a higher degree bezier curve.
> +
> + The following method is given in the Symbolic Computation section of
> + "Comparing Offset Curve Approximation Methods" by Elber, Lee and Kim
> +
> + k l ⎛ k⎞ i k-i⎛ l⎞ j l-j
> + B (t) B (t) = ⎜ ⎟ t (1-t) ⎜ ⎟ t (1-t)
> + i j ⎝ i⎠ ⎝ j⎠
> + ⎛ k⎞ ⎛ l⎞ i+j k+l-i-j
> + = ⎜ ⎟ ⎜ ⎟ t (1-t)
> + ⎝ i⎠ ⎝ j⎠
> +
> + ⎛ k⎞ ⎛ l⎞
> + = ⎝ i⎠ ⎝ j⎠ k+l
> + ──────── B (t)
> + ⎛ k + l⎞ i+j
> + ⎝ i + j⎠
> +
> + m n
> +C1(t) C2(t) = ∑ P_i B_i,m (t) ∑ P_j B_j,n (t)
> + i=0 j=0
> +
> + m n
> + = ∑ ∑ P_i P_j B_i,m (t) B_j,n (t)
> + i=0 j=0
> +
> + m+n m + n
> + = ∑ Q_k B_k (t)
> + k=0
> +
> +Where Q_k is:
> + ⎛ m⎞ ⎛ n⎞
> + ⎝ i⎠ ⎝ j⎠
> + Q_k = P_i * P_j ─────────
> + ⎛ m+n⎞
> + ⎝ i+j⎠
> +
> +And for the case of degree 3 beziers
> +
> + ⎛ 3⎞ ⎛ 3⎞
> + ⎝ i⎠ ⎝ j⎠
> + Q_k = P_i * P_j ─────────
> + ⎛ 6 ⎞
> + ⎝ i+j⎠
> +
> + This expands to:
> +
> + i j
> + 0 0 0 = (1 * 1) / 1 = 1
> +
> + 0 1 1 = (1 * 3) / 6 = .5
> + 1 0 1 = (3 * 1) / 6 = .5
> +
> + 0 2 2 = (1 * 3) / 15 = .2
> + 1 1 2 = (3 * 3) / 15 = .6
> + 2 0 2 = (3 * 1) / 15 = .2
> +
> + 0 3 3 = (1 * 1) / 20 = .05
> + 1 2 3 = (3 * 3) / 20 = .45
> + 2 1 3 = (3 * 3) / 20 = .45
> + 3 0 3 = (1 * 1) / 20 = .05
> +
> + 1 3 4 = (3 * 1) / 15 = .2
> + 2 2 4 = (3 * 3) / 15 = .6
> + 3 1 4 = (1 * 3) / 15 = .2
> +
> + 2 3 5 = (3 * 1) / 6 = .5
> + 3 2 5 = (1 * 3) / 6 = .5
> +
> + 3 3 6 = (1 * 1) / 1 = 1
> +
> +Which simplifies to the following:
> + */
> +
> +
> + bzprod[0] += bz1.a.x * bz1.a.x;
> + bzprod[0] += bz1.a.y * bz1.a.y;
> +
> + bzprod[1] += bz1.a.x * bz1.b.x;
> + bzprod[1] += bz1.a.y * bz1.b.y;
> +
> + bzprod[2] += bz1.a.x * bz1.c.x * 0.4;
> + bzprod[2] += bz1.b.x * bz1.b.x * 0.6;
> + bzprod[2] += bz1.a.y * bz1.c.y * 0.4;
> + bzprod[2] += bz1.b.y * bz1.b.y * 0.6;
> +
> + bzprod[3] += bz1.d.x * bz1.a.x * 0.1;
> + bzprod[3] += bz1.b.x * bz1.c.x * 0.9;
> + bzprod[3] += bz1.d.y * bz1.a.y * 0.1;
> + bzprod[3] += bz1.b.y * bz1.c.y * 0.9;
> +
> + bzprod[4] += bz1.b.x * bz1.d.x * 0.4;
> + bzprod[4] += bz1.c.x * bz1.c.x * 0.6;
> + bzprod[4] += bz1.d.y * bz1.b.y * 0.4;
> + bzprod[4] += bz1.c.y * bz1.c.y * 0.6;
> +
> + bzprod[5] += bz1.c.x * bz1.d.x;
> + bzprod[5] += bz1.d.y * bz1.c.y;
> +
> + bzprod[6] += bz1.d.x * bz1.d.x;
> + bzprod[6] += bz1.d.y * bz1.d.y;
> +
> +
> + /* the result is a bezier polynomial that represents the distance
> squared between
> + * the two input polynomials */
> +
> + /* we don't need to subtract the desired offset because our metric
> doesn't depend on being centered around 0 */
> +#if 1
> + bzprod[0] -= (desired_offset*desired_offset);
> + bzprod[1] -= (desired_offset*desired_offset);
> + bzprod[2] -= (desired_offset*desired_offset);
> + bzprod[3] -= (desired_offset*desired_offset);
> + bzprod[4] -= (desired_offset*desired_offset);
> + bzprod[5] -= (desired_offset*desired_offset);
> + bzprod[6] -= (desired_offset*desired_offset);
> +#endif
> + *t = 0.5;
> + return !is_curvy_t(bzprod, sizeof(bzprod)/sizeof(bzprod[0])-1,
> max_error, t);
> +}
> +
> +void
> +print_knot (knots_t c) {
> + /*printf("(%.13a %.13a) (%.13a %.13a) (%.13a %.13a) (%.13a %.13a)\n",
> c.a.x, c.a.y, c.b.x, c.b.y, c.c.x, c.c.y, c.d.x, c.d.y);*/
> + printf("(%.5f %.5f) (%.5f %.5f) (%.5f %.5f) (%.5f %.5f)\n", c.a.x,
> c.a.y, c.b.x, c.b.y, c.c.x, c.c.y, c.d.x, c.d.y);
> +}
> +
> +static knots_t
> +convolve_with_circle (knots_t spline, double dist)
> +{
> + vector_t in_normal = normalize(perp(begin_tangent(spline)));
> + vector_t out_normal = normalize(perp(end_tangent(spline)));
> + /* find an arc the goes from the input normal to the output_normal */
> + knots_t arc_spline = arc_segment_cart(in_normal, out_normal, 1, in_normal,
> out_normal);
> +
> + /* approximate convolving 'spline' with the arc spline (XXX: is convolve
> the right word?) */
> + spline.a.x += dist * arc_spline.a.x;
> + spline.a.y += dist * arc_spline.a.y;
> + spline.b.x += dist * arc_spline.b.x;
> + spline.b.y += dist * arc_spline.b.y;
> + spline.c.x += dist * arc_spline.c.x;
> + spline.c.y += dist * arc_spline.c.y;
> + spline.d.x += dist * arc_spline.d.x;
> + spline.d.y += dist * arc_spline.d.y;
> +
> + return spline;
> +}
> +
> +/* This approach is inspired by "Approximation of circular arcs and offset
> curves by Bezier curves of high degree"
> + * by YJ Ahn, Y soo Kim, Y Shin.
> + *
> + * This is a similar idea to:
> + * "Offset approximation based on reparameterizaing the path of a moving
> point along the base circle", ZHAO, WANG
> + * and a bunch of papers by Lee et al.
> + * "Planar curve offset based on circle approximation"
> + * "New approximation methods of planar offset and convolution curves"
> + * "Polynomial/rational approximation of Minkowski sum boundary curves"
> + *
> + * However these other approaches produce curves of higher degree than the
> input curve making them unsuitable
> + * for use here.
> + * */
> +static void
> +approximate_offset_curve_with_shin (knots_t self, double dist, void
> (*curve_fn)(void *, knots_t), void *closure)
> +{
> + /* since we're going to approximating the offset curve with arcs
> + we want to ensure that we don't have any inflection points in our
> spline */
> + inflection_points_t t_inflect = inflection_points(self);
> +
> + /* split the curve at the inflection points and convolve each with an
> approximation of
> + * a circle */
> + knots_t remaining = self;
> + double adjusted_inflect = t_inflect.t2;
> +
> + /* check that the first inflection point is in range */
> + if (t_inflect.t1 > 0 && t_inflect.t1 < 1) {
> + /* split at the inflection point */
> + _de_casteljau_t (&self, &remaining, t_inflect.t1);
> +
> + /* approximate */
> + curve_fn(closure, convolve_with_circle(self, dist));
> +
> + /* reparamaterize the second inflection point over the 'remaining'
> spline:
> + * (domain between inflection points)/(domain of remaining) */
> + adjusted_inflect = (t_inflect.t2-t_inflect.t1)/(1 - t_inflect.t1);
> + }
> +
> + /* check that the second inflection point is in range and not equal to t1.
> + * we don't use the reparameterized value so that test remains simple */
> + if (t_inflect.t2 > t_inflect.t1 && t_inflect.t2 > 0 && t_inflect.t2 < 1) {
> + /* split into one segment */
> + knots_t self = remaining;
> + _de_casteljau_t (&self, &remaining, adjusted_inflect);
> + curve_fn(closure, convolve_with_circle(self, dist));
> + }
> +
> + /* deal with what's left of the spline */
> + curve_fn(closure, convolve_with_circle(remaining, dist));
> +}
> +
> +/* Computes the offset polygon for the control polygon of spline. We can
> + * use this is an approximation of the offset spline. This approximation is
> + * give by Tiller W, Hanson E G. in "Offsets of two-dimensional profile" */
> +static knots_t
> +knot_offset (knots_t self, double width, cairo_bool_t *is_parallel)
> +{
> + /* this code is inspired by the libart mitreing code */
> +
> + /* difference vectors between each point in the knot */
> + double dx0, dy0, dx1, dy1, dx2, dy2;
> + /* difference vector lengths */
> + double ld0, ld1, ld2;
> + /* temporary vector for dealing with degeneracies */
> + double last_x, last_y;
> +
> + double scale;
> +
> + /* normalized normal vectors for each difference vector */
> + double dlx0, dly0, dlx1, dly1, dlx2, dly2;
> +
> + /* bisected/midpoint vectors */
> + double dm1x, dm1y, dm2x, dm2y;
> +
> + double dmr2_1, dmr2_2;
> +
> + knots_t result;
> +
> + dx0 = self.b.x - self.a.x;
> + dy0 = self.b.y - self.a.y;
> + ld0 = sqrt(dx0*dx0 + dy0*dy0);
> +
> + dx1 = self.c.x - self.b.x;
> + dy1 = self.c.y - self.b.y;
> + ld1 = sqrt(dx1*dx1 + dy1*dy1);
> +
> + dx2 = self.d.x - self.c.x;
> + dy2 = self.d.y - self.c.y;
> + ld2 = sqrt(dx2*dx2 + dy2*dy2);
> +
> + /* compute normalized normals */
> + scale = 1. / ld0;
> + dlx0 = -dy0 * scale;
> + dly0 = dx0 * scale;
> +
> + scale = 1. / ld1;
> + dlx1 = -dy1 * scale;
> + dly1 = dx1 * scale;
> +
> + scale = 1. / ld2;
> + dlx2 = -dy2 * scale;
> + dly2 = dx2 * scale;
> +
> + /* deal with any degeneracies in the spline by treating
> + * degenerate segments as having the same normal
> + * as their neighbour. If all of the segments are degenerate
> + * than we will fail the is_parallel test below */
> + last_x = 0;
> + last_y = 0;
> +
> + /* first pass */
> + if (ld0) {
> + last_x = dlx0;
> + last_y = dly0;
> + }
> + if (ld1) {
> + last_x = dlx1;
> + last_y = dly1;
> + }
> + if (ld2) {
> + last_x = dlx2;
> + last_y = dly2;
> + }
> +
> + /* second pass */
> + if (!ld2) {
> + dlx2 = last_x;
> + dly2 = last_y;
> + } else {
> + last_x = dlx2;
> + last_y = dly2;
> + }
> + if (!ld1) {
> + dlx1 = last_x;
> + dly1 = last_y;
> + } else {
> + last_x = dlx1;
> + last_y = dly1;
> + }
> + if (!ld0) {
> + dlx0 = last_x;
> + dly0 = last_y;
> + } else {
> + last_x = dlx0;
> + last_y = dly0;
> + }
> +
> + /* mid-point vector sum */
> + dm1x = (dlx0 + dlx1);
> + dm1y = (dly0 + dly1);
> +
> + dm2x = (dlx1 + dlx2);
> + dm2y = (dly1 + dly2);
> +
> + /* length squared of the mid-point vector sum */
> + dmr2_1 = (dm1x * dm1x + dm1y * dm1y);
> + dmr2_2 = (dm2x * dm2x + dm2y * dm2y);
> +
> + /* the choice of this EPSILON is arbitrary and could use further study */
> +#define PARALLEL_EPSILON 1e-6
> + if (fabs(dmr2_1) < PARALLEL_EPSILON || fabs(dmr2_2) < PARALLEL_EPSILON)
> + *is_parallel = TRUE;
> + else
> + *is_parallel = FALSE;
> +
> + scale = width * 2 / dmr2_1;
> + dm1x *= scale;
> + dm1y *= scale;
> +
> + scale = width * 2 / dmr2_2;
> + dm2x *= scale;
> + dm2y *= scale;
> +
> + /* write out the result */
> + result.a.x = self.a.x + dlx0 * width;
> + result.a.y = self.a.y + dly0 * width;
> +
> + result.b.x = self.b.x + dm1x;
> + result.b.y = self.b.y + dm1y;
> +
> + result.c.x = self.c.x + dm2x;
> + result.c.y = self.c.y + dm2y;
> +
> + result.d.x = self.d.x + dlx2 * width;
> + result.d.y = self.d.y + dly2 * width;
> +
> + return result;
> +}
> +
> +/* plan:
> + * if we approximate the original bezier curve with line segments
> + * and then produce an offset to those lines. We will end up
> + * with sharp angles at places of high curvature.
> + *
> + * It is at these places of high curvature that we want to approximate
> + * the offset with an arc instead of continuing to subdivide.
> + *
> + * How do we find the areas of high curvature?
> + * - Ideas:
> + * As we subdivide the original bezier
> + * we can get an idea of how flat it is.
> + * If the original bezier is flat but the offset approximation is not within
> our bounds
> + * we should stop recursing and approximate the segment with an arc.
> + *
> + * The degree of required flatness of the original curve should be related
> to the
> + * the offset length. The greater the offset distance the less flat the
> original
> + * bezier needs to be.
> + *
> + * pros:
> + * - this gives us an easier condition to reason about the termination of the
> + * algorithm because we terminate the recursion when the input bezier has
> + * been subdivided to 'flat' instead of when the offset is good.
> + * This is valuable because it's possible to create an input curve that
> does not have a
> + * good offset approximation down to the resolution of a double.
> + */
> +void
> +curve_offset (knots_t self, double dist, double tolerance, void
> (*curve_fn)(void *, knots_t), void *closure)
> +{
> + cairo_bool_t recurse;
> + double break_point;
> + double max_error = tolerance;
> + knots_t offset = knot_offset(self, dist, &recurse);
> +
> + if (!recurse) {
> + /* we need to make sure we have a finite offset before checking the
> error */
> + ensure_finite(offset);
> + recurse = !error_within_bounds_elber(self, offset, dist, max_error,
> &break_point);
> + } else {
> + /* TODO: we could probably choose a better place to split than halfway
> + * for times when we know we're going to recurse */
> + break_point = .5;
> + }
> +
> + if (recurse) {
> + /* error is too large. subdivide on max t and try again. */
> + knots_t left = self;
> + knots_t right;
> +
> + cairo_bool_t is_continuous;
> +
> + /* We need to do something to handle regions of high curvature
> + *
> + * skia uses the first and second derivitives at the points of 'max
> curvature' to check for
> + * pinchynes.
> + * qt tests whether the points are close and reverse direction.
> + * float l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) + (orig->y3
> - orig->y4)*(orig->y3 - orig->y4);
> + * float dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) + (orig->y1
> - orig->y2)*(orig->y3 - orig->y4);
> + *
> + * we just check if the knot is flat and has large error.
> + */
> + if (is_knot_flat(self)) {
> + /* we don't want to recurse anymore because we're pretty flat,
> + * instead approximate the offset curve with an arc.
> + *
> + * The previously generated offset curve can become really bad if
> the the intersections
> + * are far away from the original curve (self) */
> +
> + approximate_offset_curve_with_shin (self, dist, curve_fn, closure);
> + return;
> + }
> +
> + is_continuous = _de_casteljau_t(&left, &right, break_point);
> +
> + curve_offset(left, dist, tolerance, curve_fn, closure);
> +
> + if (!is_continuous) {
> + /* add circle:
> + we can use the exit the normal from the left side
> + as the begining normal of our cusp */
> + vector_t normal = perp (end_tangent (left));
> + semi_circle (left.d.x, left.d.y, dist, normal, curve_fn, closure);
> + }
> +
> + curve_offset(right, dist, tolerance, curve_fn, closure);
> + } else {
> + curve_fn(closure, offset);
> + }
> +}
> +
> diff --git a/src/cairo-spline-offset.h b/src/cairo-spline-offset.h
> new file mode 100644
> index 0000000..9faa2cb
> --- /dev/null
> +++ b/src/cairo-spline-offset.h
> @@ -0,0 +1,18 @@
> +typedef cairo_point_double_t point_t;
> +typedef struct _knots {
> + point_t a,b,c,d;
> +} knots_t;
> +
> +void print_knot(knots_t k);
> +
> +struct curve_list {
> + knots_t curve;
> + double dist;
> + struct curve_list *next;
> + struct curve_list *prev;
> +};
> +
> +typedef struct curve_list curve_list_t;
> +
> +void
> +curve_offset(knots_t self, double offset, double tolerance, void
> (*curve_to_fn)(void *path, knots_t k), void *closure);
> diff --git a/src/cairo-stroke-to-path.c b/src/cairo-stroke-to-path.c
> new file mode 100644
> index 0000000..8c0da82
> --- /dev/null
> +++ b/src/cairo-stroke-to-path.c
> @@ -0,0 +1,1508 @@
> +/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
> +/* cairo - a vector graphics library with display and print output
> + *
> + * Copyright © 2009 Mozilla Foundation
> + *
> + * This library is free software; you can redistribute it and/or
> + * modify it either under the terms of the GNU Lesser General Public
> + * License version 2.1 as published by the Free Software Foundation
> + * (the "LGPL") or, at your option, under the terms of the Mozilla
> + * Public License Version 1.1 (the "MPL"). If you do not alter this
> + * notice, a recipient may use your version of this file under either
> + * the MPL or the LGPL.
> + *
> + * You should have received a copy of the LGPL along with this library
> + * in the file COPYING-LGPL-2.1; if not, write to the Free Software
> + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
> + * You should have received a copy of the MPL along with this library
> + * in the file COPYING-MPL-1.1
> + *
> + * The contents of this file are subject to the Mozilla Public License
> + * Version 1.1 (the "License"); you may not use this file except in
> + * compliance with the License. You may obtain a copy of the License at
> + * http://www.mozilla.org/MPL/
> + *
> + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
> + * OF ANY KIND, either express or implied. See the LGPL or the MPL for
> + * the specific language governing rights and limitations.
> + *
> + * The Original Code is the cairo graphics library.
> + *
> + * The Initial Developer of the Original Code is Jeff Muizelaar
> + *
> + */
> +
> +/* Takes a path as input and produces a stroked path as output.
> + * The resulting path may self intersect so it needs to be filled with
> + * a non-zero winding rule. */
> +
> +#define _BSD_SOURCE /* for hypot() */
> +#include "cairoint.h"
> +#include "cairo-path-fixed-private.h"
> +#include "cairo-spline-offset.h"
> +
> +#define printf(a, ...)
> +
> +typedef struct {
> + cairo_path_fixed_t *path;
> + cairo_matrix_t *ctm;
> +
> + /* we need to keep track of whether we've drawn anything yet
> + so that we can do a move_to to the intial point of a curve
> + before drawing it */
> + cairo_bool_t has_current_point;
> + cairo_int_status_t status;
> +} path_output_t;
> +
> +static void line_to (path_output_t *path, double x, double y)
> +{
> + if (path->ctm)
> + cairo_matrix_transform_point (path->ctm, &x, &y);
> + path->has_current_point = TRUE;
> +
> + if (!path->status)
> + path->status = _cairo_path_fixed_line_to (path->path,
> + _cairo_fixed_from_double(x),
> + _cairo_fixed_from_double(y));
> +}
> +
> +static void curve_to (path_output_t *path, double x0, double y0, double x1,
> double y1, double x2, double y2)
> +{
> + if (path->ctm) {
> + cairo_matrix_transform_point (path->ctm, &x0, &y0);
> + cairo_matrix_transform_point (path->ctm, &x1, &y1);
> + cairo_matrix_transform_point (path->ctm, &x2, &y2);
> + }
> +
> + if (!path->status)
> + path->status = _cairo_path_fixed_curve_to (path->path,
> + _cairo_fixed_from_double (x0), _cairo_fixed_from_double (y0),
> + _cairo_fixed_from_double (x1), _cairo_fixed_from_double (y1),
> + _cairo_fixed_from_double (x2), _cairo_fixed_from_double (y2));
> +
> +}
> +
> +static void close_path (path_output_t *path)
> +{
> + if (!path->status)
> + path->status = _cairo_path_fixed_close_path (path->path);
> + if (!path->status)
> + _cairo_path_fixed_new_sub_path (path->path);
> +}
> +
> +typedef point_t vector_t;
> +
> +static inline double
> +dot (vector_t a, vector_t b)
> +{
> + return a.x * b.x + a.y * b.y;
> +}
> +
> +static cairo_bool_t
> +point_eq (point_t a, point_t b)
> +{
> + return a.x == b.x && a.y == b.y;
> +}
> +
> +static inline vector_t
> +perp (vector_t v)
> +{
> + vector_t p = {-v.y, v.x};
> + return p;
> +}
> +
> +static inline vector_t
> +flip (vector_t a)
> +{
> + vector_t ar;
> + ar.x = -a.x;
> + ar.y = -a.y;
> + return ar;
> +}
> +
> +/* given a normal rotate the vector 90 degrees to the right clockwise
> + * This function has a period of 4. e.g. swap(swap(swap(swap(x) == x */
> +static vector_t
> +swap (vector_t a)
> +{
> + vector_t ar;
> + /* one of these needs to be negative. We choose a.x so that we rotate to
> the right instead of negating */
> + ar.x = a.y;
> + ar.y = -a.x;
> + return ar;
> +}
> +
> +static vector_t
> +unperp (vector_t a)
> +{
> + return swap (a);
> +}
> +
> +/* Compute a spline approximation of the arc
> + centered at xc, yc from the angle a to the angle b
> +
> + The angle between a and b should not be more than a
> + quarter circle (pi/2)
> +
> + The approximation is similar to an approximation given in:
> + "Approximation of a cubic bezier curve by circular arcs and vice versa"
> + by Alekas Riškus. However that approximation becomes unstable when the
> + angle of the arc approaches 0.
> +
> + This approximation is inspired by a discusion with Boris Zbarsky
> + and essentially just computes:
> +
> + h = 4.0/3.0 * tan ((angle_B - angle_A) / 4.0);
> +
> + without converting to polar coordinates.
> +
> + A different way to do this is covered in "Approximation of a cubic bezier
> + curve by circular arcs and vice versa" by Alekas Riškus. However, the
> method
> + presented there doesn't handle arcs with angles close to 0 because it
> + divides by the perp dot product of the two angle vectors.
> + */
> +
> +static void
> +arc_segment (path_output_t *path,
> + double xc,
> + double yc,
> + double radius,
> + vector_t a,
> + vector_t b)
> +{
> + double r_sin_A, r_cos_A;
> + double r_sin_B, r_cos_B;
> + double h;
> + vector_t mid, mid2;
> + double l;
> +
> + r_sin_A = radius * a.y;
> + r_cos_A = radius * a.x;
> + r_sin_B = radius * b.y;
> + r_cos_B = radius * b.x;
> +
> + /* bisect the angle between 'a' and 'b' with 'mid' */
> + mid.x = a.x + b.x;
> + mid.y = a.y + b.y;
> + l = sqrt(mid.x*mid.x + mid.y*mid.y);
> + mid.x /= l;
> + mid.y /= l;
> +
> + /* bisect the angle between 'a' and 'mid' with 'mid2' this is parallel to a
> + * line with angle (B - A)/4 */
> + mid2.x = a.x + mid.x;
> + mid2.y = a.y + mid.y;
> +
> + h = (4./3.)*dot(perp(a), mid2)/dot(a, mid2);
> + //h = (4./3.)*(-a.y*mid.x + a.x*mid.y)/(a.x*mid2.x + a.y*mid2.y);
> +
> + curve_to (path,
> + xc + r_cos_A - h * r_sin_A,
> + yc + r_sin_A + h * r_cos_A,
> + xc + r_cos_B + h * r_sin_B,
> + yc + r_sin_B - h * r_cos_B,
> + xc + r_cos_B,
> + yc + r_sin_B);
> +}
> +
> +
> +static vector_t
> +bisect (vector_t a, vector_t b)
> +{
> + vector_t mid;
> + double len;
> +
> + if (dot (a, b) >= 0) {
> + /* if the angle between a and b is accute, then we can
> + * just add the vectors and normalize */
> + mid.x = a.x + b.x;
> + mid.y = a.y + b.y;
> + } else {
> + /* otherwise, we can flip a, add it
> + * and then use the perpendicular of the result */
> + a = flip (a);
> + mid.x = a.x + b.x;
> + mid.y = a.y + b.y;
> + mid = perp (mid);
> + }
> +
> + /* normalize */
> + /* because we assume that 'a' and 'b' are normalized, we can use
> + * sqrt instead of hypot because the range of mid is limited */
> + len = sqrt (mid.x*mid.x + mid.y*mid.y);
> + mid.x /= len;
> + mid.y /= len;
> + return mid;
> +}
> +
> +static void
> +arc (path_output_t *path, double xc, double yc, double radius, vector_t a,
> vector_t b)
> +{
> + /* find a vector that bisects the angle between a and b */
> + vector_t mid_v = bisect (a, b);
> +
> + /* construct the arc using two curve segments */
> + arc_segment (path, xc, yc, radius, a, mid_v);
> + arc_segment (path, xc, yc, radius, mid_v, b);
> +}
> +
> +static inline void
> +join_round (path_output_t *path, point_t center, vector_t a, vector_t b,
> double radius)
> +{
> + /*
> + int ccw = dot (perp (b), a) >= 0; // XXX: is this always true?
> + yes, otherwise we have an interior angle.
> + assert (ccw);
> + */
> + arc (path, center.x, center.y, radius, a, b);
> +}
> +
> +static void
> +draw_circle (path_output_t *path, point_t center, double radius)
> +{
> + vector_t a = {1, 0};
> + vector_t b = {-1, 0};
> +
> + /* draw a line to the begining of the arc */
> + line_to (path, center.x + radius * a.x, center.y + radius * a.y);
> +
> + arc (path, center.x, center.y, radius, a, b);
> + arc (path, center.x, center.y, radius, b, a);
> +}
> +
> +static point_t
> +c2p (cairo_matrix_t *ctm_inverse, cairo_point_t c)
> +{
> + point_t p;
> + p.x = _cairo_fixed_to_double(c.x);
> + p.y = _cairo_fixed_to_double(c.y);
> + if (ctm_inverse)
> + cairo_matrix_transform_point (ctm_inverse, &p.x, &p.y);
> +
> + return p;
> +}
> +
> +#if 1
> +static vector_t
> +compute_normal (point_t p0, point_t p1)
> +{
> + vector_t n;
> + /* u is parallel vector */
> + double ux = p1.x - p0.x;
> + double uy = p1.y - p0.y;
> +
> + /* we actually want the inverse square root here. then we won't have to
> divide */
> + double ulen = hypot(ux, uy);
> + /* cairo uses hypot which does sqrt(ux*ux + uy*uy) without the accuracy
> problems
> + i.e. hypot is slower, but more accurate */
> + assert (ulen != 0);
> + // v is perpendicular *unit* vector
> + n.x = -uy/ulen;
> + n.y = ux/ulen;
> +
> + return n;
> +}
> +#else
> +#include <emmintrin.h>
> +/* a quick and dirty sse implementation. This is much lower
> + * precision than the version above and not as fast as it
> + * could be. */
> +static vector_t
> +compute_normal (point_t p0, point_t p1)
> +{
> + vector_t n;
> + /* u is parallel vector */
> + float ux = p1.x - p0.x;
> + float uy = p1.y - p0.y;
> +
> +
> + __m128 mux = _mm_load_ss (&ux);
> + __m128 muy = _mm_load_ss (&uy);
> +
> + __m128 mux2 = _mm_mul_ss(mux, mux);
> + __m128 muy2 = _mm_mul_ss(muy, muy);
> +
> + __m128 rlen = _mm_rsqrt_ss(_mm_add_ss(muy2, mux2));
> +#if 1
> + mux = _mm_mul_ss(mux, rlen);
> + muy = _mm_sub_ps(_mm_setzero_ps(), _mm_mul_ss(muy, rlen)); //negate
> + __m128 results = _mm_shuffle_ps (mux, muy, _MM_SHUFFLE(0, 0, 0, 0)); //
> get bottom words
> + results = _mm_shuffle_ps (results, results, _MM_SHUFFLE(0, 0, 0, 2)); // x
> and y
> +#else
> + rlen = _mm_shuffle_ps (rlen, rlen, _MM_SHUFFLE(0, 0, 0, 0)); // get bottom
> words
> + muy = _mm_sub_ps(_mm_setzero_ps(), muy);
> + __m128 results = _mm_shuffle_ps (mux, muy, _MM_SHUFFLE(0, 0, 0, 0)); //
> get bottom words
> + results = _mm_shuffle_ps (results, results, _MM_SHUFFLE(0, 0, 0, 2)); // x
> and y
> + results = _mm_mul_ps(mux, rlen);
> +#endif
> +
> +
> + __m128d result = _mm_cvtps_pd (results);
> + _mm_storeu_pd(&n.x, result);
> +#if 0
> + __m128 muxy = _mm_shuffle_ps (mux, muy, _MM_SHUFFLE(0, 0, 0, 0)); // get
> bottom words
> + /* we actually want the inverse square root here. then we won't have to
> divide */
> + muxy = _mm_mul_ps(muxy, muxy);
> + muxy = _mm_shuffle_ps (mux, muy, _MM_SHUFFLE(0, 0, 0, 0)); // get bottom
> words
> +#endif
> + return n;
> +}
> +#endif
> +
> +
> +
> +/* computes the outgoing normal for curve given by a,b,c,d
> + * returning the original normal if the curve is point */
> +static vector_t
> +curve_normal (vector_t original_normal, point_t a, point_t b, point_t c,
> point_t d)
> +{
> + vector_t n = original_normal;
> + if (point_eq (c, d)) {
> + if (point_eq (b, c)) {
> + if (!point_eq (a, b)) {
> + n = compute_normal (a, b);
> + }
> + } else {
> + n = compute_normal (b, c);
> + }
> + } else {
> + n = compute_normal (c, d);
> + }
> + return n;
> +}
> +static void ensure_finite (knots_t k)
> +{
> +
> + if (!(
> + isfinite(k.a.x) &&
> + isfinite(k.a.y) &&
> + isfinite(k.b.x) &&
> + isfinite(k.b.y) &&
> + isfinite(k.c.x) &&
> + isfinite(k.c.y) &&
> + isfinite(k.d.x) &&
> + isfinite(k.d.y))) {
> + print_knot(k);
> + assert(0);
> + }
> +}
> +
> +
> +static void offset_curve_to(void *closure, knots_t c)
> +{
> + path_output_t *path = closure;
> + ensure_finite(c);
> + //XXX: it would be nice if we didn't have to check this for every point
> + if (!path->has_current_point)
> + line_to(path, c.a.x, c.a.y);
> + curve_to(path, c.b.x, c.b.y, c.c.x, c.c.y, c.d.x, c.d.y);
> +}
> +
> +static void
> +draw_offset_curve (path_output_t *path,
> + point_t a, point_t b, point_t c, point_t d, double offset)
> +{
> + knots_t curve = {a, b, c, d};
> + /* we want greater tolerance when the lines we are stroking are narrower
> + * because any deviations will be more noticeable.
> + * Fortunately, the narrow the lines are the easier it is to approximate
> + * the offset curve. It could be argued that this is a bad choice because
> + * one could draw two large but slightly different stroke widths on top of
> + * each other and the result wouldn't necessarily match. However,
> + * I'm not sure if tha's actually a problem. */
> + double tolerance = offset * 2 / 500.; /* the choice of 500 is pretty
> arbitrary */
> +
> + curve_offset(curve, offset, tolerance, offset_curve_to, path);
> +}
> +
> +/* Finds the intersection of two lines each defined by a point and a normal.
> + From "Example 2: Find the interesection of two lines" of
> + "The Pleasures of "Perp Dot" Products"
> + F. S. Hill, Jr. */
> +static point_t
> +line_intersection (point_t A, vector_t a_perp, point_t B, vector_t b_perp)
> +{
> + point_t intersection;
> + double denom;
> + double t;
> +
> + vector_t a = unperp(a_perp);
> + vector_t c = {B.x - A.x, B.y - A.y};
> + denom = dot(b_perp, a);
> + if (denom == 0.0) {
> + assert(0 && "TROUBLE");
> + }
> +
> + t = dot (b_perp, c)/denom;
> +
> + intersection.x = A.x+t*(a.x);
> + intersection.y = A.y+t*(a.y);
> +
> + return intersection;
> +}
> +
> +static cairo_bool_t
> +is_interior_angle (vector_t a, vector_t b) {
> + /* angles of 180 and 0 degress will evaluate to 0, however
> + * we to treat 180 as an interior angle and 180 as an exterior angle */
> + return dot (perp (a), b) > 0 ||
> + (a.x == b.x && a.y == b.y); /* 0 degrees is interior */
> +}
> +
> +static void
> +join_segment_line (path_output_t *path, cairo_stroke_style_t *style, point_t
> p, vector_t s1_normal, vector_t s2_normal)
> +{
> + double miter_limit = style->miter_limit;
> + cairo_line_join_t join = style->line_join;
> + double offset = style->line_width/2;
> +
> + point_t start = {p.x + s1_normal.x*offset, p.y + s1_normal.y*offset};
> + point_t end = {p.x + s2_normal.x*offset, p.y + s2_normal.y*offset};
> +
> + if (is_interior_angle (s1_normal, s2_normal)) {
> + line_to(path, start.x, start.y);
> + //XXX: while you wouldn't think this point is necessary, it is when we
> the segments we are joining
> + //are shorter than the line width
> + /* qt does a check to avoid adding this additional point when possible
> */
> + line_to(path, p.x, p.y);
> +
> + line_to(path, end.x, end.y);
> + } else {
> + switch (join) {
> + case CAIRO_LINE_JOIN_ROUND:
> + line_to(path, start.x, start.y);
> + join_round(path, p, s1_normal, s2_normal, offset);
> + break;
> + case CAIRO_LINE_JOIN_MITER:
> + {
> + double in_dot_out = -s1_normal.x*s2_normal.x +
> -s1_normal.y*s2_normal.y;
> + // XXX: we are going to have an extra colinear segment
> here */
> + if (2 <= miter_limit*miter_limit * (1 - in_dot_out)) {
> + point_t intersection = line_intersection(start,
> s1_normal, end, s2_normal);
> + line_to(path, intersection.x, intersection.y);
> + break;
> + }
> + }
> + // fall through
> + case CAIRO_LINE_JOIN_BEVEL:
> + line_to(path, start.x, start.y);
> + line_to(path, end.x, end.y);
> + break;
> + }
> + }
> +}
> +
> +
> +static void
> +join_segment_curve (path_output_t *path, cairo_stroke_style_t *style, point_t
> p, vector_t s1_normal, vector_t s2_normal)
> +{
> + cairo_line_join_t join = style->line_join;
> + double offset = style->line_width/2;
> + double miter_limit = style->miter_limit;
> +
> + point_t start = {p.x + s1_normal.x*offset, p.y + s1_normal.y*offset};
> + point_t end = {p.x + s2_normal.x*offset, p.y + s2_normal.y*offset};
> + if (is_interior_angle (s1_normal, s2_normal)) {
> + //XXX: while you wouldn't think this point is necessary, it is when we
> the segments we are joining
> + //are shorter than the line width
> + /* qt does a check to avoid adding this additional point when possible
> */
> + line_to(path, p.x, p.y);
> + line_to(path, end.x, end.y);
> + } else {
> + switch (join) {
> + case CAIRO_LINE_JOIN_ROUND:
> + join_round(path, p, s1_normal, s2_normal, offset);
> + break;
> + case CAIRO_LINE_JOIN_MITER:
> + {
> + double in_dot_out = -s1_normal.x*s2_normal.x +
> -s1_normal.y*s2_normal.y;
> + // XXX: we are going to have an extra colinear segment here */
> + if (2 <= miter_limit*miter_limit * (1 - in_dot_out)) {
> + point_t intersection = line_intersection(start, s1_normal,
> end, s2_normal);
> + line_to(path, intersection.x, intersection.y);
> + break;
> + }
> + }
> + // fall through
> + case CAIRO_LINE_JOIN_BEVEL:
> + line_to(path, end.x, end.y);
> + break;
> + }
> + }
> +}
> +
> +/* we have some different options as to what the semantics of cap_line should
> be:
> + - here's how skia's works:
> + - it uses a virtual function call instead of a switch statement.
> + - it assumes that the caller has added the start point of the cap
> + - here's an interesting bit: the square capper has different behaviour
> + depending on whether the last segment is a curve or not.
> + If it is a line it will adjust the last point of the path
> + and only set the outside point of the cap. This avoids the
> + the extra points when capping a square line.
> + - qt and mesa's openvg state tracker do this cute thing
> + where they treat caps as joins. i.e a butt cap maps
> + to a miter join, a round cap to a round join and
> + a square cap is special cased.
> + 3 line segments are always emitted for a square cap
> + it seems the code assumes that the first point is implied?
> +
> + I don't think the similarities of caps and joins outweigh the differences.
> Further
> + I think keeping them separate makes it easier to understand.
> +*/
> +static void
> +cap_line (path_output_t *path, cairo_stroke_style_t *style, point_t end,
> vector_t normal)
> +{
> + cairo_line_cap_t cap = style->line_cap;
> + double offset = style->line_width/2;
> +
> + /* This function will add additional unnecessary lines when it is called
> after a curve
> + * segment. I'm not sure it's worth trying to eliminate them */
> + switch (cap) {
> + case CAIRO_LINE_CAP_ROUND:
> + {
> + line_to (path, end.x + offset*normal.x, end.y +
> offset*normal.y);
> + arc(path, end.x, end.y, offset, normal, flip(normal));
> + break;
> + }
> + case CAIRO_LINE_CAP_SQUARE:
> + {
> + // parallel vector
> + double vx = normal.y;
> + double vy = -normal.x;
> + // move the end point down the line by offset
> + end.x += vx*offset;
> + end.y += vy*offset;
> +
> + // offset the end point of last_line to draw the cap at the end
> + line_to(path, end.x + offset*normal.x, end.y +
> offset*normal.y);
> + line_to(path, end.x - offset*normal.x, end.y -
> offset*normal.y);
> + break;
> + }
> + case CAIRO_LINE_CAP_BUTT:
> + {
> + line_to (path, end.x + offset*normal.x, end.y +
> offset*normal.y);
> + // offset the end point of last_line to draw the cap at the end
> + line_to(path, end.x - offset*normal.x, end.y -
> offset*normal.y);
> + break;
> + }
> + }
> +}
> +
> +#define cairo_path_head(path__) (&(path__)->buf.base)
> +#define cairo_path_tail(path__) cairo_path_buf_prev (cairo_path_head (path__))
> +
> +#define cairo_path_buf_next(pos__) \
> + cairo_list_entry ((pos__)->link.next, cairo_path_buf_t, link)
> +#define cairo_path_buf_prev(pos__) \
> + cairo_list_entry ((pos__)->link.prev, cairo_path_buf_t, link)
> +
> +// index is the first segment we need to deal with
> +typedef struct {
> + const cairo_path_buf_t *buf;
> + cairo_point_t *points;
> + unsigned int op_index;
> + const cairo_path_buf_t *first;
> +} path_ittr;
> +
> +static const uint8_t num_args[] = {
> + 1, /* cairo_path_move_to */
> + 1, /* cairo_path_op_line_to */
> + 3, /* cairo_path_op_curve_to */
> + 0, /* cairo_path_op_close_path */
> + };
> +
> +static inline path_ittr
> +ittr_next (path_ittr index)
> +{
> + index.points += num_args[(int)index.buf->op[index.op_index]];
> + index.op_index++;
> + if (index.op_index == index.buf->num_ops) {
> + index.buf = cairo_path_buf_next (index.buf);
> +#ifdef ITTR_DEBUG
> + if (index.buf == index.first) {
> + assert(0);
> + index.buf = NULL;
> + index.points = NULL;
> + index.op_index = 0xbaadf00d;
> + }
> +#endif
> + index.op_index = 0;
> + index.points = index.buf->points;
> + }
> + return index;
> +}
> +
> +static inline path_ittr
> +ittr_prev (path_ittr index)
> +{
> + if (index.op_index == 0) {
> + index.buf = cairo_path_buf_prev (index.buf);
> + index.op_index = index.buf->num_ops-1;
> + index.points = index.buf->points + (index.buf->num_points);
> + } else {
> + index.op_index--;
> + }
> + index.points -= num_args[(int)index.buf->op[index.op_index]];
> + return index;
> +}
> +
> +static inline cairo_path_op_t
> +ittr_op (path_ittr i)
> +{
> + return i.buf->op[i.op_index];
> +}
> +
> +static cairo_bool_t
> +ittr_done(path_ittr i)
> +{
> + return i.buf == NULL;
> +}
> +
> +static cairo_bool_t
> +ittr_last (path_ittr i)
> +{
> + return i.op_index+1 == i.buf->num_ops && cairo_path_buf_next(i.buf) ==
> i.first;
> +}
> +
> +static cairo_bool_t
> +ittr_eq (path_ittr a, path_ittr b)
> +{
> + return a.buf == b.buf && a.op_index == b.op_index;
> +}
> +
> +
> +static void
> +draw_degenerate_path (path_output_t *path_out, cairo_stroke_style_t *style,
> point_t point)
> +{
> + if (style->line_cap == CAIRO_LINE_CAP_ROUND) {
> + draw_circle(path_out, point, style->line_width/2);
> + }
> +}
> +
> +/* it might be interesting to see if we can just skip degenerate segments... */
> +
> +static cairo_status_t
> +_cairo_subpath_stroke_to_path (path_ittr *ittr,
> + cairo_stroke_style_t *stroke_style,
> + path_output_t *path_out,
> + cairo_matrix_t *ctm_inverse)
> +{
> + double offset = stroke_style->line_width/2;
> + cairo_status_t status = CAIRO_STATUS_SUCCESS;
> + path_ittr i = *ittr;
> + cairo_matrix_t *ctm_i = ctm_inverse;
> +
> + point_t begin = c2p (ctm_i, i.points[0]);
> + point_t end_point = begin;
> +
> + cairo_path_op_t op;
> + cairo_point_t *points;
> + vector_t end_normal;
> + vector_t initial_normal;
> + point_t end;
> +
> + int op_count = 0;
> + cairo_bool_t closed_path = FALSE;
> + point_t last_point;
> + vector_t closed_normal;
> +
> + assert(ittr_op(i) == CAIRO_PATH_OP_MOVE_TO);
> +
> + /* handle beginging of the line: we want to get an intial normal to work
> with
> + * before we start drawing */
> + while (1) {
> + i = ittr_next (i);
> + op = ittr_op (i);
> + points = i.points;
> +
> + if (op == CAIRO_PATH_OP_MOVE_TO) {
> + *ittr = i;
> + draw_degenerate_path(path_out, stroke_style, begin);
> + return CAIRO_STATUS_SUCCESS;
> + }
> +
> + if (op == CAIRO_PATH_OP_CLOSE_PATH) {
> + *ittr = ittr_next (i);
> + draw_degenerate_path(path_out, stroke_style, begin);
> + return CAIRO_STATUS_SUCCESS;
> + }
> +
> + if (op == CAIRO_PATH_OP_LINE_TO) {
> + point_t p = c2p(ctm_i, points[0]);
> + //XXX: it would be better if we compared points in fixed point...
> + if (!point_eq(begin, p)) {
> + initial_normal = compute_normal(begin, p);
> + break;
> + }
> + } else {
> + point_t p0 = c2p(ctm_i, points[0]);
> + point_t p1 = c2p(ctm_i, points[1]);
> + point_t p2 = c2p(ctm_i, points[2]);
> + assert(ittr_op (i) == CAIRO_PATH_OP_CURVE_TO);
> + //XXX: maybe use the helper function?
> + if (!point_eq (begin, p0)) {
> + initial_normal = compute_normal (begin, p0);
> + break;
> + } else {
> + if (!point_eq (begin, p1)) {
> + initial_normal = compute_normal (begin, p1);
> + break;
> + } else {
> + if (!point_eq (begin, p2)) {
> + initial_normal = compute_normal (begin, p2);
> + break;
> + }
> + }
> + }
> + }
> +
> + if (ittr_last (i)) {
> + /* if we had a normal for the last op we would have broken out
> already */
> + printf("degen\n");
> + *ittr = i;
> + draw_degenerate_path (path_out, stroke_style, begin);
> + return CAIRO_STATUS_SUCCESS;
> + }
> + }
> +
> + end_normal = initial_normal;
> +
> + /* end_normal needs to be the normal between i.points[] and the preceeding
> point */
> + while (!ittr_last (i)) {
> + op_count++;
> +
> + i = ittr_next (i);
> + cairo_path_op_t next_op = ittr_op (i);
> + cairo_point_t *next_points = i.points;
> +
> + switch (next_op) {
> + case CAIRO_PATH_OP_MOVE_TO:
> + *ittr = i;
> + i = ittr_prev (i);
> + op_count--;
> + // we are done with the current subpath
> + // cap it and return to the begining
> + //assert(0);
> + goto done;
> + case CAIRO_PATH_OP_LINE_TO:
> + case CAIRO_PATH_OP_CURVE_TO:
> + // get first point of next_op
> + end = c2p (ctm_i, next_points[0]);
> + break;
> + case CAIRO_PATH_OP_CLOSE_PATH:
> + // close the path
> + // XXX: relies on the fact that CLOSE_PATH is never the last
> path_op (it is always followed by an OP_MOVE)
> + closed_path = TRUE;
> + // the first point of the first op
> + end = c2p (ctm_i, ittr->points[0]);
> + break;
> + default:
> + ASSERT_NOT_REACHED;
> + }
> + if (unlikely (status))
> + return status;
> +
> + switch (op) {
> + case CAIRO_PATH_OP_CURVE_TO:
> + {
> + point_t p0 = c2p (ctm_i, points[0]);
> + point_t p1 = c2p (ctm_i, points[1]);
> + point_t p2 = c2p (ctm_i, points[2]);
> +
> + vector_t n2 = end_normal;
> + if (!point_eq (p0, p1))
> + n2 = compute_normal (p0, p1);
> + if (!point_eq (p1, p2))
> + n2 = compute_normal (p1, p2);
> + end_normal = n2;
> +
> + draw_offset_curve (path_out, begin,
> + p0,
> + p1,
> + p2,
> + offset);
> +
> + if (!point_eq (p2, end)) {
> + vector_t n3 = compute_normal (p2, end);
> + join_segment_curve (path_out, stroke_style, p2, n2,
> n3);
> + end_normal = n3;
> + }
> +
> + begin = p2;
> + end_point = begin;
> + }
> + break;
> + case CAIRO_PATH_OP_LINE_TO:
> + {
> + point_t mid = c2p (ctm_i, points[0]);
> + if (!point_eq (mid, end)) {
> + vector_t n1 = end_normal;
> + vector_t n2 = compute_normal (mid, end);
> + join_segment_line (path_out, stroke_style, mid, n1,
> n2);
> + end_normal = n2;
> + begin = mid;
> + end_point = mid;
> + }
> + }
> + break;
> + default:
> + ASSERT_NOT_REACHED;
> + }
> + if (closed_path)
> + break;
> + op = next_op;
> + points = next_points;
> + };
> +
> + if (!closed_path)
> + *ittr = i;
> +done:
> + // op should be set the last op in the path
> + if (closed_path) {
> + point_t first_point = c2p (ctm_i, ittr->points[0]);
> +
> + assert(ittr_op (*ittr) == CAIRO_PATH_OP_MOVE_TO);
> + closed_normal = end_normal;
> + last_point = end_point;
> + join_segment_line (path_out, stroke_style, first_point, end_normal,
> initial_normal);
> +
> + // XXX: is this right?
> + begin = first_point;
> + *ittr = ittr_next (i);
> + path_out->has_current_point = FALSE;
> + close_path (path_out);
> + } else {
> + if (op == CAIRO_PATH_OP_CURVE_TO) {
> + point_t p0 = c2p (ctm_i, points[0]);
> + point_t p1 = c2p (ctm_i, points[1]);
> + point_t p2 = c2p (ctm_i, points[2]);
> +
> + /* draw capped curve segment */
> + draw_offset_curve (path_out, end_point, p0, p1, p2, offset);
> + cap_line (path_out, stroke_style, p2, curve_normal (end_normal,
> end_point, p0, p1, p2));
> + draw_offset_curve (path_out, p2, p1, p0, end_point, offset);
> +
> + begin = p0;
> + } else if (op == CAIRO_PATH_OP_LINE_TO) {
> + begin = c2p (ctm_i, points[0]);
> + cap_line (path_out, stroke_style, begin, end_normal);
> + } else {
> + assert(0);
> + }
> + }
> +
> + end_normal = flip (end_normal);
> +
> + // pre-conditions
> + i = ittr_prev(i);
> + op = ittr_op(i);
> + points = i.points;
> +
> + /* traverse backwards to the begining drawing
> + * the other side of the stroked path */
> + while (op_count) {
> + i = ittr_prev (i);
> + cairo_path_op_t next_op = ittr_op (i);
> + cairo_point_t *next_points = i.points;
> +
> + switch (next_op) {
> + case CAIRO_PATH_OP_MOVE_TO:
> + end = c2p (ctm_i, next_points[0]);
> + break;
> + case CAIRO_PATH_OP_LINE_TO:
> + end = c2p (ctm_i, next_points[0]);
> + break;
> + case CAIRO_PATH_OP_CURVE_TO:
> + // get first point of next_op
> + end = c2p (ctm_i, next_points[2]);
> + break;
> + case CAIRO_PATH_OP_CLOSE_PATH:
> + // close the path
> + assert(0);
> + break;
> + default:
> + ASSERT_NOT_REACHED;
> + }
> + if (unlikely (status))
> + return status;
> +
> + switch (op) {
> + case CAIRO_PATH_OP_CURVE_TO:
> + {
> + point_t p2 = c2p (ctm_i, points[2]);
> + point_t p1 = c2p (ctm_i, points[1]);
> + point_t p0 = c2p (ctm_i, points[0]);
> + if (!point_eq (p2, p1)) {
> + vector_t n0 = compute_normal (p2, p1);
> + // XXX whether we use join_segment_line or
> join_segment_curve here depends
> + // on whether we are coming from a line or from a
> curve. Does it matter?
> + // this used to be join_segment_curve but it was wrong
> for the following:
> + // cairo_move_to(cr, 550, 400);
> + // cairo_curve_to(cr, 531.687500,
> 469.878906, 415.203125, 506.437500, 247.179688, 524.625000);
> + // cairo_line_to(cr, 257.945312, 624.046875);
> + join_segment_line (path_out, stroke_style, p2,
> end_normal, n0);
> + end_normal = n0;
> + }
> + end_normal = curve_normal (end_normal, p2, p1, p0, end);
> + draw_offset_curve (path_out,
> + p2,
> + p1,
> + p0,
> + end,
> + offset);
> + //XXX: this feels suspect...
> + begin = p0;
> + end_point = end;
> + }
> + break;
> + case CAIRO_PATH_OP_LINE_TO:
> + {
> + point_t mid = c2p (ctm_i, points[0]);
> + vector_t n1 = end_normal;
> + if (!point_eq (mid, end)) {
> + vector_t n2 = compute_normal (mid, end);
> + join_segment_line (path_out, stroke_style, mid, n1,
> n2);
> + end_normal = n2;
> + begin = mid;
> + end_point = end;
> + }
> + }
> + break;
> + default:
> + ASSERT_NOT_REACHED;
> + }
> +
> + points = next_points;
> + op = next_op;
> + op_count--;
> +
> + }
> +
> + if (closed_path) {
> + vector_t n2 = end_normal;
> + printf("finish closed\n");
> + assert(ittr_op (i) == CAIRO_PATH_OP_MOVE_TO);
> + if (!point_eq (end_point, last_point)) {
> + n2 = compute_normal (end_point, last_point);
> + join_segment_line (path_out, stroke_style, c2p (ctm_i,
> i.points[0]), end_normal, n2);
> + }
> +
> + join_segment_line (path_out, stroke_style, last_point, n2, flip
> (closed_normal));
> + } else {
> + cap_line (path_out, stroke_style, end_point, end_normal);
> + }
> + close_path (path_out);
> +
> + return CAIRO_STATUS_SUCCESS;
> +}
> +
> +typedef struct {
> + point_t point;
> + vector_t normal;
> +} dash_point_t;
> +
> +static double
> +distance (point_t p0, point_t p1)
> +{
> + double ux = p1.x - p0.x;
> + double uy = p1.y - p0.y;
> + return hypot(ux, uy);
> +}
> +
> +/* i points to the last op we've just finished */
> +static dash_point_t
> +skip_subpath (dash_point_t start_point, path_output_t *path_out, path_ittr *i,
> path_ittr subpath_start, path_ittr *subpath_end, cairo_matrix_t *ctm_i,
> cairo_bool_t *closed, double length)
> +{
> + //XXX: review the naming of points to make sure it makes sense and is
> consistent
> + path_ittr index = *i;
> + path_ittr next_index;
> + dash_point_t end_point = start_point;
> + point_t next_point;
> + cairo_bool_t done = FALSE;
> +
> + assert(!ittr_last(index));
> +
> + next_index = ittr_next(index);
> +
> + printf("skip_subpath: %d\n", index.op_index);
> +
> + if (ittr_op(next_index) == CAIRO_PATH_OP_CLOSE_PATH) {
> + *closed = TRUE;
> + next_index = subpath_start;
> + }
> +
> + assert(ittr_op(next_index) == CAIRO_PATH_OP_LINE_TO || ittr_eq(next_index,
> subpath_start));
> + next_point = c2p(ctm_i, next_index.points[0]);
> +
> + while (length > 0) { //XXX: is this condition even needed?
> + double d = distance(end_point.point, next_point);
> + assert(ittr_op(next_index) == CAIRO_PATH_OP_LINE_TO ||
> ittr_op(next_index) == CAIRO_PATH_OP_MOVE_TO);
> + printf("d(%d): %f of %f\n", index.op_index, d, length);
> + if (d >= length) {
> + /* move the end_point a distance 'length' along the line with the
> normal end_point.normal */
> + end_point.point.x += -end_point.normal.y*-length;
> + end_point.point.y += end_point.normal.x*-length;
> + length = 0;
> + printf("skippath break\n");
> + break;
> + } else {
> + end_point.point = next_point;
> +
> + if (ittr_eq(next_index, subpath_start)) {
> + /* we've passed the begining; we are done */
> + done = TRUE;
> + break;
> + }
> +
> + if (ittr_last(next_index)) {
> + /* we're at the end of the path; we are done */
> + *subpath_end = next_index;
> + done = TRUE;
> + break;
> + }
> +
> + index = next_index;
> + next_index = ittr_next(next_index);
> +
> + if (ittr_op(next_index) == CAIRO_PATH_OP_CLOSE_PATH) {
> + /* we have a closed path so wrap around toward the begining
> (subpath_start) */
> + *closed = TRUE;
> + *subpath_end = ittr_next(next_index);
> + next_index = subpath_start;
> + } else if (ittr_op(next_index) == CAIRO_PATH_OP_MOVE_TO) {
> + *subpath_end = next_index;
> + done = TRUE;
> + break;
> + }
> +
> + next_point = c2p(ctm_i, next_index.points[0]);
> + if (!point_eq(end_point.point, next_point)) {
> + /* XXX: we might be able to avoid computing the normal for
> every point we vist
> + * and instead only compute it for the last segment */
> + end_point.normal = compute_normal(end_point.point, next_point);
> + }
> +
> + printf("next %f %f\n", d, length);
> + length -= d;
> + }
> + }
> +
> + *i = index;
> +
> + if (done)
> + i->buf = NULL;
> +
> + return end_point;
> +}
> +
> +static dash_point_t
> +dash_subpath (dash_point_t start_point, path_output_t *path_out, path_ittr
> *index, path_ittr subpath_start, path_ittr *subpath_done, cairo_matrix_t
> *ctm_i, cairo_stroke_style_t *style, double length, int begin_on, cairo_bool_t
> *closed, double start_length)
> +{
> + dash_point_t end_point;
> + point_t first = start_point.point;
> + path_ittr i = *index;
> + path_ittr subpath_end = {};
> + int closed_path = 0;
> + int done = 0;
> + vector_t n1 = start_point.normal;
> + path_ittr start_index = i;
> + path_ittr next_i;
> + point_t p1;
> + // investigate more normal reuse.
> + // ideally we would only compute the normal for each segment once
> + // deal with short paths (count < 3)
> + assert(!ittr_last(i));
> + printf("dash_subpath(%f): %d: %f %f\n", length, i.op_index, first.x,
> first.y);
> +
> + next_i = ittr_next(i);
> +
> + if (ittr_op(next_i) == CAIRO_PATH_OP_CLOSE_PATH) {
> + subpath_end = i;
> + *subpath_done = ittr_next(next_i);
> + next_i = subpath_start;
> + *closed = TRUE;
> + }
> +
> + assert(ittr_op(next_i) == CAIRO_PATH_OP_LINE_TO || ittr_eq(next_i,
> subpath_start));
> + //printf("off: %f %f, %f %f\n", end_point.point.x, end_point.point.y,
> path[index].x, path[index].y);
> + p1 = c2p(ctm_i, next_i.points[0]);
> + do {
> + double d;
> + vector_t n2;
> + point_t p2;
> + assert(ittr_op(next_i) == CAIRO_PATH_OP_LINE_TO || ittr_eq(next_i,
> subpath_start));
> + d = distance (first, p1);
> + if (d >= length) {
> + end_point.point.x = first.x + length*n1.y;
> + end_point.point.y = first.y + length*-n1.x;
> + end_point.normal = n1;
> + break;
> + }
> +
> + if (ittr_last (next_i)) {
> + /* we're at the end so we must be done */
> + done = 1;
> + *subpath_done = next_i;
> + end_point.point = c2p(ctm_i, next_i.points[0]);
> + end_point.normal = n1;
> + break;
> + }
> +
> + /* We don't have enough length in the current segment so get the next
> one
> + * This means advancing i and next_i */
> +
> + if (ittr_eq(next_i, subpath_start)) {
> + /* we're already at the beginning of the path so we don't have
> anything left to dash */
> + printf("done\n");
> + //XXX done the path
> + done = 1;
> + if (!begin_on) {
> + /* we didn't skip the initial segment; so we're all done */
> + length = 0;
> + end_point.point = c2p(ctm_i, next_i.points[0]);
> + end_point.normal = n1;
> + break;
> + } else {
> + /* the initial segment started on, so join with it and draw it
> */
> + length = start_length;
> + i = next_i;
> + next_i = ittr_next(next_i);
> + }
> + } else {
> + i = next_i;
> + next_i = ittr_next(next_i);
> +
> + if (ittr_op(next_i) == CAIRO_PATH_OP_CLOSE_PATH) {
> + subpath_end = i;
> + *subpath_done = ittr_next(next_i);
> + next_i = subpath_start;
> + *closed = TRUE;
> + } else if (ittr_op(next_i) == CAIRO_PATH_OP_MOVE_TO) {
> + done = 1;
> + end_point.point = c2p(ctm_i, i.points[0]);
> + end_point.normal = n1;
> + *subpath_done = next_i;
> + //XXX: it would be good if we could avoid doing this
> ittr_prev()
> + i = ittr_prev(i);
> + printf("dash: segment end break\n");
> + break;
> + }
> + length -= d;
> + }
> +
> + p2 = c2p(ctm_i, next_i.points[0]);
> + if (!point_eq(p1, p2)) {
> + n2 = compute_normal(p1, p2);
> + end_point.normal = n2;
> + end_point.point = p2;
> + }
> +
> + if (ittr_eq(next_i, start_index)) {
> + // we've reached the place where we started so we need to loop the
> path instead of
> + // capping it
> + done = 1;
> + closed_path = 1;
> + /*
> + gcc complains that end_point can be used uninitialzed in this
> function because we don't set
> + it here when we break out of the loop. I don't think we can get to
> here without setting end_point
> + and here's why:
> +
> + p2 == start_index point
> + p1 must have the same value as p2
> +
> + the only time that next_i can equal start_index is when
> start_index == subpath_start
> + this means that the whole path needs to be here. However, unless
> the path is degenerate
> + end_point will be set. But no degenerate paths will pass into here
> because they will be
> + found else where.
> +
> + Can we make this more explict?
> + */
> + printf("closed path\n");
> + // XXX: do we need to set end_point here? normally we would get an
> end_point from the code above.
> + // but if we have a degenerate path we won't
> + break;
> + }
> +
> + // XXX: having to check this twice sort of sucks
> + if (!point_eq(p1, p2)) {
> + join_segment_line(path_out, style, p1, n1, n2);
> + n1 = n2;
> + first = p1;
> + p1 = p2;
> + }
> + } while (1);
> +
> + /* at this point end_point must be initialized and 'i' must point to the
> point before the end_point */
> +
> + *index = i;
> +
> + point_t closed_p1;
> + point_t closed_p2;
> + vector_t closed_n1;
> + vector_t closed_n2;
> + vector_t closed_n3;
> + if (closed_path) {
> + // join the line back with itself
> + closed_p1 = c2p (ctm_i, i.points[0]);
> + closed_p2 = end_point.point;
> + closed_n1 = n1;
> + closed_n2 = compute_normal (closed_p1, closed_p2);
> + closed_n3 = compute_normal (closed_p2, c2p(ctm_i, ittr_next
> (next_i).points[0]));
> + join_segment_line (path_out, style, closed_p1, closed_n1,
> closed_n2);
> + join_segment_line (path_out, style, closed_p2, closed_n2,
> closed_n3);
> + close_path (path_out);
> + } else {
> + // draw cap
> + cap_line (path_out, style, end_point.point, end_point.normal);
> + }
> +
> + start_point.normal = flip (start_point.normal);
> +
> + /* draw the other side of the path, returning to the begining */
> + n1 = flip (end_point.normal);
> + p1 = c2p (ctm_i, i.points[0]);
> + path_ittr prev_i = i;
> + while (!ittr_eq (prev_i, start_index)) {
> + i = prev_i;
> + if (ittr_eq (prev_i, subpath_start)) {
> + prev_i = subpath_end;
> + } else {
> + prev_i = ittr_prev (prev_i);
> + }
> + point_t p2 = c2p (ctm_i, prev_i.points[0]);
> + if (!point_eq (p1, p2)) {
> + vector_t n2 = compute_normal (p1, p2);
> + join_segment_line (path_out, style, p1, n1, n2);
> +
> + n1 = n2;
> + p1 = p2;
> + }
> + }
> +
> + /* finish up */
> +
> + if (closed_path) {
> + join_segment_line (path_out, style, closed_p2, flip (closed_n3), flip
> (closed_n2));
> + join_segment_line (path_out, style, closed_p1, flip (closed_n2), flip
> (closed_n1));
> + close_path (path_out);
> + } else {
> + /* draw cap */
> + cap_line(path_out, style, start_point.point, start_point.normal);
> + close_path (path_out);
> + }
> +
> + if (done)
> + index->buf = NULL;
> +
> + return end_point;
> +
> +}
> +
> +static cairo_status_t
> +_cairo_subpath_dash_to_path (path_ittr *ittr,
> + cairo_stroke_style_t *style,
> + path_output_t *path_out,
> + cairo_matrix_t *ctm_i)
> +{
> +
> + cairo_bool_t on = TRUE, begin_on, closed = FALSE;
> +
> + double length, start_length;
> +
> + double *dash = style->dash;
> + double dash_init = style->dash_offset;
> + int dash_len = style->num_dashes;
> + int dash_state = 0;
> + path_ittr index = *ittr;
> + path_ittr subpath_end = {};
> +
> + dash_point_t start_point;
> + dash_point_t end_point;
> + path_ittr subpath_start = index;
> +
> + assert(ittr_op(index) == CAIRO_PATH_OP_MOVE_TO);
> +
> + ///XXX: this code is different from cairo, figure out which is better
> + /* intiailize dash state */
> + length = dash[dash_state++ % dash_len];
> +
> + /* decrease dash_init until we are in the correct dash_state */
> + /* the intervals are closed */
> + /* we make sure that we don't skip over 0 length segments */
> + while (length > 0 && dash_init - length >= 0) {
> + dash_init -= length;
> + on = !on;
> + length = dash[dash_state++ % dash_len];
> + }
> +
> + begin_on = on;
> + length -= dash_init;
> + printf("subpath starts %s with length of %f\n", on ? "on" : "off", length);
> +
> + start_length = length;
> +
> + start_point.point = c2p(ctm_i, index.points[0]);
> + //XXX: to share this with the non dashed code we need to deal with dash
> on/off
> + while (1) {
> + if (ittr_op(ittr_next(index)) == CAIRO_PATH_OP_LINE_TO) {
> + point_t p = c2p(ctm_i, ittr_next(index).points[0]);
> + if (!point_eq(start_point.point, p)) {
> + /* we have a normal so we can start the regular stroking
> process */
> + start_point.normal = compute_normal(start_point.point,
> c2p(ctm_i, ittr_next(index).points[0]));
> + break;
> + }
> + }
> + index = ittr_next(index);
> +
> + if (ittr_op(index) == CAIRO_PATH_OP_MOVE_TO) {
> + *ittr = index;
> + if (on)
> + draw_degenerate_path (path_out, style, start_point.point);
> + return CAIRO_STATUS_SUCCESS;
> + }
> +
> + if (ittr_op(index) == CAIRO_PATH_OP_CLOSE_PATH) {
> + *ittr = ittr_next(index);
> + if (on)
> + draw_degenerate_path (path_out, style, start_point.point);
> + return CAIRO_STATUS_SUCCESS;
> + }
> +
> + if (ittr_last(index)) {
> + *ittr = index;
> + if (on)
> + draw_degenerate_path (path_out, style, start_point.point);
> + return CAIRO_STATUS_SUCCESS;
> + }
> + }
> +
> + end_point = start_point;
> +
> + /* the first segment is special because we might need to join with it.
> However, we won't know
> + * what to do until we reach the end of the subpath
> + * Different renderers behave differently here:
> + * No Join: skia, qt, mesa openvg, coregraphics
> + * Join: opera, cairo, ghostscript, adobe */
> + if (begin_on) {
> + on = !on;
> + /* if the first dash segment is larger than the entire line we'll skip
> the whole thing */
> + end_point = skip_subpath (end_point, path_out, &index, subpath_start,
> &subpath_end, ctm_i, &closed, length);
> + length = dash[dash_state++ % dash_len];
> + printf("done skip: %d\n", index.op_index);
> + if (ittr_done(index)) {
> + printf("reset\n");
> + // flip to back on so that we don't skip everything again
> + on = !on;
> + index = *ittr;
> + length = start_length;
> + end_point = start_point;
> + }
> + }
> +
> + do {
> + printf("index: %d\n", index.op_index);
> + if (on) {
> + end_point = dash_subpath (end_point, path_out, &index,
> subpath_start, &subpath_end, ctm_i, style, length, begin_on, &closed,
> start_length);
> + } else {
> + end_point = skip_subpath (end_point, path_out, &index,
> subpath_start, &subpath_end, ctm_i, &closed, length);
> + }
> + on = !on;
> + length = dash[dash_state++ % dash_len];
> +
> + // cairo does an implicit move_to after a close_path so we need to
> start a new sub path
> + _cairo_path_fixed_new_sub_path (path_out->path);
> + } while (!ittr_done(index));
> +
> + *ittr = index;
> + // draw the initial segment if we haven't yet.
> + if ((!closed && begin_on) || (closed && on)) {
> + printf("draw initial %f\n", start_length);
> + index = subpath_start;
> + end_point = start_point;
> + end_point = dash_subpath (end_point, path_out, &index, subpath_start,
> &subpath_start, ctm_i, style, start_length, begin_on, &closed, start_length);
> + }
> + *ittr = subpath_end;
> + return CAIRO_STATUS_SUCCESS;
> +}
> +
> +static cairo_status_t
> +_cairo_path_dash_to_path (const cairo_path_fixed_t *path,
> + cairo_stroke_style_t *stroke_style,
> + cairo_path_fixed_t *path_out,
> + cairo_matrix_t *ctm,
> + cairo_matrix_t *ctm_inverse)
> +{
> + path_ittr i;
> + path_output_t output_path;
> +
> + output_path.status = CAIRO_STATUS_SUCCESS;
> + output_path.ctm = ctm;
> + output_path.path = path_out;
> +
> + i.buf = i.first = cairo_path_head(path);
> + i.op_index = 0;
> + i.points = i.buf->points;
> +
> + while (!ittr_last(i)) {
> + _cairo_subpath_dash_to_path(&i, stroke_style, &output_path,
> ctm_inverse);
> + }
> +
> + return output_path.status;
> +}
> +
> +cairo_status_t
> +_cairo_path_stroke_to_path (const cairo_path_fixed_t *path,
> + cairo_stroke_style_t *stroke_style,
> + cairo_path_fixed_t *path_out,
> + cairo_matrix_t *ctm,
> + cairo_matrix_t *ctm_inverse,
> + double tolerance)
> +{
> + path_ittr i;
> + path_output_t output_path;
> +
> + cairo_status_t status = CAIRO_STATUS_SUCCESS;
> +
> + /* if we have an empty path, we're alredy done */
> + if (cairo_path_head(path)->num_ops == 0)
> + return CAIRO_STATUS_SUCCESS;
> +
> + if (stroke_style->num_dashes > 0) {
> + if (path->has_curve_to) {
> + /* Dashing curved paths directly is tricky because I know of no
> easy way
> + to split a bezier curve at a particular length. So, for now,
> flatten the
> + path before dashing it */
> + cairo_path_fixed_t flat_path;
> + status = _cairo_path_fixed_init_flat_copy (&flat_path,
> + path,
> + tolerance);
> +
> + if (unlikely(status)) {
> + _cairo_path_fixed_fini (&flat_path);
> + return status;
> + }
> +
> + status = _cairo_path_dash_to_path (&flat_path, stroke_style,
> path_out, ctm, ctm_inverse);
> + _cairo_path_fixed_fini (&flat_path);
> + return status;
> + } else {
> + return _cairo_path_dash_to_path (path, stroke_style, path_out,
> ctm, ctm_inverse);
> + }
> + }
> +
> + output_path.status = CAIRO_STATUS_SUCCESS;
> + output_path.ctm = ctm;
> + output_path.path = path_out;
> +
> + i.buf = i.first = cairo_path_head (path);
> + i.op_index = 0;
> + i.points = i.buf->points;
> +
> + while (!ittr_last (i)) {
> + output_path.has_current_point = FALSE;
> + _cairo_subpath_stroke_to_path (&i, stroke_style, &output_path,
> ctm_inverse);
> + }
> +
> + return output_path.status;
> +}
> diff --git a/src/cairo.c b/src/cairo.c
> index 3cb9b36..df2aaeb 100644
> --- a/src/cairo.c
> +++ b/src/cairo.c
> @@ -3985,6 +3985,15 @@ cairo_append_path (cairo_t *cr,
> _cairo_set_error (cr, status);
> }
>
> +cairo_path_t *
> +cairo_stroke_to_path (cairo_t *cr)
> +{
> + if (unlikely (cr->status))
> + return _cairo_path_create_in_error (cr->status);
> +
> + return _cairo_stroked_path_create (cr->path, cr->gstate);
> +}
> +
> /**
> * cairo_status:
> * @cr: a cairo context
> diff --git a/src/cairo.h b/src/cairo.h
> index 453874d..f5e9023 100644
> --- a/src/cairo.h
> +++ b/src/cairo.h
> @@ -1924,6 +1924,9 @@ cairo_append_path (cairo_t *cr,
> cairo_public void
> cairo_path_destroy (cairo_path_t *path);
>
> +cairo_public cairo_path_t *
> +cairo_stroke_to_path (cairo_t *cr);
> +
> /* Error status queries */
>
> cairo_public cairo_status_t
> diff --git a/src/cairoint.h b/src/cairoint.h
> index 16c9a44..8b098b2 100644
> --- a/src/cairoint.h
> +++ b/src/cairoint.h
> @@ -1390,6 +1390,11 @@ cairo_private cairo_status_t
> _cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
> const cairo_path_fixed_t *other);
>
> +cairo_private cairo_status_t
> +_cairo_path_fixed_init_flat_copy (cairo_path_fixed_t *path,
> + const cairo_path_fixed_t *other,
> + double tolerance);
> +
> cairo_private cairo_bool_t
> _cairo_path_fixed_is_equal (const cairo_path_fixed_t *path,
> const cairo_path_fixed_t *other);
> @@ -1586,6 +1591,15 @@ _cairo_path_fixed_stroke_to_traps (const
> cairo_path_fixed_t *path,
> double tolerance,
> cairo_traps_t *traps);
>
> +/* cairo-stroke-to-path.c */
> +cairo_status_t
> +_cairo_path_stroke_to_path (const cairo_path_fixed_t *path,
> + cairo_stroke_style_t *stroke_style,
> + cairo_path_fixed_t *path_out,
> + cairo_matrix_t *ctm,
> + cairo_matrix_t *ctm_invserse,
> + double tolerance); // XXX: the matrices could
> probably be const
> +
> cairo_private cairo_status_t
> _cairo_path_fixed_stroke_to_shaper (cairo_path_fixed_t *path,
> const cairo_stroke_style_t
> *stroke_style,
--
Carlos Garcia Campos
PGP key: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x523E6462
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20100129/d856fee8/attachment-0001.pgp
More information about the cairo
mailing list