1 /* cairo - a vector graphics library with display and print output
2 *
3 * Copyright © 2008 Chris Wilson
4 *
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.
12 *
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
18 *
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/
23 *
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.
27 *
28 * The Original Code is the cairo graphics library.
29 *
30 * The Initial Developer of the Original Code is Chris Wilson.
31 *
32 * Contributor(s):
33 * Chris Wilson <chris@chris-wilson.co.uk>
34 */
35
36 #include "cairoint.h"
37 #include "cairo-path-fixed-private.h"
38
39 typedef struct cairo_in_fill {
40 double tolerance;
41 cairo_bool_t on_edge;
42 int winding;
43
44 cairo_fixed_t x, y;
45
46 cairo_bool_t has_current_point;
47 cairo_point_t current_point;
48 cairo_point_t first_point;
49 } cairo_in_fill_t;
50
51 static void
_cairo_in_fill_init(cairo_in_fill_t * in_fill,double tolerance,double x,double y)52 _cairo_in_fill_init (cairo_in_fill_t *in_fill,
53 double tolerance,
54 double x,
55 double y)
56 {
57 in_fill->on_edge = FALSE;
58 in_fill->winding = 0;
59 in_fill->tolerance = tolerance;
60
61 in_fill->x = _cairo_fixed_from_double (x);
62 in_fill->y = _cairo_fixed_from_double (y);
63
64 in_fill->has_current_point = FALSE;
65 in_fill->current_point.x = 0;
66 in_fill->current_point.y = 0;
67 }
68
69 static void
_cairo_in_fill_fini(cairo_in_fill_t * in_fill)70 _cairo_in_fill_fini (cairo_in_fill_t *in_fill)
71 {
72 }
73
74 static int
edge_compare_for_y_against_x(const cairo_point_t * p1,const cairo_point_t * p2,cairo_fixed_t y,cairo_fixed_t x)75 edge_compare_for_y_against_x (const cairo_point_t *p1,
76 const cairo_point_t *p2,
77 cairo_fixed_t y,
78 cairo_fixed_t x)
79 {
80 cairo_fixed_t adx, ady;
81 cairo_fixed_t dx, dy;
82 cairo_int64_t L, R;
83
84 adx = p2->x - p1->x;
85 dx = x - p1->x;
86
87 if (adx == 0)
88 return -dx;
89 if ((adx ^ dx) < 0)
90 return adx;
91
92 dy = y - p1->y;
93 ady = p2->y - p1->y;
94
95 L = _cairo_int32x32_64_mul (dy, adx);
96 R = _cairo_int32x32_64_mul (dx, ady);
97
98 return _cairo_int64_cmp (L, R);
99 }
100
101 static void
_cairo_in_fill_add_edge(cairo_in_fill_t * in_fill,const cairo_point_t * p1,const cairo_point_t * p2)102 _cairo_in_fill_add_edge (cairo_in_fill_t *in_fill,
103 const cairo_point_t *p1,
104 const cairo_point_t *p2)
105 {
106 int dir;
107
108 if (in_fill->on_edge)
109 return;
110
111 /* count the number of edge crossing to -∞ */
112
113 dir = 1;
114 if (p2->y < p1->y) {
115 const cairo_point_t *tmp;
116
117 tmp = p1;
118 p1 = p2;
119 p2 = tmp;
120
121 dir = -1;
122 }
123
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))
131 {
132 in_fill->on_edge = TRUE;
133 return;
134 }
135
136 /* edge is entirely above or below, note the shortening rule */
137 if (p2->y <= in_fill->y || p1->y > in_fill->y)
138 return;
139
140 /* edge lies wholly to the right */
141 if (p1->x >= in_fill->x && p2->x >= in_fill->x)
142 return;
143
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)
146 {
147 in_fill->winding += dir;
148 }
149 }
150
151 static cairo_status_t
_cairo_in_fill_move_to(void * closure,const cairo_point_t * point)152 _cairo_in_fill_move_to (void *closure,
153 const cairo_point_t *point)
154 {
155 cairo_in_fill_t *in_fill = closure;
156
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);
162 }
163
164 in_fill->first_point = *point;
165 in_fill->current_point = *point;
166 in_fill->has_current_point = TRUE;
167
168 return CAIRO_STATUS_SUCCESS;
169 }
170
171 static cairo_status_t
_cairo_in_fill_line_to(void * closure,const cairo_point_t * point)172 _cairo_in_fill_line_to (void *closure,
173 const cairo_point_t *point)
174 {
175 cairo_in_fill_t *in_fill = closure;
176
177 if (in_fill->has_current_point)
178 _cairo_in_fill_add_edge (in_fill, &in_fill->current_point, point);
179
180 in_fill->current_point = *point;
181 in_fill->has_current_point = TRUE;
182
183 return CAIRO_STATUS_SUCCESS;
184 }
185
186 static cairo_status_t
_cairo_in_fill_curve_to(void * closure,const cairo_point_t * b,const cairo_point_t * c,const cairo_point_t * d)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)
191 {
192 cairo_in_fill_t *in_fill = closure;
193 cairo_spline_t spline;
194 cairo_fixed_t top, bot, left;
195
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;
207 }
208
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;
216 }
217
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,
221 in_fill,
222 &in_fill->current_point, b, c, d))
223 {
224 return CAIRO_STATUS_SUCCESS;
225 }
226
227 return _cairo_spline_decompose (&spline, in_fill->tolerance);
228 }
229
230 static cairo_status_t
_cairo_in_fill_close_path(void * closure)231 _cairo_in_fill_close_path (void *closure)
232 {
233 cairo_in_fill_t *in_fill = closure;
234
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);
239
240 in_fill->has_current_point = FALSE;
241 }
242
243 return CAIRO_STATUS_SUCCESS;
244 }
245
246 cairo_bool_t
_cairo_path_fixed_in_fill(const cairo_path_fixed_t * path,cairo_fill_rule_t fill_rule,double tolerance,double x,double y)247 _cairo_path_fixed_in_fill (const cairo_path_fixed_t *path,
248 cairo_fill_rule_t fill_rule,
249 double tolerance,
250 double x,
251 double y)
252 {
253 cairo_in_fill_t in_fill;
254 cairo_status_t status;
255 cairo_bool_t is_inside;
256
257 if (_cairo_path_fixed_fill_is_empty (path))
258 return FALSE;
259
260 _cairo_in_fill_init (&in_fill, tolerance, x, y);
261
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,
267 &in_fill);
268 assert (status == CAIRO_STATUS_SUCCESS);
269
270 _cairo_in_fill_close_path (&in_fill);
271
272 if (in_fill.on_edge) {
273 is_inside = TRUE;
274 } else switch (fill_rule) {
275 case CAIRO_FILL_RULE_EVEN_ODD:
276 is_inside = in_fill.winding & 1;
277 break;
278 case CAIRO_FILL_RULE_WINDING:
279 is_inside = in_fill.winding != 0;
280 break;
281 default:
282 ASSERT_NOT_REACHED;
283 is_inside = FALSE;
284 break;
285 }
286
287 _cairo_in_fill_fini (&in_fill);
288
289 return is_inside;
290 }
291