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