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 :
39 : #include "cairo-error-private.h"
40 : #include "cairo-slope-private.h"
41 :
42 : void
43 0 : _cairo_polygon_init (cairo_polygon_t *polygon)
44 : {
45 : VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
46 :
47 0 : polygon->status = CAIRO_STATUS_SUCCESS;
48 :
49 0 : polygon->num_edges = 0;
50 :
51 0 : polygon->edges = polygon->edges_embedded;
52 0 : polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
53 :
54 0 : polygon->has_current_point = FALSE;
55 0 : polygon->has_current_edge = FALSE;
56 0 : polygon->num_limits = 0;
57 :
58 0 : polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
59 0 : polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
60 0 : }
61 :
62 : void
63 0 : _cairo_polygon_limit (cairo_polygon_t *polygon,
64 : const cairo_box_t *limits,
65 : int num_limits)
66 : {
67 : int n;
68 :
69 0 : polygon->limits = limits;
70 0 : polygon->num_limits = num_limits;
71 :
72 0 : if (polygon->num_limits) {
73 0 : polygon->limit = limits[0];
74 0 : for (n = 1; n < num_limits; n++) {
75 0 : if (limits[n].p1.x < polygon->limit.p1.x)
76 0 : polygon->limit.p1.x = limits[n].p1.x;
77 :
78 0 : if (limits[n].p1.y < polygon->limit.p1.y)
79 0 : polygon->limit.p1.y = limits[n].p1.y;
80 :
81 0 : if (limits[n].p2.x > polygon->limit.p2.x)
82 0 : polygon->limit.p2.x = limits[n].p2.x;
83 :
84 0 : if (limits[n].p2.y > polygon->limit.p2.y)
85 0 : polygon->limit.p2.y = limits[n].p2.y;
86 : }
87 : }
88 0 : }
89 :
90 : void
91 0 : _cairo_polygon_fini (cairo_polygon_t *polygon)
92 : {
93 0 : if (polygon->edges != polygon->edges_embedded)
94 0 : free (polygon->edges);
95 :
96 : VG (VALGRIND_MAKE_MEM_NOACCESS (polygon, sizeof (cairo_polygon_t)));
97 0 : }
98 :
99 : /* make room for at least one more edge */
100 : static cairo_bool_t
101 0 : _cairo_polygon_grow (cairo_polygon_t *polygon)
102 : {
103 : cairo_edge_t *new_edges;
104 0 : int old_size = polygon->edges_size;
105 0 : int new_size = 4 * old_size;
106 :
107 : if (CAIRO_INJECT_FAULT ()) {
108 : polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
109 : return FALSE;
110 : }
111 :
112 0 : if (polygon->edges == polygon->edges_embedded) {
113 0 : new_edges = _cairo_malloc_ab (new_size, sizeof (cairo_edge_t));
114 0 : if (new_edges != NULL)
115 0 : memcpy (new_edges, polygon->edges, old_size * sizeof (cairo_edge_t));
116 : } else {
117 0 : new_edges = _cairo_realloc_ab (polygon->edges,
118 : new_size, sizeof (cairo_edge_t));
119 : }
120 :
121 0 : if (unlikely (new_edges == NULL)) {
122 0 : polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
123 0 : return FALSE;
124 : }
125 :
126 0 : polygon->edges = new_edges;
127 0 : polygon->edges_size = new_size;
128 :
129 0 : return TRUE;
130 : }
131 :
132 : static void
133 0 : _add_edge (cairo_polygon_t *polygon,
134 : const cairo_point_t *p1,
135 : const cairo_point_t *p2,
136 : int top, int bottom,
137 : int dir)
138 : {
139 : cairo_edge_t *edge;
140 :
141 0 : assert (top < bottom);
142 :
143 0 : if (unlikely (polygon->num_edges == polygon->edges_size)) {
144 0 : if (! _cairo_polygon_grow (polygon))
145 0 : return;
146 : }
147 :
148 0 : edge = &polygon->edges[polygon->num_edges++];
149 0 : edge->line.p1 = *p1;
150 0 : edge->line.p2 = *p2;
151 0 : edge->top = top;
152 0 : edge->bottom = bottom;
153 0 : edge->dir = dir;
154 :
155 0 : if (top < polygon->extents.p1.y)
156 0 : polygon->extents.p1.y = top;
157 0 : if (bottom > polygon->extents.p2.y)
158 0 : polygon->extents.p2.y = bottom;
159 :
160 0 : if (p1->x < polygon->extents.p1.x || p1->x > polygon->extents.p2.x) {
161 0 : cairo_fixed_t x = p1->x;
162 0 : if (top != p1->y)
163 0 : x = _cairo_edge_compute_intersection_x_for_y (p1, p2, top);
164 0 : if (x < polygon->extents.p1.x)
165 0 : polygon->extents.p1.x = x;
166 0 : if (x > polygon->extents.p2.x)
167 0 : polygon->extents.p2.x = x;
168 : }
169 :
170 0 : if (p2->x < polygon->extents.p1.x || p2->x > polygon->extents.p2.x) {
171 0 : cairo_fixed_t x = p2->x;
172 0 : if (bottom != p2->y)
173 0 : x = _cairo_edge_compute_intersection_x_for_y (p1, p2, bottom);
174 0 : if (x < polygon->extents.p1.x)
175 0 : polygon->extents.p1.x = x;
176 0 : if (x > polygon->extents.p2.x)
177 0 : polygon->extents.p2.x = x;
178 : }
179 : }
180 :
181 : static void
182 0 : _add_clipped_edge (cairo_polygon_t *polygon,
183 : const cairo_point_t *p1,
184 : const cairo_point_t *p2,
185 : const int top, const int bottom,
186 : const int dir)
187 : {
188 : cairo_point_t p[2];
189 : int top_y, bot_y;
190 : int n;
191 :
192 0 : for (n = 0; n < polygon->num_limits; n++) {
193 0 : const cairo_box_t *limits = &polygon->limits[n];
194 :
195 0 : if (top >= limits->p2.y)
196 0 : continue;
197 0 : if (bottom <= limits->p1.y)
198 0 : continue;
199 :
200 0 : if (p1->x >= limits->p1.x && p2->x >= limits->p1.x &&
201 0 : p1->x <= limits->p2.x && p2->x <= limits->p2.x)
202 : {
203 0 : top_y = top;
204 0 : if (top_y < limits->p1.y)
205 0 : top_y = limits->p1.y;
206 :
207 0 : bot_y = bottom;
208 0 : if (bot_y > limits->p2.y)
209 0 : bot_y = limits->p2.y;
210 :
211 0 : _add_edge (polygon, p1, p2, top_y, bot_y, dir);
212 : }
213 0 : else if (p1->x <= limits->p1.x && p2->x <= limits->p1.x)
214 : {
215 0 : p[0].x = limits->p1.x;
216 0 : p[0].y = limits->p1.y;
217 0 : top_y = top;
218 0 : if (top_y < p[0].y)
219 0 : top_y = p[0].y;
220 :
221 0 : p[1].x = limits->p1.x;
222 0 : p[1].y = limits->p2.y;
223 0 : bot_y = bottom;
224 0 : if (bot_y > p[1].y)
225 0 : bot_y = p[1].y;
226 :
227 0 : _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
228 : }
229 0 : else if (p1->x >= limits->p2.x && p2->x >= limits->p2.x)
230 : {
231 0 : p[0].x = limits->p2.x;
232 0 : p[0].y = limits->p1.y;
233 0 : top_y = top;
234 0 : if (top_y < p[0].y)
235 0 : top_y = p[0].y;
236 :
237 0 : p[1].x = limits->p2.x;
238 0 : p[1].y = limits->p2.y;
239 0 : bot_y = bottom;
240 0 : if (bot_y > p[1].y)
241 0 : bot_y = p[1].y;
242 :
243 0 : _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
244 : }
245 : else
246 : {
247 : int left_y, right_y;
248 : int p1_y, p2_y;
249 :
250 0 : left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
251 : limits->p1.x);
252 0 : right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
253 : limits->p2.x);
254 :
255 0 : p1_y = top;
256 0 : p2_y = bottom;
257 :
258 0 : if (p1->x < p2->x) {
259 0 : if (p1->x < limits->p1.x && left_y > limits->p1.y) {
260 0 : p[0].x = limits->p1.x;
261 0 : p[0].y = limits->p1.y;
262 0 : top_y = p1_y;
263 0 : if (top_y < p[0].y)
264 0 : top_y = p[0].y;
265 :
266 0 : p[1].x = limits->p1.x;
267 0 : p[1].y = limits->p2.y;
268 0 : bot_y = left_y;
269 0 : if (bot_y > p[1].y)
270 0 : bot_y = p[1].y;
271 :
272 0 : if (bot_y > top_y)
273 0 : _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
274 0 : p1_y = bot_y;
275 : }
276 :
277 0 : if (p2->x > limits->p2.x && right_y < limits->p2.y) {
278 0 : p[0].x = limits->p2.x;
279 0 : p[0].y = limits->p1.y;
280 0 : top_y = right_y;
281 0 : if (top_y < p[0].y)
282 0 : top_y = p[0].y;
283 :
284 0 : p[1].x = limits->p2.x;
285 0 : p[1].y = limits->p2.y;
286 0 : bot_y = p2_y;
287 0 : if (bot_y > p[1].y)
288 0 : bot_y = p[1].y;
289 :
290 0 : if (bot_y > top_y)
291 0 : _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
292 0 : p2_y = top_y;
293 : }
294 : } else {
295 0 : if (p1->x > limits->p2.x && right_y > limits->p1.y) {
296 0 : p[0].x = limits->p2.x;
297 0 : p[0].y = limits->p1.y;
298 0 : top_y = p1_y;
299 0 : if (top_y < p[0].y)
300 0 : top_y = p[0].y;
301 :
302 0 : p[1].x = limits->p2.x;
303 0 : p[1].y = limits->p2.y;
304 0 : bot_y = right_y;
305 0 : if (bot_y > p[1].y)
306 0 : bot_y = p[1].y;
307 :
308 0 : if (bot_y > top_y)
309 0 : _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
310 0 : p1_y = bot_y;
311 : }
312 :
313 0 : if (p2->x < limits->p1.x && left_y < limits->p2.y) {
314 0 : p[0].x = limits->p1.x;
315 0 : p[0].y = limits->p1.y;
316 0 : top_y = left_y;
317 0 : if (top_y < p[0].y)
318 0 : top_y = p[0].y;
319 :
320 0 : p[1].x = limits->p1.x;
321 0 : p[1].y = limits->p2.y;
322 0 : bot_y = p2_y;
323 0 : if (bot_y > p[1].y)
324 0 : bot_y = p[1].y;
325 :
326 0 : if (bot_y > top_y)
327 0 : _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
328 0 : p2_y = top_y;
329 : }
330 : }
331 :
332 0 : if (p1_y < limits->p1.y)
333 0 : p1_y = limits->p1.y;
334 0 : if (p2_y > limits->p2.y)
335 0 : p2_y = limits->p2.y;
336 0 : if (p2_y > p1_y)
337 0 : _add_edge (polygon, p1, p2, p1_y, p2_y, dir);
338 : }
339 : }
340 0 : }
341 :
342 : static void
343 0 : _cairo_polygon_add_edge (cairo_polygon_t *polygon,
344 : const cairo_point_t *p1,
345 : const cairo_point_t *p2)
346 : {
347 : int dir;
348 :
349 : /* drop horizontal edges */
350 0 : if (p1->y == p2->y)
351 0 : return;
352 :
353 0 : if (p1->y < p2->y) {
354 0 : dir = 1;
355 : } else {
356 : const cairo_point_t *t;
357 0 : t = p1, p1 = p2, p2 = t;
358 0 : dir = -1;
359 : }
360 :
361 0 : if (polygon->num_limits) {
362 0 : if (p2->y <= polygon->limit.p1.y)
363 0 : return;
364 :
365 0 : if (p1->y >= polygon->limit.p2.y)
366 0 : return;
367 :
368 0 : _add_clipped_edge (polygon, p1, p2, p1->y, p2->y, dir);
369 : } else
370 0 : _add_edge (polygon, p1, p2, p1->y, p2->y, dir);
371 : }
372 :
373 : cairo_status_t
374 0 : _cairo_polygon_add_external_edge (void *polygon,
375 : const cairo_point_t *p1,
376 : const cairo_point_t *p2)
377 : {
378 0 : _cairo_polygon_add_edge (polygon, p1, p2);
379 0 : return _cairo_polygon_status (polygon);
380 : }
381 :
382 : cairo_status_t
383 0 : _cairo_polygon_add_line (cairo_polygon_t *polygon,
384 : const cairo_line_t *line,
385 : int top, int bottom,
386 : int dir)
387 : {
388 : /* drop horizontal edges */
389 0 : if (line->p1.y == line->p2.y)
390 0 : return CAIRO_STATUS_SUCCESS;
391 :
392 0 : if (bottom <= top)
393 0 : return CAIRO_STATUS_SUCCESS;
394 :
395 0 : if (polygon->num_limits) {
396 0 : if (line->p2.y <= polygon->limit.p1.y)
397 0 : return CAIRO_STATUS_SUCCESS;
398 :
399 0 : if (line->p1.y >= polygon->limit.p2.y)
400 0 : return CAIRO_STATUS_SUCCESS;
401 :
402 0 : _add_clipped_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
403 : } else
404 0 : _add_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
405 :
406 0 : return polygon->status;
407 : }
408 :
409 : /* flattened path operations */
410 :
411 : cairo_status_t
412 0 : _cairo_polygon_move_to (cairo_polygon_t *polygon,
413 : const cairo_point_t *point)
414 : {
415 0 : if (polygon->has_current_edge) {
416 0 : _cairo_polygon_add_edge (polygon,
417 0 : &polygon->last_point,
418 0 : &polygon->current_point);
419 0 : polygon->has_current_edge = FALSE;
420 : }
421 :
422 0 : if (! polygon->has_current_point) {
423 0 : polygon->first_point = *point;
424 0 : polygon->has_current_point = TRUE;
425 : }
426 :
427 0 : polygon->current_point = *point;
428 0 : return polygon->status;
429 : }
430 :
431 : cairo_status_t
432 0 : _cairo_polygon_line_to (cairo_polygon_t *polygon,
433 : const cairo_point_t *point)
434 : {
435 : /* squash collinear edges */
436 0 : if (polygon->has_current_edge) {
437 0 : if (polygon->current_point.x != point->x ||
438 0 : polygon->current_point.y != point->y)
439 : {
440 : cairo_slope_t this;
441 :
442 0 : _cairo_slope_init (&this, &polygon->current_point, point);
443 0 : if (_cairo_slope_equal (&polygon->current_edge, &this)) {
444 0 : polygon->current_point = *point;
445 0 : return CAIRO_STATUS_SUCCESS;
446 : }
447 :
448 0 : _cairo_polygon_add_edge (polygon,
449 0 : &polygon->last_point,
450 0 : &polygon->current_point);
451 :
452 0 : polygon->last_point = polygon->current_point;
453 0 : polygon->current_edge = this;
454 : }
455 0 : } else if (polygon->has_current_point) {
456 0 : if (polygon->current_point.x != point->x ||
457 0 : polygon->current_point.y != point->y)
458 : {
459 0 : polygon->last_point = polygon->current_point;
460 0 : _cairo_slope_init (&polygon->current_edge,
461 0 : &polygon->last_point,
462 : point);
463 0 : polygon->has_current_edge = TRUE;
464 : }
465 : } else {
466 0 : polygon->first_point = *point;
467 0 : polygon->has_current_point = TRUE;
468 : }
469 :
470 0 : polygon->current_point = *point;
471 0 : return polygon->status;
472 : }
473 :
474 : cairo_status_t
475 0 : _cairo_polygon_close (cairo_polygon_t *polygon)
476 : {
477 : cairo_status_t status;
478 :
479 0 : if (polygon->has_current_point) {
480 0 : status = _cairo_polygon_line_to (polygon, &polygon->first_point);
481 0 : polygon->has_current_point = FALSE;
482 : }
483 :
484 0 : if (polygon->has_current_edge) {
485 0 : _cairo_polygon_add_edge (polygon,
486 0 : &polygon->last_point,
487 0 : &polygon->current_point);
488 0 : polygon->has_current_edge = FALSE;
489 : }
490 :
491 0 : return polygon->status;
492 : }
|
