Algoritmo del pittore

L'algoritmo del pittore, conosciuto anche come riempimento prioritario, è una delle soluzioni più semplici al problema della visibilità nella computer grafica. Quando si rappresenta una scena tridimensionale su un piano bidimensionale è necessario decidere quali poligoni sono visibili e quali saranno nascosti.

Il nome dell'algoritmo si riferisce al semplice metodo usato dai pittori che disegnano prima le parti distanti della scena e poi le ricoprono con le parti più vicine. L'algoritmo del pittore ordina tutti i poligoni nella scena per la loro profondità e successivamente li disegna in ordine. ^[1] In questo modo le parti nascoste saranno ridipinte con le parti visibili, a scapito del costo di dover ridisegnare delle aree della scena.

L'algoritmo può fallire in alcuni casi. In questo esempio, i poligoni A, B e C si sovrappongono. Non è possibile decidere quale poligono è sopra gli altri. ^[2] In questo caso i poligoni devono essere tagliati in qualche modo per consentire l'ordinamento. L'algoritmo di Newell proposto nel 1972 fornisce un metodo per il ritaglio di questi poligoni. Numerosi altri metodi sono stati proposti nel campo della geometria computazionale.

Nella sua implementazione di base, l'algoritmo del pittore può essere inefficiente. Esso forza il sistema a renderizzare ogni punto di tutti i poligoni nell'insieme visibile, anche se qualche poligono risulterà nascosto nella scena finale.

L'algoritmo del pittore invertito ^[3] è a volte usato disegnando prima gli oggetti vicini al pittore - con la regola che le parti già disegnate non saranno ridisegnate. Questo può essere molto efficiente poiché non è necessario calcolare i colori per le parti che sono distanti e sono nascoste dagli oggetti vicini. Tuttavia, l'algoritmo inverso soffre degli stessi problemi della versione normale.

Questo e altri difetti dell'algoritmo portarono allo sviluppo della tecnica dello Z-buffer, che può essere visto come uno sviluppo dell'algoritmo del pittore che risolve i conflitti di profondità, rimuovendo la necessità di un ordinamento di rendering basato sulla profondità.

Note

^ (2008) Binary Space Partitions. In: Computational Geometry. Springer, Berlin, Heidelberg, Chapter 12, p 259. ISBN 9783540779742
^ (2008) Binary Space Partitions. In: Computational Geometry. Springer, Berlin, Heidelberg, Chapter 12, p 260. ISBN 9783540779742
^ (2004) Developing Games in Java. In: New Riders Games Series. Brackeen, D., Barker, B., Vanhelsuwé, L. New Riders., p. 485. ISBN 9781592730056

Altri progetti

Wikimedia Commons contiene immagini o altri file su Algoritmo del pittore

[1] (2008) Binary Space Partitions. In: Computational Geometry. Springer, Berlin, Heidelberg, Chapter 12, p 259. ISBN 9783540779742

[2] (2008) Binary Space Partitions. In: Computational Geometry. Springer, Berlin, Heidelberg, Chapter 12, p 260. ISBN 9783540779742

[3] (2004) Developing Games in Java. In: New Riders Games Series. Brackeen, D., Barker, B., Vanhelsuwé, L. New Riders., p. 485. ISBN 9781592730056

[1]

[2]

[3]