1
/* -*- Mode: c; c-basic-offset: 4; indent-tabs-mode: t; tab-width: 8; -*- */
2
/* cairo - a vector graphics library with display and print output
3
 *
4
 * Copyright © 2002 University of Southern California
5
 *
6
 * This library is free software; you can redistribute it and/or
7
 * modify it either under the terms of the GNU Lesser General Public
8
 * License version 2.1 as published by the Free Software Foundation
9
 * (the "LGPL") or, at your option, under the terms of the Mozilla
10
 * Public License Version 1.1 (the "MPL"). If you do not alter this
11
 * notice, a recipient may use your version of this file under either
12
 * the MPL or the LGPL.
13
 *
14
 * You should have received a copy of the LGPL along with this library
15
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16
 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17
 * You should have received a copy of the MPL along with this library
18
 * in the file COPYING-MPL-1.1
19
 *
20
 * The contents of this file are subject to the Mozilla Public License
21
 * Version 1.1 (the "License"); you may not use this file except in
22
 * compliance with the License. You may obtain a copy of the License at
23
 * http://www.mozilla.org/MPL/
24
 *
25
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27
 * the specific language governing rights and limitations.
28
 *
29
 * The Original Code is the cairo graphics library.
30
 *
31
 * The Initial Developer of the Original Code is University of Southern
32
 * California.
33
 *
34
 * Contributor(s):
35
 *	Carl D. Worth <cworth@cworth.org>
36
 */
37

            
38
#include "cairoint.h"
39
#include "cairo-boxes-private.h"
40
#include "cairo-error-private.h"
41
#include "cairo-path-fixed-private.h"
42
#include "cairo-region-private.h"
43
#include "cairo-traps-private.h"
44

            
45
typedef struct cairo_filler {
46
    cairo_polygon_t *polygon;
47
    double tolerance;
48

            
49
    cairo_box_t limit;
50
    cairo_bool_t has_limits;
51

            
52
    cairo_point_t current_point;
53
    cairo_point_t last_move_to;
54
} cairo_filler_t;
55

            
56
static cairo_status_t
57
133620249
_cairo_filler_line_to (void *closure,
58
		       const cairo_point_t *point)
59
{
60
133620249
    cairo_filler_t *filler = closure;
61
    cairo_status_t status;
62

            
63
133620249
    status = _cairo_polygon_add_external_edge (filler->polygon,
64
133620249
					       &filler->current_point,
65
					       point);
66

            
67
133620249
    filler->current_point = *point;
68

            
69
133620249
    return status;
70
}
71

            
72
static cairo_status_t
73
563436
_cairo_filler_add_point (void *closure,
74
			 const cairo_point_t *point,
75
			 const cairo_slope_t *tangent)
76
{
77
563436
    return _cairo_filler_line_to (closure, point);
78
};
79

            
80
static cairo_status_t
81
53294088
_cairo_filler_close (void *closure)
82
{
83
53294088
    cairo_filler_t *filler = closure;
84

            
85
    /* close the subpath */
86
53294088
    return _cairo_filler_line_to (closure, &filler->last_move_to);
87
}
88

            
89
static cairo_status_t
90
26673252
_cairo_filler_move_to (void *closure,
91
		       const cairo_point_t *point)
92
{
93
26673252
    cairo_filler_t *filler = closure;
94
    cairo_status_t status;
95

            
96
    /* close current subpath */
97
26673252
    status = _cairo_filler_close (closure);
98
26673252
    if (unlikely (status))
99
	return status;
100

            
101
        /* make sure that the closure represents a degenerate path */
102
26673252
    filler->current_point = *point;
103
26673252
    filler->last_move_to = *point;
104

            
105
26673252
    return CAIRO_STATUS_SUCCESS;
106
}
107

            
108
static cairo_status_t
109
94896
_cairo_filler_curve_to (void		*closure,
110
			const cairo_point_t	*p1,
111
			const cairo_point_t	*p2,
112
			const cairo_point_t	*p3)
