src/cairo-boxes-intersect.c

   1 /*
   2  * Copyright © 2004 Carl Worth
   3  * Copyright © 2006 Red Hat, Inc.
   4  * Copyright © 2009 Chris Wilson
   5  * Copyright © 2011 Intel Corporation
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it either under the terms of the GNU Lesser General Public
   9  * License version 2.1 as published by the Free Software Foundation
  10  * (the "LGPL") or, at your option, under the terms of the Mozilla
  11  * Public License Version 1.1 (the "MPL"). If you do not alter this
  12  * notice, a recipient may use your version of this file under either
  13  * the MPL or the LGPL.
  14  *
  15  * You should have received a copy of the LGPL along with this library
  16  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  18  * You should have received a copy of the MPL along with this library
  19  * in the file COPYING-MPL-1.1
  20  *
  21  * The contents of this file are subject to the Mozilla Public License
  22  * Version 1.1 (the "License"); you may not use this file except in
  23  * compliance with the License. You may obtain a copy of the License at
  24  * http://www.mozilla.org/MPL/
  25  *
  26  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  27  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  28  * the specific language governing rights and limitations.
  29  *
  30  * The Original Code is the cairo graphics library.
  31  *
  32  * The Initial Developer of the Original Code is Carl Worth
  33  *
  34  * Contributor(s):
  35  *      Carl D. Worth <cworth@cworth.org>
  36  *      Chris Wilson <chris@chris-wilson.co.uk>
  37  */
  38
  39 /* Provide definitions for standalone compilation */
  40 #include "cairoint.h"
  41
  42 #include "cairo-boxes-private.h"
  43 #include "cairo-error-private.h"
  44 #include "cairo-combsort-inline.h"
  45 #include "cairo-list-private.h"
  46
  47 #include <setjmp.h>
  48
  49 typedef struct _rectangle rectangle_t;
  50 typedef struct _edge edge_t;
  51
  52 struct _edge {
  53     edge_t *next, *prev;
  54     edge_t *right;
  55     cairo_fixed_t x, top;
  56     int a_or_b;
  57     int dir;
  58 };
  59
  60 struct _rectangle {
  61     edge_t left, right;
  62     int32_t top, bottom;
  63 };
  64
  65 #define UNROLL3(x) x x x
  66
  67 /* the parent is always given by index/2 */
  68 #define PQ_PARENT_INDEX(i) ((i) >> 1)
  69 #define PQ_FIRST_ENTRY 1
  70
  71 /* left and right children are index * 2 and (index * 2) +1 respectively */
  72 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
  73
  74 typedef struct _pqueue {
  75     int size, max_size;
  76
  77     rectangle_t **elements;
  78     rectangle_t *elements_embedded[1024];
  79 } pqueue_t;
  80
  81 typedef struct _sweep_line {
  82     rectangle_t **rectangles;
  83     pqueue_t pq;
  84     edge_t head, tail;
  85     edge_t *insert_left, *insert_right;
  86     int32_t current_y;
  87     int32_t last_y;
  88
  89     jmp_buf unwind;
  90 } sweep_line_t;
  91
  92 #define DEBUG_TRAPS 0
  93
  94 #if DEBUG_TRAPS
  95 static void
  96 dump_traps (cairo_traps_t *traps, const char *filename)
  97 {
  98     FILE *file;
  99     int n;
 100
 101     if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
 102         return;
 103
 104     file = fopen (filename, "a");
 105     if (file != NULL) {
 106         for (n = 0; n < traps->num_traps; n++) {
 107             fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
 108                      traps->traps[n].top,
 109                      traps->traps[n].bottom,
 110                      traps->traps[n].left.p1.x,
 111                      traps->traps[n].left.p1.y,
 112                      traps->traps[n].left.p2.x,
 113                      traps->traps[n].left.p2.y,
 114                      traps->traps[n].right.p1.x,
 115                      traps->traps[n].right.p1.y,
 116                      traps->traps[n].right.p2.x,
 117                      traps->traps[n].right.p2.y);
 118         }
 119         fprintf (file, "\n");
 120         fclose (file);
 121     }
 122 }
 123 #else
 124 #define dump_traps(traps, filename)
 125 #endif
 126
 127 static inline int
 128 rectangle_compare_start (const rectangle_t *a,
 129                          const rectangle_t *b)
 130 {
 131     return a->top - b->top;
 132 }
 133
 134 static inline int
 135 rectangle_compare_stop (const rectangle_t *a,
 136                          const rectangle_t *b)
 137 {
 138     return a->bottom - b->bottom;
 139 }
 140
 141 static inline void
 142 pqueue_init (pqueue_t *pq)
 143 {
 144     pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
 145     pq->size = 0;
 146
 147     pq->elements = pq->elements_embedded;
 148     pq->elements[PQ_FIRST_ENTRY] = NULL;
 149 }
 150
 151 static inline void
 152 pqueue_fini (pqueue_t *pq)
 153 {
 154     if (pq->elements != pq->elements_embedded)
 155         free (pq->elements);
 156 }
 157
 158 static cairo_bool_t
 159 pqueue_grow (pqueue_t *pq)
 160 {
 161     rectangle_t **new_elements;
 162     pq->max_size *= 2;
 163
 164     if (pq->elements == pq->elements_embedded) {
 165         new_elements = _cairo_malloc_ab (pq->max_size,
 166                                          sizeof (rectangle_t *));
 167         if (unlikely (new_elements == NULL))
 168             return FALSE;
 169
 170         memcpy (new_elements, pq->elements_embedded,
 171                 sizeof (pq->elements_embedded));
 172     } else {
 173         new_elements = _cairo_realloc_ab (pq->elements,
 174                                           pq->max_size,
 175                                           sizeof (rectangle_t *));
 176         if (unlikely (new_elements == NULL))
 177             return FALSE;
 178     }
 179
 180     pq->elements = new_elements;
 181     return TRUE;
 182 }
 183
 184 static inline void
 185 pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
 186 {
 187     rectangle_t **elements;
 188     int i, parent;
 189
 190     if (unlikely (sweep->pq.size + 1 == sweep->pq.max_size)) {
 191         if (unlikely (! pqueue_grow (&sweep->pq))) {
 192             longjmp (sweep->unwind,
 193                      _cairo_error (CAIRO_STATUS_NO_MEMORY));
 194         }
 195     }
 196
 197     elements = sweep->pq.elements;
 198     for (i = ++sweep->pq.size;
 199          i != PQ_FIRST_ENTRY &&
 200          rectangle_compare_stop (rectangle,
 201                                  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
 202          i = parent)
 203     {
 204         elements[i] = elements[parent];
 205     }
 206
 207     elements[i] = rectangle;
 208 }
 209
 210 static inline void
 211 pqueue_pop (pqueue_t *pq)
 212 {
 213     rectangle_t **elements = pq->elements;
 214     rectangle_t *tail;
 215     int child, i;
 216
 217     tail = elements[pq->size--];
 218     if (pq->size == 0) {
 219         elements[PQ_FIRST_ENTRY] = NULL;
 220         return;
 221     }
 222
 223     for (i = PQ_FIRST_ENTRY;
 224          (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
 225          i = child)
 226     {
 227         if (child != pq->size &&
 228             rectangle_compare_stop (elements[child+1],
 229                                     elements[child]) < 0)
 230         {
 231             child++;
 232         }
 233
 234         if (rectangle_compare_stop (elements[child], tail) >= 0)
 235             break;
 236
 237         elements[i] = elements[child];
 238     }
 239     elements[i] = tail;
 240 }
 241
 242 static inline rectangle_t *
 243 rectangle_pop_start (sweep_line_t *sweep_line)
 244 {
 245     return *sweep_line->rectangles++;
 246 }
 247
 248 static inline rectangle_t *
 249 rectangle_peek_stop (sweep_line_t *sweep_line)
 250 {
 251     return sweep_line->pq.elements[PQ_FIRST_ENTRY];
 252 }
 253
 254 CAIRO_COMBSORT_DECLARE (_rectangle_sort,
 255                         rectangle_t *,
 256                         rectangle_compare_start)
 257
 258 static void
 259 sweep_line_init (sweep_line_t    *sweep_line,
 260                  rectangle_t    **rectangles,
 261                  int              num_rectangles)
 262 {
 263     _rectangle_sort (rectangles, num_rectangles);
 264     rectangles[num_rectangles] = NULL;
 265     sweep_line->rectangles = rectangles;
 266
 267     sweep_line->head.x = INT32_MIN;
 268     sweep_line->head.right = NULL;
 269     sweep_line->head.dir = 0;
 270     sweep_line->head.next = &sweep_line->tail;
 271     sweep_line->tail.x = INT32_MAX;
 272     sweep_line->tail.right = NULL;
 273     sweep_line->tail.dir = 0;
 274     sweep_line->tail.prev = &sweep_line->head;
 275
 276     sweep_line->insert_left = &sweep_line->tail;
 277     sweep_line->insert_right = &sweep_line->tail;
 278
 279     sweep_line->current_y = INT32_MIN;
 280     sweep_line->last_y = INT32_MIN;
 281
 282     pqueue_init (&sweep_line->pq);
 283 }
 284
 285 static void
 286 sweep_line_fini (sweep_line_t *sweep_line)
 287 {
 288     pqueue_fini (&sweep_line->pq);
 289 }
 290
 291 static void
 292 end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot, cairo_boxes_t *out)
 293 {
 294     if (likely (left->top < bot)) {
 295         cairo_status_t status;
 296         cairo_box_t box;
 297
 298         box.p1.x = left->x;
 299         box.p1.y = left->top;
 300         box.p2.x = left->right->x;
 301         box.p2.y = bot;
 302
 303         status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
 304         if (unlikely (status))
 305             longjmp (sweep_line->unwind, status);
 306     }
 307
 308     left->right = NULL;
 309 }
 310
 311 /* Start a new trapezoid at the given top y coordinate, whose edges
 312  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
 313  * then either add it to the traps in `traps', if the trapezoid's
 314  * right edge differs from `edge->next', or do nothing if the new
 315  * trapezoid would be a continuation of the existing one. */
 316 static inline void
 317 start_or_continue_box (sweep_line_t *sweep_line,
 318                        edge_t   *left,
 319                        edge_t   *right,
 320                        int               top,
 321                        cairo_boxes_t *out)
 322 {
 323     if (left->right == right)
 324         return;
 325
 326     if (left->right != NULL) {
 327         if (right != NULL && left->right->x == right->x) {
 328             /* continuation on right, so just swap edges */
 329             left->right = right;
 330             return;
 331         }
 332
 333         end_box (sweep_line, left, top, out);
 334     }
 335
 336     if (right != NULL && left->x != right->x) {
 337         left->top = top;
 338         left->right = right;
 339     }
 340 }
 341
 342 static inline int is_zero(const int *winding)
 343 {
 344     return winding[0] == 0 || winding[1] == 0;
 345 }
 346
 347 static inline void
 348 active_edges (sweep_line_t *sweep, cairo_boxes_t *out)
 349 {
 350     int top = sweep->current_y;
 351     int winding[2] = { 0 };
 352     edge_t *pos;
 353
 354     if (sweep->last_y == sweep->current_y)
 355         return;
 356
 357     pos = sweep->head.next;
 358     if (pos == &sweep->tail)
 359         return;
 360
 361     do {
 362         edge_t *left, *right;
 363
 364         left = pos;
 365         do {
 366             winding[left->a_or_b] += left->dir;
 367             if (!is_zero (winding))
 368                 break;
 369             if (left->next == &sweep->tail)
 370                 goto out;
 371
 372             if (unlikely (left->right != NULL))
 373                 end_box (sweep, left, top, out);
 374
 375             left = left->next;
 376         } while (1);
 377
 378         right = left->next;
 379         do {
 380             if (unlikely (right->right != NULL))
 381                 end_box (sweep, right, top, out);
 382
 383             winding[right->a_or_b] += right->dir;
 384             if (is_zero (winding)) {
 385                 /* skip co-linear edges */
 386                 if (likely (right->x != right->next->x))
 387                     break;
 388             }
 389
 390             right = right->next;
 391         } while (TRUE);
 392
 393         start_or_continue_box (sweep, left, right, top, out);
 394
 395         pos = right->next;
 396     } while (pos != &sweep->tail);
 397
 398 out:
 399     sweep->last_y = sweep->current_y;
 400 }
 401
 402 static inline void
 403 sweep_line_delete_edge (sweep_line_t *sweep_line, edge_t *edge, cairo_boxes_t *out)
 404 {
 405     if (edge->right != NULL) {
 406         edge_t *next = edge->next;
 407         if (next->x == edge->x) {
 408             next->top = edge->top;
 409             next->right = edge->right;
 410         } else {
 411             end_box (sweep_line, edge, sweep_line->current_y, out);
 412         }
 413     }
 414
 415     if (sweep_line->insert_left == edge)
 416         sweep_line->insert_left = edge->next;
 417     if (sweep_line->insert_right == edge)
 418         sweep_line->insert_right = edge->next;
 419
 420     edge->prev->next = edge->next;
 421     edge->next->prev = edge->prev;
 422 }
 423
 424 static inline void
 425 sweep_line_delete (sweep_line_t *sweep,
 426                    rectangle_t  *rectangle,
 427                    cairo_boxes_t *out)
 428 {
 429     sweep_line_delete_edge (sweep, &rectangle->left, out);
 430     sweep_line_delete_edge (sweep, &rectangle->right, out);
 431
 432     pqueue_pop (&sweep->pq);
 433 }
 434
 435 static inline void
 436 insert_edge (edge_t *edge, edge_t *pos)
 437 {
 438     if (pos->x != edge->x) {
 439         if (pos->x > edge->x) {
 440             do {
 441                 UNROLL3({
 442                     if (pos->prev->x <= edge->x)
 443                         break;
 444                     pos = pos->prev;
 445                 })
 446             } while (TRUE);
 447         } else {
 448             do {
 449                 UNROLL3({
 450                     pos = pos->next;
 451                     if (pos->x >= edge->x)
 452                         break;
 453                 })
 454             } while (TRUE);
 455         }
 456     }
 457
 458     pos->prev->next = edge;
 459     edge->prev = pos->prev;
 460     edge->next = pos;
 461     pos->prev = edge;
 462 }
 463
 464 static inline void
 465 sweep_line_insert (sweep_line_t *sweep, rectangle_t     *rectangle)
 466 {
 467     edge_t *pos;
 468
 469     /* right edge */
 470     pos = sweep->insert_right;
 471     insert_edge (&rectangle->right, pos);
 472     sweep->insert_right = &rectangle->right;
 473
 474     /* left edge */
 475     pos = sweep->insert_left;
 476     if (pos->x > sweep->insert_right->x)
 477         pos = sweep->insert_right->prev;
 478     insert_edge (&rectangle->left, pos);
 479     sweep->insert_left = &rectangle->left;
 480
 481     pqueue_push (sweep, rectangle);
 482 }
 483
 484 static cairo_status_t
 485 intersect (rectangle_t **rectangles, int num_rectangles, cairo_boxes_t *out)
 486 {
 487     sweep_line_t sweep_line;
 488     rectangle_t *rectangle;
 489     cairo_status_t status;
 490
 491     sweep_line_init (&sweep_line, rectangles, num_rectangles);
 492     if ((status = setjmp (sweep_line.unwind)))
 493         goto unwind;
 494
 495     rectangle = rectangle_pop_start (&sweep_line);
 496     do {
 497         if (rectangle->top != sweep_line.current_y) {
 498             rectangle_t *stop;
 499
 500             stop = rectangle_peek_stop (&sweep_line);
 501             while (stop != NULL && stop->bottom < rectangle->top) {
 502                 if (stop->bottom != sweep_line.current_y) {
 503                     active_edges (&sweep_line, out);
 504                     sweep_line.current_y = stop->bottom;
 505                 }
 506
 507                 sweep_line_delete (&sweep_line, stop, out);
 508
 509                 stop = rectangle_peek_stop (&sweep_line);
 510             }
 511
 512             active_edges (&sweep_line, out);
 513             sweep_line.current_y = rectangle->top;
 514         }
 515
 516         sweep_line_insert (&sweep_line, rectangle);
 517     } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL);
 518
 519     while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
 520         if (rectangle->bottom != sweep_line.current_y) {
 521             active_edges (&sweep_line, out);
 522             sweep_line.current_y = rectangle->bottom;
 523         }
 524
 525         sweep_line_delete (&sweep_line, rectangle, out);
 526     }
 527
 528 unwind:
 529     sweep_line_fini (&sweep_line);
 530     return status;
 531 }
 532
 533 static cairo_status_t
 534 _cairo_boxes_intersect_with_box (const cairo_boxes_t *boxes,
 535                                  const cairo_box_t *box,
 536                                  cairo_boxes_t *out)
 537 {
 538     cairo_status_t status;
 539     int i, j;
 540
 541     if (out == boxes) { /* inplace update */
 542         struct _cairo_boxes_chunk *chunk;
 543
 544         out->num_boxes = 0;
 545         for (chunk = &out->chunks; chunk != NULL; chunk = chunk->next) {
 546             for (i = j = 0; i < chunk->count; i++) {
 547                 cairo_box_t *b = &chunk->base[i];
 548
 549                 b->p1.x = MAX (b->p1.x, box->p1.x);
 550                 b->p1.y = MAX (b->p1.y, box->p1.y);
 551                 b->p2.x = MIN (b->p2.x, box->p2.x);
 552                 b->p2.y = MIN (b->p2.y, box->p2.y);
 553                 if (b->p1.x < b->p2.x && b->p1.y < b->p2.y) {
 554                     if (i != j)
 555                         chunk->base[j] = *b;
 556                     j++;
 557                 }
 558             }
 559             /* XXX unlink empty chains? */
 560             chunk->count = j;
 561             out->num_boxes += j;
 562         }
 563     } else {
 564         const struct _cairo_boxes_chunk *chunk;
 565
 566         _cairo_boxes_clear (out);
 567         _cairo_boxes_limit (out, box, 1);
 568         for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
 569             for (i = 0; i < chunk->count; i++) {
 570                 status = _cairo_boxes_add (out,
 571                                            CAIRO_ANTIALIAS_DEFAULT,
 572                                            &chunk->base[i]);
 573                 if (unlikely (status))
 574                     return status;
 575             }
 576         }
 577     }
 578
 579     return CAIRO_STATUS_SUCCESS;
 580 }
 581
 582 cairo_status_t
 583 _cairo_boxes_intersect (const cairo_boxes_t *a,
 584                         const cairo_boxes_t *b,
 585                         cairo_boxes_t *out)
 586 {
 587     rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
 588     rectangle_t *rectangles;
 589     rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 1];
 590     rectangle_t **rectangles_ptrs;
 591     const struct _cairo_boxes_chunk *chunk;
 592     cairo_status_t status;
 593     int i, j, count;
 594
 595     if (unlikely (a->num_boxes == 0 || b->num_boxes == 0)) {
 596         _cairo_boxes_clear (out);
 597         return CAIRO_STATUS_SUCCESS;
 598     }
 599
 600     if (a->num_boxes == 1) {
 601         cairo_box_t box = a->chunks.base[0];
 602         return _cairo_boxes_intersect_with_box (b, &box, out);
 603     }
 604     if (b->num_boxes == 1) {
 605         cairo_box_t box = b->chunks.base[0];
 606         return _cairo_boxes_intersect_with_box (a, &box, out);
 607     }
 608
 609     rectangles = stack_rectangles;
 610     rectangles_ptrs = stack_rectangles_ptrs;
 611     count = a->num_boxes + b->num_boxes;
 612     if (count > ARRAY_LENGTH (stack_rectangles)) {
 613         rectangles = _cairo_malloc_ab_plus_c (count,
 614                                               sizeof (rectangle_t) +
 615                                               sizeof (rectangle_t *),
 616                                               sizeof (rectangle_t *));
 617         if (unlikely (rectangles == NULL))
 618             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 619
 620         rectangles_ptrs = (rectangle_t **) (rectangles + count);
 621     }
 622
 623     j = 0;
 624     for (chunk = &a->chunks; chunk != NULL; chunk = chunk->next) {
 625         const cairo_box_t *box = chunk->base;
 626         for (i = 0; i < chunk->count; i++) {
 627             if (box[i].p1.x < box[i].p2.x) {
 628                 rectangles[j].left.x = box[i].p1.x;
 629                 rectangles[j].left.dir = 1;
 630
 631                 rectangles[j].right.x = box[i].p2.x;
 632                 rectangles[j].right.dir = -1;
 633             } else {
 634                 rectangles[j].right.x = box[i].p1.x;
 635                 rectangles[j].right.dir = 1;
 636
 637                 rectangles[j].left.x = box[i].p2.x;
 638                 rectangles[j].left.dir = -1;
 639             }
 640
 641             rectangles[j].left.a_or_b = 0;
 642             rectangles[j].left.right = NULL;
 643             rectangles[j].right.a_or_b = 0;
 644             rectangles[j].right.right = NULL;
 645
 646             rectangles[j].top = box[i].p1.y;
 647             rectangles[j].bottom = box[i].p2.y;
 648
 649             rectangles_ptrs[j] = &rectangles[j];
 650             j++;
 651         }
 652     }
 653     for (chunk = &b->chunks; chunk != NULL; chunk = chunk->next) {
 654         const cairo_box_t *box = chunk->base;
 655         for (i = 0; i < chunk->count; i++) {
 656             if (box[i].p1.x < box[i].p2.x) {
 657                 rectangles[j].left.x = box[i].p1.x;
 658                 rectangles[j].left.dir = 1;
 659
 660                 rectangles[j].right.x = box[i].p2.x;
 661                 rectangles[j].right.dir = -1;
 662             } else {
 663                 rectangles[j].right.x = box[i].p1.x;
 664                 rectangles[j].right.dir = 1;
 665
 666                 rectangles[j].left.x = box[i].p2.x;
 667                 rectangles[j].left.dir = -1;
 668             }
 669
 670             rectangles[j].left.a_or_b = 1;
 671             rectangles[j].left.right = NULL;
 672             rectangles[j].right.a_or_b = 1;
 673             rectangles[j].right.right = NULL;
 674
 675             rectangles[j].top = box[i].p1.y;
 676             rectangles[j].bottom = box[i].p2.y;
 677
 678             rectangles_ptrs[j] = &rectangles[j];
 679             j++;
 680         }
 681     }
 682     assert (j == count);
 683
 684     _cairo_boxes_clear (out);
 685     status = intersect (rectangles_ptrs, j, out);
 686     if (rectangles != stack_rectangles)
 687         free (rectangles);
 688
 689     return status;
 690 }