2 * Copyright © 2004 Carl Worth
3 * Copyright © 2006 Red Hat, Inc.
4 * Copyright © 2009 Chris Wilson
6 * This library is free software; you can redistribute it and/or
7 * modify it either under the terms of the GNU Lesser General Public
8 * License version 2.1 as published by the Free Software Foundation
9 * (the "LGPL") or, at your option, under the terms of the Mozilla
10 * Public License Version 1.1 (the "MPL"). If you do not alter this
11 * notice, a recipient may use your version of this file under either
12 * the MPL or the LGPL.
14 * You should have received a copy of the LGPL along with this library
15 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 * You should have received a copy of the MPL along with this library
18 * in the file COPYING-MPL-1.1
20 * The contents of this file are subject to the Mozilla Public License
21 * Version 1.1 (the "License"); you may not use this file except in
22 * compliance with the License. You may obtain a copy of the License at
23 * http://www.mozilla.org/MPL/
25 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 * the specific language governing rights and limitations.
29 * The Original Code is the cairo graphics library.
31 * The Initial Developer of the Original Code is Carl Worth
34 * Carl D. Worth <cworth@cworth.org>
35 * Chris Wilson <chris@chris-wilson.co.uk>
38 /* Provide definitions for standalone compilation */
41 #include "cairo-boxes-private.h"
42 #include "cairo-error-private.h"
43 #include "cairo-combsort-inline.h"
44 #include "cairo-list-private.h"
45 #include "cairo-traps-private.h"
49 typedef struct _rectangle rectangle_t;
50 typedef struct _edge edge_t;
64 #define UNROLL3(x) x x x
66 /* the parent is always given by index/2 */
67 #define PQ_PARENT_INDEX(i) ((i) >> 1)
68 #define PQ_FIRST_ENTRY 1
70 /* left and right children are index * 2 and (index * 2) +1 respectively */
71 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
73 typedef struct _sweep_line {
74 rectangle_t **rectangles;
76 edge_t head, tail, *insert, *cursor;
82 cairo_fill_rule_t fill_rule;
84 cairo_bool_t do_traps;
94 dump_traps (cairo_traps_t *traps, const char *filename)
99 if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
102 file = fopen (filename, "a");
104 for (n = 0; n < traps->num_traps; n++) {
105 fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
107 traps->traps[n].bottom,
108 traps->traps[n].left.p1.x,
109 traps->traps[n].left.p1.y,
110 traps->traps[n].left.p2.x,
111 traps->traps[n].left.p2.y,
112 traps->traps[n].right.p1.x,
113 traps->traps[n].right.p1.y,
114 traps->traps[n].right.p2.x,
115 traps->traps[n].right.p2.y);
117 fprintf (file, "\n");
122 #define dump_traps(traps, filename)
126 rectangle_compare_start (const rectangle_t *a,
127 const rectangle_t *b)
129 return a->top - b->top;
133 rectangle_compare_stop (const rectangle_t *a,
134 const rectangle_t *b)
136 return a->bottom - b->bottom;
140 pqueue_push (sweep_line_t *sweep, rectangle_t *rectangle)
142 rectangle_t **elements;
145 elements = sweep->stop;
146 for (i = ++sweep->stop_size;
147 i != PQ_FIRST_ENTRY &&
148 rectangle_compare_stop (rectangle,
149 elements[parent = PQ_PARENT_INDEX (i)]) < 0;
152 elements[i] = elements[parent];
155 elements[i] = rectangle;
159 rectangle_pop_stop (sweep_line_t *sweep)
161 rectangle_t **elements = sweep->stop;
165 tail = elements[sweep->stop_size--];
166 if (sweep->stop_size == 0) {
167 elements[PQ_FIRST_ENTRY] = NULL;
171 for (i = PQ_FIRST_ENTRY;
172 (child = PQ_LEFT_CHILD_INDEX (i)) <= sweep->stop_size;
175 if (child != sweep->stop_size &&
176 rectangle_compare_stop (elements[child+1],
177 elements[child]) < 0)
182 if (rectangle_compare_stop (elements[child], tail) >= 0)
185 elements[i] = elements[child];
190 static inline rectangle_t *
191 rectangle_pop_start (sweep_line_t *sweep_line)
193 return *sweep_line->rectangles++;
196 static inline rectangle_t *
197 rectangle_peek_stop (sweep_line_t *sweep_line)
199 return sweep_line->stop[PQ_FIRST_ENTRY];
202 CAIRO_COMBSORT_DECLARE (_rectangle_sort,
204 rectangle_compare_start)
207 sweep_line_init (sweep_line_t *sweep_line,
208 rectangle_t **rectangles,
210 cairo_fill_rule_t fill_rule,
211 cairo_bool_t do_traps,
214 rectangles[-2] = NULL;
215 rectangles[-1] = NULL;
216 rectangles[num_rectangles] = NULL;
217 sweep_line->rectangles = rectangles;
218 sweep_line->stop = rectangles - 2;
219 sweep_line->stop_size = 0;
221 sweep_line->insert = NULL;
222 sweep_line->insert_x = INT_MAX;
223 sweep_line->cursor = &sweep_line->tail;
225 sweep_line->head.dir = 0;
226 sweep_line->head.x = INT32_MIN;
227 sweep_line->head.right = NULL;
228 sweep_line->head.prev = NULL;
229 sweep_line->head.next = &sweep_line->tail;
230 sweep_line->tail.prev = &sweep_line->head;
231 sweep_line->tail.next = NULL;
232 sweep_line->tail.right = NULL;
233 sweep_line->tail.x = INT32_MAX;
234 sweep_line->tail.dir = 0;
236 sweep_line->current_y = INT32_MIN;
237 sweep_line->last_y = INT32_MIN;
239 sweep_line->fill_rule = fill_rule;
240 sweep_line->container = container;
241 sweep_line->do_traps = do_traps;
245 edge_end_box (sweep_line_t *sweep_line, edge_t *left, int32_t bot)
247 cairo_status_t status = CAIRO_STATUS_SUCCESS;
249 /* Only emit (trivial) non-degenerate trapezoids with positive height. */
250 if (likely (left->top < bot)) {
251 if (sweep_line->do_traps) {
252 cairo_line_t _left = {
253 { left->x, left->top },
256 { left->right->x, left->top },
257 { left->right->x, bot },
259 _cairo_traps_add_trap (sweep_line->container, left->top, bot, &_left, &_right);
260 status = _cairo_traps_status ((cairo_traps_t *) sweep_line->container);
265 box.p1.y = left->top;
266 box.p2.x = left->right->x;
269 status = _cairo_boxes_add (sweep_line->container,
270 CAIRO_ANTIALIAS_DEFAULT,
274 if (unlikely (status))
275 longjmp (sweep_line->unwind, status);
280 /* Start a new trapezoid at the given top y coordinate, whose edges
281 * are `edge' and `edge->next'. If `edge' already has a trapezoid,
282 * then either add it to the traps in `traps', if the trapezoid's
283 * right edge differs from `edge->next', or do nothing if the new
284 * trapezoid would be a continuation of the existing one. */
286 edge_start_or_continue_box (sweep_line_t *sweep_line,
291 if (left->right == right)
294 if (left->right != NULL) {
295 if (left->right->x == right->x) {
296 /* continuation on right, so just swap edges */
301 edge_end_box (sweep_line, left, top);
304 if (left->x != right->x) {
310 * Merge two sorted edge lists.
312 * - head_a: The head of the first list.
313 * - head_b: The head of the second list; head_b cannot be NULL.
315 * Returns the head of the merged list.
317 * Implementation notes:
318 * To make it fast (in particular, to reduce to an insertion sort whenever
319 * one of the two input lists only has a single element) we iterate through
320 * a list until its head becomes greater than the head of the other list,
321 * then we switch their roles. As soon as one of the two lists is empty, we
322 * just attach the other one to the current list and exit.
323 * Writes to memory are only needed to "switch" lists (as it also requires
324 * attaching to the output list the list which we will be iterating next) and
325 * to attach the last non-empty list.
328 merge_sorted_edges (edge_t *head_a, edge_t *head_b)
334 if (head_a->x <= head_b->x) {
344 while (head_a != NULL && head_a->x <= x) {
346 head_a = head_a->next;
356 while (head_b != NULL && head_b->x <= x) {
358 head_b = head_b->next;
369 * Sort (part of) a list.
371 * - list: The list to be sorted; list cannot be NULL.
372 * - limit: Recursion limit.
374 * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
375 * input list; if the input list has fewer elements, head_out be a sorted list
376 * containing all the elements of the input list.
377 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
378 * all the elements of the input list).
380 * Implementation notes:
381 * Special case single element list, unroll/inline the sorting of the first two elements.
382 * Some tail recursion is used since we iterate on the bottom-up solution of the problem
383 * (we start with a small sorted list and keep merging other lists of the same size to it).
386 sort_edges (edge_t *list,
390 edge_t *head_other, *remaining;
393 head_other = list->next;
395 if (head_other == NULL) {
400 remaining = head_other->next;
401 if (list->x <= head_other->x) {
403 head_other->next = NULL;
405 *head_out = head_other;
406 head_other->prev = list->prev;
407 head_other->next = list;
408 list->prev = head_other;
412 for (i = 0; i < level && remaining; i++) {
413 remaining = sort_edges (remaining, i, &head_other);
414 *head_out = merge_sorted_edges (*head_out, head_other);
421 merge_unsorted_edges (edge_t *head, edge_t *unsorted)
423 sort_edges (unsorted, UINT_MAX, &unsorted);
424 return merge_sorted_edges (head, unsorted);
428 active_edges_insert (sweep_line_t *sweep)
434 prev = sweep->cursor;
438 } while (prev->x > x);
440 while (prev->next->x < x)
444 prev->next = merge_unsorted_edges (prev->next, sweep->insert);
445 sweep->cursor = sweep->insert;
446 sweep->insert = NULL;
447 sweep->insert_x = INT_MAX;
451 active_edges_to_traps (sweep_line_t *sweep)
453 int top = sweep->current_y;
456 if (sweep->last_y == sweep->current_y)
460 active_edges_insert (sweep);
462 pos = sweep->head.next;
463 if (pos == &sweep->tail)
466 if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING) {
468 edge_t *left, *right;
476 /* Check if there is a co-linear edge with an existing trap */
477 while (right->x == left->x) {
478 if (right->right != NULL) {
479 assert (left->right == NULL);
480 /* continuation on left */
481 left->top = right->top;
482 left->right = right->right;
485 winding += right->dir;
490 if (left->right != NULL)
491 edge_end_box (sweep, left, top);
497 /* End all subsumed traps */
498 if (unlikely (right->right != NULL))
499 edge_end_box (sweep, right, top);
501 /* Greedily search for the closing edge, so that we generate
502 * the * maximal span width with the minimal number of
505 winding += right->dir;
506 if (winding == 0 && right->x != right->next->x)
512 edge_start_or_continue_box (sweep, left, right, top);
515 } while (pos != &sweep->tail);
518 edge_t *right = pos->next;
522 /* End all subsumed traps */
523 if (unlikely (right->right != NULL))
524 edge_end_box (sweep, right, top);
526 /* skip co-linear edges */
527 if (++count & 1 && right->x != right->next->x)
533 edge_start_or_continue_box (sweep, pos, right, top);
536 } while (pos != &sweep->tail);
539 sweep->last_y = sweep->current_y;
543 sweep_line_delete_edge (sweep_line_t *sweep, edge_t *edge)
545 if (edge->right != NULL) {
546 edge_t *next = edge->next;
547 if (next->x == edge->x) {
548 next->top = edge->top;
549 next->right = edge->right;
551 edge_end_box (sweep, edge, sweep->current_y);
554 if (sweep->cursor == edge)
555 sweep->cursor = edge->prev;
557 edge->prev->next = edge->next;
558 edge->next->prev = edge->prev;
561 static inline cairo_bool_t
562 sweep_line_delete (sweep_line_t *sweep, rectangle_t *rectangle)
567 if (sweep->fill_rule == CAIRO_FILL_RULE_WINDING &&
568 rectangle->left.prev->dir == rectangle->left.dir)
570 update = rectangle->left.next != &rectangle->right;
573 sweep_line_delete_edge (sweep, &rectangle->left);
574 sweep_line_delete_edge (sweep, &rectangle->right);
576 rectangle_pop_stop (sweep);
581 sweep_line_insert (sweep_line_t *sweep, rectangle_t *rectangle)
584 sweep->insert->prev = &rectangle->right;
585 rectangle->right.next = sweep->insert;
586 rectangle->right.prev = &rectangle->left;
587 rectangle->left.next = &rectangle->right;
588 rectangle->left.prev = NULL;
589 sweep->insert = &rectangle->left;
590 if (rectangle->left.x < sweep->insert_x)
591 sweep->insert_x = rectangle->left.x;
593 pqueue_push (sweep, rectangle);
596 static cairo_status_t
597 _cairo_bentley_ottmann_tessellate_rectangular (rectangle_t **rectangles,
599 cairo_fill_rule_t fill_rule,
600 cairo_bool_t do_traps,
603 sweep_line_t sweep_line;
604 rectangle_t *rectangle;
605 cairo_status_t status;
606 cairo_bool_t update = FALSE;
608 sweep_line_init (&sweep_line,
609 rectangles, num_rectangles,
611 do_traps, container);
612 if ((status = setjmp (sweep_line.unwind)))
615 rectangle = rectangle_pop_start (&sweep_line);
617 if (rectangle->top != sweep_line.current_y) {
620 stop = rectangle_peek_stop (&sweep_line);
621 while (stop != NULL && stop->bottom < rectangle->top) {
622 if (stop->bottom != sweep_line.current_y) {
624 active_edges_to_traps (&sweep_line);
628 sweep_line.current_y = stop->bottom;
631 update |= sweep_line_delete (&sweep_line, stop);
632 stop = rectangle_peek_stop (&sweep_line);
636 active_edges_to_traps (&sweep_line);
640 sweep_line.current_y = rectangle->top;
644 sweep_line_insert (&sweep_line, rectangle);
645 } while ((rectangle = rectangle_pop_start (&sweep_line)) != NULL &&
646 sweep_line.current_y == rectangle->top);
650 while ((rectangle = rectangle_peek_stop (&sweep_line)) != NULL) {
651 if (rectangle->bottom != sweep_line.current_y) {
653 active_edges_to_traps (&sweep_line);
656 sweep_line.current_y = rectangle->bottom;
659 update |= sweep_line_delete (&sweep_line, rectangle);
662 return CAIRO_STATUS_SUCCESS;
666 _cairo_bentley_ottmann_tessellate_rectangular_traps (cairo_traps_t *traps,
667 cairo_fill_rule_t fill_rule)
669 rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
670 rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
671 rectangle_t *rectangles, **rectangles_ptrs;
672 cairo_status_t status;
675 if (unlikely (traps->num_traps <= 1))
676 return CAIRO_STATUS_SUCCESS;
678 assert (traps->is_rectangular);
680 dump_traps (traps, "bo-rects-traps-in.txt");
682 rectangles = stack_rectangles;
683 rectangles_ptrs = stack_rectangles_ptrs;
684 if (traps->num_traps > ARRAY_LENGTH (stack_rectangles)) {
685 rectangles = _cairo_malloc_ab_plus_c (traps->num_traps,
686 sizeof (rectangle_t) +
687 sizeof (rectangle_t *),
688 3*sizeof (rectangle_t *));
689 if (unlikely (rectangles == NULL))
690 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
692 rectangles_ptrs = (rectangle_t **) (rectangles + traps->num_traps);
695 for (i = 0; i < traps->num_traps; i++) {
696 if (traps->traps[i].left.p1.x < traps->traps[i].right.p1.x) {
697 rectangles[i].left.x = traps->traps[i].left.p1.x;
698 rectangles[i].left.dir = 1;
700 rectangles[i].right.x = traps->traps[i].right.p1.x;
701 rectangles[i].right.dir = -1;
703 rectangles[i].right.x = traps->traps[i].left.p1.x;
704 rectangles[i].right.dir = 1;
706 rectangles[i].left.x = traps->traps[i].right.p1.x;
707 rectangles[i].left.dir = -1;
710 rectangles[i].left.right = NULL;
711 rectangles[i].right.right = NULL;
713 rectangles[i].top = traps->traps[i].top;
714 rectangles[i].bottom = traps->traps[i].bottom;
716 rectangles_ptrs[i+2] = &rectangles[i];
718 /* XXX incremental sort */
719 _rectangle_sort (rectangles_ptrs+2, i);
721 _cairo_traps_clear (traps);
722 status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, i,
725 traps->is_rectilinear = TRUE;
726 traps->is_rectangular = TRUE;
728 if (rectangles != stack_rectangles)
731 dump_traps (traps, "bo-rects-traps-out.txt");
737 _cairo_bentley_ottmann_tessellate_boxes (const cairo_boxes_t *in,
738 cairo_fill_rule_t fill_rule,
741 rectangle_t stack_rectangles[CAIRO_STACK_ARRAY_LENGTH (rectangle_t)];
742 rectangle_t *stack_rectangles_ptrs[ARRAY_LENGTH (stack_rectangles) + 3];
743 rectangle_t *rectangles, **rectangles_ptrs;
744 rectangle_t *stack_rectangles_chain[CAIRO_STACK_ARRAY_LENGTH (rectangle_t *) ];
745 rectangle_t **rectangles_chain = NULL;
746 const struct _cairo_boxes_chunk *chunk;
747 cairo_status_t status;
748 int i, j, y_min, y_max;
750 if (unlikely (in->num_boxes == 0)) {
751 _cairo_boxes_clear (out);
752 return CAIRO_STATUS_SUCCESS;
755 if (in->num_boxes == 1) {
757 cairo_box_t *box = &in->chunks.base[0];
759 if (box->p1.x > box->p2.x) {
760 cairo_fixed_t tmp = box->p1.x;
761 box->p1.x = box->p2.x;
765 cairo_box_t box = in->chunks.base[0];
767 if (box.p1.x > box.p2.x) {
768 cairo_fixed_t tmp = box.p1.x;
773 _cairo_boxes_clear (out);
774 status = _cairo_boxes_add (out, CAIRO_ANTIALIAS_DEFAULT, &box);
775 assert (status == CAIRO_STATUS_SUCCESS);
777 return CAIRO_STATUS_SUCCESS;
780 y_min = INT_MAX; y_max = INT_MIN;
781 for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
782 const cairo_box_t *box = chunk->base;
783 for (i = 0; i < chunk->count; i++) {
784 if (box[i].p1.y < y_min)
786 if (box[i].p1.y > y_max)
790 y_min = _cairo_fixed_integer_floor (y_min);
791 y_max = _cairo_fixed_integer_floor (y_max) + 1;
794 if (y_max < in->num_boxes) {
795 rectangles_chain = stack_rectangles_chain;
796 if (y_max > ARRAY_LENGTH (stack_rectangles_chain)) {
797 rectangles_chain = _cairo_malloc_ab (y_max, sizeof (rectangle_t *));
798 if (unlikely (rectangles_chain == NULL))
799 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
801 memset (rectangles_chain, 0, y_max * sizeof (rectangle_t*));
804 rectangles = stack_rectangles;
805 rectangles_ptrs = stack_rectangles_ptrs;
806 if (in->num_boxes > ARRAY_LENGTH (stack_rectangles)) {
807 rectangles = _cairo_malloc_ab_plus_c (in->num_boxes,
808 sizeof (rectangle_t) +
809 sizeof (rectangle_t *),
810 3*sizeof (rectangle_t *));
811 if (unlikely (rectangles == NULL)) {
812 if (rectangles_chain != stack_rectangles_chain)
813 free (rectangles_chain);
814 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
817 rectangles_ptrs = (rectangle_t **) (rectangles + in->num_boxes);
821 for (chunk = &in->chunks; chunk != NULL; chunk = chunk->next) {
822 const cairo_box_t *box = chunk->base;
823 for (i = 0; i < chunk->count; i++) {
826 if (box[i].p1.x < box[i].p2.x) {
827 rectangles[j].left.x = box[i].p1.x;
828 rectangles[j].left.dir = 1;
830 rectangles[j].right.x = box[i].p2.x;
831 rectangles[j].right.dir = -1;
833 rectangles[j].right.x = box[i].p1.x;
834 rectangles[j].right.dir = 1;
836 rectangles[j].left.x = box[i].p2.x;
837 rectangles[j].left.dir = -1;
840 rectangles[j].left.right = NULL;
841 rectangles[j].right.right = NULL;
843 rectangles[j].top = box[i].p1.y;
844 rectangles[j].bottom = box[i].p2.y;
846 if (rectangles_chain) {
847 h = _cairo_fixed_integer_floor (box[i].p1.y) - y_min;
848 rectangles[j].left.next = (edge_t *)rectangles_chain[h];
849 rectangles_chain[h] = &rectangles[j];
851 rectangles_ptrs[j+2] = &rectangles[j];
857 if (rectangles_chain) {
859 for (y_min = 0; y_min < y_max; y_min++) {
862 for (r = rectangles_chain[y_min]; r; r = (rectangle_t *)r->left.next)
863 rectangles_ptrs[j++] = r;
865 _rectangle_sort (rectangles_ptrs + start, j - start);
868 if (rectangles_chain != stack_rectangles_chain)
869 free (rectangles_chain);
873 _rectangle_sort (rectangles_ptrs + 2, j);
876 _cairo_boxes_clear (out);
877 status = _cairo_bentley_ottmann_tessellate_rectangular (rectangles_ptrs+2, j,
880 if (rectangles != stack_rectangles)