FR2999005A1 - Procede de rendu d'un terrain stocke dans une base de donnees massive - Google Patents

Abstract

Procédé de rendu d'un terrain stocké dans une base de données massive ledit rendu de terrain étant affiché pour un observateur par un dispositif d'affichage comportant au moins une carte graphique comportant une mémoire cache, caractérisé en ce qu'il comporte au moins les étapes suivantes : • une étape de génération (81) de plusieurs grilles régulières de pavés de terrain de niveau de résolution différents (LODO, LOD1, LOD2) pour représenter les données de terrain de la base de données massive ; • une étape d'extraction (82) de données de terrain de la base de données massive pour plusieurs niveaux de résolution, les données de terrain extraites formant une pyramide d'extraction, composée d'une fenêtre d'extraction pour chaque niveau de détail, mise en mémoire cache. Chaque fenêtre comporte une zone active destinée à être affichée, et une zone de pré-chargement qui permet d'anticiper les transferts de données ; • une étape de sélection (83) des pavés de la pyramide d'extraction qui contribuent à l'image. • une étape de tracé (122) du rendu à partir des pavés sélectionnés.

Description

PROCEDE DE RENDU D'UN TERRAIN STOCKE DANS UNE BASE DE DONNEES MASSIVE La présente invention concerne un procédé de rendu d'un terrain stocké une base de données massive. L'invention est notamment applicable à la génération d'images de synthèse par un logiciel de simulation dans le cadre d'un entrainement d'un pilote à une conduite d'engin.

La génération d'images de synthèse représentant un milieu extérieur peut s'appliquer à de nombreux contextes : par exemple, pour l'entrainement de pilotes d'engins utilisant un simulateur de l'engin et de son environnement évoluant en temps réel. L'entrainement peut s'appliquer à des pilotes d'hélicoptère, mais aussi à des pilotes d'engins terrestres. La génération d'images de synthèse peut aussi s'appliquer à des jeux informatiques afin de simuler un environnement extérieur. La plupart des systèmes de simulation utilisant la génération d'images de synthèse comportent une base de données dans laquelle l'ensemble des données décrivant un terrain d'évolution est stocké. Pour l'exploitation de ces données de terrain et leur affichage, par exemple sur un écran faisant face au pilote à entrainer, les systèmes de simulation comportent une carte graphique comportant notamment des processeurs dédiés au calcul des données à afficher, et une mémoire vidéo qui peut être utilisée par le système de simulation comme un cache de niveau 1. De même, la mémoire principale de la carte mère peut être utilisée par ces systèmes comme un cache de niveau 2. Dans la suite, on parlera indifféremment de cache ou de mémoire cache. Les données de terrain sont généralement décrites d'une part avec des informations de type géométrique, qui comportent notamment des sommets définis par des attributs tels que position et vecteur normal, et des informations de type image, qui permettent de plaquer une texture sur la représentation géométrique, par exemple une photo aérienne. Ces données sont donc exploitées par la carte graphique, qui gère l'affichage des données de terrain sous la forme d'images. Les images peuvent par exemple être affichées sur un écran. Les calculs pour la représentation des données de terrain effectués par le processeur graphique utilisent notamment un procédé de rendu de terrain.

Un des problèmes lié au rendu de terrain en milieu extérieur est que l'environnement extérieur est décrit au moyen de données de terrain de taille importante. En effet, un milieu extérieur n'est pas toujours borné par un 5 mur par exemple mais peu s'étendre jusqu'à un horizon. Les données de terrain sont notamment stockées de façon persistante dans une base de données dite massive de part sa taille importante en terme de volume de données stockées. L'exploitation de bases de données massives est très complexe et coûteuse en temps de calcul et en mémoire cache pour les 10 processeurs de traitement de ces données. Notamment il est impossible de travailler sur des bases de données massives avec des outils de gestion et d'accès aux bases de données classiques. Les outils de gestion d'accès sont notamment des logiciels gérant des accès aux bases de données. 15 Compte tenu des limites actuelles des ordinateurs, autant en termes de capacité mémoire qu'en termes de traitement de données géométriques pour un affichage, une tendance usuelle est d'avoir recours à des techniques dites de niveaux de détail lorsque l'on souhaite maintenir un taux de rafraichissement de l'image, temps réel, stable. 20 Les techniques de niveaux de détail consistent à simplifier la représentation des éléments de la scène, en fonction de leur contribution à l'image rendue. Cette contribution peut être estimée à partir de différents critères, tels que la distance entre l'élément à afficher et le point de vue de l'observateur, ou encore une évaluation de la surface projetée de l'élément à 25 afficher dans l'image rendue. Plus la distance de l'élément à afficher à l'observateur est élevée, ou plus la surface projetée de l'élément à afficher dans l'image rendue est petite, plus on pourra se permettre de dégrader la précision de la représentation de cet élément. Pour rendre un terrain en utilisant des techniques de niveaux de 30 détail, on peut s'appuyer sur deux familles de technique: les techniques dites à niveaux de détails discrets, et celles dites à niveaux de détails continus. Les techniques de niveaux de détails discrets consistent à pré-calculer plusieurs représentations plus ou moins détaillées d'un même élément de la scène. Lors de l'affichage on sélectionne, parmi les représentations pré- 35 calculées, celle qui permet de réaliser le meilleur compromis entre le coût de traitement, et la richesse de l'affichage. Ces techniques sont particulièrement adaptées au traitement d'objets répétés dans la scène, tels que les arbres. Les techniques de niveaux de détails continus se basent sur un maillage d'un élément de la scène, dont les mailles sont localement simplifiées selon un 5 critère permettant d'estimer l'erreur introduite par la simplification des mailles dans l'image rendue. Pour limiter le coût de traitement de la simplification du maillage, ces techniques reposent sur une organisation beaucoup plus restrictive des données de l'élément représenté, et ne s'appliquent généralement qu'à un sous-ensemble des éléments de la base de données, 10 en particulier la surface du sol. Pour le traitement des données de type image, des techniques spécifiques de niveaux de détail sont utilisées, dont la plus largement répandue est le mipmapping. Le mipmapping est une technique d'application de textures, les mipmaps, qui permet d'améliorer la qualité de l'affichage en 15 réduisant par filtrage d'éventuels artefacts d'aliasing, c'est-à-dire de crénelage, tout en limitant le coût du filtrage pour permettre un rendu temps réel. Le préfixe mip vient de l'expression latine « multum in parvo », qui signifie littéralement « beaucoup de choses dans un petit endroit ». Le suffixe map provient du terme anglais, qui peut être traduit dans ce contexte par 20 image. Une mipmap est basée sur une collection d'images pré-calculées, qui accompagne une texture principale. Chaque image pré-calculée est obtenue par filtrage de la texture initiale, et peut être assimilée à un niveau de détail de la texture initiale. Par exemple, à partir d'une image d'une taille de 256x256 pixels, seront produites les mêmes images aux résolutions de 25 128x128 pixels, 64x64, 32x32, 16x16, 8x8, 4x4, 2x2 et 1x1. Lors de l'affichage d'un objet texturé par une mipmap, l'opération de filtrage consiste à échantillonner la texture en utilisant les images dont la résolution est la plus proche de celle qui correspond à la projection sur l'écran de la surface texturée de l'objet. Par rapport à la texture originale, l'utilisation de mipmaps 30 introduit un surcoût mémoire de l'ordre de trente pour cent. Différentes techniques de niveaux de détail sont décrites dans les publications suivantes : - Enrico Gobetti, Fabio Marton, Paolo Cignoni, Marco Di Benedetto, Fabio Ganovelli. C-bdam - compressed batched dynamic adaptive meshes for terrain rendering. Computer Graphics Forum, 25(3), sept 2006; - Christopher C. Tanner, Christopher J. Migdal, Michael T. Jones. The clipmap: a virtual mipmap. SIGGRAPH' 98, Proceedings of the 25th annual conference on Computer Graphics and intereactive techniques, pp 151-158, NY, USA, 1998. ACM Press ; - Frank Lossasso, Hugues Hoppe. Geometry clipmaps: terrain rendering using nested regular grids. SIGGRAPH' 2004, volume 23(3), pp 769-776, NY, USA, 2004. ACM Press; la - Peter Lindstrom, Valerio Pascucci. Terrain Simplification simplified: A general framework for view-dependent out-of-core visualization. IEEE Transactions on Visualization and Computer Graphics, 8(3), pp 239254, 2002; - Roland Wahl, Manuel Massing, Patrick Degener, Michael Guthe, 15 Reinhard Klein. Scalable compression and rendering of textured terrain data. Journal of WSCG, volume 12, 2004. Gobetti et al., Tanner et al., Lassosso et al., Lindstrom et al. utilisent des techniques de niveaux de détail pour un affichage de terrain de grande dimension et s'attachent à adapter localement la complexité des 20 éléments affichés pour un point d'intérêt, en fonction de la contribution de chaque élément à l'image rendue pour ce point d'intérêt. Plus précisément, Enrico Gobetti et al. décrivent une représentation de terrain multi-résolutions, compressée pour supporter un rendu interactif sur un plan très large, de surfaces de terrain sphériques. La 25 technique décrite est nommée C-BDAM pour Compressed Batched Dynamic Adaptive Meshes, signifiant maillage adaptatif dynamiquement compressé par lot. La technique C-B DAM est une extension des techniques BDAM et PBDAM, BDAM étant un acronyme pour l'expression anglo-saxonne Batched Dynamic Adaptive Meshes et P-BDAM étant un acronyme pour l'expression 30 anglo-saxonne Planet-Sized Batched Dynamic Adaptive Meshes. La technique C-BDAM utilise notamment une hiérarchie dans les niveaux de détail du découpage du terrain. Tanner et al., quant à eux, décrivent une méthode dite de « clipmap », qui consiste en une technique de représentation d'une texture 35 dynamique, pour réaliser un rendu de terrains de grande dimension en temps réel. Clipmap est une expression anglo-saxonne qui peut être traduite par image découpée. Une méthode de clipmap est par définition une méthode de « clipping » d'une mipmap, visant à limiter l'emprunte mémoire des données de texture. Clipping est une expression anglo-saxonne signifiant littéralement découpe. L'approche de Tanner et al. consiste à découper chaque niveau de détail de la mipmap en tuiles, afin de pouvoir gérer des textures de très grande taille, pouvant par exemple atteindre plusieurs centaines de milliers de pixels de côté, grâce à un procédé de gestion de cache. Lors de l'affichage, seule une petite portion de la texture complète est chargée en mémoire: pour chaque niveau de détail de la texture, on gère un cache qui contient les tuiles correspondant aux données images qui ont le plus de chances d'être utilisées pour le rendu. Ce cache est mis à jour dynamiquement, et de manière incrémentale, en fonction des déplacements du point de vue.

