Saltar al contenido

Dibujando lineas con el Algoritmo de Bresenham

agosto 18, 2018
Motor Render desde 0 en C++ Algoritmo de Bresenham

En este primer post introduciremos el funcionamiento básico de un motor de renderizado. Comenzaremos dibujando una línea y observando cuáles son los primeros problemas que se nos plantean. Los resolveremos utilizando el Algoritmo de Bresenham para trazar líneas en dispositivos gráficos basados en matrices de píxeles (una cantidad entera y finita de filas y columnas que representan la pantalla y se pueden colorear). Finalmente renderizaremos una malla formada por triángulos sobre un modelo 3D que cargaremos desde un fichero .obj de Wavefront.

Ejemplo_de_Bresenham

El objetivo de este primer post es el de poder renderizar la malla de un objeto 3D cargado desde un fichero Wavefront. Los códigos y parte de la información ha sido extraída y adaptada de Dmitry V. Sokolov (l’Université de Lorraine, membre d’équipe ALICE).

El problema de dibujar una línea en una pantalla digital formada por píxeles

El primer problema se nos plantea cuando queremos dibujar una línea entre un punto $A(x_0, y_0)$ y $B(x_1, y_1)$. Si lo hacemos con un lápiz y papel no tenemos problema. Sin embargo, cuando utilizamos una representación digital basada en píxeles, mapeada en una cantidad entera de filas y columnas se produce cierto error. El trazado debe ocupar como mínimo un cuadro del mapa equivalentemente a un punto. La transformación de los puntos (analógico, continuo) a pixeles cuadrados (digital, discreto) produce cierto error.

Linea_basica_y_de_errores Bresenham
La línea ideal trazada en rojo, se perciben los errores al seguir las líneas en verde. Los cuadros marcados en amarillo, serían una posible solución de la línea.

El error producido lleva a una aproximación del dibujado de la línea que presenta dos claros problemas:

  • Qué puntos o cuadros (píxeles) pasan por la recta.
  • De los puntos o cuadros (píxeles) que pasen por la recta, cuáles deben dibujarse.

Primera Aproximación

Una primera aproximación a la representación de una línea puede ser la siguiente:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    for (float t=0.; t<1.; t+=.1) {
        int x = x0*(1.-t) + x1*t;
        int y = y0*(1.-t) + y1*t;
        image.set(x, y, color);
    }
}
Primera aproximación a dibujar una línea

Que produce un resultado como el siguiente:

renderizado linea 1

Como podéis ver, el resultado obtenido no es factible. En este caso, se utiliza un incremento de $t = 0.1$ y se dibujan los pixeles.

Segunda Aproximación

En una segunda aproximación podemos elegir el valor del paso $t$ como la cantidad de pixeles a dibujar.

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { 
    for (int x=x0; x<=x1; x++) { 
        float t = (x-x0)/(float)(x1-x0); 
        int y = y0*(1.-t) + y1*t; 
        image.set(x, y, color); 
    } 
}
Segunda aproximación errónea a dibujar una línea

Sin embargo, esta aproximación también es errónea. Vamos a dibujar con ella tres líneas:

 line(13, 20, 80, 40, image, white);
 line(20, 13, 40, 80, image, red);
 line(80, 40, 13, 20, image, red);

Y se produce el siguiente resultado

renderizado linea 2

En este caso la línea blanca se dibuja correctamente, sin embargo, las lineas rojas no aparecen correctamente. La primera linea roja, tiene algunos puntos que no se han dibujado y la segunda línea roja no se ha dibujado. El error se encuentra en la división para calcular el paso $t$.

Tercera aproximación

El problema lo encontramos cuando el valor de $x_1$ es menor que el de $x_0$ o la línea es demasiado inclinada (más de 45º). Lo podemos resolver fácilmente de la siguiente forma:

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { 
    bool steep = false; 
	// si la línea es demasiado inclinada la transponemos
	if (std::abs(x0-x1)<std::abs(y0-y1)) { 
        std::swap(x0, y0); 
        std::swap(x1, y1); 
        steep = true; 
    } 
	// si la línea es de derecha a izquierda intercambiamos
    if (x0>x1) { 
        std::swap(x0, x1); 
        std::swap(y0, y1); 
    } 
    for (int x=x0; x<=x1; x++) { 
        float t = (x-x0)/(float)(x1-x0); 
        int y = y0*(1.-t) + y1*t; 
		// si está transpuesta, la re-transponemos
        if (steep) { 
            image.set(y, x, color); 
        } else { 
            image.set(x, y, color); 
        } 
    } 
}
tercera versión para dibujar una línea funcional

Y obtenemos el siguiente renderizado

renderizado linea 3

Como vemos, ahora obtenemos el resultado correcto. Las líneas se dibujan sin huecos (pixeles en blanco). La línea blanca no aparece porque la última línea roja que dibujamos era igual a la blanca pero con los puntos introducidos de forma invertida (de derecha a izquierda). Esta versión funciona con las líneas inclinadas más de 45º y con los puntos introducidos en cualquier orden.

Optimizaciones del Algoritmo de Bresenham

