Line data Source code
1 : /* cairo - a vector graphics library with display and print output
2 : *
3 : * Copyright © 2002 University of Southern California
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 University of Southern
31 : * California.
32 : *
33 : * Contributor(s):
34 : * Carl D. Worth <cworth@cworth.org>
35 : */
36 :
37 : #include "cairoint.h"
38 : #include "cairo-boxes-private.h"
39 : #include "cairo-error-private.h"
40 : #include "cairo-path-fixed-private.h"
41 : #include "cairo-region-private.h"
42 :
43 : typedef struct cairo_filler {
44 : double tolerance;
45 : cairo_polygon_t *polygon;
46 : } cairo_filler_t;
47 :
48 : static void
49 0 : _cairo_filler_init (cairo_filler_t *filler,
50 : double tolerance,
51 : cairo_polygon_t *polygon)
52 : {
53 0 : filler->tolerance = tolerance;
54 0 : filler->polygon = polygon;
55 0 : }
56 :
57 : static void
58 0 : _cairo_filler_fini (cairo_filler_t *filler)
59 : {
60 0 : }
61 :
62 : static cairo_status_t
63 0 : _cairo_filler_move_to (void *closure,
64 : const cairo_point_t *point)
65 : {
66 0 : cairo_filler_t *filler = closure;
67 0 : cairo_polygon_t *polygon = filler->polygon;
68 :
69 0 : return _cairo_polygon_close (polygon) ||
70 0 : _cairo_polygon_move_to (polygon, point);
71 : }
72 :
73 : static cairo_status_t
74 0 : _cairo_filler_line_to (void *closure,
75 : const cairo_point_t *point)
76 : {
77 0 : cairo_filler_t *filler = closure;
78 0 : return _cairo_polygon_line_to (filler->polygon, point);
79 : }
80 :
81 : static cairo_status_t
82 0 : _cairo_filler_curve_to (void *closure,
83 : const cairo_point_t *b,
84 : const cairo_point_t *c,
85 : const cairo_point_t *d)
86 : {
87 0 : cairo_filler_t *filler = closure;
88 : cairo_spline_t spline;
89 :
90 0 : if (! _cairo_spline_init (&spline,
91 : _cairo_filler_line_to, filler,
92 0 : &filler->polygon->current_point, b, c, d))
93 : {
94 0 : return _cairo_filler_line_to (closure, d);
95 : }
96 :
97 0 : return _cairo_spline_decompose (&spline, filler->tolerance);
98 : }
99 :
100 : static cairo_status_t
101 0 : _cairo_filler_close_path (void *closure)
102 : {
103 0 : cairo_filler_t *filler = closure;
104 0 : return _cairo_polygon_close (filler->polygon);
105 : }
106 :
107 : cairo_status_t
108 0 : _cairo_path_fixed_fill_to_polygon (const cairo_path_fixed_t *path,
109 : double tolerance,
110 : cairo_polygon_t *polygon)
111 : {
112 : cairo_filler_t filler;
113 : cairo_status_t status;
114 :
115 0 : _cairo_filler_init (&filler, tolerance, polygon);
116 :
117 0 : status = _cairo_path_fixed_interpret (path,
118 : CAIRO_DIRECTION_FORWARD,
119 : _cairo_filler_move_to,
120 : _cairo_filler_line_to,
121 : _cairo_filler_curve_to,
122 : _cairo_filler_close_path,
123 : &filler);
124 0 : if (unlikely (status))
125 0 : return status;
126 :
127 0 : status = _cairo_polygon_close (polygon);
128 0 : _cairo_filler_fini (&filler);
129 :
130 0 : return status;
131 : }
132 :
133 : cairo_status_t
134 0 : _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
135 : cairo_fill_rule_t fill_rule,
136 : double tolerance,
137 : cairo_traps_t *traps)
138 : {
139 : cairo_polygon_t polygon;
140 : cairo_status_t status;
141 :
142 0 : if (path->is_empty_fill)
143 0 : return CAIRO_STATUS_SUCCESS;
144 :
145 0 : _cairo_polygon_init (&polygon);
146 0 : if (traps->num_limits)
147 0 : _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
148 :
149 0 : status = _cairo_path_fixed_fill_to_polygon (path,
150 : tolerance,
151 : &polygon);
152 0 : if (unlikely (status || polygon.num_edges == 0))
153 : goto CLEANUP;
154 :
155 0 : if (path->is_rectilinear) {
156 0 : status = _cairo_bentley_ottmann_tessellate_rectilinear_polygon (traps,
157 : &polygon,
158 : fill_rule);
159 : } else {
160 0 : status = _cairo_bentley_ottmann_tessellate_polygon (traps,
161 : &polygon,
162 : fill_rule);
163 : }
164 :
165 : CLEANUP:
166 0 : _cairo_polygon_fini (&polygon);
167 0 : return status;
168 : }
169 :
170 : static cairo_region_t *
171 0 : _cairo_path_fixed_fill_rectilinear_tessellate_to_region (const cairo_path_fixed_t *path,
172 : cairo_fill_rule_t fill_rule,
173 : const cairo_rectangle_int_t *extents)
174 : {
175 : cairo_box_t box;
176 : cairo_polygon_t polygon;
177 : cairo_traps_t traps;
178 : cairo_status_t status;
179 : cairo_region_t *region;
180 :
181 : /* first try to bypass fill-to-polygon */
182 0 : _cairo_traps_init (&traps);
183 0 : status = _cairo_path_fixed_fill_rectilinear_to_traps (path,
184 : fill_rule,
185 : &traps);
186 0 : if (_cairo_status_is_error (status))
187 0 : goto CLEANUP_TRAPS;
188 :
189 0 : if (status == CAIRO_STATUS_SUCCESS) {
190 0 : status = _cairo_traps_extract_region (&traps, ®ion);
191 0 : goto CLEANUP_TRAPS;
192 : }
193 :
194 : /* path is not rectangular, try extracting clipped rectilinear edges */
195 0 : _cairo_polygon_init (&polygon);
196 0 : if (extents != NULL) {
197 0 : _cairo_box_from_rectangle (&box, extents);
198 0 : _cairo_polygon_limit (&polygon, &box, 1);
199 : }
200 :
201 : /* tolerance will be ignored as the path is rectilinear */
202 0 : status = _cairo_path_fixed_fill_to_polygon (path, 0., &polygon);
203 0 : if (unlikely (status))
204 0 : goto CLEANUP_POLYGON;
205 :
206 0 : if (polygon.num_edges == 0) {
207 0 : region = cairo_region_create ();
208 : } else {
209 0 : status =
210 : _cairo_bentley_ottmann_tessellate_rectilinear_polygon (&traps,
211 : &polygon,
212 : fill_rule);
213 0 : if (likely (status == CAIRO_STATUS_SUCCESS))
214 0 : status = _cairo_traps_extract_region (&traps, ®ion);
215 : }
216 :
217 : CLEANUP_POLYGON:
218 0 : _cairo_polygon_fini (&polygon);
219 :
220 : CLEANUP_TRAPS:
221 0 : _cairo_traps_fini (&traps);
222 :
223 0 : if (unlikely (status))
224 0 : region = _cairo_region_create_in_error (status);
225 :
226 0 : return region;
227 : }
228 :
229 : /* This special-case filler supports only a path that describes a
230 : * device-axis aligned rectangle. It exists to avoid the overhead of
231 : * the general tessellator when drawing very common rectangles.
232 : *
233 : * If the path described anything but a device-axis aligned rectangle,
234 : * this function will abort.
235 : */
236 : cairo_region_t *
237 0 : _cairo_path_fixed_fill_rectilinear_to_region (const cairo_path_fixed_t *path,
238 : cairo_fill_rule_t fill_rule,
239 : const cairo_rectangle_int_t *extents)
240 : {
241 : cairo_rectangle_int_t rectangle_stack[CAIRO_STACK_ARRAY_LENGTH (cairo_rectangle_int_t)];
242 : cairo_box_t box;
243 0 : cairo_region_t *region = NULL;
244 :
245 0 : assert (path->maybe_fill_region);
246 0 : assert (! path->is_empty_fill);
247 :
248 0 : if (_cairo_path_fixed_is_box (path, &box)) {
249 0 : rectangle_stack[0].x = _cairo_fixed_integer_part (box.p1.x);
250 0 : rectangle_stack[0].y = _cairo_fixed_integer_part (box.p1.y);
251 0 : rectangle_stack[0].width = _cairo_fixed_integer_part (box.p2.x) -
252 0 : rectangle_stack[0].x;
253 0 : rectangle_stack[0].height = _cairo_fixed_integer_part (box.p2.y) -
254 0 : rectangle_stack[0].y;
255 0 : if (! _cairo_rectangle_intersect (&rectangle_stack[0], extents))
256 0 : region = cairo_region_create ();
257 : else
258 0 : region = cairo_region_create_rectangle (&rectangle_stack[0]);
259 0 : } else if (fill_rule == CAIRO_FILL_RULE_WINDING) {
260 0 : cairo_rectangle_int_t *rects = rectangle_stack;
261 : cairo_path_fixed_iter_t iter;
262 0 : int last_cw = -1;
263 0 : int size = ARRAY_LENGTH (rectangle_stack);
264 0 : int count = 0;
265 :
266 : /* Support a series of rectangles as can be expected to describe a
267 : * GdkRegion clip region during exposes.
268 : */
269 0 : _cairo_path_fixed_iter_init (&iter, path);
270 0 : while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
271 0 : int cw = 0;
272 :
273 0 : if (box.p1.x > box.p2.x) {
274 : cairo_fixed_t t;
275 :
276 0 : t = box.p1.x;
277 0 : box.p1.x = box.p2.x;
278 0 : box.p2.x = t;
279 :
280 0 : cw = ! cw;
281 : }
282 :
283 0 : if (box.p1.y > box.p2.y) {
284 : cairo_fixed_t t;
285 :
286 0 : t = box.p1.y;
287 0 : box.p1.y = box.p2.y;
288 0 : box.p2.y = t;
289 :
290 0 : cw = ! cw;
291 : }
292 :
293 0 : if (last_cw < 0)
294 0 : last_cw = cw;
295 0 : else if (last_cw != cw)
296 0 : goto TESSELLATE;
297 :
298 0 : if (count == size) {
299 : cairo_rectangle_int_t *new_rects;
300 :
301 0 : size *= 4;
302 0 : if (rects == rectangle_stack) {
303 0 : new_rects = _cairo_malloc_ab (size,
304 : sizeof (cairo_rectangle_int_t));
305 0 : if (unlikely (new_rects == NULL)) {
306 : /* XXX _cairo_region_nil */
307 0 : break;
308 : }
309 0 : memcpy (new_rects, rects, sizeof (rectangle_stack));
310 : } else {
311 0 : new_rects = _cairo_realloc_ab (rects, size,
312 : sizeof (cairo_rectangle_int_t));
313 0 : if (unlikely (new_rects == NULL)) {
314 : /* XXX _cairo_region_nil */
315 0 : break;
316 : }
317 : }
318 0 : rects = new_rects;
319 : }
320 :
321 0 : rects[count].x = _cairo_fixed_integer_part (box.p1.x);
322 0 : rects[count].y = _cairo_fixed_integer_part (box.p1.y);
323 0 : rects[count].width = _cairo_fixed_integer_part (box.p2.x) - rects[count].x;
324 0 : rects[count].height = _cairo_fixed_integer_part (box.p2.y) - rects[count].y;
325 0 : if (_cairo_rectangle_intersect (&rects[count], extents))
326 0 : count++;
327 : }
328 :
329 0 : if (_cairo_path_fixed_iter_at_end (&iter))
330 0 : region = cairo_region_create_rectangles (rects, count);
331 :
332 : TESSELLATE:
333 0 : if (rects != rectangle_stack)
334 0 : free (rects);
335 : }
336 :
337 0 : if (region == NULL) {
338 : /* Hmm, complex polygon */
339 0 : region = _cairo_path_fixed_fill_rectilinear_tessellate_to_region (path,
340 : fill_rule,
341 : extents);
342 :
343 :
344 : }
345 :
346 0 : return region;
347 : }
348 :
349 : cairo_int_status_t
350 0 : _cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t *path,
351 : cairo_fill_rule_t fill_rule,
352 : cairo_traps_t *traps)
353 : {
354 : cairo_box_t box;
355 : cairo_status_t status;
356 :
357 0 : traps->is_rectilinear = TRUE;
358 0 : traps->is_rectangular = TRUE;
359 :
360 0 : if (_cairo_path_fixed_is_box (path, &box)) {
361 0 : return _cairo_traps_tessellate_rectangle (traps, &box.p1, &box.p2);
362 : } else {
363 : cairo_path_fixed_iter_t iter;
364 :
365 0 : _cairo_path_fixed_iter_init (&iter, path);
366 0 : while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
367 0 : if (box.p1.y > box.p2.y) {
368 : cairo_fixed_t t;
369 :
370 0 : t = box.p1.y;
371 0 : box.p1.y = box.p2.y;
372 0 : box.p2.y = t;
373 :
374 0 : t = box.p1.x;
375 0 : box.p1.x = box.p2.x;
376 0 : box.p2.x = t;
377 : }
378 :
379 0 : status = _cairo_traps_tessellate_rectangle (traps,
380 : &box.p1, &box.p2);
381 0 : if (unlikely (status)) {
382 0 : _cairo_traps_clear (traps);
383 0 : return status;
384 : }
385 : }
386 :
387 0 : if (_cairo_path_fixed_iter_at_end (&iter))
388 0 : return _cairo_bentley_ottmann_tessellate_rectangular_traps (traps, fill_rule);
389 :
390 0 : _cairo_traps_clear (traps);
391 0 : return CAIRO_INT_STATUS_UNSUPPORTED;
392 : }
393 : }
394 :
395 : static cairo_status_t
396 0 : _cairo_path_fixed_fill_rectilinear_tessellate_to_boxes (const cairo_path_fixed_t *path,
397 : cairo_fill_rule_t fill_rule,
398 : cairo_boxes_t *boxes)
399 : {
400 : cairo_polygon_t polygon;
401 : cairo_status_t status;
402 :
403 0 : _cairo_polygon_init (&polygon);
404 0 : if (boxes->num_limits) {
405 0 : _cairo_polygon_limit (&polygon, boxes->limits, boxes->num_limits);
406 0 : boxes->num_limits = 0;
407 : }
408 :
409 : /* tolerance will be ignored as the path is rectilinear */
410 0 : status = _cairo_path_fixed_fill_to_polygon (path, 0., &polygon);
411 0 : if (likely (status == CAIRO_STATUS_SUCCESS)) {
412 0 : status =
413 : _cairo_bentley_ottmann_tessellate_rectilinear_polygon_to_boxes (&polygon,
414 : fill_rule,
415 : boxes);
416 : }
417 :
418 0 : _cairo_polygon_fini (&polygon);
419 :
420 0 : return status;
421 : }
422 :
423 : cairo_status_t
424 0 : _cairo_path_fixed_fill_rectilinear_to_boxes (const cairo_path_fixed_t *path,
425 : cairo_fill_rule_t fill_rule,
426 : cairo_boxes_t *boxes)
427 : {
428 : cairo_path_fixed_iter_t iter;
429 : cairo_status_t status;
430 : cairo_box_t box;
431 :
432 0 : if (_cairo_path_fixed_is_box (path, &box))
433 0 : return _cairo_boxes_add (boxes, &box);
434 :
435 0 : _cairo_path_fixed_iter_init (&iter, path);
436 0 : while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
437 0 : if (box.p1.y == box.p2.y || box.p1.x == box.p2.x)
438 0 : continue;
439 :
440 0 : if (box.p1.y > box.p2.y) {
441 : cairo_fixed_t t;
442 :
443 0 : t = box.p1.y;
444 0 : box.p1.y = box.p2.y;
445 0 : box.p2.y = t;
446 :
447 0 : t = box.p1.x;
448 0 : box.p1.x = box.p2.x;
449 0 : box.p2.x = t;
450 : }
451 :
452 0 : status = _cairo_boxes_add (boxes, &box);
453 0 : if (unlikely (status))
454 0 : return status;
455 : }
456 :
457 0 : if (_cairo_path_fixed_iter_at_end (&iter))
458 0 : return _cairo_bentley_ottmann_tessellate_boxes (boxes, fill_rule, boxes);
459 :
460 : /* path is not rectangular, try extracting clipped rectilinear edges */
461 0 : _cairo_boxes_clear (boxes);
462 0 : return _cairo_path_fixed_fill_rectilinear_tessellate_to_boxes (path,
463 : fill_rule,
464 : boxes);
465 : }
|
