Brevet FR2872620A1 — publié le 20060106

La présente invention concerne l'affichage d'objets graphiques superposés notamment sur des fonds de cartes de navigation affichés sur un écran d'affichage. Elle s'applique notamment, mais non exclusivement à l'affichage de cartes de navigation sur un écran à cristaux liquides tel que ceux utilisés dans les systèmes de navigation embarqués notamment à bord des véhicules automobiles. Les systèmes de navigation actuels utilisent des bases de données cartographiques mémorisant des quantités de renseignements relatifs à une zone géographique, tels que des noms de rue, des points d'intérêts, etc. Ces objets sont en général mémorisés sous une forme vectorielle (forme évoluée) qui ne tient pas compte de la nature en matrice de points de l'écran d'affichage. En fonction de l'échelle de la représentation en cours du fond de carte à l'écran, un certain nombre de symboles graphiques (textes, icones...) représentatifs de ces objets peuvent être affichés. Il est cependant nécessaire de traiter les objets à afficher afin d'éviter les superpositions qui rendraient l'affichage illisible. Il existe des méthodes mathématiques de calcul d'intersection d'aires visant à analyser les recouvrements possibles des différents objets susceptibles d'être affichés sur la carte. On a ainsi proposé de définir une enveloppe pour chaque objet à afficher et de tester le recouvrement des enveloppes des objets à afficher à l'aide d'algorithmes classiques. Toutefois, ces méthodes présentent l'inconvénient de faire intervenir un grand nombre de calculs manipulant des nombres réels et d'utiliser d'importantes ressources de mémoire. Elles sont donc incompatibles avec les temps de réponse requis lors de manipulations de cartes (défilement, changement d'échelle). En outre, si l'on souhaite obtenir un espace minimal entre chaque objet à afficher, il est nécessaire d'agrandir les enveloppes définies des objets, ce qui conduit à alourdir les calculs. Par ailleurs, il est difficile, voire impossible de prévoir les durées de traitement nécessaires, du fait que dans la plupart des cas, celles-ci dépendent du nombre d'objets à afficher et/ou déjà affichés. Cette impossibilité de prévoir une durée maximale de traitement constitue un inconvénient majeur dans le cas de systèmes temps réel. D'autres méthodes envisagent la superposition des informations dans différents "plans d'affichage", chacun affecté d'une transparence variable en fonction d'une priorité affectée à l'objet à afficher (FR 2 740 889). La présente invention a pour but de proposer une méthode simple et 35 rapide, ne nécessitant que de faibles ressources de calcul et de mémoire, pour détecter des superpositions d'objets graphiques à afficher, en vue de pouvoir décider de l'affichage ou non de ces objets, ou d'un éventuel déplacement de ceux-ci dans une zone libre de recouvrement. Cet objectif est atteint par la prévision d'un procédé de détection de recouvrements d'objets lors de l'affichage sur un écran d'affichage d'une carte composée d'un fond de carte sur lequel des objets sont affichés en superposition. Selon l'invention, ce procédé comprend des étapes consistant, pour chaque objet à afficher sur le fond de carte, à : (a) déterminer des caractéristiques de positionnement et de dimensions d'un objet graphique composé de pixels juxtaposés, dont la forme simple correspond 10 au contour de l'objet à afficher, (b) déterminer en fonction des caractéristiques de l'objet graphique les positions respectives des pixels de l'objet graphique dans une mémoire graphique dont les dimensions en nombre de pixels correspondent à celles de l'écran d'affichage, et (c) si les positions déterminées des pixels de l'objet graphique ne sont pas déjà occupées dans la mémoire graphique par un autre objet graphique, placer dans un état occupé les pixels situés aux positions déterminées dans la mémoire graphique. Selon un mode de réalisation préféré de l'invention, si un objet à afficher est de type texte, l'objet graphique correspondant est un segment de ligne dont l'épaisseur correspond à la taille des caractères du texte, et la longueur correspond à la taille et au nombre des caractères du texte. Selon un autre mode de réalisation préféré de l'invention, si une position déterminée d'un pixel de l'objet graphique est déjà occupée dans la mémoire graphique par un autre objet graphique, il comprend des étapes consistant à modifier une caractéristique de positionnement et/ou de dimensions de l'objet graphique, et répéter les étapes (b) et (c). Avantageusement, un nombre prédéterminé de tentatives d'insertion d'un objet graphique dans la mémoire graphique sont effectuées avant d'abandonner l'affichage de l'objet correspondant à l'objet graphique. Selon un autre mode de réalisation préféré de l'invention, les formes possibles des objets graphiques insérés dans la mémoire graphique sont des segments de ligne, des rectangles et des polygones, la détermination des positions des pixels d'un objet graphique faisant intervenir un algorithme de tracé adapté à la forme de l'objet graphique. De préférence, l'algorithme de tracé choisi pour un segment ou un 35 rectangle est l'algorithme de Bresenham. Un mode de réalisation préféré de l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels: La figure 1 représente schématiquement une image réelle à afficher par exemple d'une carte sur laquelle sont superposés différents objets; La figure 2 représente la transposition dans un espace numérique discret de l'image montrée sur la figure 1, dans laquelle sont montrées les zones occupées 5 par les objets à superposer dans l'image affichée; La figure 3 montre l'image réelle représentée sur la figure 1 dans laquelle un objet a été ajouté ; La figure 4 représente la transposition dans l'espace numérique discret de l'image montrée sur la figure 3, incluant la zone occupée par l'objet ajouté ; La figure 5 illustre sous la forme d'un organigramme les différentes étapes du procédé selon l'invention. L'invention se base principalement sur le fait que la perception d'une image affichée est subjective et qu'une solution mathématique est probablement trop précise pour répondre au besoin réel, compte tenu que l'image à obtenir présente un nombre fini de points. La perception d'une image est en fait liée à un facteur de densité de points, La figure 1 représente une image à afficher, par exemple un fond de carte géographique 1, sur lequel doivent être superposés différents objets vectoriels complexes, tels que des informations textuelles, des icones, ou des objets graphiques complexes. Les informations textuelles peuvent être inscrites aussi bien suivant une droite qu'une courbe. Le procédé selon l'invention consiste tout d'abord à transformer les objets vectoriels en objets graphiques de forme simple (segment de droite ou courbe, rectangle ou polygone) pour lesquels il existe des algorithmes de tracé dans un espace numérique discret. Cette transformation consiste à déterminer la forme, les dimensions et la disposition (position et orientation) dans l'image à afficher de l'objet graphique, en fonction de l'échelle du fond de carte sur laquelle l'objet doit être affiché, de la forme du contour de cet objet, ainsi que de l'emplacement et de la disposition de celui-ci sur le fond de carte à afficher. Ainsi, un texte tel que le nom d'une route est défini sous forme vectorielle notamment par une forme (segment de droite ou courbe), une orientation, une taille de caractères (police de caractères) et une position par rapport au fond de carte à afficher. L'objet graphique correspondant au contour du texte est un segment de même forme que le texte, dont l'épaisseur de trait correspond à la taille des caractères du texte, compte tenu de l'échelle du fond de carte à afficher, dont la position et l'orientation dans l'image correspondent à celle du texte, et dont la longueur est déterminée en fonction du nombre de caractères du texte, de la police de caractères et de l'échelle du fond de carte. Un objet de forme complexe tel qu'une icône, est défini sous forme vectorielle par les coordonnées relatives d'un ensemble de points reliés par des lignes droites ou courbes. L'objet graphique correspondant au contour de cet objet est obtenu définissant à partir des coordonnées relatives des points de l'objet un rectangle ou un polygone incluant tous ces points. Le procédé selon l'invention consiste ensuite à utiliser un algorithme de tracé dans l'espace numérique discret de l'objet graphique obtenu, qui est choisi en fonction de la forme de cet objet. Pour les tracés de segments de droite, de rectangles ou de polygones, on peut choisir par exemple l'algorithme de Bresenham qui présente l'avantage de ne pas faire intervenir d'opérations complexes telles que des multiplications ou des divisions et de ne manipuler que des nombres entiers. Le tracé des objets graphiques est effectué dans une mémoire graphique dont les dimensions correspondent à celles de l'image à afficher. II consiste pour chaque objet graphique à afficher, à placer à l'état occupé (par exemple de 0 à 1) chaque pixel de la mémoire graphique correspondant à un pixel occupé par l'objet graphique dans l'image à afficher. La taille de cette mémoire peut donc être très faible puisqu'il suffit d'un bit par pixel de l'image à afficher. La figure 2 illustre le contenu de la mémoire graphique 2 lorsqu'on cherche à afficher l'image réelle représentée sur la figure 1, les pixels occupés étant représentés en noir. La figure 5 représente une procédure 10 conforme au procédé selon l'invention qui est exécutée à chaque fois que l'on ajoute un nouvel objet vectoriel à afficher en superposition sur le fond de carte, comme dans l'exemple de l'image réelle 1 représentée sur la figure 3. Sur la figure 5, le procédé selon l'invention comprend tout d'abord une étape 11 de transformation de l'objet vectoriel à afficher en objet graphique, cette étape consistant à déterminer la forme, les dimensions et la disposition de l'objet graphique correspondant, c'est-à-dire de la zone graphique occupée par l'objet à afficher. A l'étape suivante 12, on détermine successivement la position de tous les pixels occupés par l'objet graphique dans la mémoire graphique 2 à l'aide de l'algorithme adapté à la forme de l'objet graphique. A chaque fois que la position d'un pixel est déterminée, on teste à l'étape suivante 13 si l'emplacement déterminé du pixel de l'objet graphique à insérer est libre ou occupé par un objet graphique tracé préalablement dans la mémoire graphique 2. Si cet emplacement est libre, on mémorise dans une mémoire tampon la position du pixel à l'étape suivante 14. La mémoire tampon présente par exemple une taille correspondant à la taille de la mémoire graphique 2, ou bien se présente sous la forme d'une table de coordonnées de pixels. S'il ne s'agit pas du dernier pixel à déterminer de l'objet graphique (étape 15), on reprend la procédure à l'étape 12 pour déterminer le pixel suivant de l'objet graphique à insérer dans la mémoire graphique. Dans le cas contraire, tous les pixels de l'objet graphique sont déterminés et ne recouvrent pas un objet graphique préalablement inséré dans la mémoire graphique. On insère alors dans la mémoire graphique 2 les pixels de l'objet graphique mémorisés dans la mémoire tampon (étape 16). Par contre, si à l'étape 13 la position d'un pixel de l'objet graphique à insérer n'est pas libre dans la mémoire graphique 2, cela signifie que l'objet graphique que l'on cherche à tracer se superpose avec un objet graphique préalablement tracé, et donc que l'objet vectoriel correspondant à superposer sur le fond de carte à afficher se superpose avec un autre objet à afficher. Le tracé en cours de l'objet graphique est alors annulé pour tester un autre emplacement de l'objet graphique, une autre disposition ou une taille modifiée de celui-ci. Dans ce cas, on modifie une caractéristique (emplacement ou disposition dans l'image, dimension) de l'objet graphique à l'étape 16 et on exécute à nouveau la procédure 10 à partir de l'étape 11. Si ce tracé de l'objet graphique échoue après un nombre prédéfini de tentatives, l'insertion de l'objet dans l'image affichée est alors abandonnée. Bien entendu, cet abandon n'exclut pas que l'objet apparaisse ultérieurement à l'écran, par exemple si l'utilisateur change l'échelle du fond de carte affiché. La figure 4 montre en pixels noirs l'objet graphique correspondant à l'objet ajouté montré sur la figure 3, les pixels déjà occupés tels que représentés sur la figure 2 étant repérés par des hachures doubles. Au lieu d'indiquer uniquement les pixels de l'image à afficher, occupés par les objets à afficher, les pixels de la mémoire graphique occupés par un objet graphique peuvent contenir un identifiant d'objet graphique, un niveau de priorité d'affichage, ou encore un identifiant de plan d'image si l'image affichée est composée de plusieurs plans d'image superposés. REVENDICATIONS 1. Procédé de détection de recouvrements d'objets lors de l'affichage sur un écran d'affichage d'une carte composée d'un fond de carte (1) sur lequel des objets sont affichés en superposition, caractérisé en ce qu'il comprend des étapes consistant, pour chaque objet à afficher sur le fond de carte, à : (a) déterminer des caractéristiques de positionnement et de dimensions d'un objet graphique composé de pixels juxtaposés, dont la forme simple correspond au contour de l'objet à afficher, (b) déterminer en fonction des caractéristiques de l'objet graphique les positions respectives des pixels de l'objet graphique dans une mémoire graphique (2) dont les dimensions en nombre de pixels correspondent à celles de l'écran d'affichage, et (c) si les positions déterminées des pixels de l'objet graphique ne sont pas déjà occupées dans la mémoire graphique par un autre objet graphique, placer dans un état occupé les pixels situés aux positions déterminées dans la mémoire graphique. 2. Procédé selon la revendication 1, caractérisé en ce que si un objet à afficher est de type texte, l'objet graphique correspondant est un segment de ligne dont l'épaisseur correspond à la taille des caractères du texte, et la longueur correspond à la taille et au nombre des caractères du texte. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que si une position déterminée d'un pixel de l'objet graphique est déjà occupée dans la mémoire graphique (2) par un autre objet graphique, il comprend des étapes consistant à modifier une caractéristique de positionnement et/ou de dimensions de l'objet graphique, et répéter les étapes (b) et (c). 4. Procédé selon la revendication 3, caractérisé en ce qu'un nombre prédéterminé de tentatives d'insertion d'un objet graphique dans la mémoire graphique (2) sont effectuées avant d'abandonner l'affichage de l'objet correspondant à l'objet graphique. 5. Procédé selon l'une des revendications 1 à 4, caractérisé en ce que les formes possibles des objets graphiques insérés dans la mémoire graphique sont des segments de ligne, des rectangles et des polygones, la détermination des positions des pixels d'un objet graphique faisant intervenir un algorithme de tracé adapté à la forme de l'objet graphique. 6. Procédé selon la revendication 5, caractérisé en ce que l'algorithme de tracé choisi pour un segment ou un rectangle est l'algorithme de Bresenham.