DS Log

In my blog, I delve into the world of programming web technologies, Linux, Unix-like, and graphic design using free tools on Linux.

Monday, December 29, 2025

Bresenham's line algorithm

Bresenham's line algorithm is a highly efficient computer graphics method for drawing straight lines on pixel-based displays (rasters) by selecting the best pixels to approximate the true line, using only fast integer arithmetic (addition, subtraction, bit shifts) instead of slower floating-point math. It works by calculating an "error" or "decision" parameter at each step to decide whether the next pixel should be at the current Y-level or moved up (or down) by one pixel, efficiently creating the illusion of a continuous line by minimizing error.

// Compile with:
// gcc -std=c99 -O2 -Wall main.c -o main `sdl2-config --cflags --libs`
// gcc -std=c99 -O2 -Wall main.c -o main $(pkg-config --cflags --libs sdl2)

#include <SDL.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define WIDTH 640
#define HEIGHT 480

// Bresenham's line algorithm to draw a line from (x0,y0) to (x1,y1)
void drawLine(Uint32* pixels, int x0, int y0, int x1, int y1, Uint32 color)
{
    // Clamp coordinates to window bounds
    if (x0 < 0) x0 = 0; 
    if (x0 >= WIDTH) x0 = WIDTH - 1;
    if (y0 < 0) y0 = 0; 
    if (y0 >= HEIGHT) y0 = HEIGHT - 1;
    if (x1 < 0) x1 = 0; 
    if (x1 >= WIDTH) x1 = WIDTH - 1;
    if (y1 < 0) y1 = 0; 
    if (y1 >= HEIGHT) y1 = HEIGHT - 1;

    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sx = (x0 < x1) ? 1 : -1;
    int sy = (y0 < y1) ? 1 : -1;
    int err = dx - dy;

    while (1)
    {
        if (x0 >= 0 && x0 < WIDTH && y0 >= 0 && y0 < HEIGHT)
            pixels[y0 * WIDTH + x0] = color;

        if (x0 == x1 && y0 == y1) break;

        int e2 = 2 * err;
        if (e2 > -dy)
        {
            err -= dy;
            x0 += sx;
        }
        if (e2 < dx)
        {
            err += dx;
            y0 += sy;
        }
    }
}

int main(int argc, char* argv[])
{
    if (SDL_Init(SDL_INIT_VIDEO) != 0)
    {
        fprintf(stderr, "SDL_Init Error: %s\n", SDL_GetError());
        return 1;
    }

    SDL_Window* window = SDL_CreateWindow("Simple Paint - Connected Lines",
        SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, WIDTH, HEIGHT, SDL_WINDOW_SHOWN);
    if (!window)
    {
        fprintf(stderr, "SDL_CreateWindow Error: %s\n", SDL_GetError());
        SDL_Quit();
        return 1;
    }

    SDL_Renderer* renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
    SDL_Texture* texture = SDL_CreateTexture(renderer,
        SDL_PIXELFORMAT_ARGB8888, SDL_TEXTUREACCESS_STREAMING, WIDTH, HEIGHT);

    Uint32* pixels = malloc(WIDTH * HEIGHT * sizeof(Uint32));
    if (!pixels)
    {
        fprintf(stderr, "Failed to allocate pixel buffer\n");
        SDL_DestroyTexture(texture);
        SDL_DestroyRenderer(renderer);
        SDL_DestroyWindow(window);
        SDL_Quit();
        return 1;
    }

    // White background (0xFFFFFFFF = ARGB white)
    memset(pixels, 0xFF, WIDTH * HEIGHT * sizeof(Uint32));

    int quit = 0;
    int drawing = 0;
    int prevX = 0, prevY = 0;
    Uint32 drawColor = 0xFF000000;  // Black (ARGB)

    while (!quit)
    {
        SDL_Event event;
        while (SDL_PollEvent(&event))
        {
            switch (event.type)
            {
                case SDL_QUIT:
                    quit = 1;
                    break;

                case SDL_MOUSEBUTTONDOWN:
                    if (event.button.button == SDL_BUTTON_LEFT)
                    {
                        drawing = 1;
                        prevX = event.button.x;
                        prevY = event.button.y;
                        // Draw single pixel on click
                        if (prevX >= 0 && prevX < WIDTH && prevY >= 0 && prevY < HEIGHT)
                            pixels[prevY * WIDTH + prevX] = drawColor;
                    }
                    break;

                case SDL_MOUSEBUTTONUP:
                    if (event.button.button == SDL_BUTTON_LEFT)
                        drawing = 0;
                    break;

                case SDL_MOUSEMOTION:
                    if (drawing)
                    {
                        int currX = event.motion.x;
                        int currY = event.motion.y;

                        // Draw line from previous position to current
                        drawLine(pixels, prevX, prevY, currX, currY, drawColor);

                        prevX = currX;
                        prevY = currY;
                    }
                    break;

                case SDL_KEYDOWN:
                    if (event.key.keysym.sym == SDLK_c)  // Press 'C' to clear
                    {
                        memset(pixels, 0xFF, WIDTH * HEIGHT * sizeof(Uint32));
                    }
                    break;
            }
        }

        // Update texture and render
        SDL_UpdateTexture(texture, NULL, pixels, WIDTH * sizeof(Uint32));
        SDL_RenderClear(renderer);
        SDL_RenderCopy(renderer, texture, NULL, NULL);
        SDL_RenderPresent(renderer);

        SDL_Delay(16);  // ~60 FPS cap
    }

    free(pixels);
    SDL_DestroyTexture(texture);
    SDL_DestroyRenderer(renderer);
    SDL_DestroyWindow(window);
    SDL_Quit();

    return 0;
}

posted by damirs @ December 29, 2025