Algorithmique de
base de l'Infographie

CLIPPING

REMPLISSAGE
2D
Polygone convexe
Polygone non convexe
Zones de pixels
de couleur

RETOUR

0. Problématique

Comme dans nombre de domaines de l'informatique, l'informatique graphique fait appel à un certain nombre d'algorithmes de base utilisés de façon directe ou indirecte pour l'implantation d'autres algorithmes. Le bon fonctionnement de ces algorithmes est requis tout autant que leur fonctionnement optimal compte tenu des caractéristiques propres des dispositifs matériels sur lesquels ils sont exécutés (en particulier processeurs nombreux, mais simples et développés spécifiquement). L'optimisation de ces algorithmes est donc un but en soi.
Ce chapitre présente quelques algorithmes classiques :
  - de tracé,
  - de découpage,
  - de remplissage.

1. Dessin 2D des objets de base

1.1. Tracé de segments de droite

Le tracé de segments de droite est l'algorithme de base pour beaucoup de traitements de l'informatique graphique :
  - Dessin en fil de fer
  - Remplissage de polygone
  - Elimination des parties cachées
  - ...

Cet algorithme doit être efficace car "mis à toutes les sauces".

Problème : On désire tracer un segment entre deux points (xi,yi) et (xf,yf) de R².
Ce tracé est effectué sur un écran bitmap (composé d'une matrice de n x m pixels carrés).
-> Le segment doit être discrétisé (rasterisé).

Question : Quels pixels doit-on tracer ?

Trois impératifs:
  - On ne doit pas "dévier".
     -> Tout pixel du segment discret doit être traversé par le segment continu.
  - On ne doit pas laisser de trou.
     -> Tout pixel du segment discret doit toucher au moins un autre pixel soit par l'un de ses cotés, soit par un de ses sommets (8-connexité).

   - On doit obtenir les meilleures performances possibles.
     -> Aussi peu de pixels que possible doivent être tracés.

Compte tenu de ces impératifs et du fait qu'un segment de droite est tracé (coefficient directeur constant) et pas un autre type de courbe, 1+max(abs(xi-xf),abs(yi-yf)) pixels sont tracés. C'est à dire, si abs(xi-xf) < abs(yi-yf), un pixel et un seul par ligne interceptant le segment est tracé, sinon un pixel et un seul pixel par colonne interceptant le segment est tracé.

1.1.1. Tracé de segments par l'équation cartésienne

On souhaite tracer le segment de droite qui va du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf).

On pose comme hypothèse simplificatrice : xf > xi, yf >= yi et (xf-xi) >= (yf-yi). Tous les autres cas peuvent s'y rapporter.
-> Le coefficient directeur de la droite passant par les deux sommets est positif ou nul et inférieur ou égal à 1.

L’équation cartésienne de la droite est utilisé : y = a x + b avec a et b réels calculés de la façon suivante : a = et b = yi - a xi
Compte tenu des hypothèses posées ci-dessus, xf-xi ne peut pas être égal à 0, il n'y a donc pas de risque de division par zéro.

L'algorithme de tracé du segment de droite allant du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf) peut être implanté de la façon suivante :

/* Trace un segment de droite entre le pixel  */
/* de coordonnées (xi,yi) et le pixel         */
/* de coordonnées (xf,yf)                     */

void ligne(int xi,int yi,int xf,int yf) {
  double a =(double) (yf-yi)/(xf-xi) ;
  double b = yi - a * xi ;
  for ( int x = xi ; x <= xf ; x++ ) {
    int y =(int) (a * x + b) ;
    allume_pixel(x,y) ; }
}

Il a été construit sur la base d'une itération x de xi à xf avec calcul au moyen de l'équation cartésienne, pour chaque x, de la coordonnée y entière et allumage du pixel de coordonnées (x,y).

Caractéristiques :

L'algorithme est d'une grande simplicité algorithmique.
Une certaine lenteur est possible à cause de l'utilisation de réels, d'une division, de multiplications et de casts réel vers entier.
Une implantation hard sera peut-être complexe car les types utilisés et les opérations utilisées sur ces types devront être prévues.

1.1.2. Tracé de segments par algorithme Bresenham (algorithme du point milieu, algorithme du mid-point)

On souhaite tracer le segment de droite qui va du pixel de coordonnées (xi,yi) au pixel de coordonnées (xf,yf). On souhaite pouvoir n'utiliser que des variables entières et des opérations simples : addition, soustraction, tests.

L'algorithme de Brésenham est un algorithme incrémental en x et en y, c'est à dire que la position d'un pixel tracé est directement calculée à partir de la position du pixel tracé immédiatement avant lui. En l'occurrence, les incréments sont unitaires en x et en y car, comme on trace en 8-connexité, on trace toujours le pixel suivant parmi les 8 voisins du précédent. L'algorithme va donc utiliser deux variables entières x et y respectivement initialisées à xi et xf, et faire varier ces deux variables pour qu'elles prennent successivement les valeurs correspondant à tous les pixels à tracer, pour finir bien entendu avec x=xf et y=yf.

