FR2640792A1 - Circuit pour determiner des positions de lignes de balayage pour affichage et manipulation par un systeme infographique - Google Patents

Abstract

Ce circuit permet de déterminer les valeurs X de chaque extrémité d'une suite de lignes horizontales de balayage reliant un couple de segments de droite dont chacun est défini par un couple de sommets, les lignes horizontales de balayage définissant une aire à restituer sur un périphérique de sortie d'ordinateur. Il comprend, selon l'invention : - un premier 32 et un second 34 bloc de circuit, chacun de ces blocs de circuit comprenant des moyens pour déterminer la pente d'un segment de droite et des moyens pour déterminer, en fonction de la pente, les valeurs X de début et de fin pour chaque segment de droite de chaque ligne de balayage de l'aire à restituer, - des moyens pour faire commencer à fonctionner les deux blocs de circuit sur la même ligne de balayage, et - des moyens pour transformer la valeur Y de chaque bloc de circuit en la valeur Y de la ligne suivante de balayage adjacente au même moment.

Description

La présente invention concerne les systèmes infor-

matiques, et plus particulièrement les circuits permettant de déterminer la position des différents points d'une ligne de balayage devant être affichée sur un afficheur en sortie d'un système informatique. L'un des problèmes majeurs, lorsque l'on utilise les ordinateurs pour produire des affichages graphiques, tient au fait que, pour une seule trame de matière graphique à

restituer sur un tube cathodique, il est généralement néces-

saire de mémoriser une indication de l'information à affi-

cher en chaque position (à chaque pixel) du tube cathodique.

Avec des afficheurs de grandes dimensions et très détaillés, le nombre de pixels sur le tube cathodique peut avoisiner un millier ou plus dans le sens horizontal et un nombre comparable dans le sens vertical, donnant un total d'environ un million de pixels ou plus pour lesquels on doit mémoriser une information. Dans les systèmes préférentiels, on peut produire un certain nombre de couleurs différentes sur le tube cathodique, chacun des pixels comportant huit bits d'information numérique spécifiant la couleur particulière à produire en sortie. En conséquence, il faut mémoriser environ huit millions de bits d'information pour chaque

trame à représenter en sortie.

Il faut non seulement donner l'information de couleur pour chaque pixel de chaque trame de l'affichage, mais encore, lorsque l'on produit des affichages graphiques, le procédé habituel pour déterminer les formes des figures nécessite l'application de divers algorithmes aux données permettant de conformer ces figures. Si ces informations sont gérées par le logiciel du système, le calcul des positions de chaque point à afficher et la détermination des

données à afficher en ce point ralentissent le fonction-

nement du système à tel point que des fonctions telles que l'animation sont pratiquement impossibles à réaliser. Par exemple, si l'on veut restituer sur l'afficheur de sortie un polygone, il est nécessaire de déterminer chaque extrémité de chaque ligne horizontale constituant le polygone, car les informations sont délivrées à l'afficheur ligne d'affichage par ligne d'affichage. Dans les systèmes de l'art antérieur, cette détermination des extrémités de chaque ligne à balayer

sur l'afficheur en sortie nécessitait une exécution logi-

cielle par l'unité centrale de traitement pour calculer les valeurs d'extrémité de chaque ligne de balayage de chaque forme graphique à restituer. De telles configurations

accroissent le temps nécessaire pour restituer l'image gra-

phique à un tel point qu'il en résulte un ralentissement

notable de l'affichage.

Pour cette raison, il a été proposé divers systèmes utilisant le matériel pour accélérer ces opérations. L'un des procédés permettant d'accélérer l'opération utilise en sortie deux tampons de trame, l'un des tampons étant chargé pendant que l'autre est exploré pour affichage. Un tel système accroit notablement la vitesse de fonctionnement mais nécessite pratiquement deux fois plus de mémoire pour

le stockage des données.

C'est pourqoi l'un des buts de la présente invention est, à cet égard, d'accélérer le fonctionnement des systèmes

informatiques.

Un autre but de la présente invention est de proposer des circuits permettant de gérer par matériel les manipulations de matière graphique qui, dans le cas habituel, auraient été

gérées par le logiciel du système informatique.

Un autre but encore de la présente invention est de

proposer des circuits permettant de déterminer les coor-

données X et Y des extrémités des lignes à balayer sur l'af-

ficheur de sortie.

Ces buts, ainsi que d'autres, de la présente invention sont atteints grâce à un nouveau système d'affichage en sortie qui utilise un concept original de représentation des figures graphiques permettant d'obtenir à grande vitesse des

graphiques, tout en n'utilisant qu'un seul tampon d'affi-

chage de sortie.

Pour pouvoir réaliser par matériel la restitution des graphiques, on a constaté que les informations présentées au matériel seront traitées plus rapidement si elles sont essentiellement de même nature, quelle que soit la forme qui doit être tracée sur l'afficheur. Le système est basé sur une définition d'une figure graphique (une forme) selon laquelle on considère que la forme est composée d'un certain

nombre de sous-ensembles qui sont chacun des quadrilatères.

On prévoit des circuits pour afficher rapidement des images formées de quadrilatères, en ne gérant que les informations relatives aux quatre sommets de ces quadrilatères. Ces quadrilatères peuvent tous être gérés de la même manière par

le matériel de restitution graphique et recombinés sur l'af-

ficheur de manière à restituer la forme voulue.

Le système fractionne les quadrilatères en sous-ensembles constitués de couples de segments de droite qui sous-tendent une surface trapézoïdale à restituer sur l'afficheur de sortie. On détermine alors les coordonnées X et Y des deux extrémités de chaque ligne de balayage de chaque trapèze. La présente invention a pour objet des circuits qui déterminent en même temps l'une et l'autre extrémité de chaque ligne de balayage située à l'intérieur d'une figure en forme de

quadrilatère à afficher en sortie.

Le système et les circuits de la présente invention sont conçus de manière à sélectionner la décomposition optimale d'une forme pour que l'opération puisse être exécutée le

plus rapidement possible. Par exemple, si une forme à décom-

poser ne s'étend que partiellement à l'intérieur d'une

fenêtre de cadrage et partiellement au-dessous ou bien au-

dessus de la fenêtre de cadrage, l'opération sera exécutée plus rapidement si la portion située hors de la fenêtre de cadrage n'a pas besoin d'être traitée. Ceci peut être obtenu si la décomposition peut s'exécuter du haut vers le bas ou bien du bas vers le haut. En outre, la mémoire vive utilisée dans les systèmes informatiques est généralement divisée en

partitions appelées "pages", et des accès mémoire à l'inté-

