Algoritmo del pintor

El algoritmo del pintor (también algoritmo de clasificación por profundidad y relleno prioritario) es un algoritmo para la determinación de superficies visibles en gráficos 3D por computadora que funciona sobre la base de polígono por polígono en lugar de píxel por píxel, fila por fila o área por área de otros algoritmos de eliminación de superficies ocultas. El algoritmo del pintor crea imágenes clasificando los polígonos dentro de la imagen por su profundidad y colocando cada polígono en orden desde el objeto más lejano hasta el más cercano.

El algoritmo del pintor fue propuesto inicialmente como un método básico para abordar el problema de determinación de la superficie oculta por Martin Newell, Richard Newell y Tom Sancha en 1972, mientras los tres trabajaban en CADCentre. El nombre "algoritmo del pintor" se refiere a la técnica empleada por muchos pintores en la que comienzan pintando partes distantes de una escena antes de las partes más cercanas, cubriendo así algunas áreas de partes distantes. De manera similar, el algoritmo del pintor clasifica todos los polígonos en una escena por su profundidad y luego los pinta en este orden, de más lejano a más cercano. Pintará sobre las partes que normalmente no son visibles, resolviendo así el problema de visibilidad, a costa de haber pintado áreas invisibles de objetos distantes. La ordenación utilizada por el algoritmo se denomina 'orden de profundidad' y no tiene que respetar las distancias numéricas a las partes de la escena: la propiedad esencial de esta ordenación es, más bien, que si un objeto oscurece parte de otro, entonces el primer objeto se pinta después del objeto que oscurece. Por lo tanto, una ordenación válida se puede describir como una ordenación topológica de un gráfico acíclico dirigido que representa oclusiones entre objetos.

Las montañas distantes son pintadas primero, seguidas por los prados más cercanos; finalmente, los árboles, son pintados. Aunque algunos árboles están más distantes del punto de vista que algunas partes de los prados, el ordenamiento (montañas, prados, árboles) forma un orden de profundidad válido, porque ningún objeto en el orden oscurece cualquier parte de un objeto posterior.

Algoritmo

El algoritmo de Conceptually Painter funciona de la siguiente manera:

1. Ordenar cada polígono por profundidad
2. Coloque cada polígono del polígono más lejano al polígono más cercano

Pseudocódigo

especie polígonos por profundidadpara cada uno polígono p:
 para cada uno pixel que p cubre:
 pintura p.color on pixel

Complejidad del tiempo

La complejidad temporal del algoritmo del pintor depende en gran medida del algoritmo de clasificación utilizado para ordenar los polígonos. Asumiendo el uso del algoritmo de clasificación más óptimo, el algoritmo del pintor tiene una complejidad en el peor de los casos de O(n log n + m*n), donde n es el número de polígonos y m es el número de píxeles a rellenar.

Complejidad del espacio

La complejidad espacial del peor de los casos del algoritmo del pintor es O(n+m), donde n es el número de polígonos y m es el número de píxeles a rellenar.

Ventajas

Hay dos requisitos técnicos principales que favorecen el uso del algoritmo del pintor.

Estructura gráfica básica

El algoritmo del pintor no tiene una estructura tan compleja como sus contrapartes de otros algoritmos de clasificación de profundidad. Los componentes como el orden de renderizado basado en la profundidad, tal como lo emplea el algoritmo del pintor, son una de las formas más sencillas de designar el orden de producción gráfica. Esta simplicidad lo hace útil en escenarios básicos de salida de gráficos por computadora donde será necesario realizar un renderizado no sofisticado con poca dificultad.

Eficiencia de la memoria

A principios de los 70, cuando se desarrolló el algoritmo del pintor, la memoria física era relativamente pequeña. Esto requería que los programas administraran la memoria de la manera más eficiente posible para realizar tareas grandes sin bloquearse. El algoritmo del pintor prioriza el uso eficiente de la memoria, pero a expensas de una mayor potencia de procesamiento, ya que se deben renderizar todas las partes de todas las imágenes.

Los polígonos superpuestos pueden hacer que el algoritmo falle

Limitaciones

El algoritmo puede fallar en algunos casos, como la superposición cíclica o la perforación de polígonos.

Superposición cíclica

En el caso de la superposición cíclica, como se muestra en la figura de la derecha, los polígonos A, B y C se superponen entre sí de tal manera que es imposible determinar qué polígono está por encima de los demás. En este caso, los polígonos infractores se deben cortar para permitir la clasificación.

Polígonos perforantes

El caso de perforar polígonos surge cuando un polígono se cruza con otro. Similar a la superposición cíclica, este problema puede resolverse cortando los polígonos infractores.

Eficiencia

En implementaciones básicas, el algoritmo del pintor puede ser ineficiente. Obliga al sistema a representar cada punto en cada polígono del conjunto visible, incluso si ese polígono está ocluido en la escena final. Esto significa que, para escenas detalladas, el algoritmo del pintor puede sobrecargar el hardware de la computadora.

Variantes

Algoritmo de pintor extendido

El algoritmo de Newell, propuesto como el algoritmo extendido del algoritmo del pintor, proporciona un método para cortar polígonos cíclicos y perforantes.

Algoritmo de la pintora inversa

Otra variante del algoritmo del pintor incluye el algoritmo del pintor inverso. El algoritmo de pintor inverso pinta primero los objetos más cercanos al espectador, con la regla de que nunca se debe aplicar pintura a partes de la imagen que ya están pintadas (a menos que sean parcialmente transparentes). En un sistema de gráficos por computadora, esto puede ser muy eficiente ya que no es necesario calcular los colores (usando iluminación, texturizado, etc.) para partes de una escena distante que están ocultas por objetos cercanos. Sin embargo, el algoritmo inverso adolece de muchos de los mismos problemas que la versión estándar.

Otros algoritmos gráficos por computadora

Los defectos del algoritmo del pintor llevaron al desarrollo de técnicas de Z-buffer, que pueden verse como un desarrollo del algoritmo del pintor al resolver conflictos de profundidad píxel por píxel. reduciendo la necesidad de un orden de renderizado basado en la profundidad. Incluso en tales sistemas, a veces se emplea una variante del algoritmo del pintor. Como las implementaciones de búfer Z generalmente se basan en registros de búfer de profundidad de precisión fija implementados en hardware, existe la posibilidad de problemas de visibilidad debido al error de redondeo. Estos son superposiciones o espacios en las juntas entre polígonos. Para evitar esto, algunos motores de gráficos implementan "sobrerenderizado", dibujando los bordes afectados de ambos polígonos en el orden dado por el algoritmo del pintor. Esto significa que algunos píxeles se dibujan dos veces (como en el algoritmo del pintor completo), pero esto ocurre solo en pequeñas partes de la imagen y tiene un efecto insignificante en el rendimiento.