Brevet FR2927449A1 — publié le 20090814

TRACE DE LIGNES POLYGONALES 5 La présente invention se rapporte au domaine de l'affichage numérique de surfaces tridimensionnelles, et en particulier au tracé de lignes polygonales. L'invention est plus particulièrement adaptée aux applications embarquées, par exemple de cartographie numérique, sur des terminaux 10 mobiles, par exemple des téléphones portables, assistant personnel numérique ou PDA etc. De telles applications sont par exemple mises en oeuvre dans des terminaux mobiles aptes à communiquer avec un serveur. II existe plusieurs façons d'afficher sur un écran un objet en trois dimensions. On peut par exemple afficher la texture de la surface de l'objet. La 15 représentation filaire (ou � wireframe � en anglais) permet une meilleure visualisation du relief de la surface de l'objet. Bien entendu, on peut afficher à la fois la structure via une représentation filaire, et la texture. Une représentation filaire d'une surface tridimensionnelle peut être obtenue en traçant simplement les primitives d'affichage, que ce soit des 20 triangles ou des quadrilatères par exemple. Toutefois, les primitives d'affichage peuvent comprendre des polygones plus complexes. Par exemple, un ballon de football peut être décomposé en hexagones, une maison en quadrilatères, une montagne en polygones quelconques. Les primitives d'affichages peuvent être coplanaires ou ne pas être coplanaires. 25 Egalement, il peut être souhaitable d'afficher d'autres types de lignes polygonales, comme des lignes polygonales ouvertes, afin de permettre une visualisation de routes par exemple. Lorsque l'affichage est réalisé sur un terminal en communication avec un serveur, éventuellement distant, le terminal reçoit du serveur des données 30 d'affichage, et traite ces données pour pouvoir afficher la surface tridimensionnelle correspondant à ces données. Les données d'affichage comprennent typiquement les coordonnées de sommets des primitives d'affichage, de sorte que leur transmission nécessite relativement peu de bande passante. Lorsqu'un polygone comprend quatre points ou davantage, ce polygone peut ne pas être coplanaire. Certains terminaux relativement pauvres en ressources de mémoire et/ou de calcul, sont incapables d'afficher des polygones non coplanaires et sont configurés pour traiter uniquement des triangles. Par exemple, pour un jeu de coordonnées de trois points formant un triangle, un téléphone mobile est capable de calculer le plan passant par les trois points et d'afficher la partie du plan interne au triangle. En outre, certaines applications dans les terminaux mobiles permettant de tracer des surfaces tridimensionnelles, par exemple les interfaces de programmation (API) graphiques 3D, sont conçues pour réaliser des tracés uniquement à partir de triangles � en strip � et/ou � en fan �. Un ensemble ordonné de triangles � en strip � est tel que chaque triangle de l'ensemble, à partir du deuxième triangle selon l'ordre de l'ensemble ordonné de triangles, comporte deux sommets du triangle précédent et un nouveau sommet distinct des sommets des triangles précédents. Un ensemble ordonné de triangles � en fan � est un ensemble ordonné � en strip � dans lequel il existe un sommet commun à chacun des triangles. Ainsi certaines applications sont capables d'afficher seulement les surfaces internes de triangles, qui de plus doivent parfois être organisés � en 20 strip � et/ou � en fan �. Il serait souhaitable de pouvoir afficher un tracé de ligne polygonale en utilisant ces applications relativement pauvres en ressources de mémoire et/ou de calcul. Selon un premier aspect, l'invention a pour objet un procédé de tracé 25 d'une ligne polygonale d'une image numérique, à partir d'un ensemble ordonné 2D ou 3D de sommets, comprenant les étapes suivantes, pour au moins un sommet donné suivant un premier sommet voisin et précédent un deuxième sommet voisin de cet ensemble ordonné: a/ déterminer un point associé au sommet donné, ce point associé 30 étant situé à une distance fixée d'une droite correspondant au premier sommet voisin et au sommet donné, et situé à la même distance fixée d'une droite correspondant au sommet donné et au deuxième sommet voisin, le point associé au sommet étant sélectionné en utilisant l'ordonnancement de l'ensemble de sommets, b/ définir une suite ordonnée de triangles, les sommets de ces triangles étant définis au moins en fonction des sommets de l'ensemble et du point associé, c/ afficher les surfaces des triangles de la suite ordonnée de triangles. Ainsi, la ligne polygonale est tracée par le biais d'affichage de surfaces de triangles. Un terminal relativement pauvre en ressources mémoire et/ou calcul, capables d'afficher seulement les surfaces internes de triangles, est ainsi à même de réaliser ce tracé. Le point associé est sélectionné en tenant compte de l'ordonnancement des sommets. Le point associé peut être d'un coté ou de l'autre des lignes brisées définies par les sommets selon l'ordre de ces sommets dans l'ensemble ordonné. Les coordonnées des sommets et des points peuvent par exemple comprendre une latitude, une longitude et une altitude dans un référentiel (X, Y, Z), ou autre. La distance fixée peut être de un pixel par exemple, mais toute autre 20 valeur de distance est envisageable. Avantageusement, un vecteur associé au sommet donné, dit vecteur normal, est défini et des premier et second projetés sont déterminés en projetant orthogonalement respectivement les premier et second sommets voisins sur le plan passant par le sommet donné et orthogonal au vecteur 25 associé. La droite de l'étape a/ correspondant au premier sommet voisin et au sommet donné passe par le premier projeté et par le sommet donné, et la droite de l'étape a/ correspondant au sommet donné et au deuxième sommet voisin passe par le sommet donné et le deuxième projeté. Ainsi, le point associé appartient à un plan tangent, lequel peut être 30 plus pertinent que le plan défini par le sommet donné, le premier sommet voisin et le deuxième sommet voisin. Par exemple, dans le cas d'un ensemble ordonné de sommets correspondant à une route, il peut être judicieux de choisir un vecteur normal dans une direction fixe, typiquement la direction verticale. Selon un autre exemple, le vecteur associé au sommet donné est obtenu à partir de sommets situés dans un voisinage du sommet donné. Le plan tangent auquel appartient le point associé est défini par le voisinage du sommet donné. Les sommets situés dans ce voisinage peuvent comprendre d'autres sommets que le premier sommet voisin et le deuxième sommet voisin. Bien entendu, l'invention n'est pas limitée par cette étape de projection dans un plan orthogonal à un vecteur normal. La droite de l'étape a/ correspondant au premier sommet voisin et au sommet donné peut passer par le premier sommet voisin et par le sommet donné, et la droite de l'étape a/ correspondant au sommet donné et au deuxième sommet voisin peut passer par le sommet donné et le deuxième sommet voisin. On peut prévoir de déterminer un point milieu du segment ayant pour extrémités le sommet donné et le point qui lui est associé ; et un point symétrique du point milieu est déterminé par rapport à ce sommet donné. Les sommets des triangles de la suite ordonnée de triangles comportent ce point milieu et le point symétrique. Ainsi, la ligne à tracer recouvre les segments reliant les sommets de l'ensemble ordonné. En particulier, ce mode de réalisation peut se révéler intéressant dans le cas d'une ligne ouverte, pour laquelle il n'existe pas de raison particulière de tracer la ligne d'un coté ou de l'autre des segments. Avantageusement et de façon non limitative, pour chaque sommet d'une pluralité de sommets de l'ensemble on associe un point respectif selon l'étape a/ ; et les sommets des triangles de la suite ordonnée de triangles sont définis au moins en fonction des sommets de l'ensemble et des point associés. Avantageusement et de façon non limitative, chaque triangle à compter du deuxième triangle selon l'ordre de la suite ordonnée de triangles, comporte deux sommets du triangle qui le précède selon l'ordre et un sommet distinct des sommets de ce triangle qui le précède. Les sommets des triangles de la suite ordonnée comportent avantageusement et de façon non limitative les sommets de l'ensemble et le(s) point(s) associé(s) déterminé(s) selon l'étape a/. Selon un autre aspect, l'invention a pour objet un module adapté pour le tracé d'une ligne polygonale d'une image numérique, à partir d'un ensemble ordonné 2D ou 3D de sommets, comprenant : - des moyens de calcul pour déterminer un point associé (Bn) à un sommet donné (An) de l'ensemble ordonné, ce point associé étant situé à une distance fixée d'une droite correspondant au sommet (An_I) précédent dans l'ensemble ordonné le sommet donné et au sommet donné, et situé à la même distance fixée d'une droite correspondant au sommet donné et au sommet (An+1) suivant dans l'ensemble ordonné le sommet donné, le point associé au sommet donné étant sélectionné en utilisant l'ordonnancement de l'ensemble de sommets, - des moyens pour définir une suite ordonnée de triangles, les sommets desdits triangles étant définis au moins en fonction des sommets de l'ensemble ordonné et du point associé. - des moyens d'affichage des surfaces des triangles de la suite ordonnée. Ce module permet de mettre en oeuvre le procédé selon un aspect de l'invention. Les moyens d'affichage peuvent par exemple comprendre une interface graphique adaptée pour tracer en 3D des surfaces à l'aide de 25 triangles en � strip � qui lui sont indiqués par la suite ordonnée des sommets de ces triangles. Le module peut comprendre ou faire partie d'un terminal en communication avec un serveur. Le terminal reçoit des données du serveur, par exemple des coordonnées des sommets de l'ensemble ordonné. Les 30 données peuvent être hiérarchisées en r niveaux de précision différents. Selon encore un autre aspect, l'invention a pour objet un programme d'ordinateur comprenant des instructions pour mettre en oeuvre les étapes d'un procédé selon un mode de réalisation de l'invention, lors d'une exécution du programme par des moyens de traitement. D'autres caractéristiques et avantages de l'invention apparaîtront encore à la lecture de la description qui va suivre. Celle-ci est purement illustrative et doit être lue en regard des dessins annexés sur lesquels : - les figures 1A et 1B représentent deux ensembles ordonnés de sommets et les tracés correspondant respectivement à ces ensembles ; - la figure 2 représente un polygone � à trous �; - les figures 3A et 3B montrent deux types de tracés de lignes obtenus à partir d'ensembles de sommets ordonnés en sens inverses l'un de l'autre ; - la figure 4 illustre un procédé de tracé de ligne de polygone selon un mode de réalisation de l'invention ; -la figure 5 représente une suite de triangles susceptible d'être utilisée dans un mode de réalisation de l'invention. - la figure 6 illustre un procédé de tracé de ligne de polygone selon un autre mode de réalisation de l'invention ; Dans un mode de réalisation, on considère le tracé du contour d'une primitive polygonale. Pour des raisons de clarté de représentation, il est préférable de supposer les polygones coplanaires. Néanmoins, le procédé de tracé s'applique dans n'importe quelles circonstances, par exemple pour différentes faces d'un polyèdre quelconque. Le mode de dessin des polygones dépend essentiellement de l'ordre des sommets. En effet, les figures 1A et 1B montrent que le tracé de l'ensemble ordonné (A,B,C,D) ne coïncide pas avec le tracé de l'ensemble (A,B,D,C). Bien entendu, le tracé de l'ensemble ordonné (A,B,C,D) où les sommets sont donnés dans le sens horaire (ou sens indirect) et le tracé de l'ensemble ordonné (D,C,B,A) où ils sont donnés dans le sens antihoraire (ou sens direct) sont semblables. De même, les tracés des ensembles ordonnés (A,B,C,D) et (B,C,D,A), où les sommets sont décalés d'une position correspondent à des quadrilatères semblables. Par convention, on peut différentier les polygones en fonction de leur orientation. Une telle convention permet de déterminer sans ambigüité les zones à remplir et celles à vider. Elle permet de définir des polygones généralisés ou polygone "à trous". La figure 2 illustre le cas d'un tel polygone généralisé simplement défini à partir de deux quadrilatères orientés différemment. L'orientation utilisée pour remplissage intervient pour le tracé d'une zone de délimitation entre les mailles, appelée � wireframe � en anglais. Un tel contour sous forme de bande ne doit pas dépasser le polygone "à trou" pour que les faces d'un objet coïncident bord à bord. Les figures 3A et 3B montrent des zones de délimitation obtenues pour des ensembles de coordonnées de sommets comprenant les mêmes sommets, mais en ordre inversés l'un de l'autre. Sont représentées deux faces carrées orthogonales et les zones de délimitations, ou contours, sous forme de bandes dépassant (figure 3B) ou ne dépassant pas (figure 3A) des faces. On voit que lorsque les bandes dépassent, comme sur la figure 3B, cela nuit à la lisibilité du dessin. En d'autres termes, il faut que la bande soit toujours à l'intérieur des faces. Sur l'exemple de la figure 2, le contour de (A,B,C,D) devrait être tracé vers l'intérieur tandis que le contour de (E, F,G,H) devrait être tracé vers l'extérieur. Dans les deux cas, le contour devrait être tracé vers la normale indirecte au contour. Polygone fermé Dans le cas, tout d'abord, d'un polygone de l'espace défini par l'ensemble ordonné (A o, • • • • .4N-1) où N > 3, dans un souci de simplification, on suppose arbitrairement que l'ensemble des sommets est prolongé de manière cyclique. En d'autres termes, on note Ao = AN, A-1 = AN-1 et plus généralement T" . Z. An+w ù An_ Ensuite, on considère les trois points consécutifs du polygone An-1, An et =~n+1 autour d'un sommet donné An. Comme (.Ao, • • • , -AN-1) définit un polygone, on sait que A A, et AnAn+1 ne sont pas colinéaires. On note désormais in+1/2 le vecteur ' n`-tn+I /•-tn+1An-. Par conséquent, les trois points consécutifs autour de An définissent un plan muni de la base constituée des vecteurs en-1/2 et en+1/2. Le sens de ces 5 vecteurs dérive de l'ordonnancement des sommets dans l'ensemble ordonné de sommets. L'objectif est de déterminer le point Bä associé au point An de sorte que le polygone (Ba... ' BN-1) soit exactement à une distance de un pixel du polygone (Ao, • - , .A N-1) conformément à la figure 4. 10 On se place dans le repère défini par le point Aä et les vecteurs :n-1, 2 et iin+1 f2 On note xi, et yn les coordonnées de Bn dans le repère puis le vecteur An Bn. Par conséquent, il est vérifié : = snlln-1,+2 + YnUn+1 f2 La condition de distance de un pixel s'écrit à l'aide des équations : 1 =d([An_1,An],Bn) = 11'n - an-1/2'/en-1/21I = II 'n-1/2 +Ynt=n+1/2 - (mnjin-1/2 +Yniin+1/2, iin-1/2/t1n-1/2II IIrni1'n-1/2 +Yni1n+1/2 n-1/2+ tln-1/2)tin-1/2 - Yn(5n+1/2.21n_1/2) in-1/2Il = IIYnitn+1/2 - Un+itn+1/2' Un_1/2;)iin-1/2II = lYnl X Iliin+11`2 i'n+1/2/iin-1/2Il 1 = d1 [An, An+1], Bn) 15 = I.Cnl x Il iln-1/2 - (iËn-1/2.2/n+1/2/11n+1/2Il. On en déduit un premier raffinement des coordonnées de Bi, dans le repère : rn = II1[n-1/2 - ;,ten-112 21n+11'2%i1n-1-1/2Il et Jn IIi0n+lj2 - \?ln_1/2 , idn+1/2~}tln--112II En effet, on trouve logiquement quatre solutions correspondant aux 20 quatre demi-bissectrices de l'angle défini par les trois points dans le plan. On impose alors une condition utilisant l'ordonnancement de l'ensemble de sommets : il faut que le point Bn soit vers la normale indirecte des vecteurs Un-1/2 et il, 1 `2 La condition d'orientation vers la normale indirecte s'écrit à l'aide des déterminants : I1 .Tn det(t1n-1/2, t'n) = 0 Un= +fin .> 0 et det•(tln+1 f2, en) = =ùSn `i0 On en déduit les coordonnées exactes de Bä dans le repère : .C,y = Ilrtn-1/2 ù {.?Gn-1/2, un+1/2)ttn+1/2II et yn = + Ilttn+1/2 ù (en-1/2 ttn+1/2 Enfin, pour tracer le contour, il suffit de passer la liste ordonnée (BO, AO, ... , BN-1, AN-1, BO, A0) en bande ou � strip �. Une suite ordonnée de triangles est alors définie ((Bo,Ao,A1) , (Bo,B1,A1), (AI, B1, A2)...) à partir des sommets de l'ensemble ordonné et des points associés à ces sommets. Un exemple de suite est représenté sur la figure 5. Puis la surface de chaque triangle de la suite ordonnée est affichée, suivant un procédé connu. Ligne polygonale ouverte Dans ce mode de réalisation, le tracé d'un chemin représenté par une ligne polygonale ouverte est considéré. Le principe du procédé est sensiblement identique à l'encadrement des polygones. Cependant, il est préférable que le tracé ne soit pas affecté par l'orientation du chemin. De plus, le procédé est légèrement différent pour le premier point et le dernier point. On considère tout d'abord une ligne polygonale de l'espace défini par les points ordonnés (.4o, • • .4 -1) où N > 2. Dans l'encadrement des polygones, le point Bä est calculé dans le plan défini par les trois points consécutifs autour de An. Pour les points Al, AN-2, il est possible de recourir au procédé décrit plus haut. Cependant, ce n'est pas le cas pour les points Ao et AN-1 puisque la ligne polygonale étant ouverte, on ne peut pas définir de manière cyclique les points A-1 et AN. Par conséquent, ce procédé ne permet pas de calculer les 30 coordonnées des points Bo et BN-1...DTD: Le mode de réalisation décrit met en oeuvre un vecteur normal, pour chaque sommet auquel on cherche à associer un point. On décrit plus bas un exemple de choix de vecteur normal. Soit une liste ordonnée de vecteurs normaux (No, • . • -1). Pour les points indicés n tel que 0 Vecteur normal Pour représenter des "volumes" en utilisant les bibliothèques 3D (par exemple "OpenGL", "Direct3D" ou "M3G"), il peut être fait appel à la notion de normales. La normale est définie localement. Le plan tangent TMO (S) à une surface S en un point MO est le plan passant par MO qui approxime le mieux S au voisinage de MO. Un vecteur g est dit "normal" à une surface S en un point MO s'il est orthogonal au plan tangent TMO (S). Les cas principalement considérés sont les suivants : • Si la surface est une sous-variété suffisamment régulière dont on connaît une paramétrisation locale : M(s, t) = (x(s, t), y(s, t), z(s, t)) telle que MO = (x(0, 0), y(0, 0), z(0, 0)) alors on obtient 1-2tiro(8) = (Mo; z')avec : cl û = :- (0,0)eté = r~_1 (0,0). Os vt On en déduit alors facilement un vecteur normal direct en calculant le produit vectoriel g = é_ • Si la surface S est une sous-variété suffisamment régulière dont on connaît une équation locale : F(x, y, z) = 0 telle que MO = (xO, yO, zO) (3) alors on obtient une normale directe avec : = ( F (r0, y°, o), ù (XQ, yO, °'o), ù(ro, ya, y 4 La notion de normale permet généralement de définir comment la lumière doit être réfléchie à la surface du volume considéré. Intuitivement, on considérera que la lumière puisse être effectivement réfléchie orthogonalement à la surface. Néanmoins, les choses sont souvent plus complexes : • D'une part les surfaces sont généralement définies comme des assemblages de triangles dans l'espace. Pour calculer une normale en un point, on peut calculer la moyenne des normales aux triangles auxquels appartient le point. De manière équivalente, cela revient à calculer la dérivée discrète. • D'autre part, les surfaces considérées ne sont pas nécessairement des discrétisations de sous-variétés régulières. Ainsi, un bâtiment même très simple de la forme d'un parallélépipède n'est pas forcément régulier au niveau de ses arêtes. Cela se traduit par des ombrages différents de part et d'autre des arêtes. Pour le tracé des surfaces avec les bibliothèques 3D, cela revient à définir autant de normales différentes de part et d'autre des arêtes pour un même sommet. En effet, si un bâtiment ne peut pas être vu comme une sous-variété régulière, il peut être vu comme un assemblage de sous-variétés régulières appelées faces. Pour un sommet appartenant à deux faces, on calcule la fil. normale à chacune des faces et on attribue la "bonne normale" suivant que l'on considère que le sommet appartient plutôt à une face ou plutôt à l'autre. Par exemple : • Une sphère est constituée d'une seule sous-variété régulière. Par conséquent pour chaque point de la sphère, on définit une seule normale qui coïncide exactement avec la direction du rayon passant par ce point. • Un cube est constitué d'un assemblage de six faces sous-variétés régulières (six faces carrés). Chaque sommet du cube appartient à trois faces, autrement dit chaque sommet apparaît trois fois différemment pour construire le cube. Il faut associer à chaque sommet une normale différente suivant la face qu'on est en train de construire. • Le cylindre est constitué d'un assemblage de trois sous-variétés régulières (deux bases discales et un rectangle). Chaque point du bord du cylindre appartient à une base et au rectangle, autrement dit chaque sommet apparaît deux fois différemment pour construire le cube. Encore une fois, il faut attribuer à chaque sommet une normale différente suivant la face qu'on est en train de construire. L'utilisation des normales est standard dans toutes les bibliothèques d'affichage 3D. Le choix d'une ou de plusieurs normales par sommet dépend de la régularité de la surface. Lorsque la surface est décomposée en primitives polygonales d'affichage, la notion de régularité dépend du choix du développeur. Afin de mettre en valeur un "volume", on est souvent amené à tracer la représentation filaire (� wireframe �). En général, il s'agit simplement de tracer les bords de la primitives d'affichage. Dans les applications en mobilité, les seules primitives d'affichages sont les triangles organisés en bandes ("triangle strip") sous M3G, autour d'un centre ("triangle fan") ou indépendants les uns des autres ("triangles") sous OpenGL ou Direct3D. Néanmoins, afficher toutes les arêtes de tous les triangles n'est non seulement pas nécessaire mais également gourmand en ressources. Dans certains cas, si les primitives d'affichage restent définitivement les triangles, les primitives logiques ou "faces" peuvent être des polygones plus complexes : • Cas du cube : on est amené à considérer ses faces qui sont des carrés qui seront ensuite décomposés en triangles pour le tracé. Néanmoins, pour obtenir une représentation filaire satisfaisante, il suffit de dessiner les bords de chaque carré plutôt que ceux des triangles. • Cas de la décomposition approchée classique d'une sphère : en hexagones comme pour un ballon de football. Les primitives logiques sont les hexagones qui seront ensuite décomposés en triangles pour le tracé. Dans ce cas, il suffit de tracer le bord de chaque hexagone pour avoir une représentation filaire satisfaisante de la sphère. • Cas de la décomposition approchée d'un cylindre : chaque base est un polygone régulier et la bande de hauteur est une succession de rectangles. II suffit de tracer le contour des deux bases et les contours des rectangles pour obtenir une représentation filaire adaptée. Suivant le principe de représentation pseudo-filaire, on dessine les lignes sous formes de bandes de largeur unitaire. Néanmoins, si une bande à une largeur, elle n'a pas d'épaisseur, puisqu'il s'agit du tracé d'un objet en deux dimensions. En d'autres termes, suivant le point de vue adopté, la bande sera ou ne sera pas visible (une bande observée sur la "tranche" n'est pas visible). Il convient donc de tracer suffisamment de bandes de sorte à ce qu'elles soient raccordées les unes aux autres et qu'une ligne soit visible quel que soit le point de vue où l'arête est effectivement observable. Pour tracer les arêtes, on s'appuie sur le même principe que les normales de la lumière. La représentation pseudo-filaire d'une arête doit être visible de manière optimale lorsqu'on regarde l'arête de face. II faut donc tracer la bande dans le plan orthogonal à la normale. Lorsqu'il s'agit de tracer un chemin au sens général du terme (chemin piéton, route, etc.), ceux-ci peuvent être également vus comme des bandes de largeur pas forcément unitaire autour d'une ligne polygonale directrice. Le procédé décrit plus haut dans permet de tracer des tels chemins. II reste néanmoins à déterminer les bonnes normales pour déterminer les plans dans lesquels dessiner les bandes. II est tout à fait réaliste d'imposer à la bande d'être localement dans le plan horizontal, en particulier dans le cas d'une route puisque les routes sont en général sensiblement parallèles au sol. On obtient alors des bandes visibles de manière optimale vue de haut. Toutefois, si le chemin est sur la terre ou sur n'importe quelle autre surface, alors il peut sembler plus approprié d'introduire un paramétrage de cette surface. Chaque point du chemin doit être associé à la normale issue du point et orthogonale à la surface. Le chemin épouse alors la forme de la surface qui le supporte. L'utilisation des normales s'appuie sur la topologie de la surface à tracer. Les coordonnées des vecteurs associés aux sommets, dits "normaux", peuvent également être reçues d'un serveur avec les coordonnées de ces sommets. De manière générale, on peut prévoir un procédé de tracé d'une ligne polygonale d'une image numérique, à partir d'un ensemble ordonné 2D ou 3D de sommets, comprenant les étapes suivantes, pour au moins un sommet donné de cet ensemble : déterminer un point associé à ce sommet donné, ce point associé étant situé à une distance fixée d'une droite correspondant au sommet donné et à un autre sommet de l'ensemble ordonné, le sommet donné et l'autre sommet étant consécutifs dans l'ensemble ordonné, définir une suite ordonnée de triangles, les sommets desdits triangles étant définis au moins en fonction du point associé. Ainsi, il est possible de recourir à un procédé d'affichage de surfaces de triangles pour tracer la ligne polygonale. L'autre sommet peut suivre ou précéder le sommet donné. On peut imposer d'autres contraintes au point associé. Par exemple, on peut tenir compte d'un premier et d'un deuxième sommet voisins encadrant le sommet donné dans l'ensemble ordonné. Le point associé peut par exemple être déterminé de façon à ce qu'il soit situé à la distance fixée d'une droite correspondant à un premier sommet voisin et au sommet donné, et situé à la même distance fixée d'une droite correspondant au sommet donné et au deuxième sommet voisin. Pour un sommet donné, on peut prévoir de déterminer plus d'un point associé. Par exemple, on détermine deux points associés, symétriques l'un par rapport à l'autre, comme les points CN-1 et GN-ide la figure 6. La suite ordonnée de triangles peut alors comporter seulement des triangles dont les 5 sommets sont des points associés. Alternativement, on peut prévoir que pour deux sommets consécutifs (le sommet donné et l'autre sommet) de l'ensemble ordonné de sommets, on choisisse le point associé à l'un de ces sommets (le sommet donné) de sorte que : 10 la droite passant par ce point associé et ce sommet est perpendiculaire à la droite passant par les deux sommets consécutifs, le point associé est à une distance fixée de ce sommet, le point associé est sélectionné en utilisant 15 l'ordonnancement de l'ensemble ordonné de sommets. Un tel procédé peut être appliqué en particulier pour déterminer le point associé à un sommet correspondant à une extrémité de ligne polygonale ouverte. On peut aussi choisir d'appliquer ce procédé aux autres sommets de 20 l'ensemble ordonné. Un sommet est alors associé à un ou deux points, ce qui multiplie le nombre de triangles de la suite ordonnée de triangles. De manière générale, l'invention n'est pas limitée par la façon dont le point associé est déterminé. REVENDICATIONS 1. Module adapté pour le tracé d'une ligne polygonale d'une image 5 numérique, à partir d'un ensemble ordonné 2D ou 3D de sommets, comprenant - des moyens de calcul pour déterminer un point associé (Bn) à un sommet donné (An) de l'ensemble ordonné, ledit point associé étant situé à une distance fixée d'une droite correspondant au sommet (An_1) précédent dans l'ensemble ordonné le sommet donné et au 10 sommet donné, et situé à la même distance fixée d'une droite correspondant au sommet donné et au sommet (An+1) suivant dans l'ensemble ordonné le sommet donné, le point associé au sommet donné étant sélectionné en utilisant l'ordonnancement de l'ensemble de sommets, 15 des moyens pour définir une suite ordonnée de triangles, les sommets desdits triangles étant définis au moins en fonction des sommets de l'ensemble ordonné et du point associé. des moyens d'affichage des surfaces des triangles de la suite ordonnée. 20 2. Procédé mis en oeuvre par des moyens de traitement, de tracé d'une ligne polygonale d'une image numérique sur un écran d'un terminal, à partir d'un ensemble ordonné 2D ou 3D de sommets, comprenant les étapes suivantes, pour au moins un sommet donné (An) suivant un premier sommet 25 voisin (An_.) et précédent un deuxième sommet voisin (An+1) dudit ensemble ordonné: al déterminer un point (Bn) associé au sommet donné, ledit point associé étant situé à une distance fixée d'une droite correspondant au premier sommet voisin et au sommet donné, et situé à la même distance fixée d'une 30 droite correspondant au sommet donné et au deuxième sommet voisin, le point associé au sommet étant sélectionné en utilisant l'ordonnancement de l'ensemble de sommets,b/ définir une suite ordonnée de triangles, les sommets desdits triangles étant définis au moins en fonction des sommets de l'ensemble et du point associé, et cl afficher les surfaces des triangles de la suite ordonnée de triangles sur l'écran du terminal. 3. Procédé de tracé d'une ligne polygonale selon la revendication précédente, comprenant en outre l'étape consistant à : définir un vecteur associé (Na) au sommet donné (An) et déterminer des premier (An,n_1) et second (An n+1) projetés en projetant orthogonalement respectivement les premier (An_1) et second (An+1) sommets voisins sur le plan (Pn) passant par le sommet donné et orthogonal au vecteur associé, et dans lequel, à l'étape al : la droite correspondant au premier sommet voisin et au sommet donné passe 15 par le premier projeté et par le sommet donné, et la droite correspondant au sommet donné et au deuxième sommet voisin passe par le sommet donné et le deuxième projeté. 4. Procédé selon la revendication 3, dans lequel le vecteur associé (-Ç'',) au 20 sommet donné (An) est obtenu à partir de sommets situés dans un voisinage du sommet donné. 5. Procédé selon l'une quelconque des revendications 2 à 4 précédentes, dans lequel on réalise en outre l'étape consistant à déterminer un point milieu 25 (C•â ) du segment ayant pour extrémités le sommet donné (An) et le point (Bn,n) qui lui est associé ; et on détermine un point symétrique (~f72) du point milieu par rapport audit sommet donné ;les sommets des triangles de la suite ordonnée de triangles comportant ledit point milieu et ledit point symétrique. 6. Procédé selon la revendication 2 à 5 selon lequel, pour chaque sommet d'une pluralité de sommets de l'ensemble on associe un point respectif selon l'étape a/ ; et les sommets des triangles de la suite ordonnée de triangles sont définis au moins en fonction des sommets de l'ensemble et des point associés. 7. Procédé selon l'une quelconque des revendications 2 à 6, selon lequel chaque triangle à compter du deuxième triangle selon l'ordre de la suite ordonnée de triangles, comporte deux sommets du triangle qui le précède selon ledit ordre et un sommet distinct des sommets dudit triangle qui le précède. 8. Procédé selon l'une quelconque des revendications 2 à 7, selon lequel les sommets des triangles de la suite ordonnée comportent les sommets de l'ensemble et le(s) point(s) associé(s) déterminé(s) selon l'étape a/. 9. Programme d'ordinateur comprenant des instructions pour mettre en oeuvre les étapes d'un procédé selon l'une des revendications 2 à 8 lors d'une exécution du programme par des moyens de traitement.