Algoritmos de Trazado de Líneas en Computación Gráfica: Básico, DDA y Bresenham

Algoritmos para el trazado de líneas rectas

En la computación gráfica, trazar una línea recta consiste en calcular las coordenadas enteras de los píxeles que forman parte de la línea o que se encuentran más cerca de ella. A continuación se presentan tres implementaciones clásicas: el algoritmo básico, el algoritmo DDA (Digital Differential Analyzer) y el algoritmo de Bresenham.

1. Algoritmo básico

Este método calcula la pendiente M y la ordenada al origen B de la recta, y en cada iteración obtiene el valor de Y a partir de la ecuación Y = M·X + B. Cuando la recta es vertical (Dx = 0), se recorre directamente el eje Y.

void Basico(int X1, int Y1, int X2, int Y2)
{
    int i, X;
    float Y;
    float Dx, Dy, M, B;

    Dy = Y2 - Y1;
    Dx = X2 - X1;

    glPointSize(4.0);

    if (Dx != 0)
    {
        M = Dy / Dx;
        B = Y1 - M * X1;
        X = X1;
        Y = Y1;

        glBegin(GL_POINTS);

        glVertex2i(X, (int)round(Y));

        for (i = 0; i < abs(Dx); i++)
        {
            Y = M * X + B;

            if (Dx < 0)
                X--;
            else
                X++;

            glVertex2i(X, (int)round(Y));
        }
        glEnd();
    }
    else
    {
        glBegin(GL_POINTS);
        Y = Y1;
        X = X1;

        glVertex2i(X, (int)round(Y));

        for (i = 0; i < Dy; i++)
        {
            Y = Y + 1;
            glVertex2i(X, (int)Y);
        }
        glEnd();
    }
}

2. Algoritmo DDA

El algoritmo DDA avanza en cada paso un incremento fijo en X o en Y, según la pendiente de la recta, y dibuja el punto resultante. Se divide en cuatro casos según el signo de Dx y Dy, y el número de iteraciones corresponde al máximo entre |Dx| y |Dy|.

void DDA(int x1, int y1, int x2, int y2)
{
    int i;
    int Pasos;
    int Dx, Dy;
    float X, Y, m, IncX, IncY;

    X = x1;
    Y = y1;

    // Punto inicial
    glBegin(GL_POINTS);
    glVertex2i(X, Y);

    Dx = x2 - x1;
    Dy = y2 - y1;

    // Cantidad de iteraciones (píxeles a iluminar)
    Pasos = Max(abs(Dx), abs(Dy));

    m = (float)Dy / Dx;

    if (Dx > 0 && Dy > 0)
    {
        if (Dx > Dy)
        {
            printf("Caso 1.1: ");
            IncX = 1;
            IncY = m;
        }
        else
        {
            printf("Caso 1.2: ");
            IncY = +1;
            IncX = 1 / m;
        }
    }

    if (Dx > 0 && Dy < 0)
    {
        if (Dx > abs(Dy))
        {
            printf("Caso 2.1: ");
            IncX = 1;
            IncY = m;
        }
        else
        {
            printf("Caso 2.2: ");
            IncY = -1;
            IncX = (1 / m);
        }
    }

    if (Dx < 0 && Dy > 0)
    {
        if (abs(Dx) > Dy)
        {
            printf("Caso 3.1: ");
            IncX = -1;
            IncY = m;
        }
        else
        {
            printf("Caso 3.2: ");
            IncY = 1;
            IncX = (1 / m);
        }
    }

    if (Dx < 0 && Dy < 0)
    {
        if (abs(Dx) > abs(Dy))
        {
            printf("Caso 4.1: ");
            IncX = -1;
            IncY = -m;
        }
        else
        {
            printf("Caso 4.2: ");
            IncY = -1;
            IncX = -(1 / m);
        }
    }

    for (i = 0; i < Pasos; i++)
    {
        printf("%f , %f\n", X, Y);
        X = X + IncX;
        Y = Y + IncY;

        glVertex2i(X, Y);
    }

    glEnd();
}

3. Algoritmo de Bresenham

El algoritmo de Bresenham evita operaciones de punto flotante utilizando únicamente aritmética entera. En cada paso decide si el siguiente píxel está en la misma fila (E, Este) o en la diagonal superior (NE, Noreste) a partir del signo de la variable de decisión d. Esta versión funciona para pendientes entre 0 y 1 en valor absoluto, y para las demás se requieren adaptaciones por octantes.

void bresenham1(int x1, int y1, int x2, int y2)
{
    int slope;
    int dx, dy, incE, incNE, d, x, y;

    // Invierte las líneas donde x1 > x2
    if (x1 > x2)
    {
        bresenham1(x2, y2, x1, y1);
        return;
    }

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

    // Ajusta el incremento de y para líneas con pendiente negativa
    if (dy < 0)
    {
        slope = -1;
        dy = -dy;
    }
    else
    {
        slope = 1;
    }

    // Constantes de Bresenham
    incE = 2 * dy;
    incNE = 2 * dy - 2 * dx;
    d = 2 * dy - dx;
    y = y1;

    // Trazado
    for (x = x1; x <= x2; x++)
    {
        putpixel(x, y);

        if (d <= 0)
        {
            d += incE;
        }
        else
        {
            d += incNE;
            y += slope;
        }
    }
}

Requisitos de un buen algoritmo de trazado de líneas

Un algoritmo adecuado para el trazado de líneas debe cumplir los siguientes requisitos:

• Calcular coordenadas enteras de los píxeles que forman parte de la línea recta o que son cercanos a ella.
• Ser eficiente, minimizando el número de operaciones por píxel.
• Crear imágenes visualmente satisfactorias.
• Lograr que las líneas parezcan líneas rectas.
• Hacer que las líneas terminen con exactitud en los puntos extremos especificados.
• Mantener una densidad constante a lo largo de la línea.
• Garantizar que la densidad sea independiente de la longitud o del ángulo de la línea.