src/cairo-path-in-fill.c

   1 /* cairo - a vector graphics library with display and print output
   2  *
   3  * Copyright © 2008 Chris Wilson
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it either under the terms of the GNU Lesser General Public
   7  * License version 2.1 as published by the Free Software Foundation
   8  * (the "LGPL") or, at your option, under the terms of the Mozilla
   9  * Public License Version 1.1 (the "MPL"). If you do not alter this
  10  * notice, a recipient may use your version of this file under either
  11  * the MPL or the LGPL.
  12  *
  13  * You should have received a copy of the LGPL along with this library
  14  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  15  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  16  * You should have received a copy of the MPL along with this library
  17  * in the file COPYING-MPL-1.1
  18  *
  19  * The contents of this file are subject to the Mozilla Public License
  20  * Version 1.1 (the "License"); you may not use this file except in
  21  * compliance with the License. You may obtain a copy of the License at
  22  * http://www.mozilla.org/MPL/
  23  *
  24  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  25  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  26  * the specific language governing rights and limitations.
  27  *
  28  * The Original Code is the cairo graphics library.
  29  *
  30  * The Initial Developer of the Original Code is Chris Wilson.
  31  *
  32  * Contributor(s):
  33  *      Chris Wilson <chris@chris-wilson.co.uk>
  34  */
  35
  36 #include "cairoint.h"
  37 #include "cairo-path-fixed-private.h"
  38
  39 typedef struct cairo_in_fill {
  40     double tolerance;
  41     cairo_bool_t on_edge;
  42     int winding;
  43
  44     cairo_fixed_t x, y;
  45
  46     cairo_bool_t has_current_point;
  47     cairo_point_t current_point;
  48     cairo_point_t first_point;
  49 } cairo_in_fill_t;
  50
  51 static void
  52 _cairo_in_fill_init (cairo_in_fill_t    *in_fill,
  53                      double              tolerance,
  54                      double              x,
  55                      double              y)
  56 {
  57     in_fill->on_edge = FALSE;
  58     in_fill->winding = 0;
  59     in_fill->tolerance = tolerance;
  60
  61     in_fill->x = _cairo_fixed_from_double (x);
  62     in_fill->y = _cairo_fixed_from_double (y);
  63
  64     in_fill->has_current_point = FALSE;
  65     in_fill->current_point.x = 0;
  66     in_fill->current_point.y = 0;
  67 }
  68
  69 static void
  70 _cairo_in_fill_fini (cairo_in_fill_t *in_fill)
  71 {
  72 }
  73
  74 static int
  75 edge_compare_for_y_against_x (const cairo_point_t *p1,
  76                               const cairo_point_t *p2,
  77                               cairo_fixed_t y,
  78                               cairo_fixed_t x)
  79 {
  80     cairo_fixed_t adx, ady;
  81     cairo_fixed_t dx, dy;
  82     cairo_int64_t L, R;
  83
  84     adx = p2->x - p1->x;
  85     dx = x - p1->x;
  86
  87     if (adx == 0)
  88         return -dx;
  89     if ((adx ^ dx) < 0)
  90         return adx;
  91
  92     dy = y - p1->y;
  93     ady = p2->y - p1->y;
  94
  95     L = _cairo_int32x32_64_mul (dy, adx);
  96     R = _cairo_int32x32_64_mul (dx, ady);
  97
  98     return _cairo_int64_cmp (L, R);
  99 }
 100
 101 static void
 102 _cairo_in_fill_add_edge (cairo_in_fill_t *in_fill,
 103                          const cairo_point_t *p1,
 104                          const cairo_point_t *p2)
 105 {
 106     int dir;
 107
 108     if (in_fill->on_edge)
 109         return;
 110
 111     /* count the number of edge crossing to -∞ */
 112
 113     dir = 1;
 114     if (p2->y < p1->y) {
 115         const cairo_point_t *tmp;
 116
 117         tmp = p1;
 118         p1 = p2;
 119         p2 = tmp;
 120
 121         dir = -1;
 122     }
 123
 124     /* First check whether the query is on an edge */
 125     if ((p1->x == in_fill->x && p1->y == in_fill->y) ||
 126         (p2->x == in_fill->x && p2->y == in_fill->y) ||
 127         (! (p2->y < in_fill->y || p1->y > in_fill->y ||
 128            (p1->x > in_fill->x && p2->x > in_fill->x) ||
 129            (p1->x < in_fill->x && p2->x < in_fill->x)) &&
 130          edge_compare_for_y_against_x (p1, p2, in_fill->y, in_fill->x) == 0))
 131     {
 132         in_fill->on_edge = TRUE;
 133         return;
 134     }
 135
 136     /* edge is entirely above or below, note the shortening rule */
 137     if (p2->y <= in_fill->y || p1->y > in_fill->y)
 138         return;
 139
 140     /* edge lies wholly to the right */
 141     if (p1->x >= in_fill->x && p2->x >= in_fill->x)
 142         return;
 143
 144     if ((p1->x <= in_fill->x && p2->x <= in_fill->x) ||
 145         edge_compare_for_y_against_x (p1, p2, in_fill->y, in_fill->x) < 0)
 146     {
 147         in_fill->winding += dir;
 148     }
 149 }
 150
 151 static cairo_status_t
 152 _cairo_in_fill_move_to (void *closure,
 153                         const cairo_point_t *point)
 154 {
 155     cairo_in_fill_t *in_fill = closure;
 156
 157     /* implicit close path */
 158     if (in_fill->has_current_point) {
 159         _cairo_in_fill_add_edge (in_fill,
 160                                  &in_fill->current_point,
 161                                  &in_fill->first_point);
 162     }
 163
 164     in_fill->first_point = *point;
 165     in_fill->current_point = *point;
 166     in_fill->has_current_point = TRUE;
 167
 168     return CAIRO_STATUS_SUCCESS;
 169 }
 170
 171 static cairo_status_t
 172 _cairo_in_fill_line_to (void *closure,
 173                         const cairo_point_t *point)
 174 {
 175     cairo_in_fill_t *in_fill = closure;
 176
 177     if (in_fill->has_current_point)
 178         _cairo_in_fill_add_edge (in_fill, &in_fill->current_point, point);
 179
 180     in_fill->current_point = *point;
 181     in_fill->has_current_point = TRUE;
 182
 183     return CAIRO_STATUS_SUCCESS;
 184 }
 185
 186 static cairo_status_t
 187 _cairo_in_fill_curve_to (void *closure,
 188                          const cairo_point_t *b,
 189                          const cairo_point_t *c,
 190                          const cairo_point_t *d)
 191 {
 192     cairo_in_fill_t *in_fill = closure;
 193     cairo_spline_t spline;
 194     cairo_fixed_t top, bot, left;
 195
 196     /* first reject based on bbox */
 197     bot = top = in_fill->current_point.y;
 198     if (b->y < top) top = b->y;
 199     if (b->y > bot) bot = b->y;
 200     if (c->y < top) top = c->y;
 201     if (c->y > bot) bot = c->y;
 202     if (d->y < top) top = d->y;
 203     if (d->y > bot) bot = d->y;
 204     if (bot < in_fill->y || top > in_fill->y) {
 205         in_fill->current_point = *d;
 206         return CAIRO_STATUS_SUCCESS;
 207     }
 208
 209     left = in_fill->current_point.x;
 210     if (b->x < left) left = b->x;
 211     if (c->x < left) left = c->x;
 212     if (d->x < left) left = d->x;
 213     if (left > in_fill->x) {
 214         in_fill->current_point = *d;
 215         return CAIRO_STATUS_SUCCESS;
 216     }
 217
 218     /* XXX Investigate direct inspection of the inflections? */
 219     if (! _cairo_spline_init (&spline,
 220                               (cairo_spline_add_point_func_t)_cairo_in_fill_line_to,
 221                               in_fill,
 222                               &in_fill->current_point, b, c, d))
 223     {
 224         return CAIRO_STATUS_SUCCESS;
 225     }
 226
 227     return _cairo_spline_decompose (&spline, in_fill->tolerance);
 228 }
 229
 230 static cairo_status_t
 231 _cairo_in_fill_close_path (void *closure)
 232 {
 233     cairo_in_fill_t *in_fill = closure;
 234
 235     if (in_fill->has_current_point) {
 236         _cairo_in_fill_add_edge (in_fill,
 237                                  &in_fill->current_point,
 238                                  &in_fill->first_point);
 239
 240         in_fill->has_current_point = FALSE;
 241     }
 242
 243     return CAIRO_STATUS_SUCCESS;
 244 }
 245
 246 cairo_bool_t
 247 _cairo_path_fixed_in_fill (const cairo_path_fixed_t     *path,
 248                            cairo_fill_rule_t     fill_rule,
 249                            double                tolerance,
 250                            double                x,
 251                            double                y)
 252 {
 253     cairo_in_fill_t in_fill;
 254     cairo_status_t status;
 255     cairo_bool_t is_inside;
 256
 257     if (_cairo_path_fixed_fill_is_empty (path))
 258         return FALSE;
 259
 260     _cairo_in_fill_init (&in_fill, tolerance, x, y);
 261
 262     status = _cairo_path_fixed_interpret (path,
 263                                           _cairo_in_fill_move_to,
 264                                           _cairo_in_fill_line_to,
 265                                           _cairo_in_fill_curve_to,
 266                                           _cairo_in_fill_close_path,
 267                                           &in_fill);
 268     assert (status == CAIRO_STATUS_SUCCESS);
 269
 270     _cairo_in_fill_close_path (&in_fill);
 271
 272     if (in_fill.on_edge) {
 273         is_inside = TRUE;
 274     } else switch (fill_rule) {
 275     case CAIRO_FILL_RULE_EVEN_ODD:
 276         is_inside = in_fill.winding & 1;
 277         break;
 278     case CAIRO_FILL_RULE_WINDING:
 279         is_inside = in_fill.winding != 0;
 280         break;
 281     default:
 282         ASSERT_NOT_REACHED;
 283         is_inside = FALSE;
 284         break;
 285     }
 286
 287     _cairo_in_fill_fini (&in_fill);
 288
 289     return is_inside;
 290 }