Brevet FR2600185A1 — publié le 19871218

Procédé de surfaçage de zones d'images délimitées par des contours pour processeur graphique et processeur de surfaçage pour la mise en oeuvre de ce procédé La présente invention concerne un procédé de surfaçage de zones d'images délimitées par des contours pour processeur graphique et un processeur de surfaçage pour la mise en oeuvre de ce procédé. Les procédés de surfaçage sont mis en oeuvre dans les processeurs 5 graphiques pour faire apparaître sur un écran des surfaces délimitées par les lignes de contours. Ces surfaces sont hachurées, colorées ou encore remplies de motifs répétitifs. Leur mise en oeuvre s'effectue à l'aide de processeurs de surfaçage. Ceux-ci possèdent une mémoire auxiliaire, encore appelée mémoire de contours, à l'intérieur de laquelle les lignes 10 contours de l'image sont mémorisées en faisant usage des fonctions graphiques du processeur graphique. Un seul bit, ou élément binaire, suffit habituellement pour identifier chaque pixel d'un contour inscrit dans cette.mémoire. L'opération de surfaçage consiste à identifier les pixels internes à ces contours. L'identification a lieu en déterminant les points d'intersec15 tion de chaque ligne de pixel de l'image avec le contour pour inclure à l'intérieur de la surface les segments horizontaux ainsi délimités. Les procédés de surfaçage connus présentent l'inconvénient majeur queils ne permettent pas la détection de façon simple des points doubles qui apparaissent sur certains contours. Certains processeurs de 20 surfaçage remédient à cette difficulté en opérant une analyse de la mémoire de contours non pas le long des lignes en démarrant toujours à gauche à l'extérieur d'une surface délimitée par un contour mais en démarrant d'un point interne à celle-ci. Mais cette méthode de balayage est délicate à mettre en oeuvre et des points internes aux surfaces sont 25 omis, lorsqu'en particulier certains contours présentent des concavités. De plus, elle présente l'inconvénient majeur d'exiger. que soient fournies, en 26 0 0 1 8 5 plus des coordonnées des points situés sur les contours les coordonnées d'autant de points de départ qu'il y a de boucles dans les contours. Le but de l'invention est de pallier les inconvénients précités. A cet effet, l'invention a pour objet, un procédé de surfaçage de zones d'images délimitées par des contours pour processeur graphique, caractérisé en ce qu'il consiste à mémoriser dans une mémoire auxiliaire les contours fournis par le processeur graphique en excluant les points doubles, à balayer l'image ligne à ligne pour déterminer les points d'intersection des lignes et des contours, à mémoriser les valeurs mini10 maies et maximales des points d'intersection pour délimiter dans chaque contour la zone à surfacer, à considérer dans chaque zone ainsi délimitée les pixels un à un le long de chaque ligne pour déterminer s'ils sont internes à la zone à surfacer et les charger si tel est le cas à l'intérieur d'une mémoire d'image. L'invention a également pour objet un processeur de surfaçage faisant application du procédé précité. L'invention sera mieux comprise et d'autres caractéristiques apparaîtront à l'aide de la description qui suit en référence aux figures annexées qui représentent: - la figure 1 un organigramme illustrant les phases du procédé de surfaçage selon l'invention, - la figure 2 la structure d'une table de décision, - la figure 3 la structure du processeur de surfaçage selon l'invention, - la figure 4 un schéma de réalisation de la logique de décision de la figure 2. Le procédé selon l'invention est décrit ci-après à l'aide de l'organigramme de la figure 1. Il consiste, aux étapes représentées en 1 et 2, à rassembler les vecteurs représentant le tracé fourni par le processeur 30 graphique en blocs de pixels pour représenter les contours de l'image et, à charger aux étapes 3 et 4 chaque vecteur dans une mémoire de contours. Ce chargement s'effectue à l'étape 23 au travers d'un opérateur qui exécute l'opération connue en logique sous la désignation "OU exclusif" ou encore XOR entre l'état I logique de chaque pixel appartenant à un 2600 185 contour à mémoriser et les contenus des emplacements correspondants de la mémoire o les pixels doivent être chargés, pour exclure sur les contours ainsi chargés les points doubles. De cette façon, un état 1 logique matérialisant un pixel sur un contour pourra être inscrit en mémoire de contour chaque fois que l'emplacement correspondant à l'adresse indiquée dans la mémoire sera libre (état 0), et un état 0 sera inscrit en mémoire à la place d'un état 1 logique lorsque l'emplacement indiqué par l'adresse d'un pixel sur un contour sera déjà occupé pour matérialiser un pixel sur le contour précédemment enregistré à cet 10 emplacement. A l'étape 5 les points d'intersection des lignes de l'image avec les contours sont fournis par le processeur graphique et mémorisés afin de délimiter dans chaque contour la zone à surfacer. Le surfaçage proprement dit est exécuté à l'étape 6. Il consiste à considérer dans chaque zone à analyser, limitée comme indiqué ci-dessus, les pixels un à 15 un le long de leur ligne et à déterminer s'ils sont ou non internes à la surface. La décision est prise, par un organe de décision qui sera décrit ciaprès, en prenant en considération les états des pixels voisins entourant le pixel analysé en fonction: 1) de l'appartenance ou -non au contour de chacun des pixels 20 voisins, 2) de l'appartenance ou non à la surface du pixel qui précède le pixel analysé sur la même ligne, 3) et de l'appartenance ou non à la surface des pixels voisins du pixel analysé sur la ligne précédente. A titre d'exemple, en prenant pour pixels voisins ceux compris dans un carré de 3 x 3 pixels centré autour de chaque pixel analysé, le mode de décision précité pourra être exécuté en tenant compte des valeurs de l'ensemble des neuf pixels voisins enregistrés dans la mémoire de contour et de l'appartenance ou non à la surface d'une part, des trois 30 pixels voisins situés sur la ligne précédente et d'autre part, de celui qui précède le pixel analysé sur la même ligne. Au total, dans ce cas, la décision sera prise en fonction de 213 états possibles qui, pour des commodités de réalisation pourront être consignés dans une table de décision du type de celle qui est représentée à la figure 2 dans laquelle - 2600185 sont représentées quelques combinaisons particulières parmi les 213 combinaisons possibles d'un carré de 9 pixels référencés de P0 à P8 P0 représente le pixel analysé, P1, P2 et P3 désignant les trois pixels voisins du pixel P0 sur la ligne précédente, P4 désigne le pixel qui précède le 5 pixel P0 sur la même ligne, P5 à P8 désignent les pixels restant du carré et S désigne l'appartenance ou non du pixel P0 à la surface. Le procédé continue aux étapes 7 à 12 pour préparer les blocs des zones à surfacer en vue de leur chargement en mémoire d'image. A l'étape 7 les résultats d'analyse, transmis pixel par pixel en exécution de l'étape 10 6, sont regroupés en blocs à surfacer de 8 x 8 bits par exemple, chaque bit ayant une valeur I ou 0 selon que le pixel correspondant a été déclaré interne ou non à la surface. Chacun des bits d'un bloc à surfacer est éventuellement remplacé à l'étape 8 suivante par plusieurs bits pour définir un aspect de surface matérialisé par exemple par plusieurs 15 symboles qui sont délivrés à l'étape 9 par un générateur de symboles. Le chargement en mémoire d'image des blocs ainsi formés est ensuite exécuté aux étapes 10 et 11 en adjoignant au besoin à l'étape 12 un mot d'aspect pour désigner la couleur de la zone surfacée. Un intérêt du procédé qui vient d'être décrit est qu'il permet un 20 fonctionnement dans un mode connu dans le langage anglo-saxon sous le vocable "clipping", c'est-à-dire, un mode qui permet le surfaçage de morceaux d'images délimités par des fenêtres de formes quelconques. Chaque fenêtre est transmise par le processeur graphique aux étapes 13 et 14 pour être chargée dans la mémoire de contours. Le surfaçage de la 25 fenêtre est lancé en exécutant comme précédemment les étapes 3 à 7. Cependant les blocs surfaces obtenus ne sont pas combinés comme précédemment à des motifs pour obtenir des blocs chargeables en mémoire d'image, ils sont au contraire chargés dans la mémoire de contours ce qui ne perturbe pas le fonctionnement de l'organe de décision, 30 car ce chargement s'opère dans la zone de mémoire déjà analysée. L'analyse terminée, la surface de la fenêtre est définie par les bits chargés en mémoire de contours. Un découpage d'image ou encore un "clipping" de l'image à travers cette fenêtre peut alors s'effectuer sur toute image compilée par le processeur graphique. Les blocs définissant 2600-185 l'image, produits par le générateur de vecteur ou le générateur de symboles associé au processeur graphique, peuvent alors être transmis au processeur de surfaçage de l'invention fonctionnant dans le mode "clipping". Pour chaque bloc reçu, le processeur de surfaçage extrait de la 5 mémoire de contour aux étapes 15 et 16 le bloc homologue. Les blocs ainsi obtenus sont chargés en mémoire d'image à l'étape 11 après avoir reçu leur indication de couleur au cours de l'étape 12. Un processeur de surfaçage, permettant l'exécution du procédé précité, est décrit ci-après à l'aide du schéma de la figure 3. Ce 10 processeur est organisé autour d'un bus de données 17 qui assure le couplage et le transfert des données entre le processeur de surfaçage de l'invention et un processeur graphique 18. Il comprend, un dispositif de mémorisation des contours des zones à surfacer 19, une logique de décision 20 décrite ci-après et un organe de "clipping" 21 constitué par 15 des bancs de registres qui assurent la communication entre le dispositif de mémorisation des contours 19 et le processeur graphique 18 pour permettre le chargement des fenêtres surfacées dans une mémoire d'image, non représentée, du processeur graphique 18. Le dispositif de mémorisation des contours des zones à surfacer 19 est couplé au bus de données 17 20 à travers un circuit de combinateur "OU exclusif" 22 et des circuits d'interface 23. Ces derniers sont constitués de façon connue, par des registres tampons ou tout dispositif équivalent permettant le stockage momentané des données transitant sur le bus de données 17 pour ensuite appliquer celles-ci à l'entrée du circuit combinateur 22. 25 Il comprend également: - une mémoire 24 pour mémoriser les coordonnées maximales et minimales des contours sur chaque ligne d'image, - un contrôleur de mémoire 25 et un séquenceur 26 pour lancer de façon connue des cycles d'écriture et de lecture des données à l'intérieur 30 du dispositif de mémorisation des contours 19, et de la mémoire 24 et pour commander les opérations logiques exécutées par la logique de décision 20, - un générateur de symboles 27 couplé au bus de données 17 au moyen d'un circuit combinateur "ET logique" 28 et des circuits d'interface 26O0 185 29. Les circuits d'interface 29 sont constitués de façon connue par des registres tampons, non représentés, et assurent également l'interface entre l'organe de "clipping" 21 et le bus 17. Le circuit combinateur 28 est également couplé à une sortie S de la logique de décision 20 pour 5 effectuer le ET logique entre les bits représentant les pixels surfacés fournis par la logique de décision 20 et les symboles fournis par le générateur de symboles 27 et appliquer les résultats obtenus à l'entrée des circuits d'interface 29. Un mode de réalisation de la logique de décision 20 est représenté 10 à la figure 4. Cette logique comprend une mémoire morte programmable dans laquelle est mémorisée la table de décision de la figure 2. Cette mémoire est adressée par les treize bits d'état des pixels entourant chaque pixel analysé décrit précédemment. Elle reçoit sur une première entrée d'adressage E1 les neuf états des pixels entourant chaque pixel 15 analysé fournis par la mémoire de contours, une deuxième entrée d'adressage E2 sur laquelle sont appliqués les trois états des pixels voisins de la ligne précédant la ligne appartenant au pixel analysé et enfin une troisième entr6e d'adressage E3 sur laquelle est appliqué l'état du pixel voisin précédant sur la même ligne le pixel analysé. Les trois états des 20 pixels appliqués sur la deuxième entrée E2 d'adressage sont transmis par trois sorties d'un registre à décalage 33 dont l'entrée est couplée à la sortie S de données de la mémoire 30 au moyen d'un dispositif à retard 31 de la durée d'une ligne de balayage. L'état du pixel appliqué sur l'entrée d'adressage E3 provient de la sortie d'un registre 32 dont l'entrée est 25 directement couplée à la sortie de données de la mémoire 30. REVENDICATIONS 1. Procédé de surfaçage de zones d'images délimitées par des contours pour processeur graphique, caractérisé en ce qu'il consiste à mémoriser (4) dans une mémoire auxiliaire (19) les contours fournis par le processeur graphique (18) en excluant les points doubles (3), à balayer 5 l'image ligne à ligne pour déterminer les points d'intersection des lignes et des contours, à mémoriser (5) les valeurs maximales et minimales des points d'intersection pour délimiter dans - chaque contour la zone à surfacer, à considérer (6, 7) dans chaque zone ainsi délimitée les pixels un à un le long de chaque ligne pour déterminer s'ils sont internes à la zone à 10 surfacer et les charger si tel est le cas (8, 9, 10, 11, 12) à l'intérieur d'une mémoire d'image. 2. Processeur de surfaçage pour la mise en oeuvre du procédé selon la revendication 1, caractérisé en ce qu'il comprend: - un dispositif (19) de mémorisation des contours de l'image, - une logique de décision (20) couplée au dispositif de mémorisation des contours pour cons ater l'appartenance de chaque pixel de l'image analysée à une zone délimitée par un contour à surfacer, - et un circuit "OU exclusif" (22) couplé au dispositif de mémorisation des contours (19) pour permettre l'enregistrement, dans le dispositif 20 de mémorisation des contours (19), des pixels appartenant à un contour à surfacer et l'effacement de ceux qui forment les points doubles sur les contours entourant les zones à surfacer. 3. Processeur de surfaçage selon la revendication 2, caractérisé en ce qu'il comprend un organe de "clipping" (21) pour faire apparaître des 25 fenêtres surfacées dans l'image du processeur graphique. 4. Processeur de surfaçage selon l'une quelconque des revendications 2 et 3, caractérisé en ce qu'il comprend également une mémoire (24) pour mémoriser les coordonnées maximales et minimales des contours sur chaque ligne d'image, un contrôleur de mémoire (25) et un séquenceur (26) 30 pour lancer des cycles d'écriture et de lecture des dispositifs de mémori sation des contours (19) et de la mémoire (24) pour mémoriser les coordonnées maximales et minimales des contours et pour commander les 2600 185 g opérations logiques exécutées par la logique de décision (20) et un générateur de symboles (27) couplé à la sortie de la logique de décision pour le remplissage des zones surfacées par des symboles. 5. Processeur de surfaçage selon l'une quelconque des revendica5 tions 2 à 4, caractérisé en ce que la logique de décision (20) est formée par une mémoire morte programmable adressée par: l'état d'appartenance ou non au contour mémorisé dans le dispositif de mémorisation des contours (19) de chacun des pixels voisins du pixel analysé, l'état d'appartenance à la zone intérieure au contour à surfacer des pixels qui 10 précèdent le pixel analysé sur la même ligne et l'état d'appartenance ou non à la zone délimitée par le contour à surfacer des pixels voisins du pixel analysé sur la ligne précédente.