rieur d'une même page prennent moins de temps que si l'on doit aller d'une première adresse dans une première page à une seconde adresse dans une autre page (c'est-à-dire si l'on doit franchir une frontière de page). Si l'opération a lieu en remontant depuis le bas, on devra traverser moins de frontières de page si le traitement d'une ligne de balayage donnée s'exécute de la droite vers la gauche, plutôt que de la gauche vers la droite comme cela est habituellement le cas. En traversant moins de frontières de page, on permet

également un fonctionnement plus rapide.

La décomposition et le traitement des lignes de balayage permis par le système de la présente invention et par sa mise en oeuvre ont lieu de la gauche vers la droite ou bien de la droite vers la gauche, et de haut en bas ou de bas en haut. Les circuits sont également capables de déterminer le point de départ et le point final de chaque ligne de balayage même si la figure est formée de segments de droite formant entre eux des intersections. L'aptitude des circuits

de la présente invention a délivrer les coordonnées rectan-

gulaires permet des transferts rapides d'informations gra-

phiques vers un afficheur de sortie.

A cet effet, l'invention propose un circuit pour déter-

miner les valeurs X de chaque extrémité d'une suite de lignes horizontales reliant un couple de segments de droite dont chacun est défini par un couple de sommets, l'aire définie par les lignes horizontales devant être présentée

sur un afficheur de sortie d'un système informatique, carac-

térisé en ce qu'il comprend.: des moyens pour déterminer la variation de la valeur X entre les sommets d'un premier segment de droite; des moyens pour déterminer la variation de la valeur X entre les sommets d'un second segment de droite; des moyens pour déterminer la variation de la valeur Y entre les sommets du premier segment de droite; des moyens pour déterminer la variation de la valeur Y entre les sommets du second segment de droite; des moyens pour déterminer si la pente du premier segment de droite est supérieure à l'unité; des moyens pour déterminer si la pente du second segment de droite est supérieure à l'unité; des moyens pour établir, pour le premier segment de droite, une valeur d'erreur égale à la plus grande des variations de X et de Y entre les sommets; des moyens pour établir, pour le second segment-de droite, une valeur d'erreur égale à la plus grande des variations de X et de Y entre les sommets; des moyens pour incrémenter la valeur du terme X ou Y de plus grande variation entre les sommets à partir d'une position initiale de ce terme pour le premier segment de droite; des moyens pour incrémenter la valeur du terme X ou Y de plus grande variation entre les sommets à partir d'une position initiale de ce terme pour le second segment de droite, les positions initiales de chacun des segments de droite ayant la même valeur Y; des moyens pour retrancher de l'erreur, pour le premier segment de droite, la moindre des variations des termes X ou Y avec chaque incrément du terme X ou Y présentant la variation la plus importante entre les sommets, jusqu'à ce que l'erreur atteigne zéro; des moyens pour retrancher de l'erreur, pour le second segment de droite, la moindre des variations des termes X ou Y avec chaque incrément du terme X ou Y présentant la variation la plus importante entre les sommets, jusqu'à ce que l'erreur atteigne zéro; des moyens pour incrémenter le terme X ou Y présentant la moindre variation entre les sommets du premier segment de droite en réponse au terme d'erreur devenant zéro pour le premier segment de droite; des moyens pour incrémenter le terme X ou Y présentant la moindre variation entre les sommets du second segment de droite en réponse au terme d'erreur devenant zéro pour le second segment de droite; et des moyens pour poursuivre l'opération jusqu'à ce que les valeurs X et Y atteintes par incrémentation soient égales aux valeurs X et Y du sommet

terminal pour ce segment de droite.

Il est de préférence en outre prévu des moyens pour interrompre le fonctionnement des premiers moyens pour incrémenter la valeur du terme X ou Y de plus grande variation entre les sommets pour le segment de ligne pour lequel le terme d'erreur atteint zéro tant que le terme d'erreur pour l'autre segment de droite n'a pas atteint zéro. Selon un autre aspect de la présente invention, il est proposé un circuit pour déterminer les valeurs X de chaque extrémité d'une suite de lignes horizontales de balayage reliant un couple de segments de droite dont chacun est défini par un couple de sommets, les lignes horizontales de

balayage définissant une aire à restituer sur un péri-

phérique de sortie d'ordinateur, caractérisé en ce qu'il comprend: un premier et un second bloc de circuit, chacun

de ces blocs de circuit comprenant des moyens pour déter-

miner la pente d'un segment de droite et des moyens pour déterminer, en fonction de la pente, les valeurs X de début et de fin pour chaque segment de droite de chaque ligne de balayage de l'aire à restituer; des moyens pour faire commencer à fonctionner les deux blocs de circuit sur la même ligne de balayage; et des moyens pour transformer la valeur Y de chaque bloc de circuit en la valeur Y de la

ligne suivante de balayage adjacente au même moment.

Les buts et caractéristiques de l'invention que l'on a indiqués, ainsi que d'autres, apparaîtront clairement à

l'homme du métier à la lecture de la description détaillée

ci-dessous, faite en référence aux diverses figures des

dessins, sur lesquelles on a désigné par les mêmes réfé-

rences, d'une vue à l'autre, les éléments semblables.

La figure 1 est une représentation d'une forme graphique divisée en deux quadrilatères qui, lorsqu'ils sont affichés

séparément sur un périphérique de sortie d'ordinateur, pro-

duisent la forme d'origine complète.

Les figures 2A à 2D sont des illustrations de la forme

d'un quadrilatère simple décomposé en segments de lignes.

La figure 3 est un schéma par blocs illustrant un système de sortie graphique pour ordinateur, réalisé conformément

aux enseignements de la présente invention.

La figure 4 est une illustration du fonctionnement d'une

partie du circuit de la présente invention.

La figure 5 est un diagramme de circuit illustrant une

manière de mettre en oeuvre la présente invention.

Notations et nomenclature

Certaines parties des descriptions détaillées qui vont

suivre sont présentées en termes d'algorithmes et de représentations symboliques d'opérations effectuées sur des

bits de données dans une mémoire d'ordinateur. Ces descrip-

tions algorithmiques et ces représentations sont les moyens utilisés par les hommes du métier de l'informatique pour exposer de la manière la plus efficace leurs réalisations à

d'autres hommes du métier.

Dans le cas présent, comme d'ailleurs dans le cas géné-

ral, un algorithme est conçu sous la forme d'une séquence autonome d'étapes conduisant à un résultat voulu. Les étapes sont de celles qui nécessitent des manipulations physiques de quantités physiques. Généralement, bien que cela ne soit pas nécessaire, ces quantités prennent la forme de signaux

