Brevet FR2740888A1 — publié le 19970509

La présente invention se rapporte à un procédé de génération dynamique d'images synthétiques à niveau de détail automatique, ainsi qu'à un dispositif de mise en oeuvre de ce procédé. Les machines de synthèse d'images temps réel utilisées dans les simulateurs de vol sont capables de générer des images d'une qualité proche de la réalité grâce en particulier à l'utilisation massive de textures photographiques. Mais le nombre maximal de polygones pouvant être affichés à chaque cycle image demeure leur principale limitation. Malheureusement, on s'aperçoit que ce nombre est très mal exploité dans certaines situations. En effet, quelle que soit la distance de visibilité de l'observateur, la même attention est portée aux facettes lointaines qu'aux facettes proches. Pourtant, lors du calcul, la pertinence dans l'image des facettes éloignées est très faible par rapport à celles se trouvant à proximité de l'observateur. Certaines tentatives ont été menées dans le passé pour simplifier le paysage à longue distance. Mais celles-ci se sont révélées peu efficaces et trop contraignantes au niveau de la génération des bases de données. La visualisation de terrains réels en images de synthèse est possible grâce à l'existence de relevés altimétriques issus d'observations radars ou satellites. Ces données altimétriques se présentent en général sous la forme d'une grille bidimensionnelle donnant l'altitude en chaque point. Le modèle de terrain (algorithmes et structures de données) qui gère ces données altimétriques doit prendre en considération les trois exigences suivantes qui sont essentielles, en particulier pour des simulateurs de pilotage d'avions: - Fidélité: Les aspects caractéristiques du relief (pics, vallées) sont des repères visuels très importants pour les pilotes et influent sur la qualité de leur entraînement et de leurs décisions au cours d'une mission. Le respect des lignes de crête est donc une condition essentielle pour tout modèle cartographique. - Economie d'informations. A précision égale, le nombre de polygones représentant un terrain donné influe directement sur les temps de réponse du simulateur temps réel (rendu, collision, roulement, intervisibilité...). La rugosité d'un terrain n'étant pas régulière, le maillage doit s'adapter au relief, lâche dans les zones de pente constante, fin dans les parties accidentées. - Rapidité de génération Les bases de données de simulation pouvant couvrir des milliers de Km2, leur coût de génération est directement lié à l'utilisation d'algorithmes performants permettant d'intégrer les différentes sources de données (planimétrie, altimétrie, photométrie) en un temps minimum. Les bases de données de simulateurs d'avions étant en général très vastes, le nombre de facettes représentant le terrain est considérable. Or le visuel ne sait afficher en temps réel que quelques milliers de facettes. Afin d'éliminer très rapidement celles qui ne sont pas dans le champ de vision, on effectue une pré-troncature région. Lors de la modélisation de la base de données, le terrain est partitionné en zones rectangulaires appelées régions. De simples calculs d'intersection pyramide-boîte permettent de sélectionner les régions visibles et d'éliminer ainsi un très grand nombre de facettes. Cette découpe est également très utile si la base de données ne peut être chargée d'un bloc en mémoire. II suffit alors de ne charger que les régions comprises dans la sphère centrée sur l'observateur et de rayon égal à la distance de visibilité. Cette base de données locale est mise à jour au fur et à mesure que l'observateur se déplace : les régions qui sortent de la sphère sont déchargées et remplacées par celles qui y rentrent. Ainsi, seul l'espace mémoire limite la taille des bases de données. Pour de faibles distances de visibilité ( Le seul recours dont on dispose aujourd'hui est de simplifier les zones de la base de données où l'affichage "coince" Cette solution est coûteuse et peu pratique. De plus, pour des distances de visibilité importantes, le relief est beaucoup trop simplifié. Seuls des algorithmes sophistiqués de niveau de détail peuvent diminuer drastiquement le nombre de facettes affichées sans dégrader la qualité de l'image. Ces algorithmes sont nés du constat suivant : la pertinence d'un polygone du terrain, c'est à dire le nombre de pixels qu'il occupe à l'écran, est d'autant plus faible que ce polygone est loin. Si on ne fait rien, une partie de la puissance graphique de la machine est gaspillée à clipper, projeter, texturer... des polygones qui, en fin de compte, n'occupent qu'un ou deux pixels à l'écran. Toute la difficulté consiste donc à simplifier un terrain vu par un observateur mobile sans nuire à la pertinence de l'image. Devant la complexité mathématique et algorithmique, aucun constructeur de simulateurs n'a intégré un tel dispositif de manière vraiment efficace. Une première approche consiste à précalculer différents niveaux de détail pour chaque région et à commuter en temps réel d'un niveau à l'autre. Malheureusement cette méthode comporte beaucoup d'inconvénients: - Dépendance vis à vis des régions: Les régions jouant ici le rôle de frontières entre niveaux de détail, la qualité de la commutation dépend de leurs tailles. - Encombrement mémoire: L'encombrement mémoire limite le nombre de niveaux de détail par région et pénalise le chargement dynamique de la base de données. De plus, ce nombre varie en fonction du relief de chaque région. - Commutation trop brutale: Plus le nombre de niveaux de détail d'une région est faible, plus la commutation est brutale. Ces artefacts d'image sont très gênants pour le pilote. Pour remédier à ces problèmes, des modèles de terrain hiérarchiques ont été envisagés. Une hiérarchie de niveaux de détail au sein d'une même structure de données (quad-tree, Delaunay-pyramid) ne mémorise que les changements pour passer d'un niveau de détail à l'autre, d'où une économie de mémoire importante. L'arborescence est parcourue afin de sélectionner les triangles à afficher en fonction de la précision requise. Trois inconvénients majeurs subsistent - Niveau de détail global La construction des niveaux de détail successifs est uniquement basée sur un critère de précision indépendamment de la position d'un observateur. L'ordre d'apparition des points est figé alors que la pertinence des points varie justement en fonction de la position de l'observateur. - Modifications du terrain impossibles: Ces structures de données hiérarchiques sont rigides et n'autorisent aucune modification du terrain en temps réel. II serait nécessaire de reconstruire toute l'arborescence, ce qui est trop coûteux. - Coût additionnel de génération de la base de données. La génération de la base de données reste quelque chose de très coûteux. Les contraintes liées au temps réel compliquent la modélisation de la scène. La présente invention a pour objet un procédé de génération dynamique d'images synthétiques permettant de générer en temps réel des images synthétiques avec le maximum possible de fidélité et le meilleur rendu possible, sans nécessiter de moyens de calcul importants, en tenant compte de la pertinence des points des différents niveaux de détail en fonction de la position de l'observateur, ce procédé permettant également des modifications de la configuration du terrain en temps réel. La présente invention a également pour objet un générateur dynamique d'images synthétiques comportant des moyens qui soient le meilleur marché possible, de préférence des moyens tels que des calculateurs et des moyens de mémorisation de bases de données qui soient simples et couramment disponibles. Le procédé conforme à l'invention consiste à constituer une base de données en partant d'un fichier contenant les données topographiques relatives aux terrains à visualiser, à éliminer les données les moins significatives, puis à calculer en temps réel les points à afficher en fonction du niveau de détail requis, qui est lui-même fonction de la position de l'observateur, de l'altitude maximale du terrain à visualiser, de ia distance de visibilité et du niveau de détail requis, en sélectionnant un sous-ensemble des points de la base de données définissant une portion de terrain dont le niveau de détail a changé, en effectuant un maillage irrégulier de la portion de terrain sélectionnée, de préférence un maillage de type Delaunay, et à appliquer une texture sur les polygones résultant du maillage. Selon un aspect du procédé de l'invention, on ajuste localement la précision de la représentation du terrain par ajout ou suppression de points dans le maillage, la sélection de ces points étant faite en fonction du relief, de la position de l'observateur et du type de véhicule sur lequel se trouve l'observateur. La présente invention sera mieux comprise à la lecture de la description détaillée d'un exemple de mise en oeuvre, illustré par le dessin annexé, sur lequel - la figure 1 est un exemple de triangulation contrainte de Delaunay, pouvant être mise en oeuvre par la présente invention, - la figure 2 est un diagramme montrant l'évolution de l'erreur de triangulation d'une surface en fonction du nombre de points choisis pour la représenter, - la figure 3 est un schéma explicatif montrant l'effet de l'insertion d'un point significatif sur l'erreur de triangulation, - la figure 4 est un schéma simplifié de l'architecture logicielle d'un processeur graphique mettant en oeuvre le procédé de l'invention, et - la figure 5 est une vue explicative simplifiée en perspective définissant le critère d'erreur angulaire utilisé par la présente invention. La présente invention, pour réaliser un modèle de terrain, met en oeuvre une technique de maillage basée sur la triangulation de Delaunay, et plus précisément la triangulation contrainte de Delaunay, schématiquement illustrée en figure 1. Les points P définissant les noeuds du maillage peuvent être arbitrairement distribués dans le plan de la région 1 traitée. Cette région 1 est une des zones du terrain. Dans l'exemple de la figure 1, cette zone est simplement un rectangle. Cette technique de maillage présente de nombreux avantages. En premier lieu, la simplicité des objets traités (triangles) permet de les traiter en temps réel. Ceci est dû en particulier au fait que la majorité des algorithmes de visualisation et de manipulation géométrique sont simplifiés et accélérés grâce à l'utilisation exclusive de triangles. De plus, pour un ensemble de points donné (points d'un relevé altimétrique), la triangulation de Delaunay correspondante est unique, ce qui permet de traiter ces points dans n'importe quel ordre. La propriété remarquable de la triangulation de Delaunay est de générer des triangles qui sont le plus équilatéraux possible. Cette propriété est très avantageuse en synthèse d'images pour laquelle elle diminue les problèmes d'aliassage et de précision numérique. La triangulation de Delaunay permet de rajouter ou de supprimer un point d'un ensemble déjà triangulé sans avoir à recalculer tous les points, du fait de l'influence uniquement locale d'un tel point. Une telle manipulation interactive favorise également la modification en temps réel d'un terrain visualisé. La triangulation de Delaunay contrainte garantit l'existence de certaines arêtes dans le maillage, ce qui permet de respecter la géométrie des objets intégrés dans le terrain (routes, lignes de chemin de fer, constructions, ...). Outre la triangulation, la présente invention met en oeuvre le filtrage des surfaces de terrain visualisées. Ce filtrage permet d'éliminer les points les moins significatifs de cette surface, ce qui permet de simplifier le traitement de la zone géographique à visualiser. La triangulation effectuée ensuite sur les points restants de cette surface correspond au niveau de détail le plus fin de la base de données qui fournit ces points. Le filtrage consiste à affiner par un processus itératif la triangulation du terrain. Pour chaque point P, on calcule la distance entre ce point et le point Q qui est le projeté de P sur la triangulation courante. Cette distance correspond, localement, à l'erreur existant entre la surface du terrain approximé (résultant de la triangulation courante) et la surface du terrain réel. Après avoir calculé ainsi les erreurs relatives aux différents points, on sélectionne le point d'erreur maximale, et on l'insère dans la triangulation courante. On répète cette étape jusqu'à ce que l'erreur maximale des points de la zone considérée soit inférieure à un seuil que l'on se fixe en fonction du réalisme désiré de l'affichage et compte tenu de la puissance de calcul nécessaire pour franchir ce seuil pour divers types de terrains. La courbe de la figure 2 montre l'évolution de l'erreur (correspondant à la distance PQ telle que définie ci-dessus) en fonction du nombre de points définissant une zone donnée. La terrain n'étant pas, en général, une surface convexe, I'insertion d'un point dans la triangulation courante peut avoir pour effet d'augmenter l'erreur au lieu de la diminuer. Ainsi, par exemple comme représenté en figure 3A, on suppose que le long d'une section de terrain accidenté on dispose au départ de quatre points P1, P2, P3 et P4. L'approximation initiale est le segment P1 P2. Le point qui est ensuite inséré est celui dont la distance au segment P1 P2 est la plus grande. Supposons qu'il s'agisse de P3. On constate alors que la nouvelle erreur de P4 (distance de P4 au segment P3-P2) peut être supérieure à la distance D' entre P3 et son projeté Q3 sur le segment P1-P2. En général, on constate qu'après plusieurs insertions consécutives, L'erreur finit par descendre au-dessous de la valeur (D' dans l'exemple de la figure 3A) qu'elle avait lors de l'insertion du premier point (P3 pour l'exemple considéré). Dans la pratique, on répète cette étape d'insertion jusqu'à ce que l'erreur maximale devienne inférieure à un seuil que l'on se fixe. Dans le diagramme de la figure 2, on a supprimé les pics temporaires dus à l'insertion de points (tels que P4) correspondant à des reliefs présentant une courbure inverse de la courbure courante.Ainsi, on constate d'après cette figure 2 une diminution quasi exponentielle de l'erreur maximale dès que le nombre de points définissant une zone donnée (de dimensions de l'ordre de 100 km2) dépasse le millier. II est donc facile, pour un type de relief donné (peu accidenté, moyennement montagneux, très montagneux...) d'effectuer des essais pour obtenir une courbe telle que celle de la figure 2, et d'optimiser le rapport entre l'exactitude de la représentation du terrain et le nombre de points nécessaires à une représentation fidèle du terrain, sans surcharger inutilement le processeur de calcul graphique ou "moteur graphique" (au-delà d'un certain nombre de points, le gain en précision devient dérisoire au vu de l'augmentation du nombre de calculs). A partir des principes ci-dessus, I'invention consiste à modifier en temps réel la base de données de manière à n'envoyer au moteur graphique que les polygones caractéristiques du point de vue de l'observateur. La précision du terrain est ajustée localement par ajout et suppression de points dans le maillage courant. La sélection des points à insérer et à supprimer tient compte du relief (en particulier pour bien respecter les lignes de crête, qui sont un élément important du paysage pour un pilote d'hélicoptère ou d'avion), de la position de l'observateur et du type de mobile (char, avion, hélicoptère...). Le schéma de la figure 4 représente de façon simplifiée les deux couches logicielles principales 2, 3 du moteur graphique mettant en oeuvre le procédé de l'invention. La couche 2 est celle qui est chargée de la triangulation de Delaunay, effectuée en mode asynchrone. Elle effectue, entre autres, la régulation de charge du processeur (optimisation du traitement des paquets de données transitant en mode asynchrone), le calcul du niveau de détail et la régénération de la base de données (après modification locale de la description du terrain) au format du processeur hôte. La couche 3 est la tâche graphique proprement dite, qui rafraîchit l'écran à une cadence de, par exemple, 30 Hz. Cette tâche effectue essentiellement la prétroncature des régions (pour n'avoir à afficher que les régions visibles par l'utilisateur), I'affichage, et la transition entre deux niveaux de détail. La coopération entre les deux couches logicielles 2 et 3 se passe de la façon suivante. On suppose que le système graphique affiche des scènes que doit voir un observateur se trouvant dans un simulateur de véhicule mobile à un instant donné. La tâche graphique 3 envoie à intervalles de temps réguliers (par exemple à la cadence de 30 Hz, comme précisé ci-dessus), les polygones maillés en Delaunay à afficher (en fonction du déplacement dudit véhicule). Ces polygones correspondent au niveau de détail courant qui est affiché. De manière asynchrone, la tâche Delaunay 2 recalcule le niveau de détail approprié, afin de tenir compte du changement de position de l'observateur par rapport à la région affichée. Les points alors devenus pertinents (visibles par l'observateur et nécessaires à la définition réaliste du paysage, c'est-à-dire pas trop éloignés de l'observateur) sont insérés dans le maillage Delaunay. Les points devenus inutiles sont supprimés. Le procédé de sélection de ces points est expliqué plus en détail ci-dessous. Dès que le nouveau maillage est calculé, il se substitue à l'ancien par basculement (marqué "flip-flop" en figure 4). A chaque requête de changement de niveau de détail transmise par la couche 3, le processeur graphique recalcule la pertinence des points issus de la base de données. Dans le cas d'un observateur pouvant se retourner très rapidement (pilote d'hélicoptère ou de char), toutes les régions de terrain de la base de données locale sont traitées. Dans le cas contraire (pilote d'avion civil, ...), seules les régions relatives au cap du véhicule sont recalculées. On peut ainsi diminuer le nombre de régions à traiter Soit Easeuiî l'erreur angulaire maximale autorisée. L'erreur angulaire est définie ci-dessous en référence à la figure 4. Sa valeur maximale est fixée par l'utilisateur.La sélection des points à supprimer se fait par exemple selon le programme suivant: FAIRE POUR chaque point inséré soit Eh l'erreur en altitude commise si on enlève ce point calculer Ea l'erreur angulaire vue depuis l'observateur FIN POUR Trier les points par Ea croissant Soit P le point d'erreur minimale Supprimer P si Eap Recalculer l'erreur E des points orbites de P TANT QUE Eap La sélection des points à insérer se fait selon le programme suivant FAIRE POUR chaque point non inséré calculer Eh l'erreur en altitude calculer Ea l'erreur angulaire vue depuis l'observateur FIN POUR Trier les points par Ea décroissant Soit P le point d'erreur maximale Supprimer P si Eap > Easeuiî Recalculer l'erreur en altitude des points orbites de P TANT QUE Eap > Easeuil. L'erreur angulaire mentionnée ci-dessus est déterminée de la façon suivante (voir figure 4). L'erreur en altitude d'un point Pn est la distance Dn entre ce point Pn et son projeté Qn sur la triangulation courante Tc ne contenant pas ce point. Ce critère géométrique permet de mesurer l'influence de ce point sur l'exactitude de la représentation du terrain. En théorie, cette erreur est déterminée en supprimant ce point de la triangulation le contenant, puis en calculant l'erreur commise du fait de cette suppression, et enfin en réinsérant ce point dans la triangulation. En pratique, afin de limiter le nombre de calculs, on calcule cette erreur en projetant le point Pn dans le plan moyen Pm obtenu à partir des points orbites (points les plus proches de Pn). Le projeté de Pn dans le plan Pm est Qm. Cette erreur en altitude ne tient pas compte de la position relative de l'observateur.Par contre, L'erreur angulaire Ea en tient compte. Pour un observateur dont les yeux sont en un point 0 (étant donnée la distance relativement importante entre l'observateur et le terrain, on peut assimiler les yeux de l'observateur à un point), L'erreur angulaire Ea est l'angle formé par les segments Pn, OQn. La tâche graphique 3 commande la commutation du niveau de détail, c'est-à-dire la commutation entre une scène antérieure à une opération d'insertion/suppression de points due à un changement de position de l'observateur, et une scène juste postérieure à cette opération. Lorsqu'un point devenu pertinent est inséré on qu'un point devenu non pertinent est supprimé, la tâche graphique l'élève (ou l'abaisse) progressivement (sur plusieurs cycles d'image) depuis l'altitude du triangle sur lequel il se projette jusqu'à son altitude propre. Ce déplacement est recalculé à chaque cycle image. La vitesse d'élévation de ce point dépend de plusieurs facteurs, en particulier d'au moins l'un des facteurs suivants - de sa visibilité par l'observateur. Ainsi, un point qui ne se trouve pas dans le champ visuel instantané de l'observateur ou qui est masqué provisoirement par un obstacle est élevé immédiatement. - de la vitesse de déplacement de l'observateur. Ainsi, lorsqu'il est immobile, I'élévation des points est gelée. - de la distance du point à l'observateur. A altitude égale, plus le point est éloigné de l'observateur, plus il monte vite. Grâce à ces caractéristiques du procédé de l'invention, on obtient une commutation rapide des niveaux de détail consécutifs avec la meilleure fluidité possible de transition entre images. Les autres avantages du procédé de l'invention sont - une réduction du volume de la base de données sans perte de qualité d'image. Le système de visualisation est capable de calculer une image de rendu égal à celui obtenu par les procédés de l'art antérieur avec beaucoup moins de polygones: en moyenne, on peut éliminer 2/3 des facettes sans dégrader l'image. - automatisation de la gestion de charge du processeur graphique. II adapte la base de données aux performances du matériel par simple réglage d'un paramètre (Erreur angulaire de seuil). II permet donc d'obtenir le meilleur réalisme possible pour l'affichage des scènes compte tenu des possibilités du système graphique et de visualisation. - II simplifie la génération de la base de données: le pré-calcul des niveaux de détail devient inutile (le niveau de détail approprié est généré directement par la couche 2 de triangulation), ce qui diminue corrélativement le prix de revient des moyens de production de la base de données. - II permet la modification en temps réel de la représentation du terrain, en particulier afin de pouvoir l'adapter à des scénarios de simulation exigeants, ou à des besoins nouveaux, telle la simulation distribuée interactive. REVENDICATIONS 1. - Procédé de génération dynamique d'images synthétiques à niveau de détail automatique, selon lequel on constitue une base de données en partant d'un fichier contenant les données topographiques relatives aux terrains à visualiser, et on élimine les données les moins significatives, caractérisé en ce qu'on calcule en temps réel les points à afficher en fonction du niveau de détail requis, qui est lui-même fonction de la position de l'observateur, des lignes de crête du terrain à visualiser, de la distance de visibilité et du niveau de détail requis, que i'on sélectionne un sous-ensemble des points de la base de données définissant une portion de terrain dont le niveau de détail a changé, que l'on effectue un maillage irrégulier de la portion de terrain sélectionnée, et que l'on applique une texture sur les polygones résultant du maillage. 2. - Procédé selon la revendication 1, caractérisé en ce que le maillage est du type Delaunay. 3. - Procédé selon l'une des revendications 1 ou 2, caractérisé en ce que le niveau de détail requis est déterminé en fonction de l'erreur angulaire maximale admise (Ea) telle que vue par l'observateur. 4.- Procédé selon l'une des revendications précédentes, caractérisé en ce que la transition entre niveaux de détail successifs s'effectue au rythme du rafraîchissement de l'écran d'affichage des images synthétiques. 5. - Procédé selon la revendication 4, caractérisé en ce que la vitesse d'élévation ou d'abaissement d'un point inséré ou supprimé est variable. 6. - Procédé selon la revendication 5, caractérisé en ce que ladite vitesse est fonction de sa visibilité par l'observateur et/ou de la vitesse de déplacement de l'observateur et/ou de la distance du point à l'observateur. 7. - Procédé selon l'une des revendications 4 à 6, caractérisé en ce que la transition entre niveaux de détail successifs se fait par basculement.