El algoritmo del pintor (también algoritmo de ordenación de profundidad y algoritmo de relleno de prioridad ) es un algoritmo para la determinación de superficies visibles en gráficos de computadora 3D que funciona sobre una base de polígono por polígono en lugar de píxel por píxel , fila por fila o área por área como otros algoritmos de eliminación de superficies ocultas . [1] [2] [3] El algoritmo del pintor crea imágenes ordenando 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 de las partes que están más cerca, 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 ordenamiento utilizado por el algoritmo se denomina " orden de profundidad" y no tiene por qué respetar las distancias numéricas a las partes de la escena: la propiedad esencial de este ordenamiento es, más bien, que si un objeto oscurece parte de otro, entonces el primer objeto se pinta después del objeto que oscurece. [9] Por 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:
Ordena los polígonos por profundidad para cada polígono p : para cada píxel que p cubre: pinta p.color en el píxel
La complejidad temporal del algoritmo del pintor depende del algoritmo de ordenamiento utilizado para ordenar los polígonos. Suponiendo un algoritmo de ordenamiento ó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 que se deben rellenar.
La complejidad espacial del peor caso 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.
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 contrapartes de algoritmos de ordenamiento de profundidad. [9] [11] 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 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 de computadora donde será necesario realizar un renderizado poco sofisticado con pocas dificultades. [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 requería que los programas gestionaran la memoria de la manera más eficiente posible para llevar a cabo tareas grandes sin colapsar. El algoritmo del pintor prioriza el uso eficiente de la memoria, pero a expensas de una mayor capacidad de procesamiento, ya que se deben renderizar 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 cuál 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 perforados surge cuando un polígono interseca a otro. De manera similar a la superposición cíclica, este problema se puede resolver cortando los polígonos que intersectan. [4]
En las implementaciones básicas, el algoritmo del pintor puede resultar ineficiente. Obliga al sistema a representar cada punto de cada polígono del conjunto visible, incluso si ese polígono está oculto en la escena final. Esto significa que, en el caso de escenas detalladas, el algoritmo del pintor puede sobrecargar el hardware de la computadora.
El algoritmo de Newell , propuesto como el algoritmo extendido del algoritmo de Painter, 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 la pintura nunca debe aplicarse a partes de la imagen que ya están pintadas (a menos que sean parcialmente transparentes). En un sistema gráfico de computadora, esto puede ser muy eficiente ya que no es necesario calcular los colores (usando iluminación, texturas y demás) 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, reduciendo la necesidad de un orden de renderizado basado en la profundidad. [13] Incluso en tales sistemas, a veces se emplea una variante del algoritmo del pintor. Como las implementaciones del búfer Z generalmente se basan en registros de búfer de profundidad de precisión fija implementados en hardware, existe margen para problemas de visibilidad debido al error de redondeo. Estos son superposiciones o espacios en las uniones entre polígonos. Para evitar esto, algunos motores gráficos implementan "sobrerenderizado", [ cita requerida ] 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 completo del pintor), pero esto sucede solo en pequeñas partes de la imagen y tiene un efecto insignificante en el rendimiento.
{{cite journal}}: Requiere citar revista |journal=( ayuda ){{cite journal}}: Requiere citar revista |journal=( ayuda )