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
)