From 88923bf1fc132e77da3b31289a7ba66a3047cdcd Mon Sep 17 00:00:00 2001 From: Aaron Watry Date: Thu, 9 Jan 2014 19:16:31 -0600 Subject: [PATCH] polylines: Handle diagonal lines Split a diagonal line into 2 or more horizontal/vertical lines. We want to split the line into as small a number of segments as possible. E.g. line from (x,y) of (1,1)->(5,2) with a slope of .25 would be split into: (1,1)->(2,1), (3,2)->(5,2) This is basically an implementation of Bresenham's line algorithm but with FP instead of integers. If the line's horizontal-ish, then iterate over the x values, and every time the rounded y value changes, start a new rectangle. If abs(slope) is > 1, then iterate over the y values instead. If the slope is == 1, then we're basically stuck drawing a bunch of points. Partially Fixes: https://bugs.freedesktop.org/show_bug.cgi?id=68524 Signed-off-by: Aaron Watry --- src/glamor_polylines.c | 166 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 146 insertions(+), 20 deletions(-) diff --git a/src/glamor_polylines.c b/src/glamor_polylines.c index e723e95..8891d3f 100644 --- a/src/glamor_polylines.c +++ b/src/glamor_polylines.c @@ -33,6 +33,126 @@ * GC PolyFillRect implementation, taken straight from fb_fill.c */ +static void _draw_line(xRectangle *rects, int rect, int x1, int y1, int x2, int y2){ + rects[rect].x = x1 < x2 ? x1 : x2; + rects[rect].y = y1 < y2 ? y1 : y2; + rects[rect].width = abs(x1 - x2) + 1; + rects[rect].height = abs(y1 - y2) + 1; +} + +static xRectangle *_emit_line(xRectangle *rects, int *rects_cnt, int *rect, int x1, int y1, int x2, int y2){ + *rects_cnt += 1; + rects = realloc(rects, sizeof(xRectangle) * *rects_cnt); + _draw_line(rects, *rect, x1, y1, x2, y2); + *rect += 1; + return rects; +} + +static void _init_points(int *last_x, int *last_y, int cur_x, int cur_y, int *last_start_x, int *last_start_y){ + *last_x = *last_start_x = cur_x; + *last_y = *last_start_y = cur_y; +} + +static xRectangle *_next_point(xRectangle *rects, int *rects_cnt, int *rect, int cur_x, int cur_y, int *last_x, int *last_y, int *last_start_x, int *last_start_y, int steep){ + if ((steep && *last_x != cur_x) || (!steep && *last_y != cur_y)){ + //emit a line from last_start_x,last_start_y to last_x,last_y + rects = _emit_line(rects, rects_cnt, rect, *last_start_x, *last_start_y, *last_x, *last_y); + *last_start_x = cur_x; + *last_start_y = cur_y; + } + *last_x = cur_x; + *last_y = cur_y; + return rects; +} + +/** + * We need to split the line into as small a number of segments as + * possible. + * + * E.g. line from (x,y) of (1,1)->(5,2) with a slope of .25 + + * would be split into two lines: + * (1,1)->(2,1), (3,2)->(5,2) + * + * This is basically an implementation of Bresenham's line algorithm but with + * FP for now, since I'm lazy. + * + * If the line's horizontal-ish, then iterate over the x values, and + * every time the rounded y value changes, start a new rectangle. + * If abs(slope) is > 1, then iterate over the y values instead. + * If the slope is == 1, then we're basically stuck drawing a bunch of points. + * + * @param rects Allocated list of xRectangle storage. grows when line is split + * @param rect_cnt Number of elements allocated in list + * @param rect Current index in list. modified as needed when the line is split + * @param x1 - X Coordinate of first point in line + * @param y1 - Y Coordinate of first point in line + * @param x2 - X Coordinate of second point in line + * @param y2 - Y Coordinate of second point in line + * @return rects - reallocated as needed... grows 1 rectangle every time the line splits + */ +static xRectangle *_glamor_diagonal_line(xRectangle *rects, int *rect_cnt, int *rect, int x1, int y1, int x2, int y2){ + float slope = (float)(y2-y1) / (float)(x2-x1); + int vert = fabs(slope) > 1; + int i; + + int cur_x, cur_y; //Current point being processed + int last_x, last_y; //Last point that was processed + int last_start_x, last_start_y; //Last x,y of a started line + + if (vert){ + //If we're dealing with slope > 1, then swap the x/y coords to make the + //line more horizontal than vertical. Reduces looping code + int temp = x1; + x1 = y1; + y1 = temp; + + temp = x2; + x2 = y2; + y2 = temp; + + //and recalculate the slope. + slope = (float)(y2-y1) / (float)(x2-x1); + } + if (x1 > x2){ + //And now, if the points go right to left, swap them. + int temp = x1; + x1 = x2; + x2 = temp; + + temp = y1; + y1 = y2; + y2 = temp; + } + cur_x = x1; + cur_y = y1; + + //Now just iterate over the range from x1 to x2 and calculate the y values + //When plotting the points, if (vert==true), then just swap the cur_x/cur_y values + if (vert) + _init_points(&last_x, &last_y, y1, x1, &last_start_x, &last_start_y); + else + _init_points(&last_x, &last_y, x1, y1, &last_start_x, &last_start_y); + + for(i = 0; i <= x2-x1; i++){ + cur_x = x1+i; + cur_y = y1 + round(((float)i)*slope); + if (vert) + rects = _next_point(rects, rect_cnt, rect, cur_y, cur_x, &last_x, &last_y, &last_start_x, &last_start_y, vert); + else + rects = _next_point(rects, rect_cnt, rect, cur_x, cur_y, &last_x, &last_y, &last_start_x, &last_start_y, vert); + } + + //And now finalize the last line segment using the space that was originally + //allocated for a horizontal/vertical line slot. + if (vert) + _draw_line(rects, *rect, last_start_x, last_start_y, cur_y, cur_x); + else + _draw_line(rects, *rect, last_start_x, last_start_y, cur_x, cur_y); + + return rects; +} + /** * glamor_poly_lines() checks if it can accelerate the lines as a group of * horizontal or vertical lines (rectangles), and uses existing rectangle fill @@ -44,7 +164,7 @@ _glamor_poly_lines(DrawablePtr drawable, GCPtr gc, int mode, int n, { xRectangle *rects; int x1, x2, y1, y2; - int i; + int i, rect_cnt, rect; /* Don't try to do wide lines or non-solid fill style. */ if (gc->lineWidth != 0) { @@ -59,11 +179,12 @@ _glamor_poly_lines(DrawablePtr drawable, GCPtr gc, int mode, int n, gc->lineStyle); goto fail; } - rects = malloc(sizeof(xRectangle) * (n - 1)); + rect_cnt = n-1; + rects = malloc(sizeof(xRectangle) * rect_cnt); x1 = points[0].x; y1 = points[0].y; /* If we have any non-horizontal/vertical, fall back. */ - for (i = 0; i < n - 1; i++) { + for (rect = i = 0; i < n - 1; i++, rect++) { if (mode == CoordModePrevious) { x2 = x1 + points[i + 1].x; y2 = y1 + points[i + 1].y; @@ -72,29 +193,34 @@ _glamor_poly_lines(DrawablePtr drawable, GCPtr gc, int mode, int n, y2 = points[i + 1].y; } if (x1 != x2 && y1 != y2) { - free(rects); - glamor_fallback("stub diagonal poly_line\n"); - goto fail; - } - if (x1 < x2) { - rects[i].x = x1; - rects[i].width = x2 - x1 + 1; - } else { - rects[i].x = x2; - rects[i].width = x1 - x2 + 1; - } - if (y1 < y2) { - rects[i].y = y1; - rects[i].height = y2 - y1 + 1; + //For a diagonal line, for every line segment after the first one + //in the line, we will bump rect_cnt and realloc rects + rects = _glamor_diagonal_line(rects, &rect_cnt, &rect, x1, y1, x2, y2); + + //free(rects); + //glamor_fallback("stub diagonal poly_line\n"); + //goto fail; } else { - rects[i].y = y2; - rects[i].height = y1 - y2 + 1; + if (x1 < x2) { + rects[rect].x = x1; + rects[rect].width = x2 - x1 + 1; + } else { + rects[rect].x = x2; + rects[rect].width = x1 - x2 + 1; + } + if (y1 < y2) { + rects[rect].y = y1; + rects[rect].height = y2 - y1 + 1; + } else { + rects[rect].y = y2; + rects[rect].height = y1 - y2 + 1; + } } x1 = x2; y1 = y2; } - gc->ops->PolyFillRect(drawable, gc, n - 1, rects); + gc->ops->PolyFillRect(drawable, gc, rect_cnt, rects); free(rects); return TRUE; -- 1.8.3.2