Brevet FR2865564A1 — publié le 20050729

PROCEDE ET DISPOSITIF DE DECOMPOSITION D'UNE FORME GEOMETRIQUE 5 La présente invention concerne un procédé et un dispositif de décomposition d'une forme géométrique. Elle s'applique, en particulier à l'affichage d'images de synthèse en deux 10 ou en trois dimensions. Les procédés de décomposition de formes géométriques actuellement connus présentent des durées de calcul qui sont très élevées (par exemple de plusieurs heures pour une seule image de synthèse complexe, en trois dimensions). Chaque affichage d'image est basé sur l'affichage de formes géométriques. Ces procédés utilisent, par exemple, l'algorithme défini par M. Dan Gordon (voir, par exemple, "The scanline principle: efficient conversion of display algorithms into scanline mode", The visual computer, Editeur Springler-Verlag - 1999) par lequel on extrait, parmi tous les sommets définissant un polygone, ceux qui se trouvent en dessous des deux sommets qui l'entourent, appelés "points critiques". Puis, en partant du point critique le plus bas, on remplit le polygone définit par les côtés du polygone qui se rejoignent en ce point jusqu'à l'ordonnée du point critique suivant. Si ce point critique est extérieur à la surface déjà remplie, il est traité ultérieurement ou en parallèle et on recommence jusqu'à ce qu'un côté du polygone considéré soit achevé (il ne monte plus) ou jusqu'à ce qu'un point critique soit sur la périphérie de la surface déjà remplie. Dans le premier cas, on arrête le remplissage et on passe au point critique le plus bas restant. Dans le deuxième cas, le point critique qui est à la périphérie de la surface déjà remplie sert à couper le remplissage en remplissage de deux surfaces disjointes. Les durées de manipulation des points critiques sont au minimum proportionnelles au produit du nombre de points critiques par le logarithme de ce nombre. Lorsque le nombre de points critiques augmente, la durée de décomposition (et donc celle d'affichage) du polygone augmente considérablement. La présente invention vise à améliorer la durée de décomposition, de remplissage et/ou d'affichage d'une forme géométrique complexe ou d'une image de synthèse et, plus particulièrement, d'un polygone donné dans ladite image. Un polygone est défini par des sommets et une interpolation linéaire entre ces sommets. La présente invention ne se limite pas aux polygones mais s'étend, bien au contraire, à toute forme géométrique définie par des points (généralement des sommets) de son périmètre et, éventuellement d'autres points (par exemple des courbes de Bézier), que les morceaux de périmètre entre ces points soit ou non linéaire. A cet effet, selon un premier aspect, la présente invention vise un procédé de décomposition d'une forme géométrique définie par au moins une liste ordonnée et cyclique de sommets, caractérisé en ce qu'il comporte: au moins une étape de recherche de sections monotoniques sur la succession de sommets définie par chaque dite liste ordonnée et des bornes de ces sections, selon au moins une dimension et un sens; - au moins une étape de regroupement des sections monotoniques deux à deux pour définir des régions de ladite forme géométrique; - au moins une étape de classification des dites régions en régions "internes" pour lesquelles l'intérieur de la forme est à l'intérieur de la région considérée, et en régions "externes" pour lesquelles l'intérieur de la forme est à l'extérieur de la région considérée; - une étape de tri des régions externes en fonction de leur coordonnées dans une dimension et un sens et - une étape de décomposition de la forme géométrique en formes géométriques internes simples, décomposition mettant en oeuvre les régions externes triées. Grâce à ces dispositions, le suivi du contour de chaque polygone définissant la forme géométrique et défini par une liste ordonnée de sommet est aisé, en suivant les différentes sections qu'il comporte. La forme géométrique, dans son ensemble, est traitée rapidement grâce à la classification des régions, au tri des régions externes, puis à la décomposition en formes géométriques simples. La structure ordonnée des formes géométriques simples permet ensuite la mise en oeuvre d'un algorithme de remplissage de la forme géométrique, par exemple de type "ligne de balayage", pour affichage de la forme géométrique ou de l'image. La technique de "ligne de balayage" (en anglais "scanline") traite successivement des pixels successifs sur une même ligne, en traitant successivement les lignes successives de l'image à constituer. La présente invention permet ainsi un affichage très rapide de forme géométriques complexes. Selon des caractéristiques particulières, les formes géométriques simples sont des polygones monotones dans une dimension. Selon des caractéristiques particulières, la dimension considérée dans l'étape de recherche de sections monotoniques, et l'étape de tri est identique. Par exemple, c'est la dimension des ordonnées (dimension verticale sur une image). Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci- dessus comporte, en outre une étape de choix de la dimension et/ou du sens utilisé, en fonction du nombre total de régions internes, de régions externes, et du rapport entre ces deux nombres. En effet, l'inventeur a découvert que le choix de la dimension et/ou du sens de balayage peut influencer la durée de traitement de la forme géométrique, en fonction des facteurs indiqués ci-dessus. Selon des caractéristiques particulières, si la forme géométrique est définie par au moins deux listes ordonnées de sommets définissant au moins deux polygones dont l'un est intégralement inclus dans l'autre, le procédé tel que succinctement exposé ci-dessus comporte une étape de transformation de régions internes en régions externes et vice-versa pour les régions du polygone intégralement inclus dans l'autre. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus comporte, en outre, une étape d'affichage de l'ensemble des formes géométriques simples créées. Cet affichage peut être effectué par une méthode de type ligne de balayage, mais sans aucune utilisation de structure de type table d'arrêtes triés ("TAT"), la forme géométrique ayant déjà été décomposée en formes simples dont on possède la liste sous forme triée dans la dimension et le sens de balayage choisis. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-15 dessus comporte, en outre, une étape de détermination, parmi les sommets, de chaque début de section monotonique pour lequel: soit, d'une part, le sommet précédent dans la liste est strictement en aval dans la direction et le sens de remplissage, et, d'autre part, le premier sommet suivant dans la liste qui n'est pas au même niveau dans la direction et le sens de remplissage est en aval dans la direction et le sens de remplissage, soit, d'une part, le sommet suivant dans la liste est strictement en aval dans la direction et le sens de remplissage, et, d'autre part, le premier sommet précédent dans la liste qui n'est pas au même niveau dans la direction et le sens de remplissage est en aval dans la direction et le sens de remplissage. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus comporte, en outre, une étape de regroupement des sections monotoniques, deux à deux, de telle manière qu'elles définissent une région. Selon des caractéristiques particulières, l'étape de décomposition de ladite forme géométrique met en oeuvre lesdites régions internes et externes. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus comporte une étape de détermination de boîtes englobantes des régions internes et de limitation des régions externes prises en considération pour déterminer les formes géométriques simples relatives à une région interne en fonction de leur abscisse et de celle de la boîte englobante de la région externe considérée. Selon des caractéristiques particulières, lorsque le nombre de régions externes est au moins le double du nombre de régions internes et que le nombre de régions est supérieur à une valeur prédéterminée, on inverse le sens de traitement. Selon un deuxième aspect, la présente invention vise un dispositif de décomposition d'une forme géométrique définie par au moins une liste ordonnée et cyclique de sommets, caractérisé en ce qu'il comporte: - au moins un moyen de recherche de sections monotoniques sur la succession de sommets définie par chaque dite liste ordonnée et des bornes de ces sections, selon au moins une dimension et un sens; - au moins un moyen de regroupement des sections monotoniques deux à deux pour définir des régions de ladite forme géométrique; - au moins un moyen de classification des dites régions en régions "internes" pour lesquelles l'intérieur de la forme est à l'intérieur de la région considérée, et en régions "externes" pour lesquelles l'intérieur de la forme est à l'extérieur de la région considérée; - un moyen de tri des régions externes en fonction de leur coordonnées dans une dimension et un sens et - un moyen de décomposition de la forme géométrique en formes géométriques internes simples, décomposition mettant en oeuvre les régions internes et externes. Les caractéristiques particulières, buts et avantages de ce dispositif étant similaires à ceux du procédé tel que succinctement exposé ci-dessus, ils ne sont pas rappelés ici. Selon un troisième aspect, la présente invention vise une nouvelle méthode de remplissage d'une forme géométrique offrant une solution simple et efficace aux problèmes de qualité et/ou de vitesse, inhérents à toutes les méthodes actuelles. Une image numérique est constituée d'un nombre fini d'unités élémentaires, appelées pixels, qui représentent chacune une portion de l'image dans ses dimensions spatiales horizontales et verticales. Chaque pixel est caractérisé au minimum par une couleur uniforme, et peut contenir d'autres informations (profondeur, opacité, etc...). Dans la suite de ce document, chaque pixel est considéré être de forme carrée, d'arête unitaire. Les images numériques peuvent être acquises par des dispositifs comme les scanners, les appareils photo ou camescopes numériques, mais peuvent aussi être créées directement par des programmes informatiques, par exemple à partir d'informations géométriques saisies par l'utilisateur, ou bien générées automatiquement. Une étape obligatoire est le passage d'une information stockée sous forme vectorielle (continue) à sa représentation numérique (discrète). Cette étape, implémentée dans une caméra sous la forme d'un convertisseur analogique/digital ou ADC, est communément appelée la rastérisation dans le cas de la synthèse d'une image numérique par un ordinateur. La rastérisation consiste simplement à afficher (remplir) au moins une forme géométrique dans une image numérique. Toute méthode de rastérisation d'une forme géométrique peut être décomposée en deux étapes distinctes, répétées au moins une fois pour chaque pixel considéré de l'image numérique: 1 - au moins une étape de calcul d'au moins une information grâce aux données géométriques continues. Dans la suite de ce document, cette étape est appelée "LECTURE". 2 - au moins une étape d'utilisation de cette information pour, optionnellement, calculer au moins une couleur et écrire chaque information de couleur dans au moins un pixel. Dans la suite de ce document, cette étape est appelée "ECRITURE". La technique de rastérisation utilisée par les premiers algorithmes de remplissage de primitives géométriques (cercles, polygones, etc...), souvent appelée en anglais "Uniform Point Sampling" (ou "Echantillonnage Uniforme de Point") peut être décomposée de la façon suivante: Pour chaque pixel caractérisé par ses coordonnées (X, Y) considéré, - LECTURE: On teste si le point aux coordonnées (X + 0,5, Y + 0,5) (correspondant au centre du pixel) est à l'intérieur ou à l'extérieur de la forme géométrique. On calcule une information de type booléenne, avec 2 valeurs possibles: "dedans" ou "dehors" ; - ECRITURE: Si le point est inclus dans la forme géométrique (l'information calculée précédemment vaut "dedans"), la couleur du pixel aux coordonnées (X, Y) est mise à la couleur de la forme géométrique. On considère ci dessus qu'un pixel est un point discret, et non pas un carré d'arête et de surface unitaire. On effectue en fait un échantillonnage de la fonction continue définissant la forme géométrique à une fréquence de 1 par pixel, puis une reconstruction non pondérée des échantillons. Les images synthétisées par cette technique souffrent de nombreux défauts visibles tels que des effets d'escalier, et des trames non désirées. La rastérisation idéale d'une forme géométrique peut être définie mathématiquement comme l'échantillonnage à une fréquence infinie d'une fonction continue (étape de LECTURE), suivi de la reconstruction de cette fonction par convolution des échantillons calculés avec un filtre défini par la fonction "sin(x) / x" et de taille lui aussi infinie (étape d'ECRITURE). Cette approche théorique de la rastérisation fut pour la première fois décrite par F. Crow dans son article "The Aliasing Problem in Computer-Generated Shaded Images (Communications of the ACM, November 1977, Vol. 20, N 11, Pages 799-805). Les méthodes utilisant cette approche d'échantillonnage/reconstruction sont communément appelées "Weighted Area Sampling" (ou "Echantillonnage Pondéré de Surface"). En pratique, il est impossible d'échantillonner une fonction à une fréquence infinie, tout comme il est impossible d'appliquer un filtre de taille infinie aux échantillons calculés. On classifie habituellement les défauts créés par les implémentations de cette méthode de rastérisation en deux grandes catégories, selon leur cause: - Echantillonnage à une fréquence trop faible (non infinie). Les défauts visibles dus à une fréquence d'échantillonnage trop faible sont dans la suite de ce document appelés ALIASING. Ces défauts sont aussi parfois appelés PRE-ALIASING. - Taille du filtre de convolution trop petite (non infinie) ou fonction du filtre de convolution non adaptée. Les défauts visibles dus à une taille de filtre de convolution trop petite, ou à une fonction de filtre de convolution inadaptée sont dans la suite de ce document appelés RASTERING. Ces défauts sont aussi parfois appelés POST-ALIASING. Les défauts d'ALIASING (ou PRE-ALIASING) peuvent être atténués par exemple par un sur-échantillonnage et/ou l'utilisation de techniques stochastiques, et les défauts de RASTERING (ou POST-ALIASING) peuvent être eux aussi atténués par exemple par l'utilisation de formes particulières de filtres (filtre triangulaire, gaussien, t-sinc, etc...), et/ou par l'utilisation d'une taille de filtre de convolution plus grande. Dans la suite de ce document, nous considérons qu'un filtre est caractérisé par sa BASE et sa FORME. Par exemple, un filtre pyramidal (en anglais "tent filter") a une BASE plane carrée et un sommet en dehors du plan de la base. Partant de la remarque que l'échantillonnage d'un fonction à une fréquence infinie correspond en fait à l'intégration dé cette fonction, E. Catmull a proposé dans son article "A Hidden Algorithm With Anti- Aliasing" (Proceeding of SIGGRAPH '78, Atlanta, Georgia, August 23-25, 1978) une méthode de rastérisation appelée à tort "Unweighted Area Sampling" (ou "Echantillonnage non Pondéré de Surface"). Celle-ci consiste à décomposer la forme géométrique en primitives simples inclues dans un et un seul pixel, à calculer l'aire de recouvrement de l'ensemble des primitives inclues dans chaque pixel, puis à écrire la valeur de couleur multipliée par le rapport entre l'aire de recouvrement et l'aire totale d'un pixel. Cette technique peut être décomposée de la façon suivante: Pour chaque pixel caractérisé par ses coordonnées (X, Y) considéré : - LECTURE: On calcule l'aire totale d'intersection entre le carré de coordonnées (X, Y), (X + 1, Y + 1) et la forme géométrique. Ceci est effectué facilement par une décomposition préalable de la forme géométrique en primitives simples telles que des triangles, des trapèzes et des rectangles, toutes inclues dans le pixel considéré, décomposition effectuée grâce, par exemple, à l'utilisation d'un algorithme de "Ligne de Balayage" (Scanline) ; ECRITURE: Si cette aire est non nulle, la couleur de pixel aux coordonnées (X, Y) est mise à la couleur de la forme géométrique multipliée par le rapport entre l'aire d'intersection et l'aire totale d'un pixel. Cette méthode ne souffre d'aucun ALIASING (ou PRE-ALIASING), l'étape de LECTURE étant constituée d'une intégration et non d'un échantillonnage. Cependant, l'étape d'ECRITURE étant non pondérée (pas d'opération équivalente à la convolution par un filtre), la méthode dite d'échantillonnage non pondéré de surface souffre, contrairement aux méthodes d'échantillonnage pondéré de surface, de très forts et très visibles effets de type RASTERING. Le troisième aspect de la présente invention, dont les caractéristiques se combinent avantageusement aux caractéristiques du premier aspect de la présente invention, vise un procédé de remplissage d'une forme géométrique, caractérisé en ce qu'il comporte: - au moins une étape de décomposition de la forme géométrique en primitives graphiques simples, appelées "fragments" et - au moins une étape de calcul de l'aire d'intersection entre chaque fragment et un filtre dont la surface est supérieure à la surface d'un pixel. Ce procédé, que l'on peut appeler "Intégration Pondérée de Pixel", est le premier à posséder les avantages combinés des deux principales techniques actuelles, à savoir: - comme l'échantillonnage non pondéré de surface, il n'y aucune création de défauts d'ALIASING et - comme l'échantillonnage pondéré de surface, il y a atténuation des défauts de RASTERING, en fonction de la forme et de la taille du filtre. Il est important de noter que ce procédé est aussi la première méthode de rastérisation pondérée (avec possibilité d'utilisation d'un filtre de n'importe quelle base et forme), mais sans échantillonnage, puisque basé sur des opérations géométriques exactes telles que intersection, union, addition et d'intégration. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus comporte: - au moins une étape de décomposition de la base d'au moins un filtre en primitives graphiques simples, appelées "portions" ; - au moins une étape de calcul des aires d'intersection entre chaque fragment et chaque portion et - pour chaque pixel, au moins une étape de calcul numérique d'une fonction des aires d'intersection composant la forme du filtre appliquée au pixel, ladite fonction donnant au moins un élément de couleur pour ledit pixel auquel est appliqué ledit filtre. Selon des caractéristiques particulières, au cours de l'étape de décomposition de la base en portions, chaque portion est incluse dans un et un seul pixel. Selon des caractéristiques particulières, au cours de l'étape de décomposition de la forme géométrique en fragments, chaque fragment est inclus dans un et un seul pixel. Selon des caractéristiques particulières, au cours de l'étape de décomposition de la base d'au moins un filtre, les intersections des portions sont vides et leur réunion est égale à ladite base. Selon des caractéristiques particulières, au cours de l'étape de décomposition de la forme géométrique, les intersections des fragments sont vides et leur réunion est égale à ladite forme géométrique. Selon des caractéristiques particulières, au cours de l'étape de calcul numérique, on effectue une étape de pondération des différentes aires. Selon des caractéristiques particulières, au cours de l'étape de pondération, on pondère chaque aire selon une fonction dont la valeur dépend de la distance de ladite intersection au centre du pixel auquel est appliqué ledit filtre. Par exemple, la fonction décroissante est une fonction inverse, c'est à dire, f(d) = z * (dmax - d), où "d" est la distance considérée, "z" une constante quelconque, et "dmax" la valeur maximale que peut prendre d. Selon des caractéristiques particulières, au cours de l'étape de calcul numérique, on effectue une sommation ou addition des aires d'intersection, éventuellement pondérées, composant la forme du filtre appliquée au pixel. Grâce à chacune de ces dispositions, l'étape de calcul numérique est aisée et rapide à mettre en oeuvre. Selon des caractéristiques particulières, l'étape de calcul numérique comporte une étape de multiplication par le rapport entre l'aire du pixel et l'aire totale du filtre. Selon des caractéristiques particulières, au cours de l'étape de décomposition de la base d'un filtre, ledit filtre possède une base rectangulaire dont chaque côté est un multiple du côté correspondant d'un pixel. Grâce à ces dispositions, les différentes étapes du procédé peuvent être plus aisées et rapides à mettre en oeuvre. Selon des caractéristiques particulières, au cours de l'étape de calcul des aires d'intersection, on calcule au moins une première aire d'intersection en mettant en oeuvre au moins un fragment et au moins une portion et on calcule au moins une autre aire d'intersection, pour un autre pixel auquel le même filtre est appliqué, en mettant en oeuvre ladite première aire d'intersection. En effet, l'inventeur a découvert que pour les formes rectangulaires décrites ci-dessus, il existait des relations entre les aires d'intersection. Par exemple, pour une base rectangulaire qui correspond à quatre pixels (2 x 2) s'étendant sur neuf pixels autour du pixel auquel le filtre est appliqué, pour chaque colonne ou chaque ligne, les sommes des aires extrêmes sont égales à l'aire centrale (le calcul de 4 aires permet le calcul des 9 aires). Par exemple pour une base rectangulaire qui correspond à neuf pixels (3 x 3) s'étendant sur neuf pixels autour du pixel auquel le filtre est appliqué, pour chaque colonne ou chaque ligne, les aires extrêmes sont chacune égales à l'aire centrale. Selon des caractéristiques particulières, au cours de l'étape de calcul numérique, on pondère la couleur par un filtre. On observe que ledit filtre peut être, par exemple, gaussien, sinusoïdal, etc... A cet effet, il suffit de calculer le centre de gravité de l'intersection entre chaque fragment et chaque portion, puis la distance entre ce centre de gravité et le centre du pixel auquel le filtre est appliqué. Selon des caractéristiques particulières, la forme du filtre est une intégrale d'une forme polygonale. Selon des caractéristiques particulières, le procédé tel que succinctement exposé ci-dessus est effectué successivement pour des pixels successifs sur une même ligne, en traitant successivement les lignes successives de l'image à constituer. Cette technique dite de Scanline (ou "Ligne de Balayage") permet de réduire le nombre de calculs nécessaires pour implémenter le procédé objet de la présente invention puisque les calculs de portions, de fragments ou d'aires d'intersection effectuées pour un pixel peuvent être, au moins partiellement réutilisés pour au moins un pixel se trouvant à proximité du pixel considéré. Selon un quatrième aspect, dont les caractéristiques se combinent avantageusement aux caractéristiques du deuxième aspect de la présente invention, la présente invention vise un dispositif de rastérisation d'une forme géométrique, caractérisée en ce qu'il comporte: - au moins un moyen de décomposition de la forme géométrique en primitives graphiques simples, appelées "fragments" et - au moins un moyen de calcul de l'aire d'intersection entre chaque fragment et un filtre dont la surface est supérieuré à la surface d'un pixel. Les avantages, buts et caractéristiques du quatrième aspect de la présente invention étant similaires à ceux du troisième aspect de la présente invention, ils ne sont pas rappelés ici. D'autres avantages, buts et caractéristiques de la présente invention ressortiront de la description qui va suivre, faite dans un but explicatif et nullement limitatif en regard des dessins annexés dans lesquels: - la figure 1 représente un dispositif conforme à un aspect de la présente invention, - la figure 2 représentent une succession d'étapes mises en oeuvre dans un mode de réalisation particulier du procédé objet de la présente invention, - la figure 3 représente une succession d'étapes réalisant l'une des étapes illustrées en figure 2, - la figure 4 représente une succession d'étapes réalisant l'une des étapes illustrées en figure 2, - la figure 5 représente une succession d'étapes réalisant l'une des étapes illustrées en figure 2, - les figures 6A, 6B et 6C représentent une succession d'étapes réalisant l'une des étapes illustrées en figure 2, - la figure 7 représente un polygone particulier, - la figure 8 représente des coordonnées de pixels et une décomposition d'une forme géométrique en fragments dans un mode particulier de réalisation du procédé objet du deuxième aspect de la présente invention, - la figure 9 représente neuf pixels particuliers représentés en figure 8, - la figure 10 représente neuf portions d'un filtre de base carrée de dimension deux pixels sur deux appliquée au pixel central illustré en figure 8 ainsi qu'une partie de la forme géométrique considérée correspondant audit filtre, - la figure 11 représente, pour un fragment en forme de trapèze du pixel central illustré en figure 9, les aires d'intersection des neuf portions de filtre s'étendant sur le pixel central illustré en figure 9 avec ce fragment en forme de trapèze avec la convention que l'on a représenté en haut à gauche, l'intersection avec la portion en bas à droite, - la figure 12 représente, pour un fragment en forme de rectangle du pixel central illustré en figure 9, les aires d'intersection des neuf portions de filtre s'étendant sur le pixel central illustré en figure 8 avec ce fragment en forme de rectangle avec la même convention que pour la figure 10, - la figure 13 représente l'addition des aires représentées en figures 11 et 12, - la figure 14 représente, pour chaque pixel dont le filtre appliqué s'étend sur le pixel central illustré en figure 8, les différentes aires d'intersection non vides des fragments et des portions qui s'étendent sur ledit pixel central, - la figure 15 représente neuf aires d'intersection des portions de filtre illustrées en figure 9 et de la forme géométrique considérée pour synthétiser la couleur du pixel central illustré en figure 8, - la figure 16 représente un logigramme d'étapes mises en oeuvre dans un mode particulier de réalisation du procédé objet du troisième aspect de la présente invention et 20 - la figure 17 représente, schématiquement, la constitution d'un filtre particulier. Dans toute la description, on utilise les définitions suivantes: "polygone simple" : un polygone défini par une liste de sommets et ne comportant aucune intersection entre les segments reliant ces sommets; "polygone composite" : un polygone défini par au moins une liste de sommets et ne 25 comportant aucune intersection entre les segments reliant ces sommets; - "polygone quelconque" : un polygone défini par au moins une liste de sommets et pouvant comporter des intersections entre les segments reliant ces sommets. Dans la description, on ne décrit que le traitement des polygones simples et des polygones composites, étant entendu que la présente invention n'est pas limitée à ces types particuliers de polygones. Dans la description, on décrit d'abord au moins un mode particulier de réalisation du procédé objet du premier aspect de la présente invention (figures 1 à 7) puis un mode particulier de réalisation du procédé objet du troisième aspect de la présente invention (figures 8 à 16) avant de décrire des combinaisons avantageuses des différents aspects de la présente invention. Pour définir une image de synthèse, on décompose traditionnellement cette image en polygones. Dans la suite de la description, on décrit le remplissage de l'un de ces polygones, les autres polygones étant traités de la même manière que décrit ci-dessous ou d'une autre manière, selon leur complexité définie, par exemple, par le nombre de sommets (le procédé décrit ci-dessous étant employé lorsque le nombre de sommets est supérieur à un nombre prédéterminé. On définit un polygone par une liste de sommets par lesquels le périmètre passe successivement. Sur ce périmètre, le sommet précédent le premier sommet de la liste est le dernier sommet de la liste. Chaque sommet est défini par une abscisse "x" et une ordonnée "y". Traditionnellement, l'origine de l'abscisse et de l'ordonnée sont au coin en bas à gauche de l'image (ou de l'afficheur). Dans toute la description, on appelle polygone "y-monotone" un polygone monotone dans sa dimension verticale, "y". On définit une section monotonique comme un chemin passant par des sommets successifs du polygone entre un sommet "le plus bas" (sommet dont le sommet voisin qui n'est pas dans la section monotonique possède une ordonnée "y" supérieure ou égale à la sienne et, en cas d'égalité, le sommet suivant possède une ordonnée "y" supérieure ou égale à la sienne et, ainsi de suite) et un sommet le plus haut (sommet dont le sommet voisin qui n'est pas dans la section monotonique possède une ordonnée "y" inférieure ou égale à la sienne et, en cas d'égalité, le sommet suivant possède une ordonnée "y" inférieure ou égale à la sienne et, ainsi de suite). Le terme suivant, le sommet A est "en dessous" du sommet B, signifie que l'ordonnée du sommet A est strictement inférieure à l'ordonnée du sommet B. Respectivement, le terme "au dessus" signifie que l'ordonnée du premier est strictement supérieure à l'ordonnée du second. On définit un sens de parcours du périmètre du polygone, positif ou négatif, correspondant, dans la littérature technique aux termes "dans le sens des aiguilles d'une montre" (en anglais clockwise ou CW) et "dans le sens inverse des aiguilles d'une montre" (en anglais conterclockwise ou CCW). On observe, en figure 1, un ordinateur 50 comportant une mémoire volatile 51, une mémoire non volatile 52, un processeur 53, un écran d'affichage 54, un clavier 55, un dispositif de pointage 56, une mémoire d'image 57 et un moyen de sortie de données 58. L'ordinateur 50 est de type connu, par exemple un PC (pour "personal computer" ou ordinateur personnel). La mémoire non volatile 52 conserve un programme d'ordinateur permettant au processeur 53 d'implémenter les étapes du procédé illustrées en figures 2A, 2B et 3. La mémoire d'image 57 conserve une représentation point par point de l'image à afficher sur l'écran d'affichage 54 ou à transmettre par le moyen de sortie de données 58. Le moyen de sortie de données peut être une interface pour transmission à distance, par exemple un modem, une carte réseau ou un support de données non volatile, par exemple un compact dise numérique. Le processeur 53, la mémoire non volatile 52, la mémoire volatile 51, le moyen de sortie de données 58 et le mémoire d'image 57 constituent, conjointement les moyens caractéristiques du dispositif d'affichage d'images objet de la présente invention comportant un moyen de sortie d'un signal représentatif d'une image et des moyens de traitement adaptés, pour décomposer une forme géométrique définie par au moins une liste ordonnée et cyclique de sommets, à effectuer: - au moins une étape de recherche de sections monotoniques sur la succession de sommets définie par chaque dite liste ordonnée et des bornes de ces sections, selon au moins une dimension et un sens; - au moins une étape de regroupement des sections monotoniques deux à deux pour définir des régions de ladite forme géométrique; - au moins une étape de classification des dites régions en régions "internes" pour lesquelles l'intérieur de la forme est à l'intérieur de la région considérée, et en régions "externes" pour lesquelles l'intérieur de la forme est à l'extérieur de la région considérée; - une étape de tri des régions externes en fonction de leur coordonnées dans une dimension et un sens; - une étape de décomposition de la forme géométrique en formes géométriques internes simples, décomposition mettant en oeuvre les régions internes et externes. On observe, en figure 2, des étapes mises en oeuvre dans un mode de réalisation particulier du procédé objet de la présente invention. Au cours d'une étape 200, on définit une direction et un sens de remplissage de polygones, par exemple, par défaut ou implicitement, de bas en haut, c'est-à-dire ligne horizontale par ligne horizontale, dans le sens des ordonnées croissantes. Au cours d'une étape 205, on détermine un sommet de départ, comme indiqué en figure 3, que l'on décrit ci-après. Pour la concision de la description, pour la description de la figure 3, on utilise les notations suivantes: - "SC" désigne le sommet courant, "SD" désigne le sommet de départ qui est déterminé selon le logigramme illustré en figure 3, - "SX.Y" désigne l'ordonnée du sommet SX (X prenant toutes les valeurs numériques possibles pour définir les sommets de la liste des sommets qui définissent le polygone) , - "#SS(SX)" désigne le sommet suivant le sommet "SX" et - #ROUTE(SMIN,SMAX,SENS) crée une section monotonique avec SMIN et SMAX comme extrémités de section monotonique et SENS comme sens. Au cours d'une étape 305, on définit comme sommet courant "SC" le premier sommet nommé SO de la liste des sommets définissant le polygone, et on définit comme sommet de départ SD provisoire le sommet courant SC. Au cours d'une étape 310, on définit comme nouveau sommet courant le sommet suivant le précédent sommet courant. Au cours d'une étape 315, on détermine si le sommet courant est le sommet SO, c'est-à-dire le premier sommet de la liste des sommets définissant le polygone et aussi le sommet suivant le dernier sommet de cette liste. Si le résultat de l'étape 315 est négatif, au cours d'une étape 320, on détermine si l'ordonnée du sommet courant est inférieure ou égale à l'ordonnée du sommet de départ provisoire. Si le résultat de l'étape 320 est négatif, on réitère l'étape 310 et les étapes suivantes. Si le résultat de l'étape 320 est positif, au cours d'une étape 325, on définit comme nouveau sommet de départ provisoire, le sommet courant et on réitère l'étape 310 et les suivantes. Si le résultat de l'étape 315 est positif, c'est-à-dire si le sommet courant est le sommet SO, au cours d'une étape 330, on définit comme sommet courant le sommet de départ provisoire. Puis, au cours d'une étape 335, on définit comme nouveau sommet courant le sommet suivant le précédent sommet courant dans la liste des sommets définissant le polygone. Au cours d'une étape 340, on détermine si l'ordonnée du sommet courant est égale à l'ordonnée du sommet de départ provisoire. Si oui, au cours d'une étape 345, on définit comme nouveau sommet de départ, le sommet courant et on réitère l'étape 335 et les suivantes. Lorsque le résultat de l'étape 340 est négatif, on passe à l'étape 210, figure 2. On observe qu'à la suite de l'étape 205, on a trouvé un sommet de départ qui fait partie des sommets les plus bas du polygone et dont le sommet suivant possède une ordonnée strictement supérieure à celle du sommet de départ. Au cours d'une étape 210, on détermine toutes les sections monotoniques du polygone, selon le logigramme illustré en figure 4. Pour la description de la figure 4, on utilise les notations suivantes: - "SD" désigne le sommet de départ, - "SMIN" désigne un sommet début de section monotonique. - "SMAX" désigne un sommet fin de section monotonique, - "#SS(SX)" désigne le sommet suivant le sommet "SX", - "SENS" désigne le sens courant (le sens est positif, +1, lorsqu'il correspond à une croissance des ordonnées et négatif, -1,lorsqu'il correspond à une décroissance des ordonnées), "SS" désigne le sommet suivant et - "SC" désigne le sommet courant. En figure 4, on observe une étape 405 au cours de laquelle on définit comme sommet début de section monotonique le sommet de départ, comme sommet suivant le sommet de 2865564 14 départ, et comme sens courant, le sens positif. Au cours d'une étape 410, on définit comme sommet courant, le sommet suivant, et comme nouveau sommet suivant le sommet qui succède au précédant sommet suivant, dans la liste circulaire des sommets définissant le polygone. Au cours d'une étape 415, on détermine si le sens courant est le sens positif ou le sens négatif. Si le sens courant est le sens positif, au cours d'une étape 420, on détermine si l'ordonnée du sommet suivant est strictement inférieure à l'ordonnée du sommet courant. Si oui, au cours d'une étape 425, on crée une section monotonique dans un tableau de sections monotoniques et on lui donne les attributs suivants: SMIN, SMAX et SENS. Puis, au cours d'une étape 430, on passe le sens courant au sens négatif, le SMIN à SS et le SMAX à SC, puis on réitère l'étape 410 et les suivantes. Si le résultat de l'étape 420 est négatif, au cours d'une étape 435, on détermine si l'ordonnée du sommet suivant est strictement supérieure à l'ordonnée du sommet courant. Si non, on réitère l'étape 410 et les suivantes. Si oui, au cours d'une étape 440, on définit SMAX comme étant le sommet suivant et on réitère l'étape 410 et les suivantes. Si au cours de l'étape 415, on détermine que le sens courant est le sens négatif, au cours d'une étape 445, on détermine si l'ordonnée du sommet suivant est strictement supérieure à l'ordonnée du sommet courant. Si oui, au cours d'une étape 450, on crée une section monotonique dans un tableau de sections monotoniques et on lui donne les attributs suivants: SMIN, SMAX et SENS. Puis, au cours d'une étape 455, on détermine si le sommet est le sommet de départ. Si non, au cours d'une étape 460, on passe le sens courant au sens positif, le SMIN à SC et le SMAX à SS, puis on réitère l'étape 410 et les suivantes. Si le résultat de l'étape 455 est positif, on passe à l'étape 215 (voir figure 2). Si le résultat de l'étape 445 est négatif, au cours d'une étape 465, on détermine si l'ordonnée du sommet suivant est strictement inférieure à l'ordonnée du sommet courant. Si non, on réitère l'étape 410 et les suivantes. Si oui, au cours d'une étape 470, on définit SMIN comme étant le sommet suivant et on réitère l'étape 410 et les suivantes. On observe qu'à la suite de l'étape 205, toutes les sections monotoniques du polygone ont été trouvées et inscrites dans le tableau des sections monotoniques, qui 30 comporte, pour chaque section monotonique, les informations suivantes: - sommet début de section monotonique "SMIN", sommet fin de section monotonique "SMAX", - "YCUR", l'ordonnée courante, "XCUR", l'abscisse courante, - "SENS", le sens de parcours (positif, si le sommet le plus bas est avant le sommet le plus haut dans la liste des sommets qui définissent le polygone, sinon négatif), - pointeur sur la section monotonique suivante "NEXT", - pointeur sur la section monotonique "PREV" et - drapeau "DONE" (mis à la valeur "faux" par défaut, qui indique si la section monotonique a déjà été entièrement exploitée pour la décomposition et éventuellement le remplissage du polygone (voir plus loin). Par exemple, pour le polygone illustré en figure 7, la table des sections monotoniques comporte les sections monotoniques suivantes: no. de début de fin de sens section suivante section précédente section section section 0 5 6 positif 1 5 1 7 6 négatif 2 0 2 7 10 positif 3 1 3 12 11 négatif 4 2 4 13 14 positif 5 3 4 14 négatif 0 4 Au cours de l'étape 215, on détermine le sens du polygone (voir étapes 505 et 510, figure 5). Au cours d'une étape 220, on détermine les régions et les classifie en régions internes, pour lesquelles l'intérieur du polygone est entre les deux sections monotoniques définissant la région, et régions externes, pour lesquelles l'intérieur du polygone est à l'extérieur des deux sections monotoniques définissant la région, selon le logigramme illustré en figure 5, à partir de la fin de l'étape 510. Pour la description de la figure 5, on utilise les notations suivantes: - "#SECSORDER(Paraml, Param2)" est une fonction qui retourne la valeur "1" si la première section monotonique (Param 1) est à gauche de la deuxième section monotonique (Param2) et retourne la valeur "0" si la première section monotonique (Param 1) est à droite de la deuxième section monotonique (Param2) ; - "#NEWINTERNAL(Paraml, Param2)" est une fonction qui rajoute une région à la liste des régions internes, avec le premier paramètre (Param1) comme section monotonique gauche et le deuxième paramètre (Param2) comme section monotonique droite; - "#NEWEXTERNAL(Paraml, Param2)" est une fonction qui rajoute une région externe à la liste des régions externes, avec le premier paramètre (Param1) comme section monotonique gauche et le deuxième paramètre (Param2) comme section monotonique droite; - "#NEXT(Param)" est une fonction qui retourne la section monotonique suivante de la section monotonique passée en paramètre (Param) ; - "#NEXT2SECS(Param)" est une fonction qui retourne les deux sections monotoniques suivants la section Param, en valeurs SECO et SEC1 et incrémente de deux (prendre le suivant du suivant) la valeur de PTRSEC; - "PTRBASE" est un pointeur sur une section monotonique; - "PTRSEC" est un pointeur sur une section monotonique, pointant initialement sur la 5 dernière section monotonique créée lors de l'étape 210 et - "ORDERBASE" et "ORDER" sont des variables prenant les valeurs numériques "0" ou "1". En figure 5, on observe une étape 505 au cours de laquelle on attribue à PTRBASE la valeur PTRSEC, on effectue la fonction #NEXT2SECS(PTRSEC) et on attribue à ORDERBASE la valeur issue de la fonction #SECSORDER(SECO, SEC1). Au cours d'une étape 510, on détermine si ORDERBASE vaut "1". Si oui, au cours d'une étape 515, on effectue la fonction #NEWINTERNAL(SECO, SEC1). Sinon, au cours d'une étape 520, on effectue la fonction (#NEWINTERNAL(SEC1, SECO). On observe que l'étape 510 revient à déterminer le sens du polygone: - si ORDERBASE vaut "1", le sens du polygone est dans le sens inverse des aiguilles d'une montre; - si ORDERBASE vaut "0", le sens du polygone est dans le sens des aiguilles d'une montre. A la suite de l'une ou l'autre des étapes 515 et 520, au cours d'une étape 525, on détermine si PTRSEC vaut PRTBASE. Si oui, l'étape 220 est achevée. Sinon, au cours d'une étape 530, on effectue la fonction #NEXT2SECS(PTRSEC) et on attribue à la variable ORDER la valeur de la fonction #SECSORDER(SECO, SEC1). Puis, au cours d'une étape 535, on détermine si la variable ORDER prend la valeur de ORDERBASE. Si oui, au cours d'une étape 540, on détermine si la variable ORDER prend la valeur "1". Si oui, au cours d'une étape 545, on effectue la fonction #NEWINTERNAL(SECO, SEC1) et on retourne à l'étape 525. Sinon, au cours d'une étape 550, on effectue la fonction #NEWINTERNAL(SEC1, SECO) et on retourne à l'étape 525. Si le résultat de l'étape 535 est négatif, au cours d'une étape 555, on détermine si la variable ORDER prend la valeur "1". Si oui, au cours d'une étape 560, on effectue la fonction #NEWEXTERNAL(SECO, SEC1) et on retourne à l'étape 525. Sinon, au cours d'une étape 565, on effectue la fonction #NEWEXTERNAL(SEC1, SECO) et on retourne à l'étape 525. A la suite de l'étape 220, on dispose de la table des régions internes, qui contient pour chaque région les informations suivantes: - section mononotique gauche, - section monotonique droite, - ordonnée de départ de la région; et la table des régions externes, qui contient pour chaque région les informations suivantes: - section mononotique gauche, - section monotonique droite, - ordonnée de départ de la région; Par exemple, pour le polygone illustré en figure 7, les 6 sections monotoniques déterminent 3 régions, dont 2 sont des régions internes et 1 est une région externe. Les 2 régions internes créées ont les couples de sections monotoniques suivants: no. de région section gauche section droite 0 0 5 1 2 1 La région externe créée a les couples de sections monotoniques suivants: no. de région section gauche section droite 0 3 4 Au cours d'une étape 225, on trie les régions externes par ordre des ordonnées croissantes. En variante, au cours de cette étape de tri, on trie aussi les régions internes pour gagner du temps dans leur utilisation. Au cours d'une étape 230, on décompose le polygone en polygones ymonotones, et, éventuellement, on remplit le polygone. A cet effet, on met en oeuvre le logigramme illustré en figures 6A à 6C. Pour la description des figures 6A à 6C, on utilise les notations suivantes: - "NSTART" désigne le nombre de régions internes restant à traiter, - "NSPLIT" désigne le nombre de régions externes restant à traiter, - "NTEMP" désigne le nombre de pointeurs dans une pile temporaire appelée "TEMP", de type LIFO, pointeurs sur des polygones y-monotones, "YM" désigne un pointeur sur un polygone y-monotone définit par YMIN, son ordonnée minimum (ou de début), YMAX, son ordonnée maximum (ou de fin) , une section monotonique gauche RG et une section monotonique droite RD, "RG" désigne une section monotonique gauche (les points immédiatement à gauche de cette section monotonique sont en dehors du polygone et les points immédiatement à 30 droite de cette section monotonique sont dans le polygone), - "RD" désigne une section monotonique droite (les points immédiatement à droite de cette section monotonique sont en dehors du polygone et les points immédiatement à gauche de cette section monotonique sont dans le polygone), - "RM" un pointeur temporaire de section monotonique utilisé pour les tests de fusion, - "RG.SMAX.Y" l'ordonnée de SMAX pour la section monotonique gauche, - "RD.SMAX.Y" l'ordonnée de SMAX pour la section monotonique droite, - "DG" est un drapeau (lié à la section monotonique gauche), - "DD" est un drapeau (lié à la section monotonique droite), - "GSPLIT" est un pointeur sur la région externe courante, - "#GS1(Y, YMAX)" est la première région externe dont l'ordonnée est supérieure ou égale à l'ordonnée courante Y sur les sections monotoniques gauche et droite et dont l'ordonnée est strictement inférieure au YMAX courant, - "#GSN(GSPLIT, YMAX)" est la région externe suivant la région externe courante GSPLIT dont l'ordonnée est supérieure ou égale à l'ordonnée courante sur les sections monotoniques gauche et droite et dont l'ordonnée est strictement inférieure au YMAX courant, "#GST(RG, RD, GSPLIT)" est le résultat d'un test si la région externe courante GSPLIT coupe, c'est-à-dire se trouve entre, les sections monotoniques droites et gauche pour l'ordonnée courante, ce résultat prenant la valeur zéro s'il est négatif et la valeur 1 s'il est positif, "#RU(RG, RD, Y)" désigne la fonction de mettre à jour les sections monotoniques gauche et droite pour une ordonnée Y donnée, c'est-à-dire met YCUR à l'ordonnée courante et calcule l'abscisse correspondante pour que XCUR prenne cette valeur calculée, - "#PUSH(RG, RD)" désigne la fonction de créer un nouveau polygone y- monotone avec comme attributs RG comme section monotonique gauche et RD comme section monotonique droite, et de stocker un pointeur sur ce polygone dans la pile TEMP, - "#POP()" désigne la fonction qui supprime le pointeur le plus récente dans la pile TEMP et - "#GSR(GSPLIT)" est la fonction qui supprime la région externe de la liste des régions externes. Au cours d'une étape 605 (figure 6A), on définit NTEMP comme étant nul, NSPLIT prend la valeur du nombre de régions externes et NSTART prend la valeur du nombre de régions internes. Au cours d'une étape 610, on détermine si NTEMP est strictement supérieur à zéro. Si oui, au cours d'une étape 615, on définit YM comme le contenu de la pile TEMP, on décrémente NTEMP, on effectue la fonction #POPO et on passe à l'étape 630. Si le résultat de l'étape 610 est négatif, au cours d'une étape 620, on détermine si le nombre NSTART est strictement supérieur à zéro. Sinon, le processus est terminé. Si oui, au cours d'une étape 625, on crée un polygone y-monotone dans un tableau de polygones y-monotones et on lui attribue YMIN qui est l'ordonnée courante comme ordonnée de départ et les section monotoniques gauche et droite de la région interne suivante dans la liste des régions internes, on met le pointeur YM à la valeur d'un pointeur pointant sur cette région interne, on décrémente NSTART puis on effectue l'étape 630 au cours de laquelle, pour le polygone y-monotone, RG prend la valeur d'un pointeur sur la section monotonique gauche de la région interne et RD prend la valeur d'un pointeur sur la section monotonique droite de la région interne. Au cours d'un test 635, on détermine la valeur de RG.SMAX.Y - RD.SMAX.Y, le premier terme désignant l'ordonnée de SMAX pour la section monotonique gauche et le deuxième terme désignant l'ordonnée de SMAX pour la section monotonique droite. Si cette valeur est strictement négative, on effectue l'étape 640. Si elle est nulle, on effectue l'étape 645. Si elle est strictement positive, on effectue l'étape 650. Au cours de l'étape 640, on met le drapeau gauche DG à la valeur 1, le drapeau droit DD à la valeur zéro et YMAX prend la valeur RG.SMAX.Y. Au cours de l'étape 645, on met le drapeau gauche DG à la valeur 1, le drapeau droit DD à la valeur 1 et YMAX prend la valeur RG.SMAX.Y. Au cours de l'étape 650, on met le drapeau gauche DG à la valeur zéro, le drapeau droit DD à la valeur 1 et YMAX prend la valeur RD.SMAX.Y. A la suite de l'une quelconque des étapes 640, 645 et 650, au cours d'une étape 655, on détermine si le nombre NSPLIT de régions externes restant à traiter est strictement positif. Sinon, au cours d'une étape 660, on met GSPLIT à la valeur zéro qui signifie qu'il n'y a plus de split à traiter. Si le résultat de l'étape 655 est positif, au cours d'une étape 665, on met GSPLIT à la valeur #GS1(Y,YMAX), qui peut prendre la valeur "0" s'il n'y a pas de région externe répondant au critère de recherche. Au cours d'une étape 670 (figure 6B), on détermine si GSPLIT est différent de zéro. Si oui, au cours d'une étape 675, on met à jour les sections monotoniques droite et gauche avec l'ordonnée de GSPLIT. Puis, au cours d'une étape 680, on détermine si #GST(RG, RD, GSPLIT) vaut 1, c'est-à-dire si la région externe GSPLIT se trouve entre les sections monotoniques RG et RD. Si non, au cours d'une étape 685, GSPLIT prend la valeur #GSN(GSPLIT, YMAX) puis on réitère l'étape 670 et les suivantes. Si le résultat de l'étape 680 est positif, au cours d'une étape 690, on crée deux nouveaux polygones y-monotones avec, respectivement RG et la section monotonique gauche de GSPLIT, d'une part et la section monotonique droite de GSPLIT et RD, d'autre part, et on stocke dans la pile TEMP, deux pointeurs sur ces polygones, on incrémente de deux NTEMP, on supprime la région externe GSPLIT de la liste des régions externes et on ferme le polygone y-monotone YM courant, c'est-à-dire que l'on attribue à sa variable YMAX, l'ordonnée courante, puis on réitère l'étape 610 et les suivantes. Si le résultat de l'étape 670 est négatif, au cours d'une étape 695, on met à jour les sections monotoniques droite et gauche avec l'ordonnée YMAX. Au cours d'une étape 700, on détermine si le drapeau gauche est égal à 1. Si oui, au cours d'une étape 705, on met le pointeur de la section monotonique gauche du polygone y-monotone courant à la valeur du pointeur sur le polygone y-monotone courant, on met le drapeau DG de la section monotonique gauche à "1". A la suite de l'étape 705 ou si le résultat de l'étape 700 est négatif, au cours d'une étape 710, on détermine si le drapeau droit est égal à 1. Si oui, au cours d'une étape 715, on met le pointeur de la section monotonique droite du polygone y- monotone courant à la valeur du pointeur sur le polygone y-monotone courant, on met le drapeau DD de la section monotonique droite à "1". A la suite de l'étape 715 ou si le résultat de l'étape 710 est négatif, au cours d'une 5 étape 720 (figure 6C), on détermine si le drapeau gauche DG est égal à 1. Si oui, au cours d'une étape 725, on détermine si le sens de la section monotonique gauche RG.SENS est positif. Si oui, au cours d'une étape 730, on met la variable RM, section monotonique de fusion, à la valeur RG.NEXT, c'est-à-dire la valeur du pointeur sur la section monotonique suivant la section monotonique gauche. Sinon, au cours d'une étape 735, on met la variable RM, section monotonique de fusion, à la valeur RG. PREV, c'est-à-dire la valeur du pointeur sur la section monotonique précédent la section monotonique gauche. A la suite de l'une des étapes 730 ou 735, au cours d'une étape 740, on ferme le polygone y-monotone, en définissante son YMAX. Puis, au cours d'une étape 745, on détermine si la variable RM est égal à la section monotonique droite. Si oui, on réitère l'étape 610 et les étapes suivantes. Sinon, au cours d'une étape 750, on détermine si le drapeau DONE de la section monotonique RM est égal à 1. Si oui, au cours d'une étape 755, on crée un nouveau polygone y-monotone et on lui attribut comme section monotonique gauche, la section monotonique gauche du polygone pointé par la section monotonique de fusion, RM.YM.RG, et, comme section monotonique droite la section monotonique droite RD courante et on incrémente le compteur NTEMP. A la suite de l'étape 755 ou si le résultat de l'étape 750 est négatif, on réitère l'étape 610 et les étapes suivantes. Si le résultat de l'étape 720 est négatif, au cours d'une étape 760, on détermine si le sens de la section monotonique droite RD.SENS est positif. Si oui, au cours d'une étape 765, on met la variable RM, section monotonique de fusion, à la valeur RD.NEXT, c'est-à-dire la valeur du pointeur sur la section monotonique suivant la section monotonique droite. Sinon, au cours d'une étape 770, on met la variable RM, section monotonique de fusion, à la valeur RD.PREV, c'est-à-dire la valeur du pointeur sur la section monotonique précédent la section monotonique droite. A la suite de l'une des étapes 765 ou 770, au cours d'une étape 775, on ferme le polygone y-monotone, en définissante son YMAX. Puis, au cours d'une étape 780, on détermine si la variable RM est égal à la section monotonique gauche. Si oui, on réitère l'étape 610 et les étapes suivantes. Sinon, au cours d'une étape 785, on détermine si le drapeau DONE de la section monotonique RM est égal à 1. Si oui, au cours d'une étape 790, on crée un nouveau polygone y-monotone et on lui attribut comme section monotonique gauche, la section monotonique gauche courante et comme section monotonique droite, la section monotonique droite du polygone pointé par la section monotonique de fusion, RM.YM.RD et on incrémente le compteur NTEMP. A la suite de l'étape 790 ou si le résultat de l'étape 785 est négatif, on réitère l'étape 610 et les étapes suivantes. Grâce à la mise en oeuvre du logigramme illustré aux figures 2 à 6C, le polygone initial est décomposé en polygones y-monotones, chaque polygone y-monotone étant défini par une section monotonique gauche, une section monotonique droite, une ordonnée minimale et une ordonnée maximale. On décompose ainsi une forme géométrique complexe en un graphe ordonné de formes géométriques plus simples (ici, y-monotone). Dans des variantes, on effectue une décomposition en triangles ou en trapézes. On observe que le nombre de polygones "y-monotones" créés est au maximum égal à un de moins que le double de la somme du nombre de régions internes et du nombre de régions externes. On observe que certains polygones "y-monotones" créés comme indiqué cidessus ont une hauteur nulle mais qu'ils ont, au plus, deux prédécesseurs (c'est-à-dire que leur côté inférieur touche au plus deux autres polygones "y-monotones" dans le polygone traité) et deux successeurs (c'est-à-dire que leur côté supérieur touche au plus deux autres polygones "y-monotones" dans le polygone traité). En variante, le remplissage du polygone est effectué au cours de chacune des étapes 675 et 695. On observe que le temps de traitement des étapes 200 à 220 est sensiblement proportionnel aux nombres des sommets du polygone à décomposer. En revanche, la durée de l'étape 225 est en moyenne proportionnelle au nombre de régions externes multiplié par le logarithme de ce nombre, et la durée de l'étape 230 est, en pratique, sensiblement une fonction du nombre de sommets splits. En variante, pour réduire le temps de traitement total, si le nombre de sommets splits est supérieur d'un nombre prédéterminé au nombre des starts ou si le nombre de sommets splits est un nombre prédéterminé de fois supérieur au. nombre de sommets starts, on traite le polygone de haut en bas (remplissage des polygones "y-monotones" par ordonnées décroissantes) et non, comme indiqué ci-dessus, de bas en haut (remplissage des polygones "y-monotones" par ordre des ordonnées croissantes). Dans un mode préféré de réalisation, pendant la détermination des sections monotoniques, on crée les boîtes englobantes (en anglais "bounding-box") de chaque section monotonique et, au cours des étape 665 et 685, on se limite aux régions externes dont les deux abscisses sont entre les abscisses extrêmes des boîtes englobantes des deux sections monotoniques considérées. Dans le cas d'un polygone dit "externe" entourant au moins un autre polygone, dit "interne", on effectue les mêmes étapes de détermination des régions internes et des régions externes qu'exposé ci-dessus puis avant d'effectuer l'étape 225, les régions externes de chaque polygone interne sont considérés comme des régions internes du polygone externe et les régions internes de chaque polygone interne sont considérés comme des régions externes du polygone externe. Le tableau ci-dessous donne une comparaison de la durée de décomposition et remplissage (en millisecondes) de polygones "massivement" concaves pour la méthode décrite dans le document Gordon cité en préambule et pour la méthode objet de la présente invention, sur le même ordinateur: 15 20 On observe que plus le polygone massivement concave comporte de sommets, plus le gain de temps est élevé. Ceci est du en partie au fait que la seule opération de tri nécessaire ne s'effectue que sur les régions externes. Les régions internes sont traitées dans un ordre quelconque lors de l'étape 230, ce qui évite tout tri des régions internes... De plus, contrairement aux méthodes de décomposition de type Scanline, la décomposition de la forme géométrique en formes simples (y-monotones) est effectuée une seule fois au cours d'une première phase et le remplissage est effectué au cours d'une deuxième phase, ce qui permet de gagner du temps de traitement. Avant de décrire un mode particulier de réalisation du procédé objet du troisième aspect de la présente invention, en regard des figures 8 à 16, on précise que l'on a considéré, dans cette description, que les pixels de l'image à synthétiser sont carrés que la base du filtre que l'on applique à chaque pixel est carré avec un côté égal à un multiple entier du côté du pixel, ce dernier côté étant considéré comme unitaire, pour la simplification de la description. Chaque pixel étant repéré par les abscisses et ordonnées de son coin en bas à gauche, le pixel le plus en bas et le plus à gauche a pour coordonnées (0,0), le nombre de points durée "Gordon" durée présente invention ratio de gain 4000 420 330 1,3 5000 720 390 1,8 6000 1300 460 2,8 7000 1800 550 3,3 8000 2500 630 4,0 9000 3900 760 5,1 10000 5300 890 6,0 15000 16000 1800 8,9 20000 33000 3300 10,0 25000 60000 5200 11,5 30000 96000 7900 12,2 35000 140000 11000 12,7 40000 205000 14000 14,6 suivant, à droite, sur la même ligne a pour coordonnées (1,0), le suivant, au dessus du pixel (0,0) a pour coordonnées (0,1) et ainsi de suite. Dans cette description, on a représenté qu'une forme géométrique noire sur fond blanc (en figures 8 et 9, seuls les contours de cette forme et de ses fragments sont représentés), la présente invention s'appliquant, de la même manière pour des formes géométriques possédant des grisés ou des couleurs, par exemple représentées en rouge, vert et bleu avec, éventuellement des variations de ces couleurs sur l'étendue de chaque forme géométrique. Les figures 8 à 16 décrivent un mode de réalisation particulier du troisième aspect de la présente invention, dont les caractéristiques se combinent avantageusement aux caractéristiques du premier aspect de la présente invention, qui vise un procédé de remplissage d'une forme géométrique qui comporte: - au moins une étape de décomposition de la forme géométrique en primitives graphiques simples, appelées "fragments" et - au moins une étape de calcul de l'aire d'intersection entre chaque fragment et un filtre dont la surface est supérieure à la surface d'un pixel. Dans le mode de réalisation particulier décrit et représenté, on met en oeuvre des portions de filtre qui se trouvent chacune dans un seul pixel. En variante non représenté, on ne met pas en oeuvre de portion mais un filtre d'une surface supérieure à celle d'un pixel, comme indiqué dans la définition générale du troisième aspect de l'invention rappelé ci-dessus. On a représenté, en figure 8, les coordonnées des 36 pixels les plus en bas et les plus à gauche d'une image en supposant qu'une forme géométrique en étoile 800 à côtés droits, dont l'image doit être synthétisée y était intégralement incluses. La forme géométrique en étoile 800 est, en figure 8, décomposée en primitives simples, ou "fragments", chaque fragment étant entièrement inclus dans un pixel, possédant un nombre de côtés inférieur ou égal à quatre et au moins un côté vertical ou horizontal: triangles ou quadrilatères (rectangles, trapèzes, ...). On a représenté, en figure 9, le pixel de coordonnées (2,4) et les huit pixels qui lui sont les plus proches, de coordonnées (1,5) à (3,5), (1,4), (3,4) et (1,3) à (3,3). Pour une meilleure lecture de la figure 9 et des figures suivantes, on a légèrement séparé les différents pixels, l'intervalle de séparation n'étant pas considéré dans les différentes étapes du procédé objet du troisième aspect de la présente invention. On observe, en figure 9, que le pixel de coordonnées (2,4) comporte deux fragments 901 et 902, le premier, en haut, de forme trapézoïdale et le second, en bas, de forme rectangulaire. On observe, en figure 10, un filtre de base carrée, qui s'appliquera au pixel de coordonnées (2,4), qui est centré sur le centre du pixel de coordonnées (2,4) et dont le côté est égal au double du côté d'un pixel unitaire. On observe aussi, en figure 10, les neuf portions 1001 à 1009 qui forment une décomposition de la base du filtre, chaque portion étant entièrement incluses dans un pixel et chaque pixel ne comportant qu'au plus une portion. La portion centrale 1005 est carrée et recouvre le pixel de coordonnées (2,4), les portions 1001, 1003, 1007 et 1009 sont carrées et recouvrent le quart le plus proche du pixel de coordonnées (2, 4) des pixels de coordonnées respectives (1,5), (3,5), (1,3) et (3,3). Les portions 1002, 1004, 1006 et 1008 sont des rectangles qui recouvrent la moitié la plus proche du pixel de coordonnées (2,4) des pixels de coordonnées respectives ((2,5), (1,4), (3,4) et 2,3). On observe, en figure 11, pour le fragment 901, les neufs aires d'intersection de ce fragment avec les portions de filtres incluses dans le pixel de coordonnées (2,4) des filtres appliqués aux neuf pixels de coordonnées (1,5) à (3,3) représentés en figure 9. Par convention, on a représenté en haut à gauche, l'aire d'intersection du fragment considéré avec la portion du filtre appliqué au pixel en bas à droite, de coordonnées (3,3), au milieu à gauche, l'aire d'intersection du fragment considéré avec la portion du filtre appliqué au pixel au milieu à droite, de coordonnées (3,4) et ainsi de suite. On observe, en figure 12, pour le fragment 902, les neufs aires d'intersection de ce fragment avec les portions de filtres incluses dans le pixel de coordonnées (2,4) des filtres appliqués aux neuf pixels de coordonnées (1,5) à (3,3) représentés en figure 9. On a utilisé la même convention de représentation que pour la figure 11. On observe, en figure 13, les sommes des aires d'intersection illustrées en figures 11 et 12, de la forme géométrique avec les portions de filtres incluses dans le pixel de coordonnées (2,4) des filtres appliqués aux neuf pixels de coordonnées (1,5) à (3,3) représentés en figure 9. On a utilisé la même convention de représentation que pour la figure 10. On observe, en figure 14, une représentation matricielle dans laquelle chaque ligne représente les différentes aires d'intersection, dans le pixel dont les coordonnées sont données en début de ligne, des fragments et des portions qui sont utilisées pour synthétiser le pixel de coordonnées (2,4). Par souci de simplification, on a pas représenté les pixels qui ne contiennent aucun fragment ou les pixels qui ne contiennent aucune portion du filtre. La couleur du pixel (2,4) est, dans un mode particulier de filtre présentant la base illustrée en figure 9, filtre ne prenant que la valeur "1" sur l'ensemble de sa base, sans pondération (on parle communément de "box filter"), la somme des aires d'intersection représentées en figure 14 divisées par la surface de la base du filtre, ici quatre fois la surface unitaire (voir figure 10) et multiplié par la surface du pixel (2, 4) (ici surface unitaire). La figure représente la surface sommée des aires d'intersection considérées pour le pixel de coordonnées (2,4) dans la surface totale de la base du filtre. La couleur de l'image synthétisée dans le pixel de coordonnées (2,4) est égale au ratio de la surface noire représentée en figure 15, sur la surface totale du filtre. Par exemple si le noir est représenté par la valeur 0 et le blanc par la valeur 255, le niveau de gris du pixel (2,4) vaut environ 184. On observe, en figure 16, différentes étapes mises en oeuvre dans un mode particulier de réalisation du procédé objet du troisième aspect de la présente invention. Au cours d'une étape 1500, on initialise le procédé en mettant à zéro la valeur de ses différents paramètres (en particulier x et y), on détermine au moins une forme géométrique à représenter sur une image à synthétiser, le nombre de pixels de l'image à synthétiser et un filtre à appliquer à chaque pixel de l'image à synthétiser. Par convention, les filtres appliqués aux pixels en bord ou en coin de l'image sont constitués par troncature de la base du filtre courant. Dans la suite de la description de la figure 16, on considère le filtre dont la base est illustrée en figure 10 et dont la valeur est "1" sur l'ensemble de cette base. Au cours d'une étape 1501, on détermine les portions de la base du filtre courant. Dans le mode de réalisation représenté, la décomposition de la base du filtre en portions est telle que chaque portion est incluses dans un seul pixel. Au cours d'une étape 1503, on considère le pixel dont les coordonnées sont (x,y). Au cours d'une étape 1504, on détermine les fragments de chaque forme géométrique pour le pixel de coordonnées (x,y) et pour les pixels huit entourant ce pixel, s'ils existent. La décomposition en fragments est effectuée de façon à ce que chaque fragment créé soit inclus dans un et un seul pixel. Ces fragments sont stockés en mémoire sous la forme d'une liste chaînée de fragments par Pixel. Ainsi, chaque pixel possède la liste de tous les fragments inclus dans lui même. Lorsqu'un fragment a déjà été déterminé au cours d'une étape 1504 précédente, il est lu en mémoire et non déterminé à nouveau, pour réduire les temps de traitement. Au cours d'une étape 1505, pour chaque fragment déterminé au cours de l'étape 1504, on calcule l'aire d'intersection entre le fragment considéré et chaque portion du filtre et on mémorise cette aire en regard du pixel dont le filtre comporte cette portion de filtre. On observe que les calculs des différentes aires est simplifié dans de nombreux cas dans lesquels il existe des relations entre les aires d'intersection, notamment lorsque les bases de filtre sont des multiples du pixel. Par exemple, pour une base rectangulaire qui correspond à quatre pixels (2 x 2) s'étendant sur neuf pixels autour du pixel auquel le filtre est appliqué, pour chaque colonne ou chaque ligne, les sommes des aires extrêmes sont égales à l'aire centrale (le calcul de 4 aires permet le calcul des 9 aires). De même, pour une base rectangulaire qui correspond à neuf pixels (3 x 3) s'étendant sur neuf pixels autour du pixel auquel le filtre est appliqué, pour chaque colonne ou chaque ligne, les aires extrêmes sont chacune égales à l'aire centrale. Au cours d'une étape 1506, pour le pixel de coordonnées (x,y), on calcule la surface totale d'intersection entre la forme géométrique et la base du filtre, en additionnant l'ensemble des aires d'intersection des portions du filtre appliqué au pixel de coordonnées (x,y) avec les différents fragments de chaque forme géométrique. Puis on multiplie cette surface par la couleur de cette forme géométrique et on additionne les résultats. Puis, on multiplie le résultat de cette addition par le rapport entre l'aire d'un pixel et l'aire du filtre, à savoir dans ce cas présent'/4 ou 0,25. Au cours d'une étape 1507, on écrit le résultat de l'étape 1506 dans une mémoire 10 d'image finale, pour le pixel de coordonnées (x,y). Au cours d'une étape 1508, on détermine si x correspond au dernier pixel d'une ligne. Si non, on incrémente la valeur de x, étape 1509 et on retourne à l'étape 1504. Si le résultat de l'étape 1508 est positif, au cours d'une étape 1510, on détermine si y correspond à la dernière ligne de l'image à synthétiser. Si non, on incrémente la valeur de y et on réinitialise la valeur de x à 0, étape 1511, et on retourne à l'étape 1504. Si le résultat de l'étape 1510 est positif, la synthèse de l'image est terminée. En variante, on applique une perturbation statistique, par exemple de type "distribution de Poisson", des coordonnées des divers éléments géométriques, à savoir la BASE du filtre, et/ou les PORTIONS du filtre, et/ou les fragments de la forme géométrique à rastériser. En effet, comme le rappelle R. Cook dans son article "Stochastic Sampling in Computer Graphics" (ACM Transactions on Graphics, Vol. 5, N 1, January 1986, Pages 51-72), à l'extérieur de la fovéa (région de la rétine située dans la macula, près de l'axe optique de l'oeil), la distribution des cellules photosensibles est non-uniforme, de type "disque de Poisson", raison pour laquelle l'oeil humain ne créée pas d'aliasing, malgré le fait que ces cellules photosensibles soient en nombre limité : le système visuel humain est beaucoup plus sensible au effets d'escalier et aux trames qu'au bruit pseudo-aléatoire introduit par une distribution statistique des cellules photosensibles. La figure 17 représente, schématiquement, la constitution d'un filtre particulier, dont la 30 forme est une intégrale d'une forme polygonale. La partie droite de la figure 17 indique la correspondance de la forme polygonale, ici pyramidale, avec des pixels puis la section de la forme du filtre correspondant défini comme l'intégrale de la forme polygonale lorsque le sommet de la pyramide parcourt le pixel. La partie gauche de la figure 17 indique la correspondance de la forme polygonale, ici cubique, avec des pixels puis la section de la forme du filtre correspondant défini comme l'intégrale de la forme polygonale. REVENDICATIONS 1 - Procédé de décomposition d'une forme géométrique définie par au moins une liste ordonnée et cyclique de sommets, caractérisé en ce qu'il comporte: - au moins une étape de recherche de sections monotoniques (210) sur la succession de sommets définie par chaque dite liste ordonnée et des bornes de ces sections, selon au moins une dimension et un sens; - au moins une étape de regroupement des sections monotoniques deux à deux pour définir des régions de ladite forme géométrique (220) ; - au moins une étape de classification des dites régions en régions "internes" pour lesquelles l'intérieur de la forme est à l'intérieur de la région considérée, et en régions "externes" pour lesquelles l'intérieur de la forme est à l'extérieur de la région considérée (220) ; - une étape de tri (225) des régions externes en fonction de leur coordonnées dans une dimension et un sens et - une étape de décomposition de la forme géométrique en formes géométriques internes simples, décomposition mettant en oeuvre les régions externes triées (230). 2 - Procédé selon la revendication 1, caractérisé en ce que les formes géométriques simples sont des polygones monotones dans une dimension. 3 - Procédé selon l'une quelconque des revendications 1 ou 2, caractérisé en ce que la dimension considérée dans l'étape de recherche de sections monotoniques, et l'étape de tri est identique. 4 - Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce qu'il comporte, en outre une étape de choix de la dimension et/ou du sens utilisé, en fonction du nombre total de régions internes, de régions externes, et du rapport entre ces deux nombres. - Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que, si la forme géométrique est définie par au moins deux listes ordonnées de sommets définissant au moins deux polygones dont l'un est intégralement inclus dans l'autre, le procédé tel que succinctement exposé ci-dessus comporte une étape de transformation de régions internes en régions externes et vice-versa pour les régions du polygone intégralement inclus dans l'autre. 6 - Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comporte, en outre, une étape d'affichage de l'ensemble des formes géométriques simples créées. 7 - Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'il comporte, en outre, une étape de détermination (425, 450), parmi les sommets, de chaque début de section monotonique pour lequel: soit, d'une part, le sommet précédent dans la liste est strictement en aval dans la direction et le sens de remplissage, et, d'autre part, le premier sommet suivant dans la liste qui n'est pas au même niveau dans la direction et le sens de remplissage est en aval dans la direction et le sens de remplissage, 5. soit, d'une part, le sommet suivant dans la liste est strictement en aval dans la direction et le sens de remplissage, et, d'autre part, le premier sommet précédent dans la liste qui n'est pas au même niveau dans la direction et le sens de remplissage est en aval dans la direction et le sens de remplissage. 8 - Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce qu'il comporte, en outre, une étape de regroupement des sections monotoniques, deux à deux, de telle manière qu'elles définissent une région (515, 520, 545, 550, 560, 565). 9 - Procédé selon l'une quelconque des revendications 1 à 8, caractérisé en ce que l'étape de décomposition de ladite forme géométrique met en oeuvre lesdites régions internes et externes. 10 - Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce qu'il comporte une étape de détermination de boîtes englobantes des régions internes et de limitation des régions externes prises en considération pour déterminer les formes géométriques simples relatives à une région interne en fonction de leur abscisse et de celle de la boîte englobante de la région externe considérée. 11 - Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que, lorsque le nombre de régions externes est au moins le double du nombre de régions internes et que le nombre de régions est supérieur à une valeur prédéterminée, on inverse le sens de traitement. 12 - Dispositif de décomposition d'une forme géométrique définie par au moins une liste ordonnée et cyclique de sommets, caractérisé en ce qu'il comporte: - au moins un moyen de recherche de sections monotoniques (50, 53) sur la succession de sommets définie par chaque dite liste ordonnée et des bornes de ces sections, selon au moins une dimension et un sens; - au moins un moyen de regroupement des sections monotoniques deux à deux (50, 53) pour définir des régions de ladite forme géométrique; - au moins un moyen de classification des dites régions en régions "internes" pour lesquelles l'intérieur de la forme est à l'intérieur de la région considérée, et en régions "externes" pour lesquelles l'intérieur de la forme est à l'extérieur de la région considérée (50, 53) ; - un moyen de tri des régions externes en fonction de leur coordonnées dans une dimension et un sens (50, 53) et - un moyen de décomposition de la forme géométrique en formes géométriques internes simples, décomposition mettant en oeuvre les régions internes et externes (50, 53).