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.
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).
Contenidos
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.
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:
Que produce un resultado como el siguiente:
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.
Sin embargo, esta aproximación también es errónea. Vamos a dibujar con ella tres líneas:
Y se produce el siguiente resultado
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:
Y obtenemos el siguiente renderizado
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.
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$$
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:
Y a continuación, un listado de las caras o triángulos que se forman con los puntos anteriores, de la siguiente forma:
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:
Utilizaremos un valor predefinido de altura y anchura para el tamaño de la imagen y obtendremos un resultado como el siguiente:
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.