SDL: Added line drawing using Bresenham's line algorithm (thanks @rtrussell!)

From 9f56faeedc70e0ea1a8efd38b0c15fab269ee610 Mon Sep 17 00:00:00 2001
From: Sam Lantinga <[EMAIL REDACTED]>
Date: Sat, 8 Jan 2022 10:59:31 -0800
Subject: [PATCH] Added line drawing using Bresenham's line algorithm (thanks
 @rtrussell!)

---
 src/render/SDL_render.c | 131 +++++++++++++++++++++++++++++++++++++---
 1 file changed, 123 insertions(+), 8 deletions(-)

diff --git a/src/render/SDL_render.c b/src/render/SDL_render.c
index 1819f1f8ced..dcef14ae44c 100644
--- a/src/render/SDL_render.c
+++ b/src/render/SDL_render.c
@@ -2782,13 +2782,129 @@ SDL_RenderDrawLineF(SDL_Renderer * renderer, float x1, float y1, float x2, float
     return SDL_RenderDrawLinesF(renderer, points, 2);
 }
 
+static int plotLineLow(SDL_Renderer *renderer, float x0, float y0, float x1, float y1)
+{
+    int retval = 0;
+    float dx = x1 - x0;
+    float dy = y1 - y0;
+    int yi = 1;
+    float x, y, D;
+    int count = (x1 - x0 + 1);
+    SDL_bool isstack;
+    SDL_FPoint *points = SDL_small_alloc(SDL_FPoint, count, &isstack);
+    SDL_FPoint *tmp = points;
+
+    if (dy < 0) {
+        yi = -1;
+        dy = -dy;
+    }
+
+    D = (2 * dy) - dx;
+    y = y0;
+    for (x = x0; x <= x1; ++x) {
+        tmp->x = x;
+        tmp->y = y;
+        tmp++;
+        if (D > 0) {
+            y += yi;
+            D += 2 * (dy - dx);
+        } else {
+            D += 2*dy;
+        }
+    }
+
+    if (renderer->scale.x != 1.0f || renderer->scale.y != 1.0f) {
+        retval = RenderDrawPointsWithRectsF(renderer, points, count);
+    } else {
+        retval = QueueCmdDrawPoints(renderer, points, count);
+    }
+
+    SDL_small_free(points, isstack);
+
+    return retval;
+}
+
+static int plotLineHigh(SDL_Renderer *renderer, float x0, float y0, float x1, float y1)
+{
+    int retval = 0;
+    float dx = x1 - x0;
+    float dy = y1 - y0;
+    int xi = 1;
+    float x, y, D;
+    int count = (y1 - y0 + 1);
+    SDL_bool isstack;
+    SDL_FPoint *points = SDL_small_alloc(SDL_FPoint, count, &isstack);
+    SDL_FPoint *tmp = points;
+
+    if (dx < 0) {
+        xi = -1;
+        dx = -dx;
+    }
+
+    D = (2 * dx) - dy;
+    x = x0;
+    for (y = y0; y <= y1; ++y) {
+        tmp->x = x;
+        tmp->y = y;
+        tmp++;
+        if (D > 0) {
+            x += xi;
+            D += 2 * (dx - dy);
+        } else {
+            D += 2*dx;
+        }
+    }
+
+    if (renderer->scale.x != 1.0f || renderer->scale.y != 1.0f) {
+        retval = RenderDrawPointsWithRectsF(renderer, points, count);
+    } else {
+        retval = QueueCmdDrawPoints(renderer, points, count);
+    }
+
+    SDL_small_free(points, isstack);
+
+    return retval;
+}
+
+static int plotLineBresenham(SDL_Renderer *renderer, float x0, float y0, float x1, float y1)
+{
+    if (SDL_fabs(y1 - y0) < SDL_fabs(x1 - x0)) {
+        if (x0 > x1) {
+            return plotLineLow(renderer, x1, y1, x0, y0);
+        } else {
+            return plotLineLow(renderer, x0, y0, x1, y1);
+        }
+    } else {
+        if (y0 > y1) {
+            return plotLineHigh(renderer, x1, y1, x0, y0);
+        } else {
+            return plotLineHigh(renderer, x0, y0, x1, y1);
+        }
+    }
+}
+
+static int
+RenderDrawLinesWithPointsF(SDL_Renderer * renderer,
+                          const SDL_FPoint * points, const int count)
+{
+    int i;
+    int retval = 0;
+
+    for (i = 0; i < count-1; ++i, ++points) {
+        retval += plotLineBresenham(renderer, points[0].x, points[0].y, points[1].x, points[1].y);
+    }
+    if (retval < 0) {
+        retval = -1;
+    }
+    return retval;
+}
+
 static int
 RenderDrawLinesWithRectsF(SDL_Renderer * renderer,
                           const SDL_FPoint * points, const int count)
 {
     SDL_FRect *frect;
     SDL_FRect *frects;
-    SDL_FPoint fpoints[2];
     int i, nrects = 0;
     int retval = 0;
     SDL_bool isstack;
@@ -2818,12 +2934,7 @@ RenderDrawLinesWithRectsF(SDL_Renderer * renderer,
             frect->w = (maxX - minX + 1) * renderer->scale.x;
             frect->h = renderer->scale.y;
         } else {
-            /* FIXME: We can't use a rect for this line... */
-            fpoints[0].x = points[i].x * renderer->scale.x;
-            fpoints[0].y = points[i].y * renderer->scale.y;
-            fpoints[1].x = points[i+1].x * renderer->scale.x;
-            fpoints[1].y = points[i+1].y * renderer->scale.y;
-            retval += QueueCmdDrawLines(renderer, fpoints, 2);
+            retval += RenderDrawLinesWithPointsF(renderer, &points[i], 2);
         }
     }
 
@@ -2886,6 +2997,7 @@ SDL_RenderDrawLinesF(SDL_Renderer * renderer,
                      const SDL_FPoint * points, int count)
 {
     int retval = 0;
+    int use_renderpoints;
     int use_rendergeometry;
 
     CHECK_RENDERER_MAGIC(renderer, -1);
@@ -2904,9 +3016,12 @@ SDL_RenderDrawLinesF(SDL_Renderer * renderer,
     }
 #endif
 
+    use_renderpoints = 1;
     use_rendergeometry = 1;
 
-    if (use_rendergeometry) {
+    if (use_renderpoints) {
+        retval = RenderDrawLinesWithPointsF(renderer, points, count);
+    } else if (use_rendergeometry) {
         SDL_bool isstack1;
         SDL_bool isstack2;
         const float scale_x = renderer->scale.x;