Algorithme du peintre

En informatique, et plus précisément en imagerie numérique, 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.

Description

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 caméra, 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é.

Une mise en œuvre simpliste de l'algorithme du peintre peut être très lente. 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 consommera plus de ressources que nécessaire.

Extension

Agencement de polygones problématique pour l'algorithme du peintre.

Cet algorithme peut échouer 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.

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.

La partition binaire de l'espace (BSP) est une manière fréquemment utilisée pour « trier » les polygones.