Frank Lossasso et al. étendent la technique de « clipmap » à la gestion des données décrivant la géométrie du terrain. Cette dernière doit pouvoir être représentée sous la forme d'une grille régulière, dont chaque cellule représente un point du terrain. Les deux première coordonnées d'un point sont déduites implicitement des indices de ligne et de colonne dans la grille, alors que la troisième coordonnée, qui correspond à l'altitude, est donnée par la valeur de la cellule associée. Les données géométriques sont alors gérées en mémoire comme une texture de clipmap, formant un jeu de grilles régulières imbriquées, centrées sur le point de vue. Lossasso et al. décrivent particulièrement un procédé qui assure une continuité géométrique entre les différents niveaux de détail utilisés pour l'affichage d'un point de vue. Peter Lindstrom et al. décrivent un cadre d'application général pour un calcul de rendu d'un terrain, stocké sur une mémoire externe, afin de générer des représentations de surfaces de terrain massives. Les deux principes clefs du cadre d'application proposé sont les suivants : un raffinement du maillage du terrain dépendant de la position de l'observateur, et un schéma simple d'organisation des données de terrain, pour améliorer la cohérence et réduire le nombre d'événements de pagination entre un stockage externe du terrain et la mémoire principale d'un calculateur.

Comme de nombreuses méthodes précédemment proposées pour le raffinement d'un maillage du terrain dépendant du point de vue, Lindstrom et al. utilisent une subdivision récursive d'un maillage triangulaire pour définir un maillage régulier de données de terrain. Pour chaque rendu, l'algorithme se décompose en trois étapes principales: une génération d'un maillage adaptatif représentant le terrain, une élimination des triangles n'étant pas dans le volume de visibilité, et une gestion des transitions de niveaux de détail du maillage adaptatif en utilisant le géo-morphing. Roland Wahl et al. partent du principe que, pour des bases de données de terrain massives, l'utilisation de tuiles pré-calculées est plus 10 efficace que les méthodes en niveaux de détails continus, et consiste à résoudre les problèmes suivants: d'une part le partitionnement et la simplification des données originelles, et d'autre part la mise en oeuvre d'un algorithme de rendu permettant d'obtenir une bonne précision, les approches courantes se résumant souvent à établir un compromis entre l'erreur 15 d'approximation dans l'espace image et le taux de rafraîchissement du rendu. Pour résoudre ces problèmes, Roland Wahl et al. proposent une structure de données et une technique de niveaux de détails particulières. Leur approche permet un rendu en temps réel de jeux de données stockés de manière externe, tout en garantissant une précision de un pixel dans 20 l'espace image entre les géométries et les textures affichées, et celles des données d'origine. Ainsi, de nombreuses méthodes existent pour obtenir un rendu de terrain efficace à partir de données de description de terrain stockées sur une mémoire externe. Cependant, le recours à ces techniques spécifiques 25 complique à la fois la production de données et le développement du logiciel de rendu. En particulier, ces techniques induisent des restrictions sur la représentation géométrique des données, qui les rendent non applicables aux zones urbanisées du terrain, comprenant notamment des bâtiments. Ces zones sont alors des cas particuliers qu'il convient de gérer de façon 30 spécifique. De plus il est alors nécessaire de gérer la continuité entre les zones non urbanisées et les autres zones, ce qui complexifie encore le logiciel. Plus précisément, la plupart des solutions actuelles utilisant les 35 techniques de niveau de détail pour afficher le terrain font l'hypothèse que, en tout point de la surface de terrain, celui-ci est défini par une et une seule altitude. Il en résulte que ces techniques de niveau de détail ne permettent de gérer qu'une partie des données de description du terrain à l'exclusion notamment des faces verticales. Ainsi, les solutions actuelles de niveaux de détail de terrain ne permettent pas de gérer des éléments tels que des bâtiments ou même de simples murets. De fait, ceci interdit de s'appuyer sur les mêmes mécanismes de gestion des données de représentation du terrain pour la gestion des zones naturelles et pour la gestion des zones urbaines par exemple. Ceci pose les problèmes suivants : la production des données de terrain et le développement du logiciel exploitant ces données de terrain est particulièrement complexe. En effet plusieurs modes de production de données et d'affichage doivent être gérés selon le type de données. Egalement, un problème de continuité se pose systématiquement à la frontière entre les zones terrain en relief gérées par ces techniques et les zones gérées par d'autres techniques, qui en général, sont des techniques de niveaux de détails discrets. D'autre part, ces techniques s'appuient le plus souvent sur une représentation du terrain sous la forme de grilles régulières, qui sont peu efficaces en termes de compacité des données. Ceci est particulièrement vérifiable pour suivre de manière fine dans le relief du terrain des éléments distinctifs qui ne suivent pas les axes de la grille régulière tels que des réseaux hydraulique ou des réseaux routiers. Lorsque le point de vue se déplace, le degré de raffinement des données affichées peut évoluer localement, par exemple en enrichissant la représentation des données qui se trouvent rapprochées du point de vue, et en dégradant la représentation des données qui s'en trouvent éloignées. Pour éviter des changements brusques de l'image rendue, on a alors recours à des techniques spécifiques pour gérer ces transitions. L'une des techniques les plus utilisées dans ce cadre est le géo-morphing. Un principe du géo-morphing est que lorsque de nouveaux sommets sont introduits dans un maillage pour affiner la représentation d'une zone existante, les nouveaux sommets sont déplacés progressivement de manière à ce que la surface résultante soit une représentation intermédiaire entre la résolution de départ et la résolution à atteindre. Un inconvénient du géo-morphing est qu'il nécessite une gestion dynamique des représentations intermédiaires. Dans le cas où la partie visible du maillage du relief est entièrement transférée sur la carte graphique à chaque cycle de rafraichissement de l'image, l'essentiel du coût introduit par le géo-morphing est lié aux transferts entre l'unité principale de traitement et la carte graphique. Dans le cas contraire, le géo- morphing nécessite un traitement spécifique par la carte graphique, au niveau de l'étape de traitement des sommets du maillage. Là encore, en plus d'un impact négatif sur les performances de calcul du rendu par la carte graphique, l'impact sur la complexité du développement du logiciel de rendu peut poser un problème.