électriques ou magnétiques pouvant être mémorisés, transfé-

rés, combinés, comparés et manipulés de toute autre manière.

Il s'est révélé commode certaines fois, principalement parce qu'il s'agit là d'un usage répandu, de se référer à ces

signaux en termes de "bits", "valeurs", "éléments", "sym-

boles", "caractères", "nombres", etc. On gardera cependant à

l'esprit le fait que tous ces termes, et les termes sembla-

bles, doivent être associés aux quantités physiques appro-

priées et ne sont que des désignations commodes appliquées à

ces quantités.

Par ailleurs, les manipulations exécutées sont souvent

désignées par des termes, tels que "addition" ou "compa-

raison", qui sont généralement associés à des opérations mentales exécutées par l'homme. Cependant, dans la plupart des cas il ne sera ni souhaitable ni nécessaire de recourir aux aptitudes de l'homme pour les opérations qui seront décrites ci-dessous à propos de la présente invention; ces opérations sont des opérations exécutées en machine. Pour exécuter les opérations de la présente invention, on peut utilement employer des machines telles que des ordinateurs universels ou autres appareils semblables. Dans tous les cas, on gardera à l'esprit la distinction entre le procédé permettant de faire exécuter des opérations à un ordinateur

et le procédé de calcul proprement dit. La présente inven-

tion concerne des étapes de procédé permettant de faire fonctionner un ordinateur afin de lui faire traiter des signaux physiques électriques ou autres (par exemple méca-

niques ou chimiques) pour produire d'autres signaux phy-

siques voulus.

La présente invention concerne également un dispositif

pour exécuter ces opérations. Ce dispositif peut être réa-

lisé spécialement pour les besoins de l'invention, -ou bien il peut être constitué d'un ordinateur universel activé sélectivement ou reconfiguré par un programme informatique mémorisé dans cet ordinateur. Les algorithmes que l'on présentera ici ne sont pas propres à un ordinateur ou dispositif particulier. En particulier, on pourrait utiliser diverses machines universelles avec des programmes écrits conformément aux enseignements qui seront exposés ici, ou bien il pourrait se révéler plus commode de réaliser un dispositif plus spécialisé pour exécuter les étapes de procédé requises. La structure nécessaire à ces diverses

machines découlera de la description que l'on va donner

ci-dessous.

Description du mode de réalisation préféré

Lors de la conception des systèmes informatiques, on

s'est aperçu que l'affichage des images graphiques ralen-

tissait notablement le fonctionnement de la plupart des machines. Ceci vient du fait que la quantité d'informations que doit traiter l1ordinateur pour chaque trame à restituer sur l'afficheur en sortie est très élevée, et du fait que la manipulation de ces informations pour pouvoir restituer l'image graphique nécessite une utilisation démesurée de

l'unité centrale de traitement.

Ceci est particulièrement vrai pour un système utilisant une interface comprenant des "fenêtres" multiples sur son

- affichage de sortie. Dans un tel système, on place simul-

tanément plusieurs programmes dans des parties de la mémoire, ces programmes étant disponibles à tout moment. Les informations textuelles et graphiques en sortie de chacun de ces programmes doivent apparaître sur l'afficheur de sortie

à l'intérieur d'un ensemble donné de frontières prédé-

terminées appelées "fenêtre" ou "fenêtre de cadrage". Chaque fenêtre peut couvrir d'autres fenêtres, la "fenêtre en

avant-plan" conrrespondant au fichier actif en cours. Géné-

ralement, l'utilisateur de l'ordinateur ne manipule le pro-

gramme qu'une seule fenêtre à la fois, mais peut basculer rapidement sur un programme se trouvant dans une autre fenêtre afin de travailler avec ce programme. En général, les fenêtres nécessitent beaucoup plus de mémoire et de

temps pour leur manipulation que pour les opérations n'im-

pliquant pas de fenêtres.

Le système dont fait partie la présente invention accélère l'affichage infographique en gérant par matériel la plupart des opérations, de sorte que les informations sont instantanément disponibles. Pour permettre l'utilisation du matériel pour la mise en oeuvre de la restitution des graphiques, le système fractionne en quadrilatères les images graphiques à restituer sur l'affichage, quadrilatères qui peuvent tous être gérés de la même manière par le

matériel. Le système prend ces quadrilatères et les frac-

tionne à nouveau pour donner des segments de droite qui sous-tendent les lignes de balayage correspondantes à restituer sur l'afficheur de sortie, les différentes lignes

de balayage reconstituant finalement un trapèze. Les coor-

données X et Y des deux extrémités de chaque ligne de balayage sont alors déterminées par les circuits de la

présente invention. Le système prend ces coordonnées rectan-

gulaires et les traduit en lignes de balayage série qui peuvent être mémorisées dans un tampon de trame et affiché

sur un afficheur de sortie.

La figure 1 est une représentation d'une forme graphique divisée en deux quadrilatères 8 et 9 qui, lorsqu'ils sont individuellement affichés sur un périphérique de sortie d'ordinateur, donnent la forme originelle complète. Bien que la forme illustrée figure 1 soit simple, l'homme du métier comprendra que l'on peut restituer des formes dont la complexité varie à l'infini à condition de choisir un nombre

suffisamment important de petits quadrilatères individuels.

En fait, le système de la présente invention a été utilisé pour restituer des formes an.imées tridimensionnelles très

complexes de nature.

La figure 3 illustre sous forme de schéma par blocs un système de sortie graphique 10 réalisé conformément à la présente invention, qui peut être utilisé avec un système informatique universel. Le système 10 comporte une logique d'interfaçage de bus 12 qui reçoit de l'unité centrale de traitement du système informatique (non représentée sur les figures) des informations concernant la forme graphique que l'on souhaite afficher. La logique d'interfaçage de bus 12 reçoit des informations sur une ligne d'adressage qui indique l'endroit particulier du système 10 o l'on devra transférer la donnée en entrée. La logique d'interfaçage de bus 12 reçoit sur une ligne d'entrée des données les données

utiles telles que la description de la couleur. La logique

d'interfaçage de bus 12 reçoit également, sur une ligne de commande, un signal de commande indiquant la manière dont on

devra traiter les informations.

Lorsque l'on reconstruit des représentations graphiques à partir de quadrilatères conformément aux enseignements de la présente invention, les informations d'entrée comportent les coordonnées de l'aire rectangulaire qui définit la fenêtre particulière dans laquelle doit apparaître l'information affichée, les coordonnées (sommets) du quadrilatère et les données de couleur relatives à chaque quadrilatère. Les données de couleur qui doivent être présentées à l'affichage du quadrilatère sont mémorisées dans un étage 22 de routage

