0,0 → 1,594 |
/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */ |
/* cairo - a vector graphics library with display and print output |
* |
* Copyright © 2002 University of Southern California |
* Copyright © 2005 Red Hat, Inc. |
* Copyright © 2009 Chris Wilson |
* |
* This library is free software; you can redistribute it and/or |
* modify it either under the terms of the GNU Lesser General Public |
* License version 2.1 as published by the Free Software Foundation |
* (the "LGPL") or, at your option, under the terms of the Mozilla |
* Public License Version 1.1 (the "MPL"). If you do not alter this |
* notice, a recipient may use your version of this file under either |
* the MPL or the LGPL. |
* |
* You should have received a copy of the LGPL along with this library |
* in the file COPYING-LGPL-2.1; if not, write to the Free Software |
* Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA |
* You should have received a copy of the MPL along with this library |
* in the file COPYING-MPL-1.1 |
* |
* The contents of this file are subject to the Mozilla Public License |
* Version 1.1 (the "License"); you may not use this file except in |
* compliance with the License. You may obtain a copy of the License at |
* http://www.mozilla.org/MPL/ |
* |
* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY |
* OF ANY KIND, either express or implied. See the LGPL or the MPL for |
* the specific language governing rights and limitations. |
* |
* The Original Code is the cairo graphics library. |
* |
* The Initial Developer of the Original Code is University of Southern |
* California. |
* |
* Contributor(s): |
* Carl D. Worth <cworth@cworth.org> |
* Kristian Høgsberg <krh@redhat.com> |
* Chris Wilson <chris@chris-wilson.co.uk> |
*/ |
|
#include "cairoint.h" |
|
#include "cairo-box-inline.h" |
#include "cairo-clip-inline.h" |
#include "cairo-clip-private.h" |
#include "cairo-error-private.h" |
#include "cairo-freed-pool-private.h" |
#include "cairo-gstate-private.h" |
#include "cairo-path-fixed-private.h" |
#include "cairo-pattern-private.h" |
#include "cairo-composite-rectangles-private.h" |
#include "cairo-region-private.h" |
|
static inline int |
pot (int v) |
{ |
v--; |
v |= v >> 1; |
v |= v >> 2; |
v |= v >> 4; |
v |= v >> 8; |
v |= v >> 16; |
v++; |
return v; |
} |
|
static cairo_bool_t |
_cairo_clip_contains_rectangle_box (const cairo_clip_t *clip, |
const cairo_rectangle_int_t *rect, |
const cairo_box_t *box) |
{ |
int i; |
|
/* clip == NULL means no clip, so the clip contains everything */ |
if (clip == NULL) |
return TRUE; |
|
if (_cairo_clip_is_all_clipped (clip)) |
return FALSE; |
|
/* If we have a non-trivial path, just say no */ |
if (clip->path) |
return FALSE; |
|
if (! _cairo_rectangle_contains_rectangle (&clip->extents, rect)) |
return FALSE; |
|
if (clip->num_boxes == 0) |
return TRUE; |
|
/* Check for a clip-box that wholly contains the rectangle */ |
for (i = 0; i < clip->num_boxes; i++) { |
if (box->p1.x >= clip->boxes[i].p1.x && |
box->p1.y >= clip->boxes[i].p1.y && |
box->p2.x <= clip->boxes[i].p2.x && |
box->p2.y <= clip->boxes[i].p2.y) |
{ |
return TRUE; |
} |
} |
|
return FALSE; |
} |
|
cairo_bool_t |
_cairo_clip_contains_box (const cairo_clip_t *clip, |
const cairo_box_t *box) |
{ |
cairo_rectangle_int_t rect; |
|
_cairo_box_round_to_rectangle (box, &rect); |
return _cairo_clip_contains_rectangle_box(clip, &rect, box); |
} |
|
cairo_bool_t |
_cairo_clip_contains_rectangle (const cairo_clip_t *clip, |
const cairo_rectangle_int_t *rect) |
{ |
cairo_box_t box; |
|
box.p1.x = _cairo_fixed_from_int (rect->x); |
box.p1.y = _cairo_fixed_from_int (rect->y); |
box.p2.x = _cairo_fixed_from_int (rect->x + rect->width); |
box.p2.y = _cairo_fixed_from_int (rect->y + rect->height); |
|
return _cairo_clip_contains_rectangle_box (clip, rect, &box); |
} |
|
cairo_clip_t * |
_cairo_clip_intersect_rectilinear_path (cairo_clip_t *clip, |
const cairo_path_fixed_t *path, |
cairo_fill_rule_t fill_rule, |
cairo_antialias_t antialias) |
{ |
cairo_status_t status; |
cairo_boxes_t boxes; |
|
_cairo_boxes_init (&boxes); |
status = _cairo_path_fixed_fill_rectilinear_to_boxes (path, |
fill_rule, |
antialias, |
&boxes); |
if (likely (status == CAIRO_STATUS_SUCCESS && boxes.num_boxes)) |
clip = _cairo_clip_intersect_boxes (clip, &boxes); |
else |
clip = _cairo_clip_set_all_clipped (clip); |
_cairo_boxes_fini (&boxes); |
|
return clip; |
} |
|
static cairo_clip_t * |
_cairo_clip_intersect_rectangle_box (cairo_clip_t *clip, |
const cairo_rectangle_int_t *r, |
const cairo_box_t *box) |
{ |
cairo_box_t extents_box; |
cairo_bool_t changed = FALSE; |
int i, j; |
|
if (clip == NULL) { |
clip = _cairo_clip_create (); |
if (clip == NULL) |
return _cairo_clip_set_all_clipped (clip); |
} |
|
if (clip->num_boxes == 0) { |
clip->boxes = &clip->embedded_box; |
clip->boxes[0] = *box; |
clip->num_boxes = 1; |
if (clip->path == NULL) { |
clip->extents = *r; |
} else { |
if (! _cairo_rectangle_intersect (&clip->extents, r)) |
clip = _cairo_clip_set_all_clipped (clip); |
} |
if (clip->path == NULL) |
clip->is_region = _cairo_box_is_pixel_aligned (box); |
return clip; |
} |
|
/* Does the new box wholly subsume the clip? Perform a cheap check |
* for the common condition of a single clip rectangle. |
*/ |
if (clip->num_boxes == 1 && |
clip->boxes[0].p1.x >= box->p1.x && |
clip->boxes[0].p1.y >= box->p1.y && |
clip->boxes[0].p2.x <= box->p2.x && |
clip->boxes[0].p2.y <= box->p2.y) |
{ |
return clip; |
} |
|
for (i = j = 0; i < clip->num_boxes; i++) { |
cairo_box_t *b = &clip->boxes[j]; |
|
if (j != i) |
*b = clip->boxes[i]; |
|
if (box->p1.x > b->p1.x) |
b->p1.x = box->p1.x, changed = TRUE; |
if (box->p2.x < b->p2.x) |
b->p2.x = box->p2.x, changed = TRUE; |
|
if (box->p1.y > b->p1.y) |
b->p1.y = box->p1.y, changed = TRUE; |
if (box->p2.y < b->p2.y) |
b->p2.y = box->p2.y, changed = TRUE; |
|
j += b->p2.x > b->p1.x && b->p2.y > b->p1.y; |
} |
clip->num_boxes = j; |
|
if (clip->num_boxes == 0) |
return _cairo_clip_set_all_clipped (clip); |
|
if (! changed) |
return clip; |
|
extents_box = clip->boxes[0]; |
for (i = 1; i < clip->num_boxes; i++) { |
if (clip->boxes[i].p1.x < extents_box.p1.x) |
extents_box.p1.x = clip->boxes[i].p1.x; |
|
if (clip->boxes[i].p1.y < extents_box.p1.y) |
extents_box.p1.y = clip->boxes[i].p1.y; |
|
if (clip->boxes[i].p2.x > extents_box.p2.x) |
extents_box.p2.x = clip->boxes[i].p2.x; |
|
if (clip->boxes[i].p2.y > extents_box.p2.y) |
extents_box.p2.y = clip->boxes[i].p2.y; |
} |
|
if (clip->path == NULL) { |
_cairo_box_round_to_rectangle (&extents_box, &clip->extents); |
} else { |
cairo_rectangle_int_t extents_rect; |
|
_cairo_box_round_to_rectangle (&extents_box, &extents_rect); |
if (! _cairo_rectangle_intersect (&clip->extents, &extents_rect)) |
return _cairo_clip_set_all_clipped (clip); |
} |
|
if (clip->region) { |
cairo_region_destroy (clip->region); |
clip->region = NULL; |
} |
|
clip->is_region = FALSE; |
return clip; |
} |
|
cairo_clip_t * |
_cairo_clip_intersect_box (cairo_clip_t *clip, |
const cairo_box_t *box) |
{ |
cairo_rectangle_int_t r; |
|
_cairo_box_round_to_rectangle (box, &r); |
if (r.width == 0 || r.height == 0) |
return _cairo_clip_set_all_clipped (clip); |
|
return _cairo_clip_intersect_rectangle_box (clip, &r, box); |
} |
|
cairo_clip_t * |
_cairo_clip_intersect_boxes (cairo_clip_t *clip, |
const cairo_boxes_t *boxes) |
{ |
cairo_boxes_t clip_boxes; |
cairo_box_t limits; |
cairo_rectangle_int_t extents; |
|
if (_cairo_clip_is_all_clipped (clip)) |
return clip; |
|
if (boxes->num_boxes == 0) |
return _cairo_clip_set_all_clipped (clip); |
|
if (boxes->num_boxes == 1) |
return _cairo_clip_intersect_box (clip, boxes->chunks.base); |
|
if (clip == NULL) |
clip = _cairo_clip_create (); |
|
if (clip->num_boxes) { |
_cairo_boxes_init_for_array (&clip_boxes, clip->boxes, clip->num_boxes); |
if (unlikely (_cairo_boxes_intersect (&clip_boxes, boxes, &clip_boxes))) { |
clip = _cairo_clip_set_all_clipped (clip); |
goto out; |
} |
|
if (clip->boxes != &clip->embedded_box) |
free (clip->boxes); |
|
clip->boxes = NULL; |
boxes = &clip_boxes; |
} |
|
if (boxes->num_boxes == 0) { |
clip = _cairo_clip_set_all_clipped (clip); |
goto out; |
} else if (boxes->num_boxes == 1) { |
clip->boxes = &clip->embedded_box; |
clip->boxes[0] = boxes->chunks.base[0]; |
clip->num_boxes = 1; |
} else { |
clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes, TRUE); |
} |
_cairo_boxes_extents (boxes, &limits); |
|
_cairo_box_round_to_rectangle (&limits, &extents); |
if (clip->path == NULL) |
clip->extents = extents; |
else if (! _cairo_rectangle_intersect (&clip->extents, &extents)) |
clip = _cairo_clip_set_all_clipped (clip); |
|
if (clip->region) { |
cairo_region_destroy (clip->region); |
clip->region = NULL; |
} |
clip->is_region = FALSE; |
|
out: |
if (boxes == &clip_boxes) |
_cairo_boxes_fini (&clip_boxes); |
|
return clip; |
} |
|
cairo_clip_t * |
_cairo_clip_intersect_rectangle (cairo_clip_t *clip, |
const cairo_rectangle_int_t *r) |
{ |
cairo_box_t box; |
|
if (_cairo_clip_is_all_clipped (clip)) |
return clip; |
|
if (r->width == 0 || r->height == 0) |
return _cairo_clip_set_all_clipped (clip); |
|
box.p1.x = _cairo_fixed_from_int (r->x); |
box.p1.y = _cairo_fixed_from_int (r->y); |
box.p2.x = _cairo_fixed_from_int (r->x + r->width); |
box.p2.y = _cairo_fixed_from_int (r->y + r->height); |
|
return _cairo_clip_intersect_rectangle_box (clip, r, &box); |
} |
|
struct reduce { |
cairo_clip_t *clip; |
cairo_box_t limit; |
cairo_box_t extents; |
cairo_bool_t inside; |
|
cairo_point_t current_point; |
cairo_point_t last_move_to; |
}; |
|
static void |
_add_clipped_edge (struct reduce *r, |
const cairo_point_t *p1, |
const cairo_point_t *p2, |
int y1, int y2) |
{ |
cairo_fixed_t x; |
|
x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y1); |
if (x < r->extents.p1.x) |
r->extents.p1.x = x; |
|
x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y2); |
if (x > r->extents.p2.x) |
r->extents.p2.x = x; |
|
if (y1 < r->extents.p1.y) |
r->extents.p1.y = y1; |
|
if (y2 > r->extents.p2.y) |
r->extents.p2.y = y2; |
|
r->inside = TRUE; |
} |
|
static void |
_add_edge (struct reduce *r, |
const cairo_point_t *p1, |
const cairo_point_t *p2) |
{ |
int top, bottom; |
int top_y, bot_y; |
int n; |
|
if (p1->y < p2->y) { |
top = p1->y; |
bottom = p2->y; |
} else { |
top = p2->y; |
bottom = p1->y; |
} |
|
if (bottom < r->limit.p1.y || top > r->limit.p2.y) |
return; |
|
if (p1->x > p2->x) { |
const cairo_point_t *t = p1; |
p1 = p2; |
p2 = t; |
} |
|
if (p2->x <= r->limit.p1.x || p1->x >= r->limit.p2.x) |
return; |
|
for (n = 0; n < r->clip->num_boxes; n++) { |
const cairo_box_t *limits = &r->clip->boxes[n]; |
|
if (bottom < limits->p1.y || top > limits->p2.y) |
continue; |
|
if (p2->x <= limits->p1.x || p1->x >= limits->p2.x) |
continue; |
|
if (p1->x >= limits->p1.x && p2->x <= limits->p1.x) { |
top_y = top; |
bot_y = bottom; |
} else { |
int p1_y, p2_y; |
|
p1_y = _cairo_edge_compute_intersection_y_for_x (p1, p2, |
limits->p1.x); |
p2_y = _cairo_edge_compute_intersection_y_for_x (p1, p2, |
limits->p2.x); |
if (p1_y < p2_y) { |
top_y = p1_y; |
bot_y = p2_y; |
} else { |
top_y = p2_y; |
bot_y = p1_y; |
} |
|
if (top_y < top) |
top_y = top; |
if (bot_y > bottom) |
bot_y = bottom; |
} |
|
if (top_y < limits->p1.y) |
top_y = limits->p1.y; |
|
if (bot_y > limits->p2.y) |
bot_y = limits->p2.y; |
if (bot_y > top_y) |
_add_clipped_edge (r, p1, p2, top_y, bot_y); |
} |
} |
|
static cairo_status_t |
_reduce_line_to (void *closure, |
const cairo_point_t *point) |
{ |
struct reduce *r = closure; |
|
_add_edge (r, &r->current_point, point); |
r->current_point = *point; |
|
return CAIRO_STATUS_SUCCESS; |
} |
|
static cairo_status_t |
_reduce_close (void *closure) |
{ |
struct reduce *r = closure; |
|
return _reduce_line_to (r, &r->last_move_to); |
} |
|
static cairo_status_t |
_reduce_move_to (void *closure, |
const cairo_point_t *point) |
{ |
struct reduce *r = closure; |
cairo_status_t status; |
|
/* close current subpath */ |
status = _reduce_close (closure); |
|
/* make sure that the closure represents a degenerate path */ |
r->current_point = *point; |
r->last_move_to = *point; |
|
return status; |
} |
|
static cairo_clip_t * |
_cairo_clip_reduce_to_boxes (cairo_clip_t *clip) |
{ |
struct reduce r; |
cairo_clip_path_t *clip_path; |
cairo_status_t status; |
|
return clip; |
if (clip->path == NULL) |
return clip; |
|
r.clip = clip; |
r.extents.p1.x = r.extents.p1.y = INT_MAX; |
r.extents.p2.x = r.extents.p2.y = INT_MIN; |
r.inside = FALSE; |
|
r.limit.p1.x = _cairo_fixed_from_int (clip->extents.x); |
r.limit.p1.y = _cairo_fixed_from_int (clip->extents.y); |
r.limit.p2.x = _cairo_fixed_from_int (clip->extents.x + clip->extents.width); |
r.limit.p2.y = _cairo_fixed_from_int (clip->extents.y + clip->extents.height); |
|
clip_path = clip->path; |
do { |
r.current_point.x = 0; |
r.current_point.y = 0; |
r.last_move_to = r.current_point; |
|
status = _cairo_path_fixed_interpret_flat (&clip_path->path, |
_reduce_move_to, |
_reduce_line_to, |
_reduce_close, |
&r, |
clip_path->tolerance); |
assert (status == CAIRO_STATUS_SUCCESS); |
_reduce_close (&r); |
} while ((clip_path = clip_path->prev)); |
|
if (! r.inside) { |
_cairo_clip_path_destroy (clip->path); |
clip->path = NULL; |
} |
|
return _cairo_clip_intersect_box (clip, &r.extents); |
} |
|
cairo_clip_t * |
_cairo_clip_reduce_to_rectangle (const cairo_clip_t *clip, |
const cairo_rectangle_int_t *r) |
{ |
cairo_clip_t *copy; |
|
if (_cairo_clip_is_all_clipped (clip)) |
return (cairo_clip_t *) clip; |
|
if (_cairo_clip_contains_rectangle (clip, r)) |
return _cairo_clip_intersect_rectangle (NULL, r); |
|
copy = _cairo_clip_copy_intersect_rectangle (clip, r); |
if (_cairo_clip_is_all_clipped (copy)) |
return copy; |
|
return _cairo_clip_reduce_to_boxes (copy); |
} |
|
cairo_clip_t * |
_cairo_clip_reduce_for_composite (const cairo_clip_t *clip, |
cairo_composite_rectangles_t *extents) |
{ |
const cairo_rectangle_int_t *r; |
|
r = extents->is_bounded ? &extents->bounded : &extents->unbounded; |
return _cairo_clip_reduce_to_rectangle (clip, r); |
} |
|
cairo_clip_t * |
_cairo_clip_from_boxes (const cairo_boxes_t *boxes) |
{ |
cairo_box_t extents; |
cairo_clip_t *clip = _cairo_clip_create (); |
if (clip == NULL) |
return _cairo_clip_set_all_clipped (clip); |
|
/* XXX cow-boxes? */ |
if(boxes->num_boxes == 1) { |
clip->boxes = &clip->embedded_box; |
clip->boxes[0] = boxes->chunks.base[0]; |
clip->num_boxes = 1; |
} else { |
clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes, TRUE); |
if (clip->boxes == NULL) |
return _cairo_clip_set_all_clipped (clip); |
} |
|
_cairo_boxes_extents (boxes, &extents); |
_cairo_box_round_to_rectangle (&extents, &clip->extents); |
|
return clip; |
} |