src/cairo-bentley-ottmann-rectilinear.c

   1 /*
   2  * Copyright © 2004 Carl Worth
   3  * Copyright © 2006 Red Hat, Inc.
   4  * Copyright © 2008 Chris Wilson
   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 Carl Worth
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  *      Chris Wilson <chris@chris-wilson.co.uk>
  36  */
  37
  38 /* Provide definitions for standalone compilation */
  39 #include "cairoint.h"
  40
  41 #include "cairo-boxes-private.h"
  42 #include "cairo-combsort-inline.h"
  43 #include "cairo-error-private.h"
  44 #include "cairo-traps-private.h"
  45
  46 typedef struct _cairo_bo_edge cairo_bo_edge_t;
  47 typedef struct _cairo_bo_trap cairo_bo_trap_t;
  48
  49 /* A deferred trapezoid of an edge */
  50 struct _cairo_bo_trap {
  51     cairo_bo_edge_t *right;
  52     int32_t top;
  53 };
  54
  55 struct _cairo_bo_edge {
  56     cairo_edge_t edge;
  57     cairo_bo_edge_t *prev;
  58     cairo_bo_edge_t *next;
  59     cairo_bo_trap_t deferred_trap;
  60 };
  61
  62 typedef enum {
  63     CAIRO_BO_EVENT_TYPE_START,
  64     CAIRO_BO_EVENT_TYPE_STOP
  65 } cairo_bo_event_type_t;
  66
  67 typedef struct _cairo_bo_event {
  68     cairo_bo_event_type_t type;
  69     cairo_point_t point;
  70     cairo_bo_edge_t *edge;
  71 } cairo_bo_event_t;
  72
  73 typedef struct _cairo_bo_sweep_line {
  74     cairo_bo_event_t **events;
  75     cairo_bo_edge_t *head;
  76     cairo_bo_edge_t *stopped;
  77     int32_t current_y;
  78     cairo_bo_edge_t *current_edge;
  79 } cairo_bo_sweep_line_t;
  80
  81 static inline int
  82 _cairo_point_compare (const cairo_point_t *a,
  83                       const cairo_point_t *b)
  84 {
  85     int cmp;
  86
  87     cmp = a->y - b->y;
  88     if (likely (cmp))
  89         return cmp;
  90
  91     return a->x - b->x;
  92 }
  93
  94 static inline int
  95 _cairo_bo_edge_compare (const cairo_bo_edge_t   *a,
  96                         const cairo_bo_edge_t   *b)
  97 {
  98     int cmp;
  99
 100     cmp = a->edge.line.p1.x - b->edge.line.p1.x;
 101     if (likely (cmp))
 102         return cmp;
 103
 104     return b->edge.bottom - a->edge.bottom;
 105 }
 106
 107 static inline int
 108 cairo_bo_event_compare (const cairo_bo_event_t *a,
 109                         const cairo_bo_event_t *b)
 110 {
 111     int cmp;
 112
 113     cmp = _cairo_point_compare (&a->point, &b->point);
 114     if (likely (cmp))
 115         return cmp;
 116
 117     cmp = a->type - b->type;
 118     if (cmp)
 119         return cmp;
 120
 121     return a - b;
 122 }
 123
 124 static inline cairo_bo_event_t *
 125 _cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
 126 {
 127     return *sweep_line->events++;
 128 }
 129
 130 CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
 131                         cairo_bo_event_t *,
 132                         cairo_bo_event_compare)
 133
 134 static void
 135 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
 136                            cairo_bo_event_t     **events,
 137                            int                    num_events)
 138 {
 139     _cairo_bo_event_queue_sort (events, num_events);
 140     events[num_events] = NULL;
 141     sweep_line->events = events;
 142
 143     sweep_line->head = NULL;
 144     sweep_line->current_y = INT32_MIN;
 145     sweep_line->current_edge = NULL;
 146 }
 147
 148 static void
 149 _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
 150                              cairo_bo_edge_t            *edge)
 151 {
 152     if (sweep_line->current_edge != NULL) {
 153         cairo_bo_edge_t *prev, *next;
 154         int cmp;
 155
 156         cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
 157         if (cmp < 0) {
 158             prev = sweep_line->current_edge;
 159             next = prev->next;
 160             while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
 161                 prev = next, next = prev->next;
 162
 163             prev->next = edge;
 164             edge->prev = prev;
 165             edge->next = next;
 166             if (next != NULL)
 167                 next->prev = edge;
 168         } else if (cmp > 0) {
 169             next = sweep_line->current_edge;
 170             prev = next->prev;
 171             while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
 172                 next = prev, prev = next->prev;
 173
 174             next->prev = edge;
 175             edge->next = next;
 176             edge->prev = prev;
 177             if (prev != NULL)
 178                 prev->next = edge;
 179             else
 180                 sweep_line->head = edge;
 181         } else {
 182             prev = sweep_line->current_edge;
 183             edge->prev = prev;
 184             edge->next = prev->next;
 185             if (prev->next != NULL)
 186                 prev->next->prev = edge;
 187             prev->next = edge;
 188         }
 189     } else {
 190         sweep_line->head = edge;
 191     }
 192
 193     sweep_line->current_edge = edge;
 194 }
 195
 196 static void
 197 _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
 198                              cairo_bo_edge_t    *edge)
 199 {
 200     if (edge->prev != NULL)
 201         edge->prev->next = edge->next;
 202     else
 203         sweep_line->head = edge->next;
 204
 205     if (edge->next != NULL)
 206         edge->next->prev = edge->prev;
 207
 208     if (sweep_line->current_edge == edge)
 209         sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
 210 }
 211
 212 static inline cairo_bool_t
 213 edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
 214 {
 215     return a->edge.line.p1.x == b->edge.line.p1.x;
 216 }
 217
 218 static cairo_status_t
 219 _cairo_bo_edge_end_trap (cairo_bo_edge_t        *left,
 220                          int32_t                 bot,
 221                          cairo_bool_t            do_traps,
 222                          void                   *container)
 223 {
 224     cairo_bo_trap_t *trap = &left->deferred_trap;
 225     cairo_status_t status = CAIRO_STATUS_SUCCESS;
 226
 227     /* Only emit (trivial) non-degenerate trapezoids with positive height. */
 228     if (likely (trap->top < bot)) {
 229         if (do_traps) {
 230             _cairo_traps_add_trap (container,
 231                                    trap->top, bot,
 232                                    &left->edge.line, &trap->right->edge.line);
 233             status =  _cairo_traps_status ((cairo_traps_t *) container);
 234         } else {
 235             cairo_box_t box;
 236
 237             box.p1.x = left->edge.line.p1.x;
 238             box.p1.y = trap->top;
 239             box.p2.x = trap->right->edge.line.p1.x;
 240             box.p2.y = bot;
 241             status = _cairo_boxes_add (container, CAIRO_ANTIALIAS_DEFAULT, &box);
 242         }
 243     }
 244
 245     trap->right = NULL;
 246
 247     return status;
 248 }
 249
 250 /* Start a new trapezoid at the given top y coordinate, whose edges
 251  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
 252  * then either add it to the traps in `traps', if the trapezoid's
 253  * right edge differs from `edge->next', or do nothing if the new
 254  * trapezoid would be a continuation of the existing one. */
 255 static inline cairo_status_t
 256 _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t  *left,
 257                                        cairo_bo_edge_t  *right,
 258                                        int               top,
 259                                        cairo_bool_t      do_traps,
 260                                        void             *container)
 261 {
 262     cairo_status_t status;
 263
 264     if (left->deferred_trap.right == right)
 265         return CAIRO_STATUS_SUCCESS;
 266
 267     if (left->deferred_trap.right != NULL) {
 268         if (right != NULL && edges_collinear (left->deferred_trap.right, right))
 269         {
 270             /* continuation on right, so just swap edges */
 271             left->deferred_trap.right = right;
 272             return CAIRO_STATUS_SUCCESS;
 273         }
 274
 275         status = _cairo_bo_edge_end_trap (left, top, do_traps, container);
 276         if (unlikely (status))
 277             return status;
 278     }
 279
 280     if (right != NULL && ! edges_collinear (left, right)) {
 281         left->deferred_trap.top = top;
 282         left->deferred_trap.right = right;
 283     }
 284
 285     return CAIRO_STATUS_SUCCESS;
 286 }
 287
 288 static inline cairo_status_t
 289 _active_edges_to_traps (cairo_bo_edge_t         *left,
 290                         int32_t                  top,
 291                         cairo_fill_rule_t        fill_rule,
 292                         cairo_bool_t             do_traps,
 293                         void                    *container)
 294 {
 295     cairo_bo_edge_t *right;
 296     cairo_status_t status;
 297
 298     if (fill_rule == CAIRO_FILL_RULE_WINDING) {
 299         while (left != NULL) {
 300             int in_out;
 301
 302             /* Greedily search for the closing edge, so that we generate the
 303              * maximal span width with the minimal number of trapezoids.
 304              */
 305             in_out = left->edge.dir;
 306
 307             /* Check if there is a co-linear edge with an existing trap */
 308             right = left->next;
 309             if (left->deferred_trap.right == NULL) {
 310                 while (right != NULL && right->deferred_trap.right == NULL)
 311                     right = right->next;
 312
 313                 if (right != NULL && edges_collinear (left, right)) {
 314                     /* continuation on left */
 315                     left->deferred_trap = right->deferred_trap;
 316                     right->deferred_trap.right = NULL;
 317                 }
 318             }
 319
 320             /* End all subsumed traps */
 321             right = left->next;
 322             while (right != NULL) {
 323                 if (right->deferred_trap.right != NULL) {
 324                     status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
 325                     if (unlikely (status))
 326                         return status;
 327                 }
 328
 329                 in_out += right->edge.dir;
 330                 if (in_out == 0) {
 331                     /* skip co-linear edges */
 332                     if (right->next == NULL ||
 333                         ! edges_collinear (right, right->next))
 334                     {
 335                         break;
 336                     }
 337                 }
 338
 339                 right = right->next;
 340             }
 341
 342             status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
 343                                                             do_traps, container);
 344             if (unlikely (status))
 345                 return status;
 346
 347             left = right;
 348             if (left != NULL)
 349                 left = left->next;
 350         }
 351     } else {
 352         while (left != NULL) {
 353             int in_out = 0;
 354
 355             right = left->next;
 356             while (right != NULL) {
 357                 if (right->deferred_trap.right != NULL) {
 358                     status = _cairo_bo_edge_end_trap (right, top, do_traps, container);
 359                     if (unlikely (status))
 360                         return status;
 361                 }
 362
 363                 if ((in_out++ & 1) == 0) {
 364                     cairo_bo_edge_t *next;
 365                     cairo_bool_t skip = FALSE;
 366
 367                     /* skip co-linear edges */
 368                     next = right->next;
 369                     if (next != NULL)
 370                         skip = edges_collinear (right, next);
 371
 372                     if (! skip)
 373                         break;
 374                 }
 375
 376                 right = right->next;
 377             }
 378
 379             status = _cairo_bo_edge_start_or_continue_trap (left, right, top,
 380                                                             do_traps, container);
 381             if (unlikely (status))
 382                 return status;
 383
 384             left = right;
 385             if (left != NULL)
 386                 left = left->next;
 387         }
 388     }
 389
 390     return CAIRO_STATUS_SUCCESS;
 391 }
 392
 393 static cairo_status_t
 394 _cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
 395                                                int                       num_events,
 396                                                cairo_fill_rule_t         fill_rule,
 397                                                cairo_bool_t              do_traps,
 398                                                void                     *container)
 399 {
 400     cairo_bo_sweep_line_t sweep_line;
 401     cairo_bo_event_t *event;
 402     cairo_status_t status;
 403
 404     _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
 405
 406     while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
 407         if (event->point.y != sweep_line.current_y) {
 408             status = _active_edges_to_traps (sweep_line.head,
 409                                              sweep_line.current_y,
 410                                              fill_rule, do_traps, container);
 411             if (unlikely (status))
 412                 return status;
 413
 414             sweep_line.current_y = event->point.y;
 415         }
 416
 417         switch (event->type) {
 418         case CAIRO_BO_EVENT_TYPE_START:
 419             _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
 420             break;
 421
 422         case CAIRO_BO_EVENT_TYPE_STOP:
 423             _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
 424
 425             if (event->edge->deferred_trap.right != NULL) {
 426                 status = _cairo_bo_edge_end_trap (event->edge,
 427                                                   sweep_line.current_y,
 428                                                   do_traps, container);
 429                 if (unlikely (status))
 430                     return status;
 431             }
 432
 433             break;
 434         }
 435     }
 436
 437     return CAIRO_STATUS_SUCCESS;
 438 }
 439
 440 cairo_status_t
 441 _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t *polygon,
 442                                                                 cairo_fill_rule_t         fill_rule,
 443                                                                 cairo_boxes_t *boxes)
 444 {
 445     cairo_status_t status;
 446     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
 447     cairo_bo_event_t *events;
 448     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
 449     cairo_bo_event_t **event_ptrs;
 450     cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
 451     cairo_bo_edge_t *edges;
 452     int num_events;
 453     int i, j;
 454
 455     if (unlikely (polygon->num_edges == 0))
 456         return CAIRO_STATUS_SUCCESS;
 457
 458     num_events = 2 * polygon->num_edges;
 459
 460     events = stack_events;
 461     event_ptrs = stack_event_ptrs;
 462     edges = stack_edges;
 463     if (num_events > ARRAY_LENGTH (stack_events)) {
 464         events = _cairo_malloc_ab_plus_c (num_events,
 465                                           sizeof (cairo_bo_event_t) +
 466                                           sizeof (cairo_bo_edge_t) +
 467                                           sizeof (cairo_bo_event_t *),
 468                                           sizeof (cairo_bo_event_t *));
 469         if (unlikely (events == NULL))
 470             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 471
 472         event_ptrs = (cairo_bo_event_t **) (events + num_events);
 473         edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
 474     }
 475
 476     for (i = j = 0; i < polygon->num_edges; i++) {
 477         edges[i].edge = polygon->edges[i];
 478         edges[i].deferred_trap.right = NULL;
 479         edges[i].prev = NULL;
 480         edges[i].next = NULL;
 481
 482         event_ptrs[j] = &events[j];
 483         events[j].type = CAIRO_BO_EVENT_TYPE_START;
 484         events[j].point.y = polygon->edges[i].top;
 485         events[j].point.x = polygon->edges[i].line.p1.x;
 486         events[j].edge = &edges[i];
 487         j++;
 488
 489         event_ptrs[j] = &events[j];
 490         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
 491         events[j].point.y = polygon->edges[i].bottom;
 492         events[j].point.x = polygon->edges[i].line.p1.x;
 493         events[j].edge = &edges[i];
 494         j++;
 495     }
 496
 497     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
 498                                                             fill_rule,
 499                                                             FALSE, boxes);
 500     if (events != stack_events)
 501         free (events);
 502
 503     return status;
 504 }
 505
 506 cairo_status_t
 507 _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
 508                                                      cairo_fill_rule_t fill_rule)
 509 {
 510     cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
 511     cairo_bo_event_t *events;
 512     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
 513     cairo_bo_event_t **event_ptrs;
 514     cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
 515     cairo_bo_edge_t *edges;
 516     cairo_status_t status;
 517     int i, j, k;
 518
 519     if (unlikely (traps->num_traps == 0))
 520         return CAIRO_STATUS_SUCCESS;
 521
 522     assert (traps->is_rectilinear);
 523
 524     i = 4 * traps->num_traps;
 525
 526     events = stack_events;
 527     event_ptrs = stack_event_ptrs;
 528     edges = stack_edges;
 529     if (i > ARRAY_LENGTH (stack_events)) {
 530         events = _cairo_malloc_ab_plus_c (i,
 531                                           sizeof (cairo_bo_event_t) +
 532                                           sizeof (cairo_bo_edge_t) +
 533                                           sizeof (cairo_bo_event_t *),
 534                                           sizeof (cairo_bo_event_t *));
 535         if (unlikely (events == NULL))
 536             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 537
 538         event_ptrs = (cairo_bo_event_t **) (events + i);
 539         edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
 540     }
 541
 542     for (i = j = k = 0; i < traps->num_traps; i++) {
 543         edges[k].edge.top = traps->traps[i].top;
 544         edges[k].edge.bottom = traps->traps[i].bottom;
 545         edges[k].edge.line = traps->traps[i].left;
 546         edges[k].edge.dir = 1;
 547         edges[k].deferred_trap.right = NULL;
 548         edges[k].prev = NULL;
 549         edges[k].next = NULL;
 550
 551         event_ptrs[j] = &events[j];
 552         events[j].type = CAIRO_BO_EVENT_TYPE_START;
 553         events[j].point.y = traps->traps[i].top;
 554         events[j].point.x = traps->traps[i].left.p1.x;
 555         events[j].edge = &edges[k];
 556         j++;
 557
 558         event_ptrs[j] = &events[j];
 559         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
 560         events[j].point.y = traps->traps[i].bottom;
 561         events[j].point.x = traps->traps[i].left.p1.x;
 562         events[j].edge = &edges[k];
 563         j++;
 564         k++;
 565
 566         edges[k].edge.top = traps->traps[i].top;
 567         edges[k].edge.bottom = traps->traps[i].bottom;
 568         edges[k].edge.line = traps->traps[i].right;
 569         edges[k].edge.dir = -1;
 570         edges[k].deferred_trap.right = NULL;
 571         edges[k].prev = NULL;
 572         edges[k].next = NULL;
 573
 574         event_ptrs[j] = &events[j];
 575         events[j].type = CAIRO_BO_EVENT_TYPE_START;
 576         events[j].point.y = traps->traps[i].top;
 577         events[j].point.x = traps->traps[i].right.p1.x;
 578         events[j].edge = &edges[k];
 579         j++;
 580
 581         event_ptrs[j] = &events[j];
 582         events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
 583         events[j].point.y = traps->traps[i].bottom;
 584         events[j].point.x = traps->traps[i].right.p1.x;
 585         events[j].edge = &edges[k];
 586         j++;
 587         k++;
 588     }
 589
 590     _cairo_traps_clear (traps);
 591     status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
 592                                                             fill_rule,
 593                                                             TRUE, traps);
 594     traps->is_rectilinear = TRUE;
 595
 596     if (events != stack_events)
 597         free (events);
 598
 599     return status;
 600 }