Hispanopedia WikiEl algoritmo del pintor (también conocido como algoritmo de ordenación por profundidad y relleno de prioridad ) es un algoritmo para la determinación de superficies visibles en gráficos 3D por computadora que funciona polígono por polígono en lugar de píxel por píxel , fila por fila o área por área como otros algoritmos de determinació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 la 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, quienes comienzan pintando las partes distantes de una escena antes que las partes más cercanas, cubriendo así algunas áreas de las partes distantes. [ 6 ] [ 7 ] De manera similar, el algoritmo del pintor ordena todos los polígonos de una escena según 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 oculta parte de otro, entonces el primer objeto se pinta después del objeto que oculta. [ 9 ] Por lo tanto, un ordenamiento válido puede describirse como un ordenamiento topológico de un grafo dirigido acíclico que representa oclusiones entre objetos. [ 10 ]
Algoritmo
Conceptualmente, el algoritmo del pintor funciona de la siguiente manera:
- Ordena cada polígono por profundidad.
- Coloca cada polígono desde el polígono más alejado hasta el polígono más cercano.
Pseudocódigo
ordenar polígonos por profundidad para cada polígono p : para cada píxel que cubre p : pintar p.color en el píxel
complejidad temporal
La complejidad temporal del algoritmo del pintor depende del algoritmo de ordenación utilizado para ordenar los polígonos. Suponiendo un algoritmo de ordenación ó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 espacial
La complejidad espacial en el 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 que se van a rellenar.
Ventajas
Existen dos requisitos técnicos principales que favorecen el uso del algoritmo del pintor.
Estructura gráfica básica
El algoritmo del pintor no es tan complejo en su estructura como otros algoritmos de ordenación por profundidad. [ 9 ] [ 11 ] Componentes como el orden de renderizado basado en la profundidad, empleado por el algoritmo del pintor, son una de las formas más sencillas 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 se necesita realizar un renderizado sencillo con poca dificultad. [ 9 ]
Eficiencia de la memoria
A principios de los años 70, cuando se desarrolló el algoritmo del pintor, la memoria física era relativamente pequeña. [ 12 ] Esto obligaba a los programas a gestionar la memoria de la forma más eficiente posible para realizar tareas complejas sin fallar. El algoritmo del pintor prioriza el uso eficiente de la memoria, pero a costa de una mayor potencia de procesamiento, ya que todas las partes de todas las imágenes deben renderizarse. [ 9 ]
Limitaciones
El algoritmo puede fallar en algunos casos, como por ejemplo en casos de superposición cíclica o de perforación de polígonos.
Superposición cíclica
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 de tal manera que resulta imposible determinar cuál está encima de los demás. En este caso, los polígonos que causan la superposición deben cortarse para permitir la clasificación. [ 4 ]
Polígonos perforantes
El caso de los polígonos que se superponen surge cuando un polígono interseca a otro. De forma similar a la superposición cíclica, este problema puede resolverse cortando los polígonos que lo causan. [ 4 ]
Eficiencia
En implementaciones básicas, el algoritmo del pintor puede ser ineficiente. Obliga al sistema a renderizar cada punto de 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 del ordenador.
Reducción de errores visuales
Hay varias maneras de reducir los errores visuales que pueden ocurrir al ordenar:
Particionamiento binario del espacio
BSP es un método que consiste en crear un árbol BSP y dividir los triángulos en sus puntos de intersección. Su implementación puede ser extremadamente compleja, pero corrige la mayoría de los errores visuales.
eliminación de caras posteriores
La eliminación de caras posteriores implica cálculos para determinar si los vértices de un triángulo aparecerán en sentido horario o antihorario una vez proyectados en la pantalla, y no dibuja triángulos que no deberían ser visibles. Esto reduce algunos errores visuales, así como la cantidad total de triángulos dibujados.
Variantes
Algoritmo de pintor extendido
El algoritmo de Newell , propuesto como una extensión del algoritmo del pintor, proporciona un método para cortar polígonos cíclicos y perforantes. [ 4 ]
Algoritmo del pintor inverso
Otra variante del algoritmo del pintor es el algoritmo del pintor inverso . Este algoritmo pinta primero los objetos más cercanos al observador, con la regla de que nunca se debe aplicar pintura a las 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 (utilizando iluminación, texturizado, etc.) para las partes de una escena distante que están ocultas por objetos cercanos. Sin embargo, el algoritmo inverso presenta muchos de los mismos problemas que la versión estándar.
Otros algoritmos de gráficos por computadora
Los fallos del algoritmo del pintor llevaron al desarrollo de las técnicas de búfer Z , que pueden considerarse una evolución del algoritmo del pintor al resolver los conflictos de profundidad píxel a píxel, reduciendo la necesidad de un orden de renderizado basado en la profundidad. [ 13 ] Incluso en estos 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 solapamientos o huecos en las uniones entre polígonos. Para evitar esto, algunos motores gráficos implementan el "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 de rendimiento insignificante.
Referencias
- Foley, James ; Feiner, Steven K.; Hughes, John F. (1990). Gráficos por computadora: Principios y práctica . Reading, MA, EE. UU.: Addison-Wesley . pág . 1174. ISBN 0-201-12110-7.
- ↑ Appel, Arthur (1968). Morrel, AJH (ed.). "Sobre el cálculo de la ilusión de la realidad" (PDF) . Procesamiento de la información, Actas del Congreso IFIP de 1968, Edimburgo, Reino Unido, 5-10 de agosto de 1968, Volumen 2 - Hardware, Aplicaciones : 945–950 . Archivado (PDF) del original el 20 de julio de 2008.
- ↑ Romney, Gordon Wilson (1969-09-01). "Ensamblaje y renderizado de sólidos asistidos por computadora" . Archivado del original el 2 de noviembre de 2020.
{{cite journal}}: Para citar una revista se requiere|journal=( ayuda ) - ↑ Gary Scott Watkins. 1970. "Un algoritmo de superficie visible en tiempo real. Tesis doctoral." Universidad de Utah. Número de pedido: AAI7023061.
- 1 2 3 4 5 Newell, ME; Newell, RG; Sancha, TL (1972-08-01). "Una solución al problema de la superficie oculta" (PDF) . Actas de la conferencia anual de la ACM sobre - ACM'72 . ACM '72. Vol. 1. Boston, Massachusetts, EE. UU.: Association for Computing Machinery. págs. 443–450 . doi : 10.1145/800193.569954 . ISBN 978-1-4503-7491-0. S2CID 13829930 . Archivado (PDF) del original el 22-09-2020.
- ↑ Bouknight, W. Jack (1970-09-01). "Un procedimiento para la generación de presentaciones de gráficos por computadora tridimensionales en semitono" . Communications of the ACM . 13 (9): 527– 536. doi : 10.1145/362736.362739 . ISSN 0001-0782 . S2CID 15941472 .
- ↑ Berland, Dinah (1995). Técnicas, materiales y prácticas de estudio de pintura histórica (PDF) . The Getty Conservation Institute.
- ↑ Wylie, Chris; Romney, Gordon; Evans, David; Erdahl, Alan (14 de noviembre de 1967). "Dibujos en perspectiva de semitonos por computadora" . Actas de la conferencia conjunta de informática de otoño del 14 al 16 de noviembre de 1967 - AFIPS '67 (Otoño) . Anaheim, California: Association for Computing Machinery. págs. 49–58 . doi : 10.1145/1465611.1465619 . ISBN 978-1-4503-7896-3. S2CID 3282975 .
- ^ Desai , Apurva (2008). Gráficos por computadora . PHI Aprendizaje Pvt. Limitado. ISBN limitado 9788120335240.
- 1 2 3 4 5 de Berg, Mark (2008). Geometría Computacional (PDF) . Springer. Archivado (PDF) del original el 3 de agosto de 2016.
- ↑ de Berg, Mark (1993). Ray Shooting, Depth Orders and Hidden Surface Removal . Lecture Notes in Computer Science. Vol. 703. Springer. p. 130. ISBN 9783540570202..
- ↑ Warnock, John E. (1969-06-01). "Un algoritmo de superficie oculta para imágenes de semitonos generadas por computadora" . Archivado del original el 8 de noviembre de 2020.
{{cite journal}}: Para citar una revista se requiere|journal=( ayuda ) - ↑ Freiser, M.; Marcus, P. (junio de 1969). "Un estudio de algunas limitaciones físicas en los elementos informáticos". IEEE Transactions on Magnetics . 5 (2): 82– 90. Bibcode : 1969ITM.....5...82F . doi : 10.1109/TMAG.1969.1066403 . ISSN 1941-0069 .
- ↑ Nyberg, Daniel (2011). Análisis de dos algoritmos comunes de eliminación de superficies ocultas, el algoritmo del pintor y el búfer Z.
Enlaces externos
- Algoritmos de Painter y Z-Buffer y renderizado de polígonos
- https://www.clear.rice.edu/comp360/lectures/old/HiddenSurfText.pdf
- https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/greene93.pdf
- Gráficos por computadora en 3D
- Algoritmos de gráficos por computadora
