Brevet FR2646257A1 — publié le 19901026

PROCEDE D'AFFICHAGE D'ARCS DE COURBES PARAMETRIQUES POLYNOMIALES, SUR UN SUPPORT DE VISUALISATION D'UN MOYEN D'AFFICHAGE RELIE A UN ORDINATEUR DESCRIPTION La présente invention concerne un procédé d'affichage d'arcs de courbes paramétriques polynomiales, sur un support de visuaLisation d'un moyen d'affichage relié à un ordinateur. Elle s'applique à la conception assistée par ordinateur (CAO) et plus particuLièrement au dessin assisté par ordinateur (DAO). Elle peut apporter une aide très précieuse à la conception, notamment pour les graphistes, les mécaniciens, Les architectes, etc On sait que pour afficher un arc d'une courbe paramétrique polynomiale de Bézier, on n'affiche pas directement cet arc mais une portion d'une polyligne interpolant la courbe, Les extrémités de cette portion de polyligne correspondant aux extrémités de L'arc à afficher. La polyligne est formée par des segments de droite successifs ayant chacun deux extrémités situés sur la courbe.Lorsque La portion de polyL;gne correspondant à L'arc à afficher est obtenue, il est alors nécessaire, pour afficher cet arc sur un support de visualisation, de rechercher dans une grille de "pixels" ou "éLéments d'image" du support de visualisation, queLs sont Les pixels à afficher pour représenter au mieux L'arc de courbe à afficher, ou plus précisément, la portion de polyligne correspondant à cet arc. Deux problèmes doivent donc étre résolus pour L'affichage d'un arc d'une courbe polynomiale paramétrique : L'élaboration de La portion de polyligne interpolant la courbe et correspondant à L'arc à afficher, et la sélection des pixels du support de visuaLisation, permettant de représenter au mieux cette portion de polyligne. En ce qui concerne La sélection des pixels du support de visualisation, permettant d'afficher au mieux une portion de polyligne interpolant un arc d'une courbe à afficher, différentes méthodes sont connues et notamment : - Une première méthode, aboutissant à un affichage de mauvaise quaLité, notamment à faible résolution, consiste à arrondir Les valeurs des coordonnées des extrémités de segments de la portion de polyligne à afficher, aux valeurs des coordonnées des pixels respectivement Les plus proches de ces extrémités. Les pixels à afficher sont recherchés en effectuant une partition du plan de La grille du support de visualisation, seLon une méthode dite de "Bresenham" décrite dans l'articLe de J.E. Bresenham "An Incremental Algorithm for Digital PLotting" - IBM Systems Journal, 4(1), pages 25-30, 1965 (1). - Une deuxième méthode, déduite de la précédente, consiste à augmenter le nombre de segments de la portion de polyligne interpolant l'arc à afficher, jusqu'à obtenir des extrémités de segments cojncidant avec des pixeLs. Cette méthode nécessite des temps de calcul importants et il est de plus nécessaire de procéder à un filtrage des pixels présélectionnés afin d'éviter, dans L'affichage, des distorsions en "marches d'escalier. En ce qui concerne L'élaboration d'une polyligne interpolant une courbe, pour La portion de polyligne correspondant à un arc à afficher, La méthode la plus connue est la méthode dite de "de Casteljau" décrite notamment dans l'article "formes à pôles" par Paul de Faget de Casteljau (3) - voL.2, "Mathématiques et CAO - Hermès 1985. Cette méthode consiste à considérer que toute courbe paramétrique polynomiale de degré b peut être exprimée sous forme de courbe de Bezier, de type potynomial. Les courbes de Bézier sont décrites notamment dans L'ouvrage "Courbes et surfaces" par P. Bézier-mathématiques et CAO - volume 4 - Hermès 1986 (4). On sait par les documents (3, 4) précités qu'une courbe paramétrique polynomiale de degré b, décrite mathématiquement par la fonction vectorielle U(t) = (x(t), y(t)), avec O Dans cette relation Ui désigne les points de Bézier, et les Bi,d (t) sont les polynômes de Bernstein qui sont notament décrits dans le document (4) cidessus, ainsi que dans les documents suivants - "Numerical control : Mathematics and appLications" Wiley and Sons Ltd. 1972 par P. Bélier (5). - . Lane et R. Riesenfeld. "A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces". IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.2(1) : 35-46, 1980 (6). - L. Ramshaw. BLossoming : A Connect-the-Dots Approach to Splines. Research Report # 19, Digital Equipment Systems Research Center, Palo Alto, 1987 (7). Les points successifs U0, U1, ..., Ud sont qualifiés de points de contrôle, tandis que le polygone défini par les points U0, U1 , ..., Ud, U0, pris dans cet ordre, est qualifié de polygone de contrôle Chaque point de contrôle U peut être Localisé par des coordonnées réelles (xi,yi), dans un repère de référence. Ces coordonnées réelles sont enregistrées dans la mémoire de L'ordinateur. La méthode de "de Casteljau" mentionnée plus haut et décrite dans les documents C3) et (4) précités, permet plus précisément d'obtenir la polyligne d'interpoLation d'une courbe de sérier. Une polyligne est formée de N segments successifs, permettant de représenter cette courbe au plus près. La méthode de "de CasteLjau" est une méthode qui permet d'interpoLer une courbe de Bézier par une polyligne obtenue grâce à une subdivision de type récursif : selon cette méthode La courbe est d'abord interpolée par une polyligne à deux segments (profondeur d'interpolation k=1), puis par une polyligne à quatre segments (k=2), et ainsi de suite, pour satisfaire le critère de proximité" suivant chaque segment de la polyligne n'est pas plus éloigné' de plus d'une unité de grille de référence de la portion de courbe qu'iL interpole. L'unité de grille de référence est L'unité qui est choisie dans Le repère de référence. Cette méthode, bien que donnant une bonne représentation d'une courbe de Bélier a cependant pour inconvénient d'utiliser un traitement récursif d'interpolation, de durée importante. Le nombre N de segments d'une polyligne est Lié à la profondeur k d'interpolation, par La relation k N=2 Des auteurs, et notamment G. Wang, ont montré que La profondeur d'interpolation k satisfaisant le critère de proximité précédent, est donnée par la relation : dans Laquelle b désigne le degré de la courbe et D La diagonale du polygone de contrôle de ta courbe ; cette diagonale sera décrite plus loin en détail. Le calcul de la profondeur d'interpolation k et de la valeur de la diagonale D du polygone de contrôle est décrit dans Le document : "Comparison of three Curve Intersection ALgorithms". Computer-Aided Design, vol.18(1) : 58-63, 1986 par T. Sedergerg et S. Parry (8). Ce document cite un autre document : "The Subdivision Method for Finding the Intersection between two Bézier Curves or Surfaces. Zhejiang University Journal, 1984. Special Issue on computational geometry, par G. Wang (9) qui décrit plus précisément ces deux calculs. Ces caLculs théoriques n'ont toutefois jamais été utilisés pour générer une polyligne comparable à celle obtenue par ta méthode de "de Casteljau, mais dont la construction serait plus rapide qu'avec cette méthode. IL en résulte que L'affichage d'arcs de courbes de sérier interpolés par des portions de polylignes obtenues par la méthode de "de Casteljau", présente pour un ordinateur utilisé en CAO, des temps de calculs importants. L'invention a précisément pour but de remédier aux inconvénients mentionnés plus hauts et notamment de permettre une meilleure quaLité d'affichage des arcs de courbes paramétriques de Bezier, sur un support de visualisation défini par une griLle de pixels, avec des temps de calcul moins importants que ceux des procédés connus. Ces buts sont atteints en effectuant une sélection beaucoup plus rapide et précise des pixels à afficher pour visualiser chaque arc de courbe interpolé par une polyligne, et en effectuant un traitement récurrent des coordonnées des points de contrôle de chaque courbe, pour obtenir beaucoup plus rapidement les portions de polylignes correspondant respectivement aux arcs à afficher. L'invention concerne un procédé d'affichage d'arcs de courbes paramétriques polynomiales de Bézier, sur un support de visualisation d'un moyen d'affichage relié à un ordinateur, cet ordinateur est relié à une mémoire, L'affichage sur Le support étant déterminé par une grille de pixels définie par des lignes et des colonnes parallèles, régulièrement espacées d'un pas prédéterminé, successivement balayées, chaque pixel est localise par l'intersection d'une ligne et d'une colonne et est affiché lorsque la ligne et la colonne correspondantes reçoivent des signaux de commande d'affichage au cours du balayage, les pixels de la grille sont repérés par leur coordonnées (X, Y) dans un repère de référence (o, x, y) ayant un premier axe (x) et un deuxième axe (y) respectivement parallèles aux lignes et aux colonnes, chaque courbe de degré d est décrite mathématiquement par la fonction vectorielle U(t)=(x(t), y(t)) d'un paramètre t, avec O I i référence, ces coordonnées étant enregistrées dans la mémoire de L'ordinateur, chaque courbe est interpolable par une polyligne ayant une profondeur d'interpolation k et comportant N segments successifs orientés, ayant chacun deux extrémités situées sur la courbe, L'affichage d'un arc d'une courbe est délimité par un couple de paramètre (td, t f) sur l'intervalle to, 1] de la courbe U(t), Le procédé consiste à afficher une portion de polyligne correspondant à cet arc, délimitée par un point de départ (A ) et un point d'arrivée (Af), en affichant d les pixels les plus proches de cette portion de polyligne, caractérisé en ce qu'il consiste, pour chaque arc :: - à calculer la profondeur d'interpolation k de la courbe correspondant à cet arc, à partir du degré d de la courbe et de la diagonale D du polygone de contrôle, caLculée à partir des coordonnées enregistrées des points de contrôle, pour établir une correspondance biunivoque entre l'ordre i des extrémités E des segments de la polyligne et ta partition de L'intervalle [0,1] du paramètre t, en 2 parties égales, de sorte que ti=i.2-k,où ti est le paramètre de L'extrémité E, - à établir une transformation (t t ) 3 (i, u), (j, v), qui aux paramètres du couple (td,tf) fait correspondre respectivement deux couples de valeurs (i, u), (j, v) tels que t =i.2 +u et -k d t =J.2 +v, avec u f - à calculer par récurrence les coordonnées de i+1 premières extrémités de segments de la polyligne dans le repère de référence, pour calculer les coordonnés du point de départ A , à partir des d coordonnées des extrémités Ei et Ei+1 de segments de la polyligne,de sorte que Ad=Ei+u(Ei+1-Ei), AdEi+1 est une portion de segment à afficher, les coordonnées de Ad et Ei+1 sont enregistrées en mémoire, - à calculer par récurrence les coordonnées des extrémités Ei+1 à Ej+1 de segments de la polyligne dans le repère de référence, pour calculer les coordonnées du point d'arrivée Af, à partir des coordonnées des extrémités E et E . de sorte que Af=Ej+v(Ej+1-Ej), les segments correspondant aux extrémités Ei+1 à Ej, ainsi que la portion de segment E A étant à afficher, les coordonnées des extremités Jf E à A au sont enregistrées en mémoire, i+2 f - à déterminer, des que les coordonnées d'extrémités de chaque segment ou portion de segment à afficher sont enregistrées en mémoire, une séquence de pixels à afficher, les pixels de chaque séquence sont sélectionnés au voisinage de ce segment pour être affichés lorsque les distances séparant ces pixels du segment correspondant, mesurées dans le repère de référence, respectivement Le long des Lignes ou des colonnes balayées et qui coupent ce segment, sont inférieures en valeurs absolues à La moitié de la valeur du pas de la grille de pixels. Selon une autre caractéristique de L'invention, te calcul par récurrence des coordonnées des extrémités de segments d'une polyligne interpolant une courbe, consiste à choisir un nombre N de segments de chaque polyligne, en relation avec la profondeur k k d'interpolation, tel que N=2 , cette profondeur est donnée par la relation k= pL 94 8 D , où D désigne La valeur de La diagonale du polygone de contrôle, calculée par l'ordinateur à partir des coordonnées des points de contrôle enregistrées en mémoire, puis à determiner les coordonnées (xi+1,yi+1) des extremitées des segments de chaque polyligne, entre les points de contrôle U et U Ud, par récurrence 0 calculée par L'ordinateur, en évaluant a priori des différences en avant aux coordonnées (xi,yi) de l'extremité respectivement aux coordonnées (xi, yi) de l'extrémité d'un segment pour passer aux coordonnées (xi+1,yi+1) de l'extrémité d'un segment suivant sur la polyligne, de sorte que : xi+1=xi+#xi et yi+1=yi+#yi avec #xi+1=#xi+#xi et #yi+1=#yi+#2yi avec O Selon une autre caractéristique, pour déterminer les pixels à afficher dans chaque séquence en mesurant respectivement, le long de toutes les lignes ou de toutes les colonnes balayées qui coupent le segment correspondant à cette séquence et au voisinage de ce segment, les distances qui séparent ces pixels et ce segment - on subdivise le plan du support de visuaLisation en huit octants repérés par des numéros d'ordre prédéterminés, quatre octants de ce repère sont dits à dominante (x) lorsque Les coordonnées des points situés dans ces octants ont des va Leurs absolues sur le premier axe (x) supérieures aux valeurs absolues sur le deuxième axe (y), quatre autres octants de ce repère sont dit à dominante y lorsque les coordonnées des points situés dans ces quatre autres octants ont des valeurs absolues sur te deuxième axe (y), supérieures aux valeurs absolues sur le premier axe (x), - à partir des coordonnées des extrémités des segments ou portions de segments à afficher enregistrées en mémoire, on détermine le numéro d'ordre de L'octant contenant ces extrémités, - on effectue un balayage des lignes et des colonnes coupant chaque segment à afficher et on sélectionne, pour tout segment dont les extrémités sont dans un octant à dominante x, parmi les pixels voisins de ce segment et situés aux intersections de lignes et de colonnes, voisines de ce segment, ceux pour Lesquels les distances respectives à ce segment, mesurées sur le deuxième axe (y), sont inférieures en valeurs absolues à un demi-pas (P/2) de grille, on sélectionne, pour tout segment dont les extrémités sont dans un octant à dominante y, parmi Les pixels voisins de ce segment et situés aux intersections de Lignes et de colonnes, voisines de ce segment, ceux pour Lesquels les distances respectives à ce segment, mesurées sur le premier axe (x) sont inférieures en valeurs absolues a un demi-pas de grille (P/2), les coordonnées des pixels sélectionnés dans le repère de référence de visualisation sont celles des pixels à afficher. Les caractéristiques et avantages de l'invention ressortiront mieux de La description qui va suivre, donnée en référence aux dessins annexés dans lesquels : - la figure 1 représente schématiquement un polygone de contrôle d'une courbe paramétrique C de degré d=3, Les diagonales D1 et D2 de ce polygone, ainsi qu'une polyligne PL interpolant la courbe C, la diagonale D étant La plus grande des deux longueurs de D1 et D2, - la figure 2 représente schématiquement un ensemble de traitement permettant de mettre en oeuvre le procédé de l'invention - ta figure 3 représente schématiquement une courbe de Bézier interpolée par une polyligne, cette courbe ayant un arc à afficher auquel correspond une portion de La polyligne servant à l'affichage, - la figure 4 représente schématiquement deux des segments contenant les extrémités A et Af de la d f portion de polyligne correspondant à L'arc à afficher, - La figure 5 représente schématiquement deux segments à afficher dans la grille des pixels du support de visualisation, - la figure 6 représente schématiquement la partition du plan du support de visualisation, en huit octants, - la figure 7 représente schématiquement une portion de la grille du support de visualisation et permet de mieux comprendre la sélection d'un pixel candidat à L'affichage, - la figure 8 représente schématiquement une portion de la grille du support de visualisation, au voisinage de la jonction de deux segments consécutifs de La portion de polyligne, - La figure 9 est un organigramme du programme mis en oeuvre dans le procédé de L'invention. La méthode d'interpolation de "de CasteLiau" sera mieux comprise à L'aide de la description de La figure 1. Cette figure représente schématiquement une courbe C de Bézier, de degré d=3 par exemple, dont le polygone de contrôle PC est défini par d+1=4 points de contrôles Uû, ul, UZ, U3, de coordonnées (xO,yO), I 2 3 3 référence (o, x, y) ; ces coordonnées sont enregistrées dans la mémoire d'un ordinateur. Cette courbe peut être interpolée par une polyligne, selon la méthode de "de Casteljau" qui ne sera pas décrite ici en détail. La polyligne PL comporte N=4 segments dans l'exemple représenté ; La profondeur d'interpolation k nécessaire à l'obtention k de cette polyligne, est ici égale à 2, puisque N=2 =4. On a aussi représenté sur cette figure, les deux diagonales Dl et D2 du polygone de contrôle PC. SeLon L'invention, pour calculer par récurrence, les coordonnées d'extrémités de segments d'une polyligne interpolant une courbe, pour afficher un arc de cette courbe, on calcule tout d'abord la profondeur d'interpolation k par la formule de Wang k=[Log4D(d-1)D] 8 k de manière à calculer le nombre N=2 de segments de la polyligne. Comme indiqué plus haut pour calculer k, il est nécessaire de rechercher, parmi les valeurs des longueurs des diagonales D1 et D2 (dans l'exemple représenté sur la figure 1) du polygone de contrôle, -la valeur maximale D. Cette recherche est aisée pour chaque courbe, puisque Les coordonnées de chaque point de contrôle du polygone de contrôle de chaque courbe sont connues et sont enregistrées en mémoire. La connaissance de chaque valeur de N permet alors de connaître chaque pas élémentaire (bx 6 y ) qui permet notamment de passer de chaque première extrémité de coordonnées (xO, yO) du premier segment S1 de chaque polyligne, à la deuxième extrémité de coordonnée (x1, y1, de ce segment. Cette deuxième extrémité du premier segment SI correspond d'ailleurs à la première extrémité du segment suivant SZ de la polyligne. D'une façon générale, les coordonnées (x i+1,yi 1) des extrémités des segments de chaque polyligne, sont calculées par récurrence par l'ordinateur, en évaluant a priori le pas (#xi,#yi) qu'il faut ajouter respectivement aux coordonnées (x yi) de L'extrémité d'un segment, pour passer aux coordonnées (x i+1' yi 1) de l'extrémité d'un segment suivant sur la polyligne. Ce calcul peut être qualifié de calcul de "pas en avnat" ou "diffèrences en avant". La relation de récurrence s'établit de La manière suivante xi+1 = xi+ #xi et yi+1=yi+#yi avec #xi+1 = #xi+#xi avec #yi+1 =#yi+#y̑i A l'initialisation, pour i=O, on obtient x1 = x0 + #x0 et y1 = y0 + #y0 . #x0 et #y0 sont les corrdonnées du premier point de conrôle U. Le nombre N de segments de la polyligne étant connu, on peut alors calculer par récurrence et a priori, les différences # x = #x + # x0 det #y1 = #y0 + #y̑0 et aindsi de suite jusqu'à # x i+1 et 2 2 d i + 1 #x0 et #y0, #x0 et #y̑0, ..., #dx0 et #dy, sont initiatisés à partir des corrdonnées des points de contrôle, du degré d de la courbe, et de la profondeur d'interpolation k. La figure 2 représente schématiquement un support de visualisation 1 d'un moyen 2 d'affichage d'arcs de courbes paramétriques polynomiales de Bézier. Ce moyen d'affichage est relié à un ordinateur 3, lui même relié à une mémoire 4. Le moyen d'affichage considéré ici en exemple est un terminal à écran, mais ce moyen pourrait être une imprimante par exemple. Quel que soit Le moyen d'affichage utilisé, celui-ci est tel que L'affichage d'arcs de courbes sur le support de visualisation 1, est déterminé par une grille 5 de "pixels" ou t'éléments d'image" 6, définie par des lignes 7 et des colonnes 8, parallèles et régulièrement espacées, d'un pas P prédéterminé. Ces lignes et ces colonnes sont balayées successivement ; chaque pixel tel que 6 est localisé par L'intersection d'une Ligne et d'une colonne et repéré par ses coordonnées (X, Y) dans le repère de référence. Les axes (x, y) de ce repère sont respectivement parallèles aux lignes et aux colonnes de la grille 5.Un pixel est affiché lorsque La ligne et la colonne qui lui correspondent reçoivent des signaux de commande d'affichage provenant de moyens de commande (non représentés) du moyen d'affichage 2, sous le contrôle de l'ordinateur 3. Comme indiqué plus haut, chaque courbe paramétrique polynomiale de Bézier, telle que la courbe (C) de la figure 3, de degré d, est décrite mathématiquement par la fonction vectorielle U(t)=(x(t), y(t)), dans laquelle t appartient à l'intervalle 00,13. Cette courbe est définie par d+1 points de contrôle U (avec i=O, 1=1, ..., l=d) sur cet intervalle, ayant des coordonnées réelles (x, y) dans i i le repère de référence Co, x, y). Les coordonnées des points de contrôle sont enregistrées dans la mémoire 4 de L'ordinateur 3 de la figure 2. Sur la figure 3, PL désigne la polyligne interpolant la courbe C, avec une k profondeur k d'interpolation k, et comprenant n=2 segments successifs orientés par exemple dans le sens de la flèche F. Chaque segment a deux extrémités sur la courbe. L'affichage d'un arc de courbe A de ta courbe C, délimité par te couples de paramètre (td, t ) sur l'intervalle 0,i) correspond en fait à f La portion de polyligne correspondante, délimitée par un point de départ A et un point d'arrivée Af, en d affichant sur Le support de visualisation 1, les pixels 6 les plus proches de cette portion de polyligne. Selon l'invention, on calcule tout d'abord, grâce à la formule de Wang, la profondeur d'interpolation k de la courbe C correspondant à L'arc à afficher, à partir du degré d de cette courbe et de la diagonale D du polygone de contrôle, elle-même calculée à partir des coordonnées des points de contrôle, enregistrées dans la mémoire 4 de l'ordinateur 3. Ce calcul permet d'établir une correspondance biunivoque entre l'ordre i (allant de O à 8 dans l'exemple de la figure 3) des extrémités E des segments de la polyligne, et la partition en 2k parties égales, de l'intervalle ,1) de variation du paramètre t, de sorte que ti=i.2-k, ti étant le paramètre de l'extrémité Ei.Dans l'exemple représenté sur la figure 3, pour i=2 par exemple (correspondant à l'extrémité E ), on obtient ainsi t=1/2. 2 Cette correspondance biunivoque permet notamment d'établir une transformation tf) # (i,u), (j,v), qui aux paramètres (td,tf) fait respectivement correspondre deux couples de valeurs (i, u), (J, v) tels que t =i.2 +u et -k d t =J.2 +v, avec u f Cette correspondance est essentielle pour ramener les coordonnées t et t de L'arc de courbe à d f afficher, mesurées dans le repère to, x, y) de référence, aux coordonnées respectives des points de départ A et d'arrivée A de la portion correspondante d f de polyligne, mesurées sur cette polyligne. La figure 4 permet de mieux comprendre cette transformation. On n'a représenté sur cette figure, que les deux segments E E et E E sur lesquels sont 12 67 respectivement situés les points de départ A et d d'arrivée A . On sait qu'il est toujours possible de f déterminer un vecteur u sur E E, de module u=E1Ad/E1E2, et un vecteur v ou E6E7, de module v=E6Af/E6E7. Dans l'exemple représenté sur la figure, on a par exemple u=1/3 et v=2/3. On enregistre alors en mémoire pour le point Ad, le couple de valeurs (1, 1/3) correspondant à l'ordre i=1 de la première extrémité E du segment E E , et au nombre rationnel u=1/3.De la même manière pour le point Af, on enregistre le couple de valeurs (6, 2/3) correspondant à L'ordre J=6 de la première extrémité A6 du segment E E , et au nombre rationnel v=2/3. Au couple de paramètre (t d' t ), il f est donc possible de faire correspondre respectivement les couples des valeurs (1, 1/3), (6, 2/3). La 3 polyligne représentée en exemple comporte N=8=2 segments, de sorte que k=3. Il en résulte que -k -k d=i.2 +u=1/8+1l3 et t =J.2 +v=6/8+2/3. f Cette transformation étant établie, on calcule alors par récurrence, comme décrit plus haut (en relation avec la figure 1) dans le repère de référence (O, x, y), Les coordonnées des i+1 extrémités des segments de la polyligne ; ceci permet de calculer Les coordonnées du point de départ Ad, à partir des coordonnées des extrémités Ei et Ei+1 du segment EiEi+1 sur lequel est localisé le point Ad, de sorte que Ad=Ei+u(Ei+1-Ei). Dans l'exemple représenté sur la figure 4, si (xd,yd) désignent les coordonnées de Ad, (x1, Y1) les coordonnées de E1, et (x2, y ) les coordonnées de E , on a : xd=x1+1/3(x2-x1) yd=y1+1/3(y2-x1) Les coordonnées des i+1 segments de la polyligne, ainsi que Les coordonnées du point de départ Ad, sont enregistrées en mémoire. On calcule ensuite par récurrence, comme décrit plus haut, (en relation avec la figure 1), Les coordonnées des extrémités Ei+2 à Ej+1 des segments de La polyligne, pour calculer les coordonnées du point d'arrivée Af, à partir des coordonnées des extrémités Ej et Ej+1 du segment EjEj+1 sur lequel est localisé le point d'arrivée Af, de sorte que Af=Ej+v(Ej+1-Ej). Les coordonnées des extrémités Ei+2 à Ej+1 (E3 à E7 dans l'exemple) des segments à afficher, sont enregistrées en mémoire, ainsi que les coordonnées de L'extrémité A d du segment A E à afficher. Dans l'exemple représenté sur la figure 4, si (xf, y f) désignent les coordonnées de Af, (x6, y6) les coordonnées de E6 et (x7,y7), les coordonnées de E7, on a : x = x + 2/3 Cx -x ) f 6 7 6 y 6 7 + 2/3 (y7 - y Les coordonnées de L'extrémité A de la f portion de segment E A à afficher, sont enregistrés en 6f mémoire. Selon l'invention, des que les coordonnées des extrémités d'une portion de segment (tel que A E par exemple)ou d'un segment (E2,E3,...,E5E6) sont enregistrées, on détermine une séquence de pixels à afficher pour cette portion de segment ou ce segment appartenant à La portion de polyligne à afficher. La figure 5 va permettre de mieux comprendre la recherche des séquences de pixels sélectionnés à afficher. Sur cette figure, on a représenté un segment ou portion de segment BC dans La grille 5 des pixels du support de visualisation, ainsi qu'un segment CD dans cette grille ; ces deux segments ou portions de segments appartiennent à la portion de polyligne correspondant à l'arc à afficher. Pour déterminer chaque séquence de pixels à afficher pour chaque segment ou portion de segment, on sélectionne au voisinage de ce segment, Les pixels dont les distances au segment, mesurées Le long des lignes 7 ou des colonnes 8 balayées et qui coupent ce segment, sont inférieures à La moitié du pas de la grille (P/2). Pour Le segment BC par exemple, les distances des pixels à afficher, sont mesurées le long des lignes 7, pour des raisons qui seront expliquées plus loin. C'est ainsi que le pixel Pi (intersection de la Ligne 71 et de la colonne 81) est un pixel à afficher, car sa distance dl, mesurée le long de la Ligne 71, est inférieure à P/2.- P'1 n'est pas sélectionné car sa distance d'1 au segment BC est supérieure à P/2. Les autres pixels à afficher pour la séquence relative au segment BC, sont P2, P3, P4, P5. Pour Le segment CD, les distances des pixels à afficher, sont mesurées Le long des colonnes 8, pour des raisons qui seront expliquées plus loin. C'est ainsi que le pixel P6 (intersection de la colonne 86 et de la ligne 76) est un pixel à afficher, car sa distance d6, mesurée le long de la colonne 86, est inférieure à P/2. P'6 n'est pas sélectionné car sa distance d'6 mesurée- le long de La colonne 86, est supérieure à P/2. Les autres pixels à afficher, pour La séquence relative au segment CD, sont P7, P8, ..., P12. Les figures 6 et 7 vont permettre de mieux comprendre la sélection des pixels à afficher. Pour effectuer cette sélection et comme le montre la figure 6, on subdivise le plan du support de visualisation, en huit octants repérés par des numéros d'ordre prédéterminés. Les Lignes de balayage du support de visualisation sont parallèles à un premier axe x du repère de référence, tandis que les colonnes du support sont parallèles à un deuxième axe y de ce repère. Ces octants forment respectivement des angles de 450. Ils sont numérotés 00, 01, 11, 10, 20, 21, 31, 30, comme indiqué sur la figure. Le premier chiffre pour chaque octant, est le numéro du quadrant du repère correspondant à cet octant ; le deuxième chiffre vaut O si L'octant contient des points dont les coordonnées ont des valeurs absolues sur le premier axe x, supérieures aux valeurs absolues sur le deuxième axe y. Cet octant est alors dit à "dominante" x. IL y a donc quatre octants à dominante x : 00, 10, 20, 30. Le deuxième chiffre vaut 1 si l'octant contient des points dont les coordonnées ont des valeurs absolues sur le deuxième axe y, supérieures aux valeurs absolues sur le premier axe x. Cet octant est alors dit à "dominante" y. Il y a donc quatre octants à dominante y : 01, 11 ,21, 31. Cette subdivision étant établie, le procédé de l'invention consiste ensuite, pour chaque portion de segment, ou pour chaque segment à afficher, dont les coordonnées des extrémités sont enregistrées en mémoire, à déterminer le numéro d'ordre de L'octant contenant ces extrémités. Sur La figure 5, le segment BC par exemple est situé dans L'octant 01 à dominante y, tandis que le segment CD est situé dans L'octant 00 à dominante x. On effectue ensuite un balayage des lignes ou des colonnes coupant chaque segment à afficher ; on sélectionne, pour tout segment dont Les extrémités sont dans un octant à dominante x, parmi les pixels voisins de ce segment et situés aux intersections de colonnes, avec ce segment, les pixels pour lesquels les distances respectives à ce segment, mesurées sur le deuxième axe y. sont inférieures à P/2. C'est ainsi que dans L'exemple de ta figure 5, pour le segment CD, l'octant concerné est 00 et Les distances telles que d6 ou d'6 sont mesurées sur le deuxième axe y. De la même manière, on sélectionne, pour tout segment dont les extrémités sont dans un octant à dominante y, parmi les pixels voisins de ce segment et situés aux intersections des lignes avec ce segment, les pixels pour lesquels les distances respectives à ce segment, mesurées sur le premier axe x, sont inférieures à P/2. Dans l'exemple de la figure 5, pour Le segment AB, l'octant concerné est 01, et les distances telles que dl ou d'l, sont mesurées sur le premier axe x. Les coordonnées des pixels sélectionnés sont bien entendu celLes des pixels à afficher. L'ordinateur commande alors en conséquence le moyen d'affichage, pour provoquer l'affichage des pixels sélectionnés. La figure 7 permet de mieux comprendre le processus de détermination de la distance d'un pixel "candidat" à 12 affichage, avec le segment à afficher. Sur cette figure, on a représenté un segment à afficher dans l'octant 00 et deux lignes (71, 72) et deux cotonnes (81, 82), dont les intersections sont voisines de ce segment. On suppose que Le pixel PI, de coordonnées Cx, y) dans le repère de référence, est un pixel voisin de ce segment, et qu'il est candidat à l'affichage. On désigne par (xM, Y) les coordonnées dans Le repère, du point d'intersection M de la colonne 82 avec Le segment AB, et par d la distance séparant le pixel candidat et le segment AS. Pour ce pixel appartenant à L'octant 00, à dominante x, ainsi que pour tous les pixels des octants à dominante x (00, 10, 20, 30), il est facile de montrer que : De la même manière, il est facile de montrer que pour tout les pixels candidats à L'affichage de segments situés dans les octants à dominante y (01, 11, 21, 31), La distance d s'exprime par la relation suivante : Les valeurs des quantités x -x et y -y B A B A permettent de déterminer l'octant auquel appartient le segment AB à afficher. Le choix des coordonnées X, Y du premier pixel candidat, se fait de la manière suivante, pour L'octant 00 : Si x et y désignent par exemple les A A coordonnées du point A, extrémité d'un segment (enregistrées en mémoire), et Si ces coordonnées sont mesurées par des valeurs présentant respectivement une partie entière et une partie non entière, on désigne par Lx A] la partie entière de la valeur de x , et par [xA] la partie entière de la valeur de xA, augmentée de une unité. De la même manière, on désigne par [yA] la partie entière de la valeur de Y^, et par [yA] la partie entière de la valeur de y A' augmentée de une unité.Pour les différents octants, les coordonnées (X, Y) d'un pixel candidat sont choisies de sorte que x=rx A1, ou X=lxJ ou Y=ry1, ou Y=LyAj selon L'octant considéré. Le choix en fonction des octants est indiqué dans le tableau suivant : octants J 00 X= EX1 Y= LYA ] 01 X = Lx i y = EYA1 A A 10 X = Lx A Y = Ly A1 Il X = rx A1 v = A A 20 x = Lx J Y = r 21 x = Tx Y = Ly A1 30 X = ruz v = 31 X = Lx A1 r = Ly j A L'évaluation de la valeur absolue de la distance d est faite en trois étapes - on choisit un pixel candidat éventuel, de coordonnées X, Y, telles que définies par Le tableau ci-dessus, - on évalue la distance d, de la façon indiquée plus haut, - si d est supérieure, en valeur absolue, à la moitié de la valeur du pas de grille, on choisit un autre pixel pour Lequel Les coordonnées (X, Y) sont telles que d est inférieure, en valeur absolue, à la moitié de la valeur du pas de La grille. Pour une extrémité B d'un segment de la portion de polyligne correspondant à L'arc à afficher, on désigne par xB et yB les coordonnées de l'extremité B dont les valeurs comportent respectivement une partie entière et une partie non entière, on désigne par LX J la partie entière de la valeur de xB, et par [xB] la partie entière de la valeur de xB, augmentée de une unité. De la même manière, on désigne par [yb] la partie entière de la valeur de yB, et par [yB] la partie entière de la valeur de yB, augmentée de une unité. Le choix de la coordonnée X ou Y , du E E dernier pixel corresponddant à l'extrémité B du segment, dépend de L'octant où est située cette extrémité, et est donne par Le tableau suivant : octants O0 x = Lx J E B Ol Y = 10 xE = rx i Il Y = E 20 x = rx i E B 21 Y = y E B 30 X = Lx 31 E = E B Cette coordonnée X ou Y permet de E E déterminer Le nombre d'itérations du calcul d'affichage. Sur chaque Ligne ou colonne de balayage, il est nécessaire de déterminer qui, du pi:el candidat ou de son suivant, sur cette ligne ou cette colonne, doit être pris en considération pour L'affichage. Cette détermination est effectuée, en déterminant, selon L'octant, Si La distance d séparant Le pixel candidat et Le segment est inférieure à P/2 ou supérieure à -P/Z, tel que défini dans le tableau suivant : octants 00 d P/2 01 d P/2 10 d P12 Il d > -P/2 20 d > -P/2 21 d > -P/2 30 d > -P/Z 31 d P/Z Ce tableau montre que si d est inférieure, en valeur absolue, à P/2, le pixel candidat doit être choisi.Sinon c'est le pixel candidat suivant qui doit être choisi, sur La ligne ou La colonne balayée. Enfin, il est possible que pour deux segments consécutifs Ei-1Ei et EiEi+1 de la portion de polyligne à afficher, et tel que représenté sur la figure 8, il se produise un "saut" dans la séquence de pixels à afficher. Ce saut apparaît au voisinage de L'extrémité Ei des segments Ei-1Ei et EiEi+1, où deux pixels consécutifs P1,P2, sont distants de plus d'une unité du pas p de La grille. Dans ce cas, on ajoute lorsque c'est nécessaire, un pixel supplémentaire, par exemple P3, pour combler le saut. Ce saut est faciLe à détecter à partir des coordonnées des pixels P1 et P2 ; le pixel supplémentaire à ajouter, est déterminé, selon L'octant, par balayage de la ligne ou de la colonne qui suit les pixels P1 ou P2, et en recherchant un candidat dont la distance à l'un des segments, est inférieure, en valeur absolue, au demi-pas P/2 de la grille. La figure 9 est un organigramme des opérations essentielles d'un programme enregistré en mémoire, permettant de mettre en oeuvre le procédé de L'invention. Les opérations essentielles qui apparaissent dans cet organigramme, ont été décrites plus haut. Cet organigramme fait apparattre notamment, que La détermination des pixels à afficher pour chaque segment ou portion de segment, est entreprise des que les coodonnées des extrémités de chaque segment ou portion de segment, sont obtenues. La description qui vient d'être faite pour l'affichage d'arcs de courbes paramétriques polynomiales, reste valable pour L'affichage d'arcs de courbes paramétriques rationnelles. En effet, les traitements pour Les courbes paramétriques rationnelles peuvent être ramenés aux traitement effectués pour les courbes paramétriques polynomiales. De plus, le procédé de L'invention présente la propriété de cohérence suivante : Si on considère L'ensemble des séquences des pixels à afficher pour visualiser un arc d'une courbe, et Si on considère une portion de cet arc de courbe, les séquences de pixels à afficher pour visualiser cette portion, forment un sous ensemble de L'ensemble des séquences à afficher pour visualiser L'arc. Plus précisément, si on affiche Les pixels permettant de visualiser une portion d'un arc d'une courbe, il est certain, grâce au procédé de L'invention, que les pixeLs qui sont à afficher pour visualiser la totalité de L'arc ont, dans La partie commune à L'arc et à la portion d'arc, les mêmes coordonnées. Cette propriété de cohérence est importante, notamment lorsqu'on souhaite effacer une portion d'arc : Les coordonnées calculées, des pixels à effacer pour cette portion d'arc correspondent respectivement aux coordonnées calcuLées des pixels affichés pour cette portion. Cette propriété permet d'effectuer un "gommage" propre d'une portion d'arc d'une courbe. REVENDICATIONS 1. Procédé d'affichage d'arcs de courbes paramétriques polynomiales, sur un support de visuaLisation d'un moyen d'affichage relié à un ordinateur pour L'aide au graphisme dans la conception ou le dessin assisté par ordinateur, cet ordinateur étant relié à une mémoire, L'affichage sur Le support étant déterminé par une grille de pixels définie par des Lignes et des colonnes parallèles, régulièrement espacées d'un pas prédéterminé, successivement balayées, chaque pixel est Localisé par L'intersection d'une ligne et d'une colonne et étant affiché Lorsque la Ligne et La colonne correspondantes reçoivent des signaux de commande d'affichage au cours du balayage, les pixels de la grille sont repérés par leur coordonnées tx, y) dans un repère de référence (t, x, y) ayant un premier axe Cx) et un deuxième axe étant décrite mathématiquement par la fonction vectorielle U(t)=(x(t), y(t)) d'un paramètre t, avec Ot Ui, avec isO, 1, ..., d, délimitant un polygone de contrôle, chaque point de contrôle U ayant des coordonnées réelles (x , y ) dans le repère de référence, ces coordonnées' étant enregistrées dans la mémoire de L'ordinateur, chaque courbe est Interpolable par une polyligne ayant une profondeur d'interpolation k et comportant N segments successifs orientés, ayant chacun deux extrémités situées sur la courbe, L'affichage d'un arc d'une courbe étant déLimité par un couple de paramètre (t , t ) sur l'intervalle [0,1] de la courbe U(t), le procédé consistant à afficher une portion de polyligne correspondant à cet arc, délimitée par un point de départ (Ad) et un point d'arrivée (Af), en affichant les pixels les plus proches de cette portion de polyligne, caractérisé en ce qu'il consiste, pour chaque arc :: - à calculer La profondeur d'interpoLation k de la courbe correspondant à cet arc, à partir du degré d de La courbe et de la diagonale D du polygone de contrôLe, calculée à partir des coordonnées enregistrées des points de contrôLe, pour établir une correspondance biunivoque entre L'ordre i des extrémités Ei des segments de la polyligne et la partition de l'intervalle [0,1] du paramètre t, en 2k parties égales, de sorte que ti=i.2-k, ti étant le paramètre de L'extrémité E, - à établir une transformation (td, t f) # (i, u), (j, v), qui aux paramètres du couple (td,tf) fait correspondre respectivement deux couples de valeurs (i,u), (j,v) tels que td=i.2-k+u et tf=j.2-k+v,avec u - à calculer par récurrence, les coordonnées de i+1 premières extrémités de segments de la polyligne dans le repère de référence, pour calculer les coordonnés du point de départ Ad, à partir des coordonnées des extrémités Ei et Ei+1 de segments de la polyligne, de sorte que Ad=Ei+u(Ei+1-Ei), AdEi+1 étant une portion de segment à afficher, les coordonnées de A et E étant enregistrées en mémoire, d 1+1 - à calculer par récurrence, les coordonnées des extrémités Ei+2 à Ej+1 de segments de la polyligne dans le repère de référence, pour calculer les coordonnées du point d'arrivée Af, à partir des coordonnées des extrémités Ej et Ej+1, de sorte que Af=Ej+v(Ej+1-Ej), les segments correspondant aux extrémités Ei+1 à Ej, ainsi que la portion de segment EjAf étant à afficher, les coordonnées des extrémités Ei+2 à Af étant enregistrées en memoire, - à déterminer, des que les coordonnées d'extrémités de chaque segment ou portion de segment à afficher sont enregistrées en mémoire, une séquence de pixels à afficher, les pixels de chaque séquence étant séLectionnés au voisinage de ce segment et étant affiches sur le support de visuaLisation , Lorsque les distan- ces séparant ces pixels du segment correspondant, mesurées dans le repère de référence, respectivement Le long des lignes ou des colonnes balayées et qui coupent ce segment, sont Inférieures en valeurs absolues, à la moitié de la valeur du pas de la grille de pixels. 2. Procédé selon la revendication 1, caractérisé en ce que le calcul par récurrence des coordonnées des extrémités de segments d'une polyligne interpolant une courbe, consiste à choisir un nombre N de segments de chaque polyligne, en relation avec la profondeur k d'interpoLation, tel que k k relation k=1 profondeur est donnée par La relation k=[Log4d 8 D1 t où D désigne la valeur de ta diagonale du polygone de contrôle, calculée par L'ordinateur à partir des coordonnées des points de contrôle enregistrées en mémoire, puis à déterminer les coordonnées (x...,y...) des extrémités des segments de chaque polyligne, entre les points de contrôle U et O Ud, par récurrence calculée par L'ordinateur, en évaLuant a priori des différences en avant C6x1, #yi) qu'il faut ajouter respectivement aux coordonnées (x;, y) de L'extrémité d'un segment pour passer aux coordonnées Cx i+1, y ici de L'extrémité d'un segment suivant s*t ta-polyligne, de sorte que :: xi+1=xi+#xi et yi+1=yi+#yi avec #xi+1=#xi+#2xi et #yi+1=#yi+#2yi avec O 3. Procédé selon la revendication 1, caractérisé en ce que, pour déterminer Les pixels à afficher dans chaque séquence, en mesurant respectivement le long de toutes les Lignes ou de toutes les colonnes balayées qui coupent le segment correspondant à cette séquence au voisinage de ce segment, les distances qui séparent ces pixels et ce segment : : - on subdivise Le plan du support de visualisation en huit octants repérés par des numéros d'ordre prédéterminés, quatre octants de ce repère étant dits à dominante tx) Lorsque les coordonnées des points situés dans tes octants ont des valeurs absolues sur le premier axe (x), supérieures aux va Leurs absolues sur le deuxième axe (y), quatre autres octants de ce repère sont dits à dominante y, Lorsque les coordonnées des points situés dans ces quatre autres octants ont des valeurs absolues, sur le deuxième axe (y), supérieures aux valeurs sur le premier axe (x), - à partir des coordonnées des extrémités des segments ou portions de segments à afficher enregistrées en mémoire, on détermine le numéro d'ordre de L'octant contenant ces extrémités, - on effectue un balayage des Lignes ou des colonnes coupant chaque segment à afficher et on séLectionne, pour tout segment dont les extrémités sont dans un octant à dominante x, parmi les pixels voisins de ce segment et situés aux intersections de colonnes avec ce segment, ceux pour lesquels les distances respectives à ce segment, mesurées sur le deuxième axe (y), sont inférieures en valeurs absolues à un demi-pas (P/2) de grille, on sélectionne, pour tout segment dont les extrémités sont dans un octant à dominante y, parmi Les pixels voisins de ce segment et situés aux intersections de Lignes avec ce segment, ceux pour lesquels les distances respectives å ce segment, mesurées sur le premier axe (x) sont inférieures en valeurs absolues à un demi-pas de grilLe 4. Procédé selon La revendication 1, caractérisé en ce que tes séquences de pixels à afficher pour visualiser une portion d'un arc de courbe forment un sous-ensembLe de l'ensemble des séquences de pixels à afficher pour visuaLiser cet arc.