2 * Copyright © 2004 Carl Worth
3 * Copyright © 2006 Red Hat, Inc.
4 * Copyright © 2008 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-combsort-inline.h"
43 #include "cairo-error-private.h"
44 #include "cairo-traps-private.h"
46 typedef struct _cairo_bo_edge cairo_bo_edge_t
;
47 typedef struct _cairo_bo_trap cairo_bo_trap_t
;
49 /* A deferred trapezoid of an edge */
50 struct _cairo_bo_trap
{
51 cairo_bo_edge_t
*right
;
55 struct _cairo_bo_edge
{
57 cairo_bo_edge_t
*prev
;
58 cairo_bo_edge_t
*next
;
59 cairo_bo_trap_t deferred_trap
;
63 CAIRO_BO_EVENT_TYPE_START
,
64 CAIRO_BO_EVENT_TYPE_STOP
65 } cairo_bo_event_type_t
;
67 typedef struct _cairo_bo_event
{
68 cairo_bo_event_type_t type
;
70 cairo_bo_edge_t
*edge
;
73 typedef struct _cairo_bo_sweep_line
{
74 cairo_bo_event_t
**events
;
75 cairo_bo_edge_t
*head
;
76 cairo_bo_edge_t
*stopped
;
78 cairo_bo_edge_t
*current_edge
;
79 } cairo_bo_sweep_line_t
;
82 _cairo_point_compare (const cairo_point_t
*a
,
83 const cairo_point_t
*b
)
95 _cairo_bo_edge_compare (const cairo_bo_edge_t
*a
,
96 const cairo_bo_edge_t
*b
)
100 cmp
= a
->edge
.line
.p1
.x
- b
->edge
.line
.p1
.x
;
104 return b
->edge
.bottom
- a
->edge
.bottom
;
108 cairo_bo_event_compare (const cairo_bo_event_t
*a
,
109 const cairo_bo_event_t
*b
)
113 cmp
= _cairo_point_compare (&a
->point
, &b
->point
);
117 cmp
= a
->type
- b
->type
;
124 static inline cairo_bo_event_t
*
125 _cairo_bo_event_dequeue (cairo_bo_sweep_line_t
*sweep_line
)
127 return *sweep_line
->events
++;
130 CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort
,
132 cairo_bo_event_compare
)
135 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t
*sweep_line
,
136 cairo_bo_event_t
**events
,
139 _cairo_bo_event_queue_sort (events
, num_events
);
140 events
[num_events
] = NULL
;
141 sweep_line
->events
= events
;
143 sweep_line
->head
= NULL
;
144 sweep_line
->current_y
= INT32_MIN
;
145 sweep_line
->current_edge
= NULL
;
149 _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t
*sweep_line
,
150 cairo_bo_edge_t
*edge
)
152 if (sweep_line
->current_edge
!= NULL
) {
153 cairo_bo_edge_t
*prev
, *next
;
156 cmp
= _cairo_bo_edge_compare (sweep_line
->current_edge
, edge
);
158 prev
= sweep_line
->current_edge
;
160 while (next
!= NULL
&& _cairo_bo_edge_compare (next
, edge
) < 0)
161 prev
= next
, next
= prev
->next
;
168 } else if (cmp
> 0) {
169 next
= sweep_line
->current_edge
;
171 while (prev
!= NULL
&& _cairo_bo_edge_compare (prev
, edge
) > 0)
172 next
= prev
, prev
= next
->prev
;
180 sweep_line
->head
= edge
;
182 prev
= sweep_line
->current_edge
;
184 edge
->next
= prev
->next
;
185 if (prev
->next
!= NULL
)
186 prev
->next
->prev
= edge
;
190 sweep_line
->head
= edge
;
193 sweep_line
->current_edge
= edge
;
197 _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t
*sweep_line
,
198 cairo_bo_edge_t
*edge
)
200 if (edge
->prev
!= NULL
)
201 edge
->prev
->next
= edge
->next
;
203 sweep_line
->head
= edge
->next
;
205 if (edge
->next
!= NULL
)
206 edge
->next
->prev
= edge
->prev
;
208 if (sweep_line
->current_edge
== edge
)
209 sweep_line
->current_edge
= edge
->prev
? edge
->prev
: edge
->next
;
212 static inline cairo_bool_t
213 edges_collinear (const cairo_bo_edge_t
*a
, const cairo_bo_edge_t
*b
)
215 return a
->edge
.line
.p1
.x
== b
->edge
.line
.p1
.x
;
218 static cairo_status_t
219 _cairo_bo_edge_end_trap (cairo_bo_edge_t
*left
,
221 cairo_bool_t do_traps
,
224 cairo_bo_trap_t
*trap
= &left
->deferred_trap
;
225 cairo_status_t status
= CAIRO_STATUS_SUCCESS
;
227 /* Only emit (trivial) non-degenerate trapezoids with positive height. */
228 if (likely (trap
->top
< bot
)) {
230 _cairo_traps_add_trap (container
,
232 &left
->edge
.line
, &trap
->right
->edge
.line
);
233 status
= _cairo_traps_status ((cairo_traps_t
*) container
);
237 box
.p1
.x
= left
->edge
.line
.p1
.x
;
238 box
.p1
.y
= trap
->top
;
239 box
.p2
.x
= trap
->right
->edge
.line
.p1
.x
;
241 status
= _cairo_boxes_add (container
, CAIRO_ANTIALIAS_DEFAULT
, &box
);
250 /* Start a new trapezoid at the given top y coordinate, whose edges
251 * are `edge' and `edge->next'. If `edge' already has a trapezoid,
252 * then either add it to the traps in `traps', if the trapezoid's
253 * right edge differs from `edge->next', or do nothing if the new
254 * trapezoid would be a continuation of the existing one. */
255 static inline cairo_status_t
256 _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t
*left
,
257 cairo_bo_edge_t
*right
,
259 cairo_bool_t do_traps
,
262 cairo_status_t status
;
264 if (left
->deferred_trap
.right
== right
)
265 return CAIRO_STATUS_SUCCESS
;
267 if (left
->deferred_trap
.right
!= NULL
) {
268 if (right
!= NULL
&& edges_collinear (left
->deferred_trap
.right
, right
))
270 /* continuation on right, so just swap edges */
271 left
->deferred_trap
.right
= right
;
272 return CAIRO_STATUS_SUCCESS
;
275 status
= _cairo_bo_edge_end_trap (left
, top
, do_traps
, container
);
276 if (unlikely (status
))
280 if (right
!= NULL
&& ! edges_collinear (left
, right
)) {
281 left
->deferred_trap
.top
= top
;
282 left
->deferred_trap
.right
= right
;
285 return CAIRO_STATUS_SUCCESS
;
288 static inline cairo_status_t
289 _active_edges_to_traps (cairo_bo_edge_t
*left
,
291 cairo_fill_rule_t fill_rule
,
292 cairo_bool_t do_traps
,
295 cairo_bo_edge_t
*right
;
296 cairo_status_t status
;
298 if (fill_rule
== CAIRO_FILL_RULE_WINDING
) {
299 while (left
!= NULL
) {
302 /* Greedily search for the closing edge, so that we generate the
303 * maximal span width with the minimal number of trapezoids.
305 in_out
= left
->edge
.dir
;
307 /* Check if there is a co-linear edge with an existing trap */
309 if (left
->deferred_trap
.right
== NULL
) {
310 while (right
!= NULL
&& right
->deferred_trap
.right
== NULL
)
313 if (right
!= NULL
&& edges_collinear (left
, right
)) {
314 /* continuation on left */
315 left
->deferred_trap
= right
->deferred_trap
;
316 right
->deferred_trap
.right
= NULL
;
320 /* End all subsumed traps */
322 while (right
!= NULL
) {
323 if (right
->deferred_trap
.right
!= NULL
) {
324 status
= _cairo_bo_edge_end_trap (right
, top
, do_traps
, container
);
325 if (unlikely (status
))
329 in_out
+= right
->edge
.dir
;
331 /* skip co-linear edges */
332 if (right
->next
== NULL
||
333 ! edges_collinear (right
, right
->next
))
342 status
= _cairo_bo_edge_start_or_continue_trap (left
, right
, top
,
343 do_traps
, container
);
344 if (unlikely (status
))
352 while (left
!= NULL
) {
356 while (right
!= NULL
) {
357 if (right
->deferred_trap
.right
!= NULL
) {
358 status
= _cairo_bo_edge_end_trap (right
, top
, do_traps
, container
);
359 if (unlikely (status
))
363 if ((in_out
++ & 1) == 0) {
364 cairo_bo_edge_t
*next
;
365 cairo_bool_t skip
= FALSE
;
367 /* skip co-linear edges */
370 skip
= edges_collinear (right
, next
);
379 status
= _cairo_bo_edge_start_or_continue_trap (left
, right
, top
,
380 do_traps
, container
);
381 if (unlikely (status
))
390 return CAIRO_STATUS_SUCCESS
;
393 static cairo_status_t
394 _cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t
**start_events
,
396 cairo_fill_rule_t fill_rule
,
397 cairo_bool_t do_traps
,
400 cairo_bo_sweep_line_t sweep_line
;
401 cairo_bo_event_t
*event
;
402 cairo_status_t status
;
404 _cairo_bo_sweep_line_init (&sweep_line
, start_events
, num_events
);
406 while ((event
= _cairo_bo_event_dequeue (&sweep_line
))) {
407 if (event
->point
.y
!= sweep_line
.current_y
) {
408 status
= _active_edges_to_traps (sweep_line
.head
,
409 sweep_line
.current_y
,
410 fill_rule
, do_traps
, container
);
411 if (unlikely (status
))
414 sweep_line
.current_y
= event
->point
.y
;
417 switch (event
->type
) {
418 case CAIRO_BO_EVENT_TYPE_START
:
419 _cairo_bo_sweep_line_insert (&sweep_line
, event
->edge
);
422 case CAIRO_BO_EVENT_TYPE_STOP
:
423 _cairo_bo_sweep_line_delete (&sweep_line
, event
->edge
);
425 if (event
->edge
->deferred_trap
.right
!= NULL
) {
426 status
= _cairo_bo_edge_end_trap (event
->edge
,
427 sweep_line
.current_y
,
428 do_traps
, container
);
429 if (unlikely (status
))
437 return CAIRO_STATUS_SUCCESS
;
441 _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (const cairo_polygon_t
*polygon
,
442 cairo_fill_rule_t fill_rule
,
443 cairo_boxes_t
*boxes
)
445 cairo_status_t status
;
446 cairo_bo_event_t stack_events
[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t
)];
447 cairo_bo_event_t
*events
;
448 cairo_bo_event_t
*stack_event_ptrs
[ARRAY_LENGTH (stack_events
) + 1];
449 cairo_bo_event_t
**event_ptrs
;
450 cairo_bo_edge_t stack_edges
[ARRAY_LENGTH (stack_events
)];
451 cairo_bo_edge_t
*edges
;
455 if (unlikely (polygon
->num_edges
== 0))
456 return CAIRO_STATUS_SUCCESS
;
458 num_events
= 2 * polygon
->num_edges
;
460 events
= stack_events
;
461 event_ptrs
= stack_event_ptrs
;
463 if (num_events
> ARRAY_LENGTH (stack_events
)) {
464 events
= _cairo_malloc_ab_plus_c (num_events
,
465 sizeof (cairo_bo_event_t
) +
466 sizeof (cairo_bo_edge_t
) +
467 sizeof (cairo_bo_event_t
*),
468 sizeof (cairo_bo_event_t
*));
469 if (unlikely (events
== NULL
))
470 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
472 event_ptrs
= (cairo_bo_event_t
**) (events
+ num_events
);
473 edges
= (cairo_bo_edge_t
*) (event_ptrs
+ num_events
+ 1);
476 for (i
= j
= 0; i
< polygon
->num_edges
; i
++) {
477 edges
[i
].edge
= polygon
->edges
[i
];
478 edges
[i
].deferred_trap
.right
= NULL
;
479 edges
[i
].prev
= NULL
;
480 edges
[i
].next
= NULL
;
482 event_ptrs
[j
] = &events
[j
];
483 events
[j
].type
= CAIRO_BO_EVENT_TYPE_START
;
484 events
[j
].point
.y
= polygon
->edges
[i
].top
;
485 events
[j
].point
.x
= polygon
->edges
[i
].line
.p1
.x
;
486 events
[j
].edge
= &edges
[i
];
489 event_ptrs
[j
] = &events
[j
];
490 events
[j
].type
= CAIRO_BO_EVENT_TYPE_STOP
;
491 events
[j
].point
.y
= polygon
->edges
[i
].bottom
;
492 events
[j
].point
.x
= polygon
->edges
[i
].line
.p1
.x
;
493 events
[j
].edge
= &edges
[i
];
497 status
= _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs
, j
,
500 if (events
!= stack_events
)
507 _cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t
*traps
,
508 cairo_fill_rule_t fill_rule
)
510 cairo_bo_event_t stack_events
[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t
)];
511 cairo_bo_event_t
*events
;
512 cairo_bo_event_t
*stack_event_ptrs
[ARRAY_LENGTH (stack_events
) + 1];
513 cairo_bo_event_t
**event_ptrs
;
514 cairo_bo_edge_t stack_edges
[ARRAY_LENGTH (stack_events
)];
515 cairo_bo_edge_t
*edges
;
516 cairo_status_t status
;
519 if (unlikely (traps
->num_traps
== 0))
520 return CAIRO_STATUS_SUCCESS
;
522 assert (traps
->is_rectilinear
);
524 i
= 4 * traps
->num_traps
;
526 events
= stack_events
;
527 event_ptrs
= stack_event_ptrs
;
529 if (i
> ARRAY_LENGTH (stack_events
)) {
530 events
= _cairo_malloc_ab_plus_c (i
,
531 sizeof (cairo_bo_event_t
) +
532 sizeof (cairo_bo_edge_t
) +
533 sizeof (cairo_bo_event_t
*),
534 sizeof (cairo_bo_event_t
*));
535 if (unlikely (events
== NULL
))
536 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
538 event_ptrs
= (cairo_bo_event_t
**) (events
+ i
);
539 edges
= (cairo_bo_edge_t
*) (event_ptrs
+ i
+ 1);
542 for (i
= j
= k
= 0; i
< traps
->num_traps
; i
++) {
543 edges
[k
].edge
.top
= traps
->traps
[i
].top
;
544 edges
[k
].edge
.bottom
= traps
->traps
[i
].bottom
;
545 edges
[k
].edge
.line
= traps
->traps
[i
].left
;
546 edges
[k
].edge
.dir
= 1;
547 edges
[k
].deferred_trap
.right
= NULL
;
548 edges
[k
].prev
= NULL
;
549 edges
[k
].next
= NULL
;
551 event_ptrs
[j
] = &events
[j
];
552 events
[j
].type
= CAIRO_BO_EVENT_TYPE_START
;
553 events
[j
].point
.y
= traps
->traps
[i
].top
;
554 events
[j
].point
.x
= traps
->traps
[i
].left
.p1
.x
;
555 events
[j
].edge
= &edges
[k
];
558 event_ptrs
[j
] = &events
[j
];
559 events
[j
].type
= CAIRO_BO_EVENT_TYPE_STOP
;
560 events
[j
].point
.y
= traps
->traps
[i
].bottom
;
561 events
[j
].point
.x
= traps
->traps
[i
].left
.p1
.x
;
562 events
[j
].edge
= &edges
[k
];
566 edges
[k
].edge
.top
= traps
->traps
[i
].top
;
567 edges
[k
].edge
.bottom
= traps
->traps
[i
].bottom
;
568 edges
[k
].edge
.line
= traps
->traps
[i
].right
;
569 edges
[k
].edge
.dir
= -1;
570 edges
[k
].deferred_trap
.right
= NULL
;
571 edges
[k
].prev
= NULL
;
572 edges
[k
].next
= NULL
;
574 event_ptrs
[j
] = &events
[j
];
575 events
[j
].type
= CAIRO_BO_EVENT_TYPE_START
;
576 events
[j
].point
.y
= traps
->traps
[i
].top
;
577 events
[j
].point
.x
= traps
->traps
[i
].right
.p1
.x
;
578 events
[j
].edge
= &edges
[k
];
581 event_ptrs
[j
] = &events
[j
];
582 events
[j
].type
= CAIRO_BO_EVENT_TYPE_STOP
;
583 events
[j
].point
.y
= traps
->traps
[i
].bottom
;
584 events
[j
].point
.x
= traps
->traps
[i
].right
.p1
.x
;
585 events
[j
].edge
= &edges
[k
];
590 _cairo_traps_clear (traps
);
591 status
= _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs
, j
,
594 traps
->is_rectilinear
= TRUE
;
596 if (events
!= stack_events
)