1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
3 * Copyright © 2002 Keith Packard
4 * Copyright © 2007 Red Hat, Inc.
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 Keith Packard
34 * Keith R. Packard <keithp@keithp.com>
35 * Carl D. Worth <cworth@cworth.org>
37 * 2002-07-15: Converted from XRenderCompositeDoublePoly to #cairo_trap_t. Carl D. Worth
42 #include "cairo-box-inline.h"
43 #include "cairo-boxes-private.h"
44 #include "cairo-error-private.h"
45 #include "cairo-line-private.h"
46 #include "cairo-region-private.h"
47 #include "cairo-slope-private.h"
48 #include "cairo-traps-private.h"
49 #include "cairo-spans-private.h"
51 /* private functions */
54 _cairo_traps_init (cairo_traps_t
*traps
)
56 VG (VALGRIND_MAKE_MEM_UNDEFINED (traps
, sizeof (cairo_traps_t
)));
58 traps
->status
= CAIRO_STATUS_SUCCESS
;
60 traps
->maybe_region
= 1;
61 traps
->is_rectilinear
= 0;
62 traps
->is_rectangular
= 0;
66 traps
->traps_size
= ARRAY_LENGTH (traps
->traps_embedded
);
67 traps
->traps
= traps
->traps_embedded
;
69 traps
->num_limits
= 0;
70 traps
->has_intersections
= FALSE
;
74 _cairo_traps_limit (cairo_traps_t
*traps
,
75 const cairo_box_t
*limits
,
80 traps
->limits
= limits
;
81 traps
->num_limits
= num_limits
;
83 traps
->bounds
= limits
[0];
84 for (i
= 1; i
< num_limits
; i
++)
85 _cairo_box_add_box (&traps
->bounds
, &limits
[i
]);
89 _cairo_traps_init_with_clip (cairo_traps_t
*traps
,
90 const cairo_clip_t
*clip
)
92 _cairo_traps_init (traps
);
94 _cairo_traps_limit (traps
, clip
->boxes
, clip
->num_boxes
);
98 _cairo_traps_clear (cairo_traps_t
*traps
)
100 traps
->status
= CAIRO_STATUS_SUCCESS
;
102 traps
->maybe_region
= 1;
103 traps
->is_rectilinear
= 0;
104 traps
->is_rectangular
= 0;
106 traps
->num_traps
= 0;
107 traps
->has_intersections
= FALSE
;
111 _cairo_traps_fini (cairo_traps_t
*traps
)
113 if (traps
->traps
!= traps
->traps_embedded
)
116 VG (VALGRIND_MAKE_MEM_NOACCESS (traps
, sizeof (cairo_traps_t
)));
119 /* make room for at least one more trap */
121 _cairo_traps_grow (cairo_traps_t
*traps
)
123 cairo_trapezoid_t
*new_traps
;
124 int new_size
= 4 * traps
->traps_size
;
126 if (CAIRO_INJECT_FAULT ()) {
127 traps
->status
= _cairo_error (CAIRO_STATUS_NO_MEMORY
);
131 if (traps
->traps
== traps
->traps_embedded
) {
132 new_traps
= _cairo_malloc_ab (new_size
, sizeof (cairo_trapezoid_t
));
133 if (new_traps
!= NULL
)
134 memcpy (new_traps
, traps
->traps
, sizeof (traps
->traps_embedded
));
136 new_traps
= _cairo_realloc_ab (traps
->traps
,
137 new_size
, sizeof (cairo_trapezoid_t
));
140 if (unlikely (new_traps
== NULL
)) {
141 traps
->status
= _cairo_error (CAIRO_STATUS_NO_MEMORY
);
145 traps
->traps
= new_traps
;
146 traps
->traps_size
= new_size
;
151 _cairo_traps_add_trap (cairo_traps_t
*traps
,
152 cairo_fixed_t top
, cairo_fixed_t bottom
,
153 const cairo_line_t
*left
,
154 const cairo_line_t
*right
)
156 cairo_trapezoid_t
*trap
;
158 assert (left
->p1
.y
!= left
->p2
.y
);
159 assert (right
->p1
.y
!= right
->p2
.y
);
160 assert (bottom
> top
);
162 if (unlikely (traps
->num_traps
== traps
->traps_size
)) {
163 if (unlikely (! _cairo_traps_grow (traps
)))
167 trap
= &traps
->traps
[traps
->num_traps
++];
169 trap
->bottom
= bottom
;
171 trap
->right
= *right
;
175 _cairo_traps_add_clipped_trap (cairo_traps_t
*traps
,
176 cairo_fixed_t _top
, cairo_fixed_t _bottom
,
177 const cairo_line_t
*_left
,
178 const cairo_line_t
*_right
)
180 /* Note: With the goofy trapezoid specification, (where an
181 * arbitrary two points on the lines can specified for the left
182 * and right edges), these limit checks would not work in
183 * general. For example, one can imagine a trapezoid entirely
184 * within the limits, but with two points used to specify the left
185 * edge entirely to the right of the limits. Fortunately, for our
186 * purposes, cairo will never generate such a crazy
187 * trapezoid. Instead, cairo always uses for its points the
188 * extreme positions of the edge that are visible on at least some
189 * trapezoid. With this constraint, it's impossible for both
190 * points to be outside the limits while the relevant edge is
191 * entirely inside the limits.
193 if (traps
->num_limits
) {
194 const cairo_box_t
*b
= &traps
->bounds
;
195 cairo_fixed_t top
= _top
, bottom
= _bottom
;
196 cairo_line_t left
= *_left
, right
= *_right
;
198 /* Trivially reject if trapezoid is entirely to the right or
199 * to the left of the limits. */
200 if (left
.p1
.x
>= b
->p2
.x
&& left
.p2
.x
>= b
->p2
.x
)
203 if (right
.p1
.x
<= b
->p1
.x
&& right
.p2
.x
<= b
->p1
.x
)
206 /* And reject if the trapezoid is entirely above or below */
207 if (top
>= b
->p2
.y
|| bottom
<= b
->p1
.y
)
210 /* Otherwise, clip the trapezoid to the limits. We only clip
211 * where an edge is entirely outside the limits. If we wanted
212 * to be more clever, we could handle cases where a trapezoid
213 * edge intersects the edge of the limits, but that would
214 * require slicing this trapezoid into multiple trapezoids,
215 * and I'm not sure the effort would be worth it. */
219 if (bottom
> b
->p2
.y
)
222 if (left
.p1
.x
<= b
->p1
.x
&& left
.p2
.x
<= b
->p1
.x
)
223 left
.p1
.x
= left
.p2
.x
= b
->p1
.x
;
225 if (right
.p1
.x
>= b
->p2
.x
&& right
.p2
.x
>= b
->p2
.x
)
226 right
.p1
.x
= right
.p2
.x
= b
->p2
.x
;
228 /* Trivial discards for empty trapezoids that are likely to
229 * be produced by our tessellators (most notably convex_quad
230 * when given a simple rectangle).
235 /* cheap colinearity check */
236 if (right
.p1
.x
<= left
.p1
.x
&& right
.p1
.y
== left
.p1
.y
&&
237 right
.p2
.x
<= left
.p2
.x
&& right
.p2
.y
== left
.p2
.y
)
240 _cairo_traps_add_trap (traps
, top
, bottom
, &left
, &right
);
242 _cairo_traps_add_trap (traps
, _top
, _bottom
, _left
, _right
);
246 _compare_point_fixed_by_y (const void *av
, const void *bv
)
248 const cairo_point_t
*a
= av
, *b
= bv
;
249 int ret
= a
->y
- b
->y
;
256 _cairo_traps_tessellate_convex_quad (cairo_traps_t
*traps
,
257 const cairo_point_t q
[4])
261 cairo_slope_t ab
, ad
;
262 cairo_bool_t b_left_of_d
;
266 /* Choose a as a point with minimal y */
268 for (i
= 1; i
< 4; i
++)
269 if (_compare_point_fixed_by_y (&q
[i
], &q
[a
]) < 0)
272 /* b and d are adjacent to a, while c is opposite */
277 /* Choose between b and d so that b.y is less than d.y */
278 if (_compare_point_fixed_by_y (&q
[d
], &q
[b
]) < 0) {
283 /* Without freedom left to choose anything else, we have four
284 * cases to tessellate.
286 * First, we have to determine the Y-axis sort of the four
287 * vertices, (either abcd or abdc). After that we need to detemine
288 * which edges will be "left" and which will be "right" in the
289 * resulting trapezoids. This can be determined by computing a
290 * slope comparison of ab and ad to determine if b is left of d or
293 * Note that "left of" here is in the sense of which edges should
294 * be the left vs. right edges of the trapezoid. In particular, b
295 * left of d does *not* mean that b.x is less than d.x.
297 * This should hopefully be made clear in the lame ASCII art
298 * below. Since the same slope comparison is used in all cases, we
299 * compute it before testing for the Y-value sort. */
301 /* Note: If a == b then the ab slope doesn't give us any
302 * information. In that case, we can replace it with the ac (or
303 * equivalenly the bc) slope which gives us exactly the same
304 * information we need. At worst the names of the identifiers ab
305 * and b_left_of_d are inaccurate in this case, (would be ac, and
307 if (q
[a
].x
== q
[b
].x
&& q
[a
].y
== q
[b
].y
)
308 _cairo_slope_init (&ab
, &q
[a
], &q
[c
]);
310 _cairo_slope_init (&ab
, &q
[a
], &q
[b
]);
312 _cairo_slope_init (&ad
, &q
[a
], &q
[d
]);
314 b_left_of_d
= _cairo_slope_compare (&ab
, &ad
) > 0;
316 if (q
[c
].y
<= q
[d
].y
) {
318 /* Y-sort is abcd and b is left of d, (slope(ab) > slope (ad))
322 * / / /| |\ a.y b.y ab ad
324 * / / | | \ \ b.y c.y bc ad
326 * | / \| \ \ c.y d.y cd ad
329 left
.p1
= q
[a
]; left
.p2
= q
[b
];
330 right
.p1
= q
[a
]; right
.p2
= q
[d
];
331 _cairo_traps_add_clipped_trap (traps
, q
[a
].y
, q
[b
].y
, &left
, &right
);
332 left
.p1
= q
[b
]; left
.p2
= q
[c
];
333 _cairo_traps_add_clipped_trap (traps
, q
[b
].y
, q
[c
].y
, &left
, &right
);
334 left
.p1
= q
[c
]; left
.p2
= q
[d
];
335 _cairo_traps_add_clipped_trap (traps
, q
[c
].y
, q
[d
].y
, &left
, &right
);
337 /* Y-sort is abcd and b is right of d, (slope(ab) <= slope (ad))
340 * /| |\ \ \ a.y b.y ad ab
342 * / / | | \ \ b.y c.y ad bc
344 * / / |/ \ | c.y d.y ad cd
347 left
.p1
= q
[a
]; left
.p2
= q
[d
];
348 right
.p1
= q
[a
]; right
.p2
= q
[b
];
349 _cairo_traps_add_clipped_trap (traps
, q
[a
].y
, q
[b
].y
, &left
, &right
);
350 right
.p1
= q
[b
]; right
.p2
= q
[c
];
351 _cairo_traps_add_clipped_trap (traps
, q
[b
].y
, q
[c
].y
, &left
, &right
);
352 right
.p1
= q
[c
]; right
.p2
= q
[d
];
353 _cairo_traps_add_clipped_trap (traps
, q
[c
].y
, q
[d
].y
, &left
, &right
);
357 /* Y-sort is abdc and b is left of d, (slope (ab) > slope (ad))
360 * // / \ |\ a.y b.y ab ad
362 * / / \ \ \ \ b.y d.y bc ad
364 * // \ / \| d.y c.y bc dc
367 left
.p1
= q
[a
]; left
.p2
= q
[b
];
368 right
.p1
= q
[a
]; right
.p2
= q
[d
];
369 _cairo_traps_add_clipped_trap (traps
, q
[a
].y
, q
[b
].y
, &left
, &right
);
370 left
.p1
= q
[b
]; left
.p2
= q
[c
];
371 _cairo_traps_add_clipped_trap (traps
, q
[b
].y
, q
[d
].y
, &left
, &right
);
372 right
.p1
= q
[d
]; right
.p2
= q
[c
];
373 _cairo_traps_add_clipped_trap (traps
, q
[d
].y
, q
[c
].y
, &left
, &right
);
375 /* Y-sort is abdc and b is right of d, (slope (ab) <= slope (ad))
378 * /| / \ \\ a.y b.y ad ab
380 * / / / / \ \ b.y d.y ad bc
382 * |/ \ / \\ d.y c.y dc bc
385 left
.p1
= q
[a
]; left
.p2
= q
[d
];
386 right
.p1
= q
[a
]; right
.p2
= q
[b
];
387 _cairo_traps_add_clipped_trap (traps
, q
[a
].y
, q
[b
].y
, &left
, &right
);
388 right
.p1
= q
[b
]; right
.p2
= q
[c
];
389 _cairo_traps_add_clipped_trap (traps
, q
[b
].y
, q
[d
].y
, &left
, &right
);
390 left
.p1
= q
[d
]; left
.p2
= q
[c
];
391 _cairo_traps_add_clipped_trap (traps
, q
[d
].y
, q
[c
].y
, &left
, &right
);
396 static void add_tri (cairo_traps_t
*traps
,
398 const cairo_line_t
*left
,
399 const cairo_line_t
*right
)
407 if (cairo_lines_compare_at_y (left
, right
, y1
) > 0) {
408 const cairo_line_t
*tmp
= left
;
413 _cairo_traps_add_clipped_trap (traps
, y1
, y2
, left
, right
);
417 _cairo_traps_tessellate_triangle_with_edges (cairo_traps_t
*traps
,
418 const cairo_point_t t
[3],
419 const cairo_point_t edges
[4])
421 cairo_line_t lines
[3];
423 if (edges
[0].y
<= edges
[1].y
) {
424 lines
[0].p1
= edges
[0];
425 lines
[0].p2
= edges
[1];
427 lines
[0].p1
= edges
[1];
428 lines
[0].p2
= edges
[0];
431 if (edges
[2].y
<= edges
[3].y
) {
432 lines
[1].p1
= edges
[2];
433 lines
[1].p2
= edges
[3];
435 lines
[1].p1
= edges
[3];
436 lines
[1].p2
= edges
[2];
439 if (t
[1].y
== t
[2].y
) {
440 add_tri (traps
, t
[0].y
, t
[1].y
, &lines
[0], &lines
[1]);
444 if (t
[1].y
<= t
[2].y
) {
452 if (((t
[1].y
- t
[0].y
) < 0) ^ ((t
[2].y
- t
[0].y
) < 0)) {
453 add_tri (traps
, t
[0].y
, t
[1].y
, &lines
[0], &lines
[2]);
454 add_tri (traps
, t
[0].y
, t
[2].y
, &lines
[1], &lines
[2]);
455 } else if (abs(t
[1].y
- t
[0].y
) < abs(t
[2].y
- t
[0].y
)) {
456 add_tri (traps
, t
[0].y
, t
[1].y
, &lines
[0], &lines
[1]);
457 add_tri (traps
, t
[1].y
, t
[2].y
, &lines
[2], &lines
[1]);
459 add_tri (traps
, t
[0].y
, t
[2].y
, &lines
[1], &lines
[0]);
460 add_tri (traps
, t
[1].y
, t
[2].y
, &lines
[2], &lines
[0]);
465 * _cairo_traps_init_boxes:
466 * @traps: a #cairo_traps_t
467 * @box: an array box that will each be converted to a single trapezoid
468 * to store in @traps.
470 * Initializes a #cairo_traps_t to contain an array of rectangular
474 _cairo_traps_init_boxes (cairo_traps_t
*traps
,
475 const cairo_boxes_t
*boxes
)
477 cairo_trapezoid_t
*trap
;
478 const struct _cairo_boxes_chunk
*chunk
;
480 _cairo_traps_init (traps
);
482 while (traps
->traps_size
< boxes
->num_boxes
) {
483 if (unlikely (! _cairo_traps_grow (traps
))) {
484 _cairo_traps_fini (traps
);
485 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
489 traps
->num_traps
= boxes
->num_boxes
;
490 traps
->is_rectilinear
= TRUE
;
491 traps
->is_rectangular
= TRUE
;
492 traps
->maybe_region
= boxes
->is_pixel_aligned
;
494 trap
= &traps
->traps
[0];
495 for (chunk
= &boxes
->chunks
; chunk
!= NULL
; chunk
= chunk
->next
) {
496 const cairo_box_t
*box
;
500 for (i
= 0; i
< chunk
->count
; i
++) {
501 trap
->top
= box
->p1
.y
;
502 trap
->bottom
= box
->p2
.y
;
504 trap
->left
.p1
= box
->p1
;
505 trap
->left
.p2
.x
= box
->p1
.x
;
506 trap
->left
.p2
.y
= box
->p2
.y
;
508 trap
->right
.p1
.x
= box
->p2
.x
;
509 trap
->right
.p1
.y
= box
->p1
.y
;
510 trap
->right
.p2
= box
->p2
;
516 return CAIRO_STATUS_SUCCESS
;
520 _cairo_traps_tessellate_rectangle (cairo_traps_t
*traps
,
521 const cairo_point_t
*top_left
,
522 const cairo_point_t
*bottom_right
)
526 cairo_fixed_t top
, bottom
;
528 if (top_left
->y
== bottom_right
->y
)
529 return CAIRO_STATUS_SUCCESS
;
531 if (top_left
->x
== bottom_right
->x
)
532 return CAIRO_STATUS_SUCCESS
;
534 left
.p1
.x
= left
.p2
.x
= top_left
->x
;
535 left
.p1
.y
= right
.p1
.y
= top_left
->y
;
536 right
.p1
.x
= right
.p2
.x
= bottom_right
->x
;
537 left
.p2
.y
= right
.p2
.y
= bottom_right
->y
;
540 bottom
= bottom_right
->y
;
542 if (traps
->num_limits
) {
543 cairo_bool_t reversed
;
546 if (top
>= traps
->bounds
.p2
.y
|| bottom
<= traps
->bounds
.p1
.y
)
547 return CAIRO_STATUS_SUCCESS
;
549 /* support counter-clockwise winding for rectangular tessellation */
550 reversed
= top_left
->x
> bottom_right
->x
;
552 right
.p1
.x
= right
.p2
.x
= top_left
->x
;
553 left
.p1
.x
= left
.p2
.x
= bottom_right
->x
;
556 if (left
.p1
.x
>= traps
->bounds
.p2
.x
|| right
.p1
.x
<= traps
->bounds
.p1
.x
)
557 return CAIRO_STATUS_SUCCESS
;
559 for (n
= 0; n
< traps
->num_limits
; n
++) {
560 const cairo_box_t
*limits
= &traps
->limits
[n
];
561 cairo_line_t _left
, _right
;
562 cairo_fixed_t _top
, _bottom
;
564 if (top
>= limits
->p2
.y
)
566 if (bottom
<= limits
->p1
.y
)
569 /* Trivially reject if trapezoid is entirely to the right or
570 * to the left of the limits. */
571 if (left
.p1
.x
>= limits
->p2
.x
)
573 if (right
.p1
.x
<= limits
->p1
.x
)
576 /* Otherwise, clip the trapezoid to the limits. */
578 if (_top
< limits
->p1
.y
)
582 if (_bottom
> limits
->p2
.y
)
583 _bottom
= limits
->p2
.y
;
589 if (_left
.p1
.x
< limits
->p1
.x
) {
590 _left
.p1
.x
= limits
->p1
.x
;
591 _left
.p1
.y
= limits
->p1
.y
;
592 _left
.p2
.x
= limits
->p1
.x
;
593 _left
.p2
.y
= limits
->p2
.y
;
597 if (_right
.p1
.x
> limits
->p2
.x
) {
598 _right
.p1
.x
= limits
->p2
.x
;
599 _right
.p1
.y
= limits
->p1
.y
;
600 _right
.p2
.x
= limits
->p2
.x
;
601 _right
.p2
.y
= limits
->p2
.y
;
604 if (left
.p1
.x
>= right
.p1
.x
)
608 _cairo_traps_add_trap (traps
, _top
, _bottom
, &_right
, &_left
);
610 _cairo_traps_add_trap (traps
, _top
, _bottom
, &_left
, &_right
);
613 _cairo_traps_add_trap (traps
, top
, bottom
, &left
, &right
);
616 return traps
->status
;
620 _cairo_traps_translate (cairo_traps_t
*traps
, int x
, int y
)
622 cairo_fixed_t xoff
, yoff
;
623 cairo_trapezoid_t
*t
;
626 /* Ugh. The cairo_composite/(Render) interface doesn't allow
627 an offset for the trapezoids. Need to manually shift all
628 the coordinates to align with the offset origin of the
629 intermediate surface. */
631 xoff
= _cairo_fixed_from_int (x
);
632 yoff
= _cairo_fixed_from_int (y
);
634 for (i
= 0, t
= traps
->traps
; i
< traps
->num_traps
; i
++, t
++) {
637 t
->left
.p1
.x
+= xoff
;
638 t
->left
.p1
.y
+= yoff
;
639 t
->left
.p2
.x
+= xoff
;
640 t
->left
.p2
.y
+= yoff
;
641 t
->right
.p1
.x
+= xoff
;
642 t
->right
.p1
.y
+= yoff
;
643 t
->right
.p2
.x
+= xoff
;
644 t
->right
.p2
.y
+= yoff
;
649 _cairo_trapezoid_array_translate_and_scale (cairo_trapezoid_t
*offset_traps
,
650 cairo_trapezoid_t
*src_traps
,
652 double tx
, double ty
,
653 double sx
, double sy
)
656 cairo_fixed_t xoff
= _cairo_fixed_from_double (tx
);
657 cairo_fixed_t yoff
= _cairo_fixed_from_double (ty
);
659 if (sx
== 1.0 && sy
== 1.0) {
660 for (i
= 0; i
< num_traps
; i
++) {
661 offset_traps
[i
].top
= src_traps
[i
].top
+ yoff
;
662 offset_traps
[i
].bottom
= src_traps
[i
].bottom
+ yoff
;
663 offset_traps
[i
].left
.p1
.x
= src_traps
[i
].left
.p1
.x
+ xoff
;
664 offset_traps
[i
].left
.p1
.y
= src_traps
[i
].left
.p1
.y
+ yoff
;
665 offset_traps
[i
].left
.p2
.x
= src_traps
[i
].left
.p2
.x
+ xoff
;
666 offset_traps
[i
].left
.p2
.y
= src_traps
[i
].left
.p2
.y
+ yoff
;
667 offset_traps
[i
].right
.p1
.x
= src_traps
[i
].right
.p1
.x
+ xoff
;
668 offset_traps
[i
].right
.p1
.y
= src_traps
[i
].right
.p1
.y
+ yoff
;
669 offset_traps
[i
].right
.p2
.x
= src_traps
[i
].right
.p2
.x
+ xoff
;
670 offset_traps
[i
].right
.p2
.y
= src_traps
[i
].right
.p2
.y
+ yoff
;
673 cairo_fixed_t xsc
= _cairo_fixed_from_double (sx
);
674 cairo_fixed_t ysc
= _cairo_fixed_from_double (sy
);
676 for (i
= 0; i
< num_traps
; i
++) {
677 offset_traps
[i
].top
= _cairo_fixed_mul (src_traps
[i
].top
+ yoff
, ysc
);
678 offset_traps
[i
].bottom
= _cairo_fixed_mul (src_traps
[i
].bottom
+ yoff
, ysc
);
679 offset_traps
[i
].left
.p1
.x
= _cairo_fixed_mul (src_traps
[i
].left
.p1
.x
+ xoff
, xsc
);
680 offset_traps
[i
].left
.p1
.y
= _cairo_fixed_mul (src_traps
[i
].left
.p1
.y
+ yoff
, ysc
);
681 offset_traps
[i
].left
.p2
.x
= _cairo_fixed_mul (src_traps
[i
].left
.p2
.x
+ xoff
, xsc
);
682 offset_traps
[i
].left
.p2
.y
= _cairo_fixed_mul (src_traps
[i
].left
.p2
.y
+ yoff
, ysc
);
683 offset_traps
[i
].right
.p1
.x
= _cairo_fixed_mul (src_traps
[i
].right
.p1
.x
+ xoff
, xsc
);
684 offset_traps
[i
].right
.p1
.y
= _cairo_fixed_mul (src_traps
[i
].right
.p1
.y
+ yoff
, ysc
);
685 offset_traps
[i
].right
.p2
.x
= _cairo_fixed_mul (src_traps
[i
].right
.p2
.x
+ xoff
, xsc
);
686 offset_traps
[i
].right
.p2
.y
= _cairo_fixed_mul (src_traps
[i
].right
.p2
.y
+ yoff
, ysc
);
692 _cairo_trap_contains (cairo_trapezoid_t
*t
, cairo_point_t
*pt
)
694 cairo_slope_t slope_left
, slope_pt
, slope_right
;
698 if (t
->bottom
< pt
->y
)
701 _cairo_slope_init (&slope_left
, &t
->left
.p1
, &t
->left
.p2
);
702 _cairo_slope_init (&slope_pt
, &t
->left
.p1
, pt
);
704 if (_cairo_slope_compare (&slope_left
, &slope_pt
) < 0)
707 _cairo_slope_init (&slope_right
, &t
->right
.p1
, &t
->right
.p2
);
708 _cairo_slope_init (&slope_pt
, &t
->right
.p1
, pt
);
710 if (_cairo_slope_compare (&slope_pt
, &slope_right
) < 0)
717 _cairo_traps_contain (const cairo_traps_t
*traps
,
723 point
.x
= _cairo_fixed_from_double (x
);
724 point
.y
= _cairo_fixed_from_double (y
);
726 for (i
= 0; i
< traps
->num_traps
; i
++) {
727 if (_cairo_trap_contains (&traps
->traps
[i
], &point
))
735 _line_compute_intersection_x_for_y (const cairo_line_t
*line
,
738 return _cairo_edge_compute_intersection_x_for_y (&line
->p1
, &line
->p2
, y
);
742 _cairo_traps_extents (const cairo_traps_t
*traps
,
743 cairo_box_t
*extents
)
747 if (traps
->num_traps
== 0) {
748 extents
->p1
.x
= extents
->p1
.y
= 0;
749 extents
->p2
.x
= extents
->p2
.y
= 0;
753 extents
->p1
.x
= extents
->p1
.y
= INT32_MAX
;
754 extents
->p2
.x
= extents
->p2
.y
= INT32_MIN
;
756 for (i
= 0; i
< traps
->num_traps
; i
++) {
757 const cairo_trapezoid_t
*trap
= &traps
->traps
[i
];
759 if (trap
->top
< extents
->p1
.y
)
760 extents
->p1
.y
= trap
->top
;
761 if (trap
->bottom
> extents
->p2
.y
)
762 extents
->p2
.y
= trap
->bottom
;
764 if (trap
->left
.p1
.x
< extents
->p1
.x
) {
765 cairo_fixed_t x
= trap
->left
.p1
.x
;
766 if (trap
->top
!= trap
->left
.p1
.y
) {
767 x
= _line_compute_intersection_x_for_y (&trap
->left
,
769 if (x
< extents
->p1
.x
)
774 if (trap
->left
.p2
.x
< extents
->p1
.x
) {
775 cairo_fixed_t x
= trap
->left
.p2
.x
;
776 if (trap
->bottom
!= trap
->left
.p2
.y
) {
777 x
= _line_compute_intersection_x_for_y (&trap
->left
,
779 if (x
< extents
->p1
.x
)
785 if (trap
->right
.p1
.x
> extents
->p2
.x
) {
786 cairo_fixed_t x
= trap
->right
.p1
.x
;
787 if (trap
->top
!= trap
->right
.p1
.y
) {
788 x
= _line_compute_intersection_x_for_y (&trap
->right
,
790 if (x
> extents
->p2
.x
)
795 if (trap
->right
.p2
.x
> extents
->p2
.x
) {
796 cairo_fixed_t x
= trap
->right
.p2
.x
;
797 if (trap
->bottom
!= trap
->right
.p2
.y
) {
798 x
= _line_compute_intersection_x_for_y (&trap
->right
,
800 if (x
> extents
->p2
.x
)
809 _mono_edge_is_vertical (const cairo_line_t
*line
)
811 return _cairo_fixed_integer_round_down (line
->p1
.x
) == _cairo_fixed_integer_round_down (line
->p2
.x
);
815 _traps_are_pixel_aligned (cairo_traps_t
*traps
,
816 cairo_antialias_t antialias
)
820 if (antialias
== CAIRO_ANTIALIAS_NONE
) {
821 for (i
= 0; i
< traps
->num_traps
; i
++) {
822 if (! _mono_edge_is_vertical (&traps
->traps
[i
].left
) ||
823 ! _mono_edge_is_vertical (&traps
->traps
[i
].right
))
825 traps
->maybe_region
= FALSE
;
830 for (i
= 0; i
< traps
->num_traps
; i
++) {
831 if (traps
->traps
[i
].left
.p1
.x
!= traps
->traps
[i
].left
.p2
.x
||
832 traps
->traps
[i
].right
.p1
.x
!= traps
->traps
[i
].right
.p2
.x
||
833 ! _cairo_fixed_is_integer (traps
->traps
[i
].top
) ||
834 ! _cairo_fixed_is_integer (traps
->traps
[i
].bottom
) ||
835 ! _cairo_fixed_is_integer (traps
->traps
[i
].left
.p1
.x
) ||
836 ! _cairo_fixed_is_integer (traps
->traps
[i
].right
.p1
.x
))
838 traps
->maybe_region
= FALSE
;
848 * _cairo_traps_extract_region:
849 * @traps: a #cairo_traps_t
850 * @region: a #cairo_region_t
852 * Determines if a set of trapezoids are exactly representable as a
853 * cairo region. If so, the passed-in region is initialized to
854 * the area representing the given traps. It should be finalized
855 * with cairo_region_fini(). If not, %CAIRO_INT_STATUS_UNSUPPORTED
858 * Return value: %CAIRO_STATUS_SUCCESS, %CAIRO_INT_STATUS_UNSUPPORTED
859 * or %CAIRO_STATUS_NO_MEMORY
862 _cairo_traps_extract_region (cairo_traps_t
*traps
,
863 cairo_antialias_t antialias
,
864 cairo_region_t
**region
)
866 cairo_rectangle_int_t stack_rects
[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t
)];
867 cairo_rectangle_int_t
*rects
= stack_rects
;
868 cairo_int_status_t status
;
871 /* we only treat this a hint... */
872 if (antialias
!= CAIRO_ANTIALIAS_NONE
&& ! traps
->maybe_region
)
873 return CAIRO_INT_STATUS_UNSUPPORTED
;
875 if (! _traps_are_pixel_aligned (traps
, antialias
)) {
876 traps
->maybe_region
= FALSE
;
877 return CAIRO_INT_STATUS_UNSUPPORTED
;
880 if (traps
->num_traps
> ARRAY_LENGTH (stack_rects
)) {
881 rects
= _cairo_malloc_ab (traps
->num_traps
, sizeof (cairo_rectangle_int_t
));
883 if (unlikely (rects
== NULL
))
884 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
888 for (i
= 0; i
< traps
->num_traps
; i
++) {
891 if (antialias
== CAIRO_ANTIALIAS_NONE
) {
892 x1
= _cairo_fixed_integer_round_down (traps
->traps
[i
].left
.p1
.x
);
893 y1
= _cairo_fixed_integer_round_down (traps
->traps
[i
].top
);
894 x2
= _cairo_fixed_integer_round_down (traps
->traps
[i
].right
.p1
.x
);
895 y2
= _cairo_fixed_integer_round_down (traps
->traps
[i
].bottom
);
897 x1
= _cairo_fixed_integer_part (traps
->traps
[i
].left
.p1
.x
);
898 y1
= _cairo_fixed_integer_part (traps
->traps
[i
].top
);
899 x2
= _cairo_fixed_integer_part (traps
->traps
[i
].right
.p1
.x
);
900 y2
= _cairo_fixed_integer_part (traps
->traps
[i
].bottom
);
903 if (x2
> x1
&& y2
> y1
) {
904 rects
[rect_count
].x
= x1
;
905 rects
[rect_count
].y
= y1
;
906 rects
[rect_count
].width
= x2
- x1
;
907 rects
[rect_count
].height
= y2
- y1
;
913 *region
= cairo_region_create_rectangles (rects
, rect_count
);
914 status
= (*region
)->status
;
916 if (rects
!= stack_rects
)
923 _cairo_traps_to_boxes (cairo_traps_t
*traps
,
924 cairo_antialias_t antialias
,
925 cairo_boxes_t
*boxes
)
929 for (i
= 0; i
< traps
->num_traps
; i
++) {
930 if (traps
->traps
[i
].left
.p1
.x
!= traps
->traps
[i
].left
.p2
.x
||
931 traps
->traps
[i
].right
.p1
.x
!= traps
->traps
[i
].right
.p2
.x
)
935 _cairo_boxes_init (boxes
);
937 boxes
->num_boxes
= traps
->num_traps
;
938 boxes
->chunks
.base
= (cairo_box_t
*) traps
->traps
;
939 boxes
->chunks
.count
= traps
->num_traps
;
940 boxes
->chunks
.size
= traps
->num_traps
;
942 if (antialias
!= CAIRO_ANTIALIAS_NONE
) {
943 for (i
= 0; i
< traps
->num_traps
; i
++) {
944 /* Note the traps and boxes alias so we need to take the local copies first. */
945 cairo_fixed_t x1
= traps
->traps
[i
].left
.p1
.x
;
946 cairo_fixed_t x2
= traps
->traps
[i
].right
.p1
.x
;
947 cairo_fixed_t y1
= traps
->traps
[i
].top
;
948 cairo_fixed_t y2
= traps
->traps
[i
].bottom
;
950 boxes
->chunks
.base
[i
].p1
.x
= x1
;
951 boxes
->chunks
.base
[i
].p1
.y
= y1
;
952 boxes
->chunks
.base
[i
].p2
.x
= x2
;
953 boxes
->chunks
.base
[i
].p2
.y
= y2
;
955 if (boxes
->is_pixel_aligned
) {
956 boxes
->is_pixel_aligned
=
957 _cairo_fixed_is_integer (x1
) && _cairo_fixed_is_integer (y1
) &&
958 _cairo_fixed_is_integer (x2
) && _cairo_fixed_is_integer (y2
);
962 boxes
->is_pixel_aligned
= TRUE
;
964 for (i
= 0; i
< traps
->num_traps
; i
++) {
965 /* Note the traps and boxes alias so we need to take the local copies first. */
966 cairo_fixed_t x1
= traps
->traps
[i
].left
.p1
.x
;
967 cairo_fixed_t x2
= traps
->traps
[i
].right
.p1
.x
;
968 cairo_fixed_t y1
= traps
->traps
[i
].top
;
969 cairo_fixed_t y2
= traps
->traps
[i
].bottom
;
971 /* round down here to match Pixman's behavior when using traps. */
972 boxes
->chunks
.base
[i
].p1
.x
= _cairo_fixed_round_down (x1
);
973 boxes
->chunks
.base
[i
].p1
.y
= _cairo_fixed_round_down (y1
);
974 boxes
->chunks
.base
[i
].p2
.x
= _cairo_fixed_round_down (x2
);
975 boxes
->chunks
.base
[i
].p2
.y
= _cairo_fixed_round_down (y2
);
982 /* moves trap points such that they become the actual corners of the trapezoid */
984 _sanitize_trap (cairo_trapezoid_t
*t
)
986 cairo_trapezoid_t s
= *t
;
988 #define FIX(lr, tb, p) \
989 if (t->lr.p.y != t->tb) { \
990 t->lr.p.x = s.lr.p2.x + _cairo_fixed_mul_div_floor (s.lr.p1.x - s.lr.p2.x, s.tb - s.lr.p2.y, s.lr.p1.y - s.lr.p2.y); \
994 FIX (left
, bottom
, p2
);
995 FIX (right
, top
, p1
);
996 FIX (right
, bottom
, p2
);
999 cairo_private cairo_status_t
1000 _cairo_traps_path (const cairo_traps_t
*traps
,
1001 cairo_path_fixed_t
*path
)
1005 for (i
= 0; i
< traps
->num_traps
; i
++) {
1006 cairo_status_t status
;
1007 cairo_trapezoid_t trap
= traps
->traps
[i
];
1009 if (trap
.top
== trap
.bottom
)
1012 _sanitize_trap (&trap
);
1014 status
= _cairo_path_fixed_move_to (path
, trap
.left
.p1
.x
, trap
.top
);
1015 if (unlikely (status
)) return status
;
1016 status
= _cairo_path_fixed_line_to (path
, trap
.right
.p1
.x
, trap
.top
);
1017 if (unlikely (status
)) return status
;
1018 status
= _cairo_path_fixed_line_to (path
, trap
.right
.p2
.x
, trap
.bottom
);
1019 if (unlikely (status
)) return status
;
1020 status
= _cairo_path_fixed_line_to (path
, trap
.left
.p2
.x
, trap
.bottom
);
1021 if (unlikely (status
)) return status
;
1022 status
= _cairo_path_fixed_close_path (path
);
1023 if (unlikely (status
)) return status
;
1026 return CAIRO_STATUS_SUCCESS
;
1030 _cairo_debug_print_traps (FILE *file
, const cairo_traps_t
*traps
)
1032 cairo_box_t extents
;
1036 if (traps
->has_limits
) {
1037 printf ("%s: limits=(%d, %d, %d, %d)\n",
1039 traps
->limits
.p1
.x
, traps
->limits
.p1
.y
,
1040 traps
->limits
.p2
.x
, traps
->limits
.p2
.y
);
1044 _cairo_traps_extents (traps
, &extents
);
1045 fprintf (file
, "extents=(%d, %d, %d, %d)\n",
1046 extents
.p1
.x
, extents
.p1
.y
,
1047 extents
.p2
.x
, extents
.p2
.y
);
1049 for (n
= 0; n
< traps
->num_traps
; n
++) {
1050 fprintf (file
, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
1051 traps
->traps
[n
].top
,
1052 traps
->traps
[n
].bottom
,
1053 traps
->traps
[n
].left
.p1
.x
,
1054 traps
->traps
[n
].left
.p1
.y
,
1055 traps
->traps
[n
].left
.p2
.x
,
1056 traps
->traps
[n
].left
.p2
.y
,
1057 traps
->traps
[n
].right
.p1
.x
,
1058 traps
->traps
[n
].right
.p1
.y
,
1059 traps
->traps
[n
].right
.p2
.x
,
1060 traps
->traps
[n
].right
.p2
.y
);
1064 struct cairo_trap_renderer
{
1065 cairo_span_renderer_t base
;
1066 cairo_traps_t
*traps
;
1069 static cairo_status_t
1070 span_to_traps (void *abstract_renderer
, int y
, int h
,
1071 const cairo_half_open_span_t
*spans
, unsigned num_spans
)
1073 struct cairo_trap_renderer
*r
= abstract_renderer
;
1074 cairo_fixed_t top
, bot
;
1077 return CAIRO_STATUS_SUCCESS
;
1079 top
= _cairo_fixed_from_int (y
);
1080 bot
= _cairo_fixed_from_int (y
+ h
);
1082 if (spans
[0].coverage
) {
1083 cairo_fixed_t x0
= _cairo_fixed_from_int(spans
[0].x
);
1084 cairo_fixed_t x1
= _cairo_fixed_from_int(spans
[1].x
);
1085 cairo_line_t left
= { { x0
, top
}, { x0
, bot
} },
1086 right
= { { x1
, top
}, { x1
, bot
} };
1087 _cairo_traps_add_trap (r
->traps
, top
, bot
, &left
, &right
);
1090 } while (--num_spans
> 1);
1092 return CAIRO_STATUS_SUCCESS
;
1096 _cairo_rasterise_polygon_to_traps (cairo_polygon_t
*polygon
,
1097 cairo_fill_rule_t fill_rule
,
1098 cairo_antialias_t antialias
,
1099 cairo_traps_t
*traps
)
1101 struct cairo_trap_renderer renderer
;
1102 cairo_scan_converter_t
*converter
;
1103 cairo_int_status_t status
;
1104 cairo_rectangle_int_t r
;
1106 TRACE ((stderr
, "%s: fill_rule=%d, antialias=%d\n",
1107 __FUNCTION__
, fill_rule
, antialias
));
1108 assert(antialias
== CAIRO_ANTIALIAS_NONE
);
1110 renderer
.traps
= traps
;
1111 renderer
.base
.render_rows
= span_to_traps
;
1113 _cairo_box_round_to_rectangle (&polygon
->extents
, &r
);
1114 converter
= _cairo_mono_scan_converter_create (r
.x
, r
.y
,
1118 status
= _cairo_mono_scan_converter_add_polygon (converter
, polygon
);
1119 if (likely (status
== CAIRO_INT_STATUS_SUCCESS
))
1120 status
= converter
->generate (converter
, &renderer
.base
);
1121 converter
->destroy (converter
);