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
4 * Copyright © 2002 University of Southern California
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.
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
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/
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.
29 * The Original Code is the cairo graphics library.
31 * The Initial Developer of the Original Code is University of Southern
35 * Carl D. Worth <cworth@cworth.org>
40 #include "cairo-boxes-private.h"
41 #include "cairo-contour-private.h"
42 #include "cairo-error-private.h"
44 #define DEBUG_POLYGON 0
46 #if DEBUG_POLYGON && !NDEBUG
48 assert_last_edge_is_valid(cairo_polygon_t *polygon,
49 const cairo_box_t *limit)
54 edge = &polygon->edges[polygon->num_edges-1];
56 assert (edge->bottom > edge->top);
57 assert (edge->top >= limit->p1.y);
58 assert (edge->bottom <= limit->p2.y);
60 x = _cairo_edge_compute_intersection_x_for_y (&edge->line.p1,
63 assert (x >= limit->p1.x);
64 assert (x <= limit->p2.x);
66 x = _cairo_edge_compute_intersection_x_for_y (&edge->line.p1,
69 assert (x >= limit->p1.x);
70 assert (x <= limit->p2.x);
73 #define assert_last_edge_is_valid(p, l)
77 _cairo_polygon_add_edge (cairo_polygon_t *polygon,
78 const cairo_point_t *p1,
79 const cairo_point_t *p2,
83 _cairo_polygon_limit (cairo_polygon_t *polygon,
84 const cairo_box_t *limits,
89 polygon->limits = limits;
90 polygon->num_limits = num_limits;
92 if (polygon->num_limits) {
93 polygon->limit = limits[0];
94 for (n = 1; n < num_limits; n++) {
95 if (limits[n].p1.x < polygon->limit.p1.x)
96 polygon->limit.p1.x = limits[n].p1.x;
98 if (limits[n].p1.y < polygon->limit.p1.y)
99 polygon->limit.p1.y = limits[n].p1.y;
101 if (limits[n].p2.x > polygon->limit.p2.x)
102 polygon->limit.p2.x = limits[n].p2.x;
104 if (limits[n].p2.y > polygon->limit.p2.y)
105 polygon->limit.p2.y = limits[n].p2.y;
111 _cairo_polygon_limit_to_clip (cairo_polygon_t *polygon,
112 const cairo_clip_t *clip)
115 _cairo_polygon_limit (polygon, clip->boxes, clip->num_boxes);
117 _cairo_polygon_limit (polygon, 0, 0);
121 _cairo_polygon_init (cairo_polygon_t *polygon,
122 const cairo_box_t *limits,
125 VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
127 polygon->status = CAIRO_STATUS_SUCCESS;
129 polygon->num_edges = 0;
131 polygon->edges = polygon->edges_embedded;
132 polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
134 polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
135 polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
137 _cairo_polygon_limit (polygon, limits, num_limits);
141 _cairo_polygon_init_with_clip (cairo_polygon_t *polygon,
142 const cairo_clip_t *clip)
145 _cairo_polygon_init (polygon, clip->boxes, clip->num_boxes);
147 _cairo_polygon_init (polygon, 0, 0);
151 _cairo_polygon_init_boxes (cairo_polygon_t *polygon,
152 const cairo_boxes_t *boxes)
154 const struct _cairo_boxes_chunk *chunk;
157 VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
159 polygon->status = CAIRO_STATUS_SUCCESS;
161 polygon->num_edges = 0;
163 polygon->edges = polygon->edges_embedded;
164 polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
165 if (boxes->num_boxes > ARRAY_LENGTH (polygon->edges_embedded)/2) {
166 polygon->edges_size = 2 * boxes->num_boxes;
167 polygon->edges = _cairo_malloc_ab (polygon->edges_size,
168 2*sizeof(cairo_edge_t));
169 if (unlikely (polygon->edges == NULL))
170 return polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
173 polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
174 polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
176 polygon->limits = NULL;
177 polygon->num_limits = 0;
179 for (chunk = &boxes->chunks; chunk != NULL; chunk = chunk->next) {
180 for (i = 0; i < chunk->count; i++) {
181 cairo_point_t p1, p2;
183 p1 = chunk->base[i].p1;
185 p2.y = chunk->base[i].p2.y;
186 _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
188 p1 = chunk->base[i].p2;
190 p2.y = chunk->base[i].p1.y;
191 _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
195 return polygon->status;
199 _cairo_polygon_init_box_array (cairo_polygon_t *polygon,
205 VG (VALGRIND_MAKE_MEM_UNDEFINED (polygon, sizeof (cairo_polygon_t)));
207 polygon->status = CAIRO_STATUS_SUCCESS;
209 polygon->num_edges = 0;
211 polygon->edges = polygon->edges_embedded;
212 polygon->edges_size = ARRAY_LENGTH (polygon->edges_embedded);
213 if (num_boxes > ARRAY_LENGTH (polygon->edges_embedded)/2) {
214 polygon->edges_size = 2 * num_boxes;
215 polygon->edges = _cairo_malloc_ab (polygon->edges_size,
216 2*sizeof(cairo_edge_t));
217 if (unlikely (polygon->edges == NULL))
218 return polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
221 polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
222 polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
224 polygon->limits = NULL;
225 polygon->num_limits = 0;
227 for (i = 0; i < num_boxes; i++) {
228 cairo_point_t p1, p2;
232 p2.y = boxes[i].p2.y;
233 _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
237 p2.y = boxes[i].p1.y;
238 _cairo_polygon_add_edge (polygon, &p1, &p2, 1);
241 return polygon->status;
246 _cairo_polygon_fini (cairo_polygon_t *polygon)
248 if (polygon->edges != polygon->edges_embedded)
249 free (polygon->edges);
251 VG (VALGRIND_MAKE_MEM_NOACCESS (polygon, sizeof (cairo_polygon_t)));
254 /* make room for at least one more edge */
256 _cairo_polygon_grow (cairo_polygon_t *polygon)
258 cairo_edge_t *new_edges;
259 int old_size = polygon->edges_size;
260 int new_size = 4 * old_size;
262 if (CAIRO_INJECT_FAULT ()) {
263 polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
267 if (polygon->edges == polygon->edges_embedded) {
268 new_edges = _cairo_malloc_ab (new_size, sizeof (cairo_edge_t));
269 if (new_edges != NULL)
270 memcpy (new_edges, polygon->edges, old_size * sizeof (cairo_edge_t));
272 new_edges = _cairo_realloc_ab (polygon->edges,
273 new_size, sizeof (cairo_edge_t));
276 if (unlikely (new_edges == NULL)) {
277 polygon->status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
281 polygon->edges = new_edges;
282 polygon->edges_size = new_size;
288 _add_edge (cairo_polygon_t *polygon,
289 const cairo_point_t *p1,
290 const cairo_point_t *p2,
296 assert (top < bottom);
298 if (unlikely (polygon->num_edges == polygon->edges_size)) {
299 if (! _cairo_polygon_grow (polygon))
303 edge = &polygon->edges[polygon->num_edges++];
307 edge->bottom = bottom;
310 if (top < polygon->extents.p1.y)
311 polygon->extents.p1.y = top;
312 if (bottom > polygon->extents.p2.y)
313 polygon->extents.p2.y = bottom;
315 if (p1->x < polygon->extents.p1.x || p1->x > polygon->extents.p2.x) {
316 cairo_fixed_t x = p1->x;
318 x = _cairo_edge_compute_intersection_x_for_y (p1, p2, top);
319 if (x < polygon->extents.p1.x)
320 polygon->extents.p1.x = x;
321 if (x > polygon->extents.p2.x)
322 polygon->extents.p2.x = x;
325 if (p2->x < polygon->extents.p1.x || p2->x > polygon->extents.p2.x) {
326 cairo_fixed_t x = p2->x;
328 x = _cairo_edge_compute_intersection_x_for_y (p1, p2, bottom);
329 if (x < polygon->extents.p1.x)
330 polygon->extents.p1.x = x;
331 if (x > polygon->extents.p2.x)
332 polygon->extents.p2.x = x;
337 _add_clipped_edge (cairo_polygon_t *polygon,
338 const cairo_point_t *p1,
339 const cairo_point_t *p2,
340 const int top, const int bottom,
343 cairo_point_t bot_left, top_right;
344 cairo_fixed_t top_y, bot_y;
347 for (n = 0; n < polygon->num_limits; n++) {
348 const cairo_box_t *limits = &polygon->limits[n];
349 cairo_fixed_t pleft, pright;
351 if (top >= limits->p2.y)
353 if (bottom <= limits->p1.y)
356 bot_left.x = limits->p1.x;
357 bot_left.y = limits->p2.y;
359 top_right.x = limits->p2.x;
360 top_right.y = limits->p1.y;
362 /* The useful region */
363 top_y = MAX (top, limits->p1.y);
364 bot_y = MIN (bottom, limits->p2.y);
366 /* The projection of the edge on the horizontal axis */
367 pleft = MIN (p1->x, p2->x);
368 pright = MAX (p1->x, p2->x);
370 if (limits->p1.x <= pleft && pright <= limits->p2.x) {
371 /* Projection of the edge completely contained in the box:
372 * clip vertically by restricting top and bottom */
374 _add_edge (polygon, p1, p2, top_y, bot_y, dir);
375 assert_last_edge_is_valid (polygon, limits);
376 } else if (pright <= limits->p1.x) {
377 /* Projection of the edge to the left of the box:
378 * replace with the left side of the box (clipped top/bottom) */
380 _add_edge (polygon, &limits->p1, &bot_left, top_y, bot_y, dir);
381 assert_last_edge_is_valid (polygon, limits);
382 } else if (limits->p2.x <= pleft) {
383 /* Projection of the edge to the right of the box:
384 * replace with the right side of the box (clipped top/bottom) */
386 _add_edge (polygon, &top_right, &limits->p2, top_y, bot_y, dir);
387 assert_last_edge_is_valid (polygon, limits);
389 /* The edge and the box intersect in a generic way */
390 cairo_fixed_t left_y, right_y;
391 cairo_bool_t top_left_to_bottom_right;
393 left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
395 right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
399 * The edge intersects the lines corresponding to the left
400 * and right sides of the limit box at left_y and right_y,
401 * but we need to add edges for the range from top_y to
404 * For both intersections, there are three cases:
406 * 1) It is outside the vertical range of the limit
407 * box. In this case we can simply further clip the
408 * edge we will be emitting (i.e. restrict its
409 * top/bottom limits to those of the limit box).
411 * 2) It is inside the vertical range of the limit
412 * box. In this case, we need to add the vertical edge
413 * connecting the correct vertex to the intersection,
414 * in order to preserve the winding count.
416 * 3) It is exactly on the box. In this case, do nothing.
418 * These operations restrict the active range (stored in
419 * top_y/bot_y) so that the p1-p2 edge is completely
420 * inside the box if it is clipped to this vertical range.
423 top_left_to_bottom_right = (p1->x < p2->x) == (p1->y < p2->y);
425 if (top_left_to_bottom_right) {
426 if (_cairo_edge_compute_intersection_x_for_y (p1, p2, left_y) < limits->p1.x)
429 left_y = MIN (left_y, bot_y);
430 if (top_y < left_y) {
431 _add_edge (polygon, &limits->p1, &bot_left,
433 assert_last_edge_is_valid (polygon, limits);
437 if (_cairo_edge_compute_intersection_x_for_y (p1, p2, right_y) > limits->p1.y)
440 right_y = MAX (right_y, top_y);
441 if (bot_y > right_y) {
442 _add_edge (polygon, &top_right, &limits->p2,
443 right_y, bot_y, dir);
444 assert_last_edge_is_valid (polygon, limits);
448 if (_cairo_edge_compute_intersection_x_for_y (p1, p2, right_y) > limits->p2.x)
451 right_y = MIN (right_y, bot_y);
452 if (top_y < right_y) {
453 _add_edge (polygon, &top_right, &limits->p2,
454 top_y, right_y, dir);
455 assert_last_edge_is_valid (polygon, limits);
459 if (_cairo_edge_compute_intersection_x_for_y (p1, p2, left_y) < limits->p1.x)
462 left_y = MAX (left_y, top_y);
463 if (bot_y > left_y) {
464 _add_edge (polygon, &limits->p1, &bot_left,
466 assert_last_edge_is_valid (polygon, limits);
471 if (top_y != bot_y) {
472 _add_edge (polygon, p1, p2, top_y, bot_y, dir);
473 assert_last_edge_is_valid (polygon, limits);
480 _cairo_polygon_add_edge (cairo_polygon_t *polygon,
481 const cairo_point_t *p1,
482 const cairo_point_t *p2,
485 /* drop horizontal edges */
490 const cairo_point_t *t;
491 t = p1, p1 = p2, p2 = t;
495 if (polygon->num_limits) {
496 if (p2->y <= polygon->limit.p1.y)
499 if (p1->y >= polygon->limit.p2.y)
502 _add_clipped_edge (polygon, p1, p2, p1->y, p2->y, dir);
504 _add_edge (polygon, p1, p2, p1->y, p2->y, dir);
508 _cairo_polygon_add_external_edge (void *polygon,
509 const cairo_point_t *p1,
510 const cairo_point_t *p2)
512 _cairo_polygon_add_edge (polygon, p1, p2, 1);
513 return _cairo_polygon_status (polygon);
517 _cairo_polygon_add_line (cairo_polygon_t *polygon,
518 const cairo_line_t *line,
522 /* drop horizontal edges */
523 if (line->p1.y == line->p2.y)
524 return CAIRO_STATUS_SUCCESS;
527 return CAIRO_STATUS_SUCCESS;
529 if (polygon->num_limits) {
530 if (line->p2.y <= polygon->limit.p1.y)
531 return CAIRO_STATUS_SUCCESS;
533 if (line->p1.y >= polygon->limit.p2.y)
534 return CAIRO_STATUS_SUCCESS;
536 _add_clipped_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
538 _add_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
540 return polygon->status;
544 _cairo_polygon_add_contour (cairo_polygon_t *polygon,
545 const cairo_contour_t *contour)
547 const struct _cairo_contour_chain *chain;
548 const cairo_point_t *prev = NULL;
551 if (contour->chain.num_points <= 1)
552 return CAIRO_INT_STATUS_SUCCESS;
554 prev = &contour->chain.points[0];
555 for (chain = &contour->chain; chain; chain = chain->next) {
556 for (i = 0; i < chain->num_points; i++) {
557 _cairo_polygon_add_edge (polygon, prev, &chain->points[i],
559 prev = &chain->points[i];
563 return polygon->status;
567 _cairo_polygon_translate (cairo_polygon_t *polygon, int dx, int dy)
571 dx = _cairo_fixed_from_int (dx);
572 dy = _cairo_fixed_from_int (dy);
574 polygon->extents.p1.x += dx;
575 polygon->extents.p2.x += dx;
576 polygon->extents.p1.y += dy;
577 polygon->extents.p2.y += dy;
579 for (n = 0; n < polygon->num_edges; n++) {
580 cairo_edge_t *e = &polygon->edges[n];