de données et d'interfaçage mémoire. Les sommets du quadri-

latère et les informations concernant la fenêtre de cadrage sont mémorisés dans un circuit d'étagement des coordonnées 14 qui comportent un matériel effectuant les comparaisons des informations incidentes par des moyens bien connus de la technique antérieure tels que des registres et des circuits

à portes.

Les comparaisons effectuées comportent la comparaison de la valeur X de chaque sommet à la valeur X de chacun des autres sommets, la comparaison de la valeur Y de chaque sommet à la valeur Y de chacun des autres sommets et la comparaison de chacune des valeurs X et Y des différents sommets aux valeurs X et Y des bords de la fenêtre de

cadrage dans laquelle doivent être présentées les informa-

tions. Comme ceci est réalisé par matériel, les informations

sont immédiatement disponibles pour utilisation par le sys-

tème 10, sans aucune perte de temps d'horloge système.

Les informations relatives aux sommets du quadrilatère et

à la fenêtre de cadrage disponibles dans le circuit d'étage-

ment des coordonnées 14-sont appliquées à un étage de sé-

quencement des coordonnées 16 dans lequel le quadrilatère est décomposé en une série de sous-ensembles dont chacun est

formé de deux segments de droite du quadrilatère d'origine.

Chacun de ces sous-ensembles est choisi de manière que les segments de droite définissent une aire du quadrilatère qui

puisse être tracée par une série de lignes de balayage hori-

zontales parallèles, avec pour chacune une valeur X de début se trouvant sur l'un des segments de droite et une valeur X de fin se trouvant sur l'autre segment de droite. Pour l'essentiel, les deux segments de ligne définissent un

trapèze comprenant autant de lignes de balayage Y (hori-

zontales) que possible, compte tenu de la forme du quadri-

latère. Lorsque toute les lignes de balayage de tout les

sous-ensembles seront restitués sur l'afficheur, le quadri-

latère sera défini en totalité.

Les figures 2A à 2B illustrent un quadrilatère isolé

divisé en sous-ensembles conformément à la présente inven-

tion. Le quadrilatère que l'on décompose est illustré sur la figure 2A, et les sous-ensembles de celui-ci sont illustrés sur les figures 2B à 2D. Comme on peut le voir sur la figure 2, chaque sous-ensemble comprend, lorsqu'il est présenté sur un afficheur de sortie, une série de lignes de balayage horizontales qui commencent sur l'un des segments de droite définissant le quadrilatère et se terminent sur un autre

segment de droite. Les lignes de balayage de chaque sous-

ensemble du quadrilatère représentent une partie trapé-

zoïdale du quadrilatère d'origine. Lorsque ces lignes hori-

zontales de tous les sous-ensembles trapézoïdaux sont balayées dans le tampon de trame pour présentation sur l'afficheur de sortie, la forme du quadrilatère est recons-

tituée dans son intégralité sur l'afficheur.

Si l'on revient à la figure 3, après que les quadri-

latères aient été décomposés en sous-ensembles, on détermine dans un étage d'adressage fonctionnel 18 les valeurs X de début et de fin des diverses lignes de balayage Y. Dans le mode de réalisation préféré de la présente invention, ceci est réalisé au moyen de circuits qui déterminent les pixels particuliers constituant les valeurs X de début et de fin de

chaque ligne de balayage située à l'intérieur de la décom-

position en sous-ensembles du quadrilatère. Cet étage d'adressage fonctionnel 18 réalise également une partie du cadrage nécessaire pour adapter les divers quadrilatères aux fenêtres de cadrage, puis transfère les signaux vers un étage générateur de masque 20 qui configure les informations en blocs de seize pixels qui indiquent le début et la fin de chaque ligne de balayage et qui sont utilisés pour adresser

l'étage 22 de routage des données et d'interfaçage mémoire.

Les signaux de génération de masque sont également appli-

qués à un générateur d'adresses linéaires 24 qui traduit les adresses rectangulaires délivrées par l'étage générateur de masque 20 en signaux permettant d'adresser linéairement le tampon de trame pour l'affichage en sortie. On transfère en ce point vers le tampon de l'afficheur de sortie (tampon de trame) les données de couleur relatives au quadrilatère à afficher qui avaient été conservées en mémoire dans l'étage 22. Diverses parties du système que l'on vient de décrire sont exposées plus en détail dans un certain nombre de demandes de brevet en cours de délivrance, appartenant toutes à la Demanderesse et revendiquant la priorité de demandes déposées à la date de priorité de la présente demande et intitulées: Hardware Implementation of Clipping Comparison Logic (Réalisation matérielle d'une logique de comparaison de cadrage), aux noms de Chris Malachowsky et Curtis Priem, Method and Apparatus for Drawing in any Direction to Minimise Page Crossings (Procédé et dispositif pour effectuer des traçages en tous sens en minimisant les changements de page), aux noms de Chris Malachowsky et Curtis Priem, Clipping Utilizing Test Window (Cadrage utilisant une fenêtre de test), aux noms de Chris Malachowsky et Curtis Priem, Method and Apparatus for Controlling Index Register in a * Graphic Subsystem (Procédé et dispositif de contrôle du registre d'index dans un sous-système graphique) , aux noms de Chris Malachowsky et Curtis Priem, Method and Apparatus for Sorting Line Segments for Display and Manipulation by a Computer System (Procédé et dispositif de tri de segments de droite pour affichage et manipulation par un système informatique), aux noms de Chris Malachowsky et Curtis Priem, Method and Apparatus for Translating Rectilinear Information into Scan Line Information for Display by a Computer System (Procédé et dispositif de traduction d'informations rectangulaires en informations de lignes de balayage pour affichage par un système informatique), aux noms de Chris Malachowsky et Curtis Priem, et Method and apparatus for Decomposing a Quadrilateral Figure for Display and Manipulation by a Computer System (Procédé et dispositif de décomposition d'un quadrilatère figuré pour affichage et manipulation par un système

informatique), au nom de Chris Malachowsky.

La description de la présente invention, elle, concerne

le dispositif et le procédé permettant de déterminer les

extrémités de chaque ligne horizontale de chaque sous-

ensemble trapézoïdal du quadrilatère qui devra être produit en bout dechaîne sur l'afficheur de sortie, sous forme de lignes de balayage. Bien que la présente invention soit décrite en relation avec le système infographique illustré figure 3, les spécialistes de la technique comprendront qu'elle peut être appliquée, de façon très étendue, à d'autres systèmes destinés à produire des affichages

graphiques en sortie de systèmes informatiques.

