Can this line drawing algorithm be optimized? - SD

Question

For a project I have been working on, the ability to draw lines with a gradient (I.E. they change color over the interval they are drawn) would be very useful. I have an algorithm for this, as I will paste below, but it turns out to be DREADFULLY slow. I'm using the Bresenham algorithm to find each point, but I fear that I have reached the limits of software rendering. I've been using SDL2 thus far, and my line drawing algorithm appears 200x slower than SDL_RenderDrawLine. This is an estimate, and gathered from comparing the two functions' times to draw 10,000 lines. My function would take near 500ms, and SDL_RenderDrawLine did it in 2-3ms on my machine. I even tested the functions with horizontal lines to ensure it wasn't just a botched Bresenham algorithm, and similar slowness hatched. Unfortunately, SDL doesn't have an API for drawing lines with a gradient (or if it does, I'm blind). I knew that any software rendering would be significantly slower than hardware, but the shear magnitude of slowness caught me by surprise. Is there a method that can be used to speed this up? Have I just botched the drawing system beyond reason? I've considered saving an array of the pixels I wish to draw and then shoving them to the screen all at once, but I don't know how to do this with SDL2 and I can't seem to find the API in the wiki or documentation that allows for this. Would that even be faster?

Thanks for the consideration!

void DRW_LineGradient(SDL_Renderer* rend, SDL_Color c1, int x1, int y1, SDL_Color c2, int x2, int y2){
Uint8 tmpr, tmpg, tmpb, tmpa;
SDL_GetRenderDrawColor(rend, &tmpr, &tmpg, &tmpb, &tmpa);

int dy = y2 - y1;
int dx = x2 - x1;

/* Use doubles for a simple gradient */
double d = (abs(x1 - x2) > abs(y1 - y2) ? abs(x1 - x2) : abs(y1 - y2));
double dr = (c2.r - c1.r) / d;
double dg = (c2.g - c1.g) / d;
double db = (c2.b - c1.b) / d;
double da = (c2.a - c1.a) / d;

double r = c1.r, g = c1.g, b = c1.b, a = c1.a;

/* The line is vertical */
if (dx == 0) {
    int y;
    if (y2 >= y1) {
        for (y = y1; y <= y2; y++) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x1, y);
            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
    else{
        for (y = y1; y >= y2; y--) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x1, y);

            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
}
/* The line is horizontal */
if (dy == 0) {
    int x;
    if (x2 >= x1) {
        for (x = x1; x <= x2; x++) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x, y1);
            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
    else{
        for (x = x1; x >= x2; x--) {
            SDL_SetRenderDrawColor(rend, r, g, b, a);
            SDL_RenderDrawPoint(rend, x, y1);

            r += dr;
            g += dg;
            b += db;
            a += da;
        }
        return;
    }
}
/* The line has a slope of 1 or -1 */
if (abs(dy) == abs(dx)) {
    int xmult = 1, ymult = 1;
    if (dx < 0) {
        xmult = -1;
    }
    if (dy < 0) {
        ymult = -1;
    }
    int x = x1, y = y1;
    do {
        SDL_SetRenderDrawColor(rend, r, g, b, a);
        SDL_RenderDrawPoint(rend, x, y);
        x += xmult;
        y += ymult;
        r += dr;
        g += dg;
        b += db;
        a += da;
    } while (x != x2);
    return;
}

/* Use bresenham's algorithm to render the line */

int checky = dx >> 1;
int octant = findOctant((Line){x1, y1, x2, y2, dx, dy});

dy = abs(dy);
dx = abs(dx);
x2 = abs(x2 - x1) + x1;
y2 = abs(y2 - y1) + y1;

if (octant == 1 || octant == 2 || octant == 5 || octant == 6) {
    int tmp = dy;
    dy = dx;
    dx = tmp;
}

int x, y = 0;
for (x = 0; x <= dx; x++) {
    SDL_SetRenderDrawColor(rend, r, g, b, a);
    switch (octant) {
        case 0:
            SDL_RenderDrawPoint(rend, x + x1, y + y1);
            break;
        case 1:
            SDL_RenderDrawPoint(rend, y + x1, x + y1);
            break;
        case 2:
            SDL_RenderDrawPoint(rend, -y + x1, x + y1);
            break;
        case 3:
            SDL_RenderDrawPoint(rend, -x + x1, y + y1);
            break;
        case 4:
            SDL_RenderDrawPoint(rend, -x + x1, -y + y1);
            break;
        case 5:
            SDL_RenderDrawPoint(rend, -y + x1, -x + y1);
            break;
        case 6:
            SDL_RenderDrawPoint(rend, y + x1, -x + y1);
            break;
        case 7:
            SDL_RenderDrawPoint(rend, x + x1, -y + y1);
            break;
        default:
            break;
    }

    checky += dy;
    if (checky >= dx) {
        checky -= dx;
        y++;
    }

    r += dr;
    g += dg;
    b += db;
    a += da;
}

SDL_SetRenderDrawColor(rend, tmpr, tmpg, tmpb, tmpa);
}

