Soit à représenter une courbe Z=f(X,Y), par exemple Z=sin(racine(X2+Y2)) qui définit une onde circulaire. Suivant le point de vue, on progresse en X ou Y pour commencer par les lignes les plus proches de l'oeil puis en s'éloignant. Comme pour un paysage montagneux, on utilise la méthode de la ligne de crêtes : la ligne de crêtes est la projection de la première ligne. Puis on étudie la ligne suivante. Segment par segment, soit le segment est projeté sous la ligne de crêtes, auquel cas il n'est pas dessiné, soit il est au dessus de la ligne de crête, on le dessine et on remet à jour la ligne de crête, soit il l'intersecte, on calcule alors l'intersection, on dessine à partir de l'intersection et on réaffecte la ligne de crête. On continue ainsi les tracés, la ligne de crête remontant progressivement.
- Dans le cas de courbes mathématiques, on utilise souvent une deuxième ligne de crêtes pour la limite inférieure.
- Plutôt que de calculer une ligne de crêtes exacte (formée d'un ensemble de segments difficiles à gérer du fait des problèmes d'insertions et de suppressions multiples), on peut se limiter à la définition de l'écran, c'est à dire créer un tableau donnant pour chaque pixel en Y la hauteur de la ligne de crêtes. Ceci n'est possible que si l'on possède le source de la bibliothèque de base (pour savoir quels pixels seront allumés).
Plusieurs algorithmes existent, mais aucun n'est parfait (en général très complexes pour prendre en compte les cas particuliers). Ces algorithmes fonctionnent avec des facettes planes (ou presque planes). Il est souvent plus facile de décomposer une surface complexe en facettes planes que de généraliser l'algorithme. Certains sont plus efficaces pour un dessin au trait (tracé des frontières de facettes), d'autres pour le tracé de faces colorées (remplissage des facettes). Les différents algorithmes ne peuvent être classés suivant leurs performance, car elles dépendent des cas traités (ou du moins des cas particuliers non traités).
Si le volume à dessiner est convexe, en demandant à l'utilisateur de définir chaque face avec un "coté matière" (par un point central ou un "sens trigo"), on ne dessinera une face que si sa "normale matière" est dirigée vers l'arrière (son produit scalaire avec le vecteur Oeil-Visé positif).
Cette méthode est simple à mettre en oeuvre, mais est limitée aux volumes convexes, ce qui est assez rare. Par contre pour les volumes non convexe, bien que cette méthode n'élimine pas toutes les faces cachées, elle permet d'en éliminer rapidement la moitié.
En classant les facettes de la plus éloignée à la plus proche, il suffit de les tracer dans l'ordre. Un tracé au trait est impossible (à moins de remplir les faces avec la couleur de fond, ce qui est impossible avec une table traçante), et le dessin est long (on trace et colorie un même point de l'écran autant de fois que de faces superposées). Le remplissage de surfaces doit fonctionner pour pouvoir "passer" sur les tracés précédents et non s'arrêter contre.
Mais le véritable problème est le classement des facettes. Dans certains cas la position relative de deux surfaces dépend d'autres surfaces :
|
Pour que l'algorithme du peintre fonctionne, il faut tracer dans ce cas en
dernier la face la plus éloignée. En effet, il ne faut comparer
la position que de surfaces dont les projections se superposent.
|
Cet exemple montre qu'il existe des cas où l'algorithme du peintre ne
peut s'appliquer. La seule solution dans ce cas est de couper une des faces en
deux. Dans le cas où les faces sont décomposées en petites
facettes planes, cet algorithme donne de très bons résultats
(utilisé dans de grands codes d'éléments finis par
exemple).
|
|
Pour chaque facette, on compare sa projection avec celles de toutes les autres facettes. Si les projections ont une intersection (prévoir aussi le cas d'un face cachant entièrement la facette), regarder la droite de projection passant par le point d'intersection, déterminer les points d'intersection avec les deux faces, modifier la frontière de la face cachée. Une fois les calculs terminés, on peut tracer la partie non cachée de la facette, s'il en reste une. Le tracé est rapide, mais le calcul long. Les calculs sont complexes (programme touffu), les cas particuliers nombreux (face cachée coupée en plusieurs sous-facettes visibles, une même arrête coupant plusieurs fois la surface...). Si l'on désire colorier les facettes, il faut un algorithme pour polygones non convexes et avec "trous". la meilleure preuve de la complexité de sa mise en oeuvre est l'existence des autres algorithmes
Pour chaque arrête : on teste sa visibilité par rapport à chaque facette. Soit elle est complètement cachée, on abandonne alors cette arrête. Soit elle est complètement vue (parce qu'elle est "devant", c.a.d dans le même demi-plan que l'oeil, soit sa projection est à l'extérieur de la projection de la facette) on passe à la prochaine facette (ou on dessine l'arête si toutes les facettes ont été traitées). Soit elle est partiellement cachée, on ne garde que la partie de l'arrête vue (qui peut former plusieurs nouveaux segments) dont on testera la visibilité par rapport aux facettes restantes. Cet algorithme n'est possible que pour un dessin au trait, le remplissage en couleurs des différentes facettes n'est pas possible avec cet algorithme. Si le modèle le permet, on gagnera du temps en ne traitant qu'une fois un segment faisant partie de deux facettes.
On divise la pyramide de vision en 4. Pour chaque nouvelle pyramide : soit aucune facette n'y entre, on abandonne alors la pyramide (rien à tracer). Soit une facette dépasse tout autour de la pyramide et elle est en avant des autres facettes qui entrent (tout ou en partie) dans la pyramide, on dessine toute la base de la pyramide dans la couleur de la facette (ou rien en cas de dessin au trait) et on l'abandonne. Dans tous les autres cas on partage la pyramide en 4, et on recommence. Lorsque l'on arrive à une pyramide de la taille d'un pixel, on allume le pixel de la couleur des frontières de facettes et on abandonne la pyramide (pas la peine d'être plus précis que le matériel). Cet algorithme est rapide quand il y a beaucoup de faces cachées et que le périphérique n'est pas trop précis. Le tracé est fait point par point (donc impossible sur table traçante) dans un ordre qui pourra paraître original à celui qui regarde la progression du dessin.
On fait passer un plan dans la scène correspondant à une droite de balayage de l'écran et contenant l'oeil. On analyse l'ensemble des intersections des facettes avec ce plan, ce qui nous donne un ensemble de droites coplanaires (avec pour chacune la couleur de la facette dont elle est issue). Il faut alors déterminer les parties vues et les parties (lignes) cachées dans le plan, ce qui est plus facile que dans l'espace. On utilise autant de plans que le permet la définition de l'écran.
Cet algorithme se prête bien aux problèmes de transparence, et du fait de sa similitude avec le matériel, au câblage ou la programmation de l'algorithme directement dans la carte graphique.
En partant de chaque pixel de l'écran on trace un rayon jusqu'à l'oeil, on calcule toutes les intersections entre les faces et ce rayon, puis on choisit la couleur de la surface la plus en avant. Ceci donne de longs calculs mais se prête au parallélisme et au câblage.
On peut donner une impression de réalisme à un dessin 3D en utilisant des niveaux d'éclairage. On suppose dans un premier temps une source lumineuse située dans la scène (si possible pas dans l'axe de projection). Chaque facette reçoit une couleur d'autant plus claire que la normale à cette surface est proche du rayon venant de la source lumineuse et traversant la surface (produit scalaire). Les résultats sont encore meilleurs avec plusieurs sources lumineuses, en prenant la somme des luminosités. Si l'on utilise des facettes qui peuvent être grandes, il faut soit calculer une luminosité variant sur la surface, soit découper en petites facettes (si les pas en couleurs sont assez faibles, le résultat sera satisfaisant). Pour un résultat vraiment réaliste, il faudrait en plus vérifier si les rayons lumineux ne sont pas coupés par une autre partie de la scène, et créer des ombres. Les calculs sont alors très longs, en général on triche en utilisant des sources lumineuses n'éclairant pas trop loin (l'intensité baisse avec la distance) et un choix manuel judicieux des différentes sources (assez nombreuses).
Soit on prévoit divers types de surfaces particulières (on prévoit les cylindres et sphères par exemple), soit on décompose en facettes planes, soit on essaie de trouver une formulation mathématique permettant de modéliser les surfaces gauches (appelées à tort surfaces non mathématiques). On se limite généralement à des approximations de surfaces suffisamment précises (y compris pour l'usinage). Elles correspondent en général à l'extension 3D des problèmes de lissage de courbes (avec des principes mathématiques plus puissants d'une dimension).
Après le problème de la représentation mathématique de ces surfaces, le premier problème est celui de la détermination des tangentes. Les cas particuliers se traitent surtout empiriquement (j'ai traité plus haut les cylindres), dans le cas général, après rotation de la surface correspondant au point de vue, on cherche l'ensemble des Z max (type ligne de crêtes) soit par tests itératifs, soit par dérivation (dérivée seconde nulle). On peut aussi utiliser un méthode de type "division de pyramide" pour traiter la surface.
Autre problème rencontré, les portions de surface cachées. Une solution couramment employée consiste à décomposer la surface en petites facettes planes. Pour une visualisation acceptable, les erreurs dues à la décomposition en facettes doivent être inférieures à la définition de l'organe de tracé.