El Algoritmo de Bresenham es un método rápido para el trazado de líneas en dispositivos gráficos, cuya cualidad más apreciada es que solo realiza cálculos con enteros. Se puede adaptar para rasterizar también circunferencias y curvas.

Primera Optimización

Dentro del bucle principal vemos que la división siempre tiene el mismo denominador. Vamos a intentar extraer la división del bucle utilizando el valor de la pendiente como valor del incremento fijo del error y comprobaremos si este es mayor a $0.5$ para incrementar el valor de $y$ y resetear el error restando -1.

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) { 
    bool steep = false; 
    if (std::abs(x0-x1)<std::abs(y0-y1)) { 
        std::swap(x0, y0); 
        std::swap(x1, y1); 
        steep = true; 
    } 
    if (x0>x1) { 
        std::swap(x0, x1); 
        std::swap(y0, y1); 
    } 
    int dx = x1-x0; 
    int dy = y1-y0; 
    float derror = std::abs(dy/float(dx)); 
    float error = 0; 
    int y = y0; 
    for (int x=x0; x<=x1; x++) { 
        if (steep) { 
            image.set(y, x, color); 
        } else { 
            image.set(x, y, color); 
        } 
        error += derror; 
        if (error>.5) { 
            y += (y1>y0?1:-1); 
            error -= 1.; 
        } 
    } 
} 
primera optimización dibujar línea

optimización dibujar linea

Segunda Optimización

En esta segunda optimización realizamos una implementación del algoritmo planteado por Carlos E. Alvarez D. en pseudo-codigo para C++. En este caso solo utilizaremos números enteros y evitaremos los valores en coma flotante para acelerar la ejecución del código.

Se utiliza el parámetro $error_0 = 2 dy – 2 dx$ para decidir el error del siguiente paso de forma incremental. Con $dx = x_1 – x_0$ y $dy = y_1 – y_0$.

$$error_{i+1} = error_i + 2 dy  \mbox{  si  }  error_0 < 0$$

$$error_{i+1} = error_i + 2 dy – 2 dx  \mbox{  si  }  error_0 > 0$$

void line(int x0, int y0, int x1, int y1, TGAImage &image, TGAColor color) {
    bool steep = false;
    if (std::abs(x0-x1)<std::abs(y0-y1)) {
        std::swap(x0, y0);
        std::swap(x1, y1);
        steep = true;
    }
    if (x0>x1) {
        std::swap(x0, x1);
        std::swap(y0, y1);
    }
    int dx = x1-x0;
    int dy = y1-y0;
    int error = 2 * dy - dx;
    int Dn = error + dx;
    int Dp = error - dx;
    int x = x0;
    int y = y0;
    while (x <= x1) {
        if(error < 0){
            error = error + Dn;
        } else {
            error = error + Dp;
            y = y + 1;
        }
        x = x + 1;
        if(steep){
            image.set(y, x, color);
        } else {
            image.set(x, y, color);
        }
    }
}
Implementación óptima del algoritmo de Bresenham

Si aplicamos el método a un conjunto de 3.000.000 de líneas obtenemos una mejoría de 2.95 a 0.64 segundos, lo que implica una mejora de casi el 80%.

Aplicación sobre un modelo 3D

Para finalizar, vamos a probar con un modelo 3D que cargaremos con un fichero wavefront obj que contiene la información de la siguiente forma:

Primero, un listado de puntos (vértices) representados de la siguiente forma:

v 0.608654 -0.568839 -0.416318

Y a continuación, un listado de las caras o triángulos que se forman con los puntos anteriores, de la siguiente forma:

f 1193/1240/1193 1180/1227/1180 1179/1226/1179

En el que cada número representa la posición del punto (vértice) en el listado anterior.

Trabajaremos también con una Clase Model que será la encargada de leer los ficheros a memoria y contendrá funciones simples para acceder a los puntos y caras del modelo por su índice. Las funciones model->nfaces() , model->face(i) y model->vert(i) son las principales que nos interesan.

Con todo esto, una vez leído el fichero wavefront y cargado a memoria en un objeto Model, podemos trabajar de la siguiente forma con los puntos para renderizar el modelo 3D final:

for (int i = 0; i < model->nfaces(); i++) { 
    std::vector<int> face = model->face(i); 
    for (int j=0; j<3; j++) { 
        Vec3f v0 = model->vert(face[j]); 
        Vec3f v1 = model->vert(face[(j+1)%3]); 
        int x0 = (v0.x+1.)*width/2.; 
        int y0 = (v0.y+1.)*height/2.; 
        int x1 = (v1.x+1.)*width/2.; 
        int y1 = (v1.y+1.)*height/2.; 
        line(x0, y0, x1, y1, image, white); 
    } 
}
Render Modelo Wavefront

Utilizaremos un valor predefinido de altura y anchura para el tamaño de la imagen y obtendremos un resultado como el siguiente:

render triangulos modelo 3D

En los siguientes posts aprenderemos a rellenar los triángulos generando así superficies 2D y optimizaremos el proceso de renderizado.
Podéis encontrar el código utilizado en la cuenta de GitHub.