En ce qui concerne la mise à jour des données à charger en mémoire (principale et graphique), pour permettre l'affichage de la scène depuis le point de vue courant, et notamment les considérations sur la bande passante nécessaire à cette mise à jour, ces considérations ne sont que très rarement abordées par les publications relatives à ce domaine. En effet, les différents travaux réalisés privilégient les aspects algorithmiques. Si les problèmes liés à la bande passante sont évoqués dans les travaux sur le clipmapping, ces derniers ne proposent pas de stratégie concrète pour prévoir et répartir efficacement les mises à jour au cours du temps, par exemple en fonction du déplacement du centre d'intérêt. Un autre problème des techniques actuelles est lié à la stratégie choisie pour le rafraichissement de l'image rendue, et notamment à la technique de transition entre les niveaux de détail. En effet certaines solutions impliquent un rechargement sur la carte graphique d'un maillage complet ou partiel du terrain à afficher, et ce, à chaque cycle de traçage. Dans ce cas, le transfert des données géométriques sur la carte graphique représente une partie non négligeable du coût en temps de calcul du tracé final.

Les solutions actuelles ne traitent donc à chaque fois qu'un des aspects du problème général d'affichage de données de terrain massives en temps réel, avec un risque important de perturbation de l'image. Ceci nuit considérablement au réalisme des scènes représentant le milieu d'évolution de l'entrainement.

Un but de l'invention est notamment de pallier les inconvénients précités. A cet effet, l'invention a pour objet un procédé de rendu d'un terrain stocké dans une base de données massive ledit rendu de terrain étant 5 affiché pour un observateur par un dispositif d'affichage comportant au moins une carte graphique comportant une mémoire cache, ledit procédé comportant au moins les étapes suivantes : - une étape de génération (81) de plusieurs grilles régulières (1, 2, 3) de pavés de terrain de niveau de résolution différents (LODO, LODI, 10 LOD2) pour représenter les données de terrain de la base de données massive ; - une étape d'extraction (82, 120) de données de terrain de la base de données massive pour plusieurs niveaux de résolution, les données de terrain extraites formant une pyramide d'extraction composée 15 d'une fenêtre d'extraction pour chaque niveau de détail, mise en mémoire cache,; - une étape de sélection (83, 9, 121) des pavés de la pyramide d'extraction qui contribuent à l'image. - une étape de tracé (122) du rendu à partir des pavés sélectionnés. 20 Dans un mode de mise en oeuvre particulier, les données de terrain sont extraites pour plusieurs niveaux de résolution pour composer une pyramide d'extraction, ladite pyramide d'extraction étant constituée d'une fenêtre glissante d'extraction pour chaque niveau de résolution, ladite fenêtre 25 glissante d'extraction étant définie par un nombre de pavés de terrain fixé identique pour tous les niveaux de résolution, lesdits pavés s'étendant autour d'une position dite position du centre de la fenêtre glissante d'extraction, ledit centre de la fenêtre glissante d'extraction évoluant en temps réel en fonction de l'évolution de la position d'un centre d'intérêt, le centre d'intérêt étant 30 déterminé en fonction de la position de l'observateur par rapport au dispositif d'affichage. Une fenêtre glissante est par exemple mise en mémoire cache, comporte une zone active destinée à être affichée, et une zone de pré-chargement qui permet d'anticiper les transferts de données.

La largeur d'une fenêtre glissante d'extraction est par exemple définie par un nombre pair de pavés de terrain. Une pyramide d'extraction comportant pour chaque niveau de résolution différent une fenêtre glissante d'extraction constituée d'une grille de pavés, le pas de déplacement du centre d'une fenêtre glissante d'extraction de niveau de résolution L, est par exemple aligné sur le pas d'une grille de niveau de résolution L+1, L étant un entier, le niveau de résolution L+1 étant moins détaillé que le niveau de résolution L. Les grilles de résolution différentes de la fenêtre glissante forment par 10 exemple un arbre quaternaire, chaque niveau de l'arbre correspondant à un niveau de résolution. Le rendu de chaque pavé de la fenêtre glissante est par exemple déterminé en parcourant en profondeur l'arbre quaternaire du niveau le moins résolu au niveau le plus résolu. 15 Chaque pavé P de niveau L en intersection avec le champ de vision, et situé dans la marge de transition du niveau de résolution L-1, est par exemple tracé en mélangeant le pavé P à ses enfants dans l'arbre quaternaire. L'invention a notamment pour principaux avantages de rendre une 20 scène comportant un terrain très étendu, stocké sur des bases de données visuelles complexes avec un niveau de détail le plus riche possible en fonction de l'application du rendu d'images. Notamment, le contenu de l'image dans un rayon proche de l'observateur est enrichi, afin de pouvoir distinguer des détails sur les éléments proches de l'observateur. 25 D'autres caractéristiques et avantages de l'invention apparaîtront dans la description qui suit, donnée à titre illustratif et non limitatif, et faite en regard des dessins annexés qui représentent : - la figure 1 : un exemple de subdivision d'une base de 30 données en pavés pour plusieurs niveaux de détails ; - la figure 2: une pyramide d'extraction de données de terrain pour différents niveaux de détail ; - la figure 3: une fenêtre glissante selon l'invention ; - la figure 4a: une première position d'un centre d'intérêt ; 35 - la figure 4b: une deuxième position du centre d'intérêt ; - la figure 5: un déplacement de deux fenêtres glissantes d'extraction selon l'invention ; - la figure 6: une matérialisation des frontières de transition pour trois niveaux de détails consécutifs, correspondant à des déplacements d'un centre d'intérêt selon une direction ; - la figure 7: une matérialisation des frontières de transition dans un espace en deux dimensions, pour trois niveaux de détail consécutifs ; - la figure 8: un organigramme qui décompose en trois tâches les activités mises en oeuvre dans le procédé ; - la figure 9: un organigramme de sélection des pavés contribuant au rendu de l'image finale. - la figure 10: un exemple de calcul d'un coefficient de mélange des pavés pour le rendu dans une marge de transition d'une fenêtre glissante d'extraction ; - la figure 11: différents états possible pour une cellule d'une fenêtre glissante selon l'invention ; - la figure 12: un exemple de gestion d'une mémoire cache selon l'invention.

La figure 1 représente un exemple de subdivision d'une base de données en pavés pour plusieurs niveaux de détails LODO, LODI , LOD2. LOD est un acronyme pour l'expression anglaise Level Of Details signifiant 25 niveaux de détail. Le procédé selon l'invention prend en entrée une description de données de terrain stockées dans une base de données massive. Les données de terrain peuvent notamment être décrites dans la base de données au moyen d'un ou plusieurs maillages irréguliers. Ces maillages 30 peuvent par exemple décrire le relief du terrain, ainsi que des éléments présents sur le terrain tels que des arbres, des bâtiments, des éléments de voirie, etc. Une première étape du procédé selon l'invention est une étape de pavage de la base de données en tuiles pour plusieurs niveaux de résolution différente. Par exemple le pavage peut être analogue aux pavages utilisés 35 dans le clipmapping. Le pavage de la base de données peut produire par exemple une première grille 1 de décomposition d'un terrain, pour un premier niveau de détail LODO. La première grille 1 peut être une grille carrée comportant huit lignes et huit colonnes telles que représenté sur la figure 1 pour l'exemple. Chaque pavé de cette grille contient la description des données de la portion de terrain correspondante, par exemple sous la forme de maillages triangulaires irréguliers. Une deuxième grille 2 représente le même terrain que la première grille1, pour un niveau de détail LODI inférieur au niveau de détail LODO. Par exemple, cette deuxième grille 2 peut comporter quatre lignes et quatre colonnes. Le contenu de chaque pavé de la grille 2 est constitué de données représentant le terrain de façon plus grossière qu'au niveau LODO. Par exemple, les maillages contenus dans chaque pavé de la grille peuvent correspondre à des version simplifiées des maillages représentant le terrain original. Une troisième grille 3 représentant le même terrain peut comporter deux lignes et deux colonnes. La troisième grille 3 a un niveau de détail LOD2, inférieur au niveau de détail LODI, et au niveau de détail LODO. Le niveau de détail LOD2 est le niveau de détail le plus grossier dans l'exemple. Pour plus de clarté, la figure 1 présente des grilles comportant relativement peu de cellules. En pratique, on pourra par exemple subdiviser la base de données en vue d'obtenir des pavés dont la taille de côté est de l'ordre du kilomètre au niveau le plus résolu. Le nombre de cellules de la grille dépendra alors de l'étendue totale de la base de données, qui peut dépasser plusieurs milliers de kilomètres. La génération de grilles de différents niveaux de résolution s'effectue en amont du procédé selon l'invention afin de ne pas intégrer de processus de simplification de données terrain dans un procédé d'affichage du terrain. Ainsi, il est également avantageux de ne pas imposer de contrainte sur la représentation des données d'entrée du procédé selon l'invention. En particulier, des zones urbaines peuvent être intégrées aisément dans les données prise en compte par le procédé selon l'invention.

