Algoritmo do pintor

O algoritmo do pintor é unha das solucións máis sinxelas ao problema de visibilidade nos gráficos por ordenador 3D. Cando se quere proxectar unha escena 3D nun plano 2D, nalgún momento é necesario decidir que polígonos son visíbeis e cales están ocultos.

Obxectos sobrepostos poden provocar o fallo do algoritmo

Exemplo

Para unha paisaxe, primeiro pintas as montañas ao fondo, despois o prado e só despois os obxectos máis próximos, como árbores.

O nome de algoritmo refírese a un pintor que primeiro pinta as partes distantes dunha escena e despois as cobre coas partes máis próximas. Do mesmo xeito, o algoritmo do pintor ordena todos os polígonos pola súa profundidade e despois píntaos nesa orde. Superpón as partes normalmente non visibles e así resolve o problema de invisibilidade.

Polígonos sobrepostos poden causar un fallo no algoritmo

O algoritmo pode fallar en certos casos. Neste exemplo, os polígonos A, B e C superpóñense. Non é posible definir que polígono está enriba dos outros ou cando dous polígonos se cruzan en tres dimensións.

Nas implementacións básicas, o algoritmo do pintor pode ser ineficiente. Forza ao sistema a renderizar cada punto de cada polígono no campo visual, aínda que o polígono estea oculto na escena final. Isto significa que para escenas detalladas, o algoritmo do pintor é unha solución ineficiente.

Este e outros defectos do algoritmo levaron ao desenvolvemento de técnicas de Z-buffering, que se poden ver como un desenvolvemento do algoritmo do pintor para resolver conflitos de profundidade píxel por píxel, reducindo a necesidade de renderización baseada en profundidade. Mesmo en tales sistemas, ás veces úsase unha variante do algoritmo do pintor. Como as implementacións do Z-buffer a miúdo dependen de rexistros de buffer de profundidade de precisión fixa no hardware, hai posibilidades de problemas de visibilidade debido a erros de redondeo. Estes erros son superposicións ou espazos nas unións entre polígonos. Para evitalos, algunhas implementacións do motor gráfico "overrender" - debuxando os bordos afectados de ambos polígonos en orde polo algoritmo do pintor. Isto significa que algúns píxeles son debuxados dúas veces (como no algoritmo de pintor completo), pero isto só ocorre en pequenas partes da imaxe e ten un efecto insignificante no rendemento.

Un problema particular na aplicación do algoritmo do pintor é o de obxectos translúcidos ou transparentes.

Véxase tamén

Outros artigos

• Gráficos por ordenador 3D
• Renderizado

Ligazóns externas

• Painter's & Z-Buffer Algorithms and Polygon Rendering
• https://www.clear.rice.edu/comp360/lectures/old/HiddenSurfText.pdf
• https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/greene93.pdf