113
{
114
94896
    cairo_filler_t *filler = closure;
115
    cairo_spline_t spline;
116

            
117
94896
    if (filler->has_limits) {
118
79422
	if (! _cairo_spline_intersects (&filler->current_point, p1, p2, p3,
119
79422
					&filler->limit))
120
49620
	    return _cairo_filler_line_to (filler, p3);
121
    }
122

            
123
45276
    if (! _cairo_spline_init (&spline,
124
			      _cairo_filler_add_point, filler,
125
45276
			      &filler->current_point, p1, p2, p3))
126
    {
127
	return _cairo_filler_line_to (closure, p3);
128
    }
129

            
130
45276
    return _cairo_spline_decompose (&spline, filler->tolerance);
131
}
132

            
133
cairo_status_t
134
161526
_cairo_path_fixed_fill_to_polygon (const cairo_path_fixed_t *path,
135
				   double tolerance,
136
				   cairo_polygon_t *polygon)
137
{
138
    cairo_filler_t filler;
139
    cairo_status_t status;
140

            
141
161526
    filler.polygon = polygon;
142
161526
    filler.tolerance = tolerance;
143

            
144
161526
    filler.has_limits = FALSE;
145
161526
    if (polygon->num_limits) {
146
54715
	filler.has_limits = TRUE;
147
54715
	filler.limit = polygon->limit;
148
    }
149

            
150
    /* make sure that the closure represents a degenerate path */
151
161526
    filler.current_point.x = 0;
152
161526
    filler.current_point.y = 0;
153
161526
    filler.last_move_to = filler.current_point;
154

            
155
161526
    status = _cairo_path_fixed_interpret (path,
156
					  _cairo_filler_move_to,
157
					  _cairo_filler_line_to,
158
					  _cairo_filler_curve_to,
159
					  _cairo_filler_close,
160
					  &filler);
161
161526
    if (unlikely (status))
162
	return status;
163

            
164
161526
    return _cairo_filler_close (&filler);
165
}
166

            
167
typedef struct cairo_filler_rectilinear_aligned {
168
    cairo_polygon_t *polygon;
169

            
170
    cairo_point_t current_point;
171
    cairo_point_t last_move_to;
172
} cairo_filler_ra_t;
173

            
174
static cairo_status_t
175
54
_cairo_filler_ra_line_to (void *closure,
176
			  const cairo_point_t *point)
177
{
178
54
    cairo_filler_ra_t *filler = closure;
179
    cairo_status_t status;
180
    cairo_point_t p;
181

            
182
54
    p.x = _cairo_fixed_round_down (point->x);
183
54
    p.y = _cairo_fixed_round_down (point->y);
184

            
185
54
    status = _cairo_polygon_add_external_edge (filler->polygon,
186
54
					       &filler->current_point,
187
					       &p);
188

            
189
54
    filler->current_point = p;
190

            
191
54
    return status;
192
}
193

            
194
static cairo_status_t
195
24
_cairo_filler_ra_close (void *closure)
196
{
197
24
    cairo_filler_ra_t *filler = closure;
198
24
    return _cairo_filler_ra_line_to (closure, &filler->last_move_to);
199
}
200

            
201
static cairo_status_t
202
12
_cairo_filler_ra_move_to (void *closure,
203
			  const cairo_point_t *point)
204
{
205
12
    cairo_filler_ra_t *filler = closure;
206
    cairo_status_t status;
207
    cairo_point_t p;
208

            
209
    /* close current subpath */
210
12
    status = _cairo_filler_ra_close (closure);
211
12
    if (unlikely (status))
212
	return status;
213

            
214
12
    p.x = _cairo_fixed_round_down (point->x);
215
12
    p.y = _cairo_fixed_round_down (point->y);
216

            
217
    /* make sure that the closure represents a degenerate path */
218
12
    filler->current_point = p;
219
12
    filler->last_move_to = p;
220

            
221
12
    return CAIRO_STATUS_SUCCESS;
222
}
223

            
224
cairo_status_t
225
42
_cairo_path_fixed_fill_rectilinear_to_polygon (const cairo_path_fixed_t *path,
226
					       cairo_antialias_t antialias,
227
					       cairo_polygon_t *polygon)