Avantageusement, l'utilisation de maillages triangulaires quelconques pour les pavés de la base de données massive permet une grande souplesse dans la production des bases de données de terrain massive. Par exemple, à partir d'un niveau de détail spécifié par configuration, il est possible d'exclure du contenu des pavés les maillages correspondants à certains types de bâtiments,.

Une première étape du procédé de rendu selon l'invention, peut être une étape de prétraitement des données de la base de données de terrain. Au cours de cette première étape de prétraitement, plusieurs représentations de la base de données de terrain peuvent être générées, chacune pour un niveau de détail différent. Différentes résolutions de données sont notamment représentées sur la figure 1. La première étape du procédé de rendu peut être réalisée une seule fois pour différentes itérations du calcul de rendu. Dans la suite de la description, par convention, les niveaux de détails LOD sont numérotés par résolution décroissante. Autrement dit, le niveau LODO correspond au niveau de détail le plus précis, le niveau LODI correspond à un niveau de détail plus grossier que le niveau de détail LODO, et ainsi de suite. Pour chaque niveau de détail, les données de terrain peuvent être subdivisées selon une grille régulière de pavés ou de tuiles. Par exemple, le pas de la grille peut être doublé entre une grille d'un niveau de détail L, L étant un entier, et un niveau de détail L-1 moins résolu. Ainsi, le pavage de la base de données peut être organisé de façon à ce que chaque pavé d'une grille de niveau de détail L, soit une version simplifiée d'une union de quatre pavés adjacents de la grille de niveau L-1. Ainsi, chaque pavé d'un niveau L-1 peut être associé au noeud racine d'un arbre quaternaire, ou quadtree du niveau L. Pour chaque pavé associé à un noeud du quadtree, quatre enfants peuvent représenter chacun un quart du pavé parent, avec une résolution supérieure à celle du pavé parent.

La figure 2 représente un exemple d'une pyramide d'extraction 20 de données de terrain pour plusieurs niveaux de détails différents LODO, LODI , LOD2. En utilisant un découpage en niveau de détails analogue à celui représenté sur la figure 1, un mécanisme d'extraction de données de terrain de la base de données massive, peut être mis en place. Une distance d'extraction peut varier en fonction du niveau de détail. Une distance d'extraction représente une étendue des données de terrain extraites pour un niveau de détail défini, c'est à dire par exemple chargées depuis un dispositif de stockage externe de la base de donnée vers les mémoires principale et graphique du système de simulation, afin de pouvoir être exploitées en temps réel pour l'affichage. Par exemple, sur la figure 2, une base 21 de la pyramide d'extraction 20 représente une extraction de terrain pour un niveau de détail LOD2. Par exemple, tel que représenté sur la figure 2, la taille des données de terrain extraite pour le niveau de détail LOD2 est un carré de huit lignes par huit colonnes. Ce carré correspond à un sous-ensemble de la matrice formée par le pavage de l'intégralité de la base de données pour ce niveau de détail. Un niveau intermédiaire 22 de la pyramide d'extraction 20 correspond aux données de terrain extraites pour un niveau de détail LODI. Sur la figure 2, le niveau intermédiaire 22 comporte des données de terrain reparties sur un carré comportant huit lignes et huit colonnes. Ensuite, un niveau supérieur 23 de la pyramide d'extraction 20 correspond à des données de terrain extraites pour un niveau de détail LODO. La correspondance géographique entre les extractions des différents niveaux est matérialisée en traits gras par la projection de chaque extraction sur celle du niveau suivant.

Le procédé d'extraction peut être basé sur la stratégie suivante : pour chaque niveau de détail LODn, une fenêtre glissante de pavés, centrée sur un point d'extraction est mise à jour avec une partie des pavés de la base de données pour le niveau de détail LODn. La fenêtre glissante associée à un niveau de détail est représentée sur la figure 3. La pyramide d'extraction 20 représentée figure 2 est ainsi constituée de l'ensemble des fenêtres glissantes 23, 22 et 21, associées respectivement aux niveaux LODO, LODI et LOD2. La largeur des fenêtres glissantes 21, 22, 23, c'est-à-dire le nombre de pavés définissant leur taille, est la même pour tous les niveaux de détail LODO, LODI, LOD2. Sur la figure 2, le nombre de pavé est de huit pour l'exemple. Comme un pavé d'un maillage de niveau L+1 est deux fois plus grand qu'un pavé d'un maillage de niveau L, la distance d'extraction entre deux niveaux de détails consécutifs est donc doublée dans cet exemple. La fenêtre glissante d'extraction est nommée dans la suite clipwindow, expression anglo-saxonne signifiant littéralement fenêtre de coupe.

La figure 3 représente une clipwindow 30 selon l'invention. Une clipwindow 30 est associée à chaque niveau de détail L, et comprend un sous-ensemble des pavés définis pour ce niveau dans la base de données de terrain. Une clipwindow 30 selon l'invention comporte trois zones distinctes 31, 32, 33 centrées sur un point 34 nommé le clipcenter 34.

Clipcenter est une expression anglo-saxonne que l'on peut traduire par centre de coupe. La clipwindow 30 comporte donc : une zone centrale 31, une zone ou marge de transition 32, une zone ou marge de préchargement 33.

La zone centrale 31 et la zone de transition 32 forment une zone nommée zone active de la clipwindow 30. La zone active 31, 32 est affichée pour le rendu de terrain selon l'invention. La marge de préchargement 33 n'est pas affichée : elle est utilisée pour mettre en mémoire cache, de manière prédictive, des pavés de la clipwindow 30 ayant une chance d'entrer dans la zone active 31, 32 à court terme. Pour faciliter la gestion des problèmes de continuité entre les clipwindows de deux niveaux de détail différents, le pas de la grille correspondant au niveau L+1 peut être aligné sur le pas de la grille correspondant au niveau L. Ainsi, la gestion de la discontinuité entre les clipwindow 30 revient avantageusement à garantir la continuité à la frontière entre un pavé de niveau L et ses voisins directs dans le niveau L-1. Pour assurer cet alignement, la largeur de la clipwindow comporte un nombre pair de pavés. Le clipcenter 34 peut être défini par des coordonnées entières en deux dimensions, qui correspondent aux indices d'un pavé dans la matrice formée par la grille régulière de pavage de la base de données terrain pour le niveau de détail associé. Le pavé en question peut par exemple être celui dont le coin inférieur gauche correspond au centre de la clipwindow 30. Pour respecter les contraintes d'alignement, les coordonnées du clipcenter 34 sont donc des nombres pairs dans l'exemple présenté.

Les figures 4a et 4b illustrent l'alignement d'une clipwindow 40, associée à un niveau de détail L, sur la grille de pavage 41 définie dans la base de donnée pour le niveau de détail L+1. En particulier, elles montrent l'incidence des déplacements du centre d'intérêt 42 sur les indices du clipcenter, matérialisés par la croix en pointillés blancs 44. Sur l'exemple, le niveau de détail L est matérialisé par LO, et les indices des pavés de la grille pour ce niveau sont reportés sur les axes "LO col" et "LO row". Les indices paires du pavage 41 sont matérialisés par un quadrillage noir épais. Ce dernier coïncide avec la grille formée par le pavage du niveau de détail L+1.

