Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
14952 fschmid 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
18122 mrdocs 15
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
14952 fschmid 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
_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,
220
                              _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
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
 
257
    if (path->is_empty_fill)
258
        return FALSE;
259
 
260
    _cairo_in_fill_init (&in_fill, tolerance, x, y);
261
 
262
    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
    assert (status == CAIRO_STATUS_SUCCESS);
270
 
271
    _cairo_in_fill_close_path (&in_fill);
272
 
273
    if (in_fill.on_edge) {
274
        is_inside = TRUE;
275
    } else switch (fill_rule) {
276
    case CAIRO_FILL_RULE_EVEN_ODD:
277
        is_inside = in_fill.winding & 1;
278
        break;
279
    case CAIRO_FILL_RULE_WINDING:
280
        is_inside = in_fill.winding != 0;
281
        break;
282
    default:
283
        ASSERT_NOT_REACHED;
284
        is_inside = FALSE;
285
        break;
286
    }
287
 
288
    _cairo_in_fill_fini (&in_fill);
289
 
290
    return is_inside;
291
}