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
pot(int v)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
_cairo_clip_contains_rectangle_box(const cairo_clip_t * clip,const cairo_rectangle_int_t * rect,const cairo_box_t * box)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
_cairo_clip_contains_box(const cairo_clip_t * clip,const cairo_box_t * box)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
_cairo_clip_contains_rectangle(const cairo_clip_t * clip,const cairo_rectangle_int_t * rect)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 _cairo_box_from_rectangle_int (&box, rect);
123 return _cairo_clip_contains_rectangle_box (clip, rect, &box);
124 }
125
126 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)127 _cairo_clip_intersect_rectilinear_path (cairo_clip_t *clip,
128 const cairo_path_fixed_t *path,
129 cairo_fill_rule_t fill_rule,
130 cairo_antialias_t antialias)
131 {
132 cairo_status_t status;
133 cairo_boxes_t boxes;
134
135 _cairo_boxes_init (&boxes);
136 status = _cairo_path_fixed_fill_rectilinear_to_boxes (path,
137 fill_rule,
138 antialias,
139 &boxes);
140 if (likely (status == CAIRO_STATUS_SUCCESS && boxes.num_boxes))
141 clip = _cairo_clip_intersect_boxes (clip, &boxes);
142 else
143 clip = _cairo_clip_set_all_clipped (clip);
144 _cairo_boxes_fini (&boxes);
145
146 return clip;
147 }
148
149 static cairo_clip_t *
_cairo_clip_intersect_rectangle_box(cairo_clip_t * clip,const cairo_rectangle_int_t * r,const cairo_box_t * box)150 _cairo_clip_intersect_rectangle_box (cairo_clip_t *clip,
151 const cairo_rectangle_int_t *r,
152 const cairo_box_t *box)
153 {
154 cairo_box_t extents_box;
155 cairo_bool_t changed = FALSE;
156 int i, j;
157
158 if (clip == NULL) {
159 clip = _cairo_clip_create ();
160 if (clip == NULL)
161 return _cairo_clip_set_all_clipped (clip);
162 }
163
164 if (clip->num_boxes == 0) {
165 clip->boxes = &clip->embedded_box;
166 clip->boxes[0] = *box;
167 clip->num_boxes = 1;
168 if (clip->path == NULL) {
169 clip->extents = *r;
170 } else {
171 if (! _cairo_rectangle_intersect (&clip->extents, r))
172 return _cairo_clip_set_all_clipped (clip);
173 }
174 if (clip->path == NULL)
175 clip->is_region = _cairo_box_is_pixel_aligned (box);
176 return clip;
177 }
178
179 /* Does the new box wholly subsume the clip? Perform a cheap check
180 * for the common condition of a single clip rectangle.
181 */
182 if (clip->num_boxes == 1 &&
183 clip->boxes[0].p1.x >= box->p1.x &&
184 clip->boxes[0].p1.y >= box->p1.y &&
185 clip->boxes[0].p2.x <= box->p2.x &&
186 clip->boxes[0].p2.y <= box->p2.y)
187 {
188 return clip;
189 }
190
191 for (i = j = 0; i < clip->num_boxes; i++) {
192 cairo_box_t *b = &clip->boxes[j];
193
194 if (j != i)
195 *b = clip->boxes[i];
196
197 if (box->p1.x > b->p1.x)
198 b->p1.x = box->p1.x, changed = TRUE;
199 if (box->p2.x < b->p2.x)
200 b->p2.x = box->p2.x, changed = TRUE;
201
202 if (box->p1.y > b->p1.y)
203 b->p1.y = box->p1.y, changed = TRUE;
204 if (box->p2.y < b->p2.y)
205 b->p2.y = box->p2.y, changed = TRUE;
206
207 j += b->p2.x > b->p1.x && b->p2.y > b->p1.y;
208 }
209 clip->num_boxes = j;
210
211 if (clip->num_boxes == 0)
212 return _cairo_clip_set_all_clipped (clip);
213
214 if (! changed)
215 return clip;
216
217 extents_box = clip->boxes[0];
218 for (i = 1; i < clip->num_boxes; i++) {
219 if (clip->boxes[i].p1.x < extents_box.p1.x)
220 extents_box.p1.x = clip->boxes[i].p1.x;
221
222 if (clip->boxes[i].p1.y < extents_box.p1.y)
223 extents_box.p1.y = clip->boxes[i].p1.y;
224
225 if (clip->boxes[i].p2.x > extents_box.p2.x)
226 extents_box.p2.x = clip->boxes[i].p2.x;
227
228 if (clip->boxes[i].p2.y > extents_box.p2.y)
229 extents_box.p2.y = clip->boxes[i].p2.y;
230 }
231
232 if (clip->path == NULL) {
233 _cairo_box_round_to_rectangle (&extents_box, &clip->extents);
234 } else {
235 cairo_rectangle_int_t extents_rect;
236
237 _cairo_box_round_to_rectangle (&extents_box, &extents_rect);
238 if (! _cairo_rectangle_intersect (&clip->extents, &extents_rect))
239 return _cairo_clip_set_all_clipped (clip);
240 }
241
242 if (clip->region) {
243 cairo_region_destroy (clip->region);
244 clip->region = NULL;
245 }
246
247 clip->is_region = FALSE;
248 return clip;
249 }
250
251 cairo_clip_t *
_cairo_clip_intersect_box(cairo_clip_t * clip,const cairo_box_t * box)252 _cairo_clip_intersect_box (cairo_clip_t *clip,
253 const cairo_box_t *box)
254 {
255 cairo_rectangle_int_t r;
256
257 if (_cairo_clip_is_all_clipped (clip))
258 return clip;
259
260 _cairo_box_round_to_rectangle (box, &r);
261 if (r.width == 0 || r.height == 0)
262 return _cairo_clip_set_all_clipped (clip);
263
264 return _cairo_clip_intersect_rectangle_box (clip, &r, box);
265 }
266
267 /* Copy a box set to a clip
268 *
269 * @param boxes The box set to copy from.
270 * @param clip The clip to copy to (return buffer).
271 * @returns Zero if the allocation failed (the clip will be set to
272 * all-clipped), otherwise non-zero.
273 */
274 static cairo_bool_t
_cairo_boxes_copy_to_clip(const cairo_boxes_t * boxes,cairo_clip_t * clip)275 _cairo_boxes_copy_to_clip (const cairo_boxes_t *boxes, cairo_clip_t *clip)
276 {
277 /* XXX cow-boxes? */
278 if (boxes->num_boxes == 1) {
279 clip->boxes = &clip->embedded_box;
280 clip->boxes[0] = boxes->chunks.base[0];
281 clip->num_boxes = 1;
282 return TRUE;
283 }
284
285 clip->boxes = _cairo_boxes_to_array (boxes, &clip->num_boxes);
286 if (unlikely (clip->boxes == NULL))
287 {
288 _cairo_clip_set_all_clipped (clip);
289 return FALSE;
290 }
291
292 return TRUE;
293 }
294
295 cairo_clip_t *
_cairo_clip_intersect_boxes(cairo_clip_t * clip,const cairo_boxes_t * boxes)296 _cairo_clip_intersect_boxes (cairo_clip_t *clip,
297 const cairo_boxes_t *boxes)
298 {
299 cairo_boxes_t clip_boxes;
300 cairo_box_t limits;
301 cairo_rectangle_int_t extents;
302
303 if (_cairo_clip_is_all_clipped (clip))
304 return clip;
305
306 if (boxes->num_boxes == 0)
307 return _cairo_clip_set_all_clipped (clip);
308
309 if (boxes->num_boxes == 1)
310 return _cairo_clip_intersect_box (clip, boxes->chunks.base);
311
312 if (clip == NULL)
313 clip = _cairo_clip_create ();
314
315 if (clip->num_boxes) {
316 _cairo_boxes_init_for_array (&clip_boxes, clip->boxes, clip->num_boxes);
317 if (unlikely (_cairo_boxes_intersect (&clip_boxes, boxes, &clip_boxes))) {
318 clip = _cairo_clip_set_all_clipped (clip);
319 goto out;
320 }
321
322 if (clip->boxes != &clip->embedded_box)
323 free (clip->boxes);
324
325 clip->boxes = NULL;
326 boxes = &clip_boxes;
327 }
328
329 if (boxes->num_boxes == 0) {
330 clip = _cairo_clip_set_all_clipped (clip);
331 goto out;
332 }
333
334 _cairo_boxes_copy_to_clip (boxes, clip);
335
336 _cairo_boxes_extents (boxes, &limits);
337
338 _cairo_box_round_to_rectangle (&limits, &extents);
339 if (clip->path == NULL) {
340 clip->extents = extents;
341 } else if (! _cairo_rectangle_intersect (&clip->extents, &extents)) {
342 clip = _cairo_clip_set_all_clipped (clip);
343 goto out;
344 }
345
346 if (clip->region) {
347 cairo_region_destroy (clip->region);
348 clip->region = NULL;
349 }
350 clip->is_region = FALSE;
351
352 out:
353 if (boxes == &clip_boxes)
354 _cairo_boxes_fini (&clip_boxes);
355
356 return clip;
357 }
358
359 cairo_clip_t *
_cairo_clip_intersect_rectangle(cairo_clip_t * clip,const cairo_rectangle_int_t * r)360 _cairo_clip_intersect_rectangle (cairo_clip_t *clip,
361 const cairo_rectangle_int_t *r)
362 {
363 cairo_box_t box;
364
365 if (_cairo_clip_is_all_clipped (clip))
366 return clip;
367
368 if (r->width == 0 || r->height == 0)
369 return _cairo_clip_set_all_clipped (clip);
370
371 _cairo_box_from_rectangle_int (&box, r);
372
373 return _cairo_clip_intersect_rectangle_box (clip, r, &box);
374 }
375
376 struct reduce {
377 cairo_clip_t *clip;
378 cairo_box_t limit;
379 cairo_box_t extents;
380 cairo_bool_t inside;
381
382 cairo_point_t current_point;
383 cairo_point_t last_move_to;
384 };
385
386 static void
_add_clipped_edge(struct reduce * r,const cairo_point_t * p1,const cairo_point_t * p2,int y1,int y2)387 _add_clipped_edge (struct reduce *r,
388 const cairo_point_t *p1,
389 const cairo_point_t *p2,
390 int y1, int y2)
391 {
392 cairo_fixed_t x;
393
394 x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y1);
395 if (x < r->extents.p1.x)
396 r->extents.p1.x = x;
397
398 x = _cairo_edge_compute_intersection_x_for_y (p1, p2, y2);
399 if (x > r->extents.p2.x)
400 r->extents.p2.x = x;
401
402 if (y1 < r->extents.p1.y)
403 r->extents.p1.y = y1;
404
405 if (y2 > r->extents.p2.y)
406 r->extents.p2.y = y2;
407
408 r->inside = TRUE;
409 }
410
411 static void
_add_edge(struct reduce * r,const cairo_point_t * p1,const cairo_point_t * p2)412 _add_edge (struct reduce *r,
413 const cairo_point_t *p1,
414 const cairo_point_t *p2)
415 {
416 int top, bottom;
417 int top_y, bot_y;
418 int n;
419
420 if (p1->y < p2->y) {
421 top = p1->y;
422 bottom = p2->y;
423 } else {
424 top = p2->y;
425 bottom = p1->y;
426 }
427
428 if (bottom < r->limit.p1.y || top > r->limit.p2.y)
429 return;
430
431 if (p1->x > p2->x) {
432 const cairo_point_t *t = p1;
433 p1 = p2;
434 p2 = t;
435 }
436
437 if (p2->x <= r->limit.p1.x || p1->x >= r->limit.p2.x)
438 return;
439
440 for (n = 0; n < r->clip->num_boxes; n++) {
441 const cairo_box_t *limits = &r->clip->boxes[n];
442
443 if (bottom < limits->p1.y || top > limits->p2.y)
444 continue;
445
446 if (p2->x <= limits->p1.x || p1->x >= limits->p2.x)
447 continue;
448
449 if (p1->x >= limits->p1.x && p2->x <= limits->p1.x) {
450 top_y = top;
451 bot_y = bottom;
452 } else {
453 int p1_y, p2_y;
454
455 p1_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
456 limits->p1.x);
457 p2_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
458 limits->p2.x);
459 if (p1_y < p2_y) {
460 top_y = p1_y;
461 bot_y = p2_y;
462 } else {
463 top_y = p2_y;
464 bot_y = p1_y;
465 }
466
467 if (top_y < top)
468 top_y = top;
469 if (bot_y > bottom)
470 bot_y = bottom;
471 }
472
473 if (top_y < limits->p1.y)
474 top_y = limits->p1.y;
475
476 if (bot_y > limits->p2.y)
477 bot_y = limits->p2.y;
478 if (bot_y > top_y)
479 _add_clipped_edge (r, p1, p2, top_y, bot_y);
480 }
481 }
482
483 static cairo_status_t
_reduce_line_to(void * closure,const cairo_point_t * point)484 _reduce_line_to (void *closure,
485 const cairo_point_t *point)
486 {
487 struct reduce *r = closure;
488
489 _add_edge (r, &r->current_point, point);
490 r->current_point = *point;
491
492 return CAIRO_STATUS_SUCCESS;
493 }
494
495 static cairo_status_t
_reduce_close(void * closure)496 _reduce_close (void *closure)
497 {
498 struct reduce *r = closure;
499
500 return _reduce_line_to (r, &r->last_move_to);
501 }
502
503 static cairo_status_t
_reduce_move_to(void * closure,const cairo_point_t * point)504 _reduce_move_to (void *closure,
505 const cairo_point_t *point)
506 {
507 struct reduce *r = closure;
508 cairo_status_t status;
509
510 /* close current subpath */
511 status = _reduce_close (closure);
512
513 /* make sure that the closure represents a degenerate path */
514 r->current_point = *point;
515 r->last_move_to = *point;
516
517 return status;
518 }
519
520 static cairo_clip_t *
_cairo_clip_reduce_to_boxes(cairo_clip_t * clip)521 _cairo_clip_reduce_to_boxes (cairo_clip_t *clip)
522 {
523 struct reduce r;
524 cairo_clip_path_t *clip_path;
525 cairo_status_t status;
526
527 return clip;
528 if (clip->path == NULL)
529 return clip;
530
531 r.clip = clip;
532 r.extents.p1.x = r.extents.p1.y = INT_MAX;
533 r.extents.p2.x = r.extents.p2.y = INT_MIN;
534 r.inside = FALSE;
535
536 r.limit.p1.x = _cairo_fixed_from_int (clip->extents.x);
537 r.limit.p1.y = _cairo_fixed_from_int (clip->extents.y);
538 r.limit.p2.x = _cairo_fixed_from_int (clip->extents.x + clip->extents.width);
539 r.limit.p2.y = _cairo_fixed_from_int (clip->extents.y + clip->extents.height);
540
541 clip_path = clip->path;
542 do {
543 r.current_point.x = 0;
544 r.current_point.y = 0;
545 r.last_move_to = r.current_point;
546
547 status = _cairo_path_fixed_interpret_flat (&clip_path->path,
548 _reduce_move_to,
549 _reduce_line_to,
550 _reduce_close,
551 &r,
552 clip_path->tolerance);
553 assert (status == CAIRO_STATUS_SUCCESS);
554 _reduce_close (&r);
555 } while ((clip_path = clip_path->prev));
556
557 if (! r.inside) {
558 _cairo_clip_path_destroy (clip->path);
559 clip->path = NULL;
560 }
561
562 return _cairo_clip_intersect_box (clip, &r.extents);
563 }
564
565 cairo_clip_t *
_cairo_clip_reduce_to_rectangle(const cairo_clip_t * clip,const cairo_rectangle_int_t * r)566 _cairo_clip_reduce_to_rectangle (const cairo_clip_t *clip,
567 const cairo_rectangle_int_t *r)
568 {
569 cairo_clip_t *copy;
570
571 if (_cairo_clip_is_all_clipped (clip))
572 return (cairo_clip_t *) clip;
573
574 if (_cairo_clip_contains_rectangle (clip, r))
575 return _cairo_clip_intersect_rectangle (NULL, r);
576
577 copy = _cairo_clip_copy_intersect_rectangle (clip, r);
578 if (_cairo_clip_is_all_clipped (copy))
579 return copy;
580
581 return _cairo_clip_reduce_to_boxes (copy);
582 }
583
584 cairo_clip_t *
_cairo_clip_reduce_for_composite(const cairo_clip_t * clip,cairo_composite_rectangles_t * extents)585 _cairo_clip_reduce_for_composite (const cairo_clip_t *clip,
586 cairo_composite_rectangles_t *extents)
587 {
588 const cairo_rectangle_int_t *r;
589
590 r = extents->is_bounded ? &extents->bounded : &extents->unbounded;
591 return _cairo_clip_reduce_to_rectangle (clip, r);
592 }
593
594 cairo_clip_t *
_cairo_clip_from_boxes(const cairo_boxes_t * boxes)595 _cairo_clip_from_boxes (const cairo_boxes_t *boxes)
596 {
597 cairo_box_t extents;
598 cairo_clip_t *clip = _cairo_clip_create ();
599 if (clip == NULL)
600 return _cairo_clip_set_all_clipped (clip);
601
602 if (unlikely (! _cairo_boxes_copy_to_clip (boxes, clip)))
603 return clip;
604
605 _cairo_boxes_extents (boxes, &extents);
606 _cairo_box_round_to_rectangle (&extents, &clip->extents);
607
608 return clip;
609 }
610