From 89408bc2c8c55c2cffa040a522a62597cba02248 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Tue, 30 Sep 2014 08:44:43 +0100 Subject: [PATCH] tor: Fix loss of precision from projection onto sample grid The goal is to preserve the precision in the gradients of the edges and only apply the projection into the final cell location. We also include the half-subrow offset as spotted by Massimo. References: https://bugs.freedesktop.org/show_bug.cgi?id=84396 Testcase: coverage-rhombus Signed-off-by: Chris Wilson --- src/cairo-tor-scan-converter.c | 286 ++++++++++++++++++++++------------------- 1 file changed, 152 insertions(+), 134 deletions(-) diff --git a/src/cairo-tor-scan-converter.c b/src/cairo-tor-scan-converter.c index 89ef20f..a26a433 100644 --- a/src/cairo-tor-scan-converter.c +++ b/src/cairo-tor-scan-converter.c @@ -315,7 +315,7 @@ struct edge { /* Original sign of the edge: +1 for downwards, -1 for upwards * edges. */ int dir; - int vertical; + int cell; /* Current x coordinate while the edge is on the active * list. Initialised to the x coordinate of the top of the @@ -473,22 +473,6 @@ floored_divrem(int a, int b) return qr; } -/* Compute the floored division (x*a)/b. Assumes / and % perform symmetric - * division. */ -static struct quorem -floored_muldivrem(int x, int a, int b) -{ - struct quorem qr; - long long xa = (long long)x*a; - qr.quo = xa/b; - qr.rem = xa%b; - if ((xa>=0) != (b>=0) && qr.rem) { - qr.quo -= 1; - qr.rem += b; - } - return qr; -} - static struct _pool_chunk * _pool_chunk_init( struct _pool_chunk *p, @@ -808,7 +792,7 @@ cell_list_render_edge(struct cell_list *cells, struct quorem x1 = edge->x; struct quorem x2 = x1; - if (! edge->vertical) { + if (edge->dy == 0) { x2.quo += edge->dxdy_full.quo; x2.rem += edge->dxdy_full.rem; if (x2.rem >= 0) { @@ -976,78 +960,19 @@ _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon, *ptail = e; } -inline static void -polygon_add_edge (struct polygon *polygon, - const cairo_edge_t *edge) -{ - struct edge *e; - grid_scaled_x_t dx; - grid_scaled_y_t dy; - grid_scaled_y_t ytop, ybot; - grid_scaled_y_t ymin = polygon->ymin; - grid_scaled_y_t ymax = polygon->ymax; - - if (unlikely (edge->top >= ymax || edge->bottom <= ymin)) - return; - - e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge)); - - dx = edge->line.p2.x - edge->line.p1.x; - dy = edge->line.p2.y - edge->line.p1.y; - e->dy = dy; - e->dir = edge->dir; - - ytop = edge->top >= ymin ? edge->top : ymin; - ybot = edge->bottom <= ymax ? edge->bottom : ymax; - e->ytop = ytop; - e->height_left = ybot - ytop; - - if (dx == 0) { - e->vertical = TRUE; - e->x.quo = edge->line.p1.x; - e->x.rem = 0; - e->dxdy.quo = 0; - e->dxdy.rem = 0; - e->dxdy_full.quo = 0; - e->dxdy_full.rem = 0; - } else { - e->vertical = FALSE; - e->dxdy = floored_divrem (dx, dy); - if (ytop == edge->line.p1.y) { - e->x.quo = edge->line.p1.x; - e->x.rem = 0; - } else { - e->x = floored_muldivrem (ytop - edge->line.p1.y, dx, dy); - e->x.quo += edge->line.p1.x; - } - - if (e->height_left >= GRID_Y) { - e->dxdy_full = floored_muldivrem (GRID_Y, dx, dy); - } else { - e->dxdy_full.quo = 0; - e->dxdy_full.rem = 0; - } - } - - _polygon_insert_edge_into_its_y_bucket (polygon, e); - - e->x.rem -= dy; /* Bias the remainder for faster - * edge advancement. */ -} - static void active_list_reset (struct active_list *active) { - active->head.vertical = 1; active->head.height_left = INT_MAX; - active->head.x.quo = INT_MIN; + active->head.dy = 0; + active->head.cell = INT_MIN; active->head.prev = NULL; active->head.next = &active->tail; active->tail.prev = &active->head; active->tail.next = NULL; - active->tail.x.quo = INT_MAX; + active->tail.cell = INT_MAX; active->tail.height_left = INT_MAX; - active->tail.vertical = 1; + active->tail.dy = 0; active->min_height = 0; active->is_vertical = 1; } @@ -1084,7 +1009,7 @@ merge_sorted_edges (struct edge *head_a, struct edge *head_b) prev = head_a->prev; next = &head; - if (head_a->x.quo <= head_b->x.quo) { + if (head_a->cell <= head_b->cell) { head = head_a; } else { head = head_b; @@ -1093,8 +1018,8 @@ merge_sorted_edges (struct edge *head_a, struct edge *head_b) } do { - x = head_b->x.quo; - while (head_a != NULL && head_a->x.quo <= x) { + x = head_b->cell; + while (head_a != NULL && head_a->cell <= x) { prev = head_a; next = &head_a->next; head_a = head_a->next; @@ -1106,8 +1031,8 @@ merge_sorted_edges (struct edge *head_a, struct edge *head_b) return head; start_with_b: - x = head_a->x.quo; - while (head_b != NULL && head_b->x.quo <= x) { + x = head_a->cell; + while (head_b != NULL && head_b->cell <= x) { prev = head_b; next = &head_b->next; head_b = head_b->next; @@ -1153,7 +1078,7 @@ sort_edges (struct edge *list, } remaining = head_other->next; - if (list->x.quo <= head_other->x.quo) { + if (list->cell <= head_other->cell) { *head_out = list; head_other->next = NULL; } else { @@ -1197,7 +1122,7 @@ can_do_full_row (struct active_list *active) while (NULL != e) { if (e->height_left < min_height) min_height = e->height_left; - is_vertical &= e->vertical; + is_vertical &= e->dy == 0; e = e->next; } @@ -1210,19 +1135,27 @@ can_do_full_row (struct active_list *active) /* Check for intersections as no edges end during the next row. */ for (e = active->head.next; e != &active->tail; e = e->next) { - struct quorem x = e->x; + int cell; - if (! e->vertical) { + if (e->dy) { + struct quorem x = e->x; x.quo += e->dxdy_full.quo; x.rem += e->dxdy_full.rem; - if (x.rem >= 0) - ++x.quo; - } + if (x.rem < 0) { + x.quo--; + x.rem += e->dy; + } else if (x.rem >= e->dy) { + x.quo++; + x.rem -= e->dy; + } + cell = x.quo + (x.rem >= e->dy/2); + } else + cell = e->cell; - if (x.quo < prev_x) + if (cell < prev_x) return 0; - prev_x = x.quo; + prev_x = cell; } return 1; @@ -1256,7 +1189,7 @@ polygon_fill_buckets (struct active_list *active, buckets[suby] = edge; if (edge->height_left < min_height) min_height = edge->height_left; - is_vertical &= edge->vertical; + is_vertical &= edge->dy == 0; edge = next; } @@ -1264,6 +1197,25 @@ polygon_fill_buckets (struct active_list *active, active->min_height = min_height; } +static void step (struct edge *edge) +{ + if (edge->dy == 0) + return; + + edge->x.quo += edge->dxdy.quo; + edge->x.rem += edge->dxdy.rem; + if (edge->x.rem < 0) { + --edge->x.quo; + edge->x.rem += edge->dy; + } else if (edge->x.rem >= edge->dy) { + ++edge->x.quo; + edge->x.rem -= edge->dy; + } + assert (edge->x.rem >= 0 && edge->x.rem < edge->dy); + + edge->cell = edge->x.quo + (edge->x.rem >= edge->dy/2); +} + inline static void sub_row (struct active_list *active, struct cell_list *coverages, @@ -1277,29 +1229,24 @@ sub_row (struct active_list *active, while (&active->tail != edge) { struct edge *next = edge->next; - int xend = edge->x.quo; + int xend = edge->cell; if (--edge->height_left) { - edge->x.quo += edge->dxdy.quo; - edge->x.rem += edge->dxdy.rem; - if (edge->x.rem >= 0) { - ++edge->x.quo; - edge->x.rem -= edge->dy; - } + step (edge); - if (edge->x.quo < prev_x) { + if (edge->cell < prev_x) { struct edge *pos = edge->prev; pos->next = next; next->prev = pos; do { pos = pos->prev; - } while (edge->x.quo < pos->x.quo); + } while (edge->cell < pos->cell); pos->next->prev = edge; edge->next = pos->next; edge->prev = pos; pos->next = edge; } else - prev_x = edge->x.quo; + prev_x = edge->cell; active->min_height = -1; } else { edge->prev->next = next; @@ -1308,7 +1255,7 @@ sub_row (struct active_list *active, winding += edge->dir; if ((winding & mask) == 0) { - if (next->x.quo != xend) { + if (next->cell != xend) { cell_list_add_subspan (coverages, xstart, xend); xstart = INT_MIN; } @@ -1331,14 +1278,21 @@ inline static void dec (struct active_list *a, struct edge *e, int h) inline static void full_step (struct edge *e) { - if (! e->vertical) { - e->x.quo += e->dxdy_full.quo; - e->x.rem += e->dxdy_full.rem; - if (e->x.rem >= 0) { - ++e->x.quo; - e->x.rem -= e->dy; - } + if (e->dy == 0) + return; + + e->x.quo += e->dxdy_full.quo; + e->x.rem += e->dxdy_full.rem; + if (e->x.rem < 0) { + e->x.quo--; + e->x.rem += e->dy; + } else if (e->x.rem >= e->dy) { + ++e->x.quo; + e->x.rem -= e->dy; } + assert (e->x.rem >= 0 && e->x.rem < e->dy); + + e->cell = e->x.quo + (e->x.rem >= e->dy/2); } static void @@ -1360,7 +1314,7 @@ full_row (struct active_list *active, dec (active, right, GRID_Y); winding += right->dir; - if ((winding & mask) == 0 && right->next->x.quo != right->x.quo) + if ((winding & mask) == 0 && right->next->cell != right->cell) break; full_step (right); @@ -1482,10 +1436,92 @@ glitter_scan_converter_reset( #define INPUT_TO_GRID_general(in, out, grid_scale) do { \ long long tmp__ = (long long)(grid_scale) * (in); \ + tmp__ += 1 << (GLITTER_INPUT_BITS-1); \ tmp__ >>= GLITTER_INPUT_BITS; \ (out) = tmp__; \ } while (0) +inline static void +polygon_add_edge (struct polygon *polygon, + const cairo_edge_t *edge) +{ + struct edge *e; + grid_scaled_y_t ytop, ybot; + const cairo_point_t *p1, *p2; + + INPUT_TO_GRID_Y (edge->top, ytop); + if (ytop < polygon->ymin) + ytop = polygon->ymin; + + INPUT_TO_GRID_Y (edge->bottom, ybot); + if (ybot > polygon->ymax) + ybot = polygon->ymax; + + if (ybot <= ytop) + return; + + e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge)); + + e->ytop = ytop; + e->height_left = ybot - ytop; + if (edge->line.p2.y > edge->line.p1.y) { + e->dir = edge->dir; + p1 = &edge->line.p1; + p2 = &edge->line.p2; + } else { + e->dir = -edge->dir; + p1 = &edge->line.p2; + p2 = &edge->line.p1; + } + + if (p2->x == p1->x) { + e->cell = p1->x; + e->x.quo = e->x.rem = 0; + e->dxdy.quo = e->dxdy.rem = 0; + e->dxdy_full.quo = e->dxdy_full.rem = 0; + e->dy = 0; + } else { + int64_t Ex, Ey, tmp; + + Ex = (int64_t)(p2->x - p1->x) * GRID_X; + Ey = (int64_t)(p2->y - p1->y) * GRID_Y * (2 << GLITTER_INPUT_BITS); + + e->dxdy.quo = Ex * (2 << GLITTER_INPUT_BITS) / Ey; + e->dxdy.rem = Ex * (2 << GLITTER_INPUT_BITS) % Ey; + + tmp = (int64_t)(2*ytop + 1) << GLITTER_INPUT_BITS; + tmp -= (int64_t)p1->y * GRID_Y * 2; + tmp *= Ex; + e->x.quo = tmp / Ey; + e->x.rem = tmp % Ey; + + tmp = (int64_t)p1->x * GRID_X; + e->x.quo += tmp >> GLITTER_INPUT_BITS; + e->x.rem += ((tmp & ((1 << GLITTER_INPUT_BITS) - 1)) * Ey) / (1 << GLITTER_INPUT_BITS); + + if (e->x.rem < 0) { + e->x.quo--; + e->x.rem += Ey; + } else if (e->x.rem >= Ey) { + e->x.quo++; + e->x.rem -= Ey; + } + assert (e->x.rem >= 0 && e->x.rem < Ey); + + if (e->height_left >= GRID_Y) { + tmp = Ex * (2 * GRID_Y << GLITTER_INPUT_BITS); + e->dxdy_full.quo = tmp / Ey; + e->dxdy_full.rem = tmp % Ey; + } else + e->dxdy_full.quo = e->dxdy_full.rem = 0; + + e->cell = e->x.quo + (e->x.rem >= Ey/2); + e->dy = Ey; + } + + _polygon_insert_edge_into_its_y_bucket (polygon, e); +} + /* Add a new polygon edge from pixel (x1,y1) to (x2,y2) to the scan * converter. The coordinates represent pixel positions scaled by * 2**GLITTER_PIXEL_BITS. If this function fails then the scan @@ -1495,25 +1531,7 @@ I void glitter_scan_converter_add_edge (glitter_scan_converter_t *converter, const cairo_edge_t *edge) { - cairo_edge_t e; - - INPUT_TO_GRID_Y (edge->top, e.top); - INPUT_TO_GRID_Y (edge->bottom, e.bottom); - if (e.top >= e.bottom) - return; - - /* XXX: possible overflows if GRID_X/Y > 2**GLITTER_INPUT_BITS */ - INPUT_TO_GRID_Y (edge->line.p1.y, e.line.p1.y); - INPUT_TO_GRID_Y (edge->line.p2.y, e.line.p2.y); - if (e.line.p1.y == e.line.p2.y) - e.line.p2.y++; /* little fudge to prevent a div-by-zero */ - - INPUT_TO_GRID_X (edge->line.p1.x, e.line.p1.x); - INPUT_TO_GRID_X (edge->line.p2.x, e.line.p2.x); - - e.dir = edge->dir; - - polygon_add_edge (converter->polygon, &e); + polygon_add_edge (converter->polygon, edge); } static void -- 2.1.1