FR 2542470 A1 19840914 FR 8403682 A 19840309 2542470. "Système de machine à calculer à multiprocesseur pour con- vertir des éléments-objets définis dans une structure de données hiérarchique en une représentation visuelle colorée. La présente invention concerne un système de machine à calculer à multiprocesseur pour convertir des éléments-objets définis dans une structure de données hiérarchique en une représentation visuelle, ce système comportant une connexion pour un processeur central (host) pour recevoir sur cette connexion l'information des éléments-objets en vue de la stocker dans une mémoire de réception, un système de processeurs de points alimenté par la mémoire de réception pour calculer, pour chaque image, à partir de la structure de données des éléments-objets, les informations de points d'image à fournir à une connexion pour un élément de visualisation Pour l'état connu de la technique, on peut mentionner le livre de W M Newman et R F Sproull, Principles of interactive computer graphics, ISBN 0-07-046338-7, Mc Graw Hill, 1981 Ce livre donne, entre autres choses, aux pages 137 à, 142, des structures de données organisées dep 1 luieu'smawères,et sur les Fig 10 et 11 une structure de données hiérar- chique De plus, la page 421, Fig 26-4, indique comme étant convenable un système de multiprocesseur qui comporte, entre autres, un processeur central, un multiplicateur de matrice et un processeur de représen- tation visuelle. L'appendice 1, pages 481 à 489, donne un aspect général des vecteurs et des matrices Les pages 315 à 320 indiquent la formation et l'utilisation de courbes dites de Bezier qui seront discutées plus loin avec plus de détails Par éléments-objets, on entend des modèles quantitatifs d'entités spatiales ou planes, comme des plans, des corps et des structures plus compliquées Ces éléments-objets seront expliqués avec plus de détails avec référence aux Fig la à le. L'avantage d'une structure hiérarchique réside dans une capacité de modification simple d'un élément- objet situé à un bas niveau de la structure hiérar- chique sans que la structure d'ensemble se modifie, et le plus souvent dans la possibilité d'utilisation multiple à un niveau plus élevé d'éléments-objets qui sont définis à un niveau plus bas Cette dernière particularité se présente notamment pour une situation bidimensionnelle parce que, dans ce cas, lors de la visualisation, les transformations qui apparaissent sont exclusivement linéaires Le processeur central fournit a présent des relations spatiales entre les éléments-objets, comme des positions relatives ou absolues Le processeur central peut aussi fournir de nouveaux éléments-objets ou éliminer des éléments- objets existants Selon la technique connue, un problème que l'on rencontre souvent a trait au fait qu'il faut d'abord déterminer quelle partie des élé- ments-objets tombe dans le cadre de visualisation, cette opération étant qualifiée de "clipping" Il apparaîtra que selon les procédures développées ci- après, ceci n'est déterminé qu'à la fin du traitement du point en question, ce point étant considéré transi- toirement comme étant le centre d'un système de coordonnées. Dans un cas simple, la génération des points d'image peut être en synchronisme avec l'analyse de l'image dans l'élément de visualisation L'élément de visualisation peut, par exemple, fonctionner sur base d'un tube de télévision analysé suivant des lignes; il peut toutefois aussi s'agir d'une matrice d'éléments à plasma ou de diodes électroluminescentes en plusieurs couleurs L'invention se limite à des éléments de visualisation entièrement analysés, pour lesquels, pour chaque point d'image, la décision "couleur" ou "pas de couleur" doit être prise lorsque c'est le tour du point d'image en question L'invention ne concerne en effet de succession de l'analyse des points d'image peut être entièrement quelconque. L'invention a pour but de réaliser une gé- nération de points d'image rapide, le tout avec un en- semble de processeurs simples et sans qu'un trafic très intensif soit nécessaire entre le processeur central et l'ensemble des processeurs, ou entre les divers proces- seurs L'invention réalise ce but par le fait qu'elle est caractérisée en ce qu'un niveau élémentaire de la structure de données comporte des éléments-objets en tant que polygones de Bezier définis exclusivement par les points des polygones décrivant leurs côtés, qui sont reliés pour chaque niveau hiérarchique plus élevé sui- vant par des relations spatiales (transformations rela- tives) en des éléments hiérarchiquement supérieurs, jus- qu'à ce qu'à un niveau hiérarchique de tête on obtienne une structure de corrélation bidimensionnelle qui est stockée au moyen d'éléments objets et de relations spa- tiales planaires dans la mémoire de réception, que le système de processeurs de -points comporte un montage (array) de processeurs de points connectés en parallèle qui sont connectés par l'intermédiaire d'un réseau d'en- trée à la connexion pour la mémoire de réception, que chaque processeur de points fonctionne comme générateur de points d'image pour un groupe de points d'image sur l'élément de visualisation, que chaque point d'ima- ge est assigné à un des processeurs de points et que les groupes forment entre eux un motif de positionne- ment régulier, que chaque processeur de points fonc- tionne d'une part, comme processeur de structure pour dans le cas d'un point d'image prédéterminé, déter- miner successivement à partir du niveau hiérarchique de coiffagé de la structure de données, par niveau, les coordon- nées d'application associés dans l'élé- ment-objet de ce niveau jusqu'à ce que ou bien, pour l'élément-objet en question, une non-pertinence pour le point d'image en question soit détectée, ou bien un ou plusieurs éléments-objets élémentaires soient atteints, que d'autre part, des éléments-objets élémentaires définis sous la forme des dits polygones étant donnés, chaque processeur de points fonctionne comme un processeur de polygone pour, à chaque point d'image prédéterminé, calculer pour chaque polygone pertinent une information binaire intérieur/extérieur en vue de former une liste valable pour ce point d'image, d'éléments-objets élémentaires et d'infor- mations de couleur associées pour les éléments-objets pour lesquels l'information est "intérieur", et qu'en outre chaque processeur de points fonctionne comme processeur de priorité afin de déterminer, à partir de la dite liste, au moyen de l'information de priorité valable pour chaque élément-objet élémentaire, la couleur à mettre en oeuvre pour ce point d'image, et que la connexion pour l'élément de visualisation comporte un multiplexeur pouvant être analysé de manière cyclique pour recevoir les signaux de couleur formés par les processeurs de points au moyen d'une analyse pouvant être activée de manière cyclique. L'invention est basée sur l'idée qu'il est avantageux de répéter, pour chaque point d'image, chaque fois des calculs similaires et simples, et qu'à cet effet, on peut se contenter de composants moins compliqués et par ailleurs plus spécifiques et donc- plus rapides De plus, le traitement débute à partir du niveau le plus élevé de la structure de données hiérar- chique; il s'avère que pour cette direction de trai- tement, on obtienne une structure plus simple dans les traitements Ce qui précède est d'autant plus vrai que chaque processeur de points ne travaille que sur une image partielle, c'est-à-dire sur une partie de l'image totale, de sorte que la parallélisation est réalisée jusqu'à un stade très avancé et que la vitesse de traitement en est également accrue. Il est avantageux que dans le processeur de polygones, pour chaque côté de polygone, une structure de décision itérative soit mise en oeuvre, de sorte que pour chaque pas itératif, un parallélogramme engendré par un côté de polygone ou une partie de côté de polygone se trouvant au moins partiellement dans l'image soit comparé à l'endroit du point d'image réel au sujet duquel il faut décider, que pour le point d'image à l'intérieur du parallélogramme, le côté du polygone ou la partie de côté du polygone soit divisé jusqu'à ce que, dans un pas itératif élémentaire, la coïncidence du point d'image et de la diagonale soit éventuellement constatée (ATSIDE), mais que pour le reste, lorsque le point d'image réel se trouve en dehors du parallélogramme en question, ou lorsque le point d'image et la diagonale ne coincident pas dans un pas itératif élémentaire, le nombre de points d'inter- section de tous les côtés du polygone en question avec une droite semiinfinie passant par le point d'image réel est compté et, dans le cas d'un nombre impair, une information "enfermé" (INSIDE) est formée pour ce point d'image, l'information "intérieur" étant formée à partir de l'information "enfermé" Ceci semble 9 tre une itération facile à réaliser, certainement lorsque, dans le cas de côtés de polygone droits, la division est ramenée à une division par deux; l'itération converge en moyenne très rapidement Dans ce cas, il est avan- tageux -que l'information "intérieur" mentionnée soit également formée à partir de la dite coïncidence, mais que pour le reste ce soit l'information "extérieur" mentionnée Ainsi, le contour du polygone est considéré comme étant situé à l'intérieur, mais ce contour peut aussi être considéré comme étant situé à l'extérieur. Une réalisation avantageuse est obtenue pour un élément de visualisation dans lequel les points d'image sont organisés selon des rangées et des colonnes, les côtés du dit parallélogramme étant parallèles à des rangées ou à des colonnes et la dite droite semi-infinie étant parallèle à un des côtés Ceci simplifie les essais dans les processeurs de points. Il est avantageux, lorsque l'ensemble des processeurs de points est divisé en ensembles partiels et qu'une mémoire auxiliaire est prévue pour chaque ensemble partiel, que dans un ensemble partiel, les processeurs de points travaillent sur une image par- tielle commune, qu'entre la mémoire de réception et les mémoires auxiliaires qui y sont connectées par l'inter- médiaire d'un démultiplexeur analysable de manière cyclique, un processeur de réduction soit connecté pour, à partir de la structure de données hiérarchique, successivement à partir du niveau hiérarchique de tète déterminer niveau par niveau, la pertinence de l'élément-objet en question pour l'image partielle correspondante jusqu'à ce qu'une non- pertinence soit détectée ou jusqu'a ce que les éléments-objets élémen- taires soient atteints pour ne transférer à la mémoire auxiliaire en question que la partie de la structure de données pour laquelle au moins un élément-objet élémen- taire qui y est relié est détecté comme pertinent y compris l'ensemble des éléments-objets élémentaires détectés comme pertinents La parallélisation est ainsi pour ainsi dire réalisée en deux niveaux, de sorte qu'une accélération importante est malgré tout obtenue pour des frais limités La partie de la structure de données hiérarchique à traiter par chaque processeur de points n'est à présent que limitée, de sorte que la 2542470 i vitesse de traitement par les processeurs de points augmente fortement La grandeur limitée de la partie de la structure de données à traiter permet aussi de la multiplier sans inconvénient: un élément-objet déter- miné peut simultanément être présent dans plusieurs mémoires auxiliaires Grâce à la mise en oeuvre de mémoires auxiliaires, chaque processeur de points ne doit plus que rarement faire appel à la mémoire de réception Des lectures compétitives et imprévisibles à partir des processeurs de points dans la mémoire de réception sont de ce fait évitées Les processeurs de points n'ont pas non plus besoin de communication entre eux, ce qui simplifie la structure de la fourniture d'information: il n'y a par exemple aucun mécanisme d'interruption entre les processeurs de points, ni aucun arbitrage entre différents demandeurs, ni aucun risque de blocage réciproque entre différents demandeurs. Il est avantageux que la dite pertinence soit régie par une coïncidence au moins partielle de l'image partielle en question et d'une zone rectangulaire entourant un élément-objet et stockée dans la mémoire de réception pour chaque élémentobjet de la structure de données De tels rectangles entourants conduisent à nouveau à un traitement de calcul simple, de sorte que le traitement peut 8 tre réalisé plus rapidement. Il est avantageux qu'entre l'ensemble de processeurs de points et l'élément de visualisation, soit connecté un tampon d'image double comportant une partie de réception destinée à recevoir des processeurs de points, de l'information couleur concernant une image entière et une partie d'émission destinée à contenir l'information couleur concernant une image entière et à la transmettre à l'élément de visuali- sation jusqu'à ce que la partie de réception, après avoir été complètement remplie -de l'information d'une image, soit commutée en partie d'émission et la partie qui jusqu'alors fonctionnait comme partie d'émission, en partie de réception Une représentation visuelle continue peut ainsi être fournie à un observateur parce qu'une image une fois stockée peut être analysée plusieurs fois Des effets de papillotement et des effets analogues sont alors évités. Il est avantageux que dans la mémoire de réception, chaque élément-objet élémentaire soit pourvu d'une indication de priorité Ceci est d'une réali- sation simple La donnée de priorité peut être un nombre, les nombres inférieurs précédant par exemple les nombres supérieurs. Pour -visualiser une structure de données organisée de manière tridimensionnelle dans une pro- jection centrale ou une projection parallèle, il est avantageux que, pour les éléments-objets élémentaires qui y sont définis sous la forme des dits polygones, une indication de priorité implicite soit donnée par les paramètres de l'équation du plan contenant qui contient localement l'élément-objet élémentaire en question et que dans le cas de polygones chevauchant localement après projection sur le tableau, les valeurs paramétriques des points d'intersection des plans contenants localement associés avec la-droite paramé- trisée dans le sens de la projection et par le point de projection en question, donnent par comparaison, explicitement la priorité relative Cet essai de comparaison ne doit être activé dans les processeurs de priorité que lorsqu'un chevauchement est détecté dans les processeurs de polygones de structure entre deux éléments-objets élémentaires De plus, dans ce cas, aucune limitation n'est imposée dans le sens o des polygones concaves ou par ailleurs, des polygones se 2542470. coupant mutuellement ne pourraient pas se présenter. L'invention met en pratique, à l'aide de moyens simples, des traitements concernant des points qui étaient jusqu'à présent difficiles à réaliser, comme os par exemple la combinaison (le mélange) de diverses cou- leurs selon une règle de priorité Dans une situation bidimensionnelle, la priorité ne doit plus être déter- minée par une définition d'ordre de succession, mais peut être choisie d'une manière indépendante pour chaque élément-objet élémentaire Dans une situation tridimen- sionnelle, aucun algorithmique de triage difficile à réaliser n'est nécessaire au total entre les éléments- objets, mais les priorités peuvent être dérivées de ma- nière simple par un calcul organisé point par point De plus, des algorithmes anti-alias peuvent être facile- ment réalisés par observation d'un groupe local de points d'image. COURTE DESCRIPTION DES FIGURES L'invention sera décrite en plusieurs par- ties, a savoir, dans l'ordre: la structure de données hiérarchiques des éléments-objets, les traitements phé- noménologiques successifs sur ces éléments-objets, une description globale du système de machine à calculer, les traitements effectués dans le-processeur de réduction, les traitements dans le processeur de polygones, la réalisation d'un processeur de polygones et des complé- ments pour une situation tridimensionnelle. La Fig la illustre quelques exemples d'é- léments-objets élémentaires délimités par des lignes droites; Les Fig lb à le illustrent des détails concernant la formation des polygones dits de Bezier dont les cÈtés peuvent être formés par des courbes de Bezier d'ordre supérieur; La Fig 2 illustre un exemple d'une branche d'une structure de données hiérarchique d'éléments-objets; la Fig 3 illustre un exemple plus étendu d'une structure de données hiérarchique; la Fig 4 est un schéma symbolique d'un système à multiprocesseur; la Fig 5 illustre l'organisation d'une image à visualiser dans un espace de visualisation bidimen- sionnel; la Fig 6 est un schéma plus détaillé d'un système à multiprocesseur; les Fig 7 a et 7 b illustrent un organigramme pour la sélection d'éléments-objets dans un processeur de réduction; la Fig 8 illustre un programme pour le traitement dans un processeur de polygones; les Fig 9 a et 9 b illustrent quelques formules sous forme de figures; les Fig 10 a à 10 f illustrent quelques possi- bilités dans le cas du programme de la Fig 8; la Fig 11 est un schéma synoptique d'un processeur de polygones pour des polygones de Bezier formés de lignes droites; la Fig 12 est un schéma synoptique d'un processeur de polygones pour des polygones de Bezier dont les côtés sont formés par des courbes de Bezier tout au plus du troisième ordre. ELEMENTS-OBJETS ET STRUCTURE DE DONNEES La Fig 1 illustre quelques exemples d'élé- ments-objets élémentaires formés de lignes droites; pour plus de simplicité, on examinera tout d'abord une situation planaire L'élément 30 est un polygone convexe, ce qui peut être enregistré dans la structure de données sous la forme d'une chaîne (string) de données, mentionnant dans l'ordre: le nom de l'objet, sous la forme d'un identificateur, qui indique égale- il ment le nombre de sommets, dans le cas présent donc "six", ensuite une rangée de sept informations de sommets, à savoir dans l'ordre le sommet de départ, le premier sommet suivant dans le sens des aiguilles d'une montre (vers la droite ou au contraire vers la gauche) et les autres sommets suivants, jusqu'à ce que le sommet de départ apparaisse pour la seconde fois à titre de dernier sommet Chaque sommet est donné par ses coordonnées relatives par rapport à un point de référence dans l'élément- objet à l'intérieur duquel l'élément-objet élémentaire en question est relié La manière de stocker l'information au niveau du système dans la mémoire initiale, par exemple selon une organi- sation segmentaire, n'est pas spécifique à l'invention et ne sera pas' décrite plus en détail Les hachures indiquent que le polygone en question possède un domaine intérieur d'une couleur déterminée Dans ce cas, le domaine intérieur peut ou bien être incolore, ou bien être d'une autre couleur Dans ce dernier cas, le domaine intérieur du polygone peut aussi présenter la couleur de fond. Dans l'exemple donné, le contour du polygone est considéré comme appartenant au domaine intérieur. Ce choix est en lui-même aléatoire De plus, l'infor- mation du polygone en question contient encore une donnée de priorité Lorsque deuxc polygones ont un point commun dans le domaine intérieur, le polygone de faible priorité peut être couvert par un polygone de priorité plus élevée Il est cependant aussi possible qu'une couleur mélangée soit obtenue Il convient de noter que deux couleurs seulement sont pertinentes pour le polygone en question et qu'aucune ligne d'une largeur pour ainsi dire infiniment petite n'apparaît Lors- qu'une ligne doit être indiquée dans une image, cette indication est réalisée sous la forme d'un polygone étroit Ceci a l'avantage que lors d'une poursuite de la réduction d'échelle, la ligne en question s'amincira automatiquement de plus en plus et disparaîtra fina- lement par échantillonnage par défaut (undersampling), sans qu'un algorithme supplémentaire soit nécessaire pour le traitement de lignes (de contour). L'élément 32 est d'une manière correspondante un polygone comportant huit sommets et est partiel- lement concave Pour le reste, les mêmes particularités que celles mentionnées à propos de l'élément 30 sont valables. L'élément 31 est un polygone d'une autre catégorie On peut le décrire d'une part comme un hexagone présentant deux sommets coincidants; le traitement est alors le même que pour les polygones mentionnés plus haut Par ailleurs, le polygone en question peut aussi être considéré comme un quadri- latère dont deux côtés se coupent Le domaine inté- rieur, y compris le contour, est toujours d'une autre couleur que le domaine extérieur. D'une manière correspondante, on peut consi- dérer l'élément 33 comme un pentagone; comme indiqué, une partie du domaine enfermé est définie comme domaine non intérieur parce qu'il n'est pas hachuré Il en est de même dans le cas de l'élément 35 Il est clair qu'à l'aide d-'un autre algorithme que celui qui est prévu dans la forme d'exécution préférée, d'autres conven- tions pour la coloration de tels polygones compliqués sont possibles Notamment, le contour d'un polygone peut recevoir la couleur de fond. Les Fig lb à le donnent des détails concer- nant la formation de polygones dits de Bezier dont les côtés peuvent être formés par des courbes de Bezier d'ordre supérieur La Fig lb donne la formule de telles courbes de Bezier, d'autres détails concernant le comportement phénoménologique de ces courbes sont donnés dans la littérature de référence citée Une courbe de Bezier de l'ordre N = 1 est un segment de ligne droite entre les points p O et pi qui sont des points d'extrémité. Dans la terminologie ici utilisée, il s'agit des points descriptifs de ce segment de ligne La troisième et la quatrième ligne donnent respectivement des courbes de Dezier du deuxième et du troisième ordre Sur la troisième ligne, p O et p 2 sont les points d'extrémité d'une para- bole, le point pi ne se trouvant pas sur la parabole. Sur la quatrième ligne, p O et p 3 sont les points d'ex- trémité de la courbe, les points pi, p 2 ne se trouvant pas sur la courbe Les segments de ligne qui relient les points d'extrémité au point descriptif suivant/précédant sont tangents à la courbe Il s'avère qu'à l'aide des cas donnés, une multitude de possibilités peut être réalisée. La Fig lc indique la formation d'une courbe de Bezier du premier ordre Les deux points descriptifs sont 300 et 302 Le segment de ligne est divisé en deux parties égales par le point 304 Les moitiés sont divisées en deux parties égales respectivement par les points 306 et 308. La Fig id illustre la formation d'une courbe de Bezier du deuxième ordre Les trois points descriptifs sont 310, 312 et 314; ces trois points déterminent donc deux courbes de Bezier du premier ordre Les segments de lignes respectifs sont divisés en deux parties chaque fois égales par les points 316, 318 Le segment de ligne formé par les points mentionnés en dernier lieu est divisé en deux parties égales par le point 320 On peut prouver que ce dernier point est un point de la courbe de Bezier du deuxième ordre en question En répétant les opérations en question, on peut déterminer une série de points qui divisent la courbe de Bezier en question chaque fois en de plus petits segments: les points 310, 316 et 320 forment en effet les points descriptifs d'une courbe de Bezier qui coïncide avec la courbe de Bezier déterminée par les points 310, 314 et 312 La Fig le illustre la formation d'une courbe de Bezier du troisième ordre Les quatre points descrip- tifs sont 322, 324, 326, 328 Les segments de lignes déterminés par des paires successives de points des- criptifs sont divisés en deux parties égales par les points respectifs 330, 332, 334 Ce processus est répété par les points 336, 338 Le segment de ligne décrit par ces deux derniers points est divisé en deux parties égales par le point 340 On peut prouver que ce dernier point est à nouveau un point de la courbe de Bezier du troisième ordre en question et aussi que les courbes de Bezier déterminées par les séries de points 322, 330, 336, 340 et 340, 338, 334, 328 sont ensemble identiques à la courbe de Bezier déterminée par la série de points 322, 324, 326, 328 Les points de division par deux des courbes de Bezier, donc dans les cas représentés, respectivement les points 304, 306, 308, 320, 340, sont utilisés, dans le processeur de polygones décrit plus loin, pour exécuter un traitement itératif On peut former des figures plates à partir des côtés de polygones mentionnés A l'instar des polygones classiques de la Fig la, ils sont qualifiés de polygones de Bezier Ces polygones peuvent donc être formés de courbes de Bezier d'ordres différents. Un segment de ligne tel que représenté sur la Fig lc forme la diagonale d'un parallélogramme qui est pour le reste entièrement donné lorsque les directions de ses côtés sont données De la même manière, les points descriptifs d'une courbe de Bezier selon les Fig ld/e engendrent également un parallélogramme lorsque les directions des côtés sont données: ce parallélogramme est le plus petit qui contient tous les points descriptifs de la courbe de Bezier en question. Ce parallélogramme est appelé parallélogramme engendré. Il est aisé d'admettre que tous les points d'pne courbe de Bezier se trouvent à l'intérieur du parallélogramme engendré par ses points descriptifs Lorsqu'un côté de polygone est spécifié par les points descriptifs, l'ordre de la courbe dans la mémoire de réception fait également partie des spécifications. Il convient de noter que la forme des courbes dé- pend aussi de l'ordre de succession des points descriptifs. Un polygone de Bezier peut être formé par concaténation de plusieurs courbes de Bezier, exactement comme un poly- gone classique peut être formé par concaténation de seg- ments de lignes droites Dans la forme d'exécution pré- férée, décrite plus loin, il est exigé que les courbes de Bezier aient une allure monotone par rapport aux deux di- rections de coordonnées S'il n'en est pas ainsi, une courbe peut êtredivisée en segments qui satisfont chacun l'exigence Pour une courbe de Bezier avec au maximum quatre points descriptifs, l'exigence que tous les points descriptifs se trouvent dans le rectangle qui est engendré par les points d'extrémité Ceci simplifie l'algorithme. La littérature citée indique, en outre, la formation de surfaces courbes ou non, comme étant décrites par deux ensembles de polygones de Bezier. Les éléments-objets peuvent être soumis à des relations spatiales (transformations relatives) Celles-ci sont valables dans une situation bidimensionnelle, par exemple par rapport à un système d'axes de référence translation rotation modification d'échelle (augmentation ou diminution) réflexion par rapport à un point ou une ligne droite. La Fig 2 illustre un exemple d'une branche d'une structure de données hiérarchique d'éléments-objets. Chaque niveau est représenté symboliquement Le ni- veau inférieur 36 comporte à gauche, en tant qu'élé- ment-objet, un triangle équilatéral qui est indiqué. sous la forme de la chaîne de sommets mentionnée plus haut A droite, cet élément-objet comporte, à titre de donnée supplémentaire, un rectangle circonscrit (dans le cas présent un carré) du triangle équilatéral, qui est donné, par exemple, par les coordonnées x et y des côtés du rectangle par rapport au système de coordonnées de l'élément-objet d'ordre supérieur suivant dans lequel il est relié Le rec- tangle en question n'est pas unique pour le triangle, car chaque orientation relative fournit un rectangle circonscrit propre Il n'est pas nécessaire que pour une orientation déterminée, on choisisse la figure la plus petite, mais ceci économise en général le temps de calcul Ainsi, dans le cas o les côtés sont formés par des courbes de Bezier d'ordre supérieur, on pourrait utiliser un rectangle circonscrit "trop grand" Le stockage de l'élément-objet élémentaire peut à nouveau s'effectuer d'une manière classique L'emplacement du triangle équilatéral dans le rectangle circonscrit est indiqué en traits pointillés, tandis que le rectangle est tracé en traits interrompus. Au niveau hiérarchique supérieur suivant 38, le triangle équilatéral du niveau 36 est combiné avec une structure crochue, c'est-à-dire un polygone compor- tant des parties très étroites qui ne sont pas hachurées Cette structure crochue n'est, ici pas représentée en tant que partie d'un niveau hiérarchique inférieur A droite, cette combinaison est à nouveau représentée à l'intérieur du rectangle circonscrit associé (dans ce cas, à nouveau un carré) La combi- naison des deux éléments-objets élémentaires peut être réalisée par des relations spatiales, comme expliqué plus haut Le rectangle circonscrit de la combinaison peut être déterminé d'une manière élémentaire. Au niveau supérieur suivant 40, l'élément- objet représenté du niveau 38 est à nouveau combiné avec un polygone (pentagone), et un rectangle cir- conscrit est également représenté en traits interrompus Dans la structure de données, les rela- tions entre les éléments-objets sont données, par exemple, par des indicateurs d'adresse dans la mémoire de réception. La Fig 3 illustre un deuxième exemple d'une structure de données hiérarchique d'éléments-objets A un niveau de tête le losange 66 représente, avec le rectangle circonscrit associé 42, une structure cohérente bidimensionnelle; aux niveaux inférieurs, seuls sont numérotés esdrectangée-circonscrits respectifs 44 64 et les éléments-objets élémentaires ou non ne sont indiqués que par des losanges non numérotés Au niveau inférieur suivant, la structure de cohérence est forizmée-de trois éléments-objets ( 44, 46, 48 y Au tr oisième niveau de la figure, l'élément-objet 46 est formé des éléments-objets constitutifs 50, 52 et l'élément-objet 48 des éléments-objets 54, 56 Au quatrième niveau de la figure, l'élément-objet 44 est formé des éléments-objets 58, 60, l'élément-objet 52 de l'élément-objet 60 et l'élément-objet 54 des éléments- objets 62, 64 Les éléments-objets 50 et 54 à 64 doivent être considérés comme élémentaires Le fait qu'un élément-objet soit élémentaire ou non n'est en lui-même détermine que par son emplacement dans la structure de données hiérarchique, en l'occurrence lorsqu'il n'y a pas de niveau inférieur par rapport à cet élément-objet Dans une forme d'exécution préférée, la structure de données comporte deux sortes d'éléments: en premier lieu, on trouve les éléments- objets proprement dits En deuxième lieu, on trouve ce qui est qualifié d'appels: un appel indique la trans- formation entre le cadre de référence de l'élément- objet appelant ou supérieur et de l'élément-objet appelé ou inférieur Ce n'est que pour les éléments- objets élémentaires qu'il n'y a pas d'appel prévu parce qu'il est prévu qu'à ce niveau inférieur, les relations sont le plus souvent invariables; ceci est donc légè- rement différent de la Fig 2 dans laquelle même entre les deux niveaux inférieurs, la rotation et le chan- gement d'échelle sont possibles Pour plus de simpli- cité, les appels seront considérés ci-après comme faisant partie de l'élément-objet inférieur Le sens de la séparation précitée entre appels et éléments-objets se situe dans la simplification de l'utilisation multiple d'éléments-objets. DESCRIPTION GLOBALE DU SYSTEME DE MACHINE A CALCULER Les opérations exécutées sur les éléments- objets sont décrites avec référence à la Fig 4 qui illustre plus ou moins symboliquement le système A multiprocesseur Le bloc 68 est une mémoire a accès aléatoire dans laquelle se trouve la structure de données hiérarchique et ce dans une situation tridimen- sionnelle Dans le cas, par exemple, d'un simulateur de vol pour des pilotes, ceci donne la "réalité" spatiale. Une situation plus simple se présente fréquemment en cas de "conception assistée par ordinateur (CAO ou CAD) La représentation en perspective peut dans ce cas Atre souvent négligée et une projection parallèle est utilisée, en opposition à la projection dite centrale de systèmes en perspective Le bloc 70, qui est réalisé par une machine à calculer, symbolise la transformation de la structure de données vers un centre visuel, en ne tenant pas encore compte du mode de projection Les transformations déterminent donc la situation relative de l'élément-objet en question par rapport au centre visuel, ceci étant aussi exprimé dans le système de coordonnées de l'oeil associé Les dispositions en question peuvent éventuellement faire partie du processeur central Dans le bloc 72, la réduction de la situation tridimensionnelle vers la situation bidimensionnelle est réalisée Le bloc 72 est aussi réalisé par une machine à calculer Dans cette machine, est notamment déterminée la projection de l'élément-objet qui, point par point, est directement donnée par les équations de transformation: x(p)= X"/Z", et y(p)= Y"/Z", dans lesquelles la dou- ble apostrophe indique les coordonnées dans le système de coordonnées de l'oeil. Cette projection est à présent stockée comme une (partie d'une) structure de cohérence bidimen- sionnelle dans la mémoire à accès aléatoire 74 Dans des cas bidimensionnels, par exemple lorsque le système décrit est utilisé pour la conception de circuits intégrés, cette mémoire 74 comporte directement la structure de données hiérarchique bidimensionnelle des éléments-objets et les blocs 68, 70, 72 peuvent donc être omis Les blocs 68 à 72 peuvent en soi faire partie du processeur central. Le bloc 76 représente un processeur de réduc- tion dont le fonctionnement sera décrit plus en détail ci-après Le bloc 78 est un ensemble de processeurs de points qui sont connectés au processeur de réduction 76 au moyen d'une structure de démultiplexage simplement indiquée comme un branchement de ligne Dans cet exemple simple, quatre processeurs de points seulement sont indiqués Le processeur de points 80 est formé d'une mémoire 88 et du processeur proprement dit 90 La commande d'entrée/sortie du processeur 80 et une structure de bus éventuelle utilisée à cet effet ne sont pas représentées pour plus de simplicité. La Fig 5 illustre l'organisation d'une image dans un espace de visualisation bidimensionnel La case indique le domaine de coordonnées dans lequel la structure de cohérence de coiffage des éléments-objets est définie La case 102 indique le domaine de coor- données qui doit en être visualisé Pour plus de simplicité, les directions principales des cases 100, 102 sont choisies de manière correspondante On suppose que l'élément de visualisation est un tube de télé- * vision à balayage de trame, la direction des lignes dans l'image étant orientée horizontalement La case 102 comporte huit cases partielles 104 à 118, la division du reste de la zone étant représentée mais non numérotée. Le processeur de réduction 76 effectue à présent la réduction suivante Lorsque, par exemple, l'information couleur de la case partielle 104 doit être calculée, on examine au départ du niveau maximum de la structure de données hiérarchique, pour tous les éléments-objets, si le rectangle circonscrit de l'élé- ment-objet en question a un point commun avec la case partielle en question Ce n'est que dans l'affirmative que les éléments constitutifs de l'élément-objet en question, donnés en tant qu'éléments-objets, sont soumis à la même enquête Lorsqu'il n'y a pas de point commun, l'élémentobjet en question ainsi que les éléments-objets constitutifs sont par la suite négligés Lorsqu'un élément-objet élémentaire a effec- tivement un point commun avec la case partielle, l'information de cet élément-objet, ainsi que de tous les éléments-objets de niveau hiérarchique supérieur dans lequel cet élément-objet élémentaire est relié, est appliquée au processeur de points qui doit traiter la case partielle en question ou une partie de celle- ci L'état relié est réalisé par le fait que l'élément- objet en question agit en tant qu'élément d'une rela- tion spatiale Un organigramme de ces opérations est illustré sur les Fig 7 a, 7 b et sera décrit plus en détail plus loin. La Fig 6 illustre un schéma plus détaillé d'un système à multiprocesseur Le bloc 160 représente un démultiplexeur pouvant être activé de manière cyclique qui est alimenté selon la flèche indiquée à gauche par le processeur de réduction Au démulti- plexeur sont connectées seize mémoires partielles dont seules la première 162 et la dernière 164 sont indiquées Par analogie avec la Fig 5, l'image de télévision est subdivisée en seize bandes verticales; chaque bande est subdivisée en un nombre fixe (par exemple seize) de cases partielles disposées l'une au- dessus de l'autre On dispose donc de 256 cases par- tielles parmi lesquelles une bande horizontale de seize cases partielles est chaque fois traitée en une fois. Dans une première opération partielle, l'information pertinente pour le traitement des cases partielles respectives est transférée de la structure de données vers la mémoire partielle en question Lorsque la bande de cases partielles est traitée, l'information pour la bande suivante de cases partielles est déterminée et est stockée dans les mémoires partielles L'élément 166 est un démultiplexeur secondaire qui rend le contenu de la mémoire partielle 162 disponible pour quatre proces- seurs de points ( 168 à 174) Il y a donc un total 64- processeurs pour une image complète Dans chaque case partielle, chaque processeur de points est actif pour des points d'image prédéterminés et dans une forme d'exécution avantageuse, deux lignes de télévision sont traitées chaque fois dans une case partielle et en particulier, le processeur de points 168 traite la partie gauche de la ligne supérieure, le processeur de points 170, la partie droite de la ligne supérieure, le processeur de points 172, la partie gauche de la ligne suivante et le processeur de points 174, la partie droite de cette ligne suivante Lorsque tous les processeurs de points ont achevé de traiter de cette façon les parties de ligne qui leur sont attribuées, l'information couleur totale de deux lignes de télé- vision est déterminée L'élément 176 est un multi- plexeur pouvant être analysé de façon cyclique qui analyse tout d'abord tous les processeurs de points qui ont traité une partie de la première ligne de télé- vision, puis les processeurs de points qui ont traité une partie de la deuxième ligne de télévision L'infor- mation est transférée vers la partie réceptrice de la mémoire d'image Lorsque l'information est appliquée dans l'ordre correct, la mémoire d'image (élément 92/94 sur la Fig 4 i peut être organisée en série, par exemple, par des éléments de transfert de charges ou des domaines magnétiques Lorsque toutes les bandes de l'image ont été traitées, l'image est le cas échéant à nouveau traitée tandis que dans la mémoire de visuali- sation, la partie de réception et la partie d'émission échangent leurs fonctions Ceci n'a bien entendu de sens que lorsque l'image est ainsi modifiée, par exemple par le fait que le centre visuel change de place, que le facteur de grossissement egt modifié, ou que dans la structure de données, un ou plusieurs éléments-objets sont modifiés, par déplacement, par adjonction ou par suppression Dans le cas d'une image non modifiée, il suffit qu'elle soit déterminée une seule fois. LES OPERATIONS DANS LE PROCESSEUR DE REDUCTION Les Fig 7 a et 7 b illustrent un organigramme pour la sélection des éléments-objets, telle qu'elle se produit dans le processeur de réduction et telle qu'elle peut se produire à peu près de la même manière lorsque le processeur de points fonctionne comme processeur de structure L'opération démarre dans le bloc 130, par exemple la procédure en question est appelée dans une mémoire de programme et les variables sont déclarées Dans le bloc 232, les coordonnées du bord gauche XL, du bord droit XR, du bord supérieur YB et du bord inférieur YO sont établies, il s'agit là des coordonnées qui détermineront au niveau le plus bas de la structure de données hiérarchique (coordonnées d'application) la nature pertinente ou non de l'élé- ment-objet en question Il s'agit donc des coordonnées des sommets du rectangle circonscrit Dans le proces- seur de structure, les coordonnées du point en question sont complétées Dans le bloc 134, l'adresse de mémoire de la structure de données hiérarchique à traiter est appelée, c'est-à-dire l'adresse de la structure de cohérence de coiffage Tous les éléments-objets pos- sèdent un bit de pertinence:-tous ces bits de perti- nence sont à présent ramenés à l'état initial Dans le bloc 136, une pile à accès global est créée Dans le bloc 138, la procédure récursive "examine" est appelée et assure l'examen proprement dit des éléments- objets du point de vue de la présence ou non d'une pertinence. Lorsque le système abandonne à nouveau le premier exemplaire appelé de ces procédures, les opérations se terminent dans le bloc 140 Dans ce cas, tous les -éléments-objets dont les bits de pertinence sont placés sont transférés vers la mémoire partielle en question. Dans la réalisation dui processeur de structure, les éléments-objets élémentaires pertinents sont traités dans ce but dans le processeur de polygones. La Fig 7 b illustre la procédure "examine". Cette procédure démarre dans le bloc 142 Dans le bloc 144, on détecte si la case partielle à examiner che- vauche avec l'élément-objet actuel; en première ins- tance, l'élément-objet est la structure de cohérence de 254247 O coiffage appelée dans la Fig 7 a Lorsqu'il n'y a pas de chevauchement, le système revient au sous-programme a partir duquel la procédure en question a été appelée: bloc 184 S'il y a chevauchement, l'adresse de l'élément-objet actuel est inscrite sur la pile globale: bloc 146 De plus, la variable auxiliaire BRA est mise a zéro Celle-ci indique le numéro de l'élé- ment-objet suivant à examiner, c'est-à-dire les élé- ments-objets constitutifs du niveau inférieur suivant; ils sont numérotés selon les nombres naturels Dans le bloc 148, la variable BRA est incrémentée et dans le bloc 150 est détecté s'il y a ou non chevauchement. Dans la négative, est détecté dans le bloc 180 si l'élément-objet constitutif de l'élément-objet actuel était le dernier du niveau inférieur suivant S'il en est ainsi, dans le bloc 182, la donnée la plus récente est enlevée de la pile globale et n'est pas traitée davantage Lorsque dans ce cas la pile globale est entièrement vide, il s'agit d'une opération perdue. Dans le bloc 184, le système revient à la procédure que l'exemplaire présent de la procédure "examine" avait appelé En l'occurence, il s'agit donc de la procédure de la Fig 7 a Lorsqu'un chevauchement a bel et bien été détecté dans le bloc 150, l'adresse de l'élément- objet constitutif actuel est inscrite sur la pile globale Dans le bloc 154 est détecté si ce dernier élément était un élément-objet élémentaire Dans l'affirmative, toute l'information est reprise de la pile globale et le bit de pertinence de tous les éléments-objets qui y sont référenciés est placé Le système revient ensuite au bloc 180. Lorsque aucun élément-objet élémentaire n'était en cours de traitement dans le bloc 154, les variables locales de l'environnement du processus (dites run-time stack) sont sauvegardées dans le bloc 186 Il s'agit au moins des coordonnées de la fenêtre (bloc 132) ou des coordonnées qui en sont dérivées par les transformations effectuées et de la valeur réelle de la variable BRA dans l'exemplaire en question de la procédure "examine" Dans le bloc 188, les coordonnées de fenêtre sont recalculées au moyen de l'inverse des relations spatiales pour l'élément-objet en question vers l'élément-objet supérieur suivant, y compris les transformations effectuées entre-temps (ce dernier élément était donc actuel au moment de l'entrée de la procédure dans le bloc 142) Ensuite, dans le bloc 190, la procédure "examine" est A nouveau appelée Lors du retour à partir du bloc 190, le bloc 192 correspond au bloc 182 et le système passe au bloc 180. Lorsque tous les éléments-objets sont traités, ceux dont les bits de pertinence ont été placés doivent être considérés davantage Dans une réalisation simple, le système parcourt tous les éléments-objets et examine chaque fois le bit de pertinence Il peut aussi être réalisé avec une seconde procédure récursive: "process"; celle-ci ne sera que brièvement décrite En lieu et place d'un chevauchement, cette procédure détecte le bit de pertinence Au lieu du bloc 156/158, les éléments-objets en question sont transférés vers la mémoire partielle Le bloc 188 est supprimé et pour le reste, les opérations se déroulent à peu près confor- mément à la Fig 7 b. LE FONCTIONNEMENT DES PROCESSEURS DE POINTS On décrira à présent le fonctionnement de l'ensemble des processeurs de points et pour ce faire, on partira pour plus de simplicité de la Fig 4. Lorsque la mémoire auxiliaire 88 dans le processeur 80 contient la structure de données réduite pertinente pour la case partielle en cours de traitement (cette structure de données est à nouveau agencée de la même manière hiérarchique), le traitement de l'information peut débuter Le processeur de points suit la même séquence successivement pour chaque point d'image traité et fonctionne pour ce point d'image succes- sivement en tant que processeur de structure, proces- seur de polygones et processeur de priorité En prin- cipe, ces opérations peuvent aussi être exécutées dans une autre relation Ainsi, les opérations sur les polygones peuvent débuter pour un polygone déterminé lorsque celui-ci a été traité complètement par les opérations du processeur de structure Les opérations pour le processeur de priorité peuvent débuter pour les polygones pour lesquels les opérations pour déterminer l'information "intérieur" ou l'information "extérieur" ont été entièrement achevées Sous ce rapport, le processeur 90 peut donc aussi être formé de plusieurs processeurs partiels qui exécutent chacun une partie des opérations selon que les données nécessaires à cet effet sont disponibles Le multitraitement est par lui- même connu et pour plus de concision, on ne le décrira pas en détail ici. Les opérations pour le fonctionnement comme processeur de structure se déroulent de la même manière que les opérations dans le processeur de réduction et ce pour une case partielle qui n'est formée que d'un seul point A cet effet, il suffit qu'une seule paire de coordonnées (au lieu de deux) soit transformée et conservée sur la "run-time stack" précitée De plus, dans le processeur de points, aucun alignement avec les axes du nouveau système de coordonnées ne doit alors être prévu, parce qu'il ne s'agit que d'un seul point. Finalement, (seuls des) éléments-objets élémentaires pertinents (leurs adresses) doivent être copiés dans le processeur de points au profit du processeur de poly- gones, y compris l'information de priorité éventuelle pour le processeur de priorité. Les opérations concernant le processeur de polygones seront décrites ciaprès Les opérations pour le processeur de priorité sont le plus souvent simples: dans un environnement bidimensionnel, chaque polygone à colorer est pourvu d'un nombre de priorité propre et dans le cas d'un chevauchement, la couleur du nombre de priorité le plus élevé est simplement consi- dérée comme "gagnante" Lorsque plusieurs polygones possèdent des couleurs présentant le même nombre de priorité, une couleur mélangée est réalisée La forma- tion de couleurs mélangées est en elle-même bien connue Lorsque la couleur à réaliser pour un point déterminé est établie, le point d'image suivant de -la case partielle à traiter par le processeur de points en question est examiné Lorsque tous les points d'une case partielle ont été traités, le processeur de réduction 76 est réactivé pour fournir l'information d'une case partielle suivante L'information de couleur ainsi formée est fournie à un double tampon 92/94 La partie 92 est une partie de réception et est pour plus de simplicité construite comme une mémoire série, par exemple avec des modules de 300 kbits, dont plusieurs sont disposés en parallèle pour stocker une information de plusieurs bits pour chaque point d'image Pour chaque point d'image, un octet est, par exemple, fourni en parallèle par le processeur de points en question. La partie 94 est une partie de visualisation et a la même capacité que la partie de réception Lorsque tous les points d'image de la case 102 ont été traités, la partie de visualisation et la partie de réception échangent leurs fonctions. L'élément de visualisation 96 est, par exem- ple, un appareil classique basé sur un tube de télé- vision à 600 lignes d'image sur chacune desquelles 1000 points d'image sont décomptés Le réseau de sortie entre les processeurs de points respectifs et le double tampon comporte une organisation de multiplexage, de sorte que l'information des couleurs déterminées par les processeurs de points est fournie dans l'ordre dans lequel les points en question doivent être représentés sur l'écran Les calculs point par point ne prennent pas le même temps pour chaque point et de plus, les processeurs de points doivent être analysés de manière cyclique pour fournir l'information dans l'ordre correct C'est pourquoi la sortie d'un processeur de points comporte une quantité de tampon intermédiaire o des informations couleur déjà déterminées sont stockées jusqu'à ce qu'elles doivent être rendues disponibles pour le double tampon. LES OPERATIONS DANS LE PROCESSEUR DE POLYGONES La Fig 8 illustre en un langage algorithmique de machine à calculer les opérations à réaliser par le processeur de polygones, pour déterminer pour un point d' image déterminé et pour un polygone déterminé, l'information couleur partielle "intérieur" ou "non intérieur" Par ailleurs, la Fig 9 b déclare quelques grandeurs initiales, à savoir un "bag" de paires de points, la même paire de points pouvant donc se pré- senter plusieurs fois, trois variables booléennes et deux nombres entiers Un point d'image est un élément d'un ensemble de paires de noe es entiers: e 1 cint P a les coordonnées (xp,yp) La distance mutuelle "d" entre deux points est déterminée comme étant la valeur absolue de la distance maximum dans une direction de coordonnées (x ou y) Une courbe est formée par une rangée de points dont la distance mutuelle est chaque fois égal " 1 "; le nombre de points de la courbe est qualifié dans cette définition de "longueur" Une distance " 1 " correspond donc à une longueur " 2 " Le' rectangle circonscrit de deux points P,Q comporte tous des points d'image pour lesquels (x xp)*(x xq) d'une courbe, tous les points de chaque courbe par- tielle de cette courbe étant situés dans le rectangle circonscrit déterminé par les points d'extrémité de cette courbe partielle Les courbes de Bezier illus- trées sur les Fig lc à le satisfont donc à ces conditions En fonction de la coordonnée x, la coor- donnée y est ou bien "non montante" ou bien "non descendante"; il en va de même pour la coordonnée x en fonction de la coordonnée y. Pour l'algorithme ici décrit, toutes les courbes de Bezier ne sont pas admissibles, par exemple ne le sont pas celles pour lesquelles un point des- criptif intermédiaire ne se trouve pas à l'intérieur du rectangle circonscrit déterminé par les points descrip- tifs extrêmes Lorsque de telles courbes apparaissent, une solution simple, qui n'implique aucune approxi- mation de la courbe, consite à subdiviser une courbe' de Bezier en parties pour lesquelles le problème ne se présente pas Il convient de noter également que l'exigence imposée est moins stricte que celle selon laquelle tous les points descriptifs d'une courbe de Bezier doivent se trouver à l'intérieur du rectangle formé par les points d'extrémité. Un polygone "G" est une rangée de points dans laquelle les points d'extrémité coincident sans autre restriction pour les autres points La courbe d'un polygone sous une fonction de traçage de ligne est la somme des courbes déterminées par les côtés successifs du polygone sous ces fonctions de traçage de ligne. Dans le cas o un polygone n'est formé que d'un seul point, cette courbe est identique à ce seul point Pour chaque triplet des grandeurs polygone G, fonction de traçage de ligne f, et point P, on définit à présent un premier prédicat ATSIDE et un second prédicat INSIDE qui peuvent chacun être "vrai" ou "pas vrai" Le premier prédicat est "vrai" lorsque le point d'image en question coincide avec un point indiqué par la fonction detraçage de ligne en question comme point de côté du polygone Le prédicat INSIDE est "vrai" lorsque le nombre de points d'intersection d'une droite semi- infinie quelconque partant du point en question avec un nombre quelconque des côtés du polygone est impair. Dans la forme d'exécution décrite, cette droite semi- infinie a la direction x négative Le prédicat INSIDE est donné sous forme -de formule sur la Fig 9 a Un point d'intersection est défini par deux conditions nécessaires La première est que deux points k,k+l du côté du polygone se trouvent sur la coordonnée y supérieure suivante ou inférieure suivante par rapport au point d'origine P, de sorte que le produit des différences des coordonnées y ait la valeur "-1 " La deuxième condition est que pour tous les points du côté du polygone compris entre les points k et k+l, la coordonnée x soit plus petite que celle du point d'origine P et que la coordonnée y soit égale à celle du point P Sous ce rapport, la Fig l Oa indique donc une situation dans laquelle un point d'intersection est présent entre les points k et k+l, tandis que dans la situation de la Fig l Ob, aucun point d'intersection n'est présent Le nombre total de points d'intersection de la droite semi-infinie avec un nombre quelconque des côtés du polygone doit alors être impair pour une situation "intérieur" Dans l'expression, le signe pour une addition modulo-x est utilisé, x ayant la valeur n. Lorsque sur la troisième ligne de la Fig 9 a, le signe "plus petit que" est utilisé, la droite semi-infinie en question s'étend dans la direction x positive Lorsque le nombre de points d'intersection est impair, le prédicat INSIDE est valable Finalement, l'information couleur est comptée positive lorsque ou bien le pré- dicat ATSIDE, ou bien le précicat INSIDE est vrai: il s'agit du prédicat INCLUDES Pour un polygone, un point et une fonction de traçage de ligne donnés, la valeur du prédicat INCLUDES doit alors être déterminée. On peut prouver que les prédicats précités, parmi lesquels INCLUDES fournit l'information inté- rieur/extérieur finale, peuvent être calculés de la manière suivante A cet effet, il faut tout d'abord définir de la manière suivante deux prédicats intermédiaires - Le prédicat INBOX 1 entre deux points Q,R et un point P à examiner est vrai lorsque le point en ques- tion est compris dans le rectangle circonscrit déter- miné par Q et R (x P x Q)*(xi P x R) le produit doit être au maximum égal à zéro. Le prédicat INBOX 2 est vrai lorsque le rec- tangle circonscrit déterminé par les points Q et R contient deux points A et B pour lesquels il s'avère que le point A se trouve à gauche sur la même coor- donnée y que le point P, et le point B, voisin du point A, sur la coordonnée y supérieure suivante Ceci signifie, entre autres, que le point P ne se trouve ni sur le côté gauche ni sur le côté supérieur du rec- tangle circonscrit Les Fig 10 d à 10 f indiquent un certain nombre de possibilités pour un rectangle décrit par A et B; pour chacune de ces possibilités, le prédicat INBOX 2 est 'vrai", quelques positions diffé- rentes du point P étant chaque fois indiquées Il est de cette façon possible de vérifier très facilement le prédicat INSIDE, compte tenu des exigences choisies pour la fonction de traçage de ligne. Dans la liste de tâches de la Fig 8, on part d'un ensemble (bag) de paires de points B, o des doubles peuvent éventuellement apparaître De plus, trois grandeurs auxiliaires bivalentes sont prévues in,àat et stop et q et r sont définis sur les nombres naturels La liste de tâches de la Fig 8 comporte les tâches suivantes Sur la ligne 200, le polygone en question est déclaré Sur la ligne 201, le nombre de paires de points est déclaré comme étant chaque fois déterminé par un côté respectif du polygone, tandis que les grandeurs in,at deviennent fausses Sur la ligne 202, les opérations démarrent et sont poursuivies jusqu'à ce que ou bien toutes les paires de points de B aient été traitées, ou bien que la grandeur "at" soit devenue "vraie" Sur la ligne 203, deux points'Q,R sont prélevés de B Sur la ligne 204 a lieu la détection visant à déterminer si le point P se trouve dans le rectangle déterminé par Q et R; Lorsqu'il n'en est pas ainsi, le système suit la ligne droite verticale débutant à cet endroit pour terminer à la ligne 230 De la même manière, les autres lignes droites verticales indiquent une structure d'itération (nest) Sur la ligne 205 a lieu la détection déterminant si le point P coïncide avec le point Q ou avec le point R S'il en est ainsi, la grandeur "at" est "vraie" Lorsque l'essai donne un résultat négatif, une série de in points est désignée sur la ligne 208 au moyen de la courbe se terminant en Q et en R sous la fonction de traçage de ligne f Une grandeur auxiliaire "stop" est rendue "fausse" et les numéros d'ordre q,r sont attri- bués respectivement au premier et au dernier point de la courbe Aussi longtemps que la grandeur "stop" reste "fausse", le système continue Sur la ligne 210, la grandeur p est rendue égale à la différence entre q et r Deux cas sont à présent possibles Si p est égal à O ou à 1, les points Eq et Er sont voisins et le rectan- gle circonscrit qu'ils déterminent contient quatre points d'image: le rectangle dit élémentaire qui ici contient quatre points à la suite de l'essai précédent sur la ligne 205 La ligne 213 indique en tout cas un arrêt Sur la ligne 214 est vérifié si aucun des points Eq, Er ne se trouve à droite du point P tandis qu'au moins un des points d'extrémité originaux Q et R se trouve dans la direction y au-dessus du point P S'il en est ainsi, la variable binaire "in" change de valeur Quelques possibilités à cet effet sont illus- trées sur les Fig l Od à 10 f. Cependant, lorsque la distance entre Eq et Er est plus grandes la ligne entre Eq et Er est divisée en deux parties sur la ligne 217, par exemple elle est partagée en deux moitiés avec arrondissement Lorsque le point P coïncide avec ce point intermédiaire Et, un arrêt a lieu sur la ligne 219 en constatant que le point en question se trouve sur le côté du polygone. Lorsque l'essai précédent donne un résultat négatif, on vérifie sur la ligne 224 si le point P se trouve respectivement dans un des rectangles diagonalisés par le point Et et par le point Eq ou le point Er S'il en est ainsi, le système revient à la ligne 209 (while), l'autre rectangle encore toujours présent (dans le cas de cet essai, le point ne peut jamais se trouver simultanément dans les deux rectangles) étant rejeté et le point Et prenant la place d'un des points Eq, Er pour le pas d'itération suivant Lorsque le point P ne se trouve pas dans un des deux rectangles circonscrits, il y a arrêt, mais on vérifie encore si le point pourrait rendre vrai le prédicat INBOX 2 par rapport au point in- termédiaire et à un des points d'extrémité le prédicat est différent de INBOX 1 et vérifie si la ligne qui a les point diagonaux du rectangle comme extrémités se trou- ve entièrement à gauche du point P, contient au moins un point dont la coordonnée y est plus grande et au moins un point dont la coordonnée y est la même ou est plus petite que celle du point P Si le prédicat INBOX 2 est "vrai", la grandeur "in" change de valeur Si le point P ne satis- fait pas à INBOX 1 (Q, R) sur la ligne 204, le système par- vient sur la ligne 230 et l'essai INBOX 2 est encore exécu- té sur les points d'extrémité Q, R,(ligne 231) Finalement, en 233, le résultat de l'algorithme, à savoir la valeur de la grandeur "atu est rendue La Fig l Oc illustre un cer- tain nombre de rectangles circonscrits indiqués par des lignes interrompues; pour plus de simplicité, on considêm ici des courbes de Bezier du premier ordre Lors de la di- vision d'un côté (ou partie de côté) de polygone Un grand nombre de points d'image ne doivent plus intervenir En d'autres termes: à cause du comportement logarithmique à la division, l'algorithme converge déjà pour bon nombre de points d'image après un ou quelques pas de traitement Il convient de noter également que l'algorithme indiqué sur la Fig 8 peut être utilisé pour des courbes de Bezier du premier ordre et ce n'est que dans ce cas qu'existe la liberté de choix du facteur de division qui ne doit pas être égal à La formation des points de division pour des courbes de Bezier d'ordre supérieur est décrite à pro- pos des Fig ld-le L'algorithme de la Fig 8 ne doit être adapté que pour ce point pour de telles courbes de Bezier d'ordre supérieur et il faut donc à cet effet toujours retenir quelques points descriptifs intermédiaires. REALISATION-D'UN PROCESSEUR DE POLYGONE La Fig 11 illustre un schéma synoptique d'un processeur de polygones, pour un polygone dont les c 8 tés sont formés par des courbes de Bezier du premier ordre Un tel circuit peut être réalisé dans un proces- seur à but spécial Seule la partie ayant trait à la coordonnée x est représentée Pour la coordonnée y, un dispositif correspondant est présent ou bien le même dispositif est utilisé en multiplexage dans le temps. La commande par programme est pour plus de simplicité non représentée, mais seules les voies de données sont indiquées On commence par charger les registres 240 et 242 respectivement de la coordonnée x d'un point descriptif (ici le point d'extrémité) du côté en question du polygone et de celle du point à examiner en question Pour les-voies de données, la largeur en bits est chaque fois indiquée Les coordonnées des points sont formées de N bits; ceci est déterminé par les dimensions du champ de travail 100 de la Fig 50 Dans l'élément arithmétique 244, la différence des deux coordonnées x est d'abord déterminée La voie de données en question a une largeur de N bits, augmentée d'un bit de signe Lorsque la différence a la valeur + 1,0 ou -1, cela peut signifier que le point en ques- tion coincide avec le point d'extrémité en question du côté du polygone ou se trouve dans un rectangle cir- conscrit élémentaire déterminé par ce point d'extrémité Pour chacun des trois cas précités, le registre 250 comporte une position de bit De plus, dans un second traitement, le résultat du traitement est transmis en même temps que le contenu du registre 248 par une voie de données d'une largeur de N+ 4 bits vers le registre 250/252: ce registre contient donc la coordonnée x relative du premier point d'extrémité du côté de polygone en question Ensuite, cette même opération est répétée pour l'autre point d'extrémité du côté de polygone en question pour lequel le résultat est stocké dans le registre 254/256 Les coordonnées y des points d'extrémité du côté de polygone en question sont traitées de la même manière Un circuit de détec- tion, non représenté, peut à présent effectuer les essais qui sont indiqués sur la Fig 8 aux lignes 204, 205, 212 Dans certains cas, le traitement du point en question peut ainsi être terminé, notamment lorsque le point en question se trouve en dehors du rectangle diagonalisé par le côté de polygone ou lorsqu'une décision au -sujet de l'information intérieur/extérieur peut être prise directement Pour réaliser les autres lignes de la Fig 8, on rend ensuite les multiplexeurs 258, 260 passants pour les contenus des registres 250 à 256, complétés par un bit "'1 " le moins significatif, tel qu'obtenu d'une source de signaux non représentée. Le milieu du côté de polygone en question est ensuite déterminé: les coordonnées x relatives sont appliquées à l'élément additionneur 270 La somme est temporai- rement stockée dans le registre 272 et est à nouveau une valeur relative Le bloc 274 correspond, du point de vue fonction, au bloc 246 De plus, le résultat de l'essai effectué sur la ligne 221 de la Fig 8 déter- mine celui des deux registres 262 à 268 vers lequel le passage doit être libéré Le point à traiter doit alors se trouver à nouveau dans le rectangle diagonalisé par la partie de côté de polygone O Tant les coordonnées x que les coordonnées y des deux points d'extrémité de cette partie doivent alors avoir des signes opposés. L'opération se poursuit ainsi jusqu'à la fin de la liste de tâches de la Fig 8. La Fig 12 est un schéma synoptique d'un processeur de polygones pour des polygones de Bezier dont les côtés sont formés par des courbes de Bezier tout au plus du troisième ordre La source d'infor- mation est une mémoire 350 à accès aléatoire, par exemple la mémoire auxiliaire en question, dans laquelle les éléments-objets élémentaires pertinents sont pourvus d'un bit de pertinence pour le processeur de polygone en question, ce bit de pertinence étant établi par le processeur de structure Dans le cas d'une structure de données importante et compliquée, cette structure de données peut ici aussi être prise comme indicateur: seuls des éléments-objets qui sont eux-mêmes pourvus d'un bit de pertinence peuvent indiquer à un niveau plus bas de la hiérarchie un élément-objet qui pourrait être pourvu d'un tel bit de pertinence Lorsque plusieurs processeurs de points travaillent sur la même structure de données, un extrait est tout d'abord préparé en vue d'un stockage dans la mémoire auxiliaire Les processeurs de points respectifs produisent alors chacun leur propre copie de cet extrait et le processeur de réduction peut produire un nouvel extrait tandis que les processeurs de points effectuent leur travail Le registre 354 fournit la coordonnée du point d'image en question L'élément additionneur 352 correspond à l'élément 244 de la Fig 11 Les coordonnées relatives du point initial Q et du point final R du côté de polygone en question sont appliqués aux registres 356, 358 Le circuit logique 240 'vérifie si le point d'image A examiner coïncide avec un des deux points d'extrémité (Fig 8, ligne 205, ceci est donc déterminé en même temps pour deux coordonnées) et si oui, la grandeur 'at" est établie et le polygone en question est terminé Le polygone suivant est alors s'il le faut adressé dans la mémoire 350 De plus, lorsque le point d'image se trouve en dehors du rectangle circonscrit (ligne 204), un signal de commande est envoyé à l'élément de com- mande de progression 422 pour adresser le côté suivant du polygone en question De plus, le circuit -logique 418 vérifie la condition INBOX 2 (Q, R), Fig 8, ligne 231 La grandeur "in" devient alors éventuellement "vraie" De plus, les coordonnées relatives des points descriptifs qui sont de quatre au maximum? sont appli- quées successivement aux registres 360 à 366 Les éléments 368 à 374 sont des multiplexeurs à 2- 4 entrées Les éléments 376 à 382 sont des registres correspondant aux éléments 250/2 et 254/6 Les blocs 384-394 représentent une structure ramifiée d'accumu- lateurs pour déterminer un ou plusieurs nouveaux points descriptifs d'une partie de côté de polygone L'élément 404 est un multiplexeur destiné à laisser passer le nombre de sortie (Et) donné par l'ordre de la courbe de Bezier en question Pour une courbe d'ordre supérieur, il s'agit de l'élément 384 et ainsi de suite L'élément 396 est un multiplexeur destiné à laisser passer la coordonnée du dernier point descriptif Dans ce cas, le bloc 402 est un circuit logique destiné à appliquer l'information correcte de Et à des circuits logiques suivants ( 400, 408) Il en est de même pour les cir- cuits logiques 406, 398 par rapport aux deux points d'extrémité du côté (ou partie de côté) de polygone. Les coordonnées du premier et du dernier point des- criptif sont ainsi appliquées respectivement aux circuits logiques 406 et 398 Le circuit logique 400 vérifie INBO Xl(Eq,Er) ou INBO Xl(Er,Et) Lorsqu'une de ces deux mentions est vraie, les multiplexeurs 368, 370, 372, 37 i deviennent passants-ponr les contenus des accumulateurs qui contiennent les données -de points descriptifs ensuite pertinents (essai dans la ligne 222, 224) Le circuit logique 410 vérifie (ligne 212) si les deux points descriptifs forment un rectangle circonscrit élémentaire, de sorte qu'éventuellement la situation des Fig 10 d, e, f peut se présenter (ligne 212) Le circuit logique 408 vérifie si le point nouvellement trouvé Et coincide avec le point d'image en question, un même essai que dans le circuit logique 420 Lorsque le point d'image en question se trouve en dehors des deux rectangles décrits par le point d'ex- trémité et le nouveau point médian, le circuit logique 412 effectue l'essai de la ligne 228, a partir duquel l'information "in" peut éventuellement être modifiée. L'information nécessaire à cet effet concernant les points Q,R avait déjà été reçue des registres 356, 358 au moyen de circuits logiques de sélection 424, 426. Les éléments 414, 416 forment des registres à cet effet. COMPLEMENTS POUR UNE SITUATION TRIDIMENSIONNELLE Dans une situation tridimensionnelle, tous les éléments-objets peuvent premièrement encore toujours être donnés sous forme de polygones plans, auquel cas tous leurs points descriptifs possèdent une troisième coordonnée, qui est alors aussi stockée dans la mémoire 68 de la Fig 4 Après transformation au moyen de l'élément 70, l'équation de ce plan est déterminée et les paramètres de l'équation de ce plan sont stockés dans la mémoire 74 à titre d'information de priorité pour les éléments-objets transformés a l'aide de l'élément 72 Lors d'un traitement par le processeur de réduction, toute l'information des éléments-objets pertinents est stockée dans la mémoire auxiliaire en question Lorsque, après les traitements décrits plus haut dans le processeur-de structure et dans le proces- seur de polygone, on constate que deux ou plus de deux polygones chevauchent un point d'image déterminé, le problème de la coloration est résolu comme suit Il convient de noter à ce propos que cela peut se produire pour une projection parallèle exactement par le fait que seuls les points descriptifs des polygones en question sont transformés vers la situation bidimen- sionnelle, après quoi le traitement de polygone décrit est effectué. 2542470. Les deux plans dans lesquels les polygones se trouvent sont donnés par les paramètres de l'équation paramétrique des plans a, b, c, d ou a', b', c', d', alors que l'équation du premier plan est: ax + by + cz + d = 0, et celle du deuxième plan: a'x + b'y + c'z + d' = 0, les signes de d et de d' étant égaux (il ne s'agit pas là d'une limitation réelle) Le point d'image actuel est donné par ses coordonnées C, D, T, c'est-à-dire par l'intersection de la ligne de vision et du tableau, de sorte que la valeur de T est fixe pour tous les points d'image Dans ce système de coordonnées de l'oeil, les équations de la droite de projection pour le point d'image actuel sont: dans le cas d'une projection parallèle: x=C, y=D, z=k T (k peut avoir une valeur quelconque), de sorte que pour les polygones respectifs, les valeurs paramétriques de k que l'on trouve pour les points d'intersection avec la ligne indicatrice sont: k = (-d a * C b * D) / (c * T), et k'= (-d' a'* C b'* D) / (c I* T), dans le cas d'une projection centrale: x=k C, y=k D, z=k T (k peut avoir une valeur quelconque), k = (-d)/(a * C + b * D + c * T), et k'= (-d')/(a'* C + b'* D + c'* T). Seules les valeurs relatives du paramètre K sont toutefois importantes et, étant donné qu'on a toujours choisi une valeur positive du coefficient d, cette détermination peut s'effectuer après multipli- cation des relations précédentes (de sorte qu'aucune division n'est requise) La plus petite valeur de k ou k' indique le polygone pour lequel l'information "intérieur" possède la plus haute priorité et pour lequel la mise en couleur interne doit donc être réalisée Lorsque plus de deux polygones sont perti- nents pour le point d'image en question, la décision est exécutée successivement par paire pour tous les polygones, seul le plus pertinent des deux étant conservé dans les opérations ultérieures. Des figures de Bezier planes sont considérées dans la description qui précède L'extension aux trois dimensions s'effectue par le fait que les courbes de Bezier s'étendent alors en deux faisceaux qui peuvent être présentés comme un double produit la o sur la Fig lb elles n'exigeaient qu'un seul produit. LISTE D'ORDRES STRT 132 STO XL, XR, YB, YO 134 144 154 CALLDATSTRUCT RESET RELBITS CREATE GLOBAL STACK CALL EXAMINE STR STRT OVERLAP? * PUSH PRESENT ADRESS ON GLOBAL STACK BRA:=O BRA = BRA + 1 OVERLAP? PUSH PRESENT ADDRESS ON GLOBAL STACK LOWEST? SET REL BITS OF GLOBAL STACK ADDRES POP WHOLE OF GLOBAL STACK LAST BRA? 182 POP GLOBAL STACK ONE 184 RETURN SAVE LOCAL VARIABLES RECALL CHECK COORDINATES BY INVERSE TRANSFORM CALL EXAMINE POP GLOBAL STACK ONE R E V E N D I C A T I O N S 1 Système de machine à calculer à multiprocesseur pour convertir des éléments-objets définis dans une structure de données hiérarchique en une représentation visuelle, ce système comportant une connexion pour un processeur central (hosi) pour recevoir sur cette conne- xion l'information des éléments-objets en vue de la stocker dans une mémoire de réception ( 74), un système de processeurs de points alimenté par la mémoire de réception pour calculer, pour chaque image, à partir de la structure de données des éléments-objets, les informations de points d'image à fournir sur une connexion pour un élément de visualisation ( 96), caractérisé en ce qu'un niveau élémen- taire de la-structure de données comporte des éléments- objets en tant que polygones de Bezier définis exclusive- ment par les points des polygones décrivant leurs c 8 tés ( 300/302, 310/312/314, 322/324/326/328), qui sont reliés pour chaque niveau hiérarchique plus élevé suivant par des relations spatiales (transformations relatives) en des éléments hiérarchiquement supérieurs, jusqu'à ce qu'à un niveau hiérarchique de tête on obtienne une structure de cohérence bidimensionnelle ( 66) qui est stockée au moyen d'éléments-objets et de relations spatiales pla- naires dans la mémoire de réception, que le système de processeurs de points comporte un montage (array) de pro- cesseurs de points connectés en parallèle ( 80, 82, 84, 86) qui sont connectés par l'intermédiaire d'un réseau d'en- trée à la connexion pour la mémoire de réception, que chaque processeur de points fonctionne comme générateur de points d'image pour un groupe de points d'image sur l'élément de visualisation, que chaque point d'image est assignéeà un des processeurs de points et que les groupes forment entre eux un motif de positionnement régu- lier, que chaque processeur de points fonc- tionne d'une part, comme processeur de structure pour, dans le cas d'un point d'image prédéterminé, déterminer successivement a partir du niveau hiérarchique de coiffage de la struc- ture de données, par niveau, les coordonnées d'appli- cation associées dans l'élément-objet de ce niveau jusqu'à ce que, ou bien pour l'élément-objet en ques- tion, une non-pertinence pour le point d'image en question soit détectée, ou bien un au plusieurs élé- ments-objets élémentaires soient atteints, que d'autre part, des élémentsobjets élémentaires définis sous la forme des dits polygones étant donnés, chaque proces- seur de points fonctionne comme processeur de polygones pour, à chaque point d'image prédéterminé, calculer pour chaque polygone pertinent une information binaire intérieur/extérieur en vue de former une liste valable pour ce point d'image, d'éléments-objets élémentaires et d'informations de couleur associées pour les élé- ments-objets pour lesquels l'information est "inté- rieur", et qu'en outre chaque processeur de points fonctionne comme processeur de priorité afin de déter- miner, à partir de la dite liste, au moyen de l'infor- mation de priorité valable pour chaque élément-objet élémentaire, la couleur à réaliser pour ce point d'image, et que la connexion pour l'élément de visuali- sation comporte un multiplexeur pouvant être analysé de manière cyclique pour recevoir les signaux de couleur formés par les processeurs de points au moyen d'une analyse pouvant être activée de manière cyclique. 2. Système de machine à calculer à multipro- cesseur suivant la revendication 1 caractérisé en ce que, dans le processeur de polygones, pour chaque côté de polygone, une structure de décision itérative est mise en oeuvre, au moyen de laquelle pour chaque pas itératif, un parallélogramme engendré par un côté de polygone ou une partie de côté de polygone se trouvant au moins partiellement dans l'image est comparé à l'endroit du point d'image actuel au sujet duquel il faut décider, que pour le point d'image à l'intérieur du parallélogramme, le côté du polygone ou la partie de côté du polygone est divisé jusqu'à ce que, dans un pas itératif, la coïncidence du point d'image et de la diagonale soit éventuellement constatée (ATSIDE), mais que pour le reste, lorsque le point d'image actuel se trouve en dehors du parallélogramme en question, ou lorsque le point d'image et la diagonale ne coïncident pas dans un pas itératif élémentaire, le nombre de points d'intersection de tous les côtés du polygone en question avec une droite semi-infinie passant par le point d'image actuel est compté et, dans le cas d'un nombre impair, une information "enfermé" (INSIDE) est formée pour ce point d'image, l'information "intérieur" étant formée à partir de l'information "enfermé". 3. Système de machine à calculer à multipro- cesseur suivant la revendication 2, caractérisé en ce que l'information "intérieur" mentionnée est également formée à partir de la dite coincidence, mais pour le reste c'est l'information "extérieur" mentionnée. 4. Système de machine à calculer à multipro- cesseur suivant la revendication 2 ou 3 pour un élément de visualisation dans lequel les points d'image sont organisés selon une matrice rectangulaire de rangges et de colonnes, caractérisé en ce que les côtés du dit parallélogramme sont parallèles aux rangées et aux colonnes respectivement et la dite droite semi-infinie est parallèle à un des côtés. 5. Système de machine à calculer à multipro- cesseur suivant la revendication 3, caractérisé en ce que l'ensemble des processeurs de points est divisé en ensembles partiels ( 166/174) et une mémoire auxiliaire ( 162) est prévue pour chaque ensemble partiel, que dans un ensemble partiel, les processeurs de points travail- lent sur une image partielle commune, qu'entre la mémoire de réception et les mémoires auxiliaires qui y sont connectées par l'intermédiaire d'un démultiplexeur analysable de manière cyclique, un processeur de réduction ( 76) est connecté pour, à partir de la structure de données hiérarchique, successivement à partir du niveau hiérarchique de coiffage, déterminer niveau par niveau, la pertinence de l'élément-objet en question pour l'image partielle correspondante jusqu' ce qu'une non-pertinence soit détectée ou jusqu'à ce que les éléments-objets élémentaires soient atteints pour ne transférer à la mémoire auxiliaire en question que la partie de la structure de données pour laquelle au moins un élément-objet élémentaire qui y est relié est détecté comme pertinent, y compris l'ensemble des éléments-objets élémentaires détectés comme pertinents. 6. Système de machine à calculer à-multipro- cesseur suivant la revendication 5, caractérisé en ce que la dite pertinence est régie par une coïncidence au moins partielle de l'image partielle en question et d'une zone rectangulaire (bounding box) entourant l'élément-objet stockée dans la mémoire de réception pour chaque élément-objet de la structure de données. 7 Système de machine à calculer à multipro- cesseur suivant l'une quelconque des revendications 1 à 6 incluses, caractérisé en ce qu'entre l'ensemble de processeurs de points et l'élément de visualisation est connecté un tampon d'image double ( 92/94) comportant une partie de réception destinée à recevoir des proces- seurs de points, de l'information couleur concernant une image entière et une partie d'émission destinée à contenir l'information couleur concernant une image entière et à la transmettre à l'élément de visuali- sation jusqu'à ce que la partie de réception, après avoir été complètement remplie de l'information d'une image, soit commutée en partie d'émission et la partie qui jusqu'alors fonctionnait comme partie d'émission, en partie de réception. 8 Système de machine à calculer à multipro- cesseur suivant la revendication 1, caractérisé en ce que dans la mémoire de réception, chaque élément-objet élémentaire est pourvu d'une indication de priorité. 9. Système de machine à calculer à multipro- cesseur suivant la revendication 8 pour visualiser une structure de données organisée de manière tridimension- nelle en une projection centrale ou une projection parallèle, caractérisé en ce que pour les éléments- objets élémentaires qui y sont définis sous la forme des dits polygones, une indication de priorité impli- cite est donnée par les paramètres de l'équation du plan contenant qui contient localement l'élément-objet élémentaire en question et dans le cas de polygones chevauchant localement après projection sur le tableau, les valeurs paramétriques des points d'intersection des plans de contenants localement associés avec la droite paramétrisée dans le sens de la projection et par le point de projection en question donnent par compa- raison, explicitement la priorité relative.