On pose de nouveau les hypothèses : xf > xi, yf >= yi, xf - xi > yf - yi. Toutes les autres situations peuvent s'y rapporter.
Compte tenu de ces hypothèses un pixel de coordonnées (x,y) est allumé en chaque abscisse entière de xi à xf. L'algorithme peut donc être construit sur la base d'un amorçage du processus incrémental par allumage préalable du pixel de coordonnées (xi,yi) suivi d'une itération simple par pas de 1 pour x de xi+1 à xf inclus.
Le problème de la gestion de la variable x étant résolu, la valeur y utilisée en chacun des x reste à déterminer. A chaque incrément de 1 de la variable x, soit la variable y reste inchangée, soit elle subit un incrément de 1. Il faut donc définir un critère permettant d'arbitrer entre ces deux possibilités.
Le principe de calcul des y fait appel à l'idée qu'un déplacement de 1.0 (1 pixel) en x se traduit sur le segment de droite réel par un déplacement en y de valeur a = (yf-yi)/(xf-xi) en valeur réel (interprétation intuitive du coefficient directeur). On peut aussi dire qu'un déplacement de dx=xf-xi en x sur le segment de droite réel s'accompagne d'un déplacement de dy=yf-yi en y. Il faudra en fait en moyenne 1.0/a=dx/dy déplacement(s) de 1 pixel en x pour qu'un déplacement de 1 pixel en y soit réalisé. Une variable entière cumul est utilisée pour stocker un indicateur numérique qui va permettre de savoir si lors d'une incrémentation de 1 opérée sur x, y doit rester inchangé ou bien doit être incrémenté de 1. A chaque incrément de x, cumul est incrémentée de dy. Si à l'issue de cette incrémentation cumul contient une valeur supérieure ou égale à dx, cela signifie que le nombre d'incréments réalisés sur x depuis le dernier incrément sur y justifie un nouvel incrément sur y. On opère donc cet incrément et on retranche dx à cumul pour le faire redescendre en dessous de dx.
Le dernier problème à résoudre consiste à déterminer la valeur d'initialisation de la variable cumul. Un choix logique consiste à l'initialiser à la valeur dx/2 qui sera aussi sa valeur finale en fin de tracé. Ainsi, on peut espérer qu'il y aura antant de pixels tracés à y = yi que de pixels tracés à y = yf, ce qui équilibre la suite de pixels globalement tracée.

Algorithme (langage C)

/* Trace un segment de droite entre le pixel  */
/* de coordonnées (xi,yi) et le pixel         */
/* de coordonnées (xf,yf)                     */

void ligne(int xi,int yi,int xf,int yf) {
  int x = xi ;
  int y = yi ;
  int dx = xf - xi ;
  int dy = yf - yi ;
  int cumul = dx / 2 ;
  allumePixel(x,y) ;
  for ( x = xi+1 ; x <= xf ; x++ ) {
    cumul += dy ;
    if ( cumul >= dx ) {
      cumul -= dx ;
      y += 1 ; }
    allumePixel(x,y) ; }
}

Remarque : Le descriptif de fonctionnement donné ci-dessus n'est pas une preuve du bon fonctionnement de l'algorithme, c'est à dire du fait qu'il trace bien un segment de droite. Il ne s'agit que d'une explication concrête de son fonctionnement.
La preuve n'est pas donnée ici. Elle est basée sur la même méthode que celle proposée pour l'algorithme de tracé d'arc de cercle donné ci-dessous.

Exercice : Prouver que le dernier pixel tracé est bien le pixel de coordonnées (xf,yf). Solution

Caractéristiques

La complexité algorithmique apparente de l'algorithme de Bresenham est plus importante que l'algorithme utilisant directement l'équation cartésienne.

L'objectif de rapidité due à l'utilisation exclusive d'entiers et d'opérateurs arithmétiques simples sur ces entiers (additions, soustractions, décalages binaires et tests comparaisons) est atteint.

L'objectif de simplification de l'architecture matérielle due à l'utilisation exclusive d'entiers courts (valeurs maximales de l'ordre de la résolution de l'écran -> petites valeurs) et à la limitation des opérations utilisées sur ces entiers est atteint.

Algorithme adapté pour le tracé de tout segment

La généralisation de l'algorithme ci-dessus à toutes les situations de placement relatif des pixels de coordonnées (xi,yi) et (xf,yf) demande deux évolutions.
(1) On utilise deux variables xinc et yinc pour gérer des incréments de 1 ou -1 pour x variant de xi à xf et y variant de yi à yf.

Les 4 quadrants définissant les valeurs d'incrément xinc et yinc
à partir de la position centrale de coordonnées (xi,yi)

