Brevet FR2693012A1 — publié le 19931231

i PROCEDE DE VISUALISATION D'IMAGES SYNTHETIQUES DE VOLUMES EN TEMPS REEL La présente invention se rapporte à un procédé de s visualisation d'images synthétiques de volumes en temps réel. Un générateur d'images synthétiques en temps réel (c'est- à-dire à un rythme d'au moins 25 images par seconde) comporte au moins trois types d'étages de calcul: un processeur géométrique, un processeur d'échantillonnage et un processeur vidéo La puissance informatique nécessaire au calcul en temps réel est telle qu'actuellement on a recours, pour chaque type d'étage, à un processeur dédié (spécialisé) Une telle solution est onéreuse et lorsque la structure est définie et réalisée, il est très difficile ou même impossible de la modifier sans changer un processeur ou 1 S même tous les processeurs. La présente invention a pour objet un procédé de visualisation d'images synthétiques de volumes en temps réel, qui ne nécessite pas pour sa mise en oeuvre de processeurs spécialisés, et qui soit simple à appliquer. Le procédé conforme à l'invention consiste à mémoriser dans une base de données les données décrivant les volumes à représenter sous forme de polyèdres quelconques à partir de leurs côtés orientés, ces données étant les attributs topologiques des côtés des polyèdres, les coordonnées dans l'espace des extrémités de ces côtés, et les attributs géométriques et photométriques des faces de ces polyèdres, à éliminer les faces auto-cachées de ces polyèdres, à effectuer un changement de repère des faces à visualiser, à éliminer tous les objets se trouvant entre l'observateur et le plan de troncature avant, à effectuer une mise en perspective pour projection en deux dimensions, et à effectuer une troncature vectorielle en deux dimensions suivant une pyramide de projection. Cette troncature vectorielle s'effectue pour chacun des plans délimitant ledits polyèdres, et pour chacun de ces plans, on effectue une troncature selon chacun des côtés des faces des polyèdres. Les calculs relatifs à la troncature et au changement de repère sont organisés de manière vectorielle de façon à obtenir les performances maximum, et permettre une parallélisation efficace du procédé de calcul utilisé par l'invention. La présente invention sera mieux comprise à la lecture de la description détaillée d'un mode de réalisation, pris à titre d'exemple non limitatif et illustré par le dessin annexé, sur lequel: la figure 1 est une vue schématique en perspective d'un objet à visualiser, dont on a mis en évidence la structure topologique le décrivant; les figures 2 à 5 sont des vues schématiques de faces d'un objet à visualiser, servant à définir les conventions utilisées pour la description topologique d'objets; la figure 6 est un tableau résumant les données utilisées par le procédé de l'invention; la figure 7 est une vue schématique de faces d'un objet, expliquant la façon de déterminer des faces auto-cachées; la figure 8 est une vue schématique en perspective montrant une pyramide de troncature; la figure 9 est un schéma expliquant un processus de mise en perspective pouvant être mis en oeuvre par le procédé de l'invention; et la figure 10 est une vue schématique en perspective montrant un volume de troncature normalisé, utilisé par le procédé de l'invention. On a schématiquement représenté en figure 1 une structure topologique 1 décrivant un objet quelconque, que l'on appellera ci-dessous "hyperfacette" Cette structure est composée de faces planes (facettes) adjacentes qui correspondent le plus exactement possible aux faces de l'objet à représenter Bien entendu, si les faces de l'objet à représenter sont planes, la correspondance est exacte, mais si elles sont courbes, la correspondance est d'autant meilleure que les facettes de la structure sont petites Une telle représentation par polyèdres est basée sur le procédé décrit par B G BAUMGART dans l'article "A polyedron Representation for Computer vision", National Computer Conference, 1975, pages 589 à 596. Une "hyperfacette" est décrite, dans une base de données, par une liste, non ordonnée, de côtés Chaque côté est caractérisé par ses deux extrémités (dites "points"), ses deux faces 1 o adjacentes (ou sa face adjacente) et ses liaisons avec d'autres côtés. On a schématiquement représenté en figure 1 une hyperfacette 1 Une facette plane de l'hyperfacette 1 est référencée 2 Cette facette 2 est bordée par quatre côtés référencés 3 à 6 Les côtés 3 à 5 sont partagés par deux facettes différentes Ils sont dits "partagés" On remarquera qu'un coté ne peut être partagé par plus de deux facettes Seul le côté 6 n'est pas partagé par deux facettes; il appartient donc au bord de l'objet figuré par l'hyperfacette 1. Un point est toujours partagé entre au moins deux côtés. Si un point n'était l'extrémité que d'un seul côté, la face bordée par ce côté ne serait pas refermée, ce qui est interdit pour une structure topologique Ainsi, par exemple, dans la structure 1, le point 7 est partagé par les côtés 3, 6 et 8 (il constitue l'une des extrémités de chacun de ces côtés Le point 9 est partagé par les côtés 10 et 1 1. Selon une autre convention, les côtés des facettes sont orientés On oriente un côté d'un point Pl vers le point P 2 On a représenté en figure 2 un tel côté 12 partagé par deux faces 13, 14, et on a représenté les normales 15, 16 à ces faces ( par convention, ces normales sont dirigées vers l'extérieur de l'objet à représenter) Les faces 13 et 14 sont respectivement appelées face gauche et face droite Les côtés des faces 13 et 14 partageant le point Pl sont référencés 17, 18 et appelés respectivement côté haut gauche et côté haut droit Les côtés des faces 13, 14 partageant le point P 2 sont référencés 19, 20 et respectivement appelés côté bas gauche et côté bas droit. Selon la convention, deux faces ayant un côté partagé doivent être orientées de la même façon: leurs normales doivent pointer vers le même demi-espace intérieur ou extérieur à l'objet dont ces deux faces font partie Cette règle facilite le traitement graphique de l'objet: deux faces ayant un côté partagé ne peuvent s'occulter mutuellement, alors qu'une élimination des parties cachées serait nécessaire si cette règle n'était pas respectée Ainsi, par exemple, on a représenté en figure 3 deux faces 21, 22 Le côté 23 n'est pas un côté partagé au sens de cette règle En effet, les normales respectives à ces faces, référencées 24, 25 pointent l'une vers le demi-espace extérieur à l'objet dont fait partie ces faces, et l'autre vers le demi-espace intérieur à cet objet En fait, il aurait fallu considérer la face opposée à l'une des deux faces 22 ou 23. On a représenté en figure 4 un exemple de face "concave" 26 Une face est dite concave lorsqu'au moins le prolongement de l'un de ses côtés la coupe Elle est dite convexe dans le cas contraire Ainsi, le prolongement 27 du côté 28 ou le prolongement 29 du côté 30 de la face 26 coupe cette face. On a représenté en figure 5 un exemple de face concave rectangulaire trouée 31 comportant quatre trous rectangulaires 32 à 35 Le prolongement de l'un quelconque des trous 32 à 35 coupe la face 31, qui est donc bien concave. On a représenté en figure 6 un tableau donnant les trois catégories d'éléments définissant la topologie d'une hyperfacette. Ces éléments sont les côtés, les points (extrémités des côtés) et les faces de l'hyperfacette Pour chaque catégorie d'éléments on définit des attributs: pour les côtés: ce sont les attributs topologiques, à savoir, pour chaque côté, les points Pl et P 2 et les faces gauche et droite (ou l'une de ces faces si le côté n'est pas partagé), et les liaisons entre côtés; pour les points: leurs attributs géométriques, c'est-à-dire leurs coordonnées dans l'espace (X, Y et Z); et pour les faces: leurs attributs géométriques et leurs attributs photométriques Les attributs géométriques sont les équations, dans l'espace, des plans des faces (de la forme Ax + By + Cz + D = 0). Leurs attributs photométriques comportent: leur couleur, leur texture et leur transparence. Une première étape du procédé de l'invention consiste à éliminer les faces auto-cachées, afin de simplifier les traitements subséquents du processeur géométrique. Lorsque l'on observe un objet, on ne peut en voir certaines faces que si l'on se trouve dans un angle de vue particulier On utilise cette propriété pour dire que si une face n'est pas orientée en direction de l'observateur, elle ne peut être vue par lui, et elle est alors dite autocachée En figure 7, on a représenté à droite la position X d'un observateur et deux faces 36, 37, ainsi que les normales 38, 39, respectivement, à ces faces La normale 38 se trouve dans le demi-espace (délimité par le plan de la face 36) vu de X, tandis que la normale 39 se trouve dans le demi-espace (délimité par le plan de la face 37) non vu de X. Mathématiquement, la visibilité d'une face est déterminée de la façon suivante: soit Ax + By + Cz + D l'équation de la face en question et lxo, yo, zo I la position de l'observateur Si Ax O + Byo + Czo + D Lorsque la position de l'observateur varie, les objets, et en particulier leurs points subissent un changement de repère, se traduisant par une rotation et/ou une translation Ce changement de repère est effectué par un processeur géométrique selon la formule suivante, qui permet d'exprimer les coordonnées absolues de chaque point (xm, Ym, Zm) dans le repère de l'observateur (xo, yo, zo) lxol r 11 '12 '13 ml x yo =r 21 r 2 r 23 Ym + ty ( 1) sZo r 1 12 r FX 1 L_ JL 22 32 33 j Lm, + lt ( 1 on peut ajouter le cas échéant des facteurs d'échelles à cette matrice. Dans cette équation, les coefficients r 11 à r 33 se rapportent aux rotations et les coefficients tx, ty, tz aux translations Ces calculs sont effectués de manière vectorielle. Lorsque les coordonnées des points des objets sont calculées dans le repère de l'observateur, on procède à une troncature dans l'espace, afin d'éliminer tous les éléments se trouvant entre l'observateur et un plan de troncature dit plan de troncature avant Ce plan, perpendiculaire à la direction d'observation, pouvant être entre l'observateur et le plan de projection ou au-delà de ce plan de projection Les facettes tronquées par le plan de troncature avant sont découpées puis refermées par l'ajout d'un côté, comme décrit ci-dessous pour la troncature en 2 D, mais ici elle est effectuée en 3 D Le cas échéant, on procède de même avec le plan de troncature arrière, qui est par exemple le plan de limite de visibilité (ligne d'horizon). On a représenté en figure 8 la pyramide d'observation 40 relative à un observateur 41, c'est-à-dire la pyramide dont les arêtes joignent l'observateur 41 (supposé ponctuel) aux sommets du plan de projection 42 La direction d'observation Zobs est perpendiculaire au plan de projection 42 On a représenté le plan de clipping avant 43, généralement parallèle au plan 42, situé entre ce plan 42 et l'observateur, et un plan de clipping arrière 44, situé au- delà du plan 42 et parallèle à celui-ci La pyramide tronquée de visualisation est la portion de la pyramide 40 comprise entre le plan de clipping 43 et le plan de projection 42, ou éventuellement entre les deux plans de clipping 43, 44 On a représenté également en figure 8 les angles de vue horizontal Ox et vertical Oy. Une fois ce "clipping" en trois dimensions effectué, on effectue une mise en perspective afin de visualiser sur un écran plat, donc en deux dimensions ( 2 D), les objets à trois dimensions ( 3 D), tout en conservant l'effet visuel de ces trois dimensions La projection la plus simple est celle faisant appel au théorème de Thalès, et est illustrée en figure 9 On y a représenté, en vue de côté, un objet 45 (en 3 D) à visualiser sur une fenêtre de visualisation 46, l'observateur 47 supposé ponctuel regardant dans la direction de visée 48 perpendiculaire à la fenêtre 46 Soit 49 un point quelconque de cet objet La droite joignant 47 à 49 coupe la fenêtre en 50 On appelle Hi et H 2 les distances respectives des points 49 et 50 à la droite 48, et Ll, L 2 les distances respectives de l'observateur 47 à la hauteur Hi et à la fenêtre 46 Selon le théorème de Thalès, on a: LI/Hl = L 2/H 2 Il est donc facile de déterminer l'emplacement sur l'écran 46 du point 50 qui est la projection en perspective du point 49 sur l'écran 46 On procède de la même façon pour tous les points de l'objet 45. Par convention, et pour des raisons d'efficacité, en même temps, on normalise les coordonnées xe, Ye de tout point de l'écran 46: -1 xe On a représenté en figure 10 le "volume de clipping normalisé" défini entre l'observateur ponctuel 51 et l'écran normalisé 52 La direction de visée 53, perpendiculaire à l'écran 52, passe par son centre 54 (de coordonnées 0, 0) On a référencé 55 à 58 les milieux des côtés de l'écran 52, de coordonnées normalisées respectives ( 0, 1,), ( 1, O), ( 0, -1), (-1, O) Les arêtes menées du point 51 aux points 55 à 58 sont respectivement référencées 59 à 62 Les angles formés par les arêtes 59, 61 d'une part et 60, 62 d'autre part ont une valeur normalisée de 900 Pour effectuer la mise en perspective, on utilise les paramètres suivants dpp: distance entre l'observateur et l'écran de projection, H 1/2 demi- hauteur de l'écran, L 1/2 demi-largeur de l'écran, e Ox' L 1/2 Fx = cotéy) = d: facteur de normalisation en x, (Oy' 11/2 Fy= cot =: facteur de normalisation en y. k Z} dpp On obtient alors les équations de projection suivantes x x O e Zo Fx e Zo Fy Une fois les informations géométriques déterminées dans le repère écran en deux dimensions, on projette toutes les équations fournissant les autres informations nécessaires à la visualisation profondeur, texture, ombrage, Pour projeter les plan des facettes, on utilise les équations de projection suivantes Axm + B Ym + C Zm + D O lBI Vecteur normal du plan normalisé ( 2) CS Distance du point origine du repère absolu au plan L'équation ci-dessus est définie dans le repère spatial absolu Pour la transformer dans le repère de l'observateur (A', B', C', D'), on utilise la transformation matricielle suivante FA rl, r 12 r 13 Ai i' r 21 =l 2 r r 23 c( 3) D' = D Atx Bty Ctz On calcule la profondeur z, ou plus précisément son inverse N = 1/z, à partir des valeurs normalisées Xe et Ye à l'aide de l'équation A'Fx B'F c' X xx y ' D' e Dl e Dl Les paramètres autres que géométriques, dont on connaît les équations dans le repère trois dimensions, sont transformés de la façon suivante lors de la projection sur l'écran Soit K la valeur de l'un quelconque de ces paramètres (texture, ombrage, luminance,) L'équation donnant K dans le repère monde à trois dimensions est de la forme: K= Px+ P Ym+ y Zm+ ( 5) Pour effectuer la projection, on fait subir aux coefficients (a, ô, y et 5) les transformations de l'équation 3, ce qui donne de nouveaux coefficients (a', Pf', Y et 3 ') L'équation donnant le paramètre K en fonction des coordonnées écran normalisées Xe et Ye est: K= A'F B' ' t 6 A Fxxe e + C' A Xx y,+ 5 ' D' e D Ye D' ax'Fx + 13 'F ye + YI = +' Selon l'invention, on procède à un clipping en trois dimensions, par la pyramide de visualisation telle que définie ci- dessus en référence à la figure 8, afin d'éliminer tout ce qui dépasse des bords de l'écran de projection. Ceci revient à exécuter le clipping d'une hyperfacette par un volume convexe délimité par k plans (ici k = 4). Tout d'abord, on recherche les faces qui doivent être réellement clippées, c'est-à-dire que l'on élimine d'office celles qui ne doivent manifestement pas être clippées: les faces auto- cachées, les faces se trouvant entièrement à l'extérieur de la pyramide de clipping, et celles se trouvant entièrement à l'intérieur de cette pyramide On marque (par exemple par un drapeau de codage) et numérote les faces restantes, qui doivent donc être clippées. Ensuite, pour chacun des k plans de clipping, on examine tour à tour chacun des côtés d'une hyperfacette coupé par le plan de clipping, et on calcule de manière vectorielle pour chacun d'eux le point d'intersection avec le plan de clipping Puis, on "raccourcit" les côtés d'origine pour ne garder que leurs parties se trouvant à I'intérieur de la pyramide de clipping, ce qui revient à pratiquer un clipping de lignes On détermine ainsi les points d'intersection de ces côtés avec le plan de clipping correspondant, et on trie ces points d'intersection par numéro de face de l'hyperfacette, puis le long de la droite de clipping orientée (orientation arbitraire) Enfin, on parcourt la liste triée des points d'intersection et on les relie deux à deux, c'est-à-dire que l'on rajoute des côtés entre ces points afin de refermer les faces. On va maintenant exposer en détail le procédé de sélection des faces à clipper Cette sélection fait appel à un code binaire de P bits attribué à chaque sommet de l'hyperfacette, indiquant sa position par rapport aux P plans de clipping Dans ce code, le bit k (k allant de 1 à P) correspondant au plan k est par exemple à O si le sommet se trouve dans le demi-espace intérieur de ce plan (le demi-espace intérieur est celui contenant la normale intérieure au plan, comme exposé ci-dessus en référence à la figure 2) La sélection des faces à clipper est réalisée au moyen de tests logiques sur ces codes binaires: une face est entièrement visible (n'est pas à clipper) si tous ses côtés sont à l'intérieur de la pyramide de clipping Dans la relation suivante, "U" représente un OU binaire: U codesoet = O ( 7) sonimt E face une face doit être clippée si au moins un de ses côtés intersecte ou si tous ses côtés entourent la pyramide de clipping Le test est le suivant (dans cette relation, "A " est un ET binaire) 3 cote E face codesonmmet 1 ^ c desonmt 2 = O ou U codesomnetl A codesommet 2 = 111 ( 8) cote E face Pour vérifier cette relation, soit il faut et il suffit qu'un côté d'une face coupe le plan de clipping (un de ses sommets est dans le demi-espace intérieur, et l'autre sommet dans le demi- espace extérieur), soit il faut que les côtés de la face entourent la pyramide (donc que tous les bits de l'union des codes des intersections des côtés soient à 1) Ce test est plus complexe que la simple intersection des codes de chaque sommet de la face, mais permet d'éliminer les faces coupées par un ou plusieurs plans mais extérieurs à la pyramide. Bien entendu, les autres faces, qui ne répondent pas à ces tests, sont extérieures à la pyramide et ne sont pas sélectionnées. Les côtés des faces à clipper étant clippés dans n'importe quel ordre, il est nécessaire de trier les points d'intersection avant de refermer ces faces Le critère de tri (coordonnée x ou y des points d'intersection) varie, bien entendu, selon la plan de clipping concerné Selon le procédé de l'invention, on trie ces points d'intersection par plan de clipping. Pour le clipping en deux dimensions, on oriente arbitrairement les bords de la fenêtre de visualisation, par exemple de gauche à droite pour les bords horizontaux, et de haut en bas pour les bords verticaux Le critère de tri est donc la coordonnée x ou y du point d'intersection. Pour le clipping en trois dimensions, il faut tenir compte du fait que la droite d'intersection du plan de clipping et du plan de la face à clipper peut avoir n'importe quelle pente Ainsi, par exemple, en figure 11, on a représenté un plan de clipping 63 dans le repère orthonormé Oxyz (Oz étant la direction d'observation, à laquelle le plan 63 est perpendiculaire, ce plan étant à une distance z = dpa de l'observateur) Sur la figure 11, on a représenté trois parties de faces coupées par le plan 63 et référencées 64 à 66 Les parties de faces visibles en figure 1 I sont celles se trouvant au-delà du plan 63 (par rapport à l'observateur) Les droites d'intersection respectives Dl à D 3 ont des pentes différentes et quelconques par rapport aux axes Ox et Oy On ne peut donc pas décider de trier arbitrairement selon les coordonnées en x ou en y. Le plan de clipping étant perpendiculaire à Oz, son équation est très simple, et les coefficients a et b de l'équation de la face clippée caractérisent directement la pente de la droite d'intersection L'équation de cette droite est de la forme fax + by + cz + d = O LZ= dpa soit, après substitution y = a x + K ( K = constante b On détermine alors le critère de tri (en 3 D) de la façon suivante: si (lai Pour terminer le clipping, il faut fermer les faces clippées. Pour cela, il faut déterminer quelle est la face gauche et quelle est la face droite du nouveau côté (joignant les côtés raccourcis) Ce nouveau côté se situe sur le plan (ou la droite) de clipping Ce n'est donc pas un côté partagé Sa deuxième face est la face droite ou gauche de l'un des côtés clippés. Pour le clipping 2 D, l'orientation de la droite de clipping permet à elle seule de dire s'il s'agit de la face droite ou de la face gauche On a représenté en figures 12 et 13 respectivement, conformément aux conventions décrites ci-dessus en référence à la figure 2, le cas o la face visible F est une face gauche (par rapport au segment orienté de Il vers 12), et le cas o la face visible F est une face droite (toujours par rapport au segment orienté de Il vers 12). Dans le cas du clipping 3 D, il faut connaître également le sens de la normale (i) à la face à clipper On a représenté en figures 14 et 15 les deux cas possibles, en se référant aux conventions établies en référence à la figure 2 Pour ces deux cas, on clippe une face triangulaire F dont la partie se trouvant à droite (telle que vue sur le dessin) du plan de clipping 67 subsiste Les cas des figures 14 et 15 se distinguent seulement par l'orientation de la normale il à la face à clipper, ce qui fait que dans le cas de la figure 14, on ne garde que la face droite, et dans le cas de la figure 15, on ne garde que la face gauche L'équation de cette normale est de la forme: ax + by + cz + D = O A priori, on pourrait penser que les signes des trois paramètres a, b, c et le critère de tri peuvent influer sur le choix final, ce qui obligerait à examiner seize cas En fait, après étude de tous ces cas, on s'aperçoit qu'en effectuant des regroupements appropriés, leur nombre se réduit à deux Le premier cas se présente lorsque le tri doit se faire selon l'axe Ox et lorsque b O, et dans ce cas, la face gauche doit être conservée Le deuxième cas se présente lorsqu'aucune de ces deux conditions n'est remplie, et la face droite doit alors être conservée. Le procédé de visualisation décrit ci-desus est avantageusement suivi d'un processus d'élimination des parties cachées (processus tel que: "Z-Buffer", tri topologique, balayage de lignes,). REVEND I CATI ON S 1 Procédé de visualisation d'images synthétiques de volumes en temps réel, caractérisé par le fait qu'il consiste à s mémoriser dans une base de données les données décrivant les volumes à représenter sous forme de polyèdres à partir de leurs côtés orientés, ces données étant les attributs topologiques des côtés des polyèdres, les coordonnées dans l'espace des extrémités de ces côtés, et les attributs géométriques et photométriques des faces de ces polyèdres, à éliminer les faces autocachées de ces polyèdres, à effectuer un changement de repère des faces à visualiser, à éliminer tous les objets se trouvant entre l'observateur et le plan de troncature avant, à effectuer une mise en perspective pour projection en deux dimensions, et à effectuer une troncature vectorielle en deux dimensions suivant une pyramide de projection. 2 Procédé selon la revendication 1, caractérisé par le fait que la troncature s'effectue de manière vectorielle pour chacun des plans délimitant ledits polyèdres, et pour chacun de ces plans, on effectue une troncature selon chacun des côtés des faces des polyèdres, et on referme les faces tronquées. 3 Procédé selon la revendication 1 ou 2, caractérisé par le fait qu'une face est auto-cachée si: Axo + Byo + Czo + D manière vectorielle. 4 Procédé selon l'une des revendications précédentes, caractérisé par le fait que le changement de repère se fait par rotation et translation afin d'exprimer les coordonnées absolues des points des objets dans le repère de l'observateur. Procédé selon l'une des revendications précédentes, caractérisé par le fait que la mise en perspective se fait par application du théorème de Thalès (figure 9). 6 Procédé selon l'une des revendications précédentes, caractérisé par le fait que la troncature est effectuée à tour de rôle pour chacun des plans de troncature, et dans chaque plan, pour chacun de tous les côtés à tronquer. 7 Procédé selon la revendication 6, caractérisé par le fait que pour effectuer la troncature des côtés, on sélectionne les côtés à tronquer, on calcule pour chacun d'eux le point d'intersection avec le plan de troncature, on raccourcit ces côtés, on trie les points d'intersection par face sur la droite de troncature, et on relie les points d'intersection deux à deux avec des côtés correctement orientés. 8 Procédé selon l'une des revendications précédentes, caractérisé par le fait qu'avant d'effectuer les troncatures, on recherche les faces qui doivent être réellement tronquées et on les marque. 9 Procédé selon l'une des revendications précédentes, caractérisé par le fait qu'il est suivi d'un processus d'élimination des parties cachées.