Une bibliothèque graphique de base est un outil permettant d'accéder aux fonctions (point, droite, cercle...) de manière aisée. Elle n'a aucune connaissance des objets que l'on dessine (impossible d'éliminer les faces cachées par exemple).
Il existe deux grands types de matériels de visualisation : en mode matriciel (point) ou en mode vectoriel (ligne).
Un écran en mode vectoriel est (ou du moins était) composé d'une face fluorescente sur laquelle pointe un rayon que l'on dirige dans le tube par l'intermédiaire des 2 bobinages (comme un oscilloscope). On ne trace que ce dont on a besoin. Les tracés sont très précis mais aucune mémoire ne mémorise le dessin effectué. Le dessin reste sur l'écran jusqu'à effacement complet (modification et animation impossibles). Une amélioration a été apportée à ces écrans vectoriel : on peut effacer un trait en demandant de le dessiner en noir. Ces écrans donnent une définition (précision de tracé) excellente. Une droite inclinée y est cependant en général représentée par un escalier car la commande du rayon se fait numériquement (mais précisément).
Sur un écran en mode point (à balayage), le rayon balaye automatiquement l'écran ligne par ligne (on appelle mode entrelacé si pour éviter le scintillement on affiche les lignes paires puis les impaires). On ne commande plus alors que l'allumage ou non du rayon. Des circuits intégrés sont disponibles pour gérer ces écrans, il suffit de leur remplir une mémoire de 0 et de 1.
En mode non entrelacé avec des mémoires 8 bits, on allume le point à la ligne L, colonne C en mettant à 1 le Xième bit de la Yième mémoire par le calcul : Position = (L*nb_col)+C; Y = partie entière de Position/8 ; X = reste de cette même division (en commençant L et C à 0). En général on donne les numéros de lignes croissants vers le bas car c'est le sens habituel du balayage.
Sur un écran à plusieurs niveaux de gris, chaque point est codé par un nombre (plusieurs bits) représentant l'intensité du rayon. Sur un écran couleur, chaque point peut être représenté par 3 nombres : les intensités des trois couleurs de base (RGB : Red Green Blue). Cette méthode permet d'afficher simultanément toutes les couleurs, mais nécessite beaucoup de mémoire : si l'on choisit 256 niveaux possibles pour les trois couleurs de base, il faut 3 octets par point, près d'1 Mo pour 640*480 points. C'est la solution choisie pour les bons écrans couleur, mais avec au moins 1280 *1024 points sur l'écran. Quand la mémoire est plus limitée, chaque point sera représenté par un numéro de couleur, chaque couleur étant définie dans une table. C'est le cas de l'écran VGA : On possède 640*480 pixels, chaque point est représenté par son numéro de couleur, entre 0 et 15 (donc sur 4 bits) : il faut donc 300 ko de mémoire. Une table de 16 triplets définit chaque couleur : l'intensité des 3 couleurs de base RGB, chacune entre 0 et 63 donc sur 6 bits. On ne peut donc avoir simultanément à l'écran que 16 couleurs, mais dans une palette de 256000 couleurs. Au temps où les définitions d'écran et le nombre de couleurs étaient suffisamment faibles, la mémoire écran était directement accessible par le processeur (en CGA, à l'adresse B800h). Désormais, on délocalise la gestion de l'écran graphique (sur une carte ou un processeur), ce qui fait qu'on ne peut plus qu'envoyer une commande au processeur graphique, sans accès direct à sa mémoire. Ce dialogue est assez coûteux en temps, et dans ce cas, donner l'ordre de tracer une ligne ira bien plus vite que de donner un à un les ordres d'allumer les points de la droite. Sur certaines stations graphiques, le processeur graphique peut être plus volumineux que l'ordinateur lui-même (mais alors il peut être capable de traiter directement les projections 3D -> 2D).
On appelle pixel (picture element, en américain mal prononcé) un point de l'écran. Sur certains matériels (PC seulement ?) la taille d'un pixel n'est pas "carrée", s'est à dire que le nombre de pixels en X, sur une longueur donnée, n'est pas le même que sur Y pour la même longueur.
Sur papier, on peut disposer d'imprimantes matricielles (ou à jet d'encre) : Il faut réserver en mémoire une matrice de bits, y mettre des 1 aux endroits à "allumer" puis quand tout le dessin est prêt envoyer cette matrice sur l'imprimante. Pour une Epson 9 aiguilles par exemple, on n'utilise que 8 aiguilles en graphique. On devra envoyer un fichier contenant les 8 premiers bits de la première colonne, de la deuxième... jusqu'à la fin de la ligne, puis on recommence pour les 8 lignes suivantes... Attention, si par hasard on obtient un code binaire sur 8 bits correspondant à une commande de gestion de la liaison avec l'imprimante, on risque quelques problèmes (résolus sous MSDOS par copy /B). Les imprimantes laser (composées d'un rayon qui "dessine" sur un tambour de photocopieuse) sont en fait matricielles. mais elles ne permettent pas l'accès direct à leur mémoire. Elles possèdent un langage de programmation, soit spécifique, soit normalisé (PostScript) mais plus onéreux. On les commande donc comme un matériel vectoriel. Les tables traçantes fonctionnent dans un mode hybride : on peut se déplacer d'un incrément soit en X, soit en Y, soit les deux en même temps, ce qui donne des tracés beaucoup plus nets pour une même définition (même distance entre deux points consécutifs). Elles possèdent elles aussi un langage de programmation de type vectoriel, mais il n'est pas standardisé (le plus connu est HPGL).
L'entrée de coordonnées 2D se fait par la souris, le clavier, le joystick, la table à digitaliser, le crayon optique, à la rigueur la caméra. Mais en 3D, à part la machine à mesurer 3 axes, on ne sait pas bien entrer une coordonnée 3D autrement que par le clavier.
Pour un écran en mode matriciel, les seules fonctions dépendant de la machine nécessaires seront :
- l'initialisation du mode graphique (car par défaut on se trouve
généralement en mode texte) ou ouverture d'une nouvelle
fenêtre
- la fermeture du mode graphique
- l'allumage d'un pixel (et le choix de couleur)
- la possibilité de tester l'état d'un pixel (allumé ou
éteint, ou sa couleur)
On en trouve un exemple sous Turbo C (versions DOS) dans bib_base.inc, ou en version DJGPP. Pour d'autres compilateurs (sur PC), une solution simple est d'utiliser l'int13 (description de Johan Calvat), ou sur ce site, mais moins bien fait. Pour Xwindows, regardez la petite démo de Paul Bourke, ou une adaptation de Graphics.h pour X
L'accès à un pixel se fait soit par accès à la mémoire écran (il suffit alors de calculer l'adresse en fonction du type de balayage, des couleurs...), soit par une commande spécifique au matériel (une interruption logicielle sur PC). Tous les autres tracés pourront être écrits en langage standard, en utilisant ces fonctions élémentaires. Mais si l'on dispose d'un processeur graphique, l'appel direct de ces tracés par l'ordre adéquat sera souvent bien plus rapide.
Dans le cas d'une imprimante matricielle, il faut en général gérer en mémoire une matrice de pixels, et envoyer le tout à l'imprimante une fois tous les tracés effectués en mémoire. L'initialisation correspondra donc à une allocation de mémoire, et mise à 0 de celle-ci, la fermeture consistera en l'envoi du dessin à l'imprimante (avec ou sans mise en forme).
Dans le cas d'une table traçante (vectorielle), on allume un point en se déplaçant plume levée vers ce point, puis en abaissant puis relevant la plume (dans ce cas, il ne faudra pas décomposer les tracés en une suite de points).
Pour une autre présentation de cet algorithme, regardez l'article d'Olivier Pécheux dans le n° 7 de PrograZine.
On peut évidement utiliser la formule Y=aX+b en travaillant sur des réels et en cherchant le point le plus proche du point théorique. C'est une très mauvaise solution car les calculs sur des réels sont très lents. De plus il faut traiter spécialement le cas des droites verticales. la meilleure solution est la suivante :
Soit à aller du point Xd,Yd au point Xf,Yf. Notons dX=|Xf-Xd| et dY=|Yf-Yd|.
Supposons dX > dY. Pour avoir une droite continue on devra donc essayer tous les X entre Xd et Xf pour déterminer leur Y et les dessiner. (dans le cas contraire faire le même raisonnement en échangeant X et Y).
Y-Yd Yf-Yd dY
équation de la droite : ------ = ------- = ---- = pente = dérivée
X-Xd Xf-Xd dX
A chaque avance de 1 en X, Y doit avancer de dY/dX (inférieur
à 1). En prenant un compteur, initialisé à 0, à
chaque avance de 1 en X, on doit y ajouter dY/dX. Une fois arrivé
à une valeur entière, on augmente Y d'un pas. Puisque l'on
cherchera maintenant la prochaine valeur entière, on peut aussi
soustraire 1 au compteur et attendre que l'on atteigne à chaque fois 1.
Or je veux utiliser que des entiers. Modifions l'algorithme en multipliant le tout par dX : Initialisons un compteur à 0, à chaque avance en X ajoutons y dY. Lorsque le compteur arrive à dX, on augmente d'un pas en Y, on soustrait dX au compteur et l'on recommence.
Rq : En initialisant le compteur à 0, on reste toujours au dessous de la droite théorique. En l'initialisant à 1 (ou plutôt dX), on reste au dessus, en l'initialisant à dX/2 on est à cheval sur la droite théorique.
dX=|Xf-Xd| dY=|Yf-Yd| avX= +1 si Xd<Xf, -1 sinon avY= +1 si Yd<Yf, -1 sinon X=Xd Y=Yd allumer(X,Y) si dX > dY alors +-- |compt=dX/2 |pour I = 1 à dX faire | +-- | |X = X + avX | |compt=compt+dY | |si compt > dX alors | | +-- | | |Y = Y + avY | | |compt=compt-dX | | +-- | |allumer(X,Y) | +-- +-- sinon +-- | (idem en échangeant X et Y) +-- exemple : base.incSur écran, certaines droites auront un aspect désagréable : ce sont les droites proches de l'horizontale, la verticale ou la diagonale, pour lesquelles on obtient un aspect "d'escalier". Sur table traçante, ce problème est beaucoup moins visible pour deux raisons. En premier lieu parce que l'on peut déplacer la plume suivant X ou Y, mais aussi suivant la diagonale : les "marches" sont alors moins angulaires. Mais de plus le pas de déplacement de la plume est généralement très inférieur au diamètre du trait obtenu, les imperfections ne se distingueront donc pas (ou beaucoup moins).
Supposons connaître une relation simple entre x et y (pour un cercle x*x + y*y = R2). Supposons le 1er point de la courbe connu (Xcentre+R,Ycentre) et le sens de la courbe (vers le haut). On représente les directions dans lesquelles on peut aller autour du point actuel par des chiffres entre 0 et 7 :
1 0 7 2 6 3 4 5Essayons le point dans la direction choisie 0 : X,Y+1.
Or X2+(Y+1)2=R2' est supérieur à R2, donc essayons la direction suivante 1 :
(X-1)2+(Y+1)2=R2'' est inférieur à R2. on a donc encadré R2. On va donc au point le plus proche de R2, et on débutera le calcul en ce point, avec la direction que l'on vient d'utiliser. On répète le procédé jusqu'au point final.
Remarques:
- Il faut évidement pour un cercle non centré en (0,0) X-Xcentre
pour X et Y-Ycentre pour Y.
- Pour l'IBM PC, 6402+2002=449600 ne rentre pas dans un
16 bits, par contre on peut traiter des cercles
jusqu'à un rayon de 46000 sur un entier 32 bits.
- On peut également utiliser la même méthode pour tracer
une droite, mais l'algorithme est moins rapide que celui présenté
plus haut.
- Sur un PC où les lignes sont plus espacées que les colonnes,
il faut tracer une ellipse
pour obtenir un cercle.
La dérivée d'un cercle est dY/dX = - X/Y. Pour un pas (supposé assez faible) dX, on aura un déplacement en Y : dY = (-X/Y)*dX. Ceci n'est bien sur applicable que pour des portions proches de l'horizontale, sinon on travaille par pas sur Y. Cette méthode est très rapide et donne d'assez bons résultats, à condition de l'utiliser sur 45deg. au maximum puis utiliser les symétries (sinon on risque ne pas retomber sur le point de départ et donc dessiner des spirales). Voir cercles.c.
Rq : dY/dX = cste correspond à la méthode donnée plus haut pour une droite
Pour un cercle, x=R cos[theta] y=R sin[theta]. En prenant des pas adéquats sur [theta] (en fonction du rayon), on trace le cercle par un ensemble de segments. Cette méthode nécessite évidement un calcul sur des réels. Elle est acceptable si on ne calcule pas les cos / sin à chaque fois (on se crée une table de sin sur 90deg., les autres valeurs en découlent rapidement).
La formulation paramétrique pour une courbe n'est intéressante que dans le cas d'un abscisse curviligne, c'est à dire quand un pas constant du paramètre conduit à une longueur constante de la courbe. Ceci donnera une précision constante sur toute la courbe.
Sur un périphérique en mode trait, on obtient le remplissage en resserrant les hachures, alors qu'en mode point on peut aussi utiliser un masque : une matrice de pixels (par exemple 16x16) où l'on donne les points à allumer et ceux à laisser éteints. Le masquage permet également des niveaux de gris sur un écran monochrome (évidement moins beau qu'un changement d'intensité de chaque pixel).
On peut utiliser deux approches totalement différentes :
On donne un point de départ dans la frontière. On trace une droite vers la droite jusqu'à trouver un point allumé, idem vers la gauche. Puis on choisit un nouveau point de départ (le meilleur est en général le milieu du segment précédemment tracé), on descend d'un pixel, et s'il est éteint on recommence. Sinon on s'arrête et on fait de même pour la partie haute. Dans le cas d'un masquage, pour chaque point trouvé, on l'allume ou non suivant le masque et sa position. Dans le cas d'un hachurage, on se déplace de manière inclinée, on "descend" perpendiculairement d'une inter-hachures.
Ceci ne fonctionne que sur des frontières convexes et quelques autres cas particuliers. Mais ne désespérons pas, il existe une solution (et même plusieurs) :
En traçant une ligne, on mémorise les deux points extrêmes G et D. En passant à la suivante, on obtient deux nouveaux points G' et D'. Si D et D' sont égaux (à un pixel près), il n'y a pas de problème. Si D'<D, alors il faut continuer jusqu'en D. Si tous les points (de D' à D) sont allumés, pas de problème. Sinon on mémorise le point où l'on était, on relance le même algorithme à partir de ce point (dans le même sens). Quand on aura traité entièrement le nouveau cas, on reviendra finir le point mémorisé. Par contre si D'>D, on continue sur la ligne précédente de D à D'. Si tous les points sont allumés, c'est bon. Sinon on mémorise et on traite à partir du premier point éteint (dans l'autre sens).
Mémoriser l'état actuel et répéter l'algorithme est facile à mettre en oeuvre grâce à la récursivité, mais on peut se passer de la récursivité en créant un tableau (géré sous forme de pile) des nouveaux points de départ à traiter.
exemples : (j'allais en descendant)
|
D'<D
mais en allant de D' tous les points sont allumés, on continue donc
normalement avec G=G' et D=D'
|
 |
D'<D
mais en allant de D' à D les points ne sont allumés que jusqu'en
D"<D. On remplit (récursivement) à partir de D" (vers le bas
suffit), puis on continuera normalement ligne suivante avec G=G' et D=D'
|
 |
D'>D,
mais en allant de D à D' sur la ligne précédente, tous les
points sont allumés, on continue donc normalement avec G=G' et D=D'
|
 |
D'>D,
mais en allant de D à D' sur la ligne précédente le point
D'' est éteint. On remplit récursivement à partir de D''
en remontant, puis on continue normalement avec G=G' et D=D'
|
Problèmes de cette méthode :
- impossible de recouvrir du dessin existant (algorithme du peintre)
- si le contour est mal fermé (un pixel éteint à une
intersection, dû aux arrondis), on remplit tout l'écran.
- obligation de tracer les frontières.
On donne au sous-programme le contour à remplir. Il pourra alors dessiner même sur d'autres dessins, on n'est pas obligé de tracer le contour. En général le contour est défini par un polygone (ensemble de points reliés par des droites), quitte à décomposer par exemple un arc de cercle en une succession de droites.
Si le polygone est CONVEXE, on commence au point le plus haut, en traitant toujours D et G (D=G au début sauf si plus d'un point à la même hauteur). Dans le polygone on pointe les deux directions à suivre. Puis on descend d'un pixel : Y. Du coté gauche du polygone, si Y < Ypoint_suivant on calcule XG en fonction du segment actuel, sinon on passe au prochain segment pour calculer XG. On calcule de même XD, et on trace la droite de G à D. On progresse ainsi jusqu'à ce que l'on arrive au Y maximal (point le plus bas).
Pour les polygones NON CONVEXES, on peut trouver de nombreux algorithmes dans la littérature (leur nombre prouve leur complexité). En voici un :
On trace une droite fictive (infinie) parallèle à la direction de hachurage, et on détermine les points d'intersections avec tous les segments (finis) du polygone. On classe ces points dans l'ordre de leur position sur cette droite, puis on trace les segments reliant le premier au second point, le 3ème au 4ème,... On recommence à inter-hachures régulières. Les cas particuliers (points doubles, segments horizontaux,...) compliquent la méthode, on s'en sort en cherchant les intersections avec les segments du contour en incluant l'extrémité haute du segment et en excluant l'extrémité basse.
On peut également essayer de DECOMPOSER LE POLYGONE EN TRIANGLES (il existe plusieurs algorithmes, assez complexes), ou la METHODE A JETONS.
Rq : pour les hachures inclinées, suivant l'algorithme choisi il peut être plus intéressant soit de le généraliser soit de faire 2 rotations : sur le polygone pour traiter des hachures horizontales (angle [theta]) puis sur les hachures avant de les tracer (-[theta]).
Il faut obligatoirement permettre à l'utilisateur de travailler à sa propre échelle. Une simple règle de 3 (2 car en X et en Y) le permet. De plus, en changeant uniquement le sous-programme de calcul d'échelle, on pourra exécuter le même programme sur des écrans différents (ou plus couramment sur un écran et une table traçante). En fait un bon programme utilisant du graphique n'utilise jamais une échelle dépendante du matériel (définition de l'écran) puisqu'il ne pourra jamais s'adapter à un changement d'écran, alors que le même programme doit souvent servir sur plusieurs ordinateurs n'ayant pas tous le même écran.
Rq : Tant qu'à calculer une échelle, autant proposer Y croissant vers le haut.
L'utilisateur travaille dans l'espace (infini), dans ses unités (n'importe quoi, des mm, daN, mètres de saucisson, semaines...), on les appelle unités utilisateur ou unités objet. Il ne veut en dessiner qu'une partie : il définit donc la fenêtre objet ou fenêtre utilisateur. En général il la définit par 4 valeurs : mini - maxi désirés en X et en Y (en unités utilisateur).
Mais on ne veut pas nécessairement mettre notre dessin sur la totalité de la feuille (ou écran). On définit donc une fenêtre papier ou fenêtre écran (on utilise le terme fenêtre papier même sur un écran). Ce sont les seules données qui ne seront pas fournies en unités utilisateur. La plupart du temps on les donne en unités écran (nombres de pixels), mais ceci rend le programme dépendant du périphérique utilisé, je préfère personnellement donner les limites de la fenêtre papier en pourcentage de la totalité de la feuille.
Si la fenêtre papier et la fenêtre utilisateur ne sont pas homothétiques, on obtiendra des distorsions (un cercle de l'espace utilisateur sera projeté dans la fenêtre papier sous forme d'une ellipse). Il est utile de proposer une échelle égale en X et Y (un carré reste un carré) et des échelles différentes (tracé de courbe par exemple).
Que faire si l'utilisateur demande de tracer une droite qui sort de la fenêtre ? Ceci arrive souvent : par exemple pour faire un zoom, plutôt que de multiplier toutes les coordonnées, on demande simplement un dessin en diminuant la fenêtre objet.
Pour le tracé d'un point, il faut effectuer 4 tests (comparer à Xmin, Xmax, Ymin, Ymax).
Pour les segments :
- Solution rapide mais peu satisfaisante : ne pas dessiner les droites dont une
des extrémités sort de la fenêtre.
- Solution très lente : le calcul de la droite se fait
complètement, on vérifie pour chaque point s'il se trouve dans
la fenêtre avant de le tracer.
- Bonne solution :
On divise l'espace en zones (0000 est la fenêtre visible) :
1001
|
1000
|
1010
|
| 0001
|
0000
|
0010
|
| 0101
|
0100
|
0110
|
On calcule le code HBDG pour les deux extrémités du segment. Si ces 2 codes sont 0000 on dessine le segment (les deux extrémités sont dans la fenêtre donc totalement visible). Sinon on calcule le code du segment qui est le ET entre les codes de ses extrémités. Si le code résultant est différent de 0, alors le segment est totalement invisible (soit totalement trop haut, trop bas, trop à droite ou à gauche) (c'est le cas le plus courant si les segments ne sont pas trop grands). Sinon on doit recalculer la (les) nouvelle valeur de l'extrémité dont le code n'était pas nul (intersection avec les bords de la fenêtre). Dans le cas d'un code de segment à 1 bit non nul, on sait directement sur quel bord est l'intersection, dans le cas à 2 bits non nuls, on doit tester une horizontale et une verticale.
Remarques :
- l'intersection d'une droite connue par 2 points et une verticale (x connu) ou
une horizontale (y connu) est très simple (donc rapide).
- il est souvent pratique de posséder un sous programme de tracé
de segment sans test de clipping (plus rapide) à utiliser quand on est
sur de ne pas dépasser la fenêtre (et surtout l'écran,
sinon on écrit n'importe où en mémoire). exemple :
tracé du cadre.
- il est en général plus rapide de faire les tests en
coordonnées écran (entiers), donc de tester le clipping sur la
fenêtre écran et non la fenêtre utilisateur. Mais dans le
cas de fenêtres non homothétiques, il faut décider si on
limite sur la fenêtre papier ou sur la projection de la fenêtre
objet.
- Cette méthode est unanimement reconnue comme la meilleure. En effet,
elle traite de la manière la plus rapide possible tous les segment
totalement visibles et presque tous ceux totalement invisibles. Seuls prennent
plus de temps ceux qui risque d'être partiellement visibles, pour
ceux-là on accepte ce temps supplémentaire puisqu'il nous permet
de déterminer la partie visible du segment.
Pour les autres courbes, le test de clipping est souvent assez complexe et donne des résultats lents, on préfère donc en général l'approximer par un ensemble de segments, en définitive on obtient un résultat plus rapide
Les programmes graphiques ont souvent besoin de calculer de grands nombres d'intersections. Par exemple pour déterminer les faces cachées d'un dessin contenant 1000 segments (ce qui est peu, surtout si l'on approxime des courbes par de petits segments), il faudra calculer 10002 intersections de segments. De nombreuses études ont été menées sur ce sujet.
Comme précisé dans le tracé de segments, l'équation d'une droite est (Yf-Y)(Xf-Xd) = (Yf-Yd)(Xf-X), que l'on peut mettre sous la forme A.X + B.Y + C =0 (a, b, c du même type que les coordonnées, entier ou réel). Trouver l'intersection revient à résoudre deux équations à deux inconnues:
|
A
.X + B .Y + C = 0
|
|
|
A'.X
+ B'.Y + C' = 0
|
- demi-plans :
équation d'un demi plan : A.X+B.Y+C < 0 (>0 pour l'autre demi-plan).
Il y a intersection si les deux extrémités de chaque segment sont de part et d'autre de l'autre droite, donc si :
(A.Xd' + B.Yd' + C ).(A.Xf' + B.Yf' + C ) <= 0 (de signe différent)
et (A'.Xd + B'.Yd + C').(A'.Xf + B'.Yf + C') <= 0
- méthode vectorielle : c'est le même principe :
les points A et B seront de part et d'autre de la droite CD : si
est de même signe que
.
Il faudra également vérifier que
.
Cette méthode permet de vérifier rapidement s'il y a intersection, mais ne donne pas le point d'intersection, à rechercher par la suite.
- méthode paramétrique :
X = Xd + (Xf-Xd).t1 (1) X,Y appartient au SEGMENT df si 0<=t1<=1
Y = Yd + (Yf-Yd).t1 (2)
X = Xd'+ (Xf'-Xd').t2 (3)
Y = Yd'+ (Yf'-Yd').t2 (4)
(1)=(3) (Xf-Xd)t1 + (Xd'-Xf')t2 + Xd-Xd' = 0 (Cramer)
(2)=(4) (Yf-Yd)t1 + (Yd'-Yf')t2 + Yd-Yd' = 0
On résout pour trouver t1 et t2. On n'a intersection que si t1 et t2 entre 0 et 1.
Rq : dans le cas où l'on pense trouver beaucoup d'intersections, on choisit une méthode donnant rapidement le point d'intersection une fois que l'on a prouvé qu'il y a intersection (paramétrique par exemple). Par contre si l'on pense trouver peu d'intersection, on utilisera une méthode prouvant rapidement s'il y a intersection, quitte à refaire tout un calcul dans les rares cas d'intersection (vectorielle ou demi-plan puis résolution simple, sachant que le déterminant sera non nul).
- intersections entre N droites : on peut étudier toutes les intersections, il y a N(N-1)/2 possibilités (ordre N2). Mais il existe d'autres algorithmes un peu plus puissants (ordre Nlog(N)), qui nécessitent de commencer d'abord par trier les points (en X croissant). Attention, le tri simple (chercher le plus petit, l'éliminer puis recommencer) prend N(N-1)/2 boucles et on n'a pas encore trouvé les intersections. Il faut utiliser des méthodes puissantes de tris. Ce type d'algorithme est surtout efficace dans certains cas particuliers (par exemple si les segments sont soit verticaux, soit horizontaux, par exemple pour gérer des fenêtres rectangulaires qui se chevauchent).
supposons l'équation de droite Y=a.X+b (sauf verticale). L'intersection de cette droite et d'un cercle vérifiera donc (X-xc)2 + (a.X+b-yc)2 =r2. En développant, on obtient :
(1+a2)X2 -2(xc+a.yc-ab).X + xc2+(b-yc)2-r2 = 0
On calcule le discriminant (0 racine double donc droite tangente au cercle, >0 si 2 points d'intersection, <0 si pas d'intersection) et l'on résout.
Dans le cas de deux cercles, on développe les 2 équations des cercles. En les soustrayant, on obtient l'équation de la droite passant par les 2 points d'intersection, on se ramène donc au cas précédent.
Rq : Ceci ne traite que les droites infinies et les cercles complets. Il est normal que l'on ait trouvé une équation du second degré, puisqu'on a au plus deux intersections. Deux ellipses donneront donc une équation du quatrième degré !
On souhaite souvent définir des objets dépendant d'autres objets, en particulier en DAO :
- droite parallèle à une autre et passant par un point ou
tangente à un cercle
- droite formant un angle avec une autre (90deg. par ex)
- droite tangente à un cercle et passant par un point
- droite tangente à 2 cercles (4 possibilités en
général)
- arc de raccordement entre 2 segments
- cercle passant par 3 points ou inscrit dans un triangle
- cercle donné par le centre et passant par un (2 pour un arc) point
- cercle dont on donne le rayon ou le diamètre
- distances imposées (à une droite par ex)
Il est souvent nécessaire de proposer à l'utilisateur final toutes ces possibilités. Mais si le modèle (c'est à dire la représentation en mémoire des objets) ne permet qu'une seule définition par type d'objet (segment par 2 points par exemple), on traduit directement la contrainte (deux points de tangence). Mais une modification des "objets supports" (un cercle de tangence) ne modifiera pas l'objet (droite tangente). Il vaut mieux que le modèle mémorise ces contraintes, mais il en devient beaucoup plus complexe. Quelle que soit l'option choisie, les sous-programmes traitant les contraintes peuvent se trouver dans la bibliothèque de base, on s'en servira soit à l'introduction des données, soit uniquement en phase finale de dessin.
Une bonne bibliothèque de base contiendra différentes "couches". La couche 0 contient le minimum à connaître pour pouvoir faire des dessins (initialisation, allumer et tester un point, dans la couleur voulue). Changer d'ordinateur, de carte graphique ou d'imprimante nécessite la mise à jour de la couche 0 uniquement. La couche 1 contient les tracés de base (segment, cercles...) ne dépendant que de la couche 0. Si ces fonctions sont disponibles sur notre matériel (et plus rapides), on pourra évidement les remplacer, mais on gardera les versions standard en commentaire en cas de changement de matériel. On prévoira également, si possible, un tracé de segment horizontal et vertical plus rapides que le cas général, qui serviront dans les couches suivantes pour accélérer les algorithmes. Une couche 2 contiendra les remplissages dans le cas général : par test de l'écran et par définition du polygone frontière. Si le matériel dispose de ces fonctions (en 95 limité aux stations), on les utilisera. Mais sinon, on prévoira aussi les remplissages de convexes (du moins si l'implantation donne des résultats plus rapides dans ce cas), par exemple pour des dessins de surfaces décomposées en facettes toutes triangulaires ou quadrangulaires). On prévoira également dans la couche 0 un remplissage rapide de rectangle (côtés parallèles aux axes), utilisé entre autre pour l'effacement d'une fenêtre. Ce dernier cas seul est disponible sur cartes VGA, les autres cas devront donc être écrits en fonction des couches précédentes. Les fonctions des couches 0 à 2 ne devront pas être proposées aux utilisateurs (dépendent de la définition de l'écran), mais une couche 3 contiendra les fonctions de définition des fenêtres objet et papier, et tous ces tracés mais en coordonnées utilisateur. Cette couche contiendra également les tests de dépassement de fenêtres (clipping). On pourra ensuite rajouter des bibliothèques de fonctions utilitaires (contraintes, calculs vectoriels, transformations matricielles,...) qui ne sont pas directement liées aux couches précédentes.
Puisque les programmes sont aujourd'hui interactifs, on pourra également prévoir une bibliothèque d'entrée de données (clavier, souris, menus déroulants...)
Enfin, on prévoira des bibliothèques de fonctions spécifiques à un type d'utilisation, utilisant la bibliothèque de base mais sans liens entre elles : bibliothèque 3D, tracés de courbes,....
