2 * Copyright © 2004 Carl Worth
3 * Copyright © 2006 Red Hat, Inc.
4 * Copyright © 2009 Chris Wilson
5 * Copyright © 2011 Intel Corporation
7 * This library is free software; you can redistribute it and/or
8 * modify it either under the terms of the GNU Lesser General Public
9 * License version 2.1 as published by the Free Software Foundation
10 * (the "LGPL") or, at your option, under the terms of the Mozilla
11 * Public License Version 1.1 (the "MPL"). If you do not alter this
12 * notice, a recipient may use your version of this file under either
13 * the MPL or the LGPL.
15 * You should have received a copy of the LGPL along with this library
16 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
18 * You should have received a copy of the MPL along with this library
19 * in the file COPYING-MPL-1.1
21 * The contents of this file are subject to the Mozilla Public License
22 * Version 1.1 (the "License"); you may not use this file except in
23 * compliance with the License. You may obtain a copy of the License at
24 * http://www.mozilla.org/MPL/
26 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
27 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
28 * the specific language governing rights and limitations.
30 * The Original Code is the cairo graphics library.
32 * The Initial Developer of the Original Code is Carl Worth
35 * Carl D. Worth <cworth@cworth.org>
36 * Chris Wilson <chris@chris-wilson.co.uk>
39 /* Provide definitions for standalone compilation */
42 #include "cairo-boxes-private.h"
43 #include "cairo-error-private.h"
44 #include "cairo-combsort-inline.h"
45 #include "cairo-list-private.h"
49 typedef struct _rectangle rectangle_t
;
50 typedef struct _edge edge_t
;
65 #define UNROLL3(x) x x x
67 /* the parent is always given by index/2 */
68 #define PQ_PARENT_INDEX(i) ((i) >> 1)
69 #define PQ_FIRST_ENTRY 1
71 /* left and right children are index * 2 and (index * 2) +1 respectively */
72 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
74 typedef struct _pqueue
{
77 rectangle_t
**elements
;
78 rectangle_t
*elements_embedded
[1024];
81 typedef struct _sweep_line
{
82 rectangle_t
**rectangles
;
85 edge_t
*insert_left
, *insert_right
;
96 dump_traps (cairo_traps_t
*traps
, const char *filename
)
101 if (getenv ("CAIRO_DEBUG_TRAPS") == NULL
)
104 file
= fopen (filename
, "a");
106 for (n
= 0; n
< traps
->num_traps
; n
++) {
107 fprintf (file
, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
109 traps
->traps
[n
].bottom
,
110 traps
->traps
[n
].left
.p1
.x
,
111 traps
->traps
[n
].left
.p1
.y
,
112 traps
->traps
[n
].left
.p2
.x
,
113 traps
->traps
[n
].left
.p2
.y
,
114 traps
->traps
[n
].right
.p1
.x
,
115 traps
->traps
[n
].right
.p1
.y
,
116 traps
->traps
[n
].right
.p2
.x
,
117 traps
->traps
[n
].right
.p2
.y
);
119 fprintf (file
, "\n");
124 #define dump_traps(traps, filename)
128 rectangle_compare_start (const rectangle_t
*a
,
129 const rectangle_t
*b
)
131 return a
->top
- b
->top
;
135 rectangle_compare_stop (const rectangle_t
*a
,
136 const rectangle_t
*b
)
138 return a
->bottom
- b
->bottom
;
142 pqueue_init (pqueue_t
*pq
)
144 pq
->max_size
= ARRAY_LENGTH (pq
->elements_embedded
);
147 pq
->elements
= pq
->elements_embedded
;
148 pq
->elements
[PQ_FIRST_ENTRY
] = NULL
;
152 pqueue_fini (pqueue_t
*pq
)
154 if (pq
->elements
!= pq
->elements_embedded
)
159 pqueue_grow (pqueue_t
*pq
)
161 rectangle_t
**new_elements
;
164 if (pq
->elements
== pq
->elements_embedded
) {
165 new_elements
= _cairo_malloc_ab (pq
->max_size
,
166 sizeof (rectangle_t
*));
167 if (unlikely (new_elements
== NULL
))
170 memcpy (new_elements
, pq
->elements_embedded
,
171 sizeof (pq
->elements_embedded
));
173 new_elements
= _cairo_realloc_ab (pq
->elements
,
175 sizeof (rectangle_t
*));
176 if (unlikely (new_elements
== NULL
))
180 pq
->elements
= new_elements
;
185 pqueue_push (sweep_line_t
*sweep
, rectangle_t
*rectangle
)
187 rectangle_t
**elements
;
190 if (unlikely (sweep
->pq
.size
+ 1 == sweep
->pq
.max_size
)) {
191 if (unlikely (! pqueue_grow (&sweep
->pq
))) {
192 longjmp (sweep
->unwind
,
193 _cairo_error (CAIRO_STATUS_NO_MEMORY
));
197 elements
= sweep
->pq
.elements
;
198 for (i
= ++sweep
->pq
.size
;
199 i
!= PQ_FIRST_ENTRY
&&
200 rectangle_compare_stop (rectangle
,
201 elements
[parent
= PQ_PARENT_INDEX (i
)]) < 0;
204 elements
[i
] = elements
[parent
];
207 elements
[i
] = rectangle
;
211 pqueue_pop (pqueue_t
*pq
)
213 rectangle_t
**elements
= pq
->elements
;
217 tail
= elements
[pq
->size
--];
219 elements
[PQ_FIRST_ENTRY
] = NULL
;
223 for (i
= PQ_FIRST_ENTRY
;
224 (child
= PQ_LEFT_CHILD_INDEX (i
)) <= pq
->size
;
227 if (child
!= pq
->size
&&
228 rectangle_compare_stop (elements
[child
+1],
229 elements
[child
]) < 0)
234 if (rectangle_compare_stop (elements
[child
], tail
) >= 0)
237 elements
[i
] = elements
[child
];
242 static inline rectangle_t
*
243 rectangle_pop_start (sweep_line_t
*sweep_line
)
245 return *sweep_line
->rectangles
++;
248 static inline rectangle_t
*
249 rectangle_peek_stop (sweep_line_t
*sweep_line
)
251 return sweep_line
->pq
.elements
[PQ_FIRST_ENTRY
];
254 CAIRO_COMBSORT_DECLARE (_rectangle_sort
,
256 rectangle_compare_start
)
259 sweep_line_init (sweep_line_t
*sweep_line
,
260 rectangle_t
**rectangles
,
263 _rectangle_sort (rectangles
, num_rectangles
);
264 rectangles
[num_rectangles
] = NULL
;
265 sweep_line
->rectangles
= rectangles
;
267 sweep_line
->head
.x
= INT32_MIN
;
268 sweep_line
->head
.right
= NULL
;
269 sweep_line
->head
.dir
= 0;
270 sweep_line
->head
.next
= &sweep_line
->tail
;
271 sweep_line
->tail
.x
= INT32_MAX
;
272 sweep_line
->tail
.right
= NULL
;
273 sweep_line
->tail
.dir
= 0;
274 sweep_line
->tail
.prev
= &sweep_line
->head
;
276 sweep_line
->insert_left
= &sweep_line
->tail
;
277 sweep_line
->insert_right
= &sweep_line
->tail
;
279 sweep_line
->current_y
= INT32_MIN
;
280 sweep_line
->last_y
= INT32_MIN
;
282 pqueue_init (&sweep_line
->pq
);
286 sweep_line_fini (sweep_line_t
*sweep_line
)
288 pqueue_fini (&sweep_line
->pq
);
292 end_box (sweep_line_t
*sweep_line
, edge_t
*left
, int32_t bot
, cairo_boxes_t
*out
)
294 if (likely (left
->top
< bot
)) {
295 cairo_status_t status
;
299 box
.p1
.y
= left
->top
;
300 box
.p2
.x
= left
->right
->x
;
303 status
= _cairo_boxes_add (out
, CAIRO_ANTIALIAS_DEFAULT
, &box
);
304 if (unlikely (status
))
305 longjmp (sweep_line
->unwind
, status
);
311 /* Start a new trapezoid at the given top y coordinate, whose edges
312 * are `edge' and `edge->next'. If `edge' already has a trapezoid,
313 * then either add it to the traps in `traps', if the trapezoid's
314 * right edge differs from `edge->next', or do nothing if the new
315 * trapezoid would be a continuation of the existing one. */
317 start_or_continue_box (sweep_line_t
*sweep_line
,
323 if (left
->right
== right
)
326 if (left
->right
!= NULL
) {
327 if (right
!= NULL
&& left
->right
->x
== right
->x
) {
328 /* continuation on right, so just swap edges */
333 end_box (sweep_line
, left
, top
, out
);
336 if (right
!= NULL
&& left
->x
!= right
->x
) {
342 static inline int is_zero(const int *winding
)
344 return winding
[0] == 0 || winding
[1] == 0;
348 active_edges (sweep_line_t
*sweep
, cairo_boxes_t
*out
)
350 int top
= sweep
->current_y
;
351 int winding
[2] = { 0 };
354 if (sweep
->last_y
== sweep
->current_y
)
357 pos
= sweep
->head
.next
;
358 if (pos
== &sweep
->tail
)
362 edge_t
*left
, *right
;
366 winding
[left
->a_or_b
] += left
->dir
;
367 if (!is_zero (winding
))
369 if (left
->next
== &sweep
->tail
)
372 if (unlikely (left
->right
!= NULL
))
373 end_box (sweep
, left
, top
, out
);
380 if (unlikely (right
->right
!= NULL
))
381 end_box (sweep
, right
, top
, out
);
383 winding
[right
->a_or_b
] += right
->dir
;
384 if (is_zero (winding
)) {
385 /* skip co-linear edges */
386 if (likely (right
->x
!= right
->next
->x
))
393 start_or_continue_box (sweep
, left
, right
, top
, out
);
396 } while (pos
!= &sweep
->tail
);
399 sweep
->last_y
= sweep
->current_y
;
403 sweep_line_delete_edge (sweep_line_t
*sweep_line
, edge_t
*edge
, cairo_boxes_t
*out
)
405 if (edge
->right
!= NULL
) {
406 edge_t
*next
= edge
->next
;
407 if (next
->x
== edge
->x
) {
408 next
->top
= edge
->top
;
409 next
->right
= edge
->right
;
411 end_box (sweep_line
, edge
, sweep_line
->current_y
, out
);
415 if (sweep_line
->insert_left
== edge
)
416 sweep_line
->insert_left
= edge
->next
;
417 if (sweep_line
->insert_right
== edge
)
418 sweep_line
->insert_right
= edge
->next
;
420 edge
->prev
->next
= edge
->next
;
421 edge
->next
->prev
= edge
->prev
;
425 sweep_line_delete (sweep_line_t
*sweep
,
426 rectangle_t
*rectangle
,
429 sweep_line_delete_edge (sweep
, &rectangle
->left
, out
);
430 sweep_line_delete_edge (sweep
, &rectangle
->right
, out
);
432 pqueue_pop (&sweep
->pq
);
436 insert_edge (edge_t
*edge
, edge_t
*pos
)
438 if (pos
->x
!= edge
->x
) {
439 if (pos
->x
> edge
->x
) {
442 if (pos
->prev
->x
<= edge
->x
)
451 if (pos
->x
>= edge
->x
)
458 pos
->prev
->next
= edge
;
459 edge
->prev
= pos
->prev
;
465 sweep_line_insert (sweep_line_t
*sweep
, rectangle_t
*rectangle
)
470 pos
= sweep
->insert_right
;
471 insert_edge (&rectangle
->right
, pos
);
472 sweep
->insert_right
= &rectangle
->right
;
475 pos
= sweep
->insert_left
;
476 if (pos
->x
> sweep
->insert_right
->x
)
477 pos
= sweep
->insert_right
->prev
;
478 insert_edge (&rectangle
->left
, pos
);
479 sweep
->insert_left
= &rectangle
->left
;
481 pqueue_push (sweep
, rectangle
);
484 static cairo_status_t
485 intersect (rectangle_t
**rectangles
, int num_rectangles
, cairo_boxes_t
*out
)
487 sweep_line_t sweep_line
;
488 rectangle_t
*rectangle
;
489 cairo_status_t status
;
491 sweep_line_init (&sweep_line
, rectangles
, num_rectangles
);
492 if ((status
= setjmp (sweep_line
.unwind
)))
495 rectangle
= rectangle_pop_start (&sweep_line
);
497 if (rectangle
->top
!= sweep_line
.current_y
) {
500 stop
= rectangle_peek_stop (&sweep_line
);
501 while (stop
!= NULL
&& stop
->bottom
< rectangle
->top
) {
502 if (stop
->bottom
!= sweep_line
.current_y
) {
503 active_edges (&sweep_line
, out
);
504 sweep_line
.current_y
= stop
->bottom
;
507 sweep_line_delete (&sweep_line
, stop
, out
);
509 stop
= rectangle_peek_stop (&sweep_line
);
512 active_edges (&sweep_line
, out
);
513 sweep_line
.current_y
= rectangle
->top
;
516 sweep_line_insert (&sweep_line
, rectangle
);
517 } while ((rectangle
= rectangle_pop_start (&sweep_line
)) != NULL
);
519 while ((rectangle
= rectangle_peek_stop (&sweep_line
)) != NULL
) {
520 if (rectangle
->bottom
!= sweep_line
.current_y
) {
521 active_edges (&sweep_line
, out
);
522 sweep_line
.current_y
= rectangle
->bottom
;
525 sweep_line_delete (&sweep_line
, rectangle
, out
);
529 sweep_line_fini (&sweep_line
);
533 static cairo_status_t
534 _cairo_boxes_intersect_with_box (const cairo_boxes_t
*boxes
,
535 const cairo_box_t
*box
,
538 cairo_status_t status
;
541 if (out
== boxes
) { /* inplace update */
542 struct _cairo_boxes_chunk
*chunk
;
545 for (chunk
= &out
->chunks
; chunk
!= NULL
; chunk
= chunk
->next
) {
546 for (i
= j
= 0; i
< chunk
->count
; i
++) {
547 cairo_box_t
*b
= &chunk
->base
[i
];
549 b
->p1
.x
= MAX (b
->p1
.x
, box
->p1
.x
);
550 b
->p1
.y
= MAX (b
->p1
.y
, box
->p1
.y
);
551 b
->p2
.x
= MIN (b
->p2
.x
, box
->p2
.x
);
552 b
->p2
.y
= MIN (b
->p2
.y
, box
->p2
.y
);
553 if (b
->p1
.x
< b
->p2
.x
&& b
->p1
.y
< b
->p2
.y
) {
559 /* XXX unlink empty chains? */
564 const struct _cairo_boxes_chunk
*chunk
;
566 _cairo_boxes_clear (out
);
567 _cairo_boxes_limit (out
, box
, 1);
568 for (chunk
= &boxes
->chunks
; chunk
!= NULL
; chunk
= chunk
->next
) {
569 for (i
= 0; i
< chunk
->count
; i
++) {
570 status
= _cairo_boxes_add (out
,
571 CAIRO_ANTIALIAS_DEFAULT
,
573 if (unlikely (status
))
579 return CAIRO_STATUS_SUCCESS
;
583 _cairo_boxes_intersect (const cairo_boxes_t
*a
,
584 const cairo_boxes_t
*b
,
587 rectangle_t stack_rectangles
[CAIRO_STACK_ARRAY_LENGTH (rectangle_t
)];
588 rectangle_t
*rectangles
;
589 rectangle_t
*stack_rectangles_ptrs
[ARRAY_LENGTH (stack_rectangles
) + 1];
590 rectangle_t
**rectangles_ptrs
;
591 const struct _cairo_boxes_chunk
*chunk
;
592 cairo_status_t status
;
595 if (unlikely (a
->num_boxes
== 0 || b
->num_boxes
== 0)) {
596 _cairo_boxes_clear (out
);
597 return CAIRO_STATUS_SUCCESS
;
600 if (a
->num_boxes
== 1) {
601 cairo_box_t box
= a
->chunks
.base
[0];
602 return _cairo_boxes_intersect_with_box (b
, &box
, out
);
604 if (b
->num_boxes
== 1) {
605 cairo_box_t box
= b
->chunks
.base
[0];
606 return _cairo_boxes_intersect_with_box (a
, &box
, out
);
609 rectangles
= stack_rectangles
;
610 rectangles_ptrs
= stack_rectangles_ptrs
;
611 count
= a
->num_boxes
+ b
->num_boxes
;
612 if (count
> ARRAY_LENGTH (stack_rectangles
)) {
613 rectangles
= _cairo_malloc_ab_plus_c (count
,
614 sizeof (rectangle_t
) +
615 sizeof (rectangle_t
*),
616 sizeof (rectangle_t
*));
617 if (unlikely (rectangles
== NULL
))
618 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
620 rectangles_ptrs
= (rectangle_t
**) (rectangles
+ count
);
624 for (chunk
= &a
->chunks
; chunk
!= NULL
; chunk
= chunk
->next
) {
625 const cairo_box_t
*box
= chunk
->base
;
626 for (i
= 0; i
< chunk
->count
; i
++) {
627 if (box
[i
].p1
.x
< box
[i
].p2
.x
) {
628 rectangles
[j
].left
.x
= box
[i
].p1
.x
;
629 rectangles
[j
].left
.dir
= 1;
631 rectangles
[j
].right
.x
= box
[i
].p2
.x
;
632 rectangles
[j
].right
.dir
= -1;
634 rectangles
[j
].right
.x
= box
[i
].p1
.x
;
635 rectangles
[j
].right
.dir
= 1;
637 rectangles
[j
].left
.x
= box
[i
].p2
.x
;
638 rectangles
[j
].left
.dir
= -1;
641 rectangles
[j
].left
.a_or_b
= 0;
642 rectangles
[j
].left
.right
= NULL
;
643 rectangles
[j
].right
.a_or_b
= 0;
644 rectangles
[j
].right
.right
= NULL
;
646 rectangles
[j
].top
= box
[i
].p1
.y
;
647 rectangles
[j
].bottom
= box
[i
].p2
.y
;
649 rectangles_ptrs
[j
] = &rectangles
[j
];
653 for (chunk
= &b
->chunks
; chunk
!= NULL
; chunk
= chunk
->next
) {
654 const cairo_box_t
*box
= chunk
->base
;
655 for (i
= 0; i
< chunk
->count
; i
++) {
656 if (box
[i
].p1
.x
< box
[i
].p2
.x
) {
657 rectangles
[j
].left
.x
= box
[i
].p1
.x
;
658 rectangles
[j
].left
.dir
= 1;
660 rectangles
[j
].right
.x
= box
[i
].p2
.x
;
661 rectangles
[j
].right
.dir
= -1;
663 rectangles
[j
].right
.x
= box
[i
].p1
.x
;
664 rectangles
[j
].right
.dir
= 1;
666 rectangles
[j
].left
.x
= box
[i
].p2
.x
;
667 rectangles
[j
].left
.dir
= -1;
670 rectangles
[j
].left
.a_or_b
= 1;
671 rectangles
[j
].left
.right
= NULL
;
672 rectangles
[j
].right
.a_or_b
= 1;
673 rectangles
[j
].right
.right
= NULL
;
675 rectangles
[j
].top
= box
[i
].p1
.y
;
676 rectangles
[j
].bottom
= box
[i
].p2
.y
;
678 rectangles_ptrs
[j
] = &rectangles
[j
];
684 _cairo_boxes_clear (out
);
685 status
= intersect (rectangles_ptrs
, j
, out
);
686 if (rectangles
!= stack_rectangles
)