Les circuits de la présente invention reçoivent des circuits qui décomposent chaque quadrilatère en signaux d'entrée de sous-ensembles représentant les couples de segments de droite qui sous-tendent une série de lignes horizontales communes devant être affichées sur l'afficheur de sortie du système informatique auquel est associé le système infographique. Ces signaux sont appliqués aux circuits sous la forme des coordonnées rectangulaires des

sommets des segments de droite sous-tendant l'aire trapé-

zoïdale particulière ayant les mêmes valeurs Y. Les circuits délivrant ces signaux sont décrits dans une demande de brevet en cours de délivrance, appartenant à la Demanderesse et revendiquant la priorité d'une demande déposée à la date de priorité de la présente demande et intitulée Method and apparatus for Decomposing a Graphics Images for Display and Manipulation by a Computer System (Procédé et dispositif de décomposition d'images infographiques pour affichage et manipulation par un système informatique), au nom de Chris Malachowsky. Comme les informations de position de ligne délivrées au circuit de la présente invention ne comprennent que les

sommets des segments de lignes définissant les divers sous-

ensembles du quadrilatère, alors que l'afficheur de sortie gère les informations ligne de balayage par ligne de

balayage, il est nécessaire de déterminer les points d'ex-

trémité de chacune des lignes de balayage Y horizontales sous-tendues par les segments de droite afin de pouvoir former sur l'afficheur de sortie les lignes de balayage de

manière à donner le quadrilatère en question. -

Lorsque l'on trace un segment sur un afficheur de sortie tel qu'un tube cathodique, le segment est défini par une

série de pixels situés sur des lignes de balayage adja-

centes. Si le segment à tracer est horizontal, une seule ligne de balayage suffit sur l'afficheur pour tracer le segment, si l'on connait l'adresse du pixel de début et du pixel de fin. Si le segment est vertical, on doit inscrire sur l'afficheur un unique pixel pour chaque ligne d'un certain nombre de lignes de balayage adjacentes. Les segments d'inclinaison intermédiaire entre l'horizontale et la verticale ont un nombre de pixels par ligne de balayage variable en fonction de la pente du segment. Si le segment a une faible pente, on trace un certain nombre de pixels adjacents sur chaque ligne de balayage d'une pluralité de

lignes de balayage adjacentes, jusqu'à achever le segment.

Si les valeurs X de début et de fin de chaque série de pixels adjacents de chaque ligne de balayage sont connues, on peut remplir les pixels sur l'afficheur intercalaires et

achever ainsi le segment.

Il est nécessaire de connaître la position, sur chaque

ligne de balayage, de chacun des segments de ligne défi-

nissant les côtés des trapèzes à balayer sur l'affichage, afin de tracer ces trapèzes. Tel est le cas si l'on veut commencer et finir chaque ligne de balayage et cadrer les lignes de balayage afin de les limiter à une fenêtre de cadrage. S'il y a intersection de la frontière de cadrage et d'un segment de droite, on doit prévoir un procédé pour déterminer la partie de chaque segment de droite qui doit être tracée. Le concept général du circuit de la présente invention consiste à déterminer ces points de début et de

fin de chaque ligne de balayage.

Le circuit de la présente invention comprend deux parties semblables afin de pouvoir gérer en même temps chacun des

deux segments de droite définissant un sous-ensemble. Cha-

cune de ces parties de circuit commence d'abord par l'un des sommets d'un segment de droite, calcule la pente de ce segment de droite, détermine à partir de ce calcul si c'est la valeur X ou la valeur Y du segment qui augmente avec le taux d'accroissement le plus fort, détermine et mémorise une

valeur d'erreur initiale qui devra être décrémentée en fonc-

tion de la pente, et commence à tracer les valeurs à partir d'un premier sommet. On choisit la valeur d'erreur pour

qu'elle soit une mesure de la distance séparant, perpen-

diculairement à l'axe de plus grand déplacement, le trajet

exact du segment de droite des pixels effectivement pro-

duits. Si la valeur de X change plus vite que celle de Y, on incrémente (ou décrémente) d'un pixel chaque pas X, tandis que l'on retranche la variation sur Y de la valeur d'erreur

jusqu'à ce que la valeur d'erreur atteigne ou dépasse zéro.

De cette manière, on détermine la valeur X pour laquelle on doit incrémenter (ou décrémenter) la valeur Y. On mémorise cette valeur X comme valeur X d'extrémité du segment de droite en question, et on incrémente (ou on décrémente) la valeur Y. On mémorise la valeur X rencontrée la première pour la nouvelle valeur Y en tant que valeur X de début pour la nouvelle ligne de valeur de balayage associée à la nouvelle valeur Y. Les opérations continuent de cette manière, avec mémorisation pour chaque valeur Y de la première et de la dernière valeur X rencontrées, jusqu'à

atteindre le sommet d'extrémité du segment de droite.

Du fait que l'on a deux circuits qui fonctionnent de la même manière pour traiter en même temps les deux segments de droite de chaque sous-ensemble d'un quadrilatère, la partie de circuit gérant le premier segment de droite prête à changer de niveau Y attend, lorsqu'elle est prête, que le circuit gérant l'autre segment de droite atteigne le moment o sa valeur Y doit changer. Lorsque ceci a lieu, les valeurs X d'une ligne de balayage complète ont été définies et peuvent être traitées; en conséquence, les deux circuits avancent en même temps à la valeur Y suivante. Le traitement des deux valeurs X de début et des deux valeurs X de fin identifiées pour chacune des lignes de balayage consiste à déterminer la valeur la plus à gauche (minimale) et la plus à droite (maximale) des valeurs X mémorisées à délivrer au

circuit de génération de masque 20 illustré figure 3.

Pour traiter rapidement chaque quadrilatère, lorsque l'on

a atteint l'extrémité d'un segment de droite d'un sous-

ensemble, le circuit charge le segment de droite suivant à traiter. Comme cela est souvent le cas, un segment de droite se termine avant l'autre. Dans un tel cas, on n'a pas besoin de recharger le segment de ligne qui ne se termine pas, et

264079Z

on économise ainsi un temps important.

Le circuit continue à traiter les segments de ligne du quadrilatère jusqu'à achèvement de la figure. A chaque étape, les valeurs produites sont transférées à des circuits permettant de trier les valeurs, afin de déterminer les valeurs réelles de début et de fin des lignes de balayage en fonction du sens de fonctionnement des circuits de la présente invention et de l'application des informations de fenêtre de cadrage. On doit effectuer cette opération de tri parce que, comme souligné plus haut, le système et le

circuit de la présente invention sont conçus pour sélec-

