Brevet FR2694427A1 — publié le 19940204

L'invention concerne de façon générale des appareils et des procédés destinés à collecter et traiter des données de sommets de polygone graphique sur ordinateur et à être utilisés pour les affichages graphiques à grande vitesse. Plus précisément, l'invention concerne l'augmentation des performances du système d'affichage sur ordinateur par réduction du nombre de calculs redondants nécessaires pour la création de données d'affichage pour une simulation "par la fenêtre". La simulation par la fenêtre implique la création d'images animées sur un affichage graphique d'ordinateur, destinées à améliorer l'interaction entre l'opérateur et le système d'ordinateur. Par exemple, la simulation par la fenêtre est actuellement utilisée dans les simulateurs de vol afin que le pilote ait la sensation d'un vol réel autour de lui. Les images affichées comprennent en général une multitude de formes polygonales bidimensionnelles et tridimensionnelles créées par le système graphique de l'ordinateur. Lors de la simulation par la fenêtre, le système graphique doit pouvoir faire tourner ou pivoter les formes polygonales affichées.Ces manipulations nécessitent l'exécution de transformations matricielles par le système pour la transformation des données de sommets en valeurs de l'espace universel (c'est-à-dire en coordonnées cartésiennes sans dimension) associées à un angle convenable de vision ou à une perspective. La sélection de coefficients convenables des matrices permet un changement d'échelle des vecteurs des polygones et la rotation ou l'inclinaison en perspective à volonté. Des exemples de systèmes connus ont mémorisé puis recherché et transformé toutes les coordonnées de sommets de chaque polygone avant la création de l'image graphique par un affichage graphique. La figure 1 est une représentation schématique d'un tel exemple de système de la technique antérieure destiné au traitement de données de sommets pour la création de formes polygonales sur un affichage graphique. Le système 10 comprend une architecture tampon à pipeline comprenant une unité centrale de traitement CPU 12, un dispositif 14 à liste d'affichage, un organe 16 de commande de liste d'affichage, un processeur 18 de transformation et un dispositif 20 d'affichage qui comprend un processeur dorsal 24. L'unité CPU 12 calcule les coordonnées de sommets et les transmet au dispositif 14 à liste d'affichage qui conserve les données de sommets à transformer.Un organe 16 de commande d'affichage retrouve séquentiellement les données de sommets dans le dispositif à liste d'affichage 14 lorsqu'elles sont nécessaires au système 10 et transmet les données individuelles de sommets à un processeur 18 de transformation. Ce dernier exécute les transformations matricielles sur les données reçues de sommets de polygone pour la transformation des coordonnées de sommets de polygone en coordonnées de l'espace universel. Le processeur 18 de transformation transmet alors les données transformées de sommets au processeur dorsal 24. Le processeur dorsal 24 exécute alors une conversion en lignes de balayage et un rendu des éléments d'image pour la création de l'image graphique affichée par le dispositif d'affichage 20.Dans le système de la technique antérieure considéré, chaque sommet doit être transformé indépendamment du fait qu'un sommet est partagé par un ou plusieurs polygones. Ainsi, lorsque les polygones partagent un sommet, le système exécute des calculs redondants de transformation qui perdent un temps précieux de l'ordinateur et ralentissent la remise à jour de l'image graphique affichée. Le temps nécessaire à une transformation matricielle peut être important lorsque l'image affichée comprend plusieurs formes polygonales ayant une multitude de coordonnées de sommets et lorsqu'il est souhaitable de faire tourner ou pivoter l'image affichée. Ainsi, un exemple de transformation matricielle unique des coordonnées des sommets, par un procédé de transformation matricielle 4 x 4, nécessite vingt-huit opérations en virgule flottante, seize multiplications et douze additions. Chaque changement élémentaire de position de l'image affichée nécessite la transformation de chaque sommet de l'image affichée pour la formation d'une perspective remise à jour d'observation de l'image. Le temps nécessaire à la transformation d'une image complète peut être important.En conséquence, il est souhaitable de réduire le temps nécessaire à la remise à jour de l'affichage par réduction ou l'élimination des transformations redondantes des sommets. Les réalisations antérieures ont visé à réduire les transformations redondantes par utilisation de données de polygone à "mailles". Comme décrit par Foley, Van Damme, Feiner et Hughes, dans "Computer Graphics Principles and Practice", Addison-Wesley Publishing Co. Inc., 1990, une maille de polygone est un ensemble de surfaces connectées de polygone représentant des volumes tridimensionnels. Une maille de polygone peut être représentée par des polygones explicites ou par des listes de pointeurs sur des sommets ou des côtés. Lorsqu'elle est représentée sous forme de polygones explicites, la "maille" contient des informations en double sous forme de sommets ou de côtés qui nécessitent des comparaisons pour la réduction de la redondance des données.Lorsqu'il est représenté sous forme d'une liste, le système de la maille utilise un mécanisme de référence indirecte pour la localisation des composantes des sommets et nécessite habituellement un tri pour la détermination des côtés adjacents. Au cours de la simulation, ces conditions supplémentaires de traitement prennent trop de temps et empêchent l'utilisation de la maille. En conséquence, un dispositif plus efficace est souhaitable pour l'élimination des transformations redondantes. La présente invention concerne un appareil et un procédé destinés à accroître les performances d'un système graphique d'ordinateur présentant des formes polygonales. Un dispositif de traitement crée des données de sommets associées à un polygone, affecte une valeur d'indice à un sommet partagé suivant, et conserve les données de sommets et la valeur d'indice dans un premier dispositif à mémoire. Une unité de commande de liste d'affichage recherche séquentiellement les données de sommets et les valeurs d'indices dans le premier dispositif à mémoire. Une unité de transformation transforme les données de sommets en données de l'espace universel. Une unité de mémorisation de type cache contient des données d'espace universel dans un second dispositif de mémoire, de préférence un dispositif de mémoire cache, et tire les données d'espace universel du second dispositif de mémoire chaque fois qu'une valeur d'indice conservée dans le premier dispositif de mémoire est tirée par l'ensemble de commande de liste d'affichage. L'unité de mémorisation cache transfère alors des données d'espace universel à un dispositif d'affichage. Dans un mode de réalisation préféré, l'unité de mémorisation cache comprend un dispositif de mémoire cache, un dispositif de commande de cache et un dispositif tampon. Les données de l'espace universel sont conservées dans le dispositif de mémoire cache. Le dispositif de commande de cache est couplé au dispositif de mémoire cache. Chaque fois que l'unité de commande de liste d'affichage tire une valeur d'indice, le dispositif de commande de cache tire les données correspondantes d'espace universel conservées dans le dispositif de mémoire cache et transfère les données d'espace universel à un bus interne. Un dispositif tampon reçoit les coordonnées d'espace universel du bus interne et transfère les données d'espace universel à un dispositif d'affichage. Dans un autre mode de réalisation préféré, le dispositif de commande de cache précité comprend un dispositif d'indexation destiné à recevoir la valeur d'indice du premier dispositif de mémoire et à transmettre la valeur d'indice à une voie d'adresse du dispositif de mémoire cache. Le dispositif de commande de cache comprend aussi un bloc de commande du dispositif d'indexation, du dispositif de mémoire cache et du dispositif tampon. D'autres caractéristiques et avantages de l'invention ressortiront mieux de la description qui va suivre de modes de réalisation, faite en référence aux dessins annexés sur lesquels la figure 1 est une représentation schématique d'un exemple de système connu pour le traitement de données de sommets la figure 2 est une représentation schématique d'un système de traitement de sommets de polygone selon la présente invention la figure 3 représente des exemples de formes polygonales destinées à être affichées par un système selon l'invention ; la figure 4 est une représentation schématique d'une liste d'affichage et de polygones dans une mémoire contenant des données de sommets ; la figure 5 est une représentation schématique plus détaillée du dispositif de mémorisation cache de l'invention ; et la figure 6 est une représentation schématique détaillée d'un système de traitement de sommets de polygone selon la présente invention. La figure 2 représente un système 11 de traitement de sommets selon la présente invention. Une unité 12 de traitement d'ordinateur (CPU) crée des données de sommets de polygone à la première apparition ou apparition originale des sommets de chaque forme polygonale et des valeurs d'indices pour l'identification des sommets partagés de plusieurs formes polygonales, et mémorise les données créées de sommets et les valeurs d'indices dans une mémoire 14 de liste d'affichage. Un organe 16 de commande de liste d'affichage a accès successivement au contenu de chaque emplacement de la mémoire 14 de liste d'affichage et transfère les données obtenues à un processeur 18 de transformation.Ce dernier exécute une transformation matricielle sur les données sélectionnées de sommets pour transformer les données de sommets en données d'espace universel, comprenant des coordonnées d'espace universel, et transmet les coordonnées transformées à un processeur dorsal 24 d'un dispositif d'affichage 20. Simultanément, les coordonnées d'espace universel de chaque sommet original sont conservées dans un dispositif 22 de mémorisation cache pour des références ultérieures. L'organe 16 de commande continue à tirer successivement le contenu de la mémoire 14 de liste d'affichage et traite les données comme décrit précédemment.Cependant, lorsque l'organe 16 de commande de liste d'affichage obtient une valeur d'indice (plutôt que des données de sommet original) dans la mémoire 14, l'organe 16 de commande utilise la valeur d'indice pour adresser les coordonnées déjà transformées du sommet partagé qui sont conservées dans le dispositif 22 de mémorisation cache. Ce dispositif 22 transmet alors les valeurs transformées antérieurement au dispositif 20 d'affichage sans qu'il soit nécessaire d'exécuter une transformation matricielle redondante des données de sommets par le processeur 18 de transformation, si bien que le temps nécessaire à la création et à la remise à jour de l'image graphique affichée est réduit. Par exemple, la figure 3 représente des exemples de formes polygonales A, B et C qui doivent être affichées par le système graphique. Des données de sommets relatives au polygone A sont référencées Ai, A2 et A3. Le polygone B comprend des sommets originaux B1 et B2 et partage des sommets A2 et A3 avec le polygone A. Le polygone C comprend un sommet original Cl et partage le sommet Ai avec le polygone A et partage le sommet B2 avec le polygone B. Comme l'indique la figure 4, ces valeurs de sommets sont conservées séquentiellement dans une partie de la mémoire du système désignée comme étant la mémoire 14 de liste d'affichage. Les informations de polygone, pour chaque polygone ainsi mémorisé, comprennent un en-tête de polygone qui identifie le polygone auquel correspondent les données ultérieures de sommets. Par exemple, l'information de polygone correspondant au polygone B commence par un entête de polygone B suivi par les sommets originaux BI et B2 qui sont alors suivis par des valeurs d'indices correspondant aux sommets A3 et A2 respectivement, partagés par le polygone A. Chaque sommet de polygone est représenté par des coordonnées de sommets X, Y et Z qui sont conservées dans les dispositifs 14 de liste d'affichage en format à virgule flottante.Chaque valeur d'indice est conservée dans la mémoire 14 de liste d'affichage en format binaire. La figure 5 est une représentation schématique plus détaillée d'un système selon l'invention. Une unité CPU 12 transmet et mémorise les données de sommets de polygone, tels que les sommets représentés sur la figure 4, à une mémoire 14 de liste de d'affichage telle que représentée sur la figure 5. L'organe 16 de commande de liste d'affichage tire successivement les données de sommet original de la mémoire 14 et transmet ces données au processeur 18 de transformation matricielle des coordonnées de sommets en coordonnées d'espace universel. Le processeur 18 de transformation transmet alors les coordonnées d'espace universel à un processeur dorsal 24 du dispositif d'affichage 20. Ce processeur 24 assure alors des tests de détourage, des divisions pour la perspective et l'établissement de cartes, destinés à transformer les coordonnées d'espace universel en coordonnées d'écran.Simultanément, l'organe 16 de commande transmet un signal au dispositif 22 de mémorisation cache. Ce dispositif 22 comporte un dispositif 26 de commande de cache, un dispositif 28 de mémoire cache de sommets, et un circuit tampon 30 d'entrée-sortie de cache. Le dispositif 26 de commande active une voie d'entrée du circuit tampon 30 qui conserve les coordonnées d'espace universel qui viennent d'être transformées. le dispositif 26 de commande de cache exécute alors une instruction qui provoque la mémorisation des valeurs d'espace universel présentes dans la voie d'entrée du circuit tampon 30 dans le dispositif 28 de mémoire cache de sommets. Le système continue à tirer successivement les données des sommets originaux de la mémoire 14 de liste d'affichage, il transforme les données de sommets en coordonnées d'espace universel dans le processeur 18 de transformation, il mémorise les coordonnées d'espace universel dans le dispositif 28, et il transmet les coordonnées d'espace universel au processeur dorsal 24 de la manière décrite précédemment jusqu'à ce que l'organe 16 de commande et d'affichage arrive à un emplacement de la mémoire de liste d'affichage qui contient une valeur d'indice d'un sommet partagé, par exemple l'indice [ A3 ] du polygone B comme indiqué sur la figure 4.Lorsqu'il obtient la valeur d'indice A3, l'organe 16 de commande représenté sur la figure 5 transmet la valeur d'indice A3 au dispositif 26 de commande de cache qui adresse alors l'emplace- ment de mémoire cache contenant les coordonnées d'espace universel correspondant aux coordonnées déjà transformées du sommet original A3 du polygone A. Le dispositif 26 de commande de cache exécute alors une instruction de recherche provoquant le chargement des données d'espace universel indexées correspondant au sommet A3 par une voie de sortie du circuit tampon 30.Le dispositif 26 de commande transmet alors un signal au circuit tampon 30 afin que les données d'espace universel A3 soient transmises par le bus 31 du système et que les coordonnées d'espace universel A3 parviennent au processeur dorsal 24 qui exécute alors les opérations de tests de détourage, de division pour la perspective, de formation de cartes, de conversion en lignes de balayage et de rendu d'éléments d'image pour la création d'une image graphique sur le dispositif d'affichage 20. Ensuite, l'organe 16 de commande d'affichage parvient à l'emplacement suivant de la mémoire de la liste d'affichage et répète le traitement décrit précédemment. La figure 6 est une représentation schématique encore plus détaillée d'un mode de réalisation préféré de l'invention. On suppose qu'une unité centrale de traitement CPU 12 a préalablement ordonné et mémorisé des données de sommets de polygone dans une mémoire de liste d'affichage. L'organe 16 de liste d'affichage tire séquentiellement les données de sommets de polygone d'une mémoire 14 de liste d'affichage et transmet les données obtenues à un processeur 18 de transformation qui assure la transformation matricielle en données d'espace universel, par exemple en coordonnées d'espace universel. Le processeur 18 de transformation transmet alors les coordonnées d'espace universel qui viennent d'être transformées à un bus 31 du système vers un processeur dorsal 24 d'un dispositif 20 d'affichage graphique. Simultanément, le processeur 18 de transformation transmet les coordonnées d'espace universel à un registre d'entrée 32 du circuit tampon d'entrée-sortie 30. Ce circuit tampon 30 comprend à la fois un registre d'entrée 32 et un registre de sortie 34. L'organe 16 de commande de liste d'affichage transmet alors un signal de commande par le bus 33 à un bloc de commande 36 qui transmet lui-même un signal au registre d'entrée 32 afin que celui-ci conserve les données qui viennent d'être transformées. Le bloc 36 de commande transmet alors un signal au dispositif 28 à mémoire cache de sommet de manière que ce dispositif 28 conserve le contenu du registre d'entrée 32. De préférence, le dispositif 28 peut conserver les données de sommets transformées pour cinq cents polygones. Le système de la figure 6 continue à tirer successivement les données de sommets de la mémoire 14 de liste d'affichage, il transforme les données dans le processeur 18 de transformation en valeurs d'espace universel, il conserve les valeurs dans la mémoire cache 28, et il transmet les valeurs transformées au processeur dorsal 24 de la manière décrite précédemment jusqu'à ce que l'organe 16 de commande d'affichage tire une valeur d'indice de la mémoire 14. Lorsque la valeur d'indice a été obtenue, l'organe 16 de commande transmet cette valeur d'indice à un registre à file ou un organe 38 d'indexation de file par un bus 34. L'organe d'indexation 38 transmet alors la valeur d'indice à une voie 40 de commande d'adresse du dispositif 28 de mémoire cache.Le bloc de commande 36 transmet alors un signal dispositif 28 et ce dernier utilise ensuite la valeur d'indice reçue à une voie de commande d'adresse 40 pour l'adressage des coordonnées d'espace universel conservées antérieurement, correspondant à la valeur d'indice du sommet partagé, et il place les coordonnées d'espace universel dans le bus 37 de données du dispositif à mémoire cache. Le bloc de commande 36 transmet alors un signal au registre de sortie 34 du circuit tampon 30 qui transfère alors les valeurs d'espace universel du bus des données de cache au bus 31 du système pour l'accès du processeur dorsal 24. Ce dernier effectue les opérations de tests de détourage, de division pour la perspective, de tracé, de conversion en lignes de balayage et de rendu d'éléments d'image pour la création d'une image graphique sur le dispositif 20 d'affichage.Ensuite, l'organe 16 passe à l'emplacement suivant de la mémoire de la liste d'affichage et répète le processus décrit précédemment. Etant donné l'élimination des étapes redondantes de transformation, le système selon l'invention réduit le temps de traitement nécessaire à la création d'une simulation par la fenêtre. Par exemple, le temps nécessaire à la consultation d'un indice est d'environ quatre cycles. A titre comparatif, le temps nécessaire pour l'exécution du processus de transformation est d'environ vingt cycles. Ainsi, le système selon l'invention permet une amélioration des performances de cinq à un par rapport au système graphique connu pour chaque sommet partagé associé aux formes polygonales à afficher. En résumé, le système selon l'invention ajoute un dispositif de mémorisation à cache et les circuits associés de commande à un système d'affichage graphique à pipeline pour la réduction ou l'élimination des transformations matricielles redondantes des données des sommets partagés, si bien que le temps de traitement nécessaire pour la création des images graphiques affichées pour une simulation par la fenêtre est réduit. Il est bien entendu que l'invention n'a été décrite et représentée qu'à titre d'exemples préférentiels et qu'on pourra apporter toute équivalence technique dans ses éléments constitutifs sans pour autant sortir de son cadre. REVENDICATIONS 1. Appareil destiné à accroître les performances d'un système graphique à ordinateur qui affiche des formes polygonales, caractérisé en ce qu'il comprend un dispositif (12) de traitement destiné à créer des données de sommets associées à un polygone, à affecter une valeur d'indice à un sommet partagé par plusieurs polygones, et à mémoriser les données de sommets et la valeur d'indice dans un premier dispositif de mémoire, un dispositif (16) de commande de liste d'affichage destiné à tirer successivement les données de sommets et les valeurs d'indice du premier dispositif de mémoire, un dispositif (18) de transformation des données de sommets en données d'espace universel, et un dispositif (22) de mémorisation cache destiné à mémoriser les données d'espace universel dans un second dispositif de mémoire, afin que les données d'espace universel soit récupérées dans le second dispositif de mémoire chaque fois qu'une valeur d'indice conservée dans le premier dispositif de mémoire est obtenue par le dispositif de commande de liste d'affichage, et à transférer les données d'espace universel à un dispositif d'affichage. 2. Appareil selon la revendication 1, caractérisé en ce que le dispositif (22) de mémorisation cache comprend un dispositif (26) de mémoire cache destiné å conserver les données d'espace universel, un dispositif (28) de commande couplé au dispositif de mémoire cache et destiné à tirer les données d'espace universel conservées dans le dispositif de mémoire cache et à transférer les données d'espace universel à un bus interne, et un dispositif tampon (30) ayant une voie d'entrée destinée à recevoir les coordonnées d'espace universel du bus interne et ayant une voie de sortie destinée à transférer les données d'espace universel au dispositif d'affichage. 3. Appareil selon la revendication 2, caractérisé en ce que le dispositif de commande (28) comporte en outre un dispositif d'indexation (38) destiné à recevoir la valeur d'indice du premier dispositif de mémoire et à transmettre la valeur d'indice à une voie d'adressage du dispositif de mémoire cache, et un dispositif (36) à bloc de commande du dispositif d'indexation, du dispositif de mémoire cache et du dispositif tampon. 4. Appareil selon la revendication 1, caractérisé en ce que les données de sommets comprennent des coordonnées de sommets X, Y et Z. 5. Appareil selon la revendication 4, caractérisé en ce que le processeur (18) de transformation exécute une multiplication matricielle des coordonnées de sommets pour la création de coordonnées d'espace universel. 6. Procédé destiné à augmenter les performances d'un système graphique à ordinateur affichant des formes polygonales, caractérisé en ce qu'il comprend les étapes suivantes la création de données de sommets associées à un polygone, l'affectation d'une valeur d'indice à un sommet partagé ayant des données de sommets créées antérieurement, la mémorisation des données de sommets et de la valeur d'indice dans un premier dispositif de mémoire, l'extraction successive des données de sommets et des valeurs d'indices du premier dispositif de mémoire, la transformation des données de sommets en données d'espace universel, la mémorisation des données d'espace universel dans un second dispositif (22) de mémoire, l'extraction des données d'espace universel du second dispositif (22) de mémoire chaque fois qu'une valeur d'indice conservée dans le premier dispositif (14) de mémoire est obtenue par le dispositif (16) de commande de liste d'affichage, et le transfert des données d'espace universel å un dispositif d'affichage (20). 7. Procédé selon la revendication 6, caractérisé en ce que les données de sommets sont mémorisées sous forme de coordonnées de sommets X, Y et Z. 8. Procédé selon la revendication 7, caractérisé en ce que la transformation des données de sommets comprend l'exécution d'une multiplication matricielle des coordonnées de sommets pour la création de coordonnées d'espace universel. 9. Procédé selon la revendication 6, caractérisé en ce que le second dispositif de mémoire comprend un dispositif (22) de mémoire cache.