src/cairo-path-fill.c

   1 /* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
   2 /* cairo - a vector graphics library with display and print output
   3  *
   4  * Copyright © 2002 University of Southern California
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it either under the terms of the GNU Lesser General Public
   8  * License version 2.1 as published by the Free Software Foundation
   9  * (the "LGPL") or, at your option, under the terms of the Mozilla
  10  * Public License Version 1.1 (the "MPL"). If you do not alter this
  11  * notice, a recipient may use your version of this file under either
  12  * the MPL or the LGPL.
  13  *
  14  * You should have received a copy of the LGPL along with this library
  15  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  17  * You should have received a copy of the MPL along with this library
  18  * in the file COPYING-MPL-1.1
  19  *
  20  * The contents of this file are subject to the Mozilla Public License
  21  * Version 1.1 (the "License"); you may not use this file except in
  22  * compliance with the License. You may obtain a copy of the License at
  23  * http://www.mozilla.org/MPL/
  24  *
  25  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  26  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  27  * the specific language governing rights and limitations.
  28  *
  29  * The Original Code is the cairo graphics library.
  30  *
  31  * The Initial Developer of the Original Code is University of Southern
  32  * California.
  33  *
  34  * Contributor(s):
  35  *      Carl D. Worth <cworth@cworth.org>
  36  */
  37
  38 #include "cairoint.h"
  39 #include "cairo-boxes-private.h"
  40 #include "cairo-error-private.h"
  41 #include "cairo-path-fixed-private.h"
  42 #include "cairo-region-private.h"
  43 #include "cairo-traps-private.h"
  44
  45 typedef struct cairo_filler {
  46     cairo_polygon_t *polygon;
  47     double tolerance;
  48
  49     cairo_box_t limit;
  50     cairo_bool_t has_limits;
  51
  52     cairo_point_t current_point;
  53     cairo_point_t last_move_to;
  54 } cairo_filler_t;
  55
  56 static cairo_status_t
  57 _cairo_filler_line_to (void *closure,
  58                        const cairo_point_t *point)
  59 {
  60     cairo_filler_t *filler = closure;
  61     cairo_status_t status;
  62
  63     status = _cairo_polygon_add_external_edge (filler->polygon,
  64                                                &filler->current_point,
  65                                                point);
  66
  67     filler->current_point = *point;
  68
  69     return status;
  70 }
  71
  72 static cairo_status_t
  73 _cairo_filler_close (void *closure)
  74 {
  75     cairo_filler_t *filler = closure;
  76
  77     /* close the subpath */
  78     return _cairo_filler_line_to (closure, &filler->last_move_to);
  79 }
  80
  81 static cairo_status_t
  82 _cairo_filler_move_to (void *closure,
  83                        const cairo_point_t *point)
  84 {
  85     cairo_filler_t *filler = closure;
  86     cairo_status_t status;
  87
  88     /* close current subpath */
  89     status = _cairo_filler_close (closure);
  90     if (unlikely (status))
  91         return status;
  92
  93         /* make sure that the closure represents a degenerate path */
  94     filler->current_point = *point;
  95     filler->last_move_to = *point;
  96
  97     return CAIRO_STATUS_SUCCESS;
  98 }
  99
 100 static cairo_status_t
 101 _cairo_filler_curve_to (void            *closure,
 102                         const cairo_point_t     *p1,
 103                         const cairo_point_t     *p2,
 104                         const cairo_point_t     *p3)
 105 {
 106     cairo_filler_t *filler = closure;
 107     cairo_spline_t spline;
 108
 109     if (filler->has_limits) {
 110         if (! _cairo_spline_intersects (&filler->current_point, p1, p2, p3,
 111                                         &filler->limit))
 112             return _cairo_filler_line_to (filler, p3);
 113     }
 114
 115     if (! _cairo_spline_init (&spline,
 116                               (cairo_spline_add_point_func_t)_cairo_filler_line_to, filler,
 117                               &filler->current_point, p1, p2, p3))
 118     {
 119         return _cairo_filler_line_to (closure, p3);
 120     }
 121
 122     return _cairo_spline_decompose (&spline, filler->tolerance);
 123 }
 124
 125 cairo_status_t
 126 _cairo_path_fixed_fill_to_polygon (const cairo_path_fixed_t *path,
 127                                    double tolerance,
 128                                    cairo_polygon_t *polygon)
 129 {
 130     cairo_filler_t filler;
 131     cairo_status_t status;
 132
 133     filler.polygon = polygon;
 134     filler.tolerance = tolerance;
 135
 136     filler.has_limits = FALSE;
 137     if (polygon->num_limits) {
 138         filler.has_limits = TRUE;
 139         filler.limit = polygon->limit;
 140     }
 141
 142     /* make sure that the closure represents a degenerate path */
 143     filler.current_point.x = 0;
 144     filler.current_point.y = 0;
 145     filler.last_move_to = filler.current_point;
 146
 147     status = _cairo_path_fixed_interpret (path,
 148                                           _cairo_filler_move_to,
 149                                           _cairo_filler_line_to,
 150                                           _cairo_filler_curve_to,
 151                                           _cairo_filler_close,
 152                                           &filler);
 153     if (unlikely (status))
 154         return status;
 155
 156     return _cairo_filler_close (&filler);
 157 }
 158
 159 typedef struct cairo_filler_rectilinear_aligned {
 160     cairo_polygon_t *polygon;
 161
 162     cairo_point_t current_point;
 163     cairo_point_t last_move_to;
 164 } cairo_filler_ra_t;
 165
 166 static cairo_status_t
 167 _cairo_filler_ra_line_to (void *closure,
 168                           const cairo_point_t *point)
 169 {
 170     cairo_filler_ra_t *filler = closure;
 171     cairo_status_t status;
 172     cairo_point_t p;
 173
 174     p.x = _cairo_fixed_round_down (point->x);
 175     p.y = _cairo_fixed_round_down (point->y);
 176
 177     status = _cairo_polygon_add_external_edge (filler->polygon,
 178                                                &filler->current_point,
 179                                                &p);
 180
 181     filler->current_point = p;
 182
 183     return status;
 184 }
 185
 186 static cairo_status_t
 187 _cairo_filler_ra_close (void *closure)
 188 {
 189     cairo_filler_ra_t *filler = closure;
 190     return _cairo_filler_ra_line_to (closure, &filler->last_move_to);
 191 }
 192
 193 static cairo_status_t
 194 _cairo_filler_ra_move_to (void *closure,
 195                           const cairo_point_t *point)
 196 {
 197     cairo_filler_ra_t *filler = closure;
 198     cairo_status_t status;
 199     cairo_point_t p;
 200
 201     /* close current subpath */
 202     status = _cairo_filler_ra_close (closure);
 203     if (unlikely (status))
 204         return status;
 205
 206     p.x = _cairo_fixed_round_down (point->x);
 207     p.y = _cairo_fixed_round_down (point->y);
 208
 209     /* make sure that the closure represents a degenerate path */
 210     filler->current_point = p;
 211     filler->last_move_to = p;
 212
 213     return CAIRO_STATUS_SUCCESS;
 214 }
 215
 216 cairo_status_t
 217 _cairo_path_fixed_fill_rectilinear_to_polygon (const cairo_path_fixed_t *path,
 218                                                cairo_antialias_t antialias,
 219                                                cairo_polygon_t *polygon)
 220 {
 221     cairo_filler_ra_t filler;
 222     cairo_status_t status;
 223
 224     if (antialias != CAIRO_ANTIALIAS_NONE)
 225         return _cairo_path_fixed_fill_to_polygon (path, 0., polygon);
 226
 227     filler.polygon = polygon;
 228
 229     /* make sure that the closure represents a degenerate path */
 230     filler.current_point.x = 0;
 231     filler.current_point.y = 0;
 232     filler.last_move_to = filler.current_point;
 233
 234     status = _cairo_path_fixed_interpret_flat (path,
 235                                                _cairo_filler_ra_move_to,
 236                                                _cairo_filler_ra_line_to,
 237                                                _cairo_filler_ra_close,
 238                                                &filler,
 239                                                0.);
 240     if (unlikely (status))
 241         return status;
 242
 243     return _cairo_filler_ra_close (&filler);
 244 }
 245
 246 cairo_status_t
 247 _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
 248                                  cairo_fill_rule_t fill_rule,
 249                                  double tolerance,
 250                                  cairo_traps_t *traps)
 251 {
 252     cairo_polygon_t polygon;
 253     cairo_status_t status;
 254
 255     if (_cairo_path_fixed_fill_is_empty (path))
 256         return CAIRO_STATUS_SUCCESS;
 257
 258     _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
 259     status = _cairo_path_fixed_fill_to_polygon (path, tolerance, &polygon);
 260     if (unlikely (status || polygon.num_edges == 0))
 261         goto CLEANUP;
 262
 263     status = _cairo_bentley_ottmann_tessellate_polygon (traps,
 264                                                         &polygon, fill_rule);
 265
 266   CLEANUP:
 267     _cairo_polygon_fini (&polygon);
 268     return status;
 269 }
 270
 271 static cairo_status_t
 272 _cairo_path_fixed_fill_rectilinear_tessellate_to_boxes (const cairo_path_fixed_t *path,
 273                                                         cairo_fill_rule_t fill_rule,
 274                                                         cairo_antialias_t antialias,
 275                                                         cairo_boxes_t *boxes)
 276 {
 277     cairo_polygon_t polygon;
 278     cairo_status_t status;
 279
 280     _cairo_polygon_init (&polygon, boxes->limits, boxes->num_limits);
 281     boxes->num_limits = 0;
 282
 283     /* tolerance will be ignored as the path is rectilinear */
 284     status = _cairo_path_fixed_fill_rectilinear_to_polygon (path, antialias, &polygon);
 285     if (likely (status == CAIRO_STATUS_SUCCESS)) {
 286         status =
 287             _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (&polygon,
 288                                                                             fill_rule,
 289                                                                             boxes);
 290     }
 291
 292     _cairo_polygon_fini (&polygon);
 293
 294     return status;
 295 }
 296
 297 cairo_status_t
 298 _cairo_path_fixed_fill_rectilinear_to_boxes (const cairo_path_fixed_t *path,
 299                                              cairo_fill_rule_t fill_rule,
 300                                              cairo_antialias_t antialias,
 301                                              cairo_boxes_t *boxes)
 302 {
 303     cairo_path_fixed_iter_t iter;
 304     cairo_status_t status;
 305     cairo_box_t box;
 306
 307     if (_cairo_path_fixed_is_box (path, &box))
 308         return _cairo_boxes_add (boxes, antialias, &box);
 309
 310     _cairo_path_fixed_iter_init (&iter, path);
 311     while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
 312         if (box.p1.y == box.p2.y || box.p1.x == box.p2.x)
 313             continue;
 314
 315         if (box.p1.y > box.p2.y) {
 316             cairo_fixed_t t;
 317
 318             t = box.p1.y;
 319             box.p1.y = box.p2.y;
 320             box.p2.y = t;
 321
 322             t = box.p1.x;
 323             box.p1.x = box.p2.x;
 324             box.p2.x = t;
 325         }
 326
 327         status = _cairo_boxes_add (boxes, antialias, &box);
 328         if (unlikely (status))
 329             return status;
 330     }
 331
 332     if (_cairo_path_fixed_iter_at_end (&iter))
 333         return _cairo_bentley_ottmann_tessellate_boxes (boxes, fill_rule, boxes);
 334
 335     /* path is not rectangular, try extracting clipped rectilinear edges */
 336     _cairo_boxes_clear (boxes);
 337     return _cairo_path_fixed_fill_rectilinear_tessellate_to_boxes (path,
 338                                                                    fill_rule,
 339                                                                    antialias,
 340                                                                    boxes);
 341 }
 342
 343 cairo_status_t
 344 _cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t *path,
 345                                              cairo_fill_rule_t        fill_rule,
 346                                              cairo_antialias_t        antialias,
 347                                              cairo_traps_t            *traps)
 348 {
 349     cairo_box_t box;
 350     cairo_status_t status;
 351
 352     traps->is_rectilinear = TRUE;
 353     traps->is_rectangular = TRUE;
 354
 355     if (_cairo_path_fixed_is_box (path, &box)) {
 356         if (antialias == CAIRO_ANTIALIAS_NONE) {
 357             box.p1.x = _cairo_fixed_round_down (box.p1.x);
 358             box.p1.y = _cairo_fixed_round_down (box.p1.y);
 359             box.p2.x = _cairo_fixed_round_down (box.p2.x);
 360             box.p2.y = _cairo_fixed_round_down (box.p2.y);
 361         }
 362         return _cairo_traps_tessellate_rectangle (traps, &box.p1, &box.p2);
 363     } else {
 364         cairo_path_fixed_iter_t iter;
 365
 366         _cairo_path_fixed_iter_init (&iter, path);
 367         while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
 368             if (box.p1.y > box.p2.y) {
 369                 cairo_fixed_t t;
 370
 371                 t = box.p1.y;
 372                 box.p1.y = box.p2.y;
 373                 box.p2.y = t;
 374
 375                 t = box.p1.x;
 376                 box.p1.x = box.p2.x;
 377                 box.p2.x = t;
 378             }
 379
 380             if (antialias == CAIRO_ANTIALIAS_NONE) {
 381                 box.p1.x = _cairo_fixed_round_down (box.p1.x);
 382                 box.p1.y = _cairo_fixed_round_down (box.p1.y);
 383                 box.p2.x = _cairo_fixed_round_down (box.p2.x);
 384                 box.p2.y = _cairo_fixed_round_down (box.p2.y);
 385             }
 386
 387             status = _cairo_traps_tessellate_rectangle (traps,
 388                                                         &box.p1, &box.p2);
 389             if (unlikely (status)) {
 390                 _cairo_traps_clear (traps);
 391                 return status;
 392             }
 393         }
 394
 395         if (_cairo_path_fixed_iter_at_end (&iter))
 396             return _cairo_bentley_ottmann_tessellate_rectangular_traps (traps, fill_rule);
 397
 398         _cairo_traps_clear (traps);
 399         return CAIRO_INT_STATUS_UNSUPPORTED;
 400     }
 401 }