tionner la meilleure manière de décomposer une forme pour que l'opération ait lieu le plus rapidement possible. Par

exemple, si une forme à décomposer ne se trouve que parti-

ellement à l'intérieur d'une fenêtre de cadrage et parti-

ellement au-dessus ou bien au-dessous de cette fenêtre de cadrage, l'opération s'exécutera plus rapidement si l'on n'a pas besoin de traiter la partie se trouvant hors de la fenêtre de cadrage. On peut obtenir ceci si la décomposition peut s'exécuter soit de haut en bas soit de bas en haut. En

outre, si l'opération a lieu de bas en haut, on doit fran-

chir en mémoire un nombre moindre de frontières de page si l'opération s'exécute de droite à gauche que si elle s'exécute de gauche à droite, comme cela est habituellement

le cas. En franchissant un moindre nombre de pages, on as-

sure un fonctionnement plus rapide.

On va donner ci-dessous un algorithme en un pseudo-code semblable au langage de programmation "C', permettant de

réaliser les opérations de la présente invention. L'algo-

rithme utilise une version modifiée de l'algorithme de

Bresenham bien connu; cependant, l'homme du métier com-

prendra qu'il existe de nombreux autres algorithmes de conversion de balayage qui pourraient être aisément adaptés

pour mettre en oeuvre la présente invention.

Dans cet algorithme: - "DeltaX" désigne la variation de X d'un sommet à l'autre, - "DeltaY" désigne la variation de Y d'un sommet à l'autre, - on donne à X comme valeur initiale la valeur du sommet de départ, - on donne à Y comme valeur initiale la valeur du sommet de départ, - "Xterm" est la valeur X du sommet terminal, - "Yterm" est la valeur Y du sommet terminal,

- "abso()" renvoie la valeur absolue des arguments spéci-

fiés, et - "axe principal" désigne soit X soit Y selon que c'est

DeltaX qui est supérieur à DeltaY, ou le contraire.