Sur la figure 4a, la zone 43 dans laquelle le centre d'intérêt peut évoluer, sans que cela se traduise par un changement des indices de clipcenter, est matérialisée par des pointillés noirs épais. Sur la figure 4a, la position de clipcenter 44 peut être définie par les indices du pavé dont le coin inférieur gauche est au centre de la clipwindow : [8; 8]. Ces indices sont les indices pairs pour lesquels la position 44 du clipcenter est la plus proche du centre d'intérêt 42. La position du centre d'intérêt 42 peut par exemple être liée à la position d'un observateur dans la scène. La position du centre d'intérêt 42 peut être asservie au déplacement de l'observateur, ou au déplacement de son regard sur l'image par exemple. o Sur la figure 4b, suite à un déplacement du centre d'intérêt, les nouveaux indices du clipcenter 44 sont [10, 10], c'est-à-dire les indices pairs du pavé dont le coin inférieur gauche est le plus proche du centre d'intérêt 42. Par suite, sur la figure 4b, la clipwindow 40 se décale pour rester centrée sur son clipcenter 44. La nouvelle zone 43 dans laquelle le centre d'intérêt 15 peut évoluer sans entraîner de déplacement la clipwindow 40 est à nouveau matérialisée. La figure 5 représente des déplacements de deux clipwindows 50, 52 de deux niveaux de détails successifs, respectivement L et L+1. Les 20 centres respectifs de ces deux clipwindows sont représentés respectivement par les points 51 et 53. Le déplacement des clipwindows 50, 51 fait suite à un déplacement du centre d'intérêt, par exemple selon un premier axe 500, sensiblement parallèle à l'un des deux axes de pavage de la base de données terrain dans l'exemple. Au cours d'une première étape 0, les 25 premier et deuxième clipcenter 51, 53, respectivement des première et deuxième clipwindows 50, 52 sont à une même position. Au cours d'une deuxième étape 1, le premier clipcenter 51 se déplace selon le premier axe 500, et la première clipwindow 50 avec lui, pour suivre un déplacement du centre d'intérêt. Les premier et deuxième clipcenter 51, 53 ne sont alors plus 30 confondus. Au cours d'une troisième étape 2, le deuxième clipcenter 53 et la deuxième clipwindow 52 se déplacent selon le premier axe 500. Le déplacement réalisé au cours de la troisième étape 2 est un déplacement sur une distance deux fois plus grande que le mouvement de la première étape 1, en effet, il existe entre les deux pas de grille des deux clipwindow 50, 52, 35 un facteur multiplicatif de deux dans cet exemple. Après le déplacement de la troisième étape 2, le deuxième clipcenter 53 se trouve placé au dessus du premier clipcenter 51. A l'issue de la troisième étape 2, la distance entre le premier et le deuxième clipcenter 51, 53 est la même qu'à l'issue de la deuxième étape 1. Au cours d'une quatrième étape 3, la deuxième clipwindow 52 se déplace encore selon le premier axe 500, vers le haut, de manière à ce que le premier clipcenter 51 soit à la même position que le deuxième clipcenter 53. De manière générale, un calcul de la position d'un clipcenter, par arrondi de la position du centre d'intérêt sur la grille de niveau supérieur tel que représenté sur les figues 4a, 4b, définit de manière unique les transitions d'une clipwindow : c'est-à-dire les frontières qui, lorsque le centre d'intérêt les traverse, donnent lieu à un déplacement du clipcenter, et par suite de la clipwindow. On peut nommer ces dernières par frontières de transition. Ainsi à chaque fois que le centre d'intérêt franchit l'une des frontières de transition, le clipcenter se déplace avec sa clipwindow. De nouveaux pavés entrent alors dans la zone de pré-chargement de la clipwindow. Ces nouveaux pavés sont extraits de la base de données, et transférés vers la mémoire cache allouée pour la clipwindow. De même des pavés sortent de la zone de pré-chargement, ils sont alors libérés de la mémoire cache.

La figure 6 illustre les relations entre les frontières de transition correspondant aux clipwindows de trois niveaux de détails consécutifs LODO, LODI , LOD2 en fonction de déplacements du centre d'intérêt. Pour l'exemple le centre d'intérêt se déplace parallèlement à un des axes des grilles de subdivision en niveaux de détails de la base de données de terrain. Dans l'exemple représenté sur la figure 6, le niveau de détail le plus résolu est le niveau LODO alors que le niveau le moins résolu est le niveau LOD2. Sur la figure 6, le déplacement du centre d'intérêt s'effectue selon un premier axe 60. Les déplacements des clipcenters des clipwindows relatives à chaque niveau de détail se font de manière parallèle au déplacement du centre d'intérêt, avec un pas de progression proportionnel au pas de chaque grille de niveau de détail. Les déplacements des clipcenters pour chaque niveau de détail LODO, LODI , LOD2 sont représentés respectivement par des flèches horizontales 61, 62, 63. Les traits verticaux sur la figure 6 représentent les frontières de transition 64, 65, 66 respectivement pour chaque niveau de détail LODO, LODI, LOD2, le long du déplacement du centre d'intérêt. Les frontières de transition du niveau de détail LODO coïncident avec les centres des pavés du niveau de détail moins résolu suivant, c'est-à-dire dans l'exemple représenté le niveau de détail LODI. De ce fait, dans l'exemple représenté sur la figure 6, des premières frontières de transition 64 correspondant au niveau de détail LODO sont deux fois moins espacées que des deuxièmes frontières de transitions 65 du niveau de détail moins résolu LODI. De même, les deuxièmes frontières de LODI sont deux fois moins espacées que des troisièmes frontières de transitions 66 du niveau de détail le moins résolu LOD2. Dans ces conditions, lorsque le centre d'intérêt se déplace parallèlement à un axe de subdivision des données de terrain, on peut démontrer qu'une distance minimale entre deux frontières de transition d'un niveau est égale à la taille d'un pavé du niveau le plus résolu.

La figure 7 représente de manière plus générale des frontières de transition dans un espace en deux dimensions 64, pour trois niveaux de détail consécutifs LODO, LODI, LOD2. La figure 7 représente donc une généralisation de la représentation des frontières de transition, telles que représentées sur la figure 6, à des déplacements quelconques du point d'intérêt dans l'espace à deux dimensions 64, dans lequel la base de données terrain a été subdivisée en grilles. La figure 7 représente notamment une superposition des trois grilles LODO, LODI, LOD2. Le déplacement du centre d'intérêt est représenté par des flèches dans la subdivision de l'espace composée des pavages relatifs aux trois niveaux de détail distincts. Les déplacements du centre d'intérêt sont tels que le centre d'intérêt traverse au plus deux frontières de transition simultanément : une frontière de transition horizontale et une frontière transition verticale. Une intersection entre une frontière horizontale et une frontière verticale est nommée point de transition. A partir d'un point de transition, le chemin le plus court pour que le centre d'intérêt parvienne à une autre transition correspond à un déplacement du centre d'intérêt selon l'un des axes de subdivision de la base de données. Avantageusement, il est donc possible de se ramener à une transition en une dimension telle que représentée sur la figure 6. Par la même, si on alloue des ressources suffisantes en terme de bande passante pour pouvoir mettre à jour deux clipwindows en relation avec un même point de transition, en un temps inférieur à celui que met le centre d'intérêt pour parcourir une distance égale à la taille d'un coté de pavé du niveau de détail le plus résolu, dans notre cas LODO, alors on peut garantir que l'on sera 5 toujours en mesure de maintenir la pyramide d'extraction à jour lors des déplacements du centre d'intérêt. Par exemple, si on dispose en entrée d'une borne supérieure sur la vitesse de déplacement du centre d'intérêt, on peut en déduire une borne supérieure de la bande passante requise pour maintenir l'ensemble des clipwindows à jour quels que soient les 10 déplacements de l'observateur. On note w la largeur d'une clipwindow, et b la largeur de la marge de pré-chargement, en nombre de pavés. Lors du passage d'une transition verticale ou horizontale, le nombre de pavés à extraire pour mettre à jour la clipwindow est bxw. . Pour un point de transition situé à une 15 intersection de deux frontières de transition, impliquant deux clipwindows de niveaux de détails différents, le nombre de pavés à recharger est 2xbxw. Soit K le coût de transfert maximal pour un pavé depuis la base de données, la bande passante peut être dimensionnée de façon à permettre le transfert d'une quantité de données égale à 2xbxwxK. Ces données 20 doivent pouvoir être transférées dans une durée inférieure ou égale au temps mis par le centre d'intérêt pour parcourir une distance égale à la taille d d'un côté d'un pavé de niveau de détail le plus résolu, par exemple LODO dans l'exemple représenté sur la figure 7. Une vitesse nommée V. est une vitesse maximale de déplacement du centre d'intérêt. La durée du 25 déplacement peut donc s'exprimer par la formule suivante : d IV.. En faisant le rapport de la quantité de données à transférer pour une telle transition, par le temps minimal dont on dispose pour le transfert, on peut donc exprimer la bande passante BW requise ainsi : BW(V.)= 2xbxwxK V x(1000). d 30 Avantageusement, l'utilisation de l'équation (1000) permet d'obtenir un comportement du chargement des données de la base de données prédictif et ainsi d'utiliser la bande passante disponible d'une manière la plus efficace. Ainsi, l'utilisation d'un cache prédictif comportant les pavés des 35 zones de pré-chargement des clipwindows permet de dimensionner simplement le matériel utilisé pour répondre à des besoins spécifiques d'un cas d'utilisation du procédé de rendu selon l'invention. Réciproquement, l'utilisation du cache prédictif permet d'adapter une production de données pour satisfaire des contraintes en termes de bande passante relatives à un matériel donné pour la mise en oeuvre du procédé selon l'invention. La figure 8 représente un organigramme qui décompose en trois tâches les activités mises en oeuvre dans le procédé. Les données source 80 de description du terrain constituent les données d'entrée du procédé. Ces données sont par exemple constituées de données images, de données géométriques décrivant la surface du terrain, ou encore d'objets types tridimensionnels, modélisés par des outils externes, et positionnés dans la base de données. Les données de description géométrique peuvent notamment être des maillages triangulaires irréguliers quelconques. Une étape préalable au calcul de rendu est une génération 81 de plusieurs représentations de la base de données pour des niveaux de détails différents. Cette génération consiste notamment à organiser les données source pour chaque niveau de détail, en les répartissant dans une grille, pour former un pavage tel que décrit figure 1. La génération peut être réalisée une seule fois pour plusieurs itérations du calcul de rendu. Par exemple, le résultat de la génération peut être calculé pour l'ensemble du terrain, puis stocké sur un système de stockage persistent, pour être accédé directement par le composant en charge du rendu. Une alternative consiste à mettre en place un serveur produisant à la demande les pavés de terrain à partir des données source. A l'exécution du système, lorsque le point d'intérêt traverse une frontière de transition tel que décrit ci-avant, le système effectue au cours d'une deuxième étape 82 une extraction de pavés, à partir de la base de données, pour plusieurs niveaux de détails différents. Les pavés extraits forment une pyramide d'extraction. La pyramide d'extraction est composée d'une fenêtre glissante d'extraction ou clipwindow pour chaque niveau de détails, chaque fenêtre glissante comportant le même nombre de pavés. Cette activité a pour résultat la mise à jour d'un cache de données, qui permet de transférer de façon prédictive les données potentiellement nécessaires à l'affichage.

