Brevet FR2865563A1 — publié le 20050729

PROCEDE ET DISPOSITIF DE REMPLISSAGE D'UNE FORME GEOMETRIQUE 5 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é etlou 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 parles 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 de 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. Selon un premier aspect, la présente invention vise un procédé de remplissage d'une 30 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 15 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 25 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 deuxième aspect, 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érieure à la surface d'un pixel. Les avantages, buts et caractéristiques du deuxième aspect de la présente invention étant similaires à ceux du premier 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 10 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 15 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 de la 25 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 de la présente invention et - 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 15 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 d'un procédé et un dispositif de décomposition d'une forme géométrique qui se combine favorablement à la présente invention (figures 1 à 7) puis un mode particulier de réalisation du procédé objet de la présente invention (figures 8 à 16) avant de décrire des combinaisons avantageuses des différents procédés. 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 parcôurs 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 disc 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 S0, 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,Iorsqu'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 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 30 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 lessuivantes. 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 20 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 30 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 (Paraml) 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 (Paraml) 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 (prend 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 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 à 20 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 oùi, 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 é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 35 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: nombre de points durée "Gordon" durée présente invention ratio de gain 4000 420. 330 1,3 10 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 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 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 procédé objet de la présente invention, dont les caractéristiques se combinent avantageusement aux 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 caractéristiques du procédé de décomposition illustré, à titre d'exemple, en figures 1 à 7, et 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 procédé objet 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 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 25 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 neufpixels 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 15 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 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 1/4 ou 0,25. Au cours d'une étape 1507, on écrit le résultat de l'étape 1506 dans une mémoire 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 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 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" (1504) et - au moins une étape de calcul de l'aire d'intersection (1505) entre chaque fragment et un filtre dont la surface est supérieure à la surface d'un pixel. 2 - Procédé selon la revendication 1, caractérisé en ce qu'il comporte: au moins une étape de décomposition de la base d'au moins un filtre en primitives graphiques simples (1501), appelées "portions" ; - au moins une étape de calcul des aires d'intersection entre chaque fragment et chaque portion (1505) 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 (1506), ladite fonction donnant au moins un élément de couleur pour ledit pixel auquel est appliqué ledit filtre. 3 - Procédé selon la revendication 2, caractérisé en ce que au cours de l'étape de décomposition de la base en portions (1501), chaque portion est incluse dans un et un seul pixel. 4 - Procédé selon l'une quelconque des revendications 2 ou 3, caractérisé en ce que au cours de l'étape de décomposition de la base d'au moins un filtre (1501), les intersections des portions sont vides et leur réunion est égale à ladite base. - Procédé selon l'une quelconque des revendications 2 à 4, caractérisé en ce que au cours de l'étape de décomposition de la base d'un filtre (1501), ledit filtre possède une base rectangulaire dont chaque côté est un multiple du côté correspondant d'un pixel. 6 - Procédé selon l'une quelconque des revendications 2 à 5, caractérisé en ce que au cours de l'étape de calcul numérique (1506), on effectue une étape de pondération des différentes aires. 7 - Procédé selon la revendication 6, caractérisé en ce que 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. 8 - Procédé selon l'une quelconque des revendications 2 à 7, caractérisé en ce que au cours de l'étape de calcul numérique (1506), on effectue une sommation ou addition des aires d'intersection, éventuellement pondérées, composant la forme du filtre appliquée au pixel. 9 - Procédé selon l'une quelconque des revendications 2 à 8, caractérisé en ce que au cours de l'étape de calcul des aires d'intersection (1505), 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. - Procédé selon l'une quelconque des revendications 1 à 9, caractérisé en ce que au cours de l'étape de décomposition de la forme géométrique en fragments (1504), chaque fragment est inclus dans un et un seul pixel. 11 - Procédé selon l'une quelconque des revendications 1 à 10, caractérisé en ce que au cours de l'étape de décomposition de la forme géométrique (1504), les intersections des fragments sont vides et leur réunion est égale à ladite forme géométrique. 12 - Procédé selon l'une quelconque des revendications 1 à 11, caractérisé en ce que l'étape de calcul numérique (1506) comporte une étape de multiplication par le rapport entre l'aire du pixel et l'aire totale du filtre. 13 - Procédé selon l'une quelconque des revendications 1 à 12, caractérisé en ce que au cours de l'étape de calcul numérique (1506), on pondère la couleur par un filtre. 14 - Procédé selon l'une quelconque des revendications 1 à 13, caractérisé en ce que la forme du filtre est une intégrale d'une forme polygonale. 15 - Procédé selon l'une quelconque des revendications 1 à 14, caractérisé en ce qu'il est effectué successivement pour des pixels successifs sur une même ligne, en traitant successivement les lignes successives de l'image à constituer. 16 - Dispositif de remplissage d'une forme géométrique mettant en oeuvre un procédé de remplissage selon l'une quelconque des revendications 1 à 15, 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" (50, 53) et - au moins un moyen de calcul de l'aire d'intersection entre chaque fragment et un filtre dont la surface est supérieure à la surface d'un pixel (50, 53).