src/cairo-clip-boxes.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /* cairo - a vector graphics library with display and print output
   3  *
   4  * Copyright © 2002 University of Southern California
   5  * Copyright © 2005 Red Hat, Inc.
   6  * Copyright © 2009 Chris Wilson
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it either under the terms of the GNU Lesser General Public
  10  * License version 2.1 as published by the Free Software Foundation
  11  * (the "LGPL") or, at your option, under the terms of the Mozilla
  12  * Public License Version 1.1 (the "MPL"). If you do not alter this
  13  * notice, a recipient may use your version of this file under either
  14  * the MPL or the LGPL.
  15  *
  16  * You should have received a copy of the LGPL along with this library
  17  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  19  * You should have received a copy of the MPL along with this library
  20  * in the file COPYING-MPL-1.1
  21  *
  22  * The contents of this file are subject to the Mozilla Public License
  23  * Version 1.1 (the "License"); you may not use this file except in
  24  * compliance with the License. You may obtain a copy of the License at
  25  * http://www.mozilla.org/MPL/
  26  *
  27  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  28  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  29  * the specific language governing rights and limitations.
  30  *
  31  * The Original Code is the cairo graphics library.
  32  *
  33  * The Initial Developer of the Original Code is University of Southern
  34  * California.
  35  *
  36  * Contributor(s):
  37  *      Carl D. Worth <cworth@cworth.org>
  38  *      Kristian Høgsberg <krh@redhat.com>
  39  *      Chris Wilson <chris@chris-wilson.co.uk>
  40  */
  41
  42 #include "cairoint.h"
  43
  44 #include "cairo-box-inline.h"
  45 #include "cairo-clip-inline.h"
  46 #include "cairo-clip-private.h"
  47 #include "cairo-error-private.h"
  48 #include "cairo-freed-pool-private.h"
  49 #include "cairo-gstate-private.h"
  50 #include "cairo-path-fixed-private.h"
  51 #include "cairo-pattern-private.h"
  52 #include "cairo-composite-rectangles-private.h"
  53 #include "cairo-region-private.h"
  54
  55 static inline int
  56 pot (int v)
  57 {
  58     v--;
  59     v |= v >> 1;
  60     v |= v >> 2;
  61     v |= v >> 4;
  62     v |= v >> 8;
  63     v |= v >> 16;
  64     v++;
  65     return v;
  66 }
  67
  68 static cairo_bool_t
  69 _cairo_clip_contains_rectangle_box (const cairo_clip_t *clip,
  70                                     const cairo_rectangle_int_t *rect,
  71                                     const cairo_box_t *box)
  72 {
  73     int i;
  74
  75     /* clip == NULL means no clip, so the clip contains everything */
  76     if (clip == NULL)
  77         return TRUE;
  78
  79     if (_cairo_clip_is_all_clipped (clip))
  80         return FALSE;
  81
  82     /* If we have a non-trivial path, just say no */
  83     if (clip->path)
  84         return FALSE;
  85
  86     if (! _cairo_rectangle_contains_rectangle (&clip->extents, rect))
  87         return FALSE;
  88
  89     if (clip->num_boxes == 0)
  90         return TRUE;
  91
  92     /* Check for a clip-box that wholly contains the rectangle */
  93     for (i = 0; i < clip->num_boxes; i++) {
  94         if (box->p1.x >= clip->boxes[i].p1.x &&
  95             box->p1.y >= clip->boxes[i].p1.y &&
  96             box->p2.x <= clip->boxes[i].p2.x &&
  97             box->p2.y <= clip->boxes[i].p2.y)
  98         {
  99             return TRUE;
 100         }
 101     }
 102
 103     return FALSE;
 104 }
 105
 106 cairo_bool_t
 107 _cairo_clip_contains_box (const cairo_clip_t *clip,
 108                           const cairo_box_t *box)
 109 {
 110     cairo_rectangle_int_t rect;
 111
 112     _cairo_box_round_to_rectangle (box, &rect);
 113     return _cairo_clip_contains_rectangle_box(clip, &rect, box);
 114 }
 115
 116 cairo_bool_t
 117 _cairo_clip_contains_rectangle (const cairo_clip_t *clip,
 118                                 const cairo_rectangle_int_t *rect)
 119 {
 120     cairo_box_t box;
 121
 122     box.p1.x = _cairo_fixed_from_int (rect->x);
 123     box.p1.y = _cairo_fixed_from_int (rect->y);
 124     box.p2.x = _cairo_fixed_from_int (rect->x + rect->width);
 125     box.p2.y = _cairo_fixed_from_int (rect->y + rect->height);
 126
 127     return _cairo_clip_contains_rectangle_box (clip, rect, &box);
 128 }
 129
 130 cairo_clip_t *
 131 _cairo_clip_intersect_rectilinear_path (cairo_clip_t *clip,
 132                                         const cairo_path_fixed_t *path,
 133                                         cairo_fill_rule_t fill_rule,
 134                                         cairo_antialias_t antialias)
 135 {
 136     cairo_status_t status;
 137     cairo_boxes_t boxes;
 138
 139     _cairo_boxes_init (&boxes);
 140     status = _cairo_path_fixed_fill_rectilinear_to_boxes (path,
 141                                                           fill_rule,
 142                                                           antialias,
 143                                                           &boxes);
 144     if (likely (status == CAIRO_STATUS_SUCCESS && boxes.num_boxes))
 145         clip = _cairo_clip_intersect_boxes (clip, &boxes);
 146     else
 147         clip = _cairo_clip_set_all_clipped (clip);
 148     _cairo_boxes_fini (&boxes);
 149
 150     return clip;
 151 }
 152
 153 static cairo_clip_t *
 154 _cairo_clip_intersect_rectangle_box (cairo_clip_t *clip,
 155                                      const cairo_rectangle_int_t *r,
 156                                      const cairo_box_t *box)
 157 {
 158     cairo_box_t extents_box;
 159     cairo_bool_t changed = FALSE;
 160     int i, j;
 161
 162     if (clip == NULL) {
 163         clip = _cairo_clip_create ();
 164         if (clip == NULL)
 165             return _cairo_clip_set_all_clipped (clip);
 166     }
 167
 168     if (clip->num_boxes == 0) {
 169         clip->boxes = &clip->embedded_box;
 170         clip->boxes[0] = *box;
 171         clip->num_boxes = 1;
 172         if (clip->path == NULL) {
 173             clip->extents = *r;
 174         } else {
 175             if (! _cairo_rectangle_intersect (&clip->extents, r))
 176                 clip = _cairo_clip_set_all_clipped (clip);
 177         }
 178         if (clip->path == NULL)
 179             clip->is_region = _cairo_box_is_pixel_aligned (box);
 180         return clip;
 181     }
 182
 183     /* Does the new box wholly subsume the clip? Perform a cheap check
 184      * for the common condition of a single clip rectangle.
 185      */
 186     if (clip->num_boxes == 1 &&
 187         clip->boxes[0].p1.x >= box->p1.x &&
 188         clip->boxes[0].p1.y >= box->p1.y &&
 189         clip->boxes[0].p2.x <= box->p2.x &&
 190         clip->boxes[0].p2.y <= box->p2.y)
 191     {
 192         return clip;
 193     }
 194
 195     for (i = j = 0; i < clip->num_boxes; i++) {
 196         cairo_box_t *b = &clip->boxes[j];
 197
 198         if (j != i)
 199             *b = clip->boxes[i];
 200
 201         if (box->p1.x > b->p1.x)
 202             b->p1.x = box->p1.x, changed = TRUE;
 203         if (box->p2.x < b->p2.x)
 204             b->p2.x = box->p2.x, changed = TRUE;
 205
 206         if (box->p1.y > b->p1.y)
 207             b->p1.y = box->p1.y, changed = TRUE;
 208         if (box->p2.y < b->p2.y)
 209             b->p2.y = box->p2.y, changed = TRUE;
 210
 211         j += b->p2.x > b->p1.x && b->p2.y > b->p1.y;
 212     }
 213     clip->num_boxes = j;
 214
 215     if (clip->num_boxes == 0)
 216         return _cairo_clip_set_all_clipped (clip);
 217
 218     if (! changed)
 219         return clip;
 220
 221     extents_box = clip->boxes[0];
 222     for (i = 1; i < clip->num_boxes; i++) {
 223             if (clip->boxes[i].p1.x < extents_box.p1.x)
 224                 extents_box.p1.x = clip->boxes[i].p1.x;
 225
 226             if (clip->boxes[i].p1.y < extents_box.p1.y)
 227                 extents_box.p1.y = clip->boxes[i].p1.y;
 228
 229             if (clip->boxes[i].p2.x > extents_box.p2.x)
 230                 extents_box.p2.x = clip->boxes[i].p2.x;
 231
 232             if (clip->boxes[i].p2.y > extents_box.p2.y)
 233                 extents_box.p2.y = clip->boxes[i].p2.y;
 234     }
 235
 236     if (clip->path == NULL) {
 237         _cairo_box_round_to_rectangle (&extents_box, &clip->extents);
 238     } else {
 239         cairo_rectangle_int_t extents_rect;
 240
 241         _cairo_box_round_to_rectangle (&extents_box, &extents_rect);
 242         if (! _cairo_rectangle_intersect (&clip->extents, &extents_rect))
 243             return _cairo_clip_set_all_clipped (clip);
 244     }
 245
 246     if (clip->region) {
 247         cairo_region_destroy (clip->region);
 248         clip->region = NULL;
 249     }
 250
 251     clip->is_region = FALSE;
 252     return clip;
 253 }
 254
 255 cairo_clip_t *
 256 _cairo_clip_intersect_box (cairo_clip_t *clip,
 257                            const cairo_box_t *box)
 258 {
 259     cairo_rectangle_int_t r;
 260
 261     _cairo_box_round_to_rectangle (box, &r);
 262     if (r.width == 0 || r.height == 0)
 263         return _cairo_clip_set_all_clipped (clip);
 264
 265     return _cairo_clip_intersect_rectangle_box (clip, &r, box);
 266 }
 267
 268 cairo_clip_t *
 269 _cairo_clip_intersect_boxes (cairo_clip_t *clip,
 270                              const cairo_boxes_t *boxes)
 271 {
 272     cairo_boxes_t clip_boxes;
 273     cairo_box_t limits;
 274     cairo_rectangle_int_t extents;
 275
 276     if (_cairo_clip_is_all_clipped (clip))
 277         return clip;
 278
 279     if (boxes->num_boxes == 0)
 280         return _cairo_clip_set_all_clipped (clip);
 281
 282     if (boxes->num_boxes == 1)
 283         return _cairo_clip_intersect_box (clip, boxes->chunks.base);
 284
 285     if (clip == NULL)
 286         clip = _cairo_clip_create ();
 287
 288     if (clip == NULL)
 289         return NULL;
 290
 291     if (clip->num_boxes) {
 292         _cairo_boxes_init_for_array (&clip_boxes, clip->boxes, clip->num_boxes);
 293         if (unlikely (_cairo_boxes_intersect (&clip_boxes, boxes, &clip_boxes))) {
 294             clip = _cairo_clip_set_all_clipped (clip);
 295             goto out;
 296         }
 297
 298         if (clip->boxes != &clip->embedded_box)
 299             free (clip->boxes);
 300
 301         clip->boxes = NULL;
 302         boxes = &clip_boxes;
 303     }
 304
 305     if (boxes->num_boxes == 0) {
 306         clip = _cairo_clip_set_all_clipped (clip);
 307         goto out;
 308     } else if (boxes->num_boxes == 1) {
 309         clip->boxes = &clip->embedded_box;
 310         clip->boxes[0] = boxes->chunks.base[0];
 311         clip->num_boxes = 1;
 312     } else {
 313         clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes, TRUE);
 314     }
 315     _cairo_boxes_extents (boxes, &limits);
 316
 317     _cairo_box_round_to_rectangle (&limits, &extents);
 318     if (clip->path == NULL)
 319         clip->extents = extents;
 320     else if (! _cairo_rectangle_intersect (&clip->extents, &extents))
 321         clip = _cairo_clip_set_all_clipped (clip);
 322
 323     if (clip->region) {
 324         cairo_region_destroy (clip->region);
 325         clip->region = NULL;
 326     }
 327     clip->is_region = FALSE;
 328
 329 out:
 330     if (boxes == &clip_boxes)
 331         _cairo_boxes_fini (&clip_boxes);
 332
 333     return clip;
 334 }
 335
 336 cairo_clip_t *
 337 _cairo_clip_intersect_rectangle (cairo_clip_t       *clip,
 338                                  const cairo_rectangle_int_t *r)
 339 {
 340     cairo_box_t box;
 341
 342     if (_cairo_clip_is_all_clipped (clip))
 343         return clip;
 344
 345     if (r->width == 0 || r->height == 0)
 346         return _cairo_clip_set_all_clipped (clip);
 347
 348     box.p1.x = _cairo_fixed_from_int (r->x);
 349     box.p1.y = _cairo_fixed_from_int (r->y);
 350     box.p2.x = _cairo_fixed_from_int (r->x + r->width);
 351     box.p2.y = _cairo_fixed_from_int (r->y + r->height);
 352
 353     return _cairo_clip_intersect_rectangle_box (clip, r, &box);
 354 }
 355
 356 struct reduce {
 357     cairo_clip_t *clip;
 358     cairo_box_t limit;
 359     cairo_box_t extents;
 360     cairo_bool_t inside;
 361
 362     cairo_point_t current_point;
 363     cairo_point_t last_move_to;
 364 };
 365
 366 static void
 367 _add_clipped_edge (struct reduce *r,
 368                    const cairo_point_t *p1,
 369                    const cairo_point_t *p2,
 370                    int y1, int y2)
 371 {
 372     cairo_fixed_t x;
 373
 374     x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y1);
 375     if (x < r->extents.p1.x)
 376         r->extents.p1.x = x;
 377
 378     x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y2);
 379     if (x > r->extents.p2.x)
 380         r->extents.p2.x = x;
 381
 382     if (y1 < r->extents.p1.y)
 383         r->extents.p1.y = y1;
 384
 385     if (y2 > r->extents.p2.y)
 386         r->extents.p2.y = y2;
 387
 388     r->inside = TRUE;
 389 }
 390
 391 static void
 392 _add_edge (struct reduce *r,
 393            const cairo_point_t *p1,
 394            const cairo_point_t *p2)
 395 {
 396     int top, bottom;
 397     int top_y, bot_y;
 398     int n;
 399
 400     if (p1->y < p2->y) {
 401         top = p1->y;
 402         bottom = p2->y;
 403     } else {
 404         top = p2->y;
 405         bottom = p1->y;
 406     }
 407
 408     if (bottom < r->limit.p1.y || top > r->limit.p2.y)
 409         return;
 410
 411     if (p1->x > p2->x) {
 412         const cairo_point_t *t = p1;
 413         p1 = p2;
 414         p2 = t;
 415     }
 416
 417     if (p2->x <= r->limit.p1.x || p1->x >= r->limit.p2.x)
 418         return;
 419
 420     for (n = 0; n < r->clip->num_boxes; n++) {
 421         const cairo_box_t *limits = &r->clip->boxes[n];
 422
 423         if (bottom < limits->p1.y || top > limits->p2.y)
 424             continue;
 425
 426         if (p2->x <= limits->p1.x || p1->x >= limits->p2.x)
 427             continue;
 428
 429         if (p1->x >= limits->p1.x && p2->x <= limits->p1.x) {
 430             top_y = top;
 431             bot_y = bottom;
 432         } else {
 433             int p1_y, p2_y;
 434
 435             p1_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 436                                                              limits->p1.x);
 437             p2_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 438                                                              limits->p2.x);
 439             if (p1_y < p2_y) {
 440                 top_y = p1_y;
 441                 bot_y = p2_y;
 442             } else {
 443                 top_y = p2_y;
 444                 bot_y = p1_y;
 445             }
 446
 447             if (top_y < top)
 448                 top_y = top;
 449             if (bot_y > bottom)
 450                 bot_y = bottom;
 451         }
 452
 453         if (top_y < limits->p1.y)
 454             top_y = limits->p1.y;
 455
 456         if (bot_y > limits->p2.y)
 457             bot_y = limits->p2.y;
 458         if (bot_y > top_y)
 459             _add_clipped_edge (r, p1, p2, top_y, bot_y);
 460     }
 461 }
 462
 463 static cairo_status_t
 464 _reduce_line_to (void *closure,
 465                        const cairo_point_t *point)
 466 {
 467     struct reduce *r = closure;
 468
 469     _add_edge (r, &r->current_point, point);
 470     r->current_point = *point;
 471
 472     return CAIRO_STATUS_SUCCESS;
 473 }
 474
 475 static cairo_status_t
 476 _reduce_close (void *closure)
 477 {
 478     struct reduce *r = closure;
 479
 480     return _reduce_line_to (r, &r->last_move_to);
 481 }
 482
 483 static cairo_status_t
 484 _reduce_move_to (void *closure,
 485                  const cairo_point_t *point)
 486 {
 487     struct reduce *r = closure;
 488     cairo_status_t status;
 489
 490     /* close current subpath */
 491     status = _reduce_close (closure);
 492
 493     /* make sure that the closure represents a degenerate path */
 494     r->current_point = *point;
 495     r->last_move_to = *point;
 496
 497     return status;
 498 }
 499
 500 static cairo_clip_t *
 501 _cairo_clip_reduce_to_boxes (cairo_clip_t *clip)
 502 {
 503     struct reduce r;
 504     cairo_clip_path_t *clip_path;
 505     cairo_status_t status;
 506
 507         return clip;
 508     if (clip->path == NULL)
 509         return clip;
 510
 511     r.clip = clip;
 512     r.extents.p1.x = r.extents.p1.y = INT_MAX;
 513     r.extents.p2.x = r.extents.p2.y = INT_MIN;
 514     r.inside = FALSE;
 515
 516     r.limit.p1.x = _cairo_fixed_from_int (clip->extents.x);
 517     r.limit.p1.y = _cairo_fixed_from_int (clip->extents.y);
 518     r.limit.p2.x = _cairo_fixed_from_int (clip->extents.x + clip->extents.width);
 519     r.limit.p2.y = _cairo_fixed_from_int (clip->extents.y + clip->extents.height);
 520
 521     clip_path = clip->path;
 522     do {
 523         r.current_point.x = 0;
 524         r.current_point.y = 0;
 525         r.last_move_to = r.current_point;
 526
 527         status = _cairo_path_fixed_interpret_flat (&clip_path->path,
 528                                                    _reduce_move_to,
 529                                                    _reduce_line_to,
 530                                                    _reduce_close,
 531                                                    &r,
 532                                                    clip_path->tolerance);
 533         assert (status == CAIRO_STATUS_SUCCESS);
 534         _reduce_close (&r);
 535     } while ((clip_path = clip_path->prev));
 536
 537     if (! r.inside) {
 538         _cairo_clip_path_destroy (clip->path);
 539         clip->path = NULL;
 540     }
 541
 542     return _cairo_clip_intersect_box (clip, &r.extents);
 543 }
 544
 545 cairo_clip_t *
 546 _cairo_clip_reduce_to_rectangle (const cairo_clip_t *clip,
 547                                  const cairo_rectangle_int_t *r)
 548 {
 549     cairo_clip_t *copy;
 550
 551     if (_cairo_clip_is_all_clipped (clip))
 552         return (cairo_clip_t *) clip;
 553
 554     if (_cairo_clip_contains_rectangle (clip, r))
 555         return _cairo_clip_intersect_rectangle (NULL, r);
 556
 557     copy = _cairo_clip_copy_intersect_rectangle (clip, r);
 558     if (_cairo_clip_is_all_clipped (copy))
 559         return copy;
 560
 561     return _cairo_clip_reduce_to_boxes (copy);
 562 }
 563
 564 cairo_clip_t *
 565 _cairo_clip_reduce_for_composite (const cairo_clip_t *clip,
 566                                   cairo_composite_rectangles_t *extents)
 567 {
 568     const cairo_rectangle_int_t *r;
 569
 570     r = extents->is_bounded ? &extents->bounded : &extents->unbounded;
 571     return _cairo_clip_reduce_to_rectangle (clip, r);
 572 }
 573
 574 cairo_clip_t *
 575 _cairo_clip_from_boxes (const cairo_boxes_t *boxes)
 576 {
 577     cairo_box_t extents;
 578     cairo_clip_t *clip = _cairo_clip_create ();
 579     if (clip == NULL)
 580         return _cairo_clip_set_all_clipped (clip);
 581
 582     /* XXX cow-boxes? */
 583     if(boxes->num_boxes == 1) {
 584         clip->boxes = &clip->embedded_box;
 585         clip->boxes[0] = boxes->chunks.base[0];
 586         clip->num_boxes = 1;
 587     } else {
 588         clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes, TRUE);
 589         if (clip->boxes == NULL)
 590             return _cairo_clip_set_all_clipped (clip);
 591     }
 592
 593     _cairo_boxes_extents (boxes, &extents);
 594     _cairo_box_round_to_rectangle (&extents, &clip->extents);
 595
 596     return clip;
 597 }