Une troisième étape 83 consiste à sélectionner, parmi les pavés présents en mémoire cache, ceux qui vont contribuer au rendu de l'image. Cette sélection consiste notamment à déterminer les pavés visibles depuis le point de vue courant, et à sélectionner le bon niveau de détail, de façon à afficher le contenu le plus adapté au point de vue. Un algorithme de sélection selon l'invention est décrit dans l'organigramme de la figure 9. La figure 9 représente un organigramme de sélection des pavés contribuant au rendu de l'image finale. On considère en premier lieu les pavés de la clipwindows correspondant au niveau de détail le moins résolu.

Pour chacun de ces pavés, les traitements décrit ci-après sont réalisés. Dans la suite, le pavé courant est noté P, la clipwindow courante est notée W, et le niveau de détail courant est noté L. Donc pour chaque pavé P, son intersection avec le champ de vision V correspondant à la position actuelle de l'observateur, est calculée au cours d'une étape 91. Le calcul peut se faire de façon conservative, en considérant l'intersection d'un volume englobant le pavé avec les différents plans du champ de vision. Si l'intersection de P avec le champ de vision est nulle, le pavé courant P est exclu de la sélection pour l'image en cours, et l'étape 90 passe au pavé suivant. Sinon, l'algorithme passe à l'étape 92, et vérifie si il existe un niveau de détail plus résolu. Si le niveau de détail courant L est le niveau le plus élevé, le pavé en cours de traitement P est directement ajouté à l'ensemble des pavés à tracer. Sinon, on considère la position relative de P par rapport à la clipwindow W-1 de niveau L-1. La comparaison est une troisième étape 94 du procédé selon l'invention, telle que représenté sur la figure 10. Lorsque P est dans la partie centrale de W-1, le procédé selon l'invention effectue alors une itération sur chacun des enfants de P dans la pyramide d'extraction, en mettant en oeuvre sur chacun des enfants l'étape 30 91 et les suivantes. Lorsque P est à l'extérieur de W-1, alors le pavé P est directement sélectionné pour le rendu au cours de l'étape 96. Lorsque P est dans la marge de transition de W-1, le tracé de P pour le rendu est réalisé au cours des étapes 95 à 99. Le tracé de P est 35 réalisé dans ce cas en mélangeant par transparence le pavé P avec les pavés enfants du pavé P qui ont une intersection non nulle avec le champ de vision, la transparence étant fonction d'un coefficient de mélange. Le mélange s'effectue tel que représenté sur la figure 10.

