- Algorithme du peintre
-
L´algorithme du peintre est l'une des solutions les plus simples pour résoudre le problème de visibilité d'un rendu en 3D sur ordinateur. En effet, une fois une scène 3D projetée sur un plan 2D, il est nécessaire de déterminer quels sont les polygones visibles, et les polygones cachés.
Les montagnes sont dessinées en premier, puis la prairie et les collines, plus proches, recouvrent leur base. Viennent ensuite les arbres, qui sont eux au premier plan.
Le nom d'« algorithme du peintre » fait référence à un peintre qui dessinerait les parties lointaines d'une scène avant les parties proches. L'algorithme du peintre trie tous les polygones de la scène par rapport à leur distance de la camera, du plus éloigné au plus proche, et les dessine dans cet ordre. Cela aura pour effet d'afficher les plus lointains avant les plus proches, ces derniers recouvrant les autres. Cela résout le problème de visibilité.
Agencement de polygones problématique pour l'algorithme du peintreCet algorithme peut faillir dans certains cas (très courants). Dans le cas où 2 polygones s'intersectent sur l'axe perpendiculaire au plan de la caméra (généralement noté Z en infographie), l'algorithme ne pourra pas calculer convenablement quel polygone afficher en premier.
Sur des implémentations basiques, l'algorithme du peintre peut être lent. Il oblige le système à afficher chaque point de chaque polygone, même si ce polygone est complètement caché par un autre une fois le rendu de la scène terminé. Cela veut dire que dans des scènes détaillées, cet algorithme consomme plus de ressources que nécessaire.
Cette faille (parmi d'autres) a conduit au développement de la technique du tampon de profondeur (Z-buffer), qui peut être vue comme une extension de la réflexion sur cet algorithme. Au lieu de considérer un polygone comme une entité indivisible, le Z-buffer part du principe que le polygone est constitué d'un ensemble de pixels avec chacun leur profondeur par rapport à la caméra. Pour des raisons pratiques et comme un ordinateur est un système discret, on procède à un test simple entre la profondeur du pixel à afficher et celle de l'éventuel pixel déjà à l'écran.
Cela n'empêche pas le tri de polygone d'être utilisé dans certains cas, y compris avec l'appui du Z-Buffer, pour la gestion des faces transparentes par exemple.
Catégorie :- Algorithme d'infographie
Wikimedia Foundation. 2010.
