Algoritmo del pintor

El algoritmo del pintor es una de las soluciones más simples para el problema de visibilidad en los gráficos 3D por computadora: Cuando se proyecta una escena de tres dimensiones en un plano de dos, es necesario determinar qué polígonos son visibles y cuáles no.

El nombre "algoritmo del pintor" se refiere a un pintor que primero dibuja los elementos lejanos de una escena y después los cubre con los más cercanos. El algoritmo del pintor ordena todos los polígonos de una escena en función de su profundidad y después los pinta en ese orden, pintando encima de las partes que no son visibles y solucionando así el problema de la visibilidad.

Se pintan primero las montañas lejanas, seguidas por el prado; finalmente se dibujan los objetos más cercanos, los árboles.

Los polígonos superpuestos pueden provocar que el algoritmo falle.

El algoritmo puede fallar en determinados casos. En este ejemplo, los polígonos A, B y C están superpuestos. No es posible determinar qué polígono está por encima de los otros o cuándo dos se intersecan en tres dimensiones. En este caso, los polígonos en cuestión deben ser cortados de alguna manera para permitir su ordenación. El algoritmo de Newell propuesto en 1972 da una solución para cortar dichos polígonos. También se han propuesto numerosos métodos en el campo de la geometría computacional.

En las implementaciones más básicas, el algoritmo del pintor puede ser poco eficiente, ya que fuerza al sistema a renderizar cada punto de todos los polígonos visibles, incluso si estos polígonos están ocultos en la escena final. Esto implica que, en las escenas detalladas, el algoritmo del pintor puede consumir demasiados recursos.

Estas y otras causas llevaron al desarrollo de las técnicas que emplean el Z-Buffer, que pueden ser vistas como un desarrollo del algoritmo del pintor que resuelve los conflictos de profundidad píxel por pixel, reduciendo la necesidad de una ordenación por profundidad. Incluso en estos sistemas, a veces se emplea una variante del algoritmo del pintor. Como las implementaciones del Z-Buffer generalmente se basan en un buffer limitado de profundidad implementado por hardware pueden producirse problemas de visibilidad debido a los errores de redondeo, provocando la superposición en la unión de dos polígonos. Para evitarlo, algunos motores gráficos implementan el "sobrerenderizado", dibujando los bordes de ambos polígonos en el orden impuesto por el algoritmo del pintor. Esto significa que algunos pixeles se dibujan dos veces (como en el algoritmo del pintor normal), pero sólo ocurre en pequeñas zonas de la imagen y apenas afecta al rendimiento.