La figure 10 représente un clipwindow 100 ainsi que son clipcenter, représenté par une croix, et un centre d'intérêt représenté par un point, ledit centre d'intérêt se déplaçant par rapport au clipcenter. La zone de transition de la clipcenter est divisée en plusieurs sous-zones dénommées par une cardinalité : NW pour Nord-Ouest, N pour Nord, NE pour Nord-Est, E pour Est, SE pour Sud-Est, S pour Sud, SW pour Sud-Ouest, et W pour Ouest. Pour chacune des huit sous-zones, un coefficient de mélange est calculé en fonction notamment de la position du centre d'intérêt. Sur une première représentation 101 de la clipwindow 100, le centre d'intérêt et le clipCenter sont confondus, le coefficient de mélange est 15 alors égal à 1, tous les pavés de zone de transition sont donc représentés sans transparence. Sur une deuxième représentation 102 de la clipwindow 100, le centre d'intérêt s'est déplacé vers l'est par rapport au clipCenter. Un premier coefficient de transparence est donc appliqué aux sous-zones NW, W et SW. 20 Si les pavés de ces sous-zones sont sélectionnés pour le rendu, le coefficient de transparence calculé sera utilisé pour les mélanger avec les pavés parents correspondants dans le niveau de détail suivant. Tous les pavés des autres sous-zones de la zone de transition se voient affecter un coefficient de 1, ce qui signifie qu'ils seront représentés sans transparence 25 s'ils sont sélectionnés pour le rendu. Sur une troisième représentation 103 de la clipwindow 100, le centre d'intérêt s'est décalé vers le nord par rapport à sa position dans la représentation 102. Le premier coefficient est toujours appliqué aux pavés des sous-zones NW, et W, et un deuxième coefficient de transparence est 30 appliqué aux pavés des sous-zones S et SE. Les pavés de la sous-zone SW se voient affecter la valeur minimale de ces deux coefficients. Les autres sous-zones se voient à nouveau affecter un coefficient de 1. Sur une quatrième représentation 104 de la clipwindow 100, le centre d'intérêt s'est à nouveau déplacé vers le nord par rapport à la 35 représentation 103. Le coefficient de transparence calculé pour les sous- zones S et SE devient alors inférieur à celui calculé pour les sous-zones W et NW. Il en résulte que la sous-zone SW se voit affecter la valeur de coefficient de la sous-zone S, et non plus celle de la sous-zone W. Le coefficient de mélange peut se calculer de la manière 5 suivante : soit focusPo int une position du centre d'intérêt, définie par ses coordonnées dans les deux dimensions principales de la base de données. Selon la convention choisie pour le pavage de la base de données, il peut s'agir par exemple d'un couple x, y dans un plan choisi pour la subdivision, ou encore d'un couple (latitude, longitude). Pour un niveau de détail, des 10 coordonnées entières klipCenter] du clipcenter correspondant à la position du centre d'intérêt peuvent être données par l'équation suivante : 0 5 [clipCenter] = 2[-1[focusPo int] + [ (1001). 2d 0,5 Dans l'équation 1001, d représente la taille de côté d'un pavé pour le niveau de détail considéré. Les symboles L J correspondent à l'opérateur "partie 15 entière". Ces coordonnées correspondent donc aux indices pairs d'un pavé dans la matrice formée par le pavage du niveau de détail considéré. Le pavé en question est le pavé d'indices pairs dont le coin inférieur gauche est le plus proche du centre d'intérêt. L'erreur d'arrondi, qui matérialise la différence entre la position du centre 20 d'intérêt et celle de clipCenter, peut être calculée de la façon suivante: [rndErrxi rndErr = = d IclipCenter]-[focusPo int] (1002). rndErr Y A partir de l'erreur d'arrondie, on peut déterminer un coefficient de mélange blend pour chaque niveau de détail et pour chaque zone de la marge de transition : blend 1 - rndErrx 1 1 1 1 24 blendw = si rndErrx > +blendTreshold blend s = sin on blend N = si rndErr < -blendTreshold sin on si rndErr y > +blendTreshold sin on si rndErr, < -blendTreshold sin on 1- blendTreshold 1 + rndErrx 1- blendTreshold { 1- rndErr 1- blendTreshold 1 + rndErryx 1- blendTreshold blend sw = min(blend w;blend s) blend sE = min(blend s;blend E) blend NE = min(blend E;blend N) blend Nw = min(blend N;blendw) (1003) Dans la formule 1003, blendThreshold est une valeur seuil, qui fixe dans chaque direction (W-E et S-N) la valeur de l'erreur à partir de laquelle on commence à mélanger les pavés de la zone de transition avec leurs parents de niveau de détail plus grossier. On peut déterminer cette valeur par la formule: userThreshold 1 blendTreshold(L)= max(userThreshold; [1 ) (1004) 21odsCnt-l-L dans laquelle lodsCnt est le nombre total de niveaux de détail générés pour la base de données, L est le niveau de détail considéré, et userThreshold est 10 une constante fixée par configuration à une valeur comprise entre zéro et un. Avantageusement, les transitions obtenues lors des changements de résolution consécutifs au déplacement du centre d'intérêt sont alors des transitions douces. Comme pour la stratégie de pré-chargement représentée sur les figures 4a, 4b, les transitions ne dépendent que de la position du 15 centre d'intérêt et possèdent les mêmes caractéristiques. La gestion de la transition progressive entre une image dans laquelle on affiche des pavés d'un premier niveau de détail, et une image dans laquelle on remplace ces pavés par leurs parents du niveau de détail plus grossier suivant, s'effectue par un jeu de transparence sur l'écran 20 d'affichage du terrain.

Avantageusement, les transitions sont appliquées à un nombre fini de pavés, ce qui permet de prédire le surcoût lié aux mélanges de pavés lors de ces phases transitoires. Ainsi, on évite les pics de temps de tracé liés à des transitions non maîtrisées, et il devient possible d'ajuster la richesse des niveaux de détail générés pour garantir un taux rafraîchissement constant de l'image. Avantageusement, le choix d'une transition par transparence image élimine les contraintes propres au géo-morphing et permet d'utiliser un maillage statique du terrain sur la carte graphique. Ainsi, le surcout dû à une utilisation de plusieurs niveaux de détails est limité. Seul le mélange des zones en cours de transition utilise du temps de calcul supplémentaire par rapport à un rendu classique. En dehors des zones en cours de transition, l'utilisation de la technique des niveaux de détail n'a pas d'impact sur les performances de l'affichage graphique.

La figure 11 représente différents états que peut prendre une cellule d'une fenêtre glissante. Comme décrit ci-avant, pour chaque pavé de la fenêtre glissante, le passage d'un niveau de résolution L à un niveau de résolution plus précis L-1 se fait en mélangeant le pavé avec ses quatre pavés enfants, c'est-à-dire avec les quatre pavés correspondant du niveau de détail L-1. Pour un bon fonctionnement du cache prédictif, les quatre pavés enfants se trouvent au même instant dans un même état. Les quatre pavés enfants forment donc un groupe cohérent que l'on peut désigner sous le terme de cellule. Une fenêtre glissante de chaque niveau de cache peut alors être décrite comme une matrice de cellules, dans laquelle chaque cellule regroupe quatre pavés. La cellule est caractérisée par les indices de son pavé inférieur gauche. Lesdits indices sont, dans cet exemple, pairs et peuvent être désignés par l'expression suivante : « position de référence de la cellule ». A partir du centre d'intérêt de la fenêtre glissante et de sa largeur, l'ensemble des positions de références valides pour toutes les cellules de la fenêtre glissante peut être calculé. Chaque position de référence valide peut être affectée à une et une seule entrée de la matrice de cellules en utilisant par exemple un opérateur modulo sur chacun des deux indices de la cellule. Ainsi, la estion du cache de cellules se ramène, pour chaque fenêtre glissante d'un niveau de détail, à mettre à jour le contenu des cellules en fonction de l'évolution de leur position de référence. Les différents états d'une cellule ainsi que les transitions entre ces différents états sont représentés sur la figure 11. Un premier état peut être l'état ATTENTE CHARGEMENT_MEM PRINCIPALE. Cet état signifie que la cellule est en état d'attente de chargement dans une mémoire principale du système de calcul de rendu. Le contenu de la cellule correspondant à la position de référence courante est donc en attente de son transfert depuis un dispositif de stockage secondaire, vers une mémoire principale du dispositif de calcul de rendu. Un dispositif de stockage secondaire peut être un disque dur, un stockage réseau. Le transfert de données d'une mémoire secondaire vers la mémoire principale est mise en oeuvre par une première fonction : Extraire_donnees_depuis_stockage_secondaire. Une cellule passe dans l'état ATTENTE CHARGEMENT_MEM PRINCIPALE lorsque sa position de référence courante est modifiée : dans ce cas, la position de la cellule devient obsolète. La position courante devenue obsolète est représentée sur la figure 9 par [position_obsolete]. Dans ce dernier cas, les données associées à la nouvelle position de la cellule sont extraites depuis le dispositif de stockage secondaire vers la mémoire principale. De plus, en fonction d'un état précédent de la cellule, le contenu correspondant à la précédente position de référence peut être déchargé de la mémoire principale et de la mémoire graphique. Si la position de référence est toujours valide, une fois les données extraites, la cellule passe à un deuxième état : ATTENTE CHARGEMENT MEM GRAPHIQUE. Sinon, la cellule reste dans l'état ATTENTE CHARGEMENT MEM PRINCIPALE de façon à pouvoir procéder ultérieurement à une extraction des données correspondant à une nouvelle position de référence. L'état ATTENTE CHARGEMENT MEM GRAPHIQUE signifie que la cellule est en attente d'être chargée dans une mémoire graphique du dispositif de rendu. Lorsque la cellule est dans le deuxième état ATTENTE CHARGEMENT MEM GRAPHIQUE, le contenu de la cellule correspondant à la position de référence courante est présent dans la mémoire principale ; il est en attente d'être transféré vers la mémoire graphique. L'action de transfert vers la mémoire graphique est représentée sur la figure 11 par la fonction Tranferer_donnees_vers_memoire_graphique. Une cellule passe dans le deuxième état lorsque les données associées à sa position de référence courante ont été extraites avec succès. Si la position de référence est toujours valide une fois les données transférées sur la mémoire graphique, la cellule passe à un troisième état : «A JOUR » signifiant que la position de référence courante à jour. Sinon lors du chargement d'une position de référence, la cellule repasse à l'état ATTENTE_CHARGEMENT_MEM_PRINCIPALE, et les données associées à la précédente position de référence sont libérées. La libération des données peut être réalisée par la fonction decharger_contenu_memoire_principale[position_ obsolete]. Lorsque la cellule est dans le troisième état AJOUR, le contenu correspondant à la position de référence courante est présent en mémoire principale et en mémoire graphique : tous les pavés de la cellule peuvent donc être tracés. Une cellule passe dans l'état AJOUR lorsque les données associées à sa position de référence courante ont été transférées avec succès sur la mémoire graphique. La cellule reste alors à l'état A_JOUR tant que la position de référence de la cellule reste inchangée. Lorsque la position de référence de la cellule change, alors la cellule repasse à l'état ATTENTE CHARGEMENT MEM PRINCIPALE, et les données associées à la précédente position devenue obsolète sont libérées de la mémoire principale et de la mémoire graphique par exemple par la fonction suivante : decharger_contenu_memoire_principale_et_graphique[postion_obsolete].

La figure 12 représente une gestion d'une mémoire cache de manière prédictive selon l'invention. Dans la suite la mémoire cache est appelée cache prédictif. Avantageusement, décomposer la gestion de la mémoire cache selon trois tâches distinctes tel que décrit ci-après permet de garantir un cycle de rafraichissement stable du dispositif d'affichage. En effet, une telle gestion de la mémoire cache permet de réduire l'impact du transfert de données, au cours d'un cycle de d'affichage, sur le taux de rafraichissement de l'image affichée lors du rendu. La décomposition en tâches de la gestion du cache prédictif se matérialise dans le système de rendu par l'implémentation de processus léger, couramment appelés des threads. La gestion du cache prédictif peut comporter trois tâches concernant : l'affichage du terrain, la sélection des cellules à afficher, l'extraction de données de terrain pour la mise à jour des cellules. Une première tâche peut être nommée AFFICHAGE. La tâche AFFICHAGE est une tâche centralisant les communications avec un pilote de la carte graphique. La tâche AFFICHAGE est principalement chargée de transmettre au pilote de la carte graphique des demandes de tracé des pavés de la base de données visibles en se référant au centre d'intérêt courant. La tâche AFFICHAGE est également responsable de transmettre des demandes de transferts de données sur la carte graphique. La tâche d'affichage est généralement cadencée par une synchronisation verticale du système d'affichage. Dans la plupart des cas, le cadencement est réalisé à une fréquence d'exécution de l'ordre de soixante hertz. Afin de limiter l'impact des transferts sur le temps de traitement d'un tracé par la carte graphique, un budget de transfert par cycle peut être affecté à la tâche AFFICHAGE. Les cellules en attente de chargement vers la mémoire graphique peuvent être insérées dans une file de rafraichissement. La file de rafraichissement est parcourue à chaque cycle de rafraichissement par la tâche d'affichage. Pour un cycle donné, le parcourt de la file de rafraichissement s'arrête lorsque le budget de transfert alloué à la tâche est consommé. Une deuxième tâche peut être une tâche de sélection, nommée SELECTION sur la figure 10. La tâche de sélection a pour objectif de prendre en compte des événements dits applicatifs tels que des déplacements de l'observateur. La tâche de sélection effectue également les mises à jour découlant du changement de statut des cellules dans le cache prédictif. Notamment, la tâche sélection réalise par exemple la fonction suivante : Mettre à jour le statut des cellules. Pour les cellules dont le contenu est devenu obsolète, des requêtes peuvent être transmises à une troisième tâche d'extraction. Par exemple : Mettre à jour le contenu des cellules. La tâche de sélection parcourt l'ensemble des cellules à jour et sélectionne dans chaque cellule parcourue les pavés à tracer, au niveau de détail approprié, tel que représenté sur la figure 9, en déroulant le procédé de rendu selon l'invention. Comme la tâche d'affichage, la tâche de sélection est cadencée sur la synchronisation verticale.

Une troisième tâche peut être une tâche d'extraction, nommée EXTRACTION sur la figure 10. La tâche d'extraction a notamment pour mission de mettre à jour le contenu des cellules dans la mémoire principale. Plus précisément, lorsque la position de référence d'une cellule a changé, la tâche d'extraction : - charge le contenu associé à la nouvelle position de référence ; - remplace le contenu correspondant à l'ancienne position de référence de la cellule, par celui correspondant à la nouvelle position de référence ; - décharge le contenu correspondant à l'ancienne position de référence. En centralisant les mises à jour de contenu des cellules dans un traitement asynchrone, la tâche d'extraction permet aux tâches synchrones de sélection et d'affichage de ne pas être bloquées par la mise à jour des cellules, et en particulier par les transferts de contenu depuis les dispositifs de stockage secondaires. Pour des raisons de performances sur les plateformes actuelles, les communications avec le pilote de la carte graphique étant centralisées par la tâche d'affichage, la tâche d'extraction communique avec la tâche d'affichage pour transférer/libérer le contenu des cellules sur la carte graphique. En fonction du nombre de processeurs disponibles sur l'unité centrale du système de rendu, la tâche d'extraction peut se matérialiser par plusieurs threads, chacun prenant simultanément en charge le traitement d'une partie des cellules en attente d'extraction. L'invention repose notamment sur deux principes : un principe de 25 gestion de la mémoire et un principe de représentation du terrain. Avantageusement, ces deux principes selon l'invention permettent de garantir une fluidité dans l'affichage des images successives tout en assurant des transitions douces, c'est-à-dire peu visible à l'ceil humain, entre les différents niveaux de détail représentés. Ainsi, lorsqu'une zone de terrain, 30 précédemment affichée avec un niveau de détail grossier passe à un affichage avec un niveau plus détaillé, la transition est peu visible pour un observateur de l'image. L'invention permet avantageusement d'accroitre les performances du système de rendu de terrain en optimisant les ressources de calcul 35 nécessaire au calcul de rendu, sans dégrader la qualité de l'image. En effet, l'invention permet simultanément : - d'augmenter significativement la distance de visibilité du terrain pour un observateur, ou de voir très loin ; - d'enrichir le contenu de l'image dans un rayon proche de l'observateur, par exemple pour distinguer des brins d'herbe, sans toutefois que cela soit perceptible à l'image. Le rafraichissement est avantageusement suffisamment réactif pour permettre à l'observateur de se déplacer à la vitesse qu'il souhaite dans la scène rendue, sans que le dispositif d'affichage ne manque de données pour afficher l'image à la résolution souhaitée.

Avantageusement, et à contre courant des solutions techniques actuelles, l'invention propose une approche s'appuyant sur des techniques simples de niveaux de détail discret, ainsi que sur une organisation astucieuse de la base de données des images à produire, permettant une gestion optimale de l'emprunte mémoire et de la bande passante. En effet, la mise en oeuvre d'un cache prédictif pour transférer les pavés requis pour l'affichage en fonction de la position du centre d'intérêt permet de répartir les transferts de données de façon optimale pour les différents niveaux de détail. De manière plus générale, le procédé selon l'invention utilise la souplesse des niveaux de détail discrets mais avec un impact sur les performances et l'utilisation de la mémoire à la fois très faible et borné. Avantageusement, les restrictions induites sur les données d'entrée sont réduites en utilisant le procédé selon l'invention. Les données d'entrée consistent notamment en un pavage du terrain en plusieurs grilles régulières imbriqués. Le contenu de chaque pavé peut notamment être un ensemble de maillages triangulaires irréguliers quelconques. Avantageusement, l'impact du procédé selon l'invention sur les performances intrinsèques de l'affichage d'image est minime.30

Claims (8)

1. REVENDICATIONS1. Procédé de gestion d'une mémoire cache pour un dispositif d'affichage comportant au moins une carte graphique et une mémoire cache, et couplé à une base de données massive stockant (80) des données de terrain, le procédé comprenant les étapes suivantes : - générer (81) plusieurs grilles régulières (1, 2, 3) de pavés de terrain de niveau de résolution différents (LODO, LODI , LOD2) pour représenter les données de terrain stockées dans la base de données massive ; - extraire (82, 120) des données de terrain de la base de données massive pour plusieurs niveaux de résolution, les données de terrain extraites formant une pyramide d'extraction composée d'une fenêtre d'extraction pour chaque niveau de détail, - stocker en mémoire cache la pyramide d'extraction ; - sélectionner (83, 121) des pavés de la pyramide d'extraction qui contribuent à une image ; et - transmettre vers la carte graphique les pavés sélectionnés pour permettre un tracé (122) du rendu à partir des pavés sélectionnés.
2. 2. Procédé selon la revendication 1, caractérisé en ce que les données de terrain sont extraites pour plusieurs niveaux de résolution pour composer une pyramide d'extraction, ladite pyramide d'extraction étant constituée d'une fenêtre glissante d'extraction pour chaque niveau de résolution, ladite fenêtre glissante d'extraction étant définie par un nombre de pavés de terrain fixé identique pour tous les niveaux de résolution, lesdits pavés s'étendant autour d'une position dite position du centre de la fenêtre glissante d'extraction, ledit centre de la fenêtre glissante d'extraction évoluant en temps réel en fonction de l'évolution de la position d'un centre d'intérêt, le centre d'intérêt étant déterminé en fonction de la position de l'observateur par rapport au dispositif d'affichage.
3. 3. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'une fenêtre glissante est mise en mémoire cache,comporte une zone active destinée à être affichée, et une zone de pré-chargement qui permet d'anticiper les transferts desdites données.
4. 4. Procédé selon la revendication 2, caractérisé en ce que la largeur d'une fenêtre glissante d'extraction est définie par un nombre pair de pavés de terrain.
5. 5. Procédé de rendu selon la revendication 2, caractérisé en ce qu'une pyramide d'extraction comportant pour chaque niveau de résolution différent une fenêtre glissante d'extraction constituée d'une grille de pavés, le pas de déplacement du centre d'une fenêtre glissante d'extraction de niveau de résolution L, est aligné sur le pas d'une grille de niveau de résolution L+1, L étant un entier, le niveau de résolution L+1 étant moins détaillé que le niveau de résolution L.
6. 6. Procédé de rendu selon la revendication 5, caractérisé en ce que les grilles de résolution différentes de la fenêtre glissante forment un arbre quaternaire, chaque niveau de l'arbre correspondant à un niveau de résolution.
7. 7. Procédé de rendu selon la revendication 6, caractérisé en ce que le rendu de chaque pavé de la fenêtre glissante est déterminé en parcourant en profondeur l'arbre quaternaire du niveau le moins résolu au niveau le plus résolu.
8. 8. Procédé de rendu selon la revendication 7, caractérisé en ce que chaque pavé P de niveau L en intersection avec le champ de vision, et situé dans la marge de transition du niveau de résolution L-1, est tracé en mélangeant le pavé P à ses enfants dans l'arbre quaternaire.