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
4
* Copyright © 2002 University of Southern California
5
* Copyright © 2005 Red Hat, Inc.
6
* Copyright © 2009 Chris Wilson
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.
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
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/
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.
31
* The Original Code is the cairo graphics library.
33
* The Initial Developer of the Original Code is University of Southern
37
* Carl D. Worth <cworth@cworth.org>
38
* Kristian Høgsberg <krh@redhat.com>
39
* Chris Wilson <chris@chris-wilson.co.uk>
43
#include "cairo-clip-inline.h"
44
#include "cairo-clip-private.h"
45
#include "cairo-error-private.h"
46
#include "cairo-freed-pool-private.h"
47
#include "cairo-gstate-private.h"
48
#include "cairo-path-fixed-private.h"
49
#include "cairo-pattern-private.h"
50
#include "cairo-composite-rectangles-private.h"
51
#include "cairo-region-private.h"
53
static freed_pool_t clip_path_pool;
54
static freed_pool_t clip_pool;
56
const cairo_clip_t __cairo_clip_all;
58
static cairo_clip_path_t *
59
_cairo_clip_path_create (cairo_clip_t *clip)
61
cairo_clip_path_t *clip_path;
63
clip_path = _freed_pool_get (&clip_path_pool);
64
if (unlikely (clip_path == NULL)) {
65
clip_path = malloc (sizeof (cairo_clip_path_t));
66
if (unlikely (clip_path == NULL))
70
CAIRO_REFERENCE_COUNT_INIT (&clip_path->ref_count, 1);
72
clip_path->prev = clip->path;
73
clip->path = clip_path;
79
_cairo_clip_path_reference (cairo_clip_path_t *clip_path)
81
assert (CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&clip_path->ref_count));
83
_cairo_reference_count_inc (&clip_path->ref_count);
89
_cairo_clip_path_destroy (cairo_clip_path_t *clip_path)
91
assert (CAIRO_REFERENCE_COUNT_HAS_REFERENCE (&clip_path->ref_count));
93
if (! _cairo_reference_count_dec_and_test (&clip_path->ref_count))
96
_cairo_path_fixed_fini (&clip_path->path);
98
if (clip_path->prev != NULL)
99
_cairo_clip_path_destroy (clip_path->prev);
101
_freed_pool_put (&clip_path_pool, clip_path);
105
_cairo_clip_create (void)
109
clip = _freed_pool_get (&clip_pool);
110
if (unlikely (clip == NULL)) {
111
clip = malloc (sizeof (cairo_clip_t));
112
if (unlikely (clip == NULL))
116
clip->extents = _cairo_unbounded_rectangle;
122
clip->is_region = FALSE;
128
_cairo_clip_destroy (cairo_clip_t *clip)
130
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
133
if (clip->path != NULL)
134
_cairo_clip_path_destroy (clip->path);
136
if (clip->boxes != &clip->embedded_box)
138
cairo_region_destroy (clip->region);
140
_freed_pool_put (&clip_pool, clip);
144
_cairo_clip_copy (const cairo_clip_t *clip)
148
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
149
return (cairo_clip_t *) clip;
151
copy = _cairo_clip_create ();
154
copy->path = _cairo_clip_path_reference (clip->path);
156
if (clip->num_boxes) {
157
if (clip->num_boxes == 1) {
158
copy->boxes = ©->embedded_box;
160
copy->boxes = _cairo_malloc_ab (clip->num_boxes, sizeof (cairo_box_t));
161
if (unlikely (copy->boxes == NULL))
162
return _cairo_clip_set_all_clipped (copy);
165
memcpy (copy->boxes, clip->boxes,
166
clip->num_boxes * sizeof (cairo_box_t));
167
copy->num_boxes = clip->num_boxes;
170
copy->extents = clip->extents;
171
copy->region = cairo_region_reference (clip->region);
172
copy->is_region = clip->is_region;
178
_cairo_clip_copy_path (const cairo_clip_t *clip)
182
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
183
return (cairo_clip_t *) clip;
185
assert (clip->num_boxes);
187
copy = _cairo_clip_create ();
188
copy->extents = clip->extents;
190
copy->path = _cairo_clip_path_reference (clip->path);
196
_cairo_clip_copy_region (const cairo_clip_t *clip)
201
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
202
return (cairo_clip_t *) clip;
204
assert (clip->num_boxes);
206
copy = _cairo_clip_create ();
207
copy->extents = clip->extents;
209
if (clip->num_boxes == 1) {
210
copy->boxes = ©->embedded_box;
212
copy->boxes = _cairo_malloc_ab (clip->num_boxes, sizeof (cairo_box_t));
213
if (unlikely (copy->boxes == NULL))
214
return _cairo_clip_set_all_clipped (copy);
217
for (i = 0; i < clip->num_boxes; i++) {
218
copy->boxes[i].p1.x = _cairo_fixed_floor (clip->boxes[i].p1.x);
219
copy->boxes[i].p1.y = _cairo_fixed_floor (clip->boxes[i].p1.y);
220
copy->boxes[i].p2.x = _cairo_fixed_ceil (clip->boxes[i].p2.x);
221
copy->boxes[i].p2.y = _cairo_fixed_ceil (clip->boxes[i].p2.y);
223
copy->num_boxes = clip->num_boxes;
225
copy->region = cairo_region_reference (clip->region);
226
copy->is_region = TRUE;
232
_cairo_clip_intersect_path (cairo_clip_t *clip,
233
const cairo_path_fixed_t *path,
234
cairo_fill_rule_t fill_rule,
236
cairo_antialias_t antialias)
238
cairo_clip_path_t *clip_path;
239
cairo_status_t status;
240
cairo_rectangle_int_t extents;
243
if (_cairo_clip_is_all_clipped (clip))
246
/* catch the empty clip path */
247
if (_cairo_path_fixed_fill_is_empty (path))
248
return _cairo_clip_set_all_clipped (clip);
250
if (_cairo_path_fixed_is_box (path, &box)) {
251
if (antialias == CAIRO_ANTIALIAS_NONE) {
252
box.p1.x = _cairo_fixed_round_down (box.p1.x);
253
box.p1.y = _cairo_fixed_round_down (box.p1.y);
254
box.p2.x = _cairo_fixed_round_down (box.p2.x);
255
box.p2.y = _cairo_fixed_round_down (box.p2.y);
258
return _cairo_clip_intersect_box (clip, &box);
260
if (_cairo_path_fixed_fill_is_rectilinear (path))
261
return _cairo_clip_intersect_rectilinear_path (clip, path,
262
fill_rule, antialias);
264
_cairo_path_fixed_approximate_clip_extents (path, &extents);
265
if (extents.width == 0 || extents.height == 0)
266
return _cairo_clip_set_all_clipped (clip);
268
clip = _cairo_clip_intersect_rectangle (clip, &extents);
269
if (_cairo_clip_is_all_clipped (clip))
272
clip_path = _cairo_clip_path_create (clip);
273
if (unlikely (clip_path == NULL))
274
return _cairo_clip_set_all_clipped (clip);
276
status = _cairo_path_fixed_init_copy (&clip_path->path, path);
277
if (unlikely (status))
278
return _cairo_clip_set_all_clipped (clip);
280
clip_path->fill_rule = fill_rule;
281
clip_path->tolerance = tolerance;
282
clip_path->antialias = antialias;
285
cairo_region_destroy (clip->region);
289
clip->is_region = FALSE;
293
static cairo_clip_t *
294
_cairo_clip_intersect_clip_path (cairo_clip_t *clip,
295
const cairo_clip_path_t *clip_path)
298
clip = _cairo_clip_intersect_clip_path (clip, clip_path->prev);
300
return _cairo_clip_intersect_path (clip,
302
clip_path->fill_rule,
303
clip_path->tolerance,
304
clip_path->antialias);
308
_cairo_clip_intersect_clip (cairo_clip_t *clip,
309
const cairo_clip_t *other)
311
if (_cairo_clip_is_all_clipped (clip))
318
return _cairo_clip_copy (other);
320
if (_cairo_clip_is_all_clipped (other))
321
return _cairo_clip_set_all_clipped (clip);
323
if (! _cairo_rectangle_intersect (&clip->extents, &other->extents))
324
return _cairo_clip_set_all_clipped (clip);
326
if (other->num_boxes) {
329
_cairo_boxes_init_for_array (&boxes, other->boxes, other->num_boxes);
330
clip = _cairo_clip_intersect_boxes (clip, &boxes);
333
if (! _cairo_clip_is_all_clipped (clip)) {
335
if (clip->path == NULL)
336
clip->path = _cairo_clip_path_reference (other->path);
338
clip = _cairo_clip_intersect_clip_path (clip, other->path);
343
cairo_region_destroy (clip->region);
346
clip->is_region = FALSE;
352
_cairo_clip_equal (const cairo_clip_t *clip_a,
353
const cairo_clip_t *clip_b)
355
const cairo_clip_path_t *cp_a, *cp_b;
357
/* are both all-clipped or no-clip? */
358
if (clip_a == clip_b)
361
/* or just one of them? */
362
if (clip_a == NULL || clip_b == NULL ||
363
_cairo_clip_is_all_clipped (clip_a) ||
364
_cairo_clip_is_all_clipped (clip_b))
369
/* We have a pair of normal clips, check their contents */
371
if (clip_a->num_boxes != clip_b->num_boxes)
374
if (memcmp (clip_a->boxes, clip_b->boxes,
375
sizeof (cairo_box_t) * clip_a->num_boxes))
380
while (cp_a && cp_b) {
384
/* XXX compare reduced polygons? */
386
if (cp_a->antialias != cp_b->antialias)
389
if (cp_a->tolerance != cp_b->tolerance)
392
if (cp_a->fill_rule != cp_b->fill_rule)
395
if (! _cairo_path_fixed_equal (&cp_a->path,
403
return cp_a == NULL && cp_b == NULL;
406
static cairo_clip_t *
407
_cairo_clip_path_copy_with_translation (cairo_clip_t *clip,
408
cairo_clip_path_t *other_path,
411
cairo_status_t status;
412
cairo_clip_path_t *clip_path;
414
if (other_path->prev != NULL)
415
clip = _cairo_clip_path_copy_with_translation (clip, other_path->prev,
417
if (_cairo_clip_is_all_clipped (clip))
420
clip_path = _cairo_clip_path_create (clip);
421
if (unlikely (clip_path == NULL))
422
return _cairo_clip_set_all_clipped (clip);
424
status = _cairo_path_fixed_init_copy (&clip_path->path,
426
if (unlikely (status))
427
return _cairo_clip_set_all_clipped (clip);
429
_cairo_path_fixed_translate (&clip_path->path, fx, fy);
431
clip_path->fill_rule = other_path->fill_rule;
432
clip_path->tolerance = other_path->tolerance;
433
clip_path->antialias = other_path->antialias;
439
_cairo_clip_translate (cairo_clip_t *clip, int tx, int ty)
442
cairo_clip_path_t *clip_path;
444
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
447
if (tx == 0 && ty == 0)
450
fx = _cairo_fixed_from_int (tx);
451
fy = _cairo_fixed_from_int (ty);
453
for (i = 0; i < clip->num_boxes; i++) {
454
clip->boxes[i].p1.x += fx;
455
clip->boxes[i].p2.x += fx;
456
clip->boxes[i].p1.y += fy;
457
clip->boxes[i].p2.y += fy;
460
clip->extents.x += tx;
461
clip->extents.y += ty;
463
if (clip->path == NULL)
466
clip_path = clip->path;
468
clip = _cairo_clip_path_copy_with_translation (clip, clip_path, fx, fy);
469
_cairo_clip_path_destroy (clip_path);
474
static cairo_status_t
475
_cairo_path_fixed_add_box (cairo_path_fixed_t *path,
476
const cairo_box_t *box)
478
cairo_status_t status;
480
status = _cairo_path_fixed_move_to (path, box->p1.x, box->p1.y);
481
if (unlikely (status))
484
status = _cairo_path_fixed_line_to (path, box->p2.x, box->p1.y);
485
if (unlikely (status))
488
status = _cairo_path_fixed_line_to (path, box->p2.x, box->p2.y);
489
if (unlikely (status))
492
status = _cairo_path_fixed_line_to (path, box->p1.x, box->p2.y);
493
if (unlikely (status))
496
return _cairo_path_fixed_close_path (path);
499
static cairo_status_t
500
_cairo_path_fixed_init_from_boxes (cairo_path_fixed_t *path,
501
const cairo_boxes_t *boxes)
503
cairo_status_t status;
504
const struct _cairo_boxes_chunk *chunk;
507
_cairo_path_fixed_init (path);
508
if (boxes->num_boxes == 0)
509
return CAIRO_STATUS_SUCCESS;
511
for (chunk = &boxes->chunks; chunk; chunk = chunk->next) {
512
for (i = 0; i < chunk->count; i++) {
513
status = _cairo_path_fixed_add_box (path, &chunk->base[i]);
514
if (unlikely (status)) {
515
_cairo_path_fixed_fini (path);
521
return CAIRO_STATUS_SUCCESS;
524
static cairo_clip_t *
525
_cairo_clip_intersect_clip_path_transformed (cairo_clip_t *clip,
526
const cairo_clip_path_t *clip_path,
527
const cairo_matrix_t *m)
529
cairo_path_fixed_t path;
532
clip = _cairo_clip_intersect_clip_path_transformed (clip,
536
if (_cairo_path_fixed_init_copy (&path, &clip_path->path))
537
return _cairo_clip_set_all_clipped (clip);
539
_cairo_path_fixed_transform (&path, m);
541
clip = _cairo_clip_intersect_path (clip,
543
clip_path->fill_rule,
544
clip_path->tolerance,
545
clip_path->antialias);
546
_cairo_path_fixed_fini (&path);
552
_cairo_clip_transform (cairo_clip_t *clip, const cairo_matrix_t *m)
556
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
559
if (_cairo_matrix_is_translation (m))
560
return _cairo_clip_translate (clip, m->x0, m->y0);
562
copy = _cairo_clip_create ();
564
if (clip->num_boxes) {
565
cairo_path_fixed_t path;
568
_cairo_boxes_init_for_array (&boxes, clip->boxes, clip->num_boxes);
569
_cairo_path_fixed_init_from_boxes (&path, &boxes);
570
_cairo_path_fixed_transform (&path, m);
572
copy = _cairo_clip_intersect_path (copy, &path,
573
CAIRO_FILL_RULE_WINDING,
575
CAIRO_ANTIALIAS_DEFAULT);
577
_cairo_path_fixed_fini (&path);
581
copy = _cairo_clip_intersect_clip_path_transformed (copy, clip->path,m);
583
_cairo_clip_destroy (clip);
588
_cairo_clip_copy_with_translation (const cairo_clip_t *clip, int tx, int ty)
593
if (clip == NULL || _cairo_clip_is_all_clipped (clip))
594
return (cairo_clip_t *)clip;
596
if (tx == 0 && ty == 0)
597
return _cairo_clip_copy (clip);
599
copy = _cairo_clip_create ();
601
return _cairo_clip_set_all_clipped (copy);
603
fx = _cairo_fixed_from_int (tx);
604
fy = _cairo_fixed_from_int (ty);
606
if (clip->num_boxes) {
607
if (clip->num_boxes == 1) {
608
copy->boxes = ©->embedded_box;
610
copy->boxes = _cairo_malloc_ab (clip->num_boxes, sizeof (cairo_box_t));
611
if (unlikely (copy->boxes == NULL))
612
return _cairo_clip_set_all_clipped (copy);
615
for (i = 0; i < clip->num_boxes; i++) {
616
copy->boxes[i].p1.x = clip->boxes[i].p1.x + fx;
617
copy->boxes[i].p2.x = clip->boxes[i].p2.x + fx;
618
copy->boxes[i].p1.y = clip->boxes[i].p1.y + fy;
619
copy->boxes[i].p2.y = clip->boxes[i].p2.y + fy;
621
copy->num_boxes = clip->num_boxes;
624
copy->extents = clip->extents;
625
copy->extents.x += tx;
626
copy->extents.y += ty;
628
if (clip->path == NULL)
631
return _cairo_clip_path_copy_with_translation (copy, clip->path, fx, fy);
635
_cairo_clip_contains_extents (const cairo_clip_t *clip,
636
const cairo_composite_rectangles_t *extents)
638
const cairo_rectangle_int_t *rect;
640
rect = extents->is_bounded ? &extents->bounded : &extents->unbounded;
641
return _cairo_clip_contains_rectangle (clip, rect);
645
_cairo_debug_print_clip (FILE *stream, const cairo_clip_t *clip)
650
fprintf (stream, "no clip\n");
654
if (_cairo_clip_is_all_clipped (clip)) {
655
fprintf (stream, "clip: all-clipped\n");
659
fprintf (stream, "clip:\n");
660
fprintf (stream, " extents: (%d, %d) x (%d, %d), is-region? %d",
661
clip->extents.x, clip->extents.y,
662
clip->extents.width, clip->extents.height,
665
fprintf (stream, " num_boxes = %d\n", clip->num_boxes);
666
for (i = 0; i < clip->num_boxes; i++) {
667
fprintf (stream, " [%d] = (%f, %f), (%f, %f)\n", i,
668
_cairo_fixed_to_double (clip->boxes[i].p1.x),
669
_cairo_fixed_to_double (clip->boxes[i].p1.y),
670
_cairo_fixed_to_double (clip->boxes[i].p2.x),
671
_cairo_fixed_to_double (clip->boxes[i].p2.y));
675
cairo_clip_path_t *clip_path = clip->path;
677
fprintf (stream, "path: aa=%d, tolerance=%f, rule=%d: ",
678
clip_path->antialias,
679
clip_path->tolerance,
680
clip_path->fill_rule);
681
_cairo_debug_print_path (stream, &clip_path->path);
682
fprintf (stream, "\n");
683
} while ((clip_path = clip_path->prev) != NULL);
687
const cairo_rectangle_int_t *
688
_cairo_clip_get_extents (const cairo_clip_t *clip)
691
return &_cairo_unbounded_rectangle;
693
if (_cairo_clip_is_all_clipped (clip))
694
return &_cairo_empty_rectangle;
696
return &clip->extents;
699
const cairo_rectangle_list_t _cairo_rectangles_nil =
700
{ CAIRO_STATUS_NO_MEMORY, NULL, 0 };
701
static const cairo_rectangle_list_t _cairo_rectangles_not_representable =
702
{ CAIRO_STATUS_CLIP_NOT_REPRESENTABLE, NULL, 0 };
705
_cairo_clip_int_rect_to_user (cairo_gstate_t *gstate,
706
cairo_rectangle_int_t *clip_rect,
707
cairo_rectangle_t *user_rect)
709
cairo_bool_t is_tight;
711
double x1 = clip_rect->x;
712
double y1 = clip_rect->y;
713
double x2 = clip_rect->x + (int) clip_rect->width;
714
double y2 = clip_rect->y + (int) clip_rect->height;
716
_cairo_gstate_backend_to_user_rectangle (gstate,
722
user_rect->width = x2 - x1;
723
user_rect->height = y2 - y1;
728
cairo_rectangle_list_t *
729
_cairo_rectangle_list_create_in_error (cairo_status_t status)
731
cairo_rectangle_list_t *list;
733
if (status == CAIRO_STATUS_NO_MEMORY)
734
return (cairo_rectangle_list_t*) &_cairo_rectangles_nil;
735
if (status == CAIRO_STATUS_CLIP_NOT_REPRESENTABLE)
736
return (cairo_rectangle_list_t*) &_cairo_rectangles_not_representable;
738
list = malloc (sizeof (*list));
739
if (unlikely (list == NULL)) {
740
status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
741
return (cairo_rectangle_list_t*) &_cairo_rectangles_nil;
744
list->status = status;
745
list->rectangles = NULL;
746
list->num_rectangles = 0;
751
cairo_rectangle_list_t *
752
_cairo_clip_copy_rectangle_list (cairo_clip_t *clip, cairo_gstate_t *gstate)
754
#define ERROR_LIST(S) _cairo_rectangle_list_create_in_error (_cairo_error (S))
756
cairo_rectangle_list_t *list;
757
cairo_rectangle_t *rectangles = NULL;
758
cairo_region_t *region = NULL;
763
return ERROR_LIST (CAIRO_STATUS_CLIP_NOT_REPRESENTABLE);
765
if (_cairo_clip_is_all_clipped (clip))
768
if (! _cairo_clip_is_region (clip))
769
return ERROR_LIST (CAIRO_STATUS_CLIP_NOT_REPRESENTABLE);
771
region = _cairo_clip_get_region (clip);
773
return ERROR_LIST (CAIRO_STATUS_NO_MEMORY);
775
n_rects = cairo_region_num_rectangles (region);
777
rectangles = _cairo_malloc_ab (n_rects, sizeof (cairo_rectangle_t));
778
if (unlikely (rectangles == NULL)) {
779
return ERROR_LIST (CAIRO_STATUS_NO_MEMORY);
782
for (i = 0; i < n_rects; ++i) {
783
cairo_rectangle_int_t clip_rect;
785
cairo_region_get_rectangle (region, i, &clip_rect);
787
if (! _cairo_clip_int_rect_to_user (gstate,
792
return ERROR_LIST (CAIRO_STATUS_CLIP_NOT_REPRESENTABLE);
798
list = malloc (sizeof (cairo_rectangle_list_t));
799
if (unlikely (list == NULL)) {
801
return ERROR_LIST (CAIRO_STATUS_NO_MEMORY);
804
list->status = CAIRO_STATUS_SUCCESS;
805
list->rectangles = rectangles;
806
list->num_rectangles = n_rects;
813
* cairo_rectangle_list_destroy:
814
* @rectangle_list: a rectangle list, as obtained from cairo_copy_clip_rectangle_list()
816
* Unconditionally frees @rectangle_list and all associated
817
* references. After this call, the @rectangle_list pointer must not
823
cairo_rectangle_list_destroy (cairo_rectangle_list_t *rectangle_list)
825
if (rectangle_list == NULL || rectangle_list == &_cairo_rectangles_nil ||
826
rectangle_list == &_cairo_rectangles_not_representable)
829
free (rectangle_list->rectangles);
830
free (rectangle_list);
834
_cairo_clip_reset_static_data (void)
836
_freed_pool_reset (&clip_path_pool);
837
_freed_pool_reset (&clip_pool);