[cairo-commit] 2 commits - src/cairo-contour.c src/cairo-contour-private.h src/cairoint.h src/cairo-path-fixed.c src/cairo-path-in-fill.c src/cairo-path-stroke.c src/cairo-path-stroke-polygon.c src/cairo-polygon.c src/cairo-spline.c src/cairo-types-private.h src/Makefile.sources util/.gitignore util/Makefile.am util/show-contour.c util/show-polygon.c
Chris Wilson
ickle at kemper.freedesktop.org
Mon Aug 15 02:37:18 PDT 2011
src/Makefile.sources | 3
src/cairo-contour-private.h | 159 ++++
src/cairo-contour.c | 453 +++++++++++++
src/cairo-path-fixed.c | 2
src/cairo-path-in-fill.c | 2
src/cairo-path-stroke-polygon.c | 1363 ++++++++++++++++++++++++++++++++++++++++
src/cairo-path-stroke.c | 14
src/cairo-polygon.c | 48 +
src/cairo-spline.c | 27
src/cairo-types-private.h | 6
src/cairoint.h | 14
util/.gitignore | 2
util/Makefile.am | 7
util/show-contour.c | 667 +++++++++++++++++++
util/show-polygon.c | 4
15 files changed, 2738 insertions(+), 33 deletions(-)
New commits:
commit 545f30856aac98199a49cf66c72dbcb66c1f3a4f
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Mon Aug 15 09:44:03 2011 +0100
stroke: Convert the outlines into contour and then into a polygon
In step 1 of speeding up stroking, we introduce contours as a means for
tracking the connected edges around the stroke. By keeping track of
these chains, we can analyse the edges as we proceed and eliminate
redundant vertices speeding up rasterisation.
Coincidentally fixes line-width-tolerance (looks like a combination of
using spline tangent vectors and tolerance).
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/Makefile.sources b/src/Makefile.sources
index 9f7b6fe..c1b9fb2 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -62,6 +62,7 @@ cairo_private = \
cairo-clip-private.h \
cairo-combsort-private.h \
cairo-compiler-private.h \
+ cairo-contour-private.h \
cairo-composite-rectangles-private.h \
cairo-default-context-private.h \
cairo-device-private.h \
@@ -132,6 +133,7 @@ cairo_sources = \
cairo-clip-surface.c \
cairo-color.c \
cairo-composite-rectangles.c \
+ cairo-contour.c \
cairo-debug.c \
cairo-default-context.c \
cairo-device.c \
diff --git a/src/cairo-contour-private.h b/src/cairo-contour-private.h
new file mode 100644
index 0000000..2eb1f60
--- /dev/null
+++ b/src/cairo-contour-private.h
@@ -0,0 +1,159 @@
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2011 Intel Corporation
+ *
+ * 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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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 Intel Corporation
+ *
+ * Contributor(s):
+ * Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+#ifndef CAIRO_CONTOUR_PRIVATE_H
+#define CAIRO_CONTOUR_PRIVATE_H
+
+#include "cairo-types-private.h"
+#include "cairo-compiler-private.h"
+#include "cairo-error-private.h"
+#include "cairo-list-private.h"
+
+#include <stdio.h>
+
+CAIRO_BEGIN_DECLS
+
+/* A contour is simply a closed chain of points that divide the infinite plane
+ * into inside and outside. Each contour is a simple polygon, that is it
+ * contains no holes or self-intersections, but maybe either concave or convex.
+ */
+
+struct _cairo_contour_chain {
+ cairo_point_t *points;
+ int num_points, size_points;
+ struct _cairo_contour_chain *next;
+};
+
+struct _cairo_contour_iter {
+ cairo_point_t *point;
+ cairo_contour_chain_t *chain;
+};
+
+struct _cairo_contour {
+ cairo_list_t next;
+ int direction;
+ cairo_contour_chain_t chain, *tail;
+
+ cairo_point_t embedded_points[64];
+};
+
+/* Initial definition of a shape is a set of contours (some representing holes) */
+struct _cairo_shape {
+ cairo_list_t contours;
+};
+
+typedef struct _cairo_shape cairo_shape_t;
+
+#if 0
+cairo_private cairo_status_t
+_cairo_shape_init_from_polygon (cairo_shape_t *shape,
+ const cairo_polygon_t *polygon);
+
+cairo_private cairo_status_t
+_cairo_shape_reduce (cairo_shape_t *shape, double tolerance);
+#endif
+
+cairo_private void
+_cairo_contour_init (cairo_contour_t *contour,
+ int direction);
+
+cairo_private cairo_int_status_t
+__cairo_contour_add_point (cairo_contour_t *contour,
+ const cairo_point_t *point);
+
+static inline cairo_int_status_t
+_cairo_contour_add_point (cairo_contour_t *contour,
+ const cairo_point_t *point)
+{
+ struct _cairo_contour_chain *tail = contour->tail;
+
+ if (unlikely (tail->num_points == tail->size_points))
+ return __cairo_contour_add_point (contour, point);
+
+ tail->points[tail->num_points++] = *point;
+ return CAIRO_INT_STATUS_SUCCESS;
+}
+
+static inline cairo_point_t *
+_cairo_contour_first_point (cairo_contour_t *c)
+{
+ return &c->chain.points[0];
+}
+
+static inline cairo_point_t *
+_cairo_contour_last_point (cairo_contour_t *c)
+{
+ return &c->tail->points[c->tail->num_points-1];
+}
+
+cairo_private void
+_cairo_contour_simplify (cairo_contour_t *contour, double tolerance);
+
+cairo_private void
+_cairo_contour_reverse (cairo_contour_t *contour);
+
+cairo_private cairo_int_status_t
+_cairo_contour_add (cairo_contour_t *dst,
+ const cairo_contour_t *src);
+
+cairo_private cairo_int_status_t
+_cairo_contour_add_reversed (cairo_contour_t *dst,
+ const cairo_contour_t *src);
+
+cairo_private void
+__cairo_contour_remove_last_chain (cairo_contour_t *contour);
+
+static inline void
+_cairo_contour_remove_last_point (cairo_contour_t *contour)
+{
+ if (contour->chain.num_points == 0)
+ return;
+
+ if (--contour->tail->num_points == 0)
+ __cairo_contour_remove_last_chain (contour);
+}
+
+cairo_private void
+_cairo_contour_reset (cairo_contour_t *contour);
+
+cairo_private void
+_cairo_contour_fini (cairo_contour_t *contour);
+
+cairo_private void
+_cairo_debug_print_contour (FILE *file, cairo_contour_t *contour);
+
+CAIRO_END_DECLS
+
+#endif /* CAIRO_CONTOUR_PRIVATE_H */
diff --git a/src/cairo-contour.c b/src/cairo-contour.c
new file mode 100644
index 0000000..ac3998b
--- /dev/null
+++ b/src/cairo-contour.c
@@ -0,0 +1,453 @@
+/*
+ * Copyright © 2004 Carl Worth
+ * Copyright © 2006 Red Hat, Inc.
+ * Copyright © 2008 Chris Wilson
+ * Copyright © 2011 Intel Corporation
+ *
+ * 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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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 Carl Worth
+ *
+ * Contributor(s):
+ * Carl D. Worth <cworth at cworth.org>
+ * Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+#include "cairoint.h"
+
+#include "cairo-error-private.h"
+#include "cairo-freelist-private.h"
+#include "cairo-combsort-private.h"
+#include "cairo-contour-private.h"
+
+void
+_cairo_contour_init (cairo_contour_t *contour,
+ int direction)
+{
+ contour->direction = direction;
+ contour->chain.points = contour->embedded_points;
+ contour->chain.next = NULL;
+ contour->chain.num_points = 0;
+ contour->chain.size_points = ARRAY_LENGTH (contour->embedded_points);
+ contour->tail = &contour->chain;
+}
+
+cairo_int_status_t
+__cairo_contour_add_point (cairo_contour_t *contour,
+ const cairo_point_t *point)
+{
+ cairo_contour_chain_t *tail = contour->tail;
+ cairo_contour_chain_t *next;
+
+ assert (tail->next == NULL);
+
+ next = _cairo_malloc_ab_plus_c (tail->size_points*2,
+ sizeof (cairo_point_t),
+ sizeof (cairo_contour_chain_t));
+ if (unlikely (next == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+ next->size_points = tail->size_points*2;
+ next->num_points = 1;
+ next->points = (cairo_point_t *)(next+1);
+ next->next = NULL;
+ tail->next = next;
+ contour->tail = next;
+
+ next->points[0] = *point;
+ return CAIRO_INT_STATUS_SUCCESS;
+}
+
+static void
+first_inc (cairo_contour_t *contour,
+ cairo_point_t **p,
+ cairo_contour_chain_t **chain)
+{
+ if (*p == (*chain)->points + (*chain)->num_points) {
+ assert ((*chain)->next);
+ *chain = (*chain)->next;
+ *p = &(*chain)->points[0];
+ } else
+ ++*p;
+}
+
+static void
+last_dec (cairo_contour_t *contour,
+ cairo_point_t **p,
+ cairo_contour_chain_t **chain)
+{
+ if (*p == (*chain)->points) {
+ cairo_contour_chain_t *prev;
+ assert (*chain != &contour->chain);
+ for (prev = &contour->chain; prev->next != *chain; prev = prev->next)
+ ;
+ *chain = prev;
+ *p = &(*chain)->points[(*chain)->num_points-1];
+ } else
+ --*p;
+}
+
+void
+_cairo_contour_reverse (cairo_contour_t *contour)
+{
+ cairo_contour_chain_t *first_chain, *last_chain;
+ cairo_point_t *first, *last;
+
+ contour->direction = -contour->direction;
+
+ if (contour->chain.num_points <= 1)
+ return;
+
+ first_chain = &contour->chain;
+ last_chain = contour->tail;
+
+ first = &first_chain->points[0];
+ last = &last_chain->points[last_chain->num_points-1];
+
+ while (first != last) {
+ cairo_point_t p;
+
+ p = *first;
+ *first = *last;
+ *last = p;
+
+ first_inc (contour, &first, &first_chain);
+ last_dec (contour, &last, &last_chain);
+ }
+}
+
+cairo_int_status_t
+_cairo_contour_add (cairo_contour_t *dst,
+ const cairo_contour_t *src)
+{
+ const cairo_contour_chain_t *chain;
+ cairo_int_status_t status;
+ int i;
+
+ for (chain = &src->chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ status = _cairo_contour_add_point (dst, &chain->points[i]);
+ if (unlikely (status))
+ return status;
+ }
+ }
+
+ return CAIRO_INT_STATUS_SUCCESS;
+}
+
+static inline cairo_bool_t
+iter_next (cairo_contour_iter_t *iter)
+{
+ if (iter->point == &iter->chain->points[iter->chain->size_points-1]) {
+ iter->chain = iter->chain->next;
+ if (iter->chain == NULL)
+ return FALSE;
+
+ iter->point = &iter->chain->points[0];
+ return TRUE;
+ } else {
+ iter->point++;
+ return TRUE;
+ }
+}
+
+static cairo_bool_t
+iter_equal (const cairo_contour_iter_t *i1,
+ const cairo_contour_iter_t *i2)
+{
+ return i1->chain == i2->chain && i1->point == i2->point;
+}
+
+static void
+iter_init (cairo_contour_iter_t *iter, cairo_contour_t *contour)
+{
+ iter->chain = &contour->chain;
+ iter->point = &contour->chain.points[0];
+}
+
+static void
+iter_init_last (cairo_contour_iter_t *iter, cairo_contour_t *contour)
+{
+ iter->chain = contour->tail;
+ iter->point = &contour->tail->points[contour->tail->num_points-1];
+}
+
+static const cairo_contour_chain_t *prev_const_chain(const cairo_contour_t *contour,
+ const cairo_contour_chain_t *chain)
+{
+ const cairo_contour_chain_t *prev;
+
+ if (chain == &contour->chain)
+ return NULL;
+
+ for (prev = &contour->chain; prev->next != chain; prev = prev->next)
+ ;
+
+ return prev;
+}
+
+cairo_int_status_t
+_cairo_contour_add_reversed (cairo_contour_t *dst,
+ const cairo_contour_t *src)
+{
+ const cairo_contour_chain_t *last;
+ cairo_int_status_t status;
+ int i;
+
+ if (src->chain.num_points == 0)
+ return CAIRO_INT_STATUS_SUCCESS;
+
+ for (last = src->tail; last; last = prev_const_chain (src, last)) {
+ for (i = last->num_points-1; i >= 0; i--) {
+ status = _cairo_contour_add_point (dst, &last->points[i]);
+ if (unlikely (status))
+ return status;
+ }
+ }
+
+ return CAIRO_INT_STATUS_SUCCESS;
+}
+
+static cairo_uint64_t
+point_distance_sq (const cairo_point_t *p1,
+ const cairo_point_t *p2)
+{
+ int32_t dx = p1->x - p2->x;
+ int32_t dy = p1->y - p2->y;
+ return _cairo_int32x32_64_mul (dx, dx) + _cairo_int32x32_64_mul (dy, dy);
+}
+
+#define DELETED(p) ((p)->x == INT_MIN && (p)->y == INT_MAX)
+#define MARK_DELETED(p) ((p)->x = INT_MIN, (p)->y = INT_MAX)
+
+static cairo_bool_t
+_cairo_contour_simplify_chain (cairo_contour_t *contour, const double tolerance,
+ const cairo_contour_iter_t *first,
+ const cairo_contour_iter_t *last)
+{
+ cairo_contour_iter_t iter, furthest;
+ uint64_t max_error;
+ int x0, y0;
+ int nx, ny;
+ int count;
+
+ iter = *first;
+ iter_next (&iter);
+ if (iter_equal (&iter, last))
+ return FALSE;
+
+ x0 = first->point->x;
+ y0 = first->point->y;
+ nx = last->point->y - y0;
+ ny = x0 - last->point->x;
+
+ count = 0;
+ max_error = 0;
+ do {
+ cairo_point_t *p = iter.point;
+ if (! DELETED(p)) {
+ uint64_t d = (uint64_t)nx * (x0 - p->x) + (uint64_t)ny * (y0 - p->y);
+ if (d * d > max_error) {
+ max_error = d * d;
+ furthest = iter;
+ }
+ count++;
+ }
+ iter_next (&iter);
+ } while (! iter_equal (&iter, last));
+ if (count == 0)
+ return FALSE;
+
+ if (max_error > tolerance * ((uint64_t)nx * nx + (uint64_t)ny * ny)) {
+ cairo_bool_t simplified;
+
+ simplified = FALSE;
+ simplified |= _cairo_contour_simplify_chain (contour, tolerance,
+ first, &furthest);
+ simplified |= _cairo_contour_simplify_chain (contour, tolerance,
+ &furthest, last);
+ return simplified;
+ } else {
+ iter = *first;
+ iter_next (&iter);
+ do {
+ MARK_DELETED (iter.point);
+ iter_next (&iter);
+ } while (! iter_equal (&iter, last));
+
+ return TRUE;
+ }
+}
+
+void
+_cairo_contour_simplify (cairo_contour_t *contour, double tolerance)
+{
+ cairo_contour_chain_t *chain;
+ cairo_point_t *last = NULL;
+ cairo_contour_iter_t iter, furthest;
+ cairo_bool_t simplified;
+ uint64_t max = 0;
+ int i;
+
+ if (contour->chain.num_points <= 2)
+ return;
+
+ tolerance = tolerance * CAIRO_FIXED_ONE;
+ tolerance *= tolerance;
+
+ /* stage 1: vertex reduction */
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ if (last == NULL ||
+ point_distance_sq (last, &chain->points[i]) > tolerance) {
+ last = &chain->points[i];
+ } else {
+ MARK_DELETED (&chain->points[i]);
+ }
+ }
+ }
+
+ /* stage2: polygon simplification using Douglas-Peucker */
+ simplified = FALSE;
+ do {
+ last = &contour->chain.points[0];
+ iter_init (&furthest, contour);
+ max = 0;
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ uint64_t d;
+
+ if (DELETED (&chain->points[i]))
+ continue;
+
+ d = point_distance_sq (last, &chain->points[i]);
+ if (d > max) {
+ furthest.chain = chain;
+ furthest.point = &chain->points[i];
+ max = d;
+ }
+ }
+ }
+ assert (max);
+
+ simplified = FALSE;
+ iter_init (&iter, contour);
+ simplified |= _cairo_contour_simplify_chain (contour, tolerance,
+ &iter, &furthest);
+
+ iter_init_last (&iter, contour);
+ if (! iter_equal (&furthest, &iter))
+ simplified |= _cairo_contour_simplify_chain (contour, tolerance,
+ &furthest, &iter);
+ } while (simplified);
+
+ iter_init (&iter, contour);
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ int num_points = chain->num_points;
+ chain->num_points = 0;
+ for (i = 0; i < num_points; i++) {
+ if (! DELETED(&chain->points[i])) {
+ if (iter.point != &chain->points[i])
+ *iter.point = chain->points[i];
+ iter.chain->num_points++;
+ iter_next (&iter);
+ }
+ }
+ }
+
+ if (iter.chain) {
+ cairo_contour_chain_t *next;
+
+ for (chain = iter.chain->next; chain; chain = next) {
+ next = chain->next;
+ free (chain);
+ }
+
+ iter.chain->next = NULL;
+ contour->tail = iter.chain;
+ }
+}
+
+void
+_cairo_contour_reset (cairo_contour_t *contour)
+{
+ _cairo_contour_fini (contour);
+ _cairo_contour_init (contour, contour->direction);
+}
+
+void
+_cairo_contour_fini (cairo_contour_t *contour)
+{
+ cairo_contour_chain_t *chain, *next;
+
+ for (chain = contour->chain.next; chain; chain = next) {
+ next = chain->next;
+ free (chain);
+ }
+}
+
+void
+_cairo_debug_print_contour (FILE *file, cairo_contour_t *contour)
+{
+ cairo_contour_chain_t *chain;
+ int num_points, size_points;
+ int i;
+
+ num_points = 0;
+ size_points = 0;
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ num_points += chain->num_points;
+ size_points += chain->size_points;
+ }
+
+ fprintf (file, "contour: direction=%d, num_points=%d / %d\n",
+ contour->direction, num_points, size_points);
+
+ num_points = 0;
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ fprintf (file, " [%d] = (%f, %f)\n",
+ num_points++,
+ _cairo_fixed_to_double (chain->points[i].x),
+ _cairo_fixed_to_double (chain->points[i].y));
+ }
+ }
+}
+
+void
+__cairo_contour_remove_last_chain (cairo_contour_t *contour)
+{
+ cairo_contour_chain_t *chain;
+
+ if (contour->tail == &contour->chain)
+ return;
+
+ for (chain = &contour->chain; chain->next != contour->tail; chain = chain->next)
+ ;
+ free (contour->tail);
+ contour->tail = chain;
+ chain->next = NULL;
+}
diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index a562e5b..d67954f 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -1128,7 +1128,7 @@ _cpf_curve_to (void *closure,
cairo_point_t *p0 = &cpf->current_point;
if (! _cairo_spline_init (&spline,
- cpf->line_to,
+ (cairo_spline_add_point_func_t)cpf->line_to,
cpf->closure,
p0, p1, p2, p3))
{
diff --git a/src/cairo-path-in-fill.c b/src/cairo-path-in-fill.c
index 3738874..1787fb1 100644
--- a/src/cairo-path-in-fill.c
+++ b/src/cairo-path-in-fill.c
@@ -217,7 +217,7 @@ _cairo_in_fill_curve_to (void *closure,
/* XXX Investigate direct inspection of the inflections? */
if (! _cairo_spline_init (&spline,
- _cairo_in_fill_line_to,
+ (cairo_spline_add_point_func_t)_cairo_in_fill_line_to,
in_fill,
&in_fill->current_point, b, c, d))
{
diff --git a/src/cairo-path-stroke-polygon.c b/src/cairo-path-stroke-polygon.c
index c60c2c0..3b8a67d 100644
--- a/src/cairo-path-stroke-polygon.c
+++ b/src/cairo-path-stroke-polygon.c
@@ -2,6 +2,7 @@
/* cairo - a vector graphics library with display and print output
*
* Copyright © 2002 University of Southern California
+ * Copyright © 2011 Intel Corporation
*
* This library is free software; you can redistribute it and/or
* modify it either under the terms of the GNU Lesser General Public
@@ -41,23 +42,34 @@
#include "cairo-box-private.h"
#include "cairo-boxes-private.h"
+#include "cairo-contour-private.h"
#include "cairo-error-private.h"
#include "cairo-path-fixed-private.h"
#include "cairo-slope-private.h"
-typedef struct cairo_stroker {
+#define DEBUG 0
+
+struct stroker {
cairo_stroke_style_t style;
+#if DEBUG
+ cairo_contour_t path;
+#endif
+
+ struct stroke_contour {
+ /* Note that these are not strictly contours as they may intersect */
+ cairo_contour_t contour;
+ } cw, ccw;
+ cairo_uint64_t contour_tolerance;
+ cairo_polygon_t *polygon;
+
const cairo_matrix_t *ctm;
const cairo_matrix_t *ctm_inverse;
double tolerance;
- double ctm_determinant;
cairo_bool_t ctm_det_positive;
- cairo_polygon_t *polygon;
- cairo_pen_t pen;
+ cairo_pen_t pen;
- cairo_point_t current_point;
cairo_point_t first_point;
cairo_bool_t has_initial_sub_path;
@@ -67,38 +79,42 @@ typedef struct cairo_stroker {
cairo_bool_t has_first_face;
cairo_stroke_face_t first_face;
+};
- cairo_bool_t has_bounds;
- cairo_box_t bounds;
-} cairo_stroker_t;
+static inline double
+normalize_slope (double *dx, double *dy);
static void
-stroker_limit (cairo_stroker_t *stroker,
- const cairo_box_t *boxes,
- int num_boxes)
+compute_face (const cairo_point_t *point,
+ const cairo_slope_t *dev_slope,
+ struct stroker *stroker,
+ cairo_stroke_face_t *face);
+
+static cairo_uint64_t
+point_distance_sq (const cairo_point_t *p1,
+ const cairo_point_t *p2)
{
- double dx, dy;
- cairo_fixed_t fdx, fdy;
-
- stroker->has_bounds = TRUE;
- _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
-
- /* Extend the bounds in each direction to account for the maximum area
- * we might generate trapezoids, to capture line segments that are outside
- * of the bounds but which might generate rendering that's within bounds.
- */
-
- _cairo_stroke_style_max_distance_from_path (&stroker->style, stroker->ctm,
- &dx, &dy);
-
- fdx = _cairo_fixed_from_double (dx);
- fdy = _cairo_fixed_from_double (dy);
+ int32_t dx = p1->x - p2->x;
+ int32_t dy = p1->y - p2->y;
+ return _cairo_int32x32_64_mul (dx, dx) + _cairo_int32x32_64_mul (dy, dy);
+}
- stroker->bounds.p1.x -= fdx;
- stroker->bounds.p2.x += fdx;
+static cairo_bool_t
+within_tolerance (const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ cairo_uint64_t tolerance)
+{
+ return _cairo_int64_lt (point_distance_sq (p1, p2), tolerance);
+}
- stroker->bounds.p1.y -= fdy;
- stroker->bounds.p2.y += fdy;
+static void
+contour_add_point (struct stroker *stroker,
+ struct stroke_contour *c,
+ const cairo_point_t *point)
+{
+ if (! within_tolerance (point, _cairo_contour_last_point (&c->contour),
+ stroker->contour_tolerance))
+ _cairo_contour_add_point (&c->contour, point);
}
static void
@@ -109,19 +125,6 @@ translate_point (cairo_point_t *point, const cairo_point_t *offset)
}
static int
-join_is_clockwise (const cairo_stroke_face_t *in,
- const cairo_stroke_face_t *out)
-{
- return _cairo_slope_compare (&in->dev_vector, &out->dev_vector) < 0;
-}
-
-/**
- * slope_compare_sgn
- *
- * Return -1, 0 or 1 depending on the relative slopes of
- * two lines.
- */
-static int
slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
{
double c = (dx1 * dy2 - dx2 * dy1);
@@ -146,43 +149,19 @@ range_step (int i, int step, int max)
* Construct a fan around the midpoint using the vertices from pen between
* inpt and outpt.
*/
-static cairo_status_t
-tessellate_fan (cairo_stroker_t *stroker,
- const cairo_slope_t *in_vector,
- const cairo_slope_t *out_vector,
- const cairo_point_t *midpt,
- const cairo_point_t *inpt,
- const cairo_point_t *outpt,
- cairo_bool_t clockwise)
+static void
+add_fan (struct stroker *stroker,
+ const cairo_slope_t *in_vector,
+ const cairo_slope_t *out_vector,
+ const cairo_point_t *midpt,
+ const cairo_point_t *inpt,
+ const cairo_point_t *outpt,
+ cairo_bool_t clockwise,
+ struct stroke_contour *c)
{
- cairo_point_t stack_points[64], *points = stack_points;
int start, stop, step, i, npoints;
- cairo_status_t status;
if (clockwise) {
- step = -1;
-
- start = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
- in_vector);
- if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_ccw,
- in_vector) < 0)
- start = range_step (start, -1, stroker->pen.num_vertices);
-
- stop = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
- out_vector);
- if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
- out_vector) > 0)
- {
- stop = range_step (stop, 1, stroker->pen.num_vertices);
- if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
- in_vector) < 0)
- {
- goto BEVEL;
- }
- }
-
- npoints = start - stop;
- } else {
step = 1;
start = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
@@ -199,119 +178,296 @@ tessellate_fan (cairo_stroker_t *stroker,
stop = range_step (stop, -1, stroker->pen.num_vertices);
if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
in_vector) < 0)
- {
- goto BEVEL;
- }
+ return;
}
npoints = stop - start;
+ } else {
+ step = -1;
+
+ start = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
+ in_vector);
+ if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_ccw,
+ in_vector) < 0)
+ start = range_step (start, -1, stroker->pen.num_vertices);
+
+ stop = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
+ out_vector);
+ if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
+ out_vector) > 0)
+ {
+ stop = range_step (stop, 1, stroker->pen.num_vertices);
+ if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
+ in_vector) < 0)
+ return;
+ }
+
+ npoints = start - stop;
}
stop = range_step (stop, step, stroker->pen.num_vertices);
-
if (npoints < 0)
npoints += stroker->pen.num_vertices;
- npoints += 3;
-
if (npoints <= 1)
- goto BEVEL;
-
- if (npoints > ARRAY_LENGTH (stack_points)) {
- points = _cairo_malloc_ab (npoints, sizeof (cairo_point_t));
- if (unlikely (points == NULL))
- return _cairo_error (CAIRO_STATUS_NO_MEMORY);
- }
-
+ return;
- /* Construct the fan. */
- npoints = 0;
- points[npoints++] = *inpt;
for (i = start;
i != stop;
i = range_step (i, step, stroker->pen.num_vertices))
{
- points[npoints] = *midpt;
- translate_point (&points[npoints], &stroker->pen.vertices[i].point);
- npoints++;
+ cairo_point_t p = *midpt;
+ translate_point (&p, &stroker->pen.vertices[i].point);
+ contour_add_point (stroker, c, &p);
}
- points[npoints++] = *outpt;
+}
- for (i = 0; i < npoints - 1; i++) {
- if (clockwise) {
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &points[i], &points[i+1]);
- } else {
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &points[i+1], &points[i]);
- }
- if (unlikely (status))
- break;
- }
+static int
+join_is_clockwise (const cairo_stroke_face_t *in,
+ const cairo_stroke_face_t *out)
+{
+ return _cairo_slope_compare (&in->dev_vector, &out->dev_vector) < 0;
+}
- if (points != stack_points)
- free (points);
+static cairo_int64_t
+distance_from_face (const cairo_stroke_face_t *face,
+ const cairo_point_t *p,
+ cairo_bool_t negate)
+{
+ int32_t dx = (p->x - face->point.x);
+ int32_t dy = (p->y - face->point.y);
+ cairo_int64_t d;
+
+ d = _cairo_int64_sub (_cairo_int32x32_64_mul (dx, face->dev_vector.dy),
+ _cairo_int32x32_64_mul (dy, face->dev_vector.dx));
+ if (negate)
+ d = _cairo_int64_negate (d);
+ return d;
+}
- return status;
+static cairo_int64_t
+distance_along_face (const cairo_stroke_face_t *face,
+ const cairo_point_t *p)
+{
+ int32_t dx = (p->x - face->point.x);
+ int32_t dy = (p->y - face->point.y);
+ return _cairo_int64_add (_cairo_int32x32_64_mul (dx, face->dev_vector.dx),
+ _cairo_int32x32_64_mul (dy, face->dev_vector.dy));
+}
+
+static void
+compute_inner_joint (cairo_point_t *p1, cairo_int64_t d_p1,
+ const cairo_point_t *p2, cairo_int64_t d_p2,
+ cairo_int64_t half_line_width)
+{
+ int32_t dx = p2->x - p1->x;
+ int32_t dy = p2->y - p1->y;
+
+ half_line_width = _cairo_int64_sub (half_line_width, d_p1);
+ d_p2 = _cairo_int64_sub (d_p2, d_p1);
+
+ p1->x += _cairo_int_96by64_32x64_divrem (_cairo_int64x32_128_mul (half_line_width, dx),
+ d_p2).quo;
-BEVEL:
- /* Ensure a leak free connection... */
- if (clockwise)
- return _cairo_polygon_add_external_edge (stroker->polygon, inpt, outpt);
- else
- return _cairo_polygon_add_external_edge (stroker->polygon, outpt, inpt);
+ p1->y += _cairo_int_96by64_32x64_divrem (_cairo_int64x32_128_mul (half_line_width, dy),
+ d_p2).quo;
}
-static cairo_status_t
-join (cairo_stroker_t *stroker,
- const cairo_stroke_face_t *in,
- const cairo_stroke_face_t *out)
+static void
+inner_join (struct stroker *stroker,
+ const cairo_stroke_face_t *in,
+ const cairo_stroke_face_t *out,
+ int clockwise)
{
- int clockwise = join_is_clockwise (out, in);
- const cairo_point_t *inpt, *outpt;
- cairo_point_t points[4];
- cairo_status_t status;
+#if 0
+ cairo_point_t last;
+ const cairo_point_t *p, *outpt;
+ struct stroke_contour *inner;
+ cairo_int64_t d_p, d_last;
+ cairo_int64_t half_line_width;
+ cairo_bool_t negate;
+
+ /* XXX line segments shorter than line-width */
+
+ if (clockwise) {
+ inner = &stroker->ccw;
+ outpt = &out->ccw;
+ negate = 1;
+ } else {
+ inner = &stroker->cw;
+ outpt = &out->cw;
+ negate = 0;
+ }
+
+ half_line_width = CAIRO_FIXED_ONE*CAIRO_FIXED_ONE/2 * stroker->style.line_width * out->length + .5;
- if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
- in->ccw.x == out->ccw.x && in->ccw.y == out->ccw.y)
+ /* On the inside, the previous end-point is always
+ * closer to the new face by definition.
+ */
+ last = *_cairo_contour_last_point (&inner->contour);
+ d_last = distance_from_face (out, &last, negate);
+ _cairo_contour_remove_last_point (&inner->contour);
+
+prev:
+ if (inner->contour.chain.num_points == 0) {
+ contour_add_point (stroker, inner, outpt);
+ return;
+ }
+ p = _cairo_contour_last_point (&inner->contour);
+ d_p = distance_from_face (out, p, negate);
+ if (_cairo_int64_lt (d_p, half_line_width) &&
+ !_cairo_int64_negative (distance_along_face (out, p)))
{
- return CAIRO_STATUS_SUCCESS;
+ last = *p;
+ d_last = d_p;
+ _cairo_contour_remove_last_point (&inner->contour);
+ goto prev;
}
+ compute_inner_joint (&last, d_last, p, d_p, half_line_width);
+ contour_add_point (stroker, inner, &last);
+#else
+ const cairo_point_t *outpt;
+ struct stroke_contour *inner;
+
if (clockwise) {
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &out->cw, &in->point);
- if (unlikely (status))
- return status;
+ inner = &stroker->ccw;
+ outpt = &out->ccw;
+ } else {
+ inner = &stroker->cw;
+ outpt = &out->cw;
+ }
+ contour_add_point (stroker, inner, &in->point);
+ contour_add_point (stroker, inner, outpt);
+#endif
+}
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &in->point, &in->cw);
- if (unlikely (status))
- return status;
+static void
+inner_close (struct stroker *stroker,
+ const cairo_stroke_face_t *in,
+ cairo_stroke_face_t *out)
+{
+#if 0
+ cairo_point_t last;
+ const cairo_point_t *p, *outpt, *inpt;
+ struct stroke_contour *inner;
+ struct _cairo_contour_chain *chain;
+
+ /* XXX line segments shorter than line-width */
+
+ if (join_is_clockwise (in, out)) {
+ inner = &stroker->ccw;
+ outpt = &in->ccw;
+ inpt = &out->ccw;
+ } else {
+ inner = &stroker->cw;
+ outpt = &in->cw;
+ inpt = &out->cw;
+ }
- inpt = &in->ccw;
- outpt = &out->ccw;
+ if (inner->contour.chain.num_points == 0) {
+ contour_add_point (stroker, inner, &in->point);
+ contour_add_point (stroker, inner, inpt);
+ *_cairo_contour_first_point (&inner->contour) =
+ *_cairo_contour_last_point (&inner->contour);
+ return;
+ }
+
+ line_width = stroker->style.line_width/2;
+ line_width *= CAIRO_FIXED_ONE;
+
+ d_last = sign * distance_from_face (out, outpt);
+ last = *outpt;
+
+ for (chain = &inner->contour.chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ p = &chain->points[i];
+ if ((d_p = sign * distance_from_face (in, p)) >= line_width &&
+ distance_from_edge (stroker, inpt, &last, p) < line_width)
+ {
+ goto out;
+ }
+
+ if (p->x != last.x || p->y != last.y) {
+ last = *p;
+ d_last = d_p;
+ }
+ }
+ }
+out:
+
+ if (d_p != d_last) {
+ double dot = (line_width - d_last) / (d_p - d_last);
+ last.x += dot * (p->x - last.x);
+ last.y += dot * (p->y - last.y);
+ }
+ *_cairo_contour_last_point (&inner->contour) = last;
+
+ for (chain = &inner->contour.chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ cairo_point_t *pp = &chain->points[i];
+ if (pp == p)
+ return;
+ *pp = last;
+ }
+ }
+#else
+ const cairo_point_t *inpt;
+ struct stroke_contour *inner;
+
+ if (join_is_clockwise (in, out)) {
+ inner = &stroker->ccw;
+ inpt = &out->ccw;
} else {
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &in->ccw, &in->point);
- if (unlikely (status))
- return status;
+ inner = &stroker->cw;
+ inpt = &out->cw;
+ }
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &in->point, &out->ccw);
- if (unlikely (status))
- return status;
+ contour_add_point (stroker, inner, &in->point);
+ contour_add_point (stroker, inner, inpt);
+ *_cairo_contour_first_point (&inner->contour) =
+ *_cairo_contour_last_point (&inner->contour);
+#endif
+}
+
+static void
+outer_close (struct stroker *stroker,
+ const cairo_stroke_face_t *in,
+ const cairo_stroke_face_t *out)
+{
+ const cairo_point_t *inpt, *outpt;
+ struct stroke_contour *outer;
+ int clockwise;
+ if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
+ in->ccw.x == out->ccw.x && out->ccw.y == out->ccw.y)
+ {
+ return;
+ }
+ clockwise = join_is_clockwise (in, out);
+ if (clockwise) {
inpt = &in->cw;
outpt = &out->cw;
+ outer = &stroker->cw;
+ } else {
+ inpt = &in->ccw;
+ outpt = &out->ccw;
+ outer = &stroker->ccw;
+ }
+
+ if (within_tolerance (inpt, outpt, stroker->contour_tolerance)) {
+ *_cairo_contour_first_point (&outer->contour) =
+ *_cairo_contour_last_point (&outer->contour);
+ return;
}
switch (stroker->style.line_join) {
case CAIRO_LINE_JOIN_ROUND:
/* construct a fan around the common midpoint */
- return tessellate_fan (stroker,
- &in->dev_vector,
- &out->dev_vector,
- &in->point, inpt, outpt,
- clockwise);
+ add_fan (stroker,
+ &in->dev_vector,
+ &out->dev_vector,
+ &in->point, inpt, outpt,
+ clockwise, outer);
+ break;
case CAIRO_LINE_JOIN_MITER:
default: {
@@ -448,52 +604,216 @@ join (cairo_stroker_t *stroker,
if (slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
slope_compare_sgn (fdx2, fdy2, mdx, mdy))
{
- points[0].x = _cairo_fixed_from_double (mx);
- points[0].y = _cairo_fixed_from_double (my);
-
- if (clockwise) {
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- inpt, &points[0]);
- if (unlikely (status))
- return status;
-
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &points[0], outpt);
- if (unlikely (status))
- return status;
- } else {
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- outpt, &points[0]);
- if (unlikely (status))
- return status;
-
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &points[0], inpt);
- if (unlikely (status))
- return status;
- }
-
- return CAIRO_STATUS_SUCCESS;
+ cairo_point_t p;
+
+ p.x = _cairo_fixed_from_double (mx);
+ p.y = _cairo_fixed_from_double (my);
+
+ *_cairo_contour_last_point (&outer->contour) = p;
+ *_cairo_contour_first_point (&outer->contour) = p;
+ return;
}
}
+ break;
}
- /* fall through ... */
-
case CAIRO_LINE_JOIN_BEVEL:
- if (clockwise) {
- return _cairo_polygon_add_external_edge (stroker->polygon,
- inpt, outpt);
- } else {
- return _cairo_polygon_add_external_edge (stroker->polygon,
- outpt, inpt);
+ break;
+ }
+ contour_add_point (stroker, outer, outpt);
+}
+
+static void
+outer_join (struct stroker *stroker,
+ const cairo_stroke_face_t *in,
+ const cairo_stroke_face_t *out,
+ int clockwise)
+{
+ const cairo_point_t *inpt, *outpt;
+ struct stroke_contour *outer;
+
+ if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
+ in->ccw.x == out->ccw.x && out->ccw.y == out->ccw.y)
+ {
+ return;
+ }
+ if (clockwise) {
+ inpt = &in->cw;
+ outpt = &out->cw;
+ outer = &stroker->cw;
+ } else {
+ inpt = &in->ccw;
+ outpt = &out->ccw;
+ outer = &stroker->ccw;
+ }
+
+ switch (stroker->style.line_join) {
+ case CAIRO_LINE_JOIN_ROUND:
+ /* construct a fan around the common midpoint */
+ add_fan (stroker,
+ &in->dev_vector,
+ &out->dev_vector,
+ &in->point, inpt, outpt,
+ clockwise, outer);
+ break;
+
+ case CAIRO_LINE_JOIN_MITER:
+ default: {
+ /* dot product of incoming slope vector with outgoing slope vector */
+ double in_dot_out = -in->usr_vector.x * out->usr_vector.x +
+ -in->usr_vector.y * out->usr_vector.y;
+ double ml = stroker->style.miter_limit;
+
+ /* Check the miter limit -- lines meeting at an acute angle
+ * can generate long miters, the limit converts them to bevel
+ *
+ * Consider the miter join formed when two line segments
+ * meet at an angle psi:
+ *
+ * /.\
+ * /. .\
+ * /./ \.\
+ * /./psi\.\
+ *
+ * We can zoom in on the right half of that to see:
+ *
+ * |\
+ * | \ psi/2
+ * | \
+ * | \
+ * | \
+ * | \
+ * miter \
+ * length \
+ * | \
+ * | .\
+ * | . \
+ * |. line \
+ * \ width \
+ * \ \
+ *
+ *
+ * The right triangle in that figure, (the line-width side is
+ * shown faintly with three '.' characters), gives us the
+ * following expression relating miter length, angle and line
+ * width:
+ *
+ * 1 /sin (psi/2) = miter_length / line_width
+ *
+ * The right-hand side of this relationship is the same ratio
+ * in which the miter limit (ml) is expressed. We want to know
+ * when the miter length is within the miter limit. That is
+ * when the following condition holds:
+ *
+ * 1/sin(psi/2) <= ml
+ * 1 <= ml sin(psi/2)
+ * 1 <= ml² sin²(psi/2)
+ * 2 <= ml² 2 sin²(psi/2)
+ * 2·sin²(psi/2) = 1-cos(psi)
+ * 2 <= ml² (1-cos(psi))
+ *
+ * in · out = |in| |out| cos (psi)
+ *
+ * in and out are both unit vectors, so:
+ *
+ * in · out = cos (psi)
+ *
+ * 2 <= ml² (1 - in · out)
+ *
+ */
+ if (2 <= ml * ml * (1 - in_dot_out)) {
+ double x1, y1, x2, y2;
+ double mx, my;
+ double dx1, dx2, dy1, dy2;
+ double ix, iy;
+ double fdx1, fdy1, fdx2, fdy2;
+ double mdx, mdy;
+
+ /*
+ * we've got the points already transformed to device
+ * space, but need to do some computation with them and
+ * also need to transform the slope from user space to
+ * device space
+ */
+ /* outer point of incoming line face */
+ x1 = _cairo_fixed_to_double (inpt->x);
+ y1 = _cairo_fixed_to_double (inpt->y);
+ dx1 = in->usr_vector.x;
+ dy1 = in->usr_vector.y;
+ cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
+
+ /* outer point of outgoing line face */
+ x2 = _cairo_fixed_to_double (outpt->x);
+ y2 = _cairo_fixed_to_double (outpt->y);
+ dx2 = out->usr_vector.x;
+ dy2 = out->usr_vector.y;
+ cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
+
+ /*
+ * Compute the location of the outer corner of the miter.
+ * That's pretty easy -- just the intersection of the two
+ * outer edges. We've got slopes and points on each
+ * of those edges. Compute my directly, then compute
+ * mx by using the edge with the larger dy; that avoids
+ * dividing by values close to zero.
+ */
+ my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
+ (dx1 * dy2 - dx2 * dy1));
+ if (fabs (dy1) >= fabs (dy2))
+ mx = (my - y1) * dx1 / dy1 + x1;
+ else
+ mx = (my - y2) * dx2 / dy2 + x2;
+
+ /*
+ * When the two outer edges are nearly parallel, slight
+ * perturbations in the position of the outer points of the lines
+ * caused by representing them in fixed point form can cause the
+ * intersection point of the miter to move a large amount. If
+ * that moves the miter intersection from between the two faces,
+ * then draw a bevel instead.
+ */
+
+ ix = _cairo_fixed_to_double (in->point.x);
+ iy = _cairo_fixed_to_double (in->point.y);
+
+ /* slope of one face */
+ fdx1 = x1 - ix; fdy1 = y1 - iy;
+
+ /* slope of the other face */
+ fdx2 = x2 - ix; fdy2 = y2 - iy;
+
+ /* slope from the intersection to the miter point */
+ mdx = mx - ix; mdy = my - iy;
+
+ /*
+ * Make sure the miter point line lies between the two
+ * faces by comparing the slopes
+ */
+ if (1 || slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
+ slope_compare_sgn (fdx2, fdy2, mdx, mdy))
+ {
+ cairo_point_t p;
+
+ p.x = _cairo_fixed_from_double (mx);
+ p.y = _cairo_fixed_from_double (my);
+
+ *_cairo_contour_last_point (&outer->contour) = p;
+ return;
+ }
}
+ break;
}
+
+ case CAIRO_LINE_JOIN_BEVEL:
+ break;
+ }
+ contour_add_point (stroker,outer, outpt);
}
-static cairo_status_t
-add_cap (cairo_stroker_t *stroker,
- const cairo_stroke_face_t *f)
+static void
+add_cap (struct stroker *stroker,
+ const cairo_stroke_face_t *f,
+ struct stroke_contour *c)
{
switch (stroker->style.line_cap) {
case CAIRO_LINE_CAP_ROUND: {
@@ -502,19 +822,16 @@ add_cap (cairo_stroker_t *stroker,
slope.dx = -f->dev_vector.dx;
slope.dy = -f->dev_vector.dy;
- return tessellate_fan (stroker,
- &f->dev_vector,
- &slope,
- &f->point, &f->cw, &f->ccw,
- FALSE);
-
+ add_fan (stroker, &f->dev_vector, &slope,
+ &f->point, &f->ccw, &f->cw,
+ FALSE, c);
+ break;
}
case CAIRO_LINE_CAP_SQUARE: {
double dx, dy;
cairo_slope_t fvector;
cairo_point_t quad[4];
- cairo_status_t status;
dx = f->usr_vector.x;
dy = f->usr_vector.y;
@@ -531,34 +848,21 @@ add_cap (cairo_stroker_t *stroker,
quad[2].y = f->cw.y + fvector.dy;
quad[3] = f->cw;
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &quad[0], &quad[1]);
- if (unlikely (status))
- return status;
-
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &quad[1], &quad[2]);
- if (unlikely (status))
- return status;
-
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &quad[2], &quad[3]);
- if (unlikely (status))
- return status;
-
- return CAIRO_STATUS_SUCCESS;
+ contour_add_point (stroker, c, &quad[1]);
+ contour_add_point (stroker, c, &quad[2]);
}
case CAIRO_LINE_CAP_BUTT:
default:
- return _cairo_polygon_add_external_edge (stroker->polygon,
- &f->ccw, &f->cw);
+ break;
}
+ contour_add_point (stroker, c, &f->cw);
}
-static cairo_status_t
-add_leading_cap (cairo_stroker_t *stroker,
- const cairo_stroke_face_t *face)
+static void
+add_leading_cap (struct stroker *stroker,
+ const cairo_stroke_face_t *face,
+ struct stroke_contour *c)
{
cairo_stroke_face_t reversed;
cairo_point_t t;
@@ -570,35 +874,29 @@ add_leading_cap (cairo_stroker_t *stroker,
reversed.usr_vector.y = -reversed.usr_vector.y;
reversed.dev_vector.dx = -reversed.dev_vector.dx;
reversed.dev_vector.dy = -reversed.dev_vector.dy;
+
t = reversed.cw;
reversed.cw = reversed.ccw;
reversed.ccw = t;
- return add_cap (stroker, &reversed);
+ add_cap (stroker, &reversed, c);
}
-static cairo_status_t
-add_trailing_cap (cairo_stroker_t *stroker,
- const cairo_stroke_face_t *face)
+static void
+add_trailing_cap (struct stroker *stroker,
+ const cairo_stroke_face_t *face,
+ struct stroke_contour *c)
{
- return add_cap (stroker, face);
+ add_cap (stroker, face, c);
}
-static inline cairo_bool_t
-compute_normalized_device_slope (double *dx, double *dy,
- const cairo_matrix_t *ctm_inverse,
- double *mag_out)
+static inline double
+normalize_slope (double *dx, double *dy)
{
double dx0 = *dx, dy0 = *dy;
double mag;
- cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
-
- if (dx0 == 0.0 && dy0 == 0.0) {
- if (mag_out)
- *mag_out = 0.0;
- return FALSE;
- }
+ assert (dx0 != 0.0 || dy0 != 0.0);
if (dx0 == 0.0) {
*dx = 0.0;
@@ -624,19 +922,24 @@ compute_normalized_device_slope (double *dx, double *dy,
*dy = dy0 / mag;
}
- if (mag_out)
- *mag_out = mag;
-
- return TRUE;
+ return mag;
}
static void
-compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
- double slope_dx, double slope_dy,
- cairo_stroker_t *stroker, cairo_stroke_face_t *face)
+compute_face (const cairo_point_t *point,
+ const cairo_slope_t *dev_slope,
+ struct stroker *stroker,
+ cairo_stroke_face_t *face)
{
double face_dx, face_dy;
cairo_point_t offset_ccw, offset_cw;
+ double slope_dx, slope_dy;
+
+ slope_dx = _cairo_fixed_to_double (dev_slope->dx);
+ slope_dy = _cairo_fixed_to_double (dev_slope->dy);
+ face->length = normalize_slope (&slope_dx, &slope_dy);
+ face->dev_slope.x = slope_dx;
+ face->dev_slope.y = slope_dy;
/*
* rotate to get a line_width/2 vector along the face, note that
@@ -645,19 +948,29 @@ compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
* whether the ctm reflects or not, and that can be determined
* by looking at the determinant of the matrix.
*/
- if (stroker->ctm_det_positive)
- {
+ if (! _cairo_matrix_is_identity (stroker->ctm_inverse)) {
+ /* Normalize the matrix! */
+ cairo_matrix_transform_distance (stroker->ctm_inverse,
+ &slope_dx, &slope_dy);
+ normalize_slope (&slope_dx, &slope_dy);
+
+ if (stroker->ctm_det_positive)
+ {
+ face_dx = - slope_dy * (stroker->style.line_width / 2.0);
+ face_dy = slope_dx * (stroker->style.line_width / 2.0);
+ }
+ else
+ {
+ face_dx = slope_dy * (stroker->style.line_width / 2.0);
+ face_dy = - slope_dx * (stroker->style.line_width / 2.0);
+ }
+
+ /* back to device space */
+ cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
+ } else {
face_dx = - slope_dy * (stroker->style.line_width / 2.0);
face_dy = slope_dx * (stroker->style.line_width / 2.0);
}
- else
- {
- face_dx = slope_dy * (stroker->style.line_width / 2.0);
- face_dy = - slope_dx * (stroker->style.line_width / 2.0);
- }
-
- /* back to device space */
- cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
offset_ccw.x = _cairo_fixed_from_double (face_dx);
offset_ccw.y = _cairo_fixed_from_double (face_dy);
@@ -678,11 +991,9 @@ compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
face->dev_vector = *dev_slope;
}
-static cairo_status_t
-add_caps (cairo_stroker_t *stroker)
+static void
+add_caps (struct stroker *stroker)
{
- cairo_status_t status;
-
/* check for a degenerative sub_path */
if (stroker->has_initial_sub_path &&
! stroker->has_first_face &&
@@ -690,96 +1001,85 @@ add_caps (cairo_stroker_t *stroker)
stroker->style.line_cap == CAIRO_LINE_CAP_ROUND)
{
/* pick an arbitrary slope to use */
- double dx = 1.0, dy = 0.0;
cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
cairo_stroke_face_t face;
- compute_normalized_device_slope (&dx, &dy,
- stroker->ctm_inverse, NULL);
+ /* arbitrarily choose first_point */
+ compute_face (&stroker->first_point, &slope, stroker, &face);
- /* arbitrarily choose first_point
- * first_point and current_point should be the same */
- compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
+ add_leading_cap (stroker, &face, &stroker->ccw);
+ add_trailing_cap (stroker, &face, &stroker->ccw);
- status = add_leading_cap (stroker, &face);
- if (unlikely (status))
- return status;
+ /* ensure the circle is complete */
+ _cairo_contour_add_point (&stroker->ccw.contour,
+ _cairo_contour_first_point (&stroker->ccw.contour));
- status = add_trailing_cap (stroker, &face);
- if (unlikely (status))
- return status;
- }
-
- if (stroker->has_first_face) {
- status = add_leading_cap (stroker, &stroker->first_face);
- if (unlikely (status))
- return status;
- }
-
- if (stroker->has_current_face) {
- status = add_trailing_cap (stroker, &stroker->current_face);
- if (unlikely (status))
- return status;
- }
-
- return CAIRO_STATUS_SUCCESS;
-}
-
-static cairo_status_t
-add_sub_edge (cairo_stroker_t *stroker,
- const cairo_point_t *p1,
- const cairo_point_t *p2,
- cairo_slope_t *dev_slope,
- double slope_dx, double slope_dy,
- cairo_stroke_face_t *start,
- cairo_stroke_face_t *end)
-{
- cairo_status_t status;
-
- compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
- *end = *start;
+ _cairo_polygon_add_contour (stroker->polygon, &stroker->ccw.contour);
+ _cairo_contour_reset (&stroker->ccw.contour);
+ } else {
+ if (stroker->has_current_face)
+ add_trailing_cap (stroker, &stroker->current_face, &stroker->ccw);
- if (p1->x == p2->x && p1->y == p2->y)
- return CAIRO_STATUS_SUCCESS;
+#if DEBUG
+ {
+ FILE *file = fopen ("contours.txt", "a");
+ _cairo_debug_print_contour (file, &stroker->path);
+ _cairo_debug_print_contour (file, &stroker->cw.contour);
+ _cairo_debug_print_contour (file, &stroker->ccw.contour);
+ fclose (file);
+ _cairo_contour_reset (&stroker->path);
+ }
+#endif
- end->point = *p2;
- end->ccw.x += p2->x - p1->x;
- end->ccw.y += p2->y - p1->y;
- end->cw.x += p2->x - p1->x;
- end->cw.y += p2->y - p1->y;
+ _cairo_polygon_add_contour (stroker->polygon, &stroker->ccw.contour);
+ _cairo_contour_reset (&stroker->ccw.contour);
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &end->cw, &start->cw);
- if (unlikely (status))
- return status;
+ if (stroker->has_first_face) {
+ _cairo_contour_add_point (&stroker->ccw.contour,
+ &stroker->first_face.cw);
+ add_leading_cap (stroker, &stroker->first_face, &stroker->ccw);
+#if DEBUG
+ {
+ FILE *file = fopen ("contours.txt", "a");
+ _cairo_debug_print_contour (file, &stroker->ccw.contour);
+ fclose (file);
+ }
+#endif
- status = _cairo_polygon_add_external_edge (stroker->polygon,
- &start->ccw, &end->ccw);
- if (unlikely (status))
- return status;
+ _cairo_polygon_add_contour (stroker->polygon,
+ &stroker->ccw.contour);
+ _cairo_contour_reset (&stroker->ccw.contour);
+ }
- return CAIRO_STATUS_SUCCESS;
+ _cairo_polygon_add_contour (stroker->polygon, &stroker->cw.contour);
+ _cairo_contour_reset (&stroker->cw.contour);
+ }
}
static cairo_status_t
+close_path (void *closure);
+
+static cairo_status_t
move_to (void *closure,
const cairo_point_t *point)
{
- cairo_stroker_t *stroker = closure;
- cairo_status_t status;
+ struct stroker *stroker = closure;
/* Cap the start and end of the previous sub path as needed */
- status = add_caps (stroker);
- if (unlikely (status))
- return status;
-
- stroker->first_point = *point;
- stroker->current_point = *point;
+ add_caps (stroker);
stroker->has_first_face = FALSE;
stroker->has_current_face = FALSE;
stroker->has_initial_sub_path = FALSE;
+ stroker->first_point = *point;
+
+#if DEBUG
+ _cairo_contour_add_point (&stroker->path, point);
+#endif
+
+ stroker->current_face.point = *point;
+
return CAIRO_STATUS_SUCCESS;
}
@@ -787,46 +1087,111 @@ static cairo_status_t
line_to (void *closure,
const cairo_point_t *point)
{
- cairo_stroker_t *stroker = closure;
- cairo_stroke_face_t start, end;
- cairo_point_t *p1 = &stroker->current_point;
+ struct stroker *stroker = closure;
+ cairo_stroke_face_t start;
+ cairo_point_t *p1 = &stroker->current_face.point;
cairo_slope_t dev_slope;
- double slope_dx, slope_dy;
- cairo_status_t status;
stroker->has_initial_sub_path = TRUE;
if (p1->x == point->x && p1->y == point->y)
return CAIRO_STATUS_SUCCESS;
+#if DEBUG
+ _cairo_contour_add_point (&stroker->path, point);
+#endif
+
_cairo_slope_init (&dev_slope, p1, point);
- slope_dx = _cairo_fixed_to_double (point->x - p1->x);
- slope_dy = _cairo_fixed_to_double (point->y - p1->y);
- compute_normalized_device_slope (&slope_dx, &slope_dy,
- stroker->ctm_inverse, NULL);
-
- status = add_sub_edge (stroker,
- p1, point,
- &dev_slope,
- slope_dx, slope_dy,
- &start, &end);
- if (unlikely (status))
- return status;
+ compute_face (p1, &dev_slope, stroker, &start);
if (stroker->has_current_face) {
+ int clockwise = join_is_clockwise (&stroker->current_face, &start);
/* Join with final face from previous segment */
- status = join (stroker, &stroker->current_face, &start);
- if (unlikely (status))
- return status;
- } else if (! stroker->has_first_face) {
- /* Save sub path's first face in case needed for closing join */
- stroker->first_face = start;
- stroker->has_first_face = TRUE;
+ if (! within_tolerance (&stroker->current_face.ccw, &start.ccw,
+ stroker->contour_tolerance) ||
+ ! within_tolerance (&stroker->current_face.cw, &start.cw,
+ stroker->contour_tolerance))
+ {
+ outer_join (stroker, &stroker->current_face, &start, clockwise);
+ inner_join (stroker, &stroker->current_face, &start, clockwise);
+ }
+ } else {
+ if (! stroker->has_first_face) {
+ /* Save sub path's first face in case needed for closing join */
+ stroker->first_face = start;
+ stroker->has_first_face = TRUE;
+ }
+ stroker->has_current_face = TRUE;
+
+ contour_add_point (stroker, &stroker->cw, &start.cw);
+ contour_add_point (stroker, &stroker->ccw, &start.ccw);
}
- stroker->current_face = end;
- stroker->has_current_face = TRUE;
- stroker->current_point = *point;
+ stroker->current_face = start;
+ stroker->current_face.point = *point;
+ stroker->current_face.ccw.x += dev_slope.dx;
+ stroker->current_face.ccw.y += dev_slope.dy;
+ stroker->current_face.cw.x += dev_slope.dx;
+ stroker->current_face.cw.y += dev_slope.dy;
+
+ contour_add_point (stroker, &stroker->cw, &stroker->current_face.cw);
+ contour_add_point (stroker, &stroker->ccw, &stroker->current_face.ccw);
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+spline_to (void *closure,
+ const cairo_point_t *point,
+ const cairo_slope_t *tangent)
+{
+ struct stroker *stroker = closure;
+ cairo_stroke_face_t face;
+
+#if DEBUG
+ _cairo_contour_add_point (&stroker->path, point);
+#endif
+ if (tangent->dx == 0 && tangent->dy == 0) {
+ const cairo_point_t *inpt, *outpt;
+ struct stroke_contour *outer;
+ cairo_point_t t;
+ int clockwise;
+
+ face = stroker->current_face;
+
+ face.usr_vector.x = -face.usr_vector.x;
+ face.usr_vector.y = -face.usr_vector.y;
+ face.dev_vector.dx = -face.dev_vector.dx;
+ face.dev_vector.dy = -face.dev_vector.dy;
+
+ t = face.cw;
+ face.cw = face.ccw;
+ face.ccw = t;
+
+ clockwise = join_is_clockwise (&stroker->current_face, &face);
+ if (clockwise) {
+ inpt = &stroker->current_face.cw;
+ outpt = &face.cw;
+ outer = &stroker->cw;
+ } else {
+ inpt = &stroker->current_face.ccw;
+ outpt = &face.ccw;
+ outer = &stroker->ccw;
+ }
+
+ add_fan (stroker,
+ &stroker->current_face.dev_vector,
+ &face.dev_vector,
+ &stroker->current_face.point, inpt, outpt,
+ clockwise, outer);
+ } else {
+ compute_face (point, tangent, stroker, &face);
+
+ contour_add_point (stroker, &stroker->cw, &face.cw);
+ contour_add_point (stroker, &stroker->ccw, &face.ccw);
+ }
+
+ stroker->current_face = face;
return CAIRO_STATUS_SUCCESS;
}
@@ -837,82 +1202,42 @@ curve_to (void *closure,
const cairo_point_t *c,
const cairo_point_t *d)
{
- cairo_stroker_t *stroker = closure;
+ struct stroker *stroker = closure;
cairo_spline_t spline;
- cairo_line_join_t line_join_save;
cairo_stroke_face_t face;
- double slope_dx, slope_dy;
- cairo_status_t status = CAIRO_STATUS_SUCCESS;
- if (! _cairo_spline_init (&spline, line_to, stroker,
- &stroker->current_point, b, c, d))
- {
+ if (! _cairo_spline_init (&spline, spline_to, stroker,
+ &stroker->current_face.point, b, c, d))
return line_to (closure, d);
- }
- /* Compute the initial face */
- if (1) {
- slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
- slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
- if (compute_normalized_device_slope (&slope_dx, &slope_dy,
- stroker->ctm_inverse, NULL))
- {
- compute_face (&stroker->current_point,
- &spline.initial_slope,
- slope_dx, slope_dy,
- stroker, &face);
- }
- if (stroker->has_current_face) {
- status = join (stroker, &stroker->current_face, &face);
- if (unlikely (status))
- return status;
- } else if (! stroker->has_first_face) {
+ compute_face (&stroker->current_face.point, &spline.initial_slope,
+ stroker, &face);
+
+ if (stroker->has_current_face) {
+ int clockwise = join_is_clockwise (&stroker->current_face, &face);
+ /* Join with final face from previous segment */
+ outer_join (stroker, &stroker->current_face, &face, clockwise);
+ inner_join (stroker, &stroker->current_face, &face, clockwise);
+ } else {
+ if (! stroker->has_first_face) {
+ /* Save sub path's first face in case needed for closing join */
stroker->first_face = face;
stroker->has_first_face = TRUE;
}
-
- stroker->current_face = face;
stroker->has_current_face = TRUE;
- }
-
- /* Temporarily modify the stroker to use round joins to guarantee
- * smooth stroked curves. */
- line_join_save = stroker->style.line_join;
- stroker->style.line_join = CAIRO_LINE_JOIN_ROUND;
-
- status = _cairo_spline_decompose (&spline, stroker->tolerance);
- if (unlikely (status))
- return status;
-
- /* And join the final face */
- if (1) {
- slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
- slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
- if (compute_normalized_device_slope (&slope_dx, &slope_dy,
- stroker->ctm_inverse, NULL))
- {
- compute_face (&stroker->current_point,
- &spline.final_slope,
- slope_dx, slope_dy,
- stroker, &face);
- }
- status = join (stroker, &stroker->current_face, &face);
- if (unlikely (status))
- return status;
-
- stroker->current_face = face;
+ contour_add_point (stroker, &stroker->cw, &face.cw);
+ contour_add_point (stroker, &stroker->ccw, &face.ccw);
}
+ stroker->current_face = face;
- stroker->style.line_join = line_join_save;
-
- return CAIRO_STATUS_SUCCESS;
+ return _cairo_spline_decompose (&spline, stroker->tolerance);
}
static cairo_status_t
close_path (void *closure)
{
- cairo_stroker_t *stroker = closure;
+ struct stroker *stroker = closure;
cairo_status_t status;
status = line_to (stroker, &stroker->first_point);
@@ -921,14 +1246,35 @@ close_path (void *closure)
if (stroker->has_first_face && stroker->has_current_face) {
/* Join first and final faces of sub path */
- status = join (stroker, &stroker->current_face, &stroker->first_face);
- if (unlikely (status))
- return status;
+ outer_close (stroker, &stroker->current_face, &stroker->first_face);
+ inner_close (stroker, &stroker->current_face, &stroker->first_face);
+#if 0
+ *_cairo_contour_first_point (&stroker->ccw.contour) =
+ *_cairo_contour_last_point (&stroker->ccw.contour);
+
+ *_cairo_contour_first_point (&stroker->cw.contour) =
+ *_cairo_contour_last_point (&stroker->cw.contour);
+#endif
+
+ _cairo_polygon_add_contour (stroker->polygon, &stroker->cw.contour);
+ _cairo_polygon_add_contour (stroker->polygon, &stroker->ccw.contour);
+
+#if DEBUG
+ {
+ FILE *file = fopen ("contours.txt", "a");
+ _cairo_debug_print_contour (file, &stroker->path);
+ _cairo_debug_print_contour (file, &stroker->cw.contour);
+ _cairo_debug_print_contour (file, &stroker->ccw.contour);
+ fclose (file);
+
+ _cairo_contour_reset (&stroker->path);
+ }
+#endif
+ _cairo_contour_reset (&stroker->cw.contour);
+ _cairo_contour_reset (&stroker->ccw.contour);
} else {
/* Cap the start and end of the sub path as needed */
- status = add_caps (stroker);
- if (unlikely (status))
- return status;
+ add_caps (stroker);
}
stroker->has_initial_sub_path = FALSE;
@@ -946,23 +1292,25 @@ _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t *path,
double tolerance,
cairo_polygon_t *polygon)
{
- cairo_stroker_t stroker;
+ struct stroker stroker;
cairo_status_t status;
- if (style->dash)
+ if (style->num_dashes) {
return _cairo_path_fixed_stroke_dashed_to_polygon (path,
style,
ctm,
ctm_inverse,
tolerance,
polygon);
+ }
stroker.style = *style;
stroker.ctm = ctm;
stroker.ctm_inverse = ctm_inverse;
stroker.tolerance = tolerance;
- stroker.ctm_det_positive = _cairo_matrix_compute_determinant (ctm) >= 0.;
+ stroker.ctm_det_positive =
+ _cairo_matrix_compute_determinant (ctm) >= 0.0;
status = _cairo_pen_init (&stroker.pen,
style->line_width / 2.0,
@@ -975,15 +1323,19 @@ _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t *path,
if (stroker.pen.num_vertices <= 1)
return CAIRO_STATUS_SUCCESS;
- stroker.polygon = polygon;
-
stroker.has_current_face = FALSE;
stroker.has_first_face = FALSE;
stroker.has_initial_sub_path = FALSE;
- stroker.has_bounds = FALSE;
- if (polygon->num_limits)
- stroker_limit (&stroker, polygon->limits, polygon->num_limits);
+#if DEBUG
+ _cairo_contour_init (&stroker.path, 0);
+#endif
+ _cairo_contour_init (&stroker.cw.contour, 1);
+ _cairo_contour_init (&stroker.ccw.contour, -1);
+ tolerance *= CAIRO_FIXED_ONE;
+ tolerance *= tolerance;
+ stroker.contour_tolerance = tolerance;
+ stroker.polygon = polygon;
status = _cairo_path_fixed_interpret (path,
move_to,
@@ -991,12 +1343,21 @@ _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t *path,
curve_to,
close_path,
&stroker);
-
/* Cap the start and end of the final sub path as needed */
if (likely (status == CAIRO_STATUS_SUCCESS))
- status = add_caps (&stroker);
+ add_caps (&stroker);
+ _cairo_contour_fini (&stroker.cw.contour);
+ _cairo_contour_fini (&stroker.ccw.contour);
_cairo_pen_fini (&stroker.pen);
+#if DEBUG
+ {
+ FILE *file = fopen ("polygons.txt", "a");
+ _cairo_debug_print_polygon (file, polygon);
+ fclose (file);
+ }
+#endif
+
return status;
}
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 819708e..c438291 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -1118,7 +1118,7 @@ _cairo_stroker_curve_to (void *closure,
_cairo_stroker_line_to;
if (! _cairo_spline_init (&spline,
- line_to, stroker,
+ (cairo_spline_add_point_func_t)line_to, stroker,
&stroker->current_point, b, c, d))
{
return line_to (closure, d);
diff --git a/src/cairo-polygon.c b/src/cairo-polygon.c
index 74ec9fa..6436712 100644
--- a/src/cairo-polygon.c
+++ b/src/cairo-polygon.c
@@ -38,12 +38,14 @@
#include "cairoint.h"
#include "cairo-boxes-private.h"
+#include "cairo-contour-private.h"
#include "cairo-error-private.h"
static void
_cairo_polygon_add_edge (cairo_polygon_t *polygon,
const cairo_point_t *p1,
- const cairo_point_t *p2);
+ const cairo_point_t *p2,
+ int dir);
void
_cairo_polygon_init (cairo_polygon_t *polygon,
@@ -131,12 +133,12 @@ _cairo_polygon_init_boxes (cairo_polygon_t *polygon,
p1 = chunk->base[i].p1;
p2.x = p1.x;
p2.y = chunk->base[i].p2.y;
- _cairo_polygon_add_edge (polygon, &p1, &p2);
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
p1 = chunk->base[i].p2;
p2.x = p1.x;
p2.y = chunk->base[i].p1.y;
- _cairo_polygon_add_edge (polygon, &p1, &p2);
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
}
}
@@ -178,12 +180,12 @@ _cairo_polygon_init_box_array (cairo_polygon_t *polygon,
p1 = boxes[i].p1;
p2.x = p1.x;
p2.y = boxes[i].p2.y;
- _cairo_polygon_add_edge (polygon, &p1, &p2);
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
p1 = boxes[i].p2;
p2.x = p1.x;
p2.y = boxes[i].p1.y;
- _cairo_polygon_add_edge (polygon, &p1, &p2);
+ _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
}
return polygon->status;
@@ -406,20 +408,17 @@ _add_clipped_edge (cairo_polygon_t *polygon,
static void
_cairo_polygon_add_edge (cairo_polygon_t *polygon,
const cairo_point_t *p1,
- const cairo_point_t *p2)
+ const cairo_point_t *p2,
+ int dir)
{
- int dir;
-
/* drop horizontal edges */
if (p1->y == p2->y)
return;
- if (p1->y < p2->y) {
- dir = 1;
- } else {
+ if (p1->y > p2->y) {
const cairo_point_t *t;
t = p1, p1 = p2, p2 = t;
- dir = -1;
+ dir = -dir;
}
if (polygon->num_limits) {
@@ -439,7 +438,7 @@ _cairo_polygon_add_external_edge (void *polygon,
const cairo_point_t *p1,
const cairo_point_t *p2)
{
- _cairo_polygon_add_edge (polygon, p1, p2);
+ _cairo_polygon_add_edge (polygon, p1, p2, 1);
return _cairo_polygon_status (polygon);
}
@@ -469,3 +468,26 @@ _cairo_polygon_add_line (cairo_polygon_t *polygon,
return polygon->status;
}
+
+cairo_status_t
+_cairo_polygon_add_contour (cairo_polygon_t *polygon,
+ const cairo_contour_t *contour)
+{
+ const struct _cairo_contour_chain *chain;
+ const cairo_point_t *prev = NULL;
+ int i;
+
+ if (contour->chain.num_points <= 1)
+ return CAIRO_INT_STATUS_SUCCESS;
+
+ prev = &contour->chain.points[0];
+ for (chain = &contour->chain; chain; chain = chain->next) {
+ for (i = 0; i < chain->num_points; i++) {
+ _cairo_polygon_add_edge (polygon, prev, &chain->points[i],
+ contour->direction);
+ prev = &chain->points[i];
+ }
+ }
+
+ return polygon->status;
+}
diff --git a/src/cairo-spline.c b/src/cairo-spline.c
index 016ecee..2467178 100644
--- a/src/cairo-spline.c
+++ b/src/cairo-spline.c
@@ -67,22 +67,27 @@ _cairo_spline_init (cairo_spline_t *spline,
else if (b->x != d->x || b->y != d->y)
_cairo_slope_init (&spline->final_slope, &spline->knots.b, &spline->knots.d);
else
- _cairo_slope_init (&spline->final_slope, &spline->knots.a, &spline->knots.d);
+ return FALSE; /* just treat this as a straight-line from a -> d */
return TRUE;
}
static cairo_status_t
-_cairo_spline_add_point (cairo_spline_t *spline, cairo_point_t *point)
+_cairo_spline_add_point (cairo_spline_t *spline,
+ const cairo_point_t *point,
+ const cairo_point_t *knot)
{
cairo_point_t *prev;
+ cairo_slope_t slope;
prev = &spline->last_point;
if (prev->x == point->x && prev->y == point->y)
return CAIRO_STATUS_SUCCESS;
+ _cairo_slope_init (&slope, point, knot);
+
spline->last_point = *point;
- return spline->add_point_func (spline->closure, point);
+ return spline->add_point_func (spline->closure, point, &slope);
}
static void
@@ -184,13 +189,15 @@ _cairo_spline_error_squared (const cairo_spline_knots_t *knots)
}
static cairo_status_t
-_cairo_spline_decompose_into (cairo_spline_knots_t *s1, double tolerance_squared, cairo_spline_t *result)
+_cairo_spline_decompose_into (cairo_spline_knots_t *s1,
+ double tolerance_squared,
+ cairo_spline_t *result)
{
cairo_spline_knots_t s2;
cairo_status_t status;
if (_cairo_spline_error_squared (s1) < tolerance_squared)
- return _cairo_spline_add_point (result, &s1->a);
+ return _cairo_spline_add_point (result, &s1->a, &s1->b);
_de_casteljau (s1, &s2);
@@ -206,6 +213,7 @@ _cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
{
cairo_spline_knots_t s1;
cairo_status_t status;
+ cairo_slope_t slope;
s1 = spline->knots;
spline->last_point = s1.a;
@@ -213,7 +221,8 @@ _cairo_spline_decompose (cairo_spline_t *spline, double tolerance)
if (unlikely (status))
return status;
- return _cairo_spline_add_point (spline, &spline->knots.d);
+ _cairo_slope_init (&slope, &spline->knots.c, &spline->knots.d);
+ return spline->add_point_func (spline->closure, &spline->knots.d, &slope);
}
/* Note: this function is only good for computing bounds in device space. */
@@ -325,7 +334,7 @@ _cairo_spline_bound (cairo_spline_add_point_func_t add_point_func,
c = -y0 + y1;
FIND_EXTREMES (a, b, c);
- status = add_point_func (closure, p0);
+ status = add_point_func (closure, p0, NULL);
if (unlikely (status))
return status;
@@ -359,10 +368,10 @@ _cairo_spline_bound (cairo_spline_add_point_func_t add_point_func,
p.x = _cairo_fixed_from_double (x);
p.y = _cairo_fixed_from_double (y);
- status = add_point_func (closure, &p);
+ status = add_point_func (closure, &p, NULL);
if (unlikely (status))
return status;
}
- return add_point_func (closure, p3);
+ return add_point_func (closure, p3, NULL);
}
diff --git a/src/cairo-types-private.h b/src/cairo-types-private.h
index 0b57ec2..966cd8f 100644
--- a/src/cairo-types-private.h
+++ b/src/cairo-types-private.h
@@ -63,6 +63,9 @@ typedef struct _cairo_clip cairo_clip_t;
typedef struct _cairo_clip_path cairo_clip_path_t;
typedef struct _cairo_color cairo_color_t;
typedef struct _cairo_color_stop cairo_color_stop_t;
+typedef struct _cairo_contour cairo_contour_t;
+typedef struct _cairo_contour_chain cairo_contour_chain_t;
+typedef struct _cairo_contour_iter cairo_contour_iter_t;
typedef struct _cairo_device_backend cairo_device_backend_t;
typedef struct _cairo_font_face_backend cairo_font_face_backend_t;
typedef struct _cairo_gstate cairo_gstate_t;
@@ -312,7 +315,8 @@ typedef struct _cairo_polygon {
typedef cairo_warn cairo_status_t
(*cairo_spline_add_point_func_t) (void *closure,
- const cairo_point_t *point);
+ const cairo_point_t *point,
+ const cairo_slope_t *tangent);
typedef struct _cairo_spline_knots {
cairo_point_t a, b, c, d;
diff --git a/src/cairoint.h b/src/cairoint.h
index e294df3..51beec2 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1030,7 +1030,9 @@ typedef struct _cairo_stroke_face {
cairo_point_t point;
cairo_point_t cw;
cairo_slope_t dev_vector;
+ cairo_point_double_t dev_slope;
cairo_point_double_t usr_vector;
+ double length;
} cairo_stroke_face_t;
/* cairo.c */
@@ -2070,6 +2072,10 @@ _cairo_polygon_add_external_edge (void *polygon,
const cairo_point_t *p2);
cairo_private cairo_status_t
+_cairo_polygon_add_contour (cairo_polygon_t *polygon,
+ const cairo_contour_t *contour);
+
+cairo_private cairo_status_t
_cairo_polygon_reduce (cairo_polygon_t *polygon,
cairo_fill_rule_t fill_rule);
diff --git a/util/.gitignore b/util/.gitignore
index ff7ffbd..9a28da1 100644
--- a/util/.gitignore
+++ b/util/.gitignore
@@ -2,8 +2,10 @@
.libs
Makefile
Makefile.in
+show-contour
show-edges
show-events
+show-polygon
show-traps
xml-to-trace
trace-to-xml
diff --git a/util/Makefile.am b/util/Makefile.am
index f3aa079..6c6c849 100644
--- a/util/Makefile.am
+++ b/util/Makefile.am
@@ -32,7 +32,7 @@ AM_CPPFLAGS = -I$(top_srcdir)/src \
-I$(top_srcdir)/util/cairo-script \
$(CAIRO_CFLAGS)
-EXTRA_PROGRAMS += show-traps show-edges show-polygon show-events
+EXTRA_PROGRAMS += show-contour show-traps show-edges show-polygon show-events
if CAIRO_HAS_INTERPRETER
EXTRA_PROGRAMS += trace-to-xml xml-to-trace
endif
@@ -56,6 +56,11 @@ show_edges_CFLAGS = $(gtk_CFLAGS)
#show_edges_LDADD = $(top_builddir)/src/libcairo.la $(gtk_LIBS)
show_edges_LDADD = $(gtk_LIBS)
+show_contour_SOURCES = show-contour.c
+show_contour_CFLAGS = $(gtk_CFLAGS)
+#show_contour_LDADD = $(top_builddir)/src/libcairo.la $(gtk_LIBS)
+show_contour_LDADD = $(gtk_LIBS)
+
show_events_SOURCES = show-events.c
show_events_CFLAGS = $(gtk_CFLAGS)
#show_events_LDADD = $(top_builddir)/src/libcairo.la $(gtk_LIBS)
diff --git a/util/show-contour.c b/util/show-contour.c
new file mode 100644
index 0000000..f3fa1ba
--- /dev/null
+++ b/util/show-contour.c
@@ -0,0 +1,667 @@
+#define _GNU_SOURCE
+#include <gtk/gtk.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <gdk/gdkkeysyms.h>
+#include <math.h>
+
+typedef struct _point {
+ gdouble x, y;
+} point_t;
+typedef struct _box {
+ point_t p1, p2;
+} box_t;
+
+typedef struct _contour {
+ struct _contour *next, *prev;
+ int direction;
+ int num_points;
+ int size;
+ point_t points[0];
+} contour_t;
+
+typedef struct _TrapView {
+ GtkWidget widget;
+
+ cairo_surface_t *pixmap;
+ int pixmap_width, pixmap_height;
+
+ box_t extents;
+ contour_t *contours;
+
+ double px, py;
+
+ gint mag_x, mag_y;
+ gint mag_size;
+ gdouble mag_zoom;
+ gboolean in_mag_drag;
+ gint mag_drag_x, mag_drag_y;
+} TrapView;
+
+typedef struct _TrapViewClass {
+ GtkWidgetClass parent_class;
+} TrapViewClass;
+
+G_DEFINE_TYPE (TrapView, trap_view, GTK_TYPE_WIDGET)
+
+static cairo_surface_t *
+pixmap_create (TrapView *self, cairo_surface_t *target)
+{
+ cairo_surface_t *surface =
+ cairo_surface_create_similar (target, CAIRO_CONTENT_COLOR,
+ self->widget.allocation.width,
+ self->widget.allocation.height);
+ cairo_t *cr = cairo_create (surface);
+ contour_t *contour;
+ gdouble sf_x, sf_y, sf;
+ gdouble mid, dim;
+ gdouble x0, y0;
+ int n;
+ box_t extents;
+
+ cairo_set_source_rgb (cr, 1, 1, 1);
+ cairo_paint (cr);
+
+ if (self->contours == NULL) {
+ cairo_destroy(cr);
+ return surface;
+ }
+
+ extents = self->extents;
+
+ mid = (extents.p2.x + extents.p1.x) / 2.;
+ dim = (extents.p2.x - extents.p1.x) / 2. * 1.25;
+ sf_x = self->widget.allocation.width / dim / 2;
+
+ mid = (extents.p2.y + extents.p1.y) / 2.;
+ dim = (extents.p2.y - extents.p1.y) / 2. * 1.25;
+ sf_y = self->widget.allocation.height / dim / 2;
+
+ sf = MIN (sf_x, sf_y);
+
+ mid = (extents.p2.x + extents.p1.x) / 2.;
+ dim = sf_x / sf * (extents.p2.x - extents.p1.x) / 2. * 1.25;
+ x0 = mid - dim;
+ mid = (extents.p2.y + extents.p1.y) / 2.;
+ dim = sf_y / sf * (extents.p2.y - extents.p1.y) / 2. * 1.25;
+ y0 = mid - dim;
+
+ for (contour = self->contours; contour; contour = contour->next) {
+ if (contour->num_points == 0)
+ continue;
+
+ cairo_save (cr); {
+ cairo_scale (cr, sf, sf);
+ cairo_translate (cr, -x0, -y0);
+ switch (contour->direction) {
+ case -1:
+ cairo_set_source_rgb (cr, 0.0, 0.0, 1.0);
+ break;
+ case 0:
+ cairo_set_source_rgb (cr, 0.0, 1.0, 0.0);
+ break;
+ case 1:
+ cairo_set_source_rgb (cr, 1.0, 0.0, 0.0);
+ break;
+ }
+ {
+ const point_t *p = &contour->points[0];
+ cairo_arc (cr, p->x, p->y, 4/sf, 0, 2 * M_PI);
+ cairo_save (cr);
+ cairo_identity_matrix (cr);
+ cairo_stroke (cr);
+ cairo_restore (cr);
+ }
+ for (n = 0; n < contour->num_points; n++) {
+ const point_t *p = &contour->points[n];
+ cairo_arc (cr, p->x, p->y, 2/sf, 0, 2 * M_PI);
+ cairo_fill (cr);
+ }
+ for (n = 0; n < contour->num_points; n++) {
+ const point_t *p = &contour->points[n];
+ cairo_line_to (cr, p->x, p->y);
+ }
+ } cairo_restore (cr);
+
+ switch (contour->direction) {
+ case -1:
+ cairo_set_source_rgb (cr, 0.3, 0.3, 0.9);
+ break;
+ case 0:
+ cairo_set_source_rgb (cr, 0.3, 0.9, 0.3);
+ break;
+ case 1:
+ cairo_set_source_rgb (cr, 0.9, 0.3, 0.3);
+ break;
+ }
+ cairo_set_line_width (cr, 1.);
+ cairo_stroke (cr);
+ }
+
+ cairo_destroy (cr);
+ return surface;
+}
+
+static void
+trap_view_draw (TrapView *self, cairo_t *cr)
+{
+ contour_t *contour;
+ gdouble sf_x, sf_y, sf;
+ gdouble mid, dim;
+ gdouble x0, y0;
+ int n;
+ box_t extents;
+
+ extents = self->extents;
+
+ mid = (extents.p2.x + extents.p1.x) / 2.;
+ dim = (extents.p2.x - extents.p1.x) / 2. * 1.25;
+ sf_x = self->widget.allocation.width / dim / 2;
+
+ mid = (extents.p2.y + extents.p1.y) / 2.;
+ dim = (extents.p2.y - extents.p1.y) / 2. * 1.25;
+ sf_y = self->widget.allocation.height / dim / 2;
+
+ sf = MIN (sf_x, sf_y);
+
+ mid = (extents.p2.x + extents.p1.x) / 2.;
+ dim = sf_x / sf * (extents.p2.x - extents.p1.x) / 2. * 1.25;
+ x0 = mid - dim;
+ mid = (extents.p2.y + extents.p1.y) / 2.;
+ dim = sf_y / sf * (extents.p2.y - extents.p1.y) / 2. * 1.25;
+ y0 = mid - dim;
+
+ if (self->pixmap_width != self->widget.allocation.width ||
+ self->pixmap_height != self->widget.allocation.height)
+ {
+ cairo_surface_destroy (self->pixmap);
+ self->pixmap = pixmap_create (self, cairo_get_target (cr));
+ self->pixmap_width = self->widget.allocation.width;
+ self->pixmap_height = self->widget.allocation.height;
+ }
+
+ cairo_set_source_surface (cr, self->pixmap, 0, 0);
+ cairo_paint (cr);
+
+ if (self->contours == NULL)
+ return;
+
+ /* draw a zoom view of the area around the mouse */
+ if (1) {
+ double zoom = self->mag_zoom;
+ int size = self->mag_size;
+ int mag_x = self->mag_x;
+ int mag_y = self->mag_y;
+
+ if (1) {
+ if (self->px + size < self->widget.allocation.width/2)
+ mag_x = self->px + size/4;
+ else
+ mag_x = self->px - size/4 - size;
+ mag_y = self->py - size/2;
+ if (mag_y < 0)
+ mag_y = 0;
+ if (mag_y + size > self->widget.allocation.height)
+ mag_y = self->widget.allocation.height - size;
+ }
+
+ cairo_save (cr); {
+ /* bottom right */
+ cairo_rectangle (cr, mag_x, mag_y, size, size);
+ cairo_stroke_preserve (cr);
+ cairo_set_source_rgb (cr, 1, 1, 1);
+ cairo_fill_preserve (cr);
+ cairo_clip (cr);
+
+ /* compute roi in extents */
+ cairo_translate (cr, mag_x + size/2, mag_y + size/2);
+
+ cairo_save (cr); {
+ for (contour = self->contours; contour; contour = contour->next) {
+ if (contour->num_points == 0)
+ continue;
+
+ cairo_save (cr); {
+ cairo_scale (cr, zoom, zoom);
+ cairo_translate (cr, -(self->px / sf + x0), -(self->py /sf + y0));
+ switch (contour->direction) {
+ case -1:
+ cairo_set_source_rgb (cr, 0.0, 0.0, 1.0);
+ break;
+ case 0:
+ cairo_set_source_rgb (cr, 0.0, 1.0, 0.0);
+ break;
+ case 1:
+ cairo_set_source_rgb (cr, 1.0, 0.0, 0.0);
+ break;
+ }
+ {
+ const point_t *p = &contour->points[0];
+ cairo_arc (cr, p->x, p->y, 4/zoom, 0, 2 * M_PI);
+ cairo_save (cr);
+ cairo_identity_matrix (cr);
+ cairo_stroke (cr);
+ cairo_restore (cr);
+ }
+ for (n = 0; n < contour->num_points; n++) {
+ const point_t *p = &contour->points[n];
+ cairo_arc (cr, p->x, p->y, 2/zoom, 0, 2 * M_PI);
+ cairo_fill (cr);
+ }
+ for (n = 0; n < contour->num_points; n++) {
+ const point_t *p = &contour->points[n];
+ cairo_line_to (cr, p->x, p->y);
+ }
+ } cairo_restore (cr);
+
+ switch (contour->direction) {
+ case -1:
+ cairo_set_source_rgb (cr, 0.3, 0.3, 0.9);
+ break;
+ case 0:
+ cairo_set_source_rgb (cr, 0.3, 0.9, 0.3);
+ break;
+ case 1:
+ cairo_set_source_rgb (cr, 0.9, 0.3, 0.3);
+ break;
+ }
+ cairo_stroke (cr);
+ }
+ } cairo_restore (cr);
+
+ /* grid */
+ cairo_save (cr); {
+ int i;
+
+ cairo_translate (cr,
+ -zoom*fmod (self->px/sf + x0, 1.),
+ -zoom*fmod (self->py/sf + y0, 1.));
+ zoom /= 2;
+ for (i = -size/2/zoom; i <= size/2/zoom + 1; i+=2) {
+ cairo_move_to (cr, zoom*i, -size/2);
+ cairo_line_to (cr, zoom*i, size/2 + zoom);
+ cairo_move_to (cr, -size/2, zoom*i);
+ cairo_line_to (cr, size/2 + zoom, zoom*i);
+ }
+ zoom *= 2;
+ cairo_set_source_rgba (cr, .7, .7, .7, .5);
+ cairo_set_line_width (cr, 1.);
+ cairo_stroke (cr);
+
+ for (i = -size/2/zoom - 1; i <= size/2/zoom + 1; i++) {
+ cairo_move_to (cr, zoom*i, -size/2);
+ cairo_line_to (cr, zoom*i, size/2 + zoom);
+ cairo_move_to (cr, -size/2, zoom*i);
+ cairo_line_to (cr, size/2 + zoom, zoom*i);
+ }
+ cairo_set_source_rgba (cr, .1, .1, .1, .5);
+ cairo_set_line_width (cr, 2.);
+ cairo_stroke (cr);
+ } cairo_restore (cr);
+
+ } cairo_restore (cr);
+ }
+}
+
+
+static gdouble
+edge_length (const point_t *p1, const point_t *p2)
+{
+ return hypot (p2->x - p1->x, p2->y - p1->y);
+}
+
+static gdouble
+contour_compute_total_length (const contour_t *contour)
+{
+ int n;
+ gdouble len = 0.;
+ for (n = 1; n < contour->num_points; n++)
+ len += edge_length (&contour->points[n-1], &contour->points[n]);
+ return len;
+}
+
+static void
+trap_view_draw_labels (TrapView *self, cairo_t *cr)
+{
+ contour_t *contour;
+ int y = 12;
+
+ for (contour = self->contours; contour; contour = contour->next) {
+ double total_length = contour_compute_total_length (contour) / 256.;
+ PangoLayout *layout;
+ gint width, height;
+ GString *string;
+ gchar *str;
+
+ if (contour->num_points == 0)
+ continue;
+
+ string = g_string_new (NULL);
+ g_string_append_printf (string,
+ "Number of points:\t%d\n"
+ "Total length of contour: \t%.2f",
+ contour->num_points,
+ total_length);
+
+ str = g_string_free (string, FALSE);
+ layout = gtk_widget_create_pango_layout (&self->widget, str);
+ g_free (str);
+
+ pango_layout_get_pixel_size (layout, &width, &height);
+
+ switch (contour->direction) {
+ case -1:
+ cairo_set_source_rgb (cr, 0.9, 0.3, 0.3);
+ break;
+ case 0:
+ cairo_set_source_rgb (cr, 0.3, 0.9, 0.3);
+ break;
+ case 1:
+ cairo_set_source_rgb (cr, 0.3, 0.3, 0.9);
+ break;
+ }
+
+ cairo_move_to (cr, 10, y);
+ pango_cairo_show_layout (cr, layout);
+ g_object_unref (layout);
+
+ y += height + 4;
+ }
+}
+
+static gboolean
+trap_view_expose (GtkWidget *w, GdkEventExpose *ev)
+{
+ TrapView *self = (TrapView *) w;
+ cairo_t *cr;
+
+ cr = gdk_cairo_create (w->window);
+ gdk_cairo_region (cr, ev->region);
+ cairo_clip (cr);
+
+ trap_view_draw (self, cr);
+ trap_view_draw_labels (self, cr);
+
+ cairo_destroy (cr);
+ return FALSE;
+}
+
+static gboolean
+trap_view_key_press (GtkWidget *w, GdkEventKey *ev)
+{
+ switch (ev->keyval) {
+ case GDK_Escape:
+ case GDK_Q:
+ gtk_main_quit ();
+ break;
+ }
+
+ return FALSE;
+}
+
+static gboolean
+trap_view_button_press (GtkWidget *w, GdkEventButton *ev)
+{
+ TrapView *self = (TrapView *) w;
+
+ if (ev->x < self->mag_x ||
+ ev->y < self->mag_y ||
+ ev->x > self->mag_x + self->mag_size ||
+ ev->y > self->mag_y + self->mag_size)
+ {
+ }
+ else
+ {
+ self->in_mag_drag = TRUE;
+ self->mag_drag_x = ev->x;
+ self->mag_drag_y = ev->y;
+ }
+
+ return FALSE;
+}
+
+static gboolean
+trap_view_button_release (GtkWidget *w, GdkEventButton *ev)
+{
+ TrapView *self = (TrapView *) w;
+
+ self->in_mag_drag = FALSE;
+
+ return FALSE;
+}
+
+static void
+trap_view_update_mouse (TrapView *self, GdkEventMotion *ev)
+{
+ self->px = ev->x;
+ self->py = ev->y;
+
+ gtk_widget_queue_draw (&self->widget);
+}
+
+static void
+trap_view_update_magnifier (TrapView *self, gint *xy)
+{
+ self->mag_x = xy[0];
+ self->mag_y = xy[1];
+
+ gtk_widget_queue_draw (&self->widget);
+}
+
+static gboolean
+trap_view_motion (GtkWidget *w, GdkEventMotion *ev)
+{
+ TrapView *self = (TrapView *) w;
+
+ if (self->in_mag_drag) {
+ int xy[2];
+
+ xy[0] = self->mag_x + ev->x - self->mag_drag_x;
+ xy[1] = self->mag_y + ev->y - self->mag_drag_y;
+
+ trap_view_update_magnifier (self, xy);
+
+ self->mag_drag_x = ev->x;
+ self->mag_drag_y = ev->y;
+ } else if (ev->x < self->mag_x ||
+ ev->y < self->mag_y ||
+ ev->x > self->mag_x + self->mag_size ||
+ ev->y > self->mag_y + self->mag_size)
+ {
+ trap_view_update_mouse (self, ev);
+ }
+
+ return FALSE;
+}
+
+static void
+trap_view_realize (GtkWidget *widget)
+{
+ GdkWindowAttr attributes;
+
+ GTK_WIDGET_SET_FLAGS (widget, GTK_REALIZED);
+
+ attributes.window_type = GDK_WINDOW_CHILD;
+ attributes.x = widget->allocation.x;
+ attributes.y = widget->allocation.y;
+ attributes.width = widget->allocation.width;
+ attributes.height = widget->allocation.height;
+ attributes.wclass = GDK_INPUT_OUTPUT;
+ attributes.visual = gtk_widget_get_visual (widget);
+ attributes.colormap = gtk_widget_get_colormap (widget);
+ attributes.event_mask = gtk_widget_get_events (widget) |
+ GDK_BUTTON_PRESS_MASK |
+ GDK_BUTTON_RELEASE_MASK |
+ GDK_KEY_PRESS_MASK |
+ GDK_KEY_RELEASE_MASK |
+ GDK_POINTER_MOTION_MASK |
+ GDK_BUTTON_MOTION_MASK |
+ GDK_EXPOSURE_MASK;
+
+ widget->window = gdk_window_new (gtk_widget_get_parent_window (widget),
+ &attributes,
+ GDK_WA_X | GDK_WA_Y |
+ GDK_WA_VISUAL | GDK_WA_COLORMAP);
+ gdk_window_set_user_data (widget->window, widget);
+
+ widget->style = gtk_style_attach (widget->style, widget->window);
+ gtk_style_set_background (widget->style, widget->window, GTK_STATE_NORMAL);
+}
+
+static void
+trap_view_size_allocate (GtkWidget *w, GdkRectangle *r)
+{
+ TrapView *self = (TrapView *) w;
+
+ GTK_WIDGET_CLASS (trap_view_parent_class)->size_allocate (w, r);
+
+ self->mag_x = w->allocation.width - self->mag_size - 10;
+ self->mag_y = w->allocation.height - self->mag_size - 10;
+}
+
+static void
+trap_view_finalize (GObject *obj)
+{
+ G_OBJECT_CLASS (trap_view_parent_class)->finalize (obj);
+}
+
+static void
+trap_view_class_init (TrapViewClass *klass)
+{
+ GObjectClass *object_class = (GObjectClass *) klass;
+ GtkWidgetClass *widget_class = (GtkWidgetClass *) klass;
+
+ object_class->finalize = trap_view_finalize;
+
+ widget_class->realize = trap_view_realize;
+ widget_class->size_allocate = trap_view_size_allocate;
+ widget_class->expose_event = trap_view_expose;
+ widget_class->key_press_event = trap_view_key_press;
+ widget_class->button_press_event = trap_view_button_press;
+ widget_class->button_release_event = trap_view_button_release;
+ widget_class->motion_notify_event = trap_view_motion;
+}
+
+static void
+trap_view_init (TrapView *self)
+{
+ self->mag_zoom = 64;
+ self->mag_size = 200;
+
+ self->extents.p1.x = G_MAXDOUBLE;
+ self->extents.p1.y = G_MAXDOUBLE;
+ self->extents.p2.x = -G_MAXDOUBLE;
+ self->extents.p2.y = -G_MAXDOUBLE;
+
+ GTK_WIDGET_SET_FLAGS (self, GTK_CAN_FOCUS);
+}
+
+static contour_t *
+_contour_add_point (TrapView *tv, contour_t *contour, point_t *p)
+{
+ if (contour == NULL)
+ return NULL;
+
+ if (p->y < tv->extents.p1.y)
+ tv->extents.p1.y = p->y;
+ if (p->y > tv->extents.p2.y)
+ tv->extents.p2.y = p->y;
+
+ if (p->x < tv->extents.p1.x)
+ tv->extents.p1.x = p->x;
+ if (p->x > tv->extents.p2.x)
+ tv->extents.p2.x = p->x;
+
+ if (contour->num_points == contour->size) {
+ int newsize = 2 * contour->size;
+ void *newcontour;
+
+ newcontour = g_realloc (contour,
+ sizeof (contour_t) + newsize * sizeof (point_t));
+ if (newcontour == NULL)
+ return contour;
+
+ contour = newcontour;
+ contour->size = newsize;
+
+ if (contour->next != NULL)
+ contour->next->prev = newcontour;
+ if (contour->prev != NULL)
+ contour->prev->next = newcontour;
+ else
+ tv->contours = newcontour;
+ }
+
+ contour->points[contour->num_points++] = *p;
+
+ return contour;
+}
+
+static contour_t *
+contour_new (TrapView *tv, int direction)
+{
+ contour_t *t;
+
+ t = g_malloc (sizeof (contour_t) + 128 * sizeof (point_t));
+ t->direction = direction;
+ t->prev = NULL;
+ t->next = tv->contours;
+ if (tv->contours)
+ tv->contours->prev = t;
+ tv->contours = t;
+
+ t->size = 128;
+ t->num_points = 0;
+
+ return t;
+}
+
+int
+main (int argc, char **argv)
+{
+ TrapView *tv;
+ contour_t *contour = NULL;
+ GtkWidget *window;
+ FILE *file;
+ char *line = NULL;
+ size_t len = 0;
+
+ gtk_init (&argc, &argv);
+
+ tv = g_object_new (trap_view_get_type (), NULL);
+
+ file = fopen (argv[1], "r");
+ if (file != NULL) {
+ while (getline (&line, &len, file) != -1) {
+ point_t p;
+ int direction;
+
+ if (sscanf (line, "contour: direction=%d", &direction)) {
+ if (contour)
+ g_print ("read %d contour\n", contour->num_points);
+
+ contour = contour_new (tv, direction);
+ } else if (sscanf (line, " [%*d] = (%lf, %lf)", &p.x, &p.y) == 2) {
+ contour = _contour_add_point (tv, contour, &p);
+ }
+ }
+
+ if (contour)
+ g_print ("read %d contour\n", contour->num_points);
+
+ g_print ("extents=(%lg, %lg), (%lg, %lg)\n",
+ tv->extents.p1.x, tv->extents.p1.y,
+ tv->extents.p2.x, tv->extents.p2.y);
+ fclose (file);
+ }
+
+ window = gtk_window_new (GTK_WINDOW_TOPLEVEL);
+ g_signal_connect (window, "delete-event",
+ G_CALLBACK (gtk_main_quit), NULL);
+ gtk_widget_set_size_request (window, 800, 800);
+ gtk_container_add (GTK_CONTAINER (window), &tv->widget);
+ gtk_widget_show_all (window);
+
+ gtk_main ();
+ return 0;
+}
diff --git a/util/show-polygon.c b/util/show-polygon.c
index 5549cf2..9571363 100644
--- a/util/show-polygon.c
+++ b/util/show-polygon.c
@@ -202,6 +202,10 @@ polygon_view_draw (PolygonView *self, cairo_t *cr)
else
mag_x = self->px - size/4 - size;
mag_y = self->py - size/2;
+ if (mag_y < 0)
+ mag_y = 0;
+ if (mag_y + size > self->widget.allocation.height)
+ mag_y = self->widget.allocation.height - size;
}
cairo_save (cr); {
commit bbe704406ca97cd51ed1fcc76da7648abde36331
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Mon Aug 15 08:23:38 2011 +0100
stroke: move normal stroker to new file
Step 1 of enhancing the speed of the stroker is to segregate from the
rest of the complex code.
Signed-off-by: Chris Wilson <chris at chris-wilson.co.uk>
diff --git a/src/Makefile.sources b/src/Makefile.sources
index 2b563f2..9f7b6fe 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -164,6 +164,7 @@ cairo_sources = \
cairo-path-in-fill.c \
cairo-path-stroke.c \
cairo-path-stroke-boxes.c \
+ cairo-path-stroke-polygon.c \
cairo-pattern.c \
cairo-pen.c \
cairo-polygon.c \
diff --git a/src/cairo-path-stroke-polygon.c b/src/cairo-path-stroke-polygon.c
new file mode 100644
index 0000000..c60c2c0
--- /dev/null
+++ b/src/cairo-path-stroke-polygon.c
@@ -0,0 +1,1002 @@
+/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
+/* cairo - a vector graphics library with display and print output
+ *
+ * Copyright © 2002 University of Southern California
+ *
+ * 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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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 University of Southern
+ * California.
+ *
+ * Contributor(s):
+ * Carl D. Worth <cworth at cworth.org>
+ * Chris Wilson <chris at chris-wilson.co.uk>
+ */
+
+#define _BSD_SOURCE /* for hypot() */
+#include "cairoint.h"
+
+#include "cairo-box-private.h"
+#include "cairo-boxes-private.h"
+#include "cairo-error-private.h"
+#include "cairo-path-fixed-private.h"
+#include "cairo-slope-private.h"
+
+typedef struct cairo_stroker {
+ cairo_stroke_style_t style;
+
+ const cairo_matrix_t *ctm;
+ const cairo_matrix_t *ctm_inverse;
+ double tolerance;
+ double ctm_determinant;
+ cairo_bool_t ctm_det_positive;
+
+ cairo_polygon_t *polygon;
+ cairo_pen_t pen;
+
+ cairo_point_t current_point;
+ cairo_point_t first_point;
+
+ cairo_bool_t has_initial_sub_path;
+
+ cairo_bool_t has_current_face;
+ cairo_stroke_face_t current_face;
+
+ cairo_bool_t has_first_face;
+ cairo_stroke_face_t first_face;
+
+ cairo_bool_t has_bounds;
+ cairo_box_t bounds;
+} cairo_stroker_t;
+
+static void
+stroker_limit (cairo_stroker_t *stroker,
+ const cairo_box_t *boxes,
+ int num_boxes)
+{
+ double dx, dy;
+ cairo_fixed_t fdx, fdy;
+
+ stroker->has_bounds = TRUE;
+ _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
+
+ /* Extend the bounds in each direction to account for the maximum area
+ * we might generate trapezoids, to capture line segments that are outside
+ * of the bounds but which might generate rendering that's within bounds.
+ */
+
+ _cairo_stroke_style_max_distance_from_path (&stroker->style, stroker->ctm,
+ &dx, &dy);
+
+ fdx = _cairo_fixed_from_double (dx);
+ fdy = _cairo_fixed_from_double (dy);
+
+ stroker->bounds.p1.x -= fdx;
+ stroker->bounds.p2.x += fdx;
+
+ stroker->bounds.p1.y -= fdy;
+ stroker->bounds.p2.y += fdy;
+}
+
+static void
+translate_point (cairo_point_t *point, const cairo_point_t *offset)
+{
+ point->x += offset->x;
+ point->y += offset->y;
+}
+
+static int
+join_is_clockwise (const cairo_stroke_face_t *in,
+ const cairo_stroke_face_t *out)
+{
+ return _cairo_slope_compare (&in->dev_vector, &out->dev_vector) < 0;
+}
+
+/**
+ * slope_compare_sgn
+ *
+ * Return -1, 0 or 1 depending on the relative slopes of
+ * two lines.
+ */
+static int
+slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
+{
+ double c = (dx1 * dy2 - dx2 * dy1);
+
+ if (c > 0) return 1;
+ if (c < 0) return -1;
+ return 0;
+}
+
+static inline int
+range_step (int i, int step, int max)
+{
+ i += step;
+ if (i < 0)
+ i = max - 1;
+ if (i >= max)
+ i = 0;
+ return i;
+}
+
+/*
+ * Construct a fan around the midpoint using the vertices from pen between
+ * inpt and outpt.
+ */
+static cairo_status_t
+tessellate_fan (cairo_stroker_t *stroker,
+ const cairo_slope_t *in_vector,
+ const cairo_slope_t *out_vector,
+ const cairo_point_t *midpt,
+ const cairo_point_t *inpt,
+ const cairo_point_t *outpt,
+ cairo_bool_t clockwise)
+{
+ cairo_point_t stack_points[64], *points = stack_points;
+ int start, stop, step, i, npoints;
+ cairo_status_t status;
+
+ if (clockwise) {
+ step = -1;
+
+ start = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
+ in_vector);
+ if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_ccw,
+ in_vector) < 0)
+ start = range_step (start, -1, stroker->pen.num_vertices);
+
+ stop = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
+ out_vector);
+ if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
+ out_vector) > 0)
+ {
+ stop = range_step (stop, 1, stroker->pen.num_vertices);
+ if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
+ in_vector) < 0)
+ {
+ goto BEVEL;
+ }
+ }
+
+ npoints = start - stop;
+ } else {
+ step = 1;
+
+ start = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
+ in_vector);
+ if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_cw,
+ in_vector) < 0)
+ start = range_step (start, 1, stroker->pen.num_vertices);
+
+ stop = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
+ out_vector);
+ if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
+ out_vector) > 0)
+ {
+ stop = range_step (stop, -1, stroker->pen.num_vertices);
+ if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
+ in_vector) < 0)
+ {
+ goto BEVEL;
+ }
+ }
+
+ npoints = stop - start;
+ }
+ stop = range_step (stop, step, stroker->pen.num_vertices);
+
+ if (npoints < 0)
+ npoints += stroker->pen.num_vertices;
+ npoints += 3;
+
+ if (npoints <= 1)
+ goto BEVEL;
+
+ if (npoints > ARRAY_LENGTH (stack_points)) {
+ points = _cairo_malloc_ab (npoints, sizeof (cairo_point_t));
+ if (unlikely (points == NULL))
+ return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+ }
+
+
+ /* Construct the fan. */
+ npoints = 0;
+ points[npoints++] = *inpt;
+ for (i = start;
+ i != stop;
+ i = range_step (i, step, stroker->pen.num_vertices))
+ {
+ points[npoints] = *midpt;
+ translate_point (&points[npoints], &stroker->pen.vertices[i].point);
+ npoints++;
+ }
+ points[npoints++] = *outpt;
+
+ for (i = 0; i < npoints - 1; i++) {
+ if (clockwise) {
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &points[i], &points[i+1]);
+ } else {
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &points[i+1], &points[i]);
+ }
+ if (unlikely (status))
+ break;
+ }
+
+ if (points != stack_points)
+ free (points);
+
+ return status;
+
+BEVEL:
+ /* Ensure a leak free connection... */
+ if (clockwise)
+ return _cairo_polygon_add_external_edge (stroker->polygon, inpt, outpt);
+ else
+ return _cairo_polygon_add_external_edge (stroker->polygon, outpt, inpt);
+}
+
+static cairo_status_t
+join (cairo_stroker_t *stroker,
+ const cairo_stroke_face_t *in,
+ const cairo_stroke_face_t *out)
+{
+ int clockwise = join_is_clockwise (out, in);
+ const cairo_point_t *inpt, *outpt;
+ cairo_point_t points[4];
+ cairo_status_t status;
+
+ if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
+ in->ccw.x == out->ccw.x && in->ccw.y == out->ccw.y)
+ {
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ if (clockwise) {
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &out->cw, &in->point);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &in->point, &in->cw);
+ if (unlikely (status))
+ return status;
+
+ inpt = &in->ccw;
+ outpt = &out->ccw;
+ } else {
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &in->ccw, &in->point);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &in->point, &out->ccw);
+ if (unlikely (status))
+ return status;
+
+ inpt = &in->cw;
+ outpt = &out->cw;
+ }
+
+ switch (stroker->style.line_join) {
+ case CAIRO_LINE_JOIN_ROUND:
+ /* construct a fan around the common midpoint */
+ return tessellate_fan (stroker,
+ &in->dev_vector,
+ &out->dev_vector,
+ &in->point, inpt, outpt,
+ clockwise);
+
+ case CAIRO_LINE_JOIN_MITER:
+ default: {
+ /* dot product of incoming slope vector with outgoing slope vector */
+ double in_dot_out = -in->usr_vector.x * out->usr_vector.x +
+ -in->usr_vector.y * out->usr_vector.y;
+ double ml = stroker->style.miter_limit;
+
+ /* Check the miter limit -- lines meeting at an acute angle
+ * can generate long miters, the limit converts them to bevel
+ *
+ * Consider the miter join formed when two line segments
+ * meet at an angle psi:
+ *
+ * /.\
+ * /. .\
+ * /./ \.\
+ * /./psi\.\
+ *
+ * We can zoom in on the right half of that to see:
+ *
+ * |\
+ * | \ psi/2
+ * | \
+ * | \
+ * | \
+ * | \
+ * miter \
+ * length \
+ * | \
+ * | .\
+ * | . \
+ * |. line \
+ * \ width \
+ * \ \
+ *
+ *
+ * The right triangle in that figure, (the line-width side is
+ * shown faintly with three '.' characters), gives us the
+ * following expression relating miter length, angle and line
+ * width:
+ *
+ * 1 /sin (psi/2) = miter_length / line_width
+ *
+ * The right-hand side of this relationship is the same ratio
+ * in which the miter limit (ml) is expressed. We want to know
+ * when the miter length is within the miter limit. That is
+ * when the following condition holds:
+ *
+ * 1/sin(psi/2) <= ml
+ * 1 <= ml sin(psi/2)
+ * 1 <= ml² sin²(psi/2)
+ * 2 <= ml² 2 sin²(psi/2)
+ * 2·sin²(psi/2) = 1-cos(psi)
+ * 2 <= ml² (1-cos(psi))
+ *
+ * in · out = |in| |out| cos (psi)
+ *
+ * in and out are both unit vectors, so:
+ *
+ * in · out = cos (psi)
+ *
+ * 2 <= ml² (1 - in · out)
+ *
+ */
+ if (2 <= ml * ml * (1 - in_dot_out)) {
+ double x1, y1, x2, y2;
+ double mx, my;
+ double dx1, dx2, dy1, dy2;
+ double ix, iy;
+ double fdx1, fdy1, fdx2, fdy2;
+ double mdx, mdy;
+
+ /*
+ * we've got the points already transformed to device
+ * space, but need to do some computation with them and
+ * also need to transform the slope from user space to
+ * device space
+ */
+ /* outer point of incoming line face */
+ x1 = _cairo_fixed_to_double (inpt->x);
+ y1 = _cairo_fixed_to_double (inpt->y);
+ dx1 = in->usr_vector.x;
+ dy1 = in->usr_vector.y;
+ cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
+
+ /* outer point of outgoing line face */
+ x2 = _cairo_fixed_to_double (outpt->x);
+ y2 = _cairo_fixed_to_double (outpt->y);
+ dx2 = out->usr_vector.x;
+ dy2 = out->usr_vector.y;
+ cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
+
+ /*
+ * Compute the location of the outer corner of the miter.
+ * That's pretty easy -- just the intersection of the two
+ * outer edges. We've got slopes and points on each
+ * of those edges. Compute my directly, then compute
+ * mx by using the edge with the larger dy; that avoids
+ * dividing by values close to zero.
+ */
+ my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
+ (dx1 * dy2 - dx2 * dy1));
+ if (fabs (dy1) >= fabs (dy2))
+ mx = (my - y1) * dx1 / dy1 + x1;
+ else
+ mx = (my - y2) * dx2 / dy2 + x2;
+
+ /*
+ * When the two outer edges are nearly parallel, slight
+ * perturbations in the position of the outer points of the lines
+ * caused by representing them in fixed point form can cause the
+ * intersection point of the miter to move a large amount. If
+ * that moves the miter intersection from between the two faces,
+ * then draw a bevel instead.
+ */
+
+ ix = _cairo_fixed_to_double (in->point.x);
+ iy = _cairo_fixed_to_double (in->point.y);
+
+ /* slope of one face */
+ fdx1 = x1 - ix; fdy1 = y1 - iy;
+
+ /* slope of the other face */
+ fdx2 = x2 - ix; fdy2 = y2 - iy;
+
+ /* slope from the intersection to the miter point */
+ mdx = mx - ix; mdy = my - iy;
+
+ /*
+ * Make sure the miter point line lies between the two
+ * faces by comparing the slopes
+ */
+ if (slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
+ slope_compare_sgn (fdx2, fdy2, mdx, mdy))
+ {
+ points[0].x = _cairo_fixed_from_double (mx);
+ points[0].y = _cairo_fixed_from_double (my);
+
+ if (clockwise) {
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ inpt, &points[0]);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &points[0], outpt);
+ if (unlikely (status))
+ return status;
+ } else {
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ outpt, &points[0]);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &points[0], inpt);
+ if (unlikely (status))
+ return status;
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+ }
+ }
+ }
+
+ /* fall through ... */
+
+ case CAIRO_LINE_JOIN_BEVEL:
+ if (clockwise) {
+ return _cairo_polygon_add_external_edge (stroker->polygon,
+ inpt, outpt);
+ } else {
+ return _cairo_polygon_add_external_edge (stroker->polygon,
+ outpt, inpt);
+ }
+ }
+}
+
+static cairo_status_t
+add_cap (cairo_stroker_t *stroker,
+ const cairo_stroke_face_t *f)
+{
+ switch (stroker->style.line_cap) {
+ case CAIRO_LINE_CAP_ROUND: {
+ cairo_slope_t slope;
+
+ slope.dx = -f->dev_vector.dx;
+ slope.dy = -f->dev_vector.dy;
+
+ return tessellate_fan (stroker,
+ &f->dev_vector,
+ &slope,
+ &f->point, &f->cw, &f->ccw,
+ FALSE);
+
+ }
+
+ case CAIRO_LINE_CAP_SQUARE: {
+ double dx, dy;
+ cairo_slope_t fvector;
+ cairo_point_t quad[4];
+ cairo_status_t status;
+
+ dx = f->usr_vector.x;
+ dy = f->usr_vector.y;
+ dx *= stroker->style.line_width / 2.0;
+ dy *= stroker->style.line_width / 2.0;
+ cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
+ fvector.dx = _cairo_fixed_from_double (dx);
+ fvector.dy = _cairo_fixed_from_double (dy);
+
+ quad[0] = f->ccw;
+ quad[1].x = f->ccw.x + fvector.dx;
+ quad[1].y = f->ccw.y + fvector.dy;
+ quad[2].x = f->cw.x + fvector.dx;
+ quad[2].y = f->cw.y + fvector.dy;
+ quad[3] = f->cw;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &quad[0], &quad[1]);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &quad[1], &quad[2]);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &quad[2], &quad[3]);
+ if (unlikely (status))
+ return status;
+
+ return CAIRO_STATUS_SUCCESS;
+ }
+
+ case CAIRO_LINE_CAP_BUTT:
+ default:
+ return _cairo_polygon_add_external_edge (stroker->polygon,
+ &f->ccw, &f->cw);
+ }
+}
+
+static cairo_status_t
+add_leading_cap (cairo_stroker_t *stroker,
+ const cairo_stroke_face_t *face)
+{
+ cairo_stroke_face_t reversed;
+ cairo_point_t t;
+
+ reversed = *face;
+
+ /* The initial cap needs an outward facing vector. Reverse everything */
+ reversed.usr_vector.x = -reversed.usr_vector.x;
+ reversed.usr_vector.y = -reversed.usr_vector.y;
+ reversed.dev_vector.dx = -reversed.dev_vector.dx;
+ reversed.dev_vector.dy = -reversed.dev_vector.dy;
+ t = reversed.cw;
+ reversed.cw = reversed.ccw;
+ reversed.ccw = t;
+
+ return add_cap (stroker, &reversed);
+}
+
+static cairo_status_t
+add_trailing_cap (cairo_stroker_t *stroker,
+ const cairo_stroke_face_t *face)
+{
+ return add_cap (stroker, face);
+}
+
+static inline cairo_bool_t
+compute_normalized_device_slope (double *dx, double *dy,
+ const cairo_matrix_t *ctm_inverse,
+ double *mag_out)
+{
+ double dx0 = *dx, dy0 = *dy;
+ double mag;
+
+ cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
+
+ if (dx0 == 0.0 && dy0 == 0.0) {
+ if (mag_out)
+ *mag_out = 0.0;
+ return FALSE;
+ }
+
+ if (dx0 == 0.0) {
+ *dx = 0.0;
+ if (dy0 > 0.0) {
+ mag = dy0;
+ *dy = 1.0;
+ } else {
+ mag = -dy0;
+ *dy = -1.0;
+ }
+ } else if (dy0 == 0.0) {
+ *dy = 0.0;
+ if (dx0 > 0.0) {
+ mag = dx0;
+ *dx = 1.0;
+ } else {
+ mag = -dx0;
+ *dx = -1.0;
+ }
+ } else {
+ mag = hypot (dx0, dy0);
+ *dx = dx0 / mag;
+ *dy = dy0 / mag;
+ }
+
+ if (mag_out)
+ *mag_out = mag;
+
+ return TRUE;
+}
+
+static void
+compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
+ double slope_dx, double slope_dy,
+ cairo_stroker_t *stroker, cairo_stroke_face_t *face)
+{
+ double face_dx, face_dy;
+ cairo_point_t offset_ccw, offset_cw;
+
+ /*
+ * rotate to get a line_width/2 vector along the face, note that
+ * the vector must be rotated the right direction in device space,
+ * but by 90° in user space. So, the rotation depends on
+ * whether the ctm reflects or not, and that can be determined
+ * by looking at the determinant of the matrix.
+ */
+ if (stroker->ctm_det_positive)
+ {
+ face_dx = - slope_dy * (stroker->style.line_width / 2.0);
+ face_dy = slope_dx * (stroker->style.line_width / 2.0);
+ }
+ else
+ {
+ face_dx = slope_dy * (stroker->style.line_width / 2.0);
+ face_dy = - slope_dx * (stroker->style.line_width / 2.0);
+ }
+
+ /* back to device space */
+ cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
+
+ offset_ccw.x = _cairo_fixed_from_double (face_dx);
+ offset_ccw.y = _cairo_fixed_from_double (face_dy);
+ offset_cw.x = -offset_ccw.x;
+ offset_cw.y = -offset_ccw.y;
+
+ face->ccw = *point;
+ translate_point (&face->ccw, &offset_ccw);
+
+ face->point = *point;
+
+ face->cw = *point;
+ translate_point (&face->cw, &offset_cw);
+
+ face->usr_vector.x = slope_dx;
+ face->usr_vector.y = slope_dy;
+
+ face->dev_vector = *dev_slope;
+}
+
+static cairo_status_t
+add_caps (cairo_stroker_t *stroker)
+{
+ cairo_status_t status;
+
+ /* check for a degenerative sub_path */
+ if (stroker->has_initial_sub_path &&
+ ! stroker->has_first_face &&
+ ! stroker->has_current_face &&
+ stroker->style.line_cap == CAIRO_LINE_CAP_ROUND)
+ {
+ /* pick an arbitrary slope to use */
+ double dx = 1.0, dy = 0.0;
+ cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
+ cairo_stroke_face_t face;
+
+ compute_normalized_device_slope (&dx, &dy,
+ stroker->ctm_inverse, NULL);
+
+ /* arbitrarily choose first_point
+ * first_point and current_point should be the same */
+ compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
+
+ status = add_leading_cap (stroker, &face);
+ if (unlikely (status))
+ return status;
+
+ status = add_trailing_cap (stroker, &face);
+ if (unlikely (status))
+ return status;
+ }
+
+ if (stroker->has_first_face) {
+ status = add_leading_cap (stroker, &stroker->first_face);
+ if (unlikely (status))
+ return status;
+ }
+
+ if (stroker->has_current_face) {
+ status = add_trailing_cap (stroker, &stroker->current_face);
+ if (unlikely (status))
+ return status;
+ }
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+add_sub_edge (cairo_stroker_t *stroker,
+ const cairo_point_t *p1,
+ const cairo_point_t *p2,
+ cairo_slope_t *dev_slope,
+ double slope_dx, double slope_dy,
+ cairo_stroke_face_t *start,
+ cairo_stroke_face_t *end)
+{
+ cairo_status_t status;
+
+ compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
+ *end = *start;
+
+ if (p1->x == p2->x && p1->y == p2->y)
+ return CAIRO_STATUS_SUCCESS;
+
+ end->point = *p2;
+ end->ccw.x += p2->x - p1->x;
+ end->ccw.y += p2->y - p1->y;
+ end->cw.x += p2->x - p1->x;
+ end->cw.y += p2->y - p1->y;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &end->cw, &start->cw);
+ if (unlikely (status))
+ return status;
+
+ status = _cairo_polygon_add_external_edge (stroker->polygon,
+ &start->ccw, &end->ccw);
+ if (unlikely (status))
+ return status;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+move_to (void *closure,
+ const cairo_point_t *point)
+{
+ cairo_stroker_t *stroker = closure;
+ cairo_status_t status;
+
+ /* Cap the start and end of the previous sub path as needed */
+ status = add_caps (stroker);
+ if (unlikely (status))
+ return status;
+
+ stroker->first_point = *point;
+ stroker->current_point = *point;
+
+ stroker->has_first_face = FALSE;
+ stroker->has_current_face = FALSE;
+ stroker->has_initial_sub_path = FALSE;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+line_to (void *closure,
+ const cairo_point_t *point)
+{
+ cairo_stroker_t *stroker = closure;
+ cairo_stroke_face_t start, end;
+ cairo_point_t *p1 = &stroker->current_point;
+ cairo_slope_t dev_slope;
+ double slope_dx, slope_dy;
+ cairo_status_t status;
+
+ stroker->has_initial_sub_path = TRUE;
+
+ if (p1->x == point->x && p1->y == point->y)
+ return CAIRO_STATUS_SUCCESS;
+
+ _cairo_slope_init (&dev_slope, p1, point);
+ slope_dx = _cairo_fixed_to_double (point->x - p1->x);
+ slope_dy = _cairo_fixed_to_double (point->y - p1->y);
+ compute_normalized_device_slope (&slope_dx, &slope_dy,
+ stroker->ctm_inverse, NULL);
+
+ status = add_sub_edge (stroker,
+ p1, point,
+ &dev_slope,
+ slope_dx, slope_dy,
+ &start, &end);
+ if (unlikely (status))
+ return status;
+
+ if (stroker->has_current_face) {
+ /* Join with final face from previous segment */
+ status = join (stroker, &stroker->current_face, &start);
+ if (unlikely (status))
+ return status;
+ } else if (! stroker->has_first_face) {
+ /* Save sub path's first face in case needed for closing join */
+ stroker->first_face = start;
+ stroker->has_first_face = TRUE;
+ }
+ stroker->current_face = end;
+ stroker->has_current_face = TRUE;
+
+ stroker->current_point = *point;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+curve_to (void *closure,
+ const cairo_point_t *b,
+ const cairo_point_t *c,
+ const cairo_point_t *d)
+{
+ cairo_stroker_t *stroker = closure;
+ cairo_spline_t spline;
+ cairo_line_join_t line_join_save;
+ cairo_stroke_face_t face;
+ double slope_dx, slope_dy;
+ cairo_status_t status = CAIRO_STATUS_SUCCESS;
+
+ if (! _cairo_spline_init (&spline, line_to, stroker,
+ &stroker->current_point, b, c, d))
+ {
+ return line_to (closure, d);
+ }
+
+ /* Compute the initial face */
+ if (1) {
+ slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
+ slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
+ if (compute_normalized_device_slope (&slope_dx, &slope_dy,
+ stroker->ctm_inverse, NULL))
+ {
+ compute_face (&stroker->current_point,
+ &spline.initial_slope,
+ slope_dx, slope_dy,
+ stroker, &face);
+ }
+ if (stroker->has_current_face) {
+ status = join (stroker, &stroker->current_face, &face);
+ if (unlikely (status))
+ return status;
+ } else if (! stroker->has_first_face) {
+ stroker->first_face = face;
+ stroker->has_first_face = TRUE;
+ }
+
+ stroker->current_face = face;
+ stroker->has_current_face = TRUE;
+ }
+
+ /* Temporarily modify the stroker to use round joins to guarantee
+ * smooth stroked curves. */
+ line_join_save = stroker->style.line_join;
+ stroker->style.line_join = CAIRO_LINE_JOIN_ROUND;
+
+ status = _cairo_spline_decompose (&spline, stroker->tolerance);
+ if (unlikely (status))
+ return status;
+
+ /* And join the final face */
+ if (1) {
+ slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
+ slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
+ if (compute_normalized_device_slope (&slope_dx, &slope_dy,
+ stroker->ctm_inverse, NULL))
+ {
+ compute_face (&stroker->current_point,
+ &spline.final_slope,
+ slope_dx, slope_dy,
+ stroker, &face);
+ }
+
+ status = join (stroker, &stroker->current_face, &face);
+ if (unlikely (status))
+ return status;
+
+ stroker->current_face = face;
+ }
+
+ stroker->style.line_join = line_join_save;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+close_path (void *closure)
+{
+ cairo_stroker_t *stroker = closure;
+ cairo_status_t status;
+
+ status = line_to (stroker, &stroker->first_point);
+ if (unlikely (status))
+ return status;
+
+ if (stroker->has_first_face && stroker->has_current_face) {
+ /* Join first and final faces of sub path */
+ status = join (stroker, &stroker->current_face, &stroker->first_face);
+ if (unlikely (status))
+ return status;
+ } else {
+ /* Cap the start and end of the sub path as needed */
+ status = add_caps (stroker);
+ if (unlikely (status))
+ return status;
+ }
+
+ stroker->has_initial_sub_path = FALSE;
+ stroker->has_first_face = FALSE;
+ stroker->has_current_face = FALSE;
+
+ return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t *path,
+ const cairo_stroke_style_t *style,
+ const cairo_matrix_t *ctm,
+ const cairo_matrix_t *ctm_inverse,
+ double tolerance,
+ cairo_polygon_t *polygon)
+{
+ cairo_stroker_t stroker;
+ cairo_status_t status;
+
+ if (style->dash)
+ return _cairo_path_fixed_stroke_dashed_to_polygon (path,
+ style,
+ ctm,
+ ctm_inverse,
+ tolerance,
+ polygon);
+
+ stroker.style = *style;
+ stroker.ctm = ctm;
+ stroker.ctm_inverse = ctm_inverse;
+ stroker.tolerance = tolerance;
+
+ stroker.ctm_det_positive = _cairo_matrix_compute_determinant (ctm) >= 0.;
+
+ status = _cairo_pen_init (&stroker.pen,
+ style->line_width / 2.0,
+ tolerance, ctm);
+ if (unlikely (status))
+ return status;
+
+ /* If the line width is so small that the pen is reduced to a
+ single point, then we have nothing to do. */
+ if (stroker.pen.num_vertices <= 1)
+ return CAIRO_STATUS_SUCCESS;
+
+ stroker.polygon = polygon;
+
+ stroker.has_current_face = FALSE;
+ stroker.has_first_face = FALSE;
+ stroker.has_initial_sub_path = FALSE;
+
+ stroker.has_bounds = FALSE;
+ if (polygon->num_limits)
+ stroker_limit (&stroker, polygon->limits, polygon->num_limits);
+
+ status = _cairo_path_fixed_interpret (path,
+ move_to,
+ line_to,
+ curve_to,
+ close_path,
+ &stroker);
+
+ /* Cap the start and end of the final sub path as needed */
+ if (likely (status == CAIRO_STATUS_SUCCESS))
+ status = add_caps (&stroker);
+
+ _cairo_pen_fini (&stroker.pen);
+
+ return status;
+}
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 02f6ba2..819708e 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -1274,12 +1274,12 @@ BAIL:
}
cairo_status_t
-_cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t *path,
- const cairo_stroke_style_t *stroke_style,
- const cairo_matrix_t *ctm,
- const cairo_matrix_t *ctm_inverse,
- double tolerance,
- cairo_polygon_t *polygon)
+_cairo_path_fixed_stroke_dashed_to_polygon (const cairo_path_fixed_t *path,
+ const cairo_stroke_style_t *stroke_style,
+ const cairo_matrix_t *ctm,
+ const cairo_matrix_t *ctm_inverse,
+ double tolerance,
+ cairo_polygon_t *polygon)
{
cairo_stroker_t stroker;
cairo_status_t status;
diff --git a/src/cairoint.h b/src/cairoint.h
index f393857..e294df3 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -1397,6 +1397,14 @@ _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t *path,
double tolerance,
cairo_polygon_t *polygon);
+cairo_private cairo_status_t
+_cairo_path_fixed_stroke_dashed_to_polygon (const cairo_path_fixed_t *path,
+ const cairo_stroke_style_t *stroke_style,
+ const cairo_matrix_t *ctm,
+ const cairo_matrix_t *ctm_inverse,
+ double tolerance,
+ cairo_polygon_t *polygon);
+
cairo_private cairo_int_status_t
_cairo_path_fixed_stroke_rectilinear_to_boxes (const cairo_path_fixed_t *path,
const cairo_stroke_style_t *stroke_style,
More information about the cairo-commit
mailing list