From dc4c7c14d07941a56e1378148c950fca63e39c7c Mon Sep 17 00:00:00 2001 From: Massimo Valentini Date: Mon, 1 Sep 2014 07:37:22 +0200 Subject: [PATCH] Bug 59098: segfault in cairo-polygon-intersect.c: active_edges() this implementation of the sweep_line treats edges to be translated upward and shrinked by 1 and 2 epsilon. It means that all edge lower vertices are considered positioned at an y = nominal y - 2 * epsilon, the upper points at y - epsilon. It follows that events having the same y are processed in the order: STOP prior than START prior than INTERSECTION (floored to integer). This way START and STOP events should find the active-edges list correctly sorted, and sorting the new edges also using slope_compare should not miss intersection, nor move the sweep line back and forth. --- src/cairo-polygon-intersect.c | 61 ++++++++++++++----------------------------- 1 file changed, 19 insertions(+), 42 deletions(-) diff --git a/src/cairo-polygon-intersect.c b/src/cairo-polygon-intersect.c index 2cd73d2..4b8210e 100644 --- a/src/cairo-polygon-intersect.c +++ b/src/cairo-polygon-intersect.c @@ -77,9 +77,9 @@ struct _cairo_bo_edge { #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1) typedef enum { - CAIRO_BO_EVENT_TYPE_STOP, - CAIRO_BO_EVENT_TYPE_INTERSECTION, - CAIRO_BO_EVENT_TYPE_START + CAIRO_BO_EVENT_TYPE_STOP = -1, + CAIRO_BO_EVENT_TYPE_START = 0, + CAIRO_BO_EVENT_TYPE_INTERSECTION = 1 } cairo_bo_event_type_t; typedef struct _cairo_bo_event { @@ -141,19 +141,6 @@ _line_compute_intersection_x_for_y (const cairo_line_t *line, return x; } -static inline int -_cairo_bo_point32_compare (cairo_bo_point32_t const *a, - cairo_bo_point32_t const *b) -{ - int cmp; - - cmp = a->y - b->y; - if (cmp) - return cmp; - - return a->x - b->x; -} - /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the * slope a is respectively greater than, equal to, or less than the * slope of b. @@ -444,7 +431,7 @@ edges_compare_x_for_y (const cairo_bo_edge_t *a, HAVE_BX = 0x2, HAVE_BOTH = HAVE_AX | HAVE_BX } have_ax_bx = HAVE_BOTH; - int32_t ax, bx; + int32_t ax = 0, bx = 0; if (y == a->edge.line.p1.y) ax = a->edge.line.p1.x; @@ -610,21 +597,14 @@ intersect_lines (cairo_bo_edge_t *a, den_det); if (_cairo_int64_eq (qr.rem, den_det)) return FALSE; -#if 0 - intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT; -#else + intersection->x.exactness = EXACT; if (! _cairo_int64_is_zero (qr.rem)) { if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem)) - qr.rem = _cairo_int64_negate (qr.rem); - qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2)); - if (_cairo_int64_ge (qr.rem, den_det)) { - qr.quo = _cairo_int64_add (qr.quo, - _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1)); - } else - intersection->x.exactness = INEXACT; + qr.quo = _cairo_int64_add (qr.quo, _cairo_int32_to_int64 (-1)); + + intersection->y.exactness = INEXACT; } -#endif intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo); /* y = det (a_det, dy1, b_det, dy2) / den_det */ @@ -633,21 +613,14 @@ intersect_lines (cairo_bo_edge_t *a, den_det); if (_cairo_int64_eq (qr.rem, den_det)) return FALSE; -#if 0 - intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT; -#else + intersection->y.exactness = EXACT; if (! _cairo_int64_is_zero (qr.rem)) { if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem)) - qr.rem = _cairo_int64_negate (qr.rem); - qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2)); - if (_cairo_int64_ge (qr.rem, den_det)) { - qr.quo = _cairo_int64_add (qr.quo, - _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1)); - } else - intersection->y.exactness = INEXACT; + qr.quo = _cairo_int64_add (qr.quo, _cairo_int32_to_int64 (-1)); + + intersection->y.exactness = INEXACT; } -#endif intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo); return TRUE; @@ -728,7 +701,7 @@ _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t *edge, top_x = _line_compute_intersection_x_for_y (&edge->edge.line, edge->edge.top); - return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0; + return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) >= 0; } else { /* cmp_bottom == 0 */ cairo_fixed_t bot_x; @@ -787,7 +760,7 @@ cairo_bo_event_compare (const cairo_bo_event_t *a, { int cmp; - cmp = _cairo_bo_point32_compare (&a->point, &b->point); + cmp = a->point.y - b->point.y; if (cmp) return cmp; @@ -795,7 +768,11 @@ cairo_bo_event_compare (const cairo_bo_event_t *a, if (cmp) return cmp; - return a - b; + cmp = a->point.x - b->point.x; + if (cmp) + return cmp; + + return a < b ? -1 : a == b ? 0 : 1; } static inline void -- 1.9.3