228
{
229
    cairo_filler_ra_t filler;
230
    cairo_status_t status;
231

            
232
42
    if (antialias != CAIRO_ANTIALIAS_NONE)
233
36
	return _cairo_path_fixed_fill_to_polygon (path, 0., polygon);
234

            
235
6
    filler.polygon = polygon;
236

            
237
    /* make sure that the closure represents a degenerate path */
238
6
    filler.current_point.x = 0;
239
6
    filler.current_point.y = 0;
240
6
    filler.last_move_to = filler.current_point;
241

            
242
6
    status = _cairo_path_fixed_interpret_flat (path,
243
					       _cairo_filler_ra_move_to,
244
					       _cairo_filler_ra_line_to,
245
					       _cairo_filler_ra_close,
246
					       &filler,
247
					       0.);
248
6
    if (unlikely (status))
249
	return status;
250

            
251
6
    return _cairo_filler_ra_close (&filler);
252
}
253

            
254
cairo_status_t
255
6
_cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
256
				 cairo_fill_rule_t fill_rule,
257
				 double tolerance,
258
				 cairo_traps_t *traps)
259
{
260
    cairo_polygon_t polygon;
261
    cairo_status_t status;
262

            
263
6
    if (_cairo_path_fixed_fill_is_empty (path))
264
	return CAIRO_STATUS_SUCCESS;
265

            
266
6
    _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
267
6
    status = _cairo_path_fixed_fill_to_polygon (path, tolerance, &polygon);
268
6
    if (unlikely (status || polygon.num_edges == 0))
269
	goto CLEANUP;
270

            
271
6
    status = _cairo_bentley_ottmann_tessellate_polygon (traps,
272
							&polygon, fill_rule);
273

            
274
6
  CLEANUP:
275
6
    _cairo_polygon_fini (&polygon);
276
6
    return status;
277
}
278

            
279
static cairo_status_t
280
42
_cairo_path_fixed_fill_rectilinear_tessellate_to_boxes (const cairo_path_fixed_t *path,
281
							cairo_fill_rule_t fill_rule,
282
							cairo_antialias_t antialias,
283
							cairo_boxes_t *boxes)
284
{
285
    cairo_polygon_t polygon;
286
    cairo_status_t status;
287

            
288
42
    _cairo_polygon_init (&polygon, boxes->limits, boxes->num_limits);
289
42
    boxes->num_limits = 0;
290

            
291
    /* tolerance will be ignored as the path is rectilinear */
292
42
    status = _cairo_path_fixed_fill_rectilinear_to_polygon (path, antialias, &polygon);
293
42
    if (likely (status == CAIRO_STATUS_SUCCESS)) {
294
	status =
295
42
	    _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (&polygon,
296
									    fill_rule,
297
									    boxes);
298
    }
299

            
300
42
    _cairo_polygon_fini (&polygon);
301

            
302
42
    return status;
303
}
304

            
305
cairo_status_t
306
340894
_cairo_path_fixed_fill_rectilinear_to_boxes (const cairo_path_fixed_t *path,
307
					     cairo_fill_rule_t fill_rule,
308
					     cairo_antialias_t antialias,
309
					     cairo_boxes_t *boxes)
310
{
311
    cairo_path_fixed_iter_t iter;
312
    cairo_status_t status;
313
    cairo_box_t box;
314

            
315
340894
    if (_cairo_path_fixed_is_box (path, &box))
316
338124
	return _cairo_boxes_add (boxes, antialias, &box);
317

            
318
2770
    _cairo_path_fixed_iter_init (&iter, path);
319
272814
    while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
320
270044
	if (box.p1.y == box.p2.y || box.p1.x == box.p2.x)
321
202800
	    continue;
322

            
323
67244
	if (box.p1.y > box.p2.y) {
324
	    cairo_fixed_t t;
325

            
326
435
	    t = box.p1.y;
327
435
	    box.p1.y = box.p2.y;
328
435
	    box.p2.y = t;
329

            
330
435
	    t = box.p1.x;
331
435
	    box.p1.x = box.p2.x;
332
435
	    box.p2.x = t;
333
	}
334

            
335
67244
	status = _cairo_boxes_add (boxes, antialias, &box);
336
67244
	if (unlikely (status))
337
	    return status;
338
    }
339

            
340
2770
    if (_cairo_path_fixed_iter_at_end (&iter))
341
2728
	return _cairo_bentley_ottmann_tessellate_boxes (boxes, fill_rule, boxes);
342

            
343
    /* path is not rectangular, try extracting clipped rectilinear edges */
344
42
    _cairo_boxes_clear (boxes);
345
42
    return _cairo_path_fixed_fill_rectilinear_tessellate_to_boxes (path,
346
								   fill_rule,
347
								   antialias,
348
								   boxes);
349
}