Initialisation DeltaX = abs(X-Xterm) DeltaY = abs(Y-Yterm) axe principal = ((DeltaY-DeltaX)≥0) ? Y:X pente = ((X-Xterm)"≥0) ? Y:X haut = ((YYterm)≥0) ? 0:1 E =: (Delta(axe principal) "1) cb = Delta(axe principal) [0] /* bit le plus faible */ Boucle principale X débutpixel (X,Y) tant que (X!=Xterm) { E = E - DeltaY si (testX(E,cb,haut)) { finpixel(X,Y) Y = Y + (haut ? 1:-1); X = X + (pente ? 1:-1); début_pixel(X,Y) E = E + DeltaX; }sinon X = X + (pente ? 1:-1); } finpixel(X,Y) Test de boucle principale X testX(e,cb,haut)= (e<0) Il (haut&&(cb==0)&&(e==0) Boucle principale Y début_pixel (X,Y) tant que (Y!=Yterm){ E = E - DeltaX si (testY(E,cb,pente)){ fin_pixel (X, Y) X = X + (pente ? 1:-1); Y = Y + (haut ? 1:-1); début pixel(X,Y) E = E + DeltaY; sinon Y = Y + (haut ? 1:1); ) fin_pixel (X, Y) Test de boucle principale Y testY(e,cb,pente) = (e<0) Il (pente&&(cb==0)&&(e==0) La figure 4 illustre le fonctionnement d'une partie des circuits de la présente invention que l'on vient de décrire pour la gestion d'un segment de droite. Sur la figure 4, on a illustré un segment de droite commençant au sommet (0,5) et se terminant au sommet (4,6). Si l'on met en oeuvre la présente invention, les circuits déterminent d'abord la variation de X entre les deux sommets du segment de droite et la variation de Y entre les sommets, puis détermine à partir de ces variations la pente du segment de droite, détermine l'axe principal (la valeur présentant la variation la plus importante) et rend le terme d'erreur égal à la moitié de la valeur de la variation de X. On choisit cette valeur moitié pour équilibrer les pixels définis par le

circuit pour le segment de droite afin de donner une appa-

rence plus symétrique. A partir de ces valeurs, le traçage commence, avec la valeur de sommet de X mémorisée comme valeur du premier X sur la ligne de balayage pour ce segment de droite. Le circuit décrémente ensuite l'erreur de la valeur de la variation selon Y et teste deux conditions: "le terme d'erreur est-t-il maintenant inférieur à zéro ?" et "la direction de traçage est-t-elle vers le haut et

l'erreur égale à zéro ?".

Si aucune de ces conditions n'est vérifiée, l'opération continue jusqu'à ce que la valeur du terme d'erreur atteigne un point tel que la condition testée devienne vraie,

* c'est-à-dire que le terme d'erreur atteigne ou dépasse zéro.

On mémorise alors la valeur du terme X comme dernière valeur X pour cette ligne de balayage (pour cette valeur Y) de ce segment de droite. L'opération continue pour la valeur Y

suivante, en mémorisant la première valeur X après l'in-

crément comme valeur X de début pour la ligne de balayage, et en ajoutant à nouveau la valeur de la variation de X au terme d'erreur. L'opération continue en suivant la ligne de balayage par accroissement des valeurs X et réduction du terme d'erreur jusqu'à ce que le terme d'erreur atteigne ou dépasse zéro. Ici encore, on mémorise alors la valeur X comme dernière valeur X de la ligne de balayage, on ajoute à nouveau la variation de X au terms d'erreur et on passe à la

valeur Y suivante.

L'opération continue jusqu'à déterminer la valeur X égale à la valeur X terminale pour le segment de droite; on a alors défini la totalité du segment de droite et le circuit peut être initialisé pour un nouveau segment de droite. On notera que, bien que chacune des parties du circuit opère de façon indépendante pour traiter l'un des deux segments de droite, lorsque chaque partie du circuit

qui gère un segment de droite a terminé une ligne de bala-

yage donnée, elle teste si l'autre segment de ligne a été complètement défini pour cette ligne de balayage. Si tel n'est pas le cas, le circuit attend alors que la ligne de balayage ait été finie pour l'autre segment de droite, afin que les deux circuits puissent progresser ensemble et que l'on puisse transférer la définition complète de chaque

ligne de balayage aux étages suivants en une seule fois.

La figure 5 illustre un circuit 30 constituant un mode de

réalisation préféré pour la mise en oeuvre de l'invention.

Le circuit 30 compbrte deux parties essentiellement semblables 32 et 34 dont chacune gère l'un des deux segments de droite. On décrira seulement la partie 32, du fait de cette similitude. Lors de la détermination des valeurs d'extrémité des lignes de balayage, on commence par initialiser les circuits pour chaque segment de droite. Pour réaliser ceci, la partie 32 reçoit, à un premier cycle d'horloge, des valeurs d'entrée représentant les valeurs de X du début et de la fin du premier segment de droite (le segment de ligne A). Ces valeurs sont, respectivement, mémorisées dans des registres 36 et 38 et transférées à des multiplexeurs 40 et 42. Les multiplexeurs 40 et 42

transfèrent les valeurs X à des portes OU EXCLUSIF 44 et 46.

Ces portes OU EXCLUSIF 44 et 46 reçoivent également des valeurs d'entrée ("zéro" ou "un") qui permettent de transférer la valeur X telle quelle ou complémentée, afin de pouvoir soit ajouter soit retrancher les valeurs au moyen d'un additionneur 48. Si, par exemple, on applique un "zéro" à la porte OU EXCLUSIF 44, la valeur sur l'autre entrée de cette porte sera simplement transférée à l'additionneur 48 tandis que, si on applique un "un" à la porte*44, la valeur d'entrée sera complémentée de sorte que il sera facile de la retrancher (en binaire). Pour déterminer la variation de la valeur de X entre le début et la fin, on calcule la différence entre les termes X et, par un multiplexeur 50, on applique pour mémorisation cette différence à un registre 52 de variation de X. Au cycle d'horloge suivant, on applique aux multiplexeurs et 42 les valeurs de Y de début et de fin du segment de droite A; de façon semblable, on détermine la variation de Y au moyen de l'additionneur 48 et on la mémorise à la fois dans un registre de variation de Y 54 et dans un registre

d'erreur 56.

La mémorisation de la valeur de variation de Y dans le registre d'erreur 56 permet de déterminer l'axe principal sans qu'il soit nécessaire de recourir à des circuits additionnels. Ceci est réalisé en transférant à l'additionneur 48 les valeurs conservées dans les registres 52 et 56, en complémentant l'une d'entre elles afin de déterminer, parmi DeltaX et DeltaY, la valeur la plus élevée. Cette valeur la plus élevée est alors divisée par deux en décalant d'une unité vers la droite la valeur dans l'additionneur 48 et en la plaçant dans le registre d'erreur au moyen du multiplexeur 50. Ceci achève l'initialisation du

circuit 32.

Au même moment, le circuit 34 reçoit les valeurs de X et de Y de début et de fin et achève leur initialisation pour l'autre segment de droite à traiter, c'est-à-dire la droite B. Une fois l'initialisation achevée, chacun des circuits 32 et 34 commence à traiter l'information de segment de droite du segment de droite qu'il gère. Si l'on considère seulement le circuit 32, la valeur de X courante pour la ligne A est conservée dans le registre 36. La valeur dans le registre 36 est testée, au moyen d'un comparateur 58, par rapport à la valeur terminale de X mémorisée dans le registre 38. Si les valeurs ne sont pas égales, les multiplexeurs 40 et 42 transfèrent à l'additionneur 48 l'erreur et les valeurs de variation de Y via les portes OU EXCLUSIF 44 et 46, de manière à retrancher de l'erreur la variation de Y. On mémorise dans le registre d'erreur 56 la valeur d'erreur réduite, et le processus continue jusqu'à ce que la valeur d'erreur atteigne ou dépasse zéro. Le rapport entre l'erreur et la valeur zéro est testée par une machine à états 60 qui, lorsque la condition de test est vérifiée, transfère la valeur de X actuelle comme valeur d'extrémité pour cette ligne de balayage Y, provoque l'incrémentation (ou la décrémentation) de la valeur de Y et restaure le registre d'erreur en ajoutant à la valeur d'erreur actuelle une valeur égale à la valeur de la variation de X. Comme on l'a souligné plus haut, lorsque l'un ou l'autre des circuits 32 ou 34 arrive au moment o une valeur de Y doit changer en fonction de la valeur de la pente du segment de droite, le premier des circuits 32 ou 34 qui atteint la valeur de changement le signale à la machine à états 60 et attent que l'autre des deux circuits 32 ou 34 soit également prêt à modifier la valeur de Y. Lorsque tel est le cas, la machine à états délivre des signaux permettant de faire progresser chacun des deux circuits 32 et 34 à la ligne Y suivante. De cette manière, les deux circuits 32 et 34 gèrent la même ligne de balayage Y en même temps, et on peut transférer ainsi en même temps aux étages suivants les

valeurs des deux extrémités d'une ligne de balayage.

Lorsque le circuit 30 de la figure 5 est en train de traiter un segment de droite pour déterminer les valeurs de X des extrémités de la ligne horizontale, et que le segment de droite est un segment de droite avec une pente supérieure ou égale à l'unité, c'est-à-dire correspondant à un angle d'inclinaison de 45 ou plus, le circuit opère, pour l'essentiel, de la même manière. Les valeurs de X de début et de fin de chaque segment de droite sont tout d'abord traitées par chacun des circuits 32 et 34 pour déterminer, dans chacun des cas, une variation de la valeur de X. Les valeurs de Y de début et de fin de chaque segment de droite sont ensuite traitées par chacun des circuits pour déterminer, dans chacun des cas, une variation de la valeur de Y. La variation de valeur de X est ensuite comparée à la variation de valeur de Y pour chacun des deux segments de droite, et l'on donne à l'erreur une valeur égale à la moitié de la variation de la valeur de Y pour chaque segment de droite ayant une pente supérieure à l'unité. Le traitement a ensuite lieu de la même manière que précédemment, en avançant cependant initialement pas à pas suivant les valeurs de Y jusqu'à ce que l'on rencontre une variation de X. Entretemps, un circuit 64 est en train de gérer les valeurs de Y. Le circuit 64 comporte un registre 66 qui, initialement, reçoit et conserve la valeur de Y, un multiplexeur 68 qui reçoit un certain nombre de signaux comprenant la valeur de fin de Y de chaque segment de droite et les valeurs minimales et maximales de cadrage Y, et un registre de fin Y 70. Les valeurs des registres 66 et 70 sont comparés par un comparateur 72 qui est capable de déterminer si une valeur est supérieure, inférieure ou égale à l'autre. Cette configuration peut être utilisée pour déterminer le moment o un segment de droite a atteint son point d'extrémité, et également pour déterminer si la figure

se trouve à l'intérieur de la fenêtre de cadrage.

Le circuit 64 comporte également un registre de cadrage Y 74 qui reçoit en entrée des valeurs représentant les valeurs de cadrage Y maximum ou minimum. Ces valeurs indiquent la position des frontières supérieure et inférieure de la fenêtre de cadrage dans laquelle on doit inscrire le quadrilatère. Le registre de cadrage 74 reçoit l'une de ces valeurs par l'intermédiaire d'un multiplexeur 76 qui laisse passer soit la valeur Y minimum soit la valeur Y maximum de la fenêtre de cadrage, selon le sens dans lequel

l'information est inscrite dans le tampon de trame.

Dans certains cas, une forme particulière à restituer peut se trouver cadrée à la fois sur son bord supérieur et sur son bord inférieur. Le cadrage au bord de début de la forme est déterminé en comparant la valeur initiale Y du registre 66 à la valeur de cadrage de début, qui est appliquée au registre 74 par un multipleur 76. Si, par exemple, l'information est en cours d'inscription en bas de l'écran, la valeur appliquée est la valeur Y de cadrage minimale; si l'on progresse dans l'autre sens, c'est la

valeur Y de cadrage maximale que l'on applique au registre.

Un multiplexeur 78 applique la valeur de cadrage au comparateur 72. Le comparateur de grandeurs 72 délivre alors un signal qui inhibe la restitution tant que la valeur Y ne

se trouve pas & l'intérieur de la fenêtre de cadrage.

La valeur de Y placée dans le registre 70 est la valeur Y de la dernière ligne & tracer dans le trapèze ou la frontière de cadrage Y appropriée, selon la valeur à laquelle on doit terminer entièrement la figure une fois que

la forme se trouve à l'intérieur de la fenêtre de cadrage.

Cette valeur (registre 70) est délivrée par le circuit (multiplexeur 78) qui compare la valeur courante de Y (registre 66) à cette valeur de fin de Y. Dans le cas o la forme s'étend au-delà de la fenêtre de cadrage, la valeur Y de fin est placée dans le registre 70 et comparée dans le comparateur 72 à la valeur Y réelle. De cette manière, on peut déterminer la valeur de fin de la partie de la forme à restituer. Ceci est particulièrement intéressant avec la présente invention, qui est capable d'inscrire les informations dans le tampon de trame aussi bien en allant vers le haut qu'en allant vers le bas (c'est-à-dire dans le sens des Y croissants ou décroissants, respectivement). Ceci permet d'exécuter la conversion de balayage de ligne de telle sorte que les informations visibles (non cadrées) soient traitées les premières lors de

cette opération, avant les informations qui seront cadrées.

On peut faire abstraction de ces dernières informations, ce

qui accroît notablement la vitesse de fonctionnement.

Claims (3)

PREVENDICATIONS

1. Un circuit (30) pour déterminer les valeurs X de chaque extrémité d'une suite de lignes horizontales reliant un couple de segments de droite dcnt chacun est défini par

un couple de sommets, l'aire définie par les lignes hori-

zontales devant être présentée sur un afficheur de sortie d'un système informatique, circuit caractérisé en ce qu'il comprend: - des moyens (32) pour déterminer la variation de la valeur X entre les sommets d'un premier segment de droite, - des moyens (34) pour déterminer la variation de la valeur X entre les sommets d'un second segment de droite, - des moyens (32) pour déterminer la variation de la valeur Y entre les sommets du premier segment de droite, - des moyens (34) pour déterminer la variation de la valeur Y entre les sommets du second segment de droite, - des moyens (32) pour déterminer si la pente du premier segment de droite est supérieure à l'unité, - des moyens (34) pour déterminer si la pente du second segment de droite est supérieure à l'unité, - des moyens (32) pour établir, pour le premier segment de droite, une valeur d'erreur égale à la plus grande des variations de X et de Y entre les sommets, - des moyens (34) pour établir, pour le second segment de droite, une valeur d'erreur égale à la plus grande des variations de X et de Y entre les sommets, des moyens (32) pour incrémenter la valeur du terme X ou Y de plus grande variation entre les sommets à partir d'une position initiale de ce terme pour le premier segment de droite, - des moyens (34) pour incrémenter la valeur du terme X ou Y de plus grande variation entre les sommets à partir d'une position initiale de ce terme pour le second segment de droite, les positions initiales de chacun des segments de droite ayant la même valeur Y, - des moyens (32) pour retrancher de l'erreur, pour le premier segment de droite, la moindre des variations des termes X ou Y avec chaque incrément du terme X ou Y

présentant la variation la plus importante entre les som-

mets, jusqu'à ce que l'erreur atteigne zéro, - des moyens (34) pour retrancher de l'erreur, pour le second segment de droite, la moindre des variations des termes X ou Y avec, chaque incrément du terme X ou Y

présentant la variation la plus importante entre les som-

mets, jusqu'à ce que l'erreur atteigne zéro, - des moyens (32) pour incrémenter le terme X ou Y présentant la moindre variation entre les sommets du premier segment de droite en réponse au terme d'erreur devenant zéro pour le premier segment de droite, - des moyens (34) pour incrémenter le terme X ou Y présentant la moindre variation entre les sommets du second segment de droite en réponse au terme d'erreur devenant zéro pour le second segment de droite, et - des moyens (32,34) pour poursuivre l'opération jusqu'à ce que les valeurs X et Y atteintes par incrémentation soient égales aux valeurs X et Y du sommet terminal pour ce

segment de droite.

2. Le. circuit pour déterminer les valeurs X de chaque extrémité d'une suite de lignes horizontales reliant un couple de segments de droite selon la revendication 1, caractérisé en ce qu'il comprend en outre: - des moyens pour interrompre le fonctionnement des premiers moyens pour incrémenter la valeur du terme X ou Y de plus grande variation entre les sommets pour le segment de ligne pour lequel le terme d'erreur atteint zéro tant que le terme d'erreur pour l'autre segment de droite n'a pas

atteint zéro.

3. Un circuit pour déterminer les valeurs X de chaque extrémité d'une suite de lignes horizontales de balayage reliant un couple de segments de droite dont chacun est défini par un couple de sommets, les lignes horizontales de

balayage définissant une aire à restituer sur un péri-

phérique de sortie d'ordinateur, circuit caractérisé en ce qu'il comprend: - un premier (32) et un second (34) bloc de circuit, chacun de ces blocs de circuit comprenant des moyens pour déterminer la pente d'un segment de droite et des moyens pour déterminer, en fonction de la pente, les valeurs X de début et de fin pour chaque segment de droite de chaque ligne de balayage de l'aire à restituer, - des moyens pour faire commencer à fonctionner les deux blocs de circuit sur la même ligne de balayage, et des moyens pour transformer la valeur Y de chaque bloc de circuit en la valeur Y de la ligne suivante de balayage

adjacente au même moment.

2C