FR 2703803 A1 19941014 FR 9304054 A 19930406 Procédé de génération d'images de synthèse La présente invention concerne un procédé de génération d'images de synthèse. Elle se rapporte notamment au domaine du traitement d'images par calculateurs numériques, ou calculateurs graphiques travaillant sur les données d'espaces à 3 ou 4 dimensions. Une application importante des calculateurs graphiques réside dans la possibilité qu'ils ont de simuler des scènes en 3 dimensions. Dans ces calculateurs les comportements dans un espace virtuel des objets où leur aspect virtuel sont calculés et visualisés pour donner aux concepteurs les moyens de déterminer les caractéristiques réelles qu'ils doivent posséder dans un espace réel. C'est pourquoi, il est généralement plus commode, moins coûteux, plus rapide et davantage efficace d'utiliser des méthodes qui permettent de voir des scènes virtuelles en 3 ou 4 dimensions que d'essayer de construire celles-ci de façon réelle, aussi bien que de tester leur effet virtuel que de faire ces mêmes tests sur des objets réels. Souvent le travail de simulation est effectué par un système de calcul et une représentation numérique des scènes et des images a lieu en mettant en oeuvre des techniques de génération et de simulation visuelle. Les techniques de synthèse d'images fournissent quelquefois des images très impressionnantes qui sont de plus en plus proches de la réalité. Néanmoins pour certaines applications, les méthodes de modélisation nécessitent souvent d'être améliorées et demandent plus de modèles reposant sur des données physiques pour atteindre un niveau de réalisme adéquat. Ce niveau de réalisme est hautement nécessaire pour atteindre les buts ordinairement assignés aux simulations qui est de "faire comme si" et pas seulement de "paraître comme si". Cela signifie par exemple, que l'illumination ou les calculs de zones d'ombres doivent être aussi corrects que possible. C'est pourquoi il est préférable d'utiliser des modèles reposant sur des données physiques1 toutes les étapes de traitement de synthèse de type "pipe-line" par exemple devant être très précises respectivement aux hypothèses qui les lient au modèle physique. Aussi dans ces chaînes de traitement, une approche rigoureuse est souhaitable afin de fournir des images de haute qualité aussi bien au plan visuel qu'au plan de la modélisation. Les systèmes de génération de scènes par calculateur souvent représentent des objets solides par une représenta tion surfacique. Cela permet de faire des approximations sur les surfaces en prélevant des échantillons de points structurés à l'intérieur de polygones plans. Les données correspondantes sont réduites en tenant compte de leur usage antérieur au cours des étapes qui suivent le procédé de synthèse "pipe-line". Les calculs d'illumination sont exécutés en prenant en compte la propagation énergétique des ondes à partir de sources rayonnantes telles que des sources de lumière, sources de radiation etc. dirigées directement sur l'ensemble de la scène, sans dispersion et atténuation par réfraction ou réflexion. Dans ce procédé qui est souvent désigné dans le langage anglosaxon par "Rendering by Energy exchanges and direction models", les ondes peuvent être arrêtées à cause d'occlusions qui peuvent apparaître entre le point ou l'élément de surface à partir duquel les ondes sont émises et un élément de surface ou un point qui les reçoit. Ceci est la cause d'ombre et de pénombre. Des erreurs et des artefacts peuvent apparaître dans les résultats lors de l'exposition d'objets en dessous de parties ombragées ou de pénombres et lors des visualisations d'images. Elles sont dues à des déterminations mauvaises de la visibilité de ces objets. Pour cela une détermination de visibilité précise est hautement souhaitable afin de corriger de tels défauts. Ceci est généralement fait par calculs géométriques. A titre d'application de ceci, la méthode d'illumination par exposition à un rayonnement d'onde est très prometteuse car elle conduit les calculs d'illumination qui donnent de bons résultats. Cette méthode d'illumination propose un modèle global de traitement des échanges d'énergie lumineuse. Elle offre une solution qui est indépendante de l'angle de vue et qui prend soin des relations entre les objets de la scène illuminée et les calculs d'ombre. Cette méthode peut être exécutée en plusieurs étapes reliées séquentiellement ensemble. Une première étape consiste à propager les ondes des sources actives vers des éléments du récepteur, au cours de cette étape la détermination de la visibilité doit être fournie entre les entités associés cidessus avec soin et précision. Selon une deuxième étape une deuxième propagation est conduite à partir des premiers récepteurs vers des éléments récepteurs de la scène restante est fonction de densité de réflexion et d'émission des éléments physiques. Finalement les données d'illumination d'échantillons sont interpolées afin de fournir des valeurs d'illumination n'importe où dans la scène à 3 dimensions, dans le voisinage des points ou des surfaces illuminés. Ceci est exécuté par un processus d'interpolation d'illumination ou "shading". Les techniques de détermination de visibilité ont pour but de fournir les parties visibles d'ensembles de surface à partir duquel la scène à 3 dimensions est composée en rapport avec une spécification de visibilité. A ce titre, il est connu deux approches différentes qui sont décrites par exemple dans le recueil de MM. Foley, Van Dam and co. "Computer Graphics" ayant pour titre "Principles and Practice" décrit dans la deuxième édition d'Addison Wesley. La première est définie comme une technique d'espace image où toute surface visible d'un pixel donné dans une image est traitée suivant un certain nombre de méthodes décrites dans les articles suivants: - Catmul "A Subdivision Algorithm for Computer Display of Curved Surfaces" PhD Thesis, Report UTEC-CSc-74-133, Computer Science Department, University of Utah, Salt Lake City, UT, December 1974. - Warnock "A Hidden-Surface Algorithm for Computer Generated Half-Tone Pictures" Technical Report TR 4-15, NTIS AD-753 671, Computer Science Department, University of Utah, Salt Lake City, UT, June 1969. - Weiler and Atherton "Hidden Surface Removal Using Polygon Area Sorting" SIGGRAPH'77 214-222. - Catmull "A Hidden-Surface Algorithm with Anti-Aliasing", SIGGRAPH'78 6-11. - Carpenter "The A-buffer, an Antialiased Hidden Surface Method", SIGGRAPH'84 103-108. et Appel "Some techniques for Shading Machine Renderings of Solids" SJCC 1968, 3745. La deuxième approche est définie comme étant une technique d'espace objet et elle consiste à comparer chaque élément de surface aux autres à partir d'un point de vue en sélectionnant ou en éliminant des parties de celui-ci de la façon par exemple décrite dans les articles: Roberts "Machine Perception of Three Dimensional Solids" Lincoln Laboratoy, TR 315, MIT - Cambridge, MA, May 1963. Apple "The Notion of Quantitative Invisibility and the Machine Rendering of Solids" Proceedings of the ACM National Conference, Thomson Bockes Washington DC, 1967. Cependant ces deux approches peuvent être utilisées ensemble comme cela est décrit par exemple dans les articles: Warnock "A Hidden-Surface Algorithm for Computer Generated Half Tone Pictures" Technical Report TR 4-15, NTIS AD-753 671, Computer Science Department, University of Utah, Salt Lake City, UT, June 1969. - Weiler and Atherton "Hidden Surface Removal Using Polygon Area Sorting" SIGGRAPH'77 214-222. et Catmull "A Hidden-Surface Algorithm with Anti-Aliasing", SIGGRAPH'78 6-11. Afin de réduire la charge de calculs pour déterminer la visibilité, plusieurs tests sont exécutés pour réduire les éléments de surfaces candidats en morcelant les éléments de surface ou pour être dans la ligne de vue du pixel courant Ces techniques sont connues sous les vocables, test de "Bounding-Box", tests de "MIN-MAX" et de "back-face culling". Elles sont décrites dans le recueil de MM. Foley, Van Dam and co. cité précédemment. En supplément à ces tests la base de données est structurée de façon à réduire les calculs en exécutant les calculs de visibilité finaux seulement si c'est nécessaire car ceux-ci sont généralement coûteux en temps de calcul et demandent à être exécutés rapidement. Pour atteindre ce but différentes méthodes sont utilisées telles qu'un découpage spatial en arbre à 4 branches ou 8 branches en utilisant une décomposition binaire et en arbre type BSP tel que décrit également dans le recueil de MM. Foley et Van Dam and co cité précédemment, positionnement adaptatif utilisant un critère de gradient d'illumination pour obtenir une meilleure détermination des ombres tel que défini dans l'article de MM. Hanrahan et Salzman ayant pour titre "A Rapid Hierarchical Radiosity Algorithm for Unoccluded Environment" Eurographics Workshop on Photosimulation, Realism and Physics in Computer Graphics, 25(4):1 97-206, August 1991. Tous ces filtrages permettent d'utiliser au minimum les traitements de visibilité réelle définie dans le recueil de MM. Foley, Van Dam et co. Les déterminations de visibilité ont lieu sur différents types de données et peuvent reposer sur les structures de données décrites précédemment. Les tests de visibilité de l'article de M. Robert a lieu en considérant une ligne de paramètres à partir d'un point de vue sur un contour en cours de test, et un polyèdre de la scène. Dans l'article de Apple les intersections des bords sont calculées avec les faces avants de polygones pour mettre à jour des paramètres d'invisibilité. Les techniques connues sous le nom de "depth-buffer" ou "z-buffer" déterminent pour chaque pixel quel est élément de surface de la scène à 3 dimensions qui est la plus proche. Il détermine la précision de l'image. Dans l'algorithme de Warnock il est fait état d'une subdivision de surface adaptative où le polygone projeté a un rapport spécifique avec la surface courante en cours de traitement. On recherche si la surface est entourée par le polygone projeté ou si elle l'intercepte, ou si elle le contient ou si elle est disjointe de lui. La subdivision est réalisée à chaque étape en utilisant un bornage rectangulaire. L'algorithme de Weiler and Atherton est similaire mais la subdivision a lieu le long des bords d'un polygone. L'algorithme, objet précision de Catmull compare seulement des fragments de polygone qui se projettent sur chaque pixel en prenant en compte la quantité de pixels couverte par les parties visibles de chaque fragment. La méthode "A-Buffer" est une approximation de la précédente dans le sens qu'elle approxime la quantité de pixels couverte par les parties visibles de chaque fragment en utilisant un masque discret de 4x8 bits pour chaque pixel dont on a besoin. Des faisceaux de droites peuvent aussi être utilisés en tirant une droite par pixel et en conservant l'intersection la plus proche existante avec la scène 3D et ltélément de surface associé. Lorsqu'une précision d'image est demandée le principal problème qui est rencontré est le phénomène d'aliasing qui peut être vu comme un problème d'échantillonnage. Cela peut être la cause dans les traitements "pipe-line" d'obtention d'ombres de mauvaises qualités. Dans le monde virtuel à 3 dimensions les ombres et les pénombres peuvent avoir une mauvaise qualité du fait d'un contour d'ombre défectueux. De ce fait des effets montrant des discontinuités de premier ordre ou des gradients artefacts peuvent apparaître. Ceci est dû à une détermination de la visibilité imparfaite relativement par exemple aux sources d'émission de lumière par exemple. Pour pallier à ces inconvénients il existe cependant des méthodes numériques assez coûteuses telles que celles décrites dans les articles de Catmull et Carpenter cités précédemment où des traitements analytiques tels que ceux de Roberts and Apple cités précédemment qui peuvent être exécutés. De la même façon, lorsqu'il faut faire apparaître sur un écran l'image finale en deux dimensions il est hautement nécessaire pour chaque pixel de connaître la contribution de chaque élément de surface visible pour obtenir une qualité visuelle acceptable. II en est de même dans l'espace objet pour obtenir avec une qualité suffisante une représentation réaliste. Le but de l'invention est de pallier les inconvénients précités. Considérant une scène à 4 dimensions décrite à un instant donné par un ensemble de polygones plans et un point de la scène à 3 dimensions considéré comme le point de projection courant, le problème est de définir les parties visibles de chaque polygone plan respectivement les uns par rapport aux autres à partir du point de projection. A cet effet, l'invention a pour objet un procédé de génération d'images de synthèse du type consistant: - à évaluer une scène dans l'espace à 3 dimensions à partir de données d'entrée représentative d' une scène dans un espace à 4 dimensions décrite à chaque instant déterminé par un ensemble de polygones plans, et à sélectionner les polygones plans correspondant aux objets de la scène à 3 dimensions, caractérisé en ce qu'il consiste: - à projeter sur un hémisphère centré autour d'un point de la scène à 3 dimensions les polygones sélectionnés, et à calculer les intersections des polygones sur l'hémisphère de projection en laissant apparentes les parties visibles. D'autres caractéristiques et avantages de l'invention apparaîtront ciaprès à l'aide de la description qui suit faite en regard des dessins annexés qui représentent: - La figure 1 le mode de projection hémisphérique mis en oeuvre par l'invention pour effectuer les calculs de visibilité d'une scène à trois dimensions. - La figure 2 une illustration du procédé mis en oeuvre par l'invention pour la détermination de la visibilité. - Les figures 3 et 4 des schémas blocs pour illustrer les étapes du procédé selon l'invention. - La figure 5 un organigramme pour illustrer un mode de sélection d'éléments de surface. - La figure 6 une illustration d'un mode de test "back face culling". - La figure 7 une illustration d'un mode de test "MIN-MAX". - La figure 8 une illustration d'un mode de sélection de secteurs. - La figure 9 un organigramme figurant le procédé de calcul géométrique mis en oeuvre par l'invention. - La figure 10 un organigramme figurant le mode de gestion des intersections mis en oeuvre par l'invention. - La figure 11 un exemple pour illustrer le mode de traitement des intersections montré à la figure 10. Contrairement aux procédés connus de l'art antérieur cités précédemment qui développent des méthodes précises de traitement numériques dans un espace image7 l'idée de l'invention est de développer une méthode analytique de traitement dans un espace objet, dans le but de fournir des résultats précis dans la détermination de la visibilité de scènes à 3 dimensions. Selon l'invention la détermination de la visibilité a lieu en découpant l'espace surfacique de la scène en polygones et en observant chaque polygone à partir d'un point déterminé, en tenant compte des autres polygones de la scène 3D. Ceci est obtenu comme le montre la figure 1 en projetant segment par segment chaque polygone à traiter, sur un hémisphère centré au point d'observation. La visibilité des polygones est testé séquentiellement pour chaque polygone caché candidat par une mise à jour du polygone visible courant en fonction des modifications de visibilité de celui projeté précédemment, qui peut être partiellement caché comme le montre l'exemple de la figure 2. Le procédé selon lequel les modifications sont exécutées consiste d'abord à projeter chaque segment d'un polygone caché candidat sur l'hémisphère défini précédemment puis à calculer les intersections utiles entre chaque segment projeté avec ceux visibles précédents, et finalement à créer un nouvel ensemble de segments visibles par gestion d'un nouvel ensemble de points, composés de sommets projetés, auquel sont ajoutés les intersections des projections des segments sur l'hémisphère en fonction de l'orientation du contour visible et du contour caché candidat. Des cas particuliers sont également pris en compte dans ce traitement, les trous et les occlusions totales pouvant être pris en compte séparément. Comme la base de données qui est ainsi créée ne prend pas en compte les artefacts causés par des polygones non plans, ou par des poly gones entrelacés sans arête de séparation, un préfiltrage est réalisé durant l'évaluation de la scène 3D afin de supprimer l'apparition de ces artefacts. Comme le montre les blocs des diagrammes des figures 3 et 4 le procédé de synthèse opère sur des données d'entrée représentatives d'une scène imaginée dans un espace à 4 dimensions (3 dimensions par la géométrie plus 1 dimension pour le temps) et sur des paramètres de visibilité et d'illumination de la scène à construire. La scène obtenue en sortie du traitement est modifiable en fonction des données et paramètres d'entrées appliqués sur les blocs diagrammes des figures 3 et 4. Selon le diagramme de la figure 4, la synthèse des images a lieu suivant une succession d'étapes référencées 1 à 5. A l'étape 1 une évaluation de la scène dans l'espace à 3 dimensions est effectuée pour un instant donné à partir des spécifications de la scène à construire de l'espace à 4 dimensions représentées par les données d'entrée. A l'étape 2 les paramètres d'environnement de la scène 3D sont sélectionnés et les éléments de surface correspondant sont échantillonnés. A l'étape 3, un calcul géométrique est effectué pour déterminer la visibilité des éléments de surface composant la scène observée. A l'étape 4 les couplages d'énergie rayonnée entre les éléments surfaces visibles sont déterminés pour en déduire à l'étape 5 les zones d'ombres et les zones illuminées portées sur les éléments de surface. La sélection des éléments de surface de l'étape 2 a lieu suivant les étapes 6 à 10 de l'organigramme de la figure 5. Aux étapes 6 et 7 une sélection d'un polygone composant un élément de surface et une sélection du point de projection ont lieu de façon connue en fonction des spécifications d'éclairage et de visibilité de la scène. Aux étapes 8 et 9 un test de d'orientation relative type "Back Face culling" et un test "MIN-MAX" sont effectués de façon connue pour trier les éléments de la scène 3D par rapport à leurs distances respectives, leur orientation et leur visibilité comme le montre les figures 6 et 7. Sur la figure 6 par exemple, les orientations des éléments de surfaces sont déterminés par les directions des normales N1 et N2 aux surfaces des polygones S1 et S2 relativement à la normale Ng à un disque plan So Pour les polygones plans P1, P2 et P3 de la figure 7 le test MIN-MAX consiste à tracer des faisceaux de droites à partir d'une origine O, d'un plan Po, pour en déduire à partir des intersections des droites du faisceau avec les plans P1, P2 et P3 qu'elles sont les plans qui en occultent d'autres c'està-dire qui se projettent l'un sur l'autre par les droites du faisceau. Dans l'exemple, il apparaît d'après le tracé des droites D1 et D2 que seul le plan P1 peut occulter le plan P2. La sélection des secteurs de l'étape 10 a lieu de la manière représentée à la figure 8 en utilisant l'intersection des surfaces vue à partir du point de vue O. Le calcul géométrique 3 a lieu suivant les étapes de traitement référencées de 11 à 16 sur la figure 9. A l'étape 11 une sélection de polygones a lieu dans une liste d'éléments de surfaces formant la scène 3D. Une projection sur l'hémisphère de la figure 1 a lieu à l'étape 12, en normalisant les vecteurs de projection reliant la projection du point courant avec les sommets du polygone caché courant. A l'étape 13 la projection sur l'hémisphère s'effectue en même temps qu'une mise à jour de l'élément de surface visible courant projeté en tenant compte de l'évolution de sa visibilité. A l'étape 14 un calcul d'intersection des arcs de cercle résultat de la projection des côtés des polygones sur l'hémisphère est effectué par application des relations de la trigonométrie sphérique. L'étape 15 détermine la validité de l'intersection trouvée en vérifiant que l'intersection s'étend sur la surface de la sphère. Une gestion des intersections est effectuée à l'étape 16, selon les étapes 17 à 21 de l'organigramme de la figure 10. A l'étape 17, s'il n'y a pas d'intersections, des tests ont lieu pour vérifier l'existence de trous ou d'occlusions totales. A l'étape 18, si des trous ou des intersections sont créés, ceux-ci sont insérés aux listes des sommets du polygone caché courant projeté et de l'élément de surface visible projeté courant. Deux listes sont ainsi créées, une pour chaque élément de surface, toutefois les points projetés, intersections et sommets sont listés dans le sens des aiguilles d'une montre pour l'élément de surface visible courant et dans le sens inverse pour le polygone caché courant. Afin de détecter quels sont les points communs aux deux listes, I'étape 19 fournit des drapeaux de commutation pour indiquer les points similaires aux deux listes. Durant l'étape 20, les deux listes sont examinées pour indiquer les parties visibles de l'élément de surface caché courant projeté en rapport avec le polygone caché courant. Ainsi pour chaque sommet d'un élément de surface visible projeté courant la première liste est examinée jusqu'à ce qu'un point commun aux deux listes soit trouvé. La deuxième liste est ensuite examinée dans le sens inverse des aiguilles d'une montre à partir du point trouvé précédent jusqu'à ce qu'un nouveau point commun soit trouvé, et ainsi de suite jusqu'à ce que chaque point de la liste 1 ait été analysé. Ceci permet de créer un nouveau polygone projeté, celuici n'étant toutefois gardé que s'il est listé dans le sens des aiguilles d'une montre, autrement celui-ci ne peut être considéré comme étant visible à partir du point courant. L'exemple de la figure 11 illustre le balayage des deux listes. Celle-ci figure un élément de surface visible courant listé dans le sens des sommets A B I C J D A et un polygone caché courant projeté listé dans le sens G F I E J H G. Le nouvel élément de surface obtenu est formé des sommets A B I E J D A listés dans le sens des aiguilles d'une montre. REVENDICATIONS 1 Procédé de génération d'images de synthèse du type consistant: - à évaluer (1) une scène dans l'espace à 3 dimensions à partir de données d'entrée représentatives d'une scène dans un espace à 4 dimensions décrite à chaque instant déterminé par un ensemble de polygones plans, et à sélectionner (11) les polygones plans correspondant aux objets de la scène à 3 dimensions, caractérisé en ce qu'il consiste: - à projeter (13) sur un hémisphère centré autour d'un point de la scène à 3 dimensions les polygones sélectionnés, et à calculer (14) les intersections des polygones sur l'hémisphère de projection en laissant apparentes les parties visibles. 2. Procédé selon la revendication 1 caractérisé en ce qu'il consiste pour calculer les intersections, à créer (18) une première liste de sommets pour chaque polygone caché courant et visible courant en balayant chaque sommet d'une liste dans le sens contraire au balayage des sommets de l'autre liste, jusqu'à ce qu'un point commun aux deux listes soit trouvé, en réinitialisant les balayages des deux listes à partir de chaque nouveau point trouvé. 3. Procédé selon l'une quelconque des revendications 1 et 2 caractérisé en ce qu'il consiste à effectuer des tests (17) pour vérifier l'existence de trous ou d'occlusions totales lorsqu'aucune intersection est trouvée.