Rev 1892 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1892 | serge | 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 |
||
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 | _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 |
||
70 | _cairo_in_fill_fini (cairo_in_fill_t *in_fill) |
||
71 | { |
||
72 | } |
||
73 | |||
74 | static int |
||
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 |
||
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 |
||
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 |
||
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 |
||
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, |
||
3959 | Serge | 220 | (cairo_spline_add_point_func_t)_cairo_in_fill_line_to, |
1892 | serge | 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 |
||
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 |
||
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 | |||
3959 | Serge | 257 | if (_cairo_path_fixed_fill_is_empty (path)) |
1892 | serge | 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 | }>>>>>>>>=>=>=>>>>>> |