SIDE NOTE:

I am reluctant to just move on to using OpenGL 3.0+ (Which I hear SDL2 has support for) because I don't know how to use it. Most tutorials I have found have explained the process of setting up the contexts with SDL and then coloring the screen one solid color, but then stop before explaining how to draw shapes and such. If someone could offer a good place to start learning about this, that would also be extremely helpful.

Answer 1

A lot of the overhead of your function is in repeated calls to SDL_RenderDrawPoint. This is (most likely) a generic function which needs to do the following operations:

1. check if x and y are in range for your current surface;
2. calculate the position inside the surface by multiplying y with surface->pitch and x with surface->format->BytesPerPixel;
3. check the current color model of the surface using SDL_PixelFormat;
4. convert the provided color to the correct format for this color model.

All of the above must be done for each single pixel. In addition, calling a function in itself is overhead -- small as it may be, it still needs to be done for each separate pixel, even if it is not visible.

You can:

1. omit x and y range checking if you are sure the line start and end points are always visible;
2. omit the convert-to-address step by calculating it once for the start of the line, then updating it by adding BytesPerPixel and pitch for a horizontal or vertical movement;
3. omit the convert-to-color model step by calculating the correct RGB values once (well, for a single color line, at least -- it's a bit harder for a gradient);
4. omit the function call by inlining the code to set a single pixel inside the line routine.

Another -- smaller -- issue: you call your own routine "Bresenham's ... but it isn't. Bresenham's optimization is actually that it avoids double calculations entirely (and its strongest point is that it still gives the mathematically correct output; something I would not count on when using double variables...).

The following routine does not check for range, color model, color values, or (indeed) if the surface should be locked. All of these operations should be ideally done outside the tight drawing loop. As it is, it assumes a 24-bit RGB color screen, with the Red byte first. [*]

I wrote this code for my current SDL environs, which is still SDL-1.0, but it should work for newer versions as well.

It is possible to use Bresenham's calculations for the delta-Red, delta-Green, and delta-Blue values as well, but I deliberately omitted them here :) They would add a lot of extra variables -- at a guess, three per color channel --, extra checks, and, not least of all, not really a visibly better quality. The difference between two successive values for Red, say 127 and 128, are usually too small to notice in a single pixel wide line. Besides, this small step would only occur if your line is at least 256 pixels long and you cover the entire range of Red from 0 to 255 in the gradient.

[*] If you are 100% sure you are targeting a specific screen model with your own program, you can use this (adjusted for that particular screen model, of course). It's feasible to target a couple of different screen models as well; write a customized routine for each, and use a function pointer to call the correct one.
Most likely this is how SDL_RenderDrawLine is able to squeeze out every millisecond of performance. Well worth writing all that code for a library (which will be used on a wide variety of screen set-ups), but most likely not for a single program such as yours. Notice I commented out a single range check, which falls back to a plain line routine if necessary. You could do the same for unusual or unexpected screen set-ups, and in that case simply call your own, slower, drawing routine. (Your routine is more robust as it uses SDL's native routines.)

The original line routine below was copied from The Internet more than a single decade ago, as I have been using it for ages. I'd gladly attribute it to someone; if anybody recognizes the comments (they are mostly as appeared in the original code), do post a comment.

void gradient_line (int x1,int y1,int x2,int y2,
    int r1,int g1, int b1,
    int r2,int g2, int b2)
{
    int     d;                      /* Decision variable                */
    int     dx,dy;                  /* Dx and Dy values for the line    */
    int     Eincr,NEincr;           /* Decision variable increments     */
    int     t;                      /* Counters etc.                    */
    unsigned char *ScrPos;
    int LineIncr;

    int rd,gd,bd;

    if (x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0 ||
        x1 >= SCREEN_WIDE || x2 >= SCREEN_WIDE ||
        y1 >= SCREEN_HIGH || y2 >= SCREEN_HIGH)
    {
        line (x1,y1, x2,y2, (r1<<16)+(g1<<8)+b1);
        return;
    }

    rd = (r2-r1)<<8;
    gd = (g2-g1)<<8;
    bd = (b2-b1)<<8;

    dx = x2 - x1;
    if (dx < 0)
        dx = -dx;
    dy = y2 - y1;
    if (dy < 0)
        dy = -dy;

    if (dy <= dx)
    {
        /* We have a line with a slope between -1 and 1
         *
         * Ensure that we are always scan converting the line from left to
         * right to ensure that we produce the same line from P1 to P0 as the
         * line from P0 to P1.
         */
        if (x2 < x1)
        {
            t = x2; x2 = x1; x1 = t;    /* Swap X coordinates           */
            t = y2; y2 = y1; y1 = t;    /* Swap Y coordinates           */
            /* Swap colors */
            r1 = r2;
            g1 = g2;
            b1 = b2;
            rd = -rd;
            gd = -gd;
            bd = -bd;
        }
        r1 <<= 8;
        g1 <<= 8;
        b1 <<= 8;

        if (y2 > y1)
        {
            LineIncr = screen->pitch;
        } else
        {
            LineIncr = -screen->pitch;
        }

        d = 2*dy - dx;              /* Initial decision variable value  */
        Eincr = 2*dy;               /* Increment to move to E pixel     */
        NEincr = 2*(dy - dx);       /* Increment to move to NE pixel    */

        ScrPos = (unsigned char *)(screen->pixels+screen->pitch*y1+x1*screen->format->BytesPerPixel);

        rd /= dx;
        gd /= dx;
        bd /= dx;

        /* Draw the first point at (x1,y1)  */
        ScrPos[0] = r1 >> 8;
        ScrPos[1] = g1 >> 8;
        ScrPos[2] = b1 >> 8;

        r1 += rd;
        g1 += gd;
        b1 += bd;

        /* Incrementally determine the positions of the remaining pixels */
        for (x1++; x1 <= x2; x1++)
        {
            if (d < 0)
            {
                d += Eincr;         /* Choose the Eastern Pixel         */
            } else
            {
                d += NEincr;        /* Choose the North Eastern Pixel   */
                ScrPos += LineIncr;
            }
            ScrPos[0] = r1>>8;
            ScrPos[1] = g1>>8;
            ScrPos[2] = b1>>8;

            ScrPos += screen->format->BytesPerPixel;

            r1 += rd;
            g1 += gd;
            b1 += bd;
        }
    } else
    {
        /* We have a line with a slope between -1 and 1 (ie: includes
         * vertical lines). We must swap our x and y coordinates for this.
         *
         * Ensure that we are always scan converting the line from left to
         * right to ensure that we produce the same line from P1 to P0 as the
         * line from P0 to P1.
         */

        if (y2 < y1)
        {
            t = x2; x2 = x1; x1 = t;    /* Swap X coordinates           */
            t = y2; y2 = y1; y1 = t;    /* Swap Y coordinates           */
            /* Swap colors */
            r1 = r2;
            g1 = g2;
            b1 = b2;
            rd = -rd;
            gd = -gd;
            bd = -bd;
        }

        r1 <<= 8;
        g1 <<= 8;
        b1 <<= 8;

        if (x2 > x1)
        {
            LineIncr = screen->format->BytesPerPixel;
        } else
        {
            LineIncr = -screen->format->BytesPerPixel;
        }

        d = 2*dx - dy;              /* Initial decision variable value  */
        Eincr = 2*dx;               /* Increment to move to E pixel     */
        NEincr = 2*(dx - dy);       /* Increment to move to NE pixel    */

        rd /= dy;
        gd /= dy;
        bd /= dy;

        /* Draw the first point at (x1,y1)  */
        ScrPos = (unsigned char *)(screen->pixels+screen->pitch*y1+x1*screen->format->BytesPerPixel);

        ScrPos[0] = r1 >> 8;
        ScrPos[1] = g1 >> 8;
        ScrPos[2] = b1 >> 8;

        r1 += rd;
        g1 += gd;
        b1 += bd;

        /* Incrementally determine the positions of the remaining pixels
         */

        for (y1++; y1 <= y2; y1++)
        {
            ScrPos += screen->pitch;
            if (d < 0)
            {
                d += Eincr;         /* Choose the Eastern Pixel         */
            } else
            {
                d += NEincr;        /* Choose the North Eastern Pixel   */
                ScrPos += LineIncr; /* (or SE pixel for dx/dy < 0!)     */
            }
            ScrPos[0] = r1 >> 8;
            ScrPos[1] = g1 >> 8;
            ScrPos[2] = b1 >> 8;

            r1 += rd;
            g1 += gd;
            b1 += bd;
        }
    }
}

.. and this is a section of a screenful of random lines with random colors, with on the right a close-up:

I did not time the difference between "native" SDL line drawing, your naive method, a pure solid color Bresenham's implementation and this one; then again, this ought not be very much slower than an SDL native line.