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->num_boxes) {
 289         _cairo_boxes_init_for_array (&clip_boxes, clip->boxes, clip->num_boxes);
 290         if (unlikely (_cairo_boxes_intersect (&clip_boxes, boxes, &clip_boxes))) {
 291             clip = _cairo_clip_set_all_clipped (clip);
 292             goto out;
 293         }
 294
 295         if (clip->boxes != &clip->embedded_box)
 296             free (clip->boxes);
 297
 298         clip->boxes = NULL;
 299         boxes = &clip_boxes;
 300     }
 301
 302     if (boxes->num_boxes == 0) {
 303         clip = _cairo_clip_set_all_clipped (clip);
 304         goto out;
 305     } else if (boxes->num_boxes == 1) {
 306         clip->boxes = &clip->embedded_box;
 307         clip->boxes[0] = boxes->chunks.base[0];
 308         clip->num_boxes = 1;
 309     } else {
 310         clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes, TRUE);
 311     }
 312     _cairo_boxes_extents (boxes, &limits);
 313
 314     _cairo_box_round_to_rectangle (&limits, &extents);
 315     if (clip->path == NULL)
 316         clip->extents = extents;
 317     else if (! _cairo_rectangle_intersect (&clip->extents, &extents))
 318         clip = _cairo_clip_set_all_clipped (clip);
 319
 320     if (clip->region) {
 321         cairo_region_destroy (clip->region);
 322         clip->region = NULL;
 323     }
 324     clip->is_region = FALSE;
 325
 326 out:
 327     if (boxes == &clip_boxes)
 328         _cairo_boxes_fini (&clip_boxes);
 329
 330     return clip;
 331 }
 332
 333 cairo_clip_t *
 334 _cairo_clip_intersect_rectangle (cairo_clip_t       *clip,
 335                                  const cairo_rectangle_int_t *r)
 336 {
 337     cairo_box_t box;
 338
 339     if (_cairo_clip_is_all_clipped (clip))
 340         return clip;
 341
 342     if (r->width == 0 || r->height == 0)
 343         return _cairo_clip_set_all_clipped (clip);
 344
 345     box.p1.x = _cairo_fixed_from_int (r->x);
 346     box.p1.y = _cairo_fixed_from_int (r->y);
 347     box.p2.x = _cairo_fixed_from_int (r->x + r->width);
 348     box.p2.y = _cairo_fixed_from_int (r->y + r->height);
 349
 350     return _cairo_clip_intersect_rectangle_box (clip, r, &box);
 351 }
 352
 353 struct reduce {
 354     cairo_clip_t *clip;
 355     cairo_box_t limit;
 356     cairo_box_t extents;
 357     cairo_bool_t inside;
 358
 359     cairo_point_t current_point;
 360     cairo_point_t last_move_to;
 361 };
 362
 363 static void
 364 _add_clipped_edge (struct reduce *r,
 365                    const cairo_point_t *p1,
 366                    const cairo_point_t *p2,
 367                    int y1, int y2)
 368 {
 369     cairo_fixed_t x;
 370
 371     x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y1);
 372     if (x < r->extents.p1.x)
 373         r->extents.p1.x = x;
 374
 375     x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y2);
 376     if (x > r->extents.p2.x)
 377         r->extents.p2.x = x;
 378
 379     if (y1 < r->extents.p1.y)
 380         r->extents.p1.y = y1;
 381
 382     if (y2 > r->extents.p2.y)
 383         r->extents.p2.y = y2;
 384
 385     r->inside = TRUE;
 386 }
 387
 388 static void
 389 _add_edge (struct reduce *r,
 390            const cairo_point_t *p1,
 391            const cairo_point_t *p2)
 392 {
 393     int top, bottom;
 394     int top_y, bot_y;
 395     int n;
 396
 397     if (p1->y < p2->y) {
 398         top = p1->y;
 399         bottom = p2->y;
 400     } else {
 401         top = p2->y;
 402         bottom = p1->y;
 403     }
 404
 405     if (bottom < r->limit.p1.y || top > r->limit.p2.y)
 406         return;
 407
 408     if (p1->x > p2->x) {
 409         const cairo_point_t *t = p1;
 410         p1 = p2;
 411         p2 = t;
 412     }
 413
 414     if (p2->x <= r->limit.p1.x || p1->x >= r->limit.p2.x)
 415         return;
 416
 417     for (n = 0; n < r->clip->num_boxes; n++) {
 418         const cairo_box_t *limits = &r->clip->boxes[n];
 419
 420         if (bottom < limits->p1.y || top > limits->p2.y)
 421             continue;
 422
 423         if (p2->x <= limits->p1.x || p1->x >= limits->p2.x)
 424             continue;
 425
 426         if (p1->x >= limits->p1.x && p2->x <= limits->p1.x) {
 427             top_y = top;
 428             bot_y = bottom;
 429         } else {
 430             int p1_y, p2_y;
 431
 432             p1_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 433                                                              limits->p1.x);
 434             p2_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
 435                                                              limits->p2.x);
 436             if (p1_y < p2_y) {
 437                 top_y = p1_y;
 438                 bot_y = p2_y;
 439             } else {
 440                 top_y = p2_y;
 441                 bot_y = p1_y;
 442             }
 443
 444             if (top_y < top)
 445                 top_y = top;
 446             if (bot_y > bottom)
 447                 bot_y = bottom;
 448         }
 449
 450         if (top_y < limits->p1.y)
 451             top_y = limits->p1.y;
 452
 453         if (bot_y > limits->p2.y)
 454             bot_y = limits->p2.y;
 455         if (bot_y > top_y)
 456             _add_clipped_edge (r, p1, p2, top_y, bot_y);
 457     }
 458 }
 459
 460 static cairo_status_t
 461 _reduce_line_to (void *closure,
 462                        const cairo_point_t *point)
 463 {
 464     struct reduce *r = closure;
 465
 466     _add_edge (r, &r->current_point, point);
 467     r->current_point = *point;
 468
 469     return CAIRO_STATUS_SUCCESS;
 470 }
 471
 472 static cairo_status_t
 473 _reduce_close (void *closure)
 474 {
 475     struct reduce *r = closure;
 476
 477     return _reduce_line_to (r, &r->last_move_to);
 478 }
 479
 480 static cairo_status_t
 481 _reduce_move_to (void *closure,
 482                  const cairo_point_t *point)
 483 {
 484     struct reduce *r = closure;
 485     cairo_status_t status;
 486
 487     /* close current subpath */
 488     status = _reduce_close (closure);
 489
 490     /* make sure that the closure represents a degenerate path */
 491     r->current_point = *point;
 492     r->last_move_to = *point;
 493
 494     return status;
 495 }
 496
 497 static cairo_clip_t *
 498 _cairo_clip_reduce_to_boxes (cairo_clip_t *clip)
 499 {
 500     struct reduce r;
 501     cairo_clip_path_t *clip_path;
 502     cairo_status_t status;
 503
 504         return clip;
 505     if (clip->path == NULL)
 506         return clip;
 507
 508     r.clip = clip;
 509     r.extents.p1.x = r.extents.p1.y = INT_MAX;
 510     r.extents.p2.x = r.extents.p2.y = INT_MIN;
 511     r.inside = FALSE;
 512
 513     r.limit.p1.x = _cairo_fixed_from_int (clip->extents.x);
 514     r.limit.p1.y = _cairo_fixed_from_int (clip->extents.y);
 515     r.limit.p2.x = _cairo_fixed_from_int (clip->extents.x + clip->extents.width);
 516     r.limit.p2.y = _cairo_fixed_from_int (clip->extents.y + clip->extents.height);
 517
 518     clip_path = clip->path;
 519     do {
 520         r.current_point.x = 0;
 521         r.current_point.y = 0;
 522         r.last_move_to = r.current_point;
 523
 524         status = _cairo_path_fixed_interpret_flat (&clip_path->path,
 525                                                    _reduce_move_to,
 526                                                    _reduce_line_to,
 527                                                    _reduce_close,
 528                                                    &r,
 529                                                    clip_path->tolerance);
 530         assert (status == CAIRO_STATUS_SUCCESS);
 531         _reduce_close (&r);
 532     } while ((clip_path = clip_path->prev));
 533
 534     if (! r.inside) {
 535         _cairo_clip_path_destroy (clip->path);
 536         clip->path = NULL;
 537     }
 538
 539     return _cairo_clip_intersect_box (clip, &r.extents);
 540 }
 541
 542 cairo_clip_t *
 543 _cairo_clip_reduce_to_rectangle (const cairo_clip_t *clip,
 544                                  const cairo_rectangle_int_t *r)
 545 {
 546     cairo_clip_t *copy;
 547
 548     if (_cairo_clip_is_all_clipped (clip))
 549         return (cairo_clip_t *) clip;
 550
 551     if (_cairo_clip_contains_rectangle (clip, r))
 552         return _cairo_clip_intersect_rectangle (NULL, r);
 553
 554     copy = _cairo_clip_copy_intersect_rectangle (clip, r);
 555     if (_cairo_clip_is_all_clipped (copy))
 556         return copy;
 557
 558     return _cairo_clip_reduce_to_boxes (copy);
 559 }
 560
 561 cairo_clip_t *
 562 _cairo_clip_reduce_for_composite (const cairo_clip_t *clip,
 563                                   cairo_composite_rectangles_t *extents)
 564 {
 565     const cairo_rectangle_int_t *r;
 566
 567     r = extents->is_bounded ? &extents->bounded : &extents->unbounded;
 568     return _cairo_clip_reduce_to_rectangle (clip, r);
 569 }
 570
 571 cairo_clip_t *
 572 _cairo_clip_from_boxes (const cairo_boxes_t *boxes)
 573 {
 574     cairo_box_t extents;
 575     cairo_clip_t *clip = _cairo_clip_create ();
 576     if (clip == NULL)
 577         return _cairo_clip_set_all_clipped (clip);
 578
 579     /* XXX cow-boxes? */
 580     if(boxes->num_boxes == 1) {
 581         clip->boxes = &clip->embedded_box;
 582         clip->boxes[0] = boxes->chunks.base[0];
 583         clip->num_boxes = 1;
 584     } else {
 585         clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes, TRUE);
 586         if (clip->boxes == NULL)
 587             return _cairo_clip_set_all_clipped (clip);
 588     }
 589
 590     _cairo_boxes_extents (boxes, &extents);
 591     _cairo_box_round_to_rectangle (&extents, &clip->extents);
 592
 593     return clip;
 594 }