Line data Source code
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
52 0 : _cairo_in_fill_init (cairo_in_fill_t *in_fill,
53 : double tolerance,
54 : double x,
55 : double y)
56 : {
57 0 : in_fill->on_edge = FALSE;
58 0 : in_fill->winding = 0;
59 0 : in_fill->tolerance = tolerance;
60 :
61 0 : in_fill->x = _cairo_fixed_from_double (x);
62 0 : in_fill->y = _cairo_fixed_from_double (y);
63 :
64 0 : in_fill->has_current_point = FALSE;
65 0 : in_fill->current_point.x = 0;
66 0 : in_fill->current_point.y = 0;
67 0 : }
68 :
69 : static void
70 0 : _cairo_in_fill_fini (cairo_in_fill_t *in_fill)
71 : {
72 0 : }
73 :
74 : static int
75 0 : 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 0 : adx = p2->x - p1->x;
85 0 : dx = x - p1->x;
86 :
87 0 : if (adx == 0)
88 0 : return -dx;
89 0 : if ((adx ^ dx) < 0)
90 0 : return adx;
91 :
92 0 : dy = y - p1->y;
93 0 : ady = p2->y - p1->y;
94 :
95 0 : L = _cairo_int32x32_64_mul (dy, adx);
96 0 : R = _cairo_int32x32_64_mul (dx, ady);
97 :
98 0 : return _cairo_int64_cmp (L, R);
99 : }
100 :
101 : static void
102 0 : _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 0 : if (in_fill->on_edge)
109 0 : return;
110 :
111 : /* count the number of edge crossing to -∞ */
112 :
113 0 : dir = 1;
114 0 : if (p2->y < p1->y) {
115 : const cairo_point_t *tmp;
116 :
117 0 : tmp = p1;
118 0 : p1 = p2;
119 0 : p2 = tmp;
120 :
121 0 : dir = -1;
122 : }
123 :
124 : /* First check whether the query is on an edge */
125 0 : if ((p1->x == in_fill->x && p1->y == in_fill->y) ||
126 0 : (p2->x == in_fill->x && p2->y == in_fill->y) ||
127 0 : (! (p2->y < in_fill->y || p1->y > in_fill->y ||
128 0 : (p1->x > in_fill->x && p2->x > in_fill->x) ||
129 0 : (p1->x < in_fill->x && p2->x < in_fill->x)) &&
130 0 : edge_compare_for_y_against_x (p1, p2, in_fill->y, in_fill->x) == 0))
131 : {
132 0 : in_fill->on_edge = TRUE;
133 0 : return;
134 : }
135 :
136 : /* edge is entirely above or below, note the shortening rule */
137 0 : if (p2->y <= in_fill->y || p1->y > in_fill->y)
138 0 : return;
139 :
140 : /* edge lies wholly to the right */
141 0 : if (p1->x >= in_fill->x && p2->x >= in_fill->x)
142 0 : return;
143 :
144 0 : if ((p1->x <= in_fill->x && p2->x <= in_fill->x) ||
145 0 : edge_compare_for_y_against_x (p1, p2, in_fill->y, in_fill->x) < 0)
146 : {
147 0 : in_fill->winding += dir;
148 : }
149 : }
150 :
151 : static cairo_status_t
152 0 : _cairo_in_fill_move_to (void *closure,
153 : const cairo_point_t *point)
154 : {
155 0 : cairo_in_fill_t *in_fill = closure;
156 :
157 : /* implicit close path */
158 0 : if (in_fill->has_current_point) {
159 0 : _cairo_in_fill_add_edge (in_fill,
160 0 : &in_fill->current_point,
161 0 : &in_fill->first_point);
162 : }
163 :
164 0 : in_fill->first_point = *point;
165 0 : in_fill->current_point = *point;
166 0 : in_fill->has_current_point = TRUE;
167 :
168 0 : return CAIRO_STATUS_SUCCESS;
169 : }
170 :
171 : static cairo_status_t
172 0 : _cairo_in_fill_line_to (void *closure,
173 : const cairo_point_t *point)
174 : {
175 0 : cairo_in_fill_t *in_fill = closure;
176 :
177 0 : if (in_fill->has_current_point)
178 0 : _cairo_in_fill_add_edge (in_fill, &in_fill->current_point, point);
179 :
180 0 : in_fill->current_point = *point;
181 0 : in_fill->has_current_point = TRUE;
182 :
183 0 : return CAIRO_STATUS_SUCCESS;
184 : }
185 :
186 : static cairo_status_t
187 0 : _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 0 : 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 0 : bot = top = in_fill->current_point.y;
198 0 : if (b->y < top) top = b->y;
199 0 : if (b->y > bot) bot = b->y;
200 0 : if (c->y < top) top = c->y;
201 0 : if (c->y > bot) bot = c->y;
202 0 : if (d->y < top) top = d->y;
203 0 : if (d->y > bot) bot = d->y;
204 0 : if (bot < in_fill->y || top > in_fill->y) {
205 0 : in_fill->current_point = *d;
206 0 : return CAIRO_STATUS_SUCCESS;
207 : }
208 :
209 0 : left = in_fill->current_point.x;
210 0 : if (b->x < left) left = b->x;
211 0 : if (c->x < left) left = c->x;
212 0 : if (d->x < left) left = d->x;
213 0 : if (left > in_fill->x) {
214 0 : in_fill->current_point = *d;
215 0 : return CAIRO_STATUS_SUCCESS;
216 : }
217 :
218 : /* XXX Investigate direct inspection of the inflections? */
219 0 : if (! _cairo_spline_init (&spline,
220 : _cairo_in_fill_line_to,
221 : in_fill,
222 0 : &in_fill->current_point, b, c, d))
223 : {
224 0 : return CAIRO_STATUS_SUCCESS;
225 : }
226 :
227 0 : return _cairo_spline_decompose (&spline, in_fill->tolerance);
228 : }
229 :
230 : static cairo_status_t
231 0 : _cairo_in_fill_close_path (void *closure)
232 : {
233 0 : cairo_in_fill_t *in_fill = closure;
234 :
235 0 : if (in_fill->has_current_point) {
236 0 : _cairo_in_fill_add_edge (in_fill,
237 0 : &in_fill->current_point,
238 0 : &in_fill->first_point);
239 :
240 0 : in_fill->has_current_point = FALSE;
241 : }
242 :
243 0 : return CAIRO_STATUS_SUCCESS;
244 : }
245 :
246 : cairo_bool_t
247 0 : _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 0 : if (path->is_empty_fill)
258 0 : return FALSE;
259 :
260 0 : _cairo_in_fill_init (&in_fill, tolerance, x, y);
261 :
262 0 : status = _cairo_path_fixed_interpret (path,
263 : CAIRO_DIRECTION_FORWARD,
264 : _cairo_in_fill_move_to,
265 : _cairo_in_fill_line_to,
266 : _cairo_in_fill_curve_to,
267 : _cairo_in_fill_close_path,
268 : &in_fill);
269 0 : assert (status == CAIRO_STATUS_SUCCESS);
270 :
271 0 : _cairo_in_fill_close_path (&in_fill);
272 :
273 0 : if (in_fill.on_edge) {
274 0 : is_inside = TRUE;
275 0 : } else switch (fill_rule) {
276 : case CAIRO_FILL_RULE_EVEN_ODD:
277 0 : is_inside = in_fill.winding & 1;
278 0 : break;
279 : case CAIRO_FILL_RULE_WINDING:
280 0 : is_inside = in_fill.winding != 0;
281 0 : break;
282 : default:
283 0 : ASSERT_NOT_REACHED;
284 0 : is_inside = FALSE;
285 0 : break;
286 : }
287 :
288 0 : _cairo_in_fill_fini (&in_fill);
289 :
290 0 : return is_inside;
291 : }
|
