1 /* cairo - a vector graphics library with display and print output
3 * Copyright © 2008 Chris Wilson
5 * This library is free software; you can redistribute it and/or
6 * modify it either under the terms of the GNU Lesser General Public
7 * License version 2.1 as published by the Free Software Foundation
8 * (the "LGPL") or, at your option, under the terms of the Mozilla
9 * Public License Version 1.1 (the "MPL"). If you do not alter this
10 * notice, a recipient may use your version of this file under either
11 * the MPL or the LGPL.
13 * You should have received a copy of the LGPL along with this library
14 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
16 * You should have received a copy of the MPL along with this library
17 * in the file COPYING-MPL-1.1
19 * The contents of this file are subject to the Mozilla Public License
20 * Version 1.1 (the "License"); you may not use this file except in
21 * compliance with the License. You may obtain a copy of the License at
22 * http://www.mozilla.org/MPL/
24 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
25 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
26 * the specific language governing rights and limitations.
28 * The Original Code is the cairo graphics library.
30 * The Initial Developer of the Original Code is Chris Wilson.
33 * Chris Wilson <chris@chris-wilson.co.uk>
37 #include "cairo-path-fixed-private.h"
39 typedef struct cairo_in_fill
{
46 cairo_bool_t has_current_point
;
47 cairo_point_t current_point
;
48 cairo_point_t first_point
;
52 _cairo_in_fill_init (cairo_in_fill_t
*in_fill
,
57 in_fill
->on_edge
= FALSE
;
59 in_fill
->tolerance
= tolerance
;
61 in_fill
->x
= _cairo_fixed_from_double (x
);
62 in_fill
->y
= _cairo_fixed_from_double (y
);
64 in_fill
->has_current_point
= FALSE
;
65 in_fill
->current_point
.x
= 0;
66 in_fill
->current_point
.y
= 0;
70 _cairo_in_fill_fini (cairo_in_fill_t
*in_fill
)
75 edge_compare_for_y_against_x (const cairo_point_t
*p1
,
76 const cairo_point_t
*p2
,
80 cairo_fixed_t adx
, ady
;
95 L
= _cairo_int32x32_64_mul (dy
, adx
);
96 R
= _cairo_int32x32_64_mul (dx
, ady
);
98 return _cairo_int64_cmp (L
, R
);
102 _cairo_in_fill_add_edge (cairo_in_fill_t
*in_fill
,
103 const cairo_point_t
*p1
,
104 const cairo_point_t
*p2
)
108 if (in_fill
->on_edge
)
111 /* count the number of edge crossing to -∞ */
115 const cairo_point_t
*tmp
;
124 /* First check whether the query is on an edge */
125 if ((p1
->x
== in_fill
->x
&& p1
->y
== in_fill
->y
) ||
126 (p2
->x
== in_fill
->x
&& p2
->y
== in_fill
->y
) ||
127 (! (p2
->y
< in_fill
->y
|| p1
->y
> in_fill
->y
||
128 (p1
->x
> in_fill
->x
&& p2
->x
> in_fill
->x
) ||
129 (p1
->x
< in_fill
->x
&& p2
->x
< in_fill
->x
)) &&
130 edge_compare_for_y_against_x (p1
, p2
, in_fill
->y
, in_fill
->x
) == 0))
132 in_fill
->on_edge
= TRUE
;
136 /* edge is entirely above or below, note the shortening rule */
137 if (p2
->y
<= in_fill
->y
|| p1
->y
> in_fill
->y
)
140 /* edge lies wholly to the right */
141 if (p1
->x
>= in_fill
->x
&& p2
->x
>= in_fill
->x
)
144 if ((p1
->x
<= in_fill
->x
&& p2
->x
<= in_fill
->x
) ||
145 edge_compare_for_y_against_x (p1
, p2
, in_fill
->y
, in_fill
->x
) < 0)
147 in_fill
->winding
+= dir
;
151 static cairo_status_t
152 _cairo_in_fill_move_to (void *closure
,
153 const cairo_point_t
*point
)
155 cairo_in_fill_t
*in_fill
= closure
;
157 /* implicit close path */
158 if (in_fill
->has_current_point
) {
159 _cairo_in_fill_add_edge (in_fill
,
160 &in_fill
->current_point
,
161 &in_fill
->first_point
);
164 in_fill
->first_point
= *point
;
165 in_fill
->current_point
= *point
;
166 in_fill
->has_current_point
= TRUE
;
168 return CAIRO_STATUS_SUCCESS
;
171 static cairo_status_t
172 _cairo_in_fill_line_to (void *closure
,
173 const cairo_point_t
*point
)
175 cairo_in_fill_t
*in_fill
= closure
;
177 if (in_fill
->has_current_point
)
178 _cairo_in_fill_add_edge (in_fill
, &in_fill
->current_point
, point
);
180 in_fill
->current_point
= *point
;
181 in_fill
->has_current_point
= TRUE
;
183 return CAIRO_STATUS_SUCCESS
;
186 static cairo_status_t
187 _cairo_in_fill_curve_to (void *closure
,
188 const cairo_point_t
*b
,
189 const cairo_point_t
*c
,
190 const cairo_point_t
*d
)
192 cairo_in_fill_t
*in_fill
= closure
;
193 cairo_spline_t spline
;
194 cairo_fixed_t top
, bot
, left
;
196 /* first reject based on bbox */
197 bot
= top
= in_fill
->current_point
.y
;
198 if (b
->y
< top
) top
= b
->y
;
199 if (b
->y
> bot
) bot
= b
->y
;
200 if (c
->y
< top
) top
= c
->y
;
201 if (c
->y
> bot
) bot
= c
->y
;
202 if (d
->y
< top
) top
= d
->y
;
203 if (d
->y
> bot
) bot
= d
->y
;
204 if (bot
< in_fill
->y
|| top
> in_fill
->y
) {
205 in_fill
->current_point
= *d
;
206 return CAIRO_STATUS_SUCCESS
;
209 left
= in_fill
->current_point
.x
;
210 if (b
->x
< left
) left
= b
->x
;
211 if (c
->x
< left
) left
= c
->x
;
212 if (d
->x
< left
) left
= d
->x
;
213 if (left
> in_fill
->x
) {
214 in_fill
->current_point
= *d
;
215 return CAIRO_STATUS_SUCCESS
;
218 /* XXX Investigate direct inspection of the inflections? */
219 if (! _cairo_spline_init (&spline
,
220 (cairo_spline_add_point_func_t
)_cairo_in_fill_line_to
,
222 &in_fill
->current_point
, b
, c
, d
))
224 return CAIRO_STATUS_SUCCESS
;
227 return _cairo_spline_decompose (&spline
, in_fill
->tolerance
);
230 static cairo_status_t
231 _cairo_in_fill_close_path (void *closure
)
233 cairo_in_fill_t
*in_fill
= closure
;
235 if (in_fill
->has_current_point
) {
236 _cairo_in_fill_add_edge (in_fill
,
237 &in_fill
->current_point
,
238 &in_fill
->first_point
);
240 in_fill
->has_current_point
= FALSE
;
243 return CAIRO_STATUS_SUCCESS
;
247 _cairo_path_fixed_in_fill (const cairo_path_fixed_t
*path
,
248 cairo_fill_rule_t fill_rule
,
253 cairo_in_fill_t in_fill
;
254 cairo_status_t status
;
255 cairo_bool_t is_inside
;
257 if (_cairo_path_fixed_fill_is_empty (path
))
260 _cairo_in_fill_init (&in_fill
, tolerance
, x
, y
);
262 status
= _cairo_path_fixed_interpret (path
,
263 _cairo_in_fill_move_to
,
264 _cairo_in_fill_line_to
,
265 _cairo_in_fill_curve_to
,
266 _cairo_in_fill_close_path
,
268 assert (status
== CAIRO_STATUS_SUCCESS
);
270 _cairo_in_fill_close_path (&in_fill
);
272 if (in_fill
.on_edge
) {
274 } else switch (fill_rule
) {
275 case CAIRO_FILL_RULE_EVEN_ODD
:
276 is_inside
= in_fill
.winding
& 1;
278 case CAIRO_FILL_RULE_WINDING
:
279 is_inside
= in_fill
.winding
!= 0;
287 _cairo_in_fill_fini (&in_fill
);