src/cairo-polygon.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
  40 #include "cairo-boxes-private.h"
  41 #include "cairo-contour-private.h"
  42 #include "cairo-error-private.h"
  43
  44 #define DEBUG_POLYGON 0
  45
  46 #if DEBUG_POLYGON && !NDEBUG
  47 static void
  48 assert_last_edge_is_valid(cairo_polygon_t *polygon,
  49                           const cairo_box_t *limit)
  50 {
  51     cairo_edge_t *edge;
  52     cairo_fixed_t x;
  53
  54     edge = &polygon->edges[polygon->num_edges-1];
  55
  56     assert (edge->bottom > edge->top);
  57     assert (edge->top >= limit->p1.y);
  58     assert (edge->bottom <= limit->p2.y);
  59
  60     x = _cairo_edge_compute_intersection_x_for_y (&edge->line.p1,
  61                                                   &edge->line.p2,
  62                                                   edge->top);
  63     assert (x >= limit->p1.x);
  64     assert (x <= limit->p2.x);
  65
  66     x = _cairo_edge_compute_intersection_x_for_y (&edge->line.p1,
  67                                                   &edge->line.p2,
  68                                                   edge->bottom);
  69     assert (x >= limit->p1.x);
  70     assert (x <= limit->p2.x);
  71 }
  72 #else
  73 #define assert_last_edge_is_valid(p, l)
  74 #endif
  75
  76 static void
  77 _cairo_polygon_add_edge (cairo_polygon_t *polygon,
  78                          const cairo_point_t *p1,
  79                          const cairo_point_t *p2,
  80                          int dir);
  81
  82 void
  83 _cairo_polygon_limit (cairo_polygon_t *polygon,
  84                      const cairo_box_t *limits,
  85                      int num_limits)
  86 {
  87     int n;
  88
  89     polygon->limits = limits;
  90     polygon->num_limits = num_limits;
  91
  92     if (polygon->num_limits) {
  93         polygon->limit = limits[0];
  94         for (n = 1; n < num_limits; n++) {
  95             if (limits[n].p1.x < polygon->limit.p1.x)
  96                 polygon->limit.p1.x = limits[n].p1.x;
  97
  98             if (limits[n].p1.y < polygon->limit.p1.y)
  99                 polygon->limit.p1.y = limits[n].p1.y;
 100
 101             if (limits[n].p2.x > polygon->limit.p2.x)
 102                 polygon->limit.p2.x = limits[n].p2.x;
 103
 104             if (limits[n].p2.y > polygon->limit.p2.y)
 105                 polygon->limit.p2.y = limits[n].p2.y;
 106         }
 107     }
 108 }
 109
 110 void
 111 _cairo_polygon_limit_to_clip (cairo_polygon_t *polygon,
 112                               const cairo_clip_t *clip)
 113 {
 114     if (clip)
 115         _cairo_polygon_limit (polygon, clip->boxes, clip->num_boxes);
 116     else
 117         _cairo_polygon_limit (polygon, 0, 0);
 118 }
 119
 120 void
 121 _cairo_polygon_init (cairo_polygon_t *polygon,
 122                      const cairo_box_t *limits,
 123                      int num_limits)
 124 {
 125     VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
 126
 127     polygon->status = CAIRO_STATUS_SUCCESS;
 128
 129     polygon->num_edges = 0;
 130
 131     polygon->edges = polygon->edges_embedded;
 132     polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
 133
 134     polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
 135     polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
 136
 137     _cairo_polygon_limit (polygon, limits, num_limits);
 138 }
 139
 140 void
 141 _cairo_polygon_init_with_clip (cairo_polygon_t *polygon,
 142                                const cairo_clip_t *clip)
 143 {
 144     if (clip)
 145         _cairo_polygon_init (polygon, clip->boxes, clip->num_boxes);
 146     else
 147         _cairo_polygon_init (polygon, 0, 0);
 148 }
 149
 150 cairo_status_t
 151 _cairo_polygon_init_boxes (cairo_polygon_t *polygon,
 152                            const cairo_boxes_t *boxes)
 153 {
 154     const struct _cairo_boxes_chunk *chunk;
 155     int i;
 156
 157     VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
 158
 159     polygon->status = CAIRO_STATUS_SUCCESS;
 160
 161     polygon->num_edges = 0;
 162
 163     polygon->edges = polygon->edges_embedded;
 164     polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
 165     if (boxes->num_boxes > ARRAY_LENGTH (polygon->edges_embedded)/2) {
 166         polygon->edges_size = 2 * boxes->num_boxes;
 167         polygon->edges = _cairo_malloc_ab (polygon->edges_size,
 168                                            2*sizeof(cairo_edge_t));
 169         if (unlikely (polygon->edges == NULL))
 170             return polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 171     }
 172
 173     polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
 174     polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
 175
 176     polygon->limits = NULL;
 177     polygon->num_limits = 0;
 178
 179     for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 180         for (i = 0; i < chunk->count; i++) {
 181             cairo_point_t p1, p2;
 182
 183             p1 = chunk->base[i].p1;
 184             p2.x = p1.x;
 185             p2.y = chunk->base[i].p2.y;
 186             _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
 187
 188             p1 = chunk->base[i].p2;
 189             p2.x = p1.x;
 190             p2.y = chunk->base[i].p1.y;
 191             _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
 192         }
 193     }
 194
 195     return polygon->status;
 196 }
 197
 198 cairo_status_t
 199 _cairo_polygon_init_box_array (cairo_polygon_t *polygon,
 200                                cairo_box_t *boxes,
 201                                int num_boxes)
 202 {
 203     int i;
 204
 205     VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
 206
 207     polygon->status = CAIRO_STATUS_SUCCESS;
 208
 209     polygon->num_edges = 0;
 210
 211     polygon->edges = polygon->edges_embedded;
 212     polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
 213     if (num_boxes > ARRAY_LENGTH (polygon->edges_embedded)/2) {
 214         polygon->edges_size = 2 * num_boxes;
 215         polygon->edges = _cairo_malloc_ab (polygon->edges_size,
 216                                            2*sizeof(cairo_edge_t));
 217         if (unlikely (polygon->edges == NULL))
 218             return polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 219     }
 220
 221     polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
 222     polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
 223
 224     polygon->limits = NULL;
 225     polygon->num_limits = 0;
 226
 227     for (i = 0; i < num_boxes; i++) {
 228         cairo_point_t p1, p2;
 229
 230         p1 = boxes[i].p1;
 231         p2.x = p1.x;
 232         p2.y = boxes[i].p2.y;
 233         _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
 234
 235         p1 = boxes[i].p2;
 236         p2.x = p1.x;
 237         p2.y = boxes[i].p1.y;
 238         _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
 239     }
 240
 241     return polygon->status;
 242 }
 243
 244
 245 void
 246 _cairo_polygon_fini (cairo_polygon_t *polygon)
 247 {
 248     if (polygon->edges != polygon->edges_embedded)
 249         free (polygon->edges);
 250
 251     VG (VALGRIND_MAKE_MEM_NOACCESS (polygon, sizeof (cairo_polygon_t)));
 252 }
 253
 254 /* make room for at least one more edge */
 255 static cairo_bool_t
 256 _cairo_polygon_grow (cairo_polygon_t *polygon)
 257 {
 258     cairo_edge_t *new_edges;
 259     int old_size = polygon->edges_size;
 260     int new_size = 4 * old_size;
 261
 262     if (CAIRO_INJECT_FAULT ()) {
 263         polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 264         return FALSE;
 265     }
 266
 267     if (polygon->edges == polygon->edges_embedded) {
 268         new_edges = _cairo_malloc_ab (new_size, sizeof (cairo_edge_t));
 269         if (new_edges != NULL)
 270             memcpy (new_edges, polygon->edges, old_size * sizeof (cairo_edge_t));
 271     } else {
 272         new_edges = _cairo_realloc_ab (polygon->edges,
 273                                        new_size, sizeof (cairo_edge_t));
 274     }
 275
 276     if (unlikely (new_edges == NULL)) {
 277         polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
 278         return FALSE;
 279     }
 280
 281     polygon->edges = new_edges;
 282     polygon->edges_size = new_size;
 283
 284     return TRUE;
 285 }
 286
 287 static void
 288 _add_edge (cairo_polygon_t *polygon,
 289            const cairo_point_t *p1,
 290            const cairo_point_t *p2,
 291            int top, int bottom,
 292            int dir)
 293 {
 294     cairo_edge_t *edge;
 295
 296     assert (top < bottom);
 297
 298     if (unlikely (polygon->num_edges == polygon->edges_size)) {
 299         if (! _cairo_polygon_grow (polygon))
 300             return;
 301     }
 302
 303     edge = &polygon->edges[polygon->num_edges++];
 304     edge->line.p1 = *p1;
 305     edge->line.p2 = *p2;
 306     edge->top = top;
 307     edge->bottom = bottom;
 308     edge->dir = dir;
 309
 310     if (top < polygon->extents.p1.y)
 311         polygon->extents.p1.y = top;
 312     if (bottom > polygon->extents.p2.y)
 313         polygon->extents.p2.y = bottom;
 314
 315     if (p1->x < polygon->extents.p1.x || p1->x > polygon->extents.p2.x) {
 316         cairo_fixed_t x = p1->x;
 317         if (top != p1->y)
 318             x = _cairo_edge_compute_intersection_x_for_y (p1, p2, top);
 319         if (x < polygon->extents.p1.x)
 320             polygon->extents.p1.x = x;
 321         if (x > polygon->extents.p2.x)
 322             polygon->extents.p2.x = x;
 323     }
 324
 325     if (p2->x < polygon->extents.p1.x || p2->x > polygon->extents.p2.x) {
 326         cairo_fixed_t x = p2->x;
 327         if (bottom != p2->y)
 328             x = _cairo_edge_compute_intersection_x_for_y (p1, p2, bottom);
 329         if (x < polygon->extents.p1.x)
 330             polygon->extents.p1.x = x;
 331         if (x > polygon->extents.p2.x)
 332             polygon->extents.p2.x = x;
 333     }
 334 }
 335
 336 static void
 337 _add_clipped_edge (cairo_polygon_t *polygon,
 338                    const cairo_point_t *p1,
 339                    const cairo_point_t *p2,
 340                    const int top, const int bottom,
 341                    const int dir)
 342 {
 343     cairo_point_t bot_left, top_right;
 344     cairo_fixed_t top_y, bot_y;
 345     int n;
 346
 347     for (n = 0; n < polygon->num_limits; n++) {
 348         const cairo_box_t *limits = &polygon->limits[n];
 349         cairo_fixed_t pleft, pright;
 350
 351         if (top >= limits->p2.y)
 352             continue;
 353         if (bottom <= limits->p1.y)
 354             continue;
 355
 356         bot_left.x = limits->p1.x;
 357         bot_left.y = limits->p2.y;
 358
 359         top_right.x = limits->p2.x;
 360         top_right.y = limits->p1.y;
 361
 362         /* The useful region */
 363         top_y = MAX (top, limits->p1.y);
 364         bot_y = MIN (bottom, limits->p2.y);
 365
 366         /* The projection of the edge on the horizontal axis */
 367         pleft = MIN (p1->x, p2->x);
 368         pright = MAX (p1->x, p2->x);
 369
 370         if (limits->p1.x <= pleft && pright <= limits->p2.x) {
 371             /* Projection of the edge completely contained in the box:
 372              * clip vertically by restricting top and bottom */
 373
 374             _add_edge (polygon, p1, p2, top_y, bot_y, dir);
 375             assert_last_edge_is_valid (polygon, limits);
 376         } else if (pright <= limits->p1.x) {
 377             /* Projection of the edge to the left of the box:
 378              * replace with the left side of the box (clipped top/bottom) */
 379
 380             _add_edge (polygon, &limits->p1, &bot_left, top_y, bot_y, dir);
 381             assert_last_edge_is_valid (polygon, limits);
 382         } else if (limits->p2.x <= pleft) {
 383             /* Projection of the edge to the right of the box:
 384              * replace with the right side of the box (clipped top/bottom) */
 385
 386             _add_edge (polygon, &top_right, &limits->p2, top_y, bot_y, dir);
 387             assert_last_edge_is_valid (polygon, limits);
 388         } else {
 389             /* The edge and the box intersect in a generic way */
 390             cairo_fixed_t left_y, right_y;
 391             cairo_bool_t top_left_to_bottom_right;
 392
 393             /*
 394              * The edge intersects the lines corresponding to the left
 395              * and right sides of the limit box at left_y and right_y,
 396              * but we need to add edges for the range from top_y to
 397              * bot_y.
 398              *
 399              * For both intersections, there are three cases:
 400              *
 401              *  1) It is outside the vertical range of the limit
 402              *     box. In this case we can simply further clip the
 403              *     edge we will be emitting (i.e. restrict its
 404              *     top/bottom limits to those of the limit box).
 405              *
 406              *  2) It is inside the vertical range of the limit
 407              *     box. In this case, we need to add the vertical edge
 408              *     connecting the correct vertex to the intersection,
 409              *     in order to preserve the winding count.
 410              *
 411              *  3) It is exactly on the box. In this case, do nothing.
 412              *
 413              * These operations restrict the active range (stored in
 414              * top_y/bot_y) so that the p1-p2 edge is completely
 415              * inside the box if it is clipped to this vertical range.
 416              */
 417
 418             top_left_to_bottom_right = (p1->x <= p2->x) == (p1->y <= p2->y);
 419             if (top_left_to_bottom_right) {
 420                 if (pleft >= limits->p1.x) {
 421                     left_y = top_y;
 422                 } else {
 423                     left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 424                                                                        limits->p1.x);
 425                     if (_cairo_edge_compute_intersection_x_for_y (p1, p2, left_y) < limits->p1.x)
 426                         left_y++;
 427                 }
 428
 429                 left_y = MIN (left_y, bot_y);
 430                 if (top_y < left_y) {
 431                     _add_edge (polygon, &limits->p1, &bot_left,
 432                                top_y, left_y, dir);
 433                     assert_last_edge_is_valid (polygon, limits);
 434                     top_y = left_y;
 435                 }
 436
 437                 if (pright <= limits->p2.x) {
 438                     right_y = bot_y;
 439                 } else {
 440                     right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 441                                                                         limits->p2.x);
 442                     if (_cairo_edge_compute_intersection_x_for_y (p1, p2, right_y) > limits->p2.x)
 443                         right_y--;
 444                 }
 445
 446                 right_y = MAX (right_y, top_y);
 447                 if (bot_y > right_y) {
 448                     _add_edge (polygon, &top_right, &limits->p2,
 449                                right_y, bot_y, dir);
 450                     assert_last_edge_is_valid (polygon, limits);
 451                     bot_y = right_y;
 452                 }
 453             } else {
 454                 if (pright <= limits->p2.x) {
 455                     right_y = top_y;
 456                 } else {
 457                     right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 458                                                                         limits->p2.x);
 459                     if (_cairo_edge_compute_intersection_x_for_y (p1, p2, right_y) > limits->p2.x)
 460                         right_y++;
 461                 }
 462
 463                 right_y = MIN (right_y, bot_y);
 464                 if (top_y < right_y) {
 465                     _add_edge (polygon, &top_right, &limits->p2,
 466                                top_y, right_y, dir);
 467                     assert_last_edge_is_valid (polygon, limits);
 468                     top_y = right_y;
 469                 }
 470
 471                 if (pleft >= limits->p1.x) {
 472                     left_y = bot_y;
 473                 } else {
 474                     left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 475                                                                        limits->p1.x);
 476                     if (_cairo_edge_compute_intersection_x_for_y (p1, p2, left_y) < limits->p1.x)
 477                         left_y--;
 478                 }
 479
 480                 left_y = MAX (left_y, top_y);
 481                 if (bot_y > left_y) {
 482                     _add_edge (polygon, &limits->p1, &bot_left,
 483                                left_y, bot_y, dir);
 484                     assert_last_edge_is_valid (polygon, limits);
 485                     bot_y = left_y;
 486                 }
 487             }
 488
 489             if (top_y != bot_y) {
 490                 _add_edge (polygon, p1, p2, top_y, bot_y, dir);
 491                 assert_last_edge_is_valid (polygon, limits);
 492             }
 493         }
 494     }
 495 }
 496
 497 static void
 498 _cairo_polygon_add_edge (cairo_polygon_t *polygon,
 499                          const cairo_point_t *p1,
 500                          const cairo_point_t *p2,
 501                          int dir)
 502 {
 503     /* drop horizontal edges */
 504     if (p1->y == p2->y)
 505         return;
 506
 507     if (p1->y > p2->y) {
 508         const cairo_point_t *t;
 509         t = p1, p1 = p2, p2 = t;
 510         dir = -dir;
 511     }
 512
 513     if (polygon->num_limits) {
 514         if (p2->y <= polygon->limit.p1.y)
 515             return;
 516
 517         if (p1->y >= polygon->limit.p2.y)
 518             return;
 519
 520         _add_clipped_edge (polygon, p1, p2, p1->y, p2->y, dir);
 521     } else
 522         _add_edge (polygon, p1, p2, p1->y, p2->y, dir);
 523 }
 524
 525 cairo_status_t
 526 _cairo_polygon_add_external_edge (void *polygon,
 527                                   const cairo_point_t *p1,
 528                                   const cairo_point_t *p2)
 529 {
 530     _cairo_polygon_add_edge (polygon, p1, p2, 1);
 531     return _cairo_polygon_status (polygon);
 532 }
 533
 534 cairo_status_t
 535 _cairo_polygon_add_line (cairo_polygon_t *polygon,
 536                          const cairo_line_t *line,
 537                          int top, int bottom,
 538                          int dir)
 539 {
 540     /* drop horizontal edges */
 541     if (line->p1.y == line->p2.y)
 542         return CAIRO_STATUS_SUCCESS;
 543
 544     if (bottom <= top)
 545         return CAIRO_STATUS_SUCCESS;
 546
 547     if (polygon->num_limits) {
 548         if (line->p2.y <= polygon->limit.p1.y)
 549             return CAIRO_STATUS_SUCCESS;
 550
 551         if (line->p1.y >= polygon->limit.p2.y)
 552             return CAIRO_STATUS_SUCCESS;
 553
 554         _add_clipped_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
 555     } else
 556         _add_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
 557
 558     return polygon->status;
 559 }
 560
 561 cairo_status_t
 562 _cairo_polygon_add_contour (cairo_polygon_t *polygon,
 563                             const cairo_contour_t *contour)
 564 {
 565     const struct _cairo_contour_chain *chain;
 566     const cairo_point_t *prev = NULL;
 567     int i;
 568
 569     if (contour->chain.num_points <= 1)
 570         return CAIRO_INT_STATUS_SUCCESS;
 571
 572     prev = &contour->chain.points[0];
 573     for (chain = &contour->chain; chain; chain = chain->next) {
 574         for (i = 0; i < chain->num_points; i++) {
 575             _cairo_polygon_add_edge (polygon, prev, &chain->points[i],
 576                                      contour->direction);
 577             prev = &chain->points[i];
 578         }
 579     }
 580
 581     return polygon->status;
 582 }
 583
 584 void
 585 _cairo_polygon_translate (cairo_polygon_t *polygon, int dx, int dy)
 586 {
 587     int n;
 588
 589     dx = _cairo_fixed_from_int (dx);
 590     dy = _cairo_fixed_from_int (dy);
 591
 592     polygon->extents.p1.x += dx;
 593     polygon->extents.p2.x += dx;
 594     polygon->extents.p1.y += dy;
 595     polygon->extents.p2.y += dy;
 596
 597     for (n = 0; n < polygon->num_edges; n++) {
 598         cairo_edge_t *e = &polygon->edges[n];
 599
 600         e->top += dy;
 601         e->bottom += dy;
 602
 603         e->line.p1.x += dx;
 604         e->line.p2.x += dx;
 605         e->line.p1.y += dy;
 606         e->line.p2.y += dy;
 607     }
 608 }