(2) L'algorithme est implanté en deux parties alternatives dont les exécutions sont arbitrées en fonction des valeurs relatives de abs(xf-xi) et abs(yf-yi) :
  - Dans la première partie, si abs(xf-xi) > abs(yf-yi) c'est à dire si le segment de droite est "plutôt horizontal" (zones (1) ci-dessous), la boucle for est construite sur x pour incrémenter par pas de 1 systématique en x. Ce sont donc les y qui sont déterminés de façon incrémentale.
  - Dans la seconde partie, si abs(xf-xi) <= abs(yf-yi) c'est à dire si le segment de droite est "plutôt vertical" (zones (2) ci-dessous), la boucle for est construite sur y pour incrémenter par pas de 1 systématique en y. Ce sont alors les x qui sont déterminés de façon incrémentale.

Les 8 octants définissant les axes sur lesquels des itérations sont construites
pour le tracé d'un segment à partir du pixel initial de coordonnées (xi,yi) :
(1) sur l'axe x, (2) sur l'axe y

/* Trace un segment de droite entre le pixel  */
/* de coordonnées (xi,yi) et le pixel         */
/* de coordonnées (xf,yf)                     */

void ligne(int xi,int yi,int xf,int yf) {{
  int x = xi ;
  int y = yi ;
  int dx = xf - xi ;
  int dy = yf - yi ;
  int xinc = ( dx > 0 ) ? 1 : -1 ;
  int yinc = ( dy > 0 ) ? 1 : -1 ;
  dx = abs(dx) ;
  dy = abs(dy) ;
  allumePixel(x,y) ;
  if ( dx > dy ) {
    int cumul = dx / 2 ;
    for ( int i = 1 ; i <= dx ; i++ ) {
      x += xinc ;
      cumul += dy ;
      if ( cumul >= dx ) {
        cumul -= dx ;
        y += yinc ; }
      allumePixel(x,y) ; } }
    else {
    int cumul = dy / 2 ;
    for ( int i = 1 ; i <= dy ; i++ ) {
      y += yinc ;
      cumul += dx ;
      if ( cumul >= dy ) {
        cumul -= dy ;
        x += xinc ; }
      allumePixel(x,y) ; } }
}

Exemples d'exécution

On souhaite tracer le segment (3,2)-(18,11).
Les valeurs caractéristiques dx et dy calculées sont dx = 18-3 = 15, dy = 11-2 = 9.

1.2. Tracé de cercle par algorithme de Bresenham

On désire tracer un arc de cercle de centre O et de rayon r circonscrit au deuxième octant du plan.

Tracé par rasterisation d'un arc de cercle de centre O et de rayon r
réduit au second octant du plan

On trace un arc de pixels entre les pixels de coordonnées (0,r) et (,).
Un pixel sera allumé sur chaque colonne d'abscisse comprise entre 0 et .

Principe de l'algorithme

Comme dans le cadre de l'algorithme de Bresenham pour le tracé de segments, le tracé du cercle est réalisé incrémentalement :
La position d'un pixel P dépend de la position du pixel précédemment tracé. Elle est déterminée via l'évaluation de la position de P au dessus ou en dessous de l'arc réel.

Si un pixel est allumé en position (x,y), le prochain pixel sera obligatoirement soit en position (x+1,y) soit en position(x+1,y-1) (tangente au cercle de coefficient directeur compris entre 0.0 et -1.0 sur notre arc).

Positionnement des points intermédiaires

L'algorithme est basé sur l'étude, pour chaque colonne de pixels, de la position (vis à vis du cercle continu : au dessus ou en dessous) du point intermédiaire entre les deux pixels superposés candidats définis ci-dessus qui encadrent le cercle (d'oú le nom d'algorithme du mid-point aussi utilisé pour cet algorithme).

Si ce point intermédiaire est situé dans le cercle, le pixel allumé sera le pixel (x+1,y) situé en dehors du cercle (cas du pixel E₁ ci-dessous). Sinon, le pixel (x+1,y-1) situé à l'intérieur du cercle est allumé (cas du pixel E₂ ci-dessous).

Positionnement des points intermédiaires

L'idée de l'algorithme est donc de définir la "position" de chaque point intermédiaire de façon incrémentale, colonne de pixels après colonne de pixels.

La position d'un point P de coordonnées (x,y) vis à vis du cercle continu est établie à partir de l'équation cartésienne f(x,y) = x² + y² - r².
-> Si f(x,y) < 0, P est dans le cercle, sinon il est à l'extérieur.

Première possibilité : L'obtention d'un résultat négatif pour cette équation (cercle rouge ci-dessous) pour un point intermédiaire M conduit au choix du pixel extérieur E. Le prochain point intermédiaire sera situé en M_E, c'est à dire un pixel à droite de M.

Choix entre pixels candidats

Seconde possibilité : Un résultat positif (cercle vert ci-dessus) conduit au choix du pixel intérieur SE, et au prochain point intermédiaire M_SE situé un pixel à droite et un pixel plus bas que M.

Définition récurente de l'algorithme

P = (xp,yp) est la position d'un pixel allumé.

La variable d (évaluant la position du point intermédiaire vis à vis du cercle) calculée à partir de P est

d = f(xp+1,yp-) = (xp+1)² + (yp-)² - r²             (1)

(1) Si d est inférieur à 0, E est choisi. Le prochain point intermédiaire est alors M_E et la nouvelle valeur de d est calculée de la manière suivante :

d_new = f(xp+2,yp-) = (xp+2)² + (yp-)² - r²

-> d = d_new = d + (2xp + 3) par substitution avec l'équation (1)

(2) Si d est supérieur à 0, SE est choisi. Le prochain point intermédiaire est M_SE et la nouvelle valeur de d est calculée de la manière suivante :

d_new = f(xp+2,yp-) = (xp+2)² + (yp-)² - r²

-> d = d_new = d + (2xp - 2yp + 5) par substitution avec l'équation (1)

-> On obtient une définition incrémentale (récurrente) de d n'utilisant que des entiers (coordonnées des pixels).

La première valeur de d est obtenue à partir de la position (0,r) pour un premier point intermédiaire de position placée en (1,r-).

-> d = d_init = 1 + r² - r + - r² = - r.

-> en entier: d = d_init = 1 - r.

Sitôt que l'algorithme conduit à une valeur xp >= yp, son exécution est arrêtée car la diagonale est atteinte.

Les conditions initiales étant connues, la récurrence étant définie, la condition d'arrêt étant fixée, on connaît maintenant totalement la définition récurrente de d.

Implantation

Le tracé d'un arc de cercle réduit au second octant centré sur l'origine où le rayon r est un paramètre entier placé en entête est réalisé par la fonction suivante :

/* Trace un arc de cercle de rayon r,         */
/* centre sur l'origine et                    */
/* reduit au deuxieme octant du plan          */

void arcDeCercle(int r) {
  int x,y,d ;
  x = 0 ;
  y = r ;
  d = 1 - r ;
  allumePixel(x,y) ;
  while ( y > x ) {
    if ( d < 0 )
      d += 2 * x + 3 ;
      else {
      d += 2 * (x - y) + 5 ;
      y-- ; }
    x++ ;
    allumePixel(x,y) ; }
}

Exemples d'exécution

Cette fonction pourra ensuite être adaptée (au moyen de symétries) pour tracer un cercle complet.

1.3. Tracé d'ellipses

Un algorithme incrémental de tracé d'ellipses basé sur une technique du midpoint peut être défini sur des principes voisins de ceux utilisés pour le segment de droite et l'arc de cercle. Le travail est plus complexe par le fait que le tracé à l'intérieur d'un quadrant n'est plus symétrique par rapport à la diagonale.

Tracé d'une ellipse sur un quadrant du plan

L'algorithme réalise le tracé en deux passes consécutives pour un quadrant. Par exemple pour le quadrant 1, une passe avec un pixel par colonne pour la région 1 et une passe avec un pixel par ligne pour la région 2. La limite entre ces deux régions est le point où la pente est de -1.

/* Trace un arc d'ellipse de demi-axe           */
/* horizontal de longueur a et de demi-axe      */
/* vertical de longueur b, centre sur l'origine */
/* et reduit au premier quadrant du plan        */

void arcEllipse(long a,long b) {
  int x,y ;
  double d1,d2 ;
  x = 0 ;
  y = b ;
  d1 = b*b - a*a*b + a*a/4 ;
  allume_pixel(x,y) ;
  while ( a*a*(y-.5) > b*b*(x+1) ) {
  if ( d1 < 0 ) {
    d1 += b*b*(2*x+3) ;
    x++ ; }
    else {
    d1 += b*b*(2*x+3) + a*a*(-2*y+2) ;
    x++ ;
    y-- ; }
  allume_pixel(x,y) ; }
  d2 = b*b*(x+.5)*(x+.5) + a*a*(y-1)*(y-1) - a*a*b*b ;
  while ( y > 0 ) {
  if ( d2 < 0 ) {
    d2 += b*b*(2*x+2) + a*a*(-2*y+3) ;
    y-- ;
    x++ ; }
    else {
    d2 += a*a*(-2*y+3) ;
    y-- ; }
  allume_pixel(x,y) ; }
}

2. Clipping (découpage)

Définition

Clipping écran : Traitement permettant de réduire le dessin d'un objet graphique à une région de l'écran.
Cette région est classiquement un rectangle mais peut être de toute autre forme.
Le clipping peut aussi être réalisé en 3D.

Exemple : Clipping de 2 segments à l'intérieur d’un rectangle.

Le clipping dans un rectangle à bords horizontaux et verticaux, typiquement une fenêtre, est un des traitements de base de l'informatique graphique. Son implantation impose l'efficacité d'exécution. Une démarche consistant à calculer tous les pixels qui devraient être afficher sans clipping et n'afficher réellement que ceux qui sont dans le rectangle est donc inenvisageable. Le clipping se présentera donc comme un prétraitement consistant à déterminer la (ou les) partie de l'objet qui devra réellement être affichée et à l'afficher.

Algorithme de Cohen-Sutherland pour le clipping d'un segment à l’intérieur d’un rectangle

Cet algorithme est basé sur la détection d’un certain nombre de configurations de placement d'un segment relativement à un rectangle.

On associe à chacune des deux extrémités du segment un code défini sur quatre valeurs pseudo booléennes permettant de repérer la position (x,y) du sommet par rapport aux 2 droites verticales et aux 2 droites horizontales définissant le rectangle de clipping (xmin, xmax)-(ymin, ymax) :
  - première valeur = 1 si x < xmin, 0 sinon,
  - deuxième valeur = 1 si x > xmax, 0 sinon,
  - troisième valeur = 1 si y < ymin, 0 sinon,
  - quatrième valeur = 1 si y > ymax, 0 sinon.

Dans deux situations on sait si un segment de coordonnées (xi,yi)-(xf,yf) est entièrement à l'intérieur ou entièrement à l'extérieur du rectangle (xmin,ymin)-(xmax,ymax) :
  - Si les codes des deux extrémités sont égaux à 0000 (cas (1) en bleu ci-dessous), le segment est forcément entièrement dans le rectangle de clipping car ses deux extrémités sont dans le rectangle de clipping. On alors sait que le prétraitement est fini et que la conclusion est que le segment peut être entièrement tracé.
  - Si le "et" entre les deux codes est différent de 0000, c'est à dire si les deux codes ont un 1 en commun en position 1, 2, 3 et/ou 4, le segment est forcément situé entièrement à l’extérieur du rectangle de clipping (cas (3) en vert ci-dessous) car les deux extrémités sont simultanément au dessus, en dessous, à droite et/ou à gauche du rectangle de clipping. On sait alors que le prétraitement est fini et que la conclusion est que rien ne doit être tracé.

Dans une autre situation on sait qu'un segment de coordonnées (xi,yi)-(xf,yf) est partiellement à l’intérieur du rectangle (xmin,ymin)-(xmax,ymax) :
  - Si un seul des codes des deux extrémités est égal à 0000, le segment est pour partie dans le rectangle de clipping (cas (2) en rouge ci-dessous). On sait que l'on aura à tracer, mais on sait pas encore quoi avec certitude.

Dans toutes les autres situations, on ne peut pas conclure (cas (4) en rose ci-dessous). On ne sait même pas si on aura à tracer quelque chose ou non.

Principe de l'algorithme

A partir du segment S initial, les extrémités de S sont déplacées sur la droite sous-tendue par S vers les droites AB, BD, AC ou CD définissant le rectangle de clipping ABDC. Le but est de transformer S de façon qu'il devienne entièrement extérieur à ABDC (cas (3)) ou entièrement intérieur à ABDC (cas (1)). Le nombre de déplacements nécessaires n'est pas connu a priori. Dans le cas où les deux extrémités sont déjà dans ABDC, il n'y a même aucun déplacement à faire. L'algorithme est donc construit sur une boucle de type "tant que" dont la condition de continuation est que le segment S n'est ni en situation (1) ni en situation (3) vis à vis de ABCD. Dans cette boucle, chaque fois qu’il est établi qu'un code d'une extrémité présente un 1, on déplace cette extrémité pour qu'elle vienne rejoindre celle des droites AB, BD, AC ou CD qui correspond au 1 trouvé. Ainsi, on change le code de cette extrémité avec pour éventuelle conséquence la fin de la boucle.

Exemples

Déplacement des extrémités des segments de droite
au cours du fonctionnement de l'algorithme de Cohen-Sutherland

La figure ci-dessus présente les deux segments S1 de P_1i à P_1f (en rose) et S2 de P_2i à p_2f (en orange) à clipper dans le rectangle ABDC. Les valeurs élémentaires des codes sont traitées de gauche à droite.

Le traitement de S1 commence avec P_1i et P_1f de codes respectifs 1010 et 0101 qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. L'extrémité P_1i possède un code différent de 0000 et est donc déplacée. Son code présente un 1 en position 1, P_1i est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite verticale AC en position (1) rose. Son code devient 0000. P_1i et P_1f ont maintenant 0000 et 0101 pour codes respectifs qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. Le code de P_1i est égal à 0000, on passe donc au traitement de P_1f. Son code présente en 1 en position 2, P_1f est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite verticale BD en position (2) rose avec pour code 0001. P_1i et P_1f ont maintenant 0000 et 0001 pour codes respectifs qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. Le code de P_1f présente en 1 en position 4, P_1f est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite horizontale AB en position (3) rose avec pour code 0000. P_1i et P_1f ont maintenant 0000 et 0000 pour codes respectifs qui sont tous deux égaux à 0000. On peut donc tracer le segment de droite qui va du point (1) rose au point (3) rose. Trois changements de position auront été nécessaires. A noter : Le point (0) vert n'a pas eu à être atteint.

Le traitement de S2 commence avec P_2i et P2_f de codes respectifs 0001 et 1000 qui ne sont pas tous deux égaux à 0000 et qui n'ont pas de 1 en commun. L'extrémité P_2i possède un code différent de 0000 et est donc déplacée. Son code présente un 1 en position 4, P_2i est donc déplacée sur la droite sous-tendue par S pour rejoindre la droite horizontale AB en position (1) orange avec pour code 1000. P_2i et P_2f ont maintenant 1000 et 1000 pour codes respectifs qui ont un 1 commun en position 1. On peut donc conclure que le segment S2 originel était entièrement en dehors de ABDC et qu'il n'y a donc rien à tracer. Un seul changement de position aura été nécessaire. A noter : Le point (0) cyan n'a pas eu à être atteint.

Algorithme (pseudo langage C)

/* Trace le segment de droite allant du pixel p1 */
/* au pixel p2, clippe dans la fenetre f         */

struct Point2D {
  int x;
  int y; }

struct Fenetre {
  int xmin;
  int xmax;
  int ymin;
  int ymax; }

void clip(Point2D p1,Point2D p2,Fenetre f) {
  code c1 = code(p1,f);
  code c2 = code(p2,f);
  tant que (c1 ou c2 contient un 1) et
           (c1 et c2 n'ont pas de 1 commun) {
    si c1 égal 0000 {
      permuter p1 et p2;
      permuter c1 et c2; }
    si c1 a un 1 en position 1 {
      p1.y = ordonnée du point d'abscisse f.xmin sur (p1,p2);
      p1.x = f.xmin; }
      sinon
      si c1 a un 1 en position 2 {
        p1.y = ordonnée du point d'abscisse f.xmax sur (p1,p2);
        p1.x = f.xmax; }
        sinon
        si c1 a un 1 en position 3 {
          p1.x = abscisse du point d'ordonnee f.ymin sur (p1,p2);
          p1.y = f.ymin; }
          sinon {
          p1.x = abscisse du point d'ordonnee f.ymax sur (p1,p2);
          p1.y = f.ymax; }
    c1 = code(p1,f); }
  si (c1 égal 0000) et (c2 égal 0000)
    tracer entre p1 et p2;
}

Remarque

Cet algorithme de clipping peut assez facilement être adapté au clipping de segments de droite à l'intérieur d'un polygone convexe quelconque.
Il peut aussi être facilement adapté pour fonctionner en 3D et permettre le clipping de segments de droite à l’intérieur d’un parallélépipède rectangle.

3. Remplissage 2D de type "FillPoly"

Définitions

Ligne brisée 2D : Ligne polygonale 2D définie par une suite non circulaire de points reliés par des segments de droite.

Polygone 2D : Surface 2D bordée par une suite circulaire de points reliés par des segments de droite.

Polygone 2D convexe : Polygone 2D tel que, quels que soient 2 points P_i et P_f qu'il contient, il est possible de rélier P_i et P_f par un segment de droite sans sortir du polygone.

3.1. Remplissage d’un polygone 2D convexe

L'opération de remplissage dont on parle ici désigne l'opération consistant à déterminer et afficher tous les pixels situés à l'intérieur du polygone traité. On connait la liste ordonnée des positions de ses sommets.

Pour les polygones convexe, le remplissage peut être réalisé trame horizontale de pixels après trame horizontale de pixels en commençant du sommet inférieur et en remontant les trames jusqu'au sommet supérieur tout en gérant le parcours des suites de faces gauche et droite pour déterminer les abscisses xi et xf des deux pixels gauche et droit extrêmes sur chaque trame.

Polygone convexe à remplir

La suite gauche de sommets est B, A, F, E. La suite droite de sommets est B, C, D, E.

3.2. Remplissage d’un polygone 2D éventuellement concave

Polygone concave à remplir

Principe

Tout comme pour le remplissage d'un polygone convexe, le remplissage d'un polygone concave est réalisé en traçant les trames horizontales de pixels internes au polygone les unes à la suite des autres en partant de la trame la plus basse (correspondant au sommet le plus bas) pour finir avec la trame la plus haute (sommet le plus haut).
Chaque trame intercepte un nombre paire n de cotés du polygone.
Après tri en x des n intersections Pi (1 <= i <= n), les lignes horizontales de pixels sont tracées entre chaque couple de coordonnées (P_2*i-1,P_2*i) avec 1 <= i <= .

Remplissage des trames de bas en haut

Difficulté : L'algorithme nécessite un tri, ce qui nuit à sa scalabilité.

Mise en œuvre

Une liste chaînée (nommée LCA ci-dessous) permet de gérer la suite des cotés actifs en cours de remontée des trames. Cette liste indique quels sont les cotés ayant une intersection avec la trame en cours de traitement. Elle est mise à jour à chaque avancée d’une trame au cours de l’exécution de l’algorithme. Elle est triée en permanence par ordre croissant des abscisses x des pixels intersections. Chaque enregistrement de cette liste contient deux informations supplémentaires permettant d'en faciliter la gestion :
  - la valeur ymax du segment permettant de savoir quand le segment doit sortir de LCA,
  - la valeur 1.0/a du segment, c'est à dire l'incrément en x pour un incrément unitaire en y.

Exemples : Ci-dessous les valeurs de LCA pour les trames 7 et 13 avec pour chaque coté actif, de haut en bas, la valeur ymax, la valeur x et la valeur 1.0/a.

 
LCA pour la trame 7

LCA pour la trame 13

Pour faciliter la gestion de la liste des cotés actifs, un prétraitement est réalisé sur les cotés visant à les précalculer et à les placer dans une structure intermédiaire (nommée SI ci-dessous). Celle-ci est un tableau de listes chaînées où pour chaque coordonnée y est stocké l’ensemble des cotés c du polygone tels que y est l'ordonnée minimale ymin des deux extrémités de c. Ainsi, en parcourant SI au cours de la remontée des trames, on pourra savoir quels cotés devront entrer dans LCA pour telle ou telle ordonnée. Pour chaque coté, les valeurs ymax, 1.0/a sont stockées dans les zones idoines. La zone x est affectée avec la valeur x correspondant à ymin (y dans la structure intermédiaire). Les listes de SI sont triées par ordre croissant de x, puis pour deux x identiques, par ordre croissant de la valeur 1/a. Ce tri a pour but de faciliter le déplacement des cotés vers LCA car cet ordre de classement devra être respecté dans LCA.
Au cours du remplissage effectif, le jeu consistera, à chaque trame d'ordonnée y, à, s'il y en a, aller chercher dans SI[y] les cotés qui doivent être activés pour les déplacer dans LCA, à retirer de LCA tous les cotés qui doivent en sortir parce que y est devenu supérieur à leur ymax et à afficher tous les morceaux de trame existant dans LCA.

Polygone concave à remplir

Structure intermédiaire de prétraitement et stockage
des cotés avec x initial, ymax et 1/a pour chacun d'eux

Algorithme (pseudo langage)

4. Remplissage d'une zone de pixels définie par une couleur (algorithmes de remplissage de type "FloodFill")

Définition

On entend par zone de pixels définie par une couleur :
  (1) soit un ensemble connexe maximum de pixels de même couleur,
  (2) soit un ensemble connexe maximum de pixels délimité par une couleur.

Ensembles de pixels connexes : taches colorées
Cas (1) : Les taches rose, jaune ou verte
Cas (2) : L'ensemble des pixels roses et jaunes vis à vis de la couleur limite verte

Dans le cas (1) le remplissage est réalisé à partir d'un pixel germe de coordonnées (x,y) dont la couleur détermine la couleur de la tache à remplir.
Dans le cas (2) le remplissage est réalisé à partir d'un pixel germe de coordonnées (x,y) et en donnant la couleur limite.

4.1. Un premier algorithme

Principe

Un algorithme récursif est implanté permettant de réaliser l'exploration/remplissage de la zone à colorier. Au cours du remplissage, à chaque fois qu'un pixel devant être rempli est parcouru, on le remplit, puis on lance récursivement l'algorithme sur les pixels qui lui sont connexes.

Algorithme pour le remplissage d'une zone bordée (langage C)

L'implantation est naturellement réalisée sous la forme d'une fonction récursive. gx et gy sont les coordonnées du pixel germe. c est la couleur de tracé. lim est la couleur limite. L'implantation est réalisée en 4-connexité.

/* Remplit la zone de pixels connexes definie      */
/* a partir du pixel germe de coordonnees (gx,gy), */
/* avec la couleur c,                              */
/* jusqu'a la couleur lim                          */

void remplissage(int gx,int gy,Couleur c,Couleur lim) {
  Couleur cp = getCouleur(gx,gy) ;
  if ( ( cp != lim ) && ( cp != c ) ) {
    putCouleur(gx,gy,c) ;
    remplissage(gx,gy+1,c,lim) ;
    remplissage(gx,gy-1,c,lim) ;
    remplissage(gx+1,gy,c,lim) ;
    remplissage(gx-1,gy,c,lim) ; }
  }

Problème : L'utilisation de la récursivité entraîne très fréquement des problèmes de dépassement de capacité de la pile du programme si les zones remplies sont trop grandes (ce qui conduit à une profondeur de récursivité trop grande). Dans le pire des cas, la profondeur de la récursivité est égale au nombre de pixels de la tache à remplir.

4.2. Un deuxième algorithme

Principe

Le remplissage est effectué itérativement trame horizontale maximale de pixels après trame horizontale maximale de pixels à partir d'un pixel germe initial.

Plus précisément, une pile PG de pixels germes est gérée dans laquelle est initialement placé le pixel germe de départ. Ensuite tant qu'il existe encore au moins un pixel germe dans la pile :
  - Le pixel germe P en haut de PG est extrait.
  - Tous les pixels Pi jusqu'à la couleur limite à droite et à gauche de P sont remplit avec la couleur de tracé.
  - Parmi les pixels juste au dessus et juste en dessous des Pi, on cherche ceux qui sont le plus à droite d'une trame horizontale de pixels maximale à remplir et on empile ces pixels dans PG.

Exemple

Germe initial empilé en position 1 dans la pile	Dépilement du germe 1 et remplissage de sa trame Analyse du voisinage et empilement des nouveaux germes 1, 2 et 3	Dépilement du germe 3 et remplissage de sa trame Analyse du voisinage et empilement des nouveaux germes 3 et 4
Dépilement du germe 4 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 4	Dépilement du germe 4 et remplissage de sa trame Analyse du voisinage sans trouver de nouveau germe à empiler	Dépilement du germe 3 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 3
Dépilement du germe 3 et remplissage de sa trame Analyse du voisinage sans trouver de nouveau germe à empiler	Dépilement du germe 2 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 2	Dépilement du germe 2 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 2
Dépilement du germe 2 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 2	Dépilement du germe 2 et remplissage de sa trame Analyse du voisinage et empilement des nouveaux germes 2 et 3	Dépilement du germe 3 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 3
Dépilement du germe 3 et remplissage de sa trame Analyse du voisinage et empilement d'un nouveau germe 3 à la même place que le germe 1	Dépilement du germe 3 et remplissage de sa trame Analyse du voisinage sans trouver de nouveau germe à empiler	Dépilement du germe 2 et remplissage de sa trame Analyse du voisinage sans trouver de nouveau germe à empiler
Dépilement du germe 1 qui a déjà été rempli et qui ne donne donc pas lieu à un nouvel empilement -> plus de germe -> remplissage terminé Résultat final

Algorithme sans récursivité pour le remplissage d'une zone bordée

L'implantation sans récursivité nécessite la définition d'une pile de positions de germes. L'algorithme prend la forme d'une boucle exécutée tant que la pile n'est pas vide. Les paramètres de l'algorithme sont les coordonnées gx et gy du germe, la couleur limite lim et la couelur de tracé c.

/* Remplit la zone de pixels connexes definie      */
/* a partir du pixel germe de coordonnees (gx,gy), */
/* avec la couleur c,                              */
/* jusqu'a la couleur lim                          */

void remplissage(int gx,int gy,Couleur c,Couleur lim) {
  int x,y,xi,xf ;
  Couleur cp ;
  p.x = calloc(1000,sizeof(int)) ;
  p.y = calloc(1000,sizeof(int)) ;
  p.x[0] = gx ;
  p.y[0] = gy ;
  p.sp = 1 ;
  while ( p.sp != 0 ) {
    xi = xf = x = p.x[p.sp-1] ;
    y = p.y[p.sp-1] ;
    x++ ;
    cp = getCouleur(x,y) ;
    while ( cp != lim ) {
      xf = x ;
      x++ ;
      cp = getCouleur(x,y) ; }
    x = p.x[p.sp-1]-1 ;
    cp = getCouleur(x,y) ;
    while ( cp != lim ) {
      xi = x ;
      x-- ;
      cp = getCouleur(x,y) ; }
    line(xi,y,xf,y,c) ;
    p.sp-- ;
    x = xf ;
    while ( x >= xi ) {
      cp = getCouleur(x,y+1) ;
      while ( ( ( cp == lim ) || ( cp == c ) ) && ( x >= xi ) ){
        x-- ;
        cp = getCouleur(x,y+1) ; }
      if ( ( x >= xi ) && ( cp != lim ) && ( cp != c ) ) {
        p.x[p.sp] = x ;
        p.y[p.sp] = y+1 ;
        p.sp++ ; }
      cp = getCouleur(x,y+1) ;
      while ( ( cp != lim ) && ( x >= xi ) ) {
        x-- ;
        cp = getCouleur(x,y+1) ; } }
    x = xf ;
    while ( x >= xi  ) {
      cp = getCouleur(x,y-1) ;
      while ( ( ( cp == lim ) || ( cp == c ) ) && ( x >= xi ) ){
        x-- ;
        cp = getCouleur(x,y-1) ; }
      if ( ( x >= xi ) && ( cp != lim ) && ( cp != c ) ) {
        p.x[p.sp] = x ;
        p.y[p.sp] = y-1 ;
        p.sp++ ; }
      cp = getCouleur(x,y-1) ;
      while ( ( cp != lim ) && ( x >= xi ) ) {
        x-- ;
        cp = getCouleur(x,y-1) ; } } }
  free(p.x) ;
  free(p.y) ;
}