El algoritmo del pintor (también algoritmo de clasificación en profundidad y relleno de prioridad ) es un algoritmo para la determinación de la superficie visible en gráficos por computadora en 3D que funciona polígono por polígono en lugar de píxel por píxel , fila por fila o área por base de área de otros algoritmos de eliminación de superficies ocultas . [1] [2] [3] 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 al más cercano. [4] [5]
El algoritmo del pintor fue propuesto inicialmente como un método básico para abordar el problema de determinación de superficies ocultas por Martin Newell , Richard Newell y Tom Sancha en 1972, mientras los tres trabajaban en CADCentre . [4] El nombre "algoritmo del pintor" se refiere a la técnica empleada por muchos pintores donde comienzan pintando partes distantes de una escena antes que partes más cercanas, cubriendo así algunas áreas de partes distantes. [6] [7] De manera similar, el algoritmo del pintor ordena todos los polígonos en una escena por su profundidad y luego los pinta en este orden, del más lejano al más cercano. [8] 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. [9] El orden utilizado por el algoritmo se llama ' orden de profundidad' y no tiene que respetar las distancias numéricas a las partes de la escena: la propiedad esencial de este orden es, más bien, que si un objeto oscurece parte de otro , luego el primer objeto se pinta después del objeto que oscurece. [9] Por lo tanto, un ordenamiento válido puede describirse como un ordenamiento topológico de un gráfico acíclico dirigido que representa oclusiones entre objetos. [10]
Conceptualmente el algoritmo de Painter funciona de la siguiente manera:
ordenar polígonos por profundidad para cada polígono p : para cada píxel que cubre p : pintar p.color en píxel
La complejidad temporal del algoritmo del pintor depende en gran medida del algoritmo de clasificación utilizado para ordenar los polígonos. Suponiendo el uso del algoritmo de clasificación más óptimo, el algoritmo de Painter 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 que se rellenarán.
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 ym es el número de píxeles que se rellenarán.
Hay dos requisitos técnicos principales que favorecen el uso del algoritmo del pintor.
El algoritmo del pintor no tiene una estructura tan compleja como sus otros algoritmos de clasificación en profundidad. [9] [11] Componentes como el orden de representación basado en la profundidad, tal como lo emplea el algoritmo del pintor, son una de las formas más simples de designar el orden de producción gráfica. [8] Esta simplicidad lo hace útil en escenarios básicos de salida de gráficos por computadora donde será necesario realizar un renderizado poco sofisticado con poca dificultad. [9]
A principios de los años 70, cuando se desarrolló el algoritmo del pintor, la memoria física era relativamente pequeña. [12] Esto requirió que los programas administraran la memoria de la manera más eficiente posible para realizar grandes tareas sin fallar. El algoritmo del pintor prioriza el uso eficiente de la memoria, pero a expensas de una mayor potencia de procesamiento, ya que se deben representar todas las partes de todas las imágenes. [9]
El algoritmo puede fallar en algunos casos, incluida la superposición cíclica o la perforación de polígonos.
En el caso de 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 deben cortarse para permitir la clasificación. [4]
El caso de polígonos perforantes surge cuando un polígono intersecta a otro. De manera similar a la superposición cíclica, este problema puede resolverse cortando los polígonos infractores. [4]
En implementaciones básicas, el algoritmo del pintor puede resultar ineficiente. Obliga al sistema a representar cada punto de cada polígono en el conjunto visible, incluso si ese polígono está ocluido en la escena terminada. Esto significa que, para escenas detalladas, el algoritmo del pintor puede sobrecargar el hardware de la computadora.
El algoritmo de Newell , propuesto como algoritmo extendido del algoritmo del pintor, proporciona un método para cortar polígonos cíclicos y perforantes. [4]
Otra variante del algoritmo del pintor incluye el algoritmo del pintor inverso . El algoritmo del 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 gráfico por computadora, esto puede ser muy eficiente ya que no es necesario calcular los colores (usando iluminación, texturas, etc.) para partes de una escena distante que están ocultas por objetos cercanos. Sin embargo, el algoritmo inverso sufre muchos de los mismos problemas que la versión estándar.
Los defectos del algoritmo del pintor llevaron al desarrollo de técnicas de búfer Z , que pueden verse como un desarrollo del algoritmo del pintor al resolver conflictos de profundidad píxel por píxel, lo que reduce la necesidad de un orden de representación basado en la profundidad. [13] 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 que surjan problemas de visibilidad debido a errores de redondeo. Son superposiciones o espacios en las uniones entre polígonos. Para evitar esto, algunos motores gráficos implementan "sobrerrepresentación", [ cita necesaria ] dibujando los bordes afectados de ambos polígonos en el orden dado por el algoritmo del pintor. Esto significa que algunos píxeles en realidad se dibujan dos veces (como en el algoritmo del pintor completo), pero esto sucede sólo en pequeñas partes de la imagen y tiene un efecto de rendimiento insignificante.
{{cite journal}}: Citar diario requiere |journal=( ayuda ){{cite journal}}: Citar diario requiere |journal=( ayuda )