Attachment 91802 Details for Bug 68524 – First attempt at handling diagonal lines in poly_line code

[patch] First attempt at handling diagonal lines in poly_line code

0001-polylines-Handle-diagonal-lines.patch (text/plain), 7.66 KB, created by Aaron Watry on 2014-01-10 01:28:14 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Aaron Watry

Created: 2014-01-10 01:28:14 UTC

Size: 7.66 KB

patch

obsolete

>From 88923bf1fc132e77da3b31289a7ba66a3047cdcd Mon Sep 17 00:00:00 2001
>From: Aaron Watry <awatry@gmail.com>
>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 <awatry@gmail.com>
>---
> 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
>

Actions: View | Splinter Review

Attachments on bug 68524: 84596 | 84597 | 91802 | 91804 | 91813 | 91814 | 92009 | 92331 | 92332 | 92333 | 92337 | 92338 | 97702

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.