Brevet FR2901439A1 — publié le 20071123

- Pair Serveur : Le Pair Serveur est un Pair d'un réseau de Pair à Pair qui peut effectuer un rôle de serveur de données pour d'autres Pairs qui s'y connectent ; Pair Client : Le Pair Client est un Pair d'un réseau de Pair à Pair qui 5 demande de l'information à des Pairs Serveurs. Arbre de sélection : L'arbre de sélection est une description simplifiée d'une représentation hiérarchique ne contenant que les informations de sélection. L'arbre de sélection est utilisé pour déterminer les noeuds qui sont visibles pour un point de vue donné ; 10 - Connectivité : la connectivité représente la manière dont sont connectés les Pairs les uns avec les autres. Dans notre cas la connectivité est fonction de la position des pairs dans un espace virtuel (i.e. de leur proximité directe) ; TTS (de l'anglais Time To Serve pour temps de service ) : temps que met l'application distante à répondre à une requête particulière. Ce 15 temps inclut le TTL (de l'anglais Time To Live pour Temps de Vie ) qui est le temps de transport des données sur le réseau ; Pourcentage de réalisation : Le pourcentage de réalisation correspond au pourcentage de requêtes acquittées par l'application distante ; Pourcentage de chargement : Le pourcentage de chargement correspond au 20 pourcentage de données chargée pour un point de vue donné par rapport à ce qui devrait être chargé si l'application distante disposait de toute cette information ; Upload (pour chargement ) : L'Upload est le débit que peut fournir le pair distant. Il peut être mesuré, ou transmis par le pair distant s'il décide 25 d'allouer une bande passante particulière pour l'envoi des données. 2 SOLUTIONS DE L'ART ANTERIEUR 2.1 Art antérieur Depuis la popularisation de l'Internet, de nombreuses personnes et entités ont mis en places des moyens logiciels permettant la création de mondes virtuels 30 en trois dimensions. Ces moyens logiciels se sont concrétisés par la mise en oeuvre de techniques de compressions, de définition d'environnement en trois dimensions ou d'environnements multimédias et de techniques de transfert de l'information. Cependant, les mondes virtuels en trois dimensions sont caractérisés par d'importants volumes de données. Les architectures centralisées classiques n'offrent pas de performances suffisantes pour permettre un échange dynamique des informations de constitution des environnements en trois dimensions en temps réel à un nombre d'utilisateurs important. Des alternatives ont été proposées pour pallier les problèmes de performances. Elles consistent généralement à précharger, au sien du terminal considéré, une base de données locale décrivant l'intégralité d'un monde virtuel. Les informations reçues depuis le serveur et envoyées à ce dernier peuvent alors se limiter à des échanges d'interaction d'un utilisateur avec l'environnement dans lequel il évolue et non plus des échanges visant à permettre au terminal de construire un environnement en temps réel. De telles solutions ont cependant leurs limites, telles que par exemple l'obligation de mettre à jour régulièrement tout ou partie de l'environnement sur le terminal considéré, ce qui peut poser des problèmes quand le volume des données à télécharger est conséquent ou encore lorsque le terminal considéré possède des capacités de stockages limités. Il n'est donc pas pertinent d'installer les environnements virtuels statiquement, au sien des terminaux. Une nouvelle technique très récente présentée dans le document A Case For 3D Streaming on Peer-to-Peer Networks de Shun-Yun Hu , National Central University of Taiwan 2006, présente une technique de partage des informations de constitution des environnements en trois dimensions basée sur le principe des réseaux de pair à pair. Selon cette technique, chaque terminal possède, à un instant donné, une partie des informations de constitution de l'environnement dans lequel il évolue (des cellules). Il peut avoir obtenu ces informations soit de la part d'un pair serveur, soit de la part d'un serveur central. Plus particulièrement, la technique proposée permet à des terminaux voisins qui sont situés dans une même portion d'un espace virtuel de s'échanger des informations de constitution de cet espace (les cellules qu'ils connaissent) sans qu'il soit obligatoirement nécessaire pour les terminaux d'interroger un serveur central. En effet, les terminaux dont un utilisateur interagit dans une portion d'espace commune à plusieurs autres terminaux (dont d'autres utilisateurs interagissent également dans cette portion d'espace) peuvent, par le biais de techniques de transmissions de données entre pairs voisins, s'échanger des informations de constitution des cellules communes. Le serveur central est alors déchargé de tout ou partie des requêtes en provenance des clients. Du point de vue du serveur, une telle technique présente de nombreux avantages, notamment le fait de la décharger d'une grande partie des demandes de transfert des informations de constitution de l'environnement 3D. Grâce à une telle technique, les terminaux, quant à eux, s'échangent des données sans qu'il soit théoriquement nécessaire d'attendre une réponse de la part d'un serveur. Cependant, l'intérêt principal attendu de cette technique de l'art antérieur est de permettre une scalabilité étendue et une utilisation simultanée par un très grand nombre d'utilisateur. 2.2 Inconvénients de l'art antérieur Un inconvénient de cette technique d'échange de pair à pair de l'art antérieur est notamment lié à l'absence de prise en compte de la constitution de la portion d'espace virtuel à échanger entre des pairs. En effet, cette technique de l'art antérieur définit bien un environnement commun entre les pairs (les cellules). Cette portion commune de l'environnement est partagée par tous les pairs dont un utilisateur évolue dans cette partie de l'environnement. Cependant les cellules ne distinguent pas les niveaux de détail de l'environnement. Ainsi, les utilisateurs situés dans une même portion d'espace virtuel partagent l'intégralité de la définition de cet espace, et ce quelle que soit, par exemple, la distance virtuelle qui sépare deux utilisateurs dans un espace. Par exemple, si on considère, dans une portion d'espace visible, deux avatars différents (représentation de deux utilisateurs différents dans la portion d'espace), le premier avatar se situant à deux mètres d'un point d'intérêt et le second avatar se situant à vingt mètres de ce même point d'intérêt. Selon la technique de l'art antérieur, ces deux pairs rechercheront et obtiendront, auprès d'autres pairs situés dans la même portion d'environnement, les mêmes informations de constitution. Une telle obtention se révèle inadéquat du fait que les deux avatars n'ont manifestement pas la même perception du point d'intérêt considéré. Un autre inconvénient de cette technique de l'art antérieur est du à l'incapacité d'un pair client considéré à prendre en compte le volume des données à télécharger depuis des pairs serveurs. En effet, la technique de l'art antérieure décrit bien un mode de sélection des pairs serveurs par un pair client en tenant compte d'un temps de latence, d'une capacité de bande passante et d'une capacité des pairs serveurs considérés à fournir l'information attendue. Cependant, une telle technique ne permet pas de gérer correctement les transferts de données entre les pairs. En effet, selon cette technique de l'art antérieur, le pair serveur qui répond le mieux à ces critères de classification sera privilégié par un pair client pour l'obtention de données manquantes. Cependant, même si ce pair serveur est très performant, la technique de l'art antérieur ne tient pas compte du volume de données à télécharger, pas plus que d'une présence d'une file d'attente éventuelle. Ainsi, l'utilisation d'une méthode de transfert de pair à pair par cette technique de l'art antérieure n'est pas à même de garantir un temps de téléchargement inférieur à celui que fournirait un serveur. 3 RESUME DE L'INVENTION La solution proposée par l'invention permet de pallier ces inconvénients de l'art antérieur, grâce à un procédé de sélection d'au moins un pair serveur pour la transmission de données de visualisation d'un contenu à destination d'au moins un pair client au sein d'un réseau de pairs, lesdites données étant organisées sous la forme de noeuds d'un arbre hiérarchique comprenant au moins un noeud parent et au moins un noeud fils, un élément visualisable étant associé à chacun desdits noeuds. Selon l'invention, un tel procédé comprend une phase de sélection d'au moins un desdits pairs serveur comprenant au moins une partie desdites données de visualisation et/ou au moins une partie dudit arbre hiérarchique, ladite phase de sélection tenant compte d'au moins une information représentative d'une taille de données d'au moins un desdits éléments visualisables. Ainsi, l'invention repose sur une approche nouvelle de la sélection de pairs 5 serveur dans le cadre de la transmission de données de visualisation d'un contenu en utilisant la taille des informations à transmettre afin de sélectionner au mieux les pairs serveur susceptibles de transmettre l'information. Selon un aspect particulier de l'invention, ladite phase de sélection comprend une étape d'identification d'un ensemble de pairs voisins comprenant 10 au moins une partie desdites données de visualisation et/ou au moins une partie dudit arbre hiérarchique. La sélection selon la taille porte donc tout autant sur la structure définissant les données de visualisation que sur les données de visualisation elles même. En effet, selon l'invention, il est possible de sélectionner un pair qui va 15 transmettre une partie de la structure de visualisation tout en sélectionnant un autre pair pour transmettre les données de visualisation en tant que telles. Ce procédé offre donc une scalabilité importante lors de la transmission des données entre pairs d'un réseau de pair à pair. Selon un mode de mise en oeuvre particulier, ladite phase de sélection 20 comprend les étapes suivantes : détermination, par ledit au moins un pair client, d'un espace virtuel de navigation courant, représenté par un sous-arbre de visualisation courant dudit arbre hiérarchique ; sélection, par ledit au moins un pair client, d'au moins un pair serveur 25 voisin présent au sein dudit espace virtuel de navigation courant, formant ledit ensemble de pairs voisins ; transmission, audit pair client, par au moins un desdits pairs serveurs voisins, d'au moins un noeud de visualisation dudit sous-arbre de visualisation courant, suite à au moins une requête dudit pair client ; 30 - association d'au moins un desdits pairs serveurs voisins, dit pair serveur associé, à chacun desdits noeuds dudit sous-arbre de visualisation en fonction des noeuds de visualisation contenus dans chacun desdits pairs serveur ; classement, par ledit pair client, desdits pairs associés, selon ladite taille de données desdits éléments visualisables desdits noeuds de visualisation transmis, pour chacun desdits noeuds ; transmission, par lesdits pairs associés, d'au moins une donnée de visualisation desdits éléments visualisables suite à au moins une demande de transmission émise par ledit pair client, en fonction dudit classement. Le pair client dispose ainsi d'un processus permettant de sélectionner les pairs serveur en fonction d'un espace virtuel de navigation courant dans lequel il se trouve. Cet espace de navigation est représenté par un arbre hiérarchique. L'arbre hiérarchique, définissant la structure des données de visualisation, est transmis au pair client suite à une requête de celui-ci en fonction des pairs serveurs qui sont connectés. Les requêtes de transmission de l'arbre hiérarchique peuvent tenir compte de la taille des données de constitution de l'arbre à transmettre. Le pair client associe les pairs serveur voisin en fonction de la taille des données de visualisation obtenues grâce à l'arbre hiérarchique puis il effectue un classement des pairs serveurs en fonction de cette taille. Il émet ensuite des requêtes de transfert des données de visualisation aux serveurs en fonction de ce classement. Selon une caractéristique originale, ladite étape de classement tient également compte d'au moins un des paramètres appartenant au groupe comprenant au moins : une quantité de bande passante disponible pour la transmission ; un temps de service ; un temps de téléchargement ; un niveau de détail dudit au moins un noeud de visualisation ; les données présentes sur lesdits pairs serveurs ; - le pourcentage de chargement ; le taux d'acquittement ; la position desdits pairs serveurs. Ainsi, l'étape de classement ne tient pas uniquement compte de la taille pais aussi d'autres paramètres permettant de s'assurer de la disponibilité et des capacités des pairs serveur ainsi que d'un niveau de détail souhaité par le pair client. Par exemple, un pair client qui requiert des données de visualisation d'un niveau de détail faible peut tout à fait interroger un pair serveur disposant de capacité faible si le volume des données à transmettre est faible. Selon un aspect particulier de l'invention, ledit procédé de sélection met en oeuvre au moins un pair, dit pair de connectivité, gérant l'accès d'un pair client à un réseau de pairs, et ladite étape de détermination d'un espace virtuel de navigation courant comprend les sous-étapes suivantes : connexion dudit pair client à au moins un desdits pairs de connectivité, de façon à permettre audit pair client d'accéder audit réseau de pairs ; -interrogation, par ledit pair client, d'au moins un pair dont un identifiant est fourni par au moins un desdits pairs de connectivité de façon à obtenir ledit sous-arbre de visualisation ; De cette façon, le pair client obtient une connexion au réseau de pairs par le biais d'un pair qui joue le rôle de pair de connectivité. Ce pair de connectivité permet au pair client considéré d'obtenir une liste de ses voisins dans l'espace virtuel au sein duquel il évolue. Cette liste permet dans un premier temps au pair client de déterminer les pairs serveurs susceptibles de lui délivrer de l'information. L'invention concerne également un signal de données échangées entre au 25 moins un pair serveur et au moins un pair client. Selon l'invention un tel signal comprend au moins un champ d'information d'au moins une information représentative d'une taille de données d'au moins un desdits éléments visualisables. Dans un autre mode de réalisation, l'invention concerne également un 30 produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur. Selon l'invention, dans au moins un mode de réalisation, un tel produit programme d'ordinateur comprend des instructions de code de programme pour l'exécution du procédé de sélection de pairs serveur tel que décrit précédemment. L'invention concerne également un terminal comprenant un pair client de sélection d'au moins un pair serveur pour la transmission de données de visualisation d'un contenu au sein d'un réseau de pairs, lesdites données étant organisées sous la forme de noeuds d'un arbre hiérarchique comprenant au moins un noeud parent et au moins un noeud fils, un élément visualisable étant associé à chacun desdits noeuds. Selon l'invention, un tel terminal comprend des moyens de sélection d'au moins un desdits pairs serveur comprenant au moins une partie desdites données de visualisation et/ou au moins une partie dudit arbre hiérarchique, ladite phase de sélection tenant compte d'au moins une information représentative d'une taille de données d'au moins un desdits éléments visualisables. Dans un autre mode de réalisation, un tel terminal peut comprendre également des moyens de mise en oeuvre des étapes du procédé de sélection tel que décrit précédemment. L'invention concerne également un serveur comprenant un pair serveur pour la transmission de données de visualisation d'un contenu, à destination d'un pair client au sein d'un réseau de pairs, lesdites données étant organisées sous la forme de noeuds d'un arbre hiérarchique comprenant au moins un noeud parent et au moins un noeud fils, un élément visualisable étant associé à chacun desdits noeuds, Selon l'invention, un tel serveur comprend des moyens de transmission, d'au moins une donnée de visualisation desdits éléments visualisables suite à au moins une demande de transmission émise par ledit pair client, en fonction d'un classement desdites données de visualisation selon une information représentative d'une taille de données d'au moins un desdits éléments visualisables. 4 LISTE DES FIGURES D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante d'un mode de réalisation préférentiel, donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés, parmi lesquels : la figure 1 présente un modèle tridimensionnel de connexion entre pairs en fonction de leur position dans l'espace virtuel ; la figure 2 démontre l'apport de la méthode de sélection des pairs connectés à la figure 1, selon l'invention - la figure 3 décrit la transmission des structures arborescentes avec mise à jour de la connectivité ; la figure 4 illustre les étapes d'initialisation de la structure arborescente par le pair client suivie de la visualisation de la représentation ; la figure 5 décrit la liste des noeuds de la structure arborescente qui sont 15 actifs et fusionnables pour un niveau de détail donné ; la figure 6 illustre le découpage d'un arbre de description ; la figure 7 décrit un exemple d'étapes conduisant à la création d'un sous-arbre de visualisation ; la figure 8 décrit également un exemple d'étapes conduisant à la création 20 d'un sous-arbre de visualisation ; la figure 9 présente un synoptique de la représentation visuelle d'un objet en fonction de la position de l'utilisateur dans la scène ; la figure 10 présente un synoptique de la représentation visuelle d'un objet en fonction du point de vue de l'utilisateur ; 25 - la figure 11 présente un diagramme de décision conduisant à la répartition des requêtes entre les pairs connectés et le serveur central ; la figure 12 illustre l'architecture matérielle d'un pair client selon l'invention ; la figure 13 illustre l'architecture matérielle d'un pair serveur selon 30 l'invention ; la figure 14 décrit le contenu du paquet HDescRPck ; la figure 15 décrit succinctement le contenu du paquet HDescAPck ; la figure 16 décrit une méthode de reconstruction de l'arbre hiérarchique ; la figure 17 décrit le graphe de scène correspondant à l'utilisation d'un HDescNode et d'un FootprintSetNode ; la figure 18 décrit précisément le contenu du paquet HDescAPck . 5 DESCRIPTION DETAILLEE DE L'INVENTION 5.1 Rappel du principe de l'invention Le principe général de l'invention repose donc sur la prise en compte d'une taille de données à télécharger lors de la sélection de pairs serveurs par un pair client. Cette prise en compte est effectuée à deux niveaux : lors de la constitution d'un arbre de description de l'espace virtuel, permettant par le pair client suite à l'interrogation des pairs serveur : la taille des données à télécharger est alors calculée au fur et à mesure de la réception des réponses de la part des pairs serveurs et du niveau de détail recherché. On calcule, pour chacun des noeuds de l'arbre de description, la taille des données géométriques qui y sont associées. Après génération de l'arbre de description hiérarchique, un découpage de celui-ci peut être effectué de manière a ce qu'il puisse être lui aussi transmis de manière progressive en fonction du point de vue l'utilisateur. Si un tel découpage est effectué, les informations concernant la taille des données ainsi que les index des parties dépendantes sont ajoutées dans les entêtes des différentes parties. Ainsi, après réception de la première partie de l'arbre de description, chaque pair est en mesure de demander les parties manquantes de l'arbre de description en tenant compte de leurs tailles respectives. Il en est de même pour les informations géométriques dont la taille est elle aussi connue. lors de la sélection et du classement des pairs serveur à partir desquels le pair client décide de télécharger les données de visualisation de l'espace virtuel considéré. Le principe de l'invention peut être mis en oeuvre selon un processus qui comporte les étapes suivantes : on associe au client courant les pairs dont l'observateur associé est proche dans l'espace virtuel courant de navigation ; lorsqu'au cours de sa navigation dans l'espace virtuel courant, le client manque de données de modélisation pour la navigation, par exemple lors d'un déplacement dans l'espace de navigation à partir d'un nouveau point de vue (ou à partir d'un premier point de vue) ou lorsque la scène a évoluée..., le client va solliciter au moins un pair serveur identifié par un paramètre de priorité, puis si celui-ci ne possède pas l'information le pair suivant selon ce même critère. De manière optionnelle, le paramètre de priorité tient compte d'au moins l'un des éléments suivants : le délai de réponse pour obtenir un premier bit (le temps de service) ; - la capacité d'émission ; la capacité de réception ; les données présentes sur le pair ; le pourcentage de chargement ; le taux d'acquittement ; - la position. Egalement de manière optionnelle, certains pairs sont référencés comme serveurs, avec un paramètre de complétude pour les données qu'ils possèdent. Toujours optionnellement, la mise à jour de la liste des pairs et/ou de leur paramètres associés est effectuée périodiquement ou suivant des évènements tels que : une absence de réponse de la part d'un pair ; une évolution des paramètres (éloignement constatée du pair, temps de réponse en augmentation, débit non assuré ...) ; Selon un mode de réalisation particulier, on décrit par la suite un enchaînement de différentes étapes menant à la sélection des pairs serveurs par un pair client et à la prise en compte de la taille des données à télécharger lors de la sélection. Ces étapes sont les suivantes : Initialisation de la connectivite du pair client ; Mise à jour de la connectivité du pair client ; Tri des pairs serveur en fonction de leurs temps de service ; Récupération des données de visualisation au niveau des pairs serveurs. 5.1.1 Initialisation de la connectivité Cette première étape correspond à la connexion au monde virtuel. Le pair client reçoit alors une liste de pairs serveurs auxquels il doit se connecter. La nouvelle liste de voisin auquel le pair doit se connecter peut être récupérée soit via le noeud pair à pair auquel il est connecté, soit via un serveur central qui gère la connectivité. Ces pairs correspondent à des voisins dans le monde virtuel et leur nombre peut être limité par la capacité du pair considéré. 5.1.2 Mise àjour de la connectivité Cette deuxième étape est effectuée à intervalles réguliers. Elle consiste à mettre à jour la connectivité du pair considéré. Entre chaque itération les pairs se déplacent au sein de l'espace virtuel. La connectivité des pairs varie donc en fonction du temps. A chaque connexion à un nouveau pair serveur, le pair considéré récupère ou mesure l'Upload disponible du nouveau pair ainsi que le temps de réponse de l'application ( Time To Serve ). Dans le cas ou un pair mesure l'Upload et le TTS , il doit re-effectuer ces opérations a intervalle régulier. L'Upload est une bande passante maximum allouée par un pair pour servir les autres pairs. Le pair utilisera une partie ou toute la bande passante disponible du pair interrogé. Une contrainte pourra par exemple de ne pas prendre plus de bande passante que celle disponible compte tenu du nombre d'autres pairs qui sont connectés au pair que l'on souhaite interroger. Il pourrait par exemple être avantageux de répartir équitablement de manière continue (ou dynamique) cette ressource en bande passante disponible via le pair que l'on souhaite mettre a contribution (ou éventuellement d'être informé du nombre de pairs qui utilisent la bande passante pour que tous ceux qui l'utilisent le fassent de manière équitable). 5.1.3 Tri des pairs en fonction du TTS Cette troisième étape peut elle aussi être effectuée à intervalle régulier. Elle consiste à trier les pairs en fonction du temps de réponse qui a été mesuré. Le pair qui a le temps de réponse le plus court est celui susceptible de fournir la donnée requise le plus rapidement possible. La volumétrie des données intervient alors. En effet, cette étape de tri tient compte de la cohérence de la taille des données à télécharger avec les capacités de chargement ( Upload ) disponibles au niveau du pair serveur considéré. Par exemple, dans le cas d'une faible volumétrie, (par exemple quand le niveau de détail est faible), un pair serveur disposant de capacités faible, voire très faible pourra tout de même être considéré comme étant le pair serveur pertinent pour le chargement du noeud considéré, par opposition à un pair disposant de très fortes capacités, mais d'un TTS plus important. Cette caractéristique est intéressante dans le contexte d'une représentation hiérarchique progressive. C'est-à-dire que pour pouvoir décoder un niveau de détail particulier, il est nécessaire de disposer des niveaux de détails plus grossiers. On transmet dans les noeuds de géométrie le delta par rapport à la représentation plus grossière. Les noeuds situés dans la partie haute de l'arbre sont donc les plus importants et il est judicieux de chercher à les récupérer le plus rapidement possible. 5.1.4 Récupération des données de visualisation Une fois que le pair est connecté à un nombre fini de pairs voisins (le serveur qui héberge la représentation complète est considéré comme un voisin qui dispose de toute l'information), le pair client démarre la procédure utile pour récupérer les données nécessaires à sa visualisation (initialisation de la récupération), puis il procède au téléchargement (récupération des données). 5.1.4.1 Initialisation de la récupération La première phase correspond à l'initialisation du client. Après une procédure de connexion, il reçoit dans un fichier une description simplifiée de l'objet ou une première partie de la description simplifiée de l'objet (c'est à dire. les niveaux de détail très grossiers). Ce fichier peut être demandé à n'importe lequel des pairs auxquels il est connecté (En particulier le serveur qui héberge la représentation complète). Puis le processus comprend alors les étapes suivantes : Emission de tout ou partie du fichier de description de l'arborescence par les pairs serveurs ou par le serveur central. Le fichier de description contient pour chaque noeud associé à un niveau de détail de l'arbre, sa position dans le repère de la scène ainsi qu'une zone de sélection. On obtient donc un fichier qui peut être progressif (donc découpé selon les contraintes de l'arbre hiérarchique) qui contient pour chacun des noeuds qui y sont inclus : L'index du noeud ; La position du centre du noeud (position x,y,z du centre de gravité par exemple) ; La zone de sélection pour ce noeud (rayon r par exemple) qui est en fait un critère d'erreur ; L'index du noeud père. La taille de la donnée associée (géométrique par exemple) ; Dans un mode de réalisation particulier, Il est possible d'utiliser une numérotation adaptée des noeuds, Afin de ne pas transmettre les index des noeuds. Dans un autre mode de réalisation, on peut optionnellement ajouter une aura correspondant à la boite englobante du noeud pour limiter le nombre de noeuds géométriquessélectionnés pour une position donnée (compte tenu de la pyramide de vue). L'entête de la partie du fichier de description, s'il est progressif, contient de manière optionnelle : - le nombre de fils de la partie ; Puis pour chaque partie : l'index de la partie fils ; la taille de la donnée de la partie fils ; le nombre de noeuds terminaux (c'est à dire auxquels il manque des fils) dont des fils sont contenus dans la partie fils considérée. (cette information est utile pour le décodage et pour déterminer quelle partie de la description est nécessaire si il manque des fils dans l'arbre hiérarchique). Optionnellement le centre de gravité et l'aura de perceptibilité des différentes parties. Cependant, ces informations peuvent aussi être déterminées après réception de la partie de description que l'on considère notamment grâce aux informations de sélection contenues dans les noeuds de description transmis. Réception du fichier de description de l'arborescence par le client. Ce dernier décode le fichier puis reconstruit la structure arborescente qui a été transmise. Le fichier reçu peut correspondre à une partie de la structure hiérarchique si le fichier de description est progressif. Chaque élément du fichier de description contient les informations concernant la taille et les index de ses fils de manière à pouvoir repartir la charge de la même façon que pour la géométrie. Optionnellement on peut rajouter pour chacun des éléments une position et une aura qui correspondra à la zone dans laquelle cet élément est requis. (deux solutions possibles: transmettre ces informations dans l'entête de la partie ou les déterminer après réception de la partie de description: connaissant les noeuds dont les fils sont inclus dans la partie de description qui est requise on peut déterminer une liste de pairs serveurs a interroger) Cette information permettra à chacun des pairs de déterminer parmi ses voisins ceux qui sont susceptibles de disposer de l'information souhaitée. 5.1.5 Récupération des données Cette deuxième phase correspond à la visualisation de la scène au sein du pair client : Pendant la visualisation, le client se charge de la sélection des noeuds (de l'arbre de description) à visualiser. Il utilise le fichier de description qui lui a été transmis à l'initialisation. Si la position courante de l'utilisateur est incluse dans la zone de sélection d'un noeud (géométrique ou partie de la description hiérarchique), celui-ci est sélectionné. A chaque instant, en fonction des données chargées et des noeuds requis, le client envoie des requêtes au meilleur pair serveur qu'il a déterminé de manière à recevoir les données de visualisation. La position du pair voisin est utilisée pour déterminer s'il doit avoir dans son cache la donnée requise. On utilise à cet effet des informations de sélection de LOD connus et la position du voisin pour savoir s'il dispose dans son cache de l'information considérée. Cette information est pondérée par le pourcentage de réalisation mesuré (qui correspond au taux de réponse acquittées dans le temps requis) ainsi que le pourcentage de chargement déterminé par le pair voisin (qui correspond au pourcentage de noeuds stockés dans le cache du voisin parmi ceux qui sont perceptibles compte tenu de son point de vue). La pondération se fait en triant les clients qui sont susceptible de disposer du noeud requis. Les pairs distants qui disposent potentiellement de l'information sont triés en fonction du pourcentage de chargement et de réalisation puis parmi ceux-ci et dans une limite imposée on les trie en fonction du TTS. Une fois que l'Upload d'un pair serveur a été atteint, il ne peut plus être utilisé jusqu'à acquittement des requêtes qui lui ont été transmises (ou jusqu'à ce qu'un timer de réinitialisation soit atteint s'il ne peut pas acquitter les requêtes). L'utilisation du fichier de description permet au client de converger plus vite vers la représentation optimale. Il est en mesure de générer des requêtes correspondant exactement à ses besoins et il est en mesure de les envoyer au pair qui peut lui fournir le meilleur service. Dans le cas d'une représentation arborescente avec une dépendance entre les noeuds, il est important de récupérer en premier les noeuds les plus hauts dans l'arbre (c'est-à-dire les noeuds parents). C'est à cet effet que l'on trie les pairs voisin en fonction du TTS de manière a effectuer la requête parmi ceux qui disposent de l'information a celui qui répondra le plus vite. 5.2 Connectivité entre les pairs Les pairs se connectent entre eux en fonction de leur proximité dans l'espace virtuel. Deux techniques peuvent être utilisées pour assurer la connectivité : On peut utiliser un ou plusieurs serveurs (dans ce cas chacun d'entre eux aura a sa charge une zone précise) pour assurer la connectivité. Tous les pairs doivent transmettre leur position courante au serveur auquel ils sont connectés. A intervalle régulier le serveur effectue une triangulation par exemple pour pouvoir déterminer quels sont les voisins de chaque pair (dans notre cas on effectue pour l'instant une triangulation de Delaunay en 2D ou un simple calcul de distance en 3D). Le serveur envoie ensuite à chacun des pairs qui sont connectés une liste de pairs auxquels ils doivent se connecter. Cette liste fait une taille d'au plus le nombre de pair voisins qu'a requis le pair considéré. Quand un pair reçoit ce type de message, il effectue une mise à jour de sa connectivité. C'est-à-dire qu'il se déconnecte des pairs qui ne sont pas dans la liste et il se connecte aux pairs auxquels il n'est pas déjà connecté. Si on utilise ce premier mode particulier d'initialisation, il est nécessaire que la liste de pair soit connexe de manière à pouvoir propager le message dans l'espace sauf si on utilise le pair de connectivité comme relais pour la transmission de cette information. Par connexe on entend qu'il existe au moins un chemin entre chacun des pairs de l'espace virtuel. On peut également utiliser un réseau de pairs dont la caractéristique est que les pairs sont connectés les uns avec les autres en fonction de leur position dans un même espace virtuel. Dans ce cas particulier la mise à jour de la connectivité pourra se faire en interrogeant le noeud (celui qui gère la connectivité) du réseau de pair pour savoir quels sont les voisins qui y sont connectés. On note que dans le cas d'un déplacement non limité dans un espace virtuel, la meilleure connectivité que l'on puisse utiliser sera une connectivité 3D. En effet, il est compréhensible qu'un utilisateur se déplaçant en altitude ait dans son cache des données très différentes de celles contenues dans le cache d'un utilisateur se déplaçant au niveau du sol. On présente, en relation avec la figure 1, un exemple de connectivité 3D. Les pairs (101, 102,...) sont connectés (1001, 1002, 1003, ...) en fonction de leur position dans l'espace virtuel. La connectivité est donc une connectivité 3D. 5.3 Transmission adaptée du modèle On présente, en relation avec la figure 2, l'apport principal de la technique de transmission adaptée et optimisée d'une structure de type arborescente en réseau. L'innovation repose sur la transmission d'une description de la scène pour optimiser les échanges sur le réseau. On suppose que le pair client (10) considéré est connecté à n pairs (2 dans l'exemple, 11 et 12) qui sont des voisins dans l'espace virtuel ou le serveur qui héberge la représentation complète. Régulièrement les voisins transmettent leur position courante au pair considéré. L'étape 0 permet au pair client 10 de déterminer quels sont les pairs serveurs qui vont lui fournir le fichier de description. Le fichier de description ou partie de celui-ci peut être transmis par n'importe quel pair serveur du moment que son upload est adapté. Parmi les pairs dont l'upload est adapté on choisit, par exemple, ceux dont le temps de réponse est le plus faible. L'étape 1 est une étape d'initialisation. Le client 10 demande (101) au pair serveur 11 qu'il a sélectionné de lui transmettre (102) en retour un fichier de description de l'arbre 1001 qui lui permettra de sélectionner les noeuds dont il aura besoin pour la visualisation. Les noeuds sont sélectionnés en fonction de la position de l'utilisateur dans la scène. La sélection des pairs serveurs pour la transmission du fichier de description tient compte de la taille du fichier de description à transmettre et de d'autres paramètres propres aux capacités des pairs serveurs ( TTS , Upload et pourcentage de réalisation). - L'étape 2 et l'étape 3 présentent des cas de sélection de noeuds. En fonction de la position 103 de l'utilisateur dans la scène 104 le client 10 demande (105, 106, 107, 108) les informations géométriques correspondant aux noeuds (1002, 1003) qu'il souhaite visualiser. Pour ce faire, il sélectionne (109, 110) les pairs serveurs 11, 12 les mieux adaptés compte tenu de leurs capacités respectives ( TTS , Upload et pourcentage de réalisation) et de l'importance des noeuds (leur taille, ou encore le volume de données à transmettre). L'étape 4 montre que si les données 1004 géométriques sont présentes dans le cache du client 10, aucun trafic réseau n'est généré. Le client 10 utilise les données qu'il a déjà chargé. On présente, en relation avec la figure 3, un cas particulier ou la connectivité est mise à jour. Les étapes décrites précédemment (figure 2) sont les mêmes, mais à l'instant t 1005 le pair client se déconnecte du pair serveur 12 pour se connecter au pair serveur 13. Ce cas se produit notamment quand le pair serveur 13 s'est rapproché du pair client 10 ou que le pair serveur 12 s'est déconnecté du réseau. Lorsque le fichier de description est progressif, les mêmes étapes sont répétées pour récupérer les parties manquantes du fichier de description en tenant compte de la possibilité de disposer de l'information de perceptibilité et de taille des parties de fichier de description manquantes. 5.4 Rappel du principe utilisé pour la visualisation On présente, en relation avec la figure 4, les données qui sont transmises sur le réseau pour que la visualisation puisse être effectuée. Dans un premier temps (40), après une procédure d'initialisation 401, on transmet, par l'intermédiaire du réseau 41 un arbre de sélection 402 qui correspond à la représentation hiérarchique sans les données géométriques. Seules sont transmises les données nécessaires à la sélection (index du noeud, index du noeud père, zone de sélection, centre de gravité du noeud). Une fois que l'arbre est reconstruit 42, le client peut demander 43 les informations dont il a besoin pour sa visualisation (représentations géométriques, images compressées ...). Le choix des noeuds à visualiser peut être effectuée au niveau du client grâce aux zones de sélection associées à chaque noeud. Si la position de l'utilisateur est incluse dans la zone de sélection d'un noeud, il est également sélectionné. En fonction de la position de l'utilisateur, le pair peut sélectionner les informations que le pair serveur qu'il a choisi doit lui transmettre pour permettre la visualisation. On note qu'avec cette technique, il est possible de faire varier en fonction du point de vue les paramètres de sélection du LOD . Il est donc possible de faire de l'auto adaptation pour privilégier la fluidité du déplacement ou la qualité de la représentation, en fonction de la taille des données associées au LOD considéré. De même cette gestion de LOD peut être contrainte par le débit fournit par le réseau car plus la représentation est détaillée, plus la quantité de données à transmettre est importante. Par la suite, on présente notamment le cas de la mise en oeuvre de l'invention dans le cadre d'une modélisation d'une ville en utilisant une représentation hiérarchique basée sur le PBTree . Il est clair cependant que l'invention ne se limite pas à cette application particulière, mais peut également être mise en oeuvre dans de nombreux autres domaines, et par exemple dans la visualisation en continu de flux multimédias scalables représentés par un arbre hiérarchique dans le cadre de réseaux pair à pair et plus généralement dans tous les cas où les objectifs listés par la suite sont intéressants. 5.5 Description d'un mode de réalisation 5.5.1 Description L'implémentation décrite ci-dessous correspond à une sélection du niveau de détail se basant sur la position du centre de gravité des noeuds dans la scène. A chacun des noeuds est associé une zone de sélection spécifique. La représentation 3D utilisée dans le cas présent est une ville. On utilise l'algorithme PBTree en tant que structure de description. On note par ailleurs que d'autres types de données peuvent être utilisés avec cette technique, comme le streaming basé point, ou les ondelettes par exemple. 5.5.2 Représentation 3D d'une ville La représentation 3D multi niveaux de détail utilisée dans cette implémentation est un PBTree . La figure 5 montre cette structure arborescente 50. Elle présente également la liste des noeuds actifs 51 (c'est-à-dire dont les contenus associés sont affichés sur le terminal client et qui sont susceptibles d'être raffinés).et fusionnables 52 pour un niveau de détail donné. Chaque noeud de ce PBTree stocke un modèle 2D de bâtiment à un niveau de détail donné. Les simplifications utilisées pour générer cette représentation multi niveaux de détails d'un ensemble de bâtiments sont au nombre de trois : Suppression d'un sommet de l'empreinte au sol. Fusion de deux bâtiments adjacents. Fusion de deux bâtiments non adjacents. La description du PBTree , ainsi que le processus de construction, et ses utilisations dans le cas d'un mode de navigation en survol a largement été décrite dans la partie implémentation du brevet [FR-05 02 4491: Procédé pour la gestion de la représentation d'au moins une scène 3D modélisée . L'implémentation dans le cadre de l'invention porte sur la sur la sélection des noeuds a transmettre en fonction de la position de l'utilisateur. 5.5.3 Génération du fichier de description de la structure arborescente La génération du fichier de description global est présentée en détail dans le brevet [FR-05 02 449]. Dans ce mode de réalisation particulier, on décrit le découpage de ce fichier de description global en un ensemble de sous arbres de description. Chaque sous-arbre peut faire l'objet d'un transfert séparé au pair qui le demande. Pour chacun des noeuds de l'arbre de description global, on rajoute la taille du message qui y est associé comme on l'a précisé précédemment. Cette taille permet de savoir si la requête que l'on compte faire en direction du pair considéré est compatible avec son upload . Si on transmet trop de requêtes a un pair (si la taille des messages qu'il va devoir envoyer dépasse son upload ), le pair ne pourra pas fournir le meilleur service possible. Les données souhaitées resteront dans la pile d'envois du pair pendant un temps non négligeable. Le fichier de description doit être progressif car suivant la taille de la structure hiérarchique que l'on souhaite décrire, il peut falloir un temps non négligeable pour le transmettre. En particulier, l'arbre de description du PBTree est une version simplifiée de ce dernier. Cet arbre ne contient que les informations nécessaires pour sélectionner le niveau de détail des bâtiments à afficher. Cet arbre est décomposé en une suite de sous-arbres permettant un envoi progressif de l'arbre de description depuis un serveur vers un client. 5.5.3.1 Principes de découpage de l'arbre de description en sous-arbre L'envoi progressif des sous-arbres s'effectue au gré des déplacements de l'utilisateur dans l'environnement urbain. La décomposition de l'arbre de description en sous-arbres s'effectue en fonction du nombre maximum de noeuds qui a été fixé pour tous les sous-arbres. Cette décomposition doit également respecter la structure d'arbre. Ainsi, l'ensemble des sous-arbres obtenus après décomposition doit également être un arbre. La figure 6 présente la décomposition d'un arbre de description en sous-arbres. Deux découpages sont présentés : un premier 60 avec quatre noeuds au maximum par sous-arbre 61, et un second 62 avec au plus six noeuds (63). L'arbre 61 représente la décomposition en sous-arbres de l'arbre 60. L'arbre 63 représente la décomposition en sous-arbres de l'arbre 61. Pour chaque partie d'arbre, on dispose de la taille de chacun des sous éléments de l'arbre, ainsi que de leur index. Il possible de manière optionnelle de déterminer quel est la zone de perceptibilité des fils grâce aux informations de sélection du LOD contenues dans la partie de l'arbre considérée. L'organisation des sous-arbres sous la forme d'un arbre permet implicitement d'ordonner le transfert progressif de l'arbre de description. Afin de recevoir le sous-arbre 614 (figure 6), il faudra avoir auparavant récupéré auprès du serveur les sous-arbres 613, 611 et 600. Le découpage d'un arbre en sous arbre doit respecter les contraintes suivantes : Les noeuds du premier niveau de l'arbre à découper doivent tous être compris dans le même sous-arbre. Ce sous-arbre constitue en fait la racine de l'arbre de sous-arbres, Tous les fils d'un noeud de l'arbre à découper doivent être compris dans le même sous-arbre. Cela implique que le nombre maximum de noeuds dans un sous-arbre doit être supérieur ou égal au nombre maximum de fils qu'un noeud de l'arbre à découper peut posséder. Cette contrainte a pour défaut d'engendrer le sous-remplissage de sous-arbres. C'est le cas notamment, du sous-arbre 621 dans le découpage utilisant six noeuds au maximum, Dans le cas du découpage du PBTree, la racine est une racine implicite. Celle-ci n'est donc pas incluse dans le premier sous-arbre. 5.5.3.2 Algorithmes de découpage de l'arbre de description en sous-arbres On décrit, en relation avec la figure 7, l'algorithme de découpage d'un arbre en sous-arbre, dans le cas d'une structure 70 contenant au maximum 5 noeuds par sous-arbre : - 71 : Sous-arbres construits après l'ajout des fils du noeud 2 ; 72 : Le noeud courant devient le noeud 3. Il y a alors suffisamment de place pour ajouter les fils du noeud 3. Mais pour respecter la contrainte que les sous arbre doivent en former un autre, un nouveau sous-arbre est créé ; 73 : Le noeud courant est le noeud 6 après avoir passé le noeud 5 sans fils. Le sous-arbre courant est celui contenant le noeud 6. Les fils du noeud 6 y sont donc ajoutés. On remarque que la création d'un nouveau sous-arbre est motivée par : Le fait qu'un sous-arbre ait atteint le nombre maximum de noeud ; Un nombre trop important de fils pour que ceux-ci soient tous ajoutés à un sous-arbre sans dépasser le nombre maximum de noeuds. Une troisième cause de création de sous-arbres est visible sur l'exemple de la figure 7. Les noeuds 2 et 3 ne sont pas situés sur les mêmes niveaux. Afin de respecter l'arborescence lors du découpage, il faut créer un nouveau sous-arbre lors de l'ajout des fils noeuds du 3. La figure 8 présente l'algorithme de découpage d'un arbre (800) en sous-arbres. Cette figure illustre les conditions suivantes de création d'un nouveau sous-arbre : le fait qu'un sous-arbre ait atteint le nombre maximum de noeud ; un nombre trop important de fils pour que ceux-ci soient tous ajoutés à un 20 sous-arbre sans dépasser le nombre maximum de noeuds. Le découpage de l'arbre 800 comprend alors les étapes suivantes : Initialisation du découpage (80) : Remplissage du premier sous-arbre 800 avec tous les fils (0 et 1) de la racine et début du processus de balayage de noeud ; 25 - ajout (81) des fils du noeud courant 0 (2 et 3) au sous-arbre 801 en cours de construction ; ajout (82) des fils du noeud courant 802 (4, 5, 6, 7) au sous-arbre en cours de construction : le noeud 1 possède 4 fils. Or le sous-arbre en cours de construction 803 est plein. Un nouveau sous arbre est créé ; 83. Le noeud courant 804 est le 2. Il ne possède aucun fils, passage au noeud 3. Ajout des fils du noeud trois au sous-arbre courant 803. Or, celui-ci est plein : construction d'un nouveau sous-arbre. 84. Le noeud courant est le 4, sans fils donc passage au noeud 5. Le noeud 5 5 possède 3 fils. Le sous-arbre courant 805 n'est pas plein, mais il possède déjà deux noeuds. Création d'un nouveau sous-arbre. Ajout (85) des fils du noeud 6 86. Les noeuds 8, 9 et 10 sont sautés car ils n'ont pas de fils. Ajout des fils du noeud 11 : le sous-arbre en cours de construction est plein, création 10 d'un nouveau sous-arbre 87. Les noeuds 14 et 15 n'ont pas de fils. La construction de la liste de sous-arbres est terminée. 5.5.3.3 Noeud de description hiérarchique ( HDescNode ) Le noeud de description hiérarchique est initialement une extension du 15 noeud FootprintSet . Un tel type de noeud est par exemple présent dans la norme MPeg4 (norme ISO/IEC JTC11SC29/WG11). Il correspond à une description hiérarchique d'un ensemble de polygones 2D. Il peut cependant être utilisé pour d'autres modèles de données supportant la progressivité. Le noeud de description hiérarchique HierarchicalDescription (nommé 20 par la suite HDescNode ), dans le cas de son utilisation avec le FootprintSet , a pour but de déterminer les bâtiments du PBTree (représenté par le FootprintSetNode ) qui doivent être affichés. Ainsi le HDescNode effectue une partie du travail du FootprintSetNode : celle de sélection du niveau de détail des bâtiments. 25 La partie de rendu des bâtiments sélectionnés continue à être effectuée par le FootprintSetNode . Au sein du graphe de scène, il y a donc une communication entre le noeud HDescNode et le noeud FootprintSetNode afin de transmettre à ce dernier la liste des bâtiments à composer. On présente, en relation avec la figure 17, le graphe de scène correspondant à l'utilisation d'un HDescNode et d'un FootprintSetNode et la relation 170 entre ces deux noeuds. Afin de sélectionner le niveau de détail des bâtiments à afficher, le 5 HDescNode utilise un PBTree simplifié : celui-ci ne contient plus la géométrie des bâtiments, mais uniquement pour chaque noeud : La sphère englobant la boîte qui contient le bâtiment 2.5D ; Les erreurs métriques ; La taille du noeud du PBTree décrit (si le mode de communication est le 10 mode pair à pair). Cette description du PBTree peut donc être transmise rapidement à travers le réseau puisqu'elle est beaucoup plus petite. En parcourant l'arbre de description du PBTree et en utilisant la notion d'aura de perceptibilité d'un bâtiment, il devient possible de naviguer en mode client/serveur dans de grands environnements 15 urbains tel que la ville de Paris. 5.5.4 Sélection des noeuds à visualiser pour la ville Dans ce mode de réalisation particulier, c'est le pair qui effectue la sélection des noeuds à visualiser. Il transmet les requêtes au pair serveur qu'il a choisi pour qu'il lui envoie les données dont il a besoin pour visualiser la structure 20 hiérarchique. Le fichier de description que l'on propose ne contient pas les informations géométriques, le client doit donc les demander au pair serveur une fois qu'il a sélectionné un noeud. Le procédé général de sélection des noeuds est décrit dans le brevet [FR-05 02 4491. Dans ce mode de réalisation, nous optimisons ce procédé. 25 Une optimisation, selon l'invention, consiste à transmettre les auras des boites englobantes des différents noeuds de l'arbre en plus de l'aura de perceptibilité et du centre de gravité. Grâce a la pyramide de vue (cône de vision) on peut connaître les noeuds visible parmi ceux qui sont perceptible (si la boite englobante est incluse dans la pyramide de vue) On présente, en relation avec la figure 9, les différents noeuds perceptibles en n'utilisant que l'aura de perceptibilité comme critère de sélection. Cette figure permet de démontrer le lien existant entre l'arbre hiérarchique, la représentation visuelle et les zones de perceptibilité ; 900: Zone de perceptibilité de l'objet ; 901 : Zone de perceptibilité du noeud; 902 :Noeud de la représentation hiérarchique ; 903 :Noeud perceptible (qui doit être développé) ; 904 :Noeud visible si l'on regarde l'objet ; - 905 : Position de l'utilisateur dans la scène. La figure 10 présente les noeuds perceptibles si l'on tient compte du point de vue de l'utilisateur et que l'on dispose des auras incluant les boites englobantes des différents noeuds. Si un noeud est perceptible et que son aura de boite englobante entre en intersection avec le point de vue, il est sélectionné. Cette figure permet de démontrer le lien existant entre l'arbre hiérarchique, la représentation visuelle et les zones de perceptibilité en tenant compte du point de vue de l'utilisateur, avec une représentation 1007 pour laquelle rien n'est perceptible ; 1000: Zone de perceptibilité de l'objet ; - 1001 : Zone de perceptibilité du noeud ; 1002 :Noeud de la représentation hiérarchique ; 1003 :Noeud perceptible (qui doit être développé) ; 1004 :Noeud visible si l'on regarde l'objet ; 1005 : Position de l'utilisateur dans la scène ; - 1006: Point de vue de l'utilisateur. On constate que le nombre de noeuds perceptibles varie si on utilise le point de vue de l'utilisateur et l'aura incluant la boite englobante du noeud. Cette information permet de limiter le nombre de noeuds géométriques qui vont être demandés au serveur. Pour permettre une légère anticipation et qu'il y ait moins de raffinements visibles dus à une latence réseau, on n'utilise pas le point de vue réel. Il est décalé en arrière de manière a pouvoir déclarer comme perceptible des noeuds qui sont en retrait ou sur les côtés du point de vue, ce qui permet une anticipation pour les mouvements de rotation ou de recul. 5.5.5 Transmission de l'arbre de description entre pairs 5.5.5.1 Protocole de communication Afin de transmettre l'arbre de description sur le réseau en mode client-serveur, un protocole applicatif reposant sur TCP/UDP-IP est défini. Il repose sur des requêtes émises par le client (description du paquet de la requête en relation avec la figure 14), et des réponses transmises par le serveur (description du paquet de réponse en relation avec la figure 15). A son démarrage, le client réclame immédiatement le sous-arbre d'index 0 au serveur en utilisant une requête HDescRPck (figure 14). Le serveur lui répond sous la forme d'un paquet HDescPck contenant le sous-arbre de description d'index O. Le client lors de son parcours du sous-arbre sera amené selon ses besoins à récupérer d'autres sous-arbres. Il les réclamera au serveur en utilisant une requête HDescRPck (figure 14). Le serveur lui répondra par un paquet 20 HDescAPck (figure 15) contenant les sous-arbres demandés. Les informations (les champs) contenues dans ces paquets sont décrites dans les paragraphes suivants. La figure 18 présente une description détaillée du contenu du paquet HDescPck . Dans le cas de la description d'un PBT, les sous-arbres sont en fait des FPHDescSubTree. L'entête (181) est donc différent de 25 l'entête du HDescSubTree (qui en fait est vide). 5.5.5.2 Principe d'encodage et compression des paquets Dans le but de transmettre plus rapidement sur le réseau l'arbre de description hiérarchique, celui-ci est encodé de manière à le compresser. 30 Les descriptions suivantes présentent cet encodage en utilisant la syntaxe SDL. Certaines parties de l'encodage sont spécifiques à la structure décrite. Ces parties spécifiques étendent en conséquence la syntaxe de base. Actuellement, une seule structure est décrite : l'arbre de description hiérarchique, il s'agit du PBTree. 5.5.5.3 Champ HierarchicalDescriptionSpecificlnfo Les paramètres de compression sont spécifiques à chaque arbre de description. Ses paramètres sont les tous premiers éléments transmis auclient. Syntaxe : class HierarchicalDescriptionDecoderConfig extends AFXDecoderSpecificlnfo { int(8) type; unsigned int(5) rootChildrenRadiusNbBits; unsigned int(5) nbChildrenNbBits; unsigned int(5) nbSubTreesNbBits; float(32) acquisitionPrecision; float(32) minMetricError; float(32) maxMetricErrorEncodingFunction; switch(type) { 0: FPHDescDecoderConfig; } } Sémantique : type spécifie le type de structure décrit par la description hiérarchique. 25 Actuellement, une seule structure est décrite : il s'agit du PBTree. Le type associé est O. rootChildrenRadiusNbBits est le nombre de bits qui sont utilisés pour encoder le rayon des fils appartenant à la racine de l'arbre de description. nbSubTreesNbBits est le nombre de bits utilisés pour encoder le 30 nombre de sous-arbres contenus dans un HDescAPck. acquisitionPrecision est la précision utilisée lors de l'encodage des deltas entre le centre de la sphère englobante d'un père et le centre de la sphère englobante des fils du noeuds. Cette valeur doit être positive est strictement supérieure à 0. minMetricError est l'erreur métrique minimum supérieure à 0 trouvée dans l'arbre de description. Cette valeur est utilisée pour décoder l'erreur métrique d'un noeud. maxMetricErrorEncodingFunction est la plus grande valeur de la 5 fonction utilisée pour encoder l'erreur métrique. La fonction de décodage est la suivante : if (encodedMetricError = 0) metricError = minMetricError else encudedMetricError - maxMetricErrorEncodingFunction 8 ù metricError = e 255 ù 1 if (metricError indexNbBits est le nombre de bits utilisés pour encoder les index des noeuds de l'arbre de description. nbNodesInSubTreeNbBits est le nombre de bits utilisés pour encoder le nombre de noeuds présents dans un sous-arbre (HDescSubTree). nbNodesOnFirstLevelOfSubTreeNbBits est le nombre de bits utilisés pour encoder le nombre de noeuds présents sur le premier niveau d'un sous-arbre. - nbSubTreesChildrenNbBits est le nombre de bits utilisés pour encoder le nombre de fils que possède un sous-arbre. nbNodesOnLastLevelNbBits est le nombre de bits utilisés pour encoder le nombre de noeuds présents sur le dernier niveau d'un sous-arbre. networkType est le type de communication réseau utilisé. Actuellement, deux types de communication sont mis en oeuvre : Type 0 : modèle client-serveur ; Type 1 : modèle pair à pair. Selon le mode de communication utilisé, des informations supplémentaires peuvent être ajoutées au flux : - nbTreeSizeNbBits est le nombre de bits utilisés pour encoder la taille d'un sous-arbre. geometryNodeSizeNbBits est le nombre de bits utilisés pour encoder la taille de la géométrie d'un noeud du PBTree. 5.5.5.5 Champ HierarchicalDescriptionAnswerPacket Syntaxe : class HierarchicalDescriptionPacket { unsigned int(HierarchicalDescriptionDecoderConfig.nbSubTreesNbBits nbSubTrees; for (i= 0; i int(FPHDescDecoderConfig.subTreeSizeNbBits) subTreeChildSize 1: 40 } } for (i= 0; i Syntaxe : class HierarchicalDescriptionNodeMessage { unsigned int(HierarchicalDescriptionDecoderConfig.nbChildrenNbBits nbChildren; if (nbChildren > 0) { unsigned int(8) encodedMetricError; } int(l) isChildOfRoot; variable temporaire non lue. if (isChildOfRoot) { float(32) gcX; float(32) gcY; float(32) gcZ; unsigned int(HierarchicalDescriptionDecoderConfig.rootChildrenRa diusNbBits) radius; } else { unsigned int(5) nbBitsDelta; int(l) isDeltaXNeg; unsigned int(nbBitsDelta) deltaX; int(l) isDeltaYNeg; unsigned int(nbBitsDelta) deltaY; int(l) isDeltaYNeg; unsigned int(nbBitsDelta) deltaZ; int(l) isDeltaRadiusNeg; unsigned int(nbBitsDelta) deltaRadius; } } Sémantique : nbChildren est le nombre de fils que possède ce noeud. encodedMetricError est la valeur encodée de l'erreur métrique pour ce noeud de description hiérarchique. Si le noeud ne possède pas de fils (i.e. c'est une feuille de l'arbre de description), son erreur métrique est nulle. Il n'est donc pas nécessaire de la transmettre. isChildOfRoot est une variable booléenne qui n'est pas lue dans le flux. Elle est utilisée pour savoir si le noeud est un fils de la racine ou non. Si le noeud est un fils de la racine, les coordonnées complètes du centre de la sphère englobante sont transmises. Sinon, elles sont déterminées en utilisant la différence entre celle du noeud à décoder et celle du noeud père. Il en est de même pour le rayon. gcX , gcY , gcZ sont les coordonnées du centre de la sphère englobante. radius est le rayon de la sphère englobante. nbBitsDelta est le nombre qu'il faut utiliser pour les lire les valeurs deltaX , deltaY , deltaZ et deltaRadius . - isDeltaNegX indique si la différence entre l'abscisse du centre de la sphère englobante du noeud père et l'abscisse du centre de la sphère englobante du noeud en cours de décodage est positive ou négative. deltaX est la valeur absolue de la différence entre l'abscisse du centre de la sphère englobante du noeud père et l'abscisse du centre de la sphère englobante du noeud en cours de décodage. Si isDeltaNegX vaut 1, deltaX doit être multiplié par -1. L'opération pour décoder l'abscisse est la suivante : if (isDeltaXNeg) deltaX = deltaX • -1 node.gcX = parentNode.gcX + HierarchilcalDescriptionDecoderConfig.acquisition Pr ecision deltaX - isDeltaYNeg , isDeltaZNeg , deltaY et deltaZ ont la même signification que isDeltaXNeg et deltaX , mais pour l'ordonnée et l'altitude. deltaRadius est la différence entre le rayon de la sphère du noeud père et le rayon du noeud en cours de décodage. L'opération pour décoder le 25 rayon du noeud courant est la suivante : radius = parentNode.radius + HierarchicalDescriptionDecoderConfig.acquisition Pr ecision deltaRadius 5.5.5.9 Champ FPDescNodeMessage Syntaxe : class FPHDescSubTree extends HierarchicalDescriptionSubTree { switch(FPHDescDecoderConfig.networkType) { 0: // pas d'information supplémentaire 1: int(8) geometryNodeSize } } Sémantique : geometryNodeSize est la taille en octet de la géométrie du noeud du PBTree décrit par le noeud de description hiérarchique. 5.5.5.10 Reconstruction de l'arbre reçu On décrit en relation avec la figure 16, une méthode de reconstruction d'un sous-arbre lors de son décodage par un pair client. Le pair client dispose d'un arbre de description 160. Il reçoit un sous arbre 161, contenant une liste de noeuds 162. Le nombre d'étapes nécessaires à la reconstruction dépend du nombre de noeuds du sous arbre reçu (dans cet exemple, il y en a sept). Pour chaque noeud de la liste de noeud 162, le pair client ajoute ce noeud à l'arbre de description en fonction du niveau du noeud dans l'arbre. 5.5.6 Sélection des pairs serveurs La sélection des pairs serveurs se fait à chaque parcours de l'arbre. Les requêtes sont transmises en fonction de l'importance des noeuds à chacun des pairs serveurs connectés (par rapport a la position du noeud dans la hiérarchie des niveaux de détail). La figure 11 présente une possibilité d'implémentation pour la répartition des requêtes entre les pairs connectés et le serveur central. Ce mode particulier de réalisation peut par exemple s'appliquer dans le cas ou le fichier de description n'est pas progressif. Le pourcentage de réalisation de la figure 11 représente le taux de requêtes non acquittées dans l'intervalle de temps imparti. Le pourcentage de réalisation doit régulièrement être remis à jour. Le pourcentage de chargement est déterminé par le pair distant et est transmis au cours d'un envoi de position. Pendant le parcours de son arbre, chaque pair détermine le pourcentage de noeuds qu'il a chargé compte tenu de sa position. Le pourcentage de chargement est maximal si toutes les données nécessaires à la visualisation compte tenu de la position courante sont contenues dans le cache du pair considéré. L'upload de chaque pair peut être fixé manuellement, dans ce cas il sera transmis dans un message d'initialisation. Il est aussi envisageable de le mesurer régulièrement. L'upload sera ajusté en fonction de l'intervalle entre chaque parcours (compte tenu que c'est un débit par seconde que l'on mesure). Le pair client charge (10) la description de la scène, puis effectue (11) le tri des noeuds de l'arbre par priorité. En cas de nouvelle position 12, le pair client récupère (13) la liste des pairs connectés au même point d'intérêt puis trie (14) cette liste en fonction de la taille, du pourcentage de chargement de réalisation, du TTS. Le pair client crée (15) ensuite la liste des noeuds à charger pour les pairs serveur ainsi que pour le serveur central. Pour chaque noeud de la liste de noeud, le pair client effectue (16) un test d'intersection du noeud considéré avec son aura de perception. S'il n'y a pas d'intersection (17), on passe au noeud suivant. S'il y a intersection (18), le pair client inspecte son cache (19) pour savoir si le noeud a déjà été chargé. Si oui (20), on passe au noeud suivant. Si non (21), il vérifie s'il est à la fin de sa liste de pair connecté (22). Si non (23) il passe les pairs considérés en revue : il effectue (24) un test d'intersection du pair serveur considéré avec son aura de perception. S'il n'y a pas d'intersection (25), on passe au pair suivant. S'il y a intersection (26), le pair client vérifie la capacité du pair serveur considéré eut égard à la taille des données à télécharger, ainsi qu'au TTS , à l'Upload . Si le pair serveur est éligible, (27), on ajoute (28) le noeud dans la liste des noeuds requis via ce pair et on passe (29) au noeud suivant. Si aucun pair (30) ne peut fournir le noeud requis, on ajoute (31) le noeud dans la liste des noeuds requis au serveur central. Lorsque cette liste de noeuds a été intégralement parcourue (32), les messages de récupération des données géométriques sont envoyées (33) aux pairs et au serveur central. 5.6 Structure des pairs La structure d'un pair client est illustrée schématiquement par la figure 12. Il comprend une mémoire 121, et une unité de traitement 120 équipée d'un microprocesseur, qui est piloté par un programme d'ordinateur (ou application) 122. L'unité de traitement 120 reçoit en entrée, via un module d'interface d'entrée réseau 123, des noeuds de constitution des arbres hiérarchiques et/ou des données de visualisation et/ou des réponses 124, que le microprocesseur traite, selon les instructions du programme 122, pour générer le sous-arbre hiérarchique et/ou effectuer le classement des pairs serveur et/ou réaliser la représentation des données et de visualisation et/ou générer de nouvelles requêtes à destination des pairs serveur 1212, qui sont transmises via un module d'interface de sortie réseau 125. La structure d'un pair serveur est illustrée schématiquement par la figure 13. Il comprend une mémoire 131, et une unité de traitement 130 équipée d'un microprocesseur, qui est piloté par un programme d'ordinateur (ou application) 132. L'unité de traitement 130 reçoit en entrée, via un module d'interface d'entrée réseau 133, des requêtes d'obtention d'arbres hiérarchiques et/ou des requêtes d'obtention de données de visualisation 134, que le microprocesseur traite, selon les instructions du programme 132, pour générer des envois de noeuds des arbres hiérarchiques et/ou des réponses et/ou des données de visualisation 136, qui sont transmises via un module d'interface de sortie réseau 135. 25 REVENDICATIONS 1. Procédé de sélection d'au moins un pair serveur pour la transmission de données de visualisation d'un contenu à destination d'au moins un pair client au sein d'un réseau de pairs, lesdites données étant organisées sous la forme de noeuds d'un arbre hiérarchique comprenant au moins un noeud parent et au moins un noeud fils, un élément visualisable étant associé à chacun desdits noeuds, caractérisé en ce qu'il comprend une phase de sélection d'au moins un desdits pairs serveur comprenant au moins une partie desdites données de visualisation et/ou au moins une partie dudit arbre hiérarchique, ladite phase de sélection tenant compte d'au moins une information représentative d'une taille de données d'au moins un desdits éléments visualisables. 2. Procédé de sélection selon la revendication 1 caractérisé en ce que ladite phase de sélection comprend une étape d'identification d'un ensemble de pairs voisins comprenant au moins une partie desdites données de visualisation et/ou au moins une partie dudit arbre hiérarchique. 3. Procédé de sélection selon la revendication 2 caractérisé en ce que ladite phase de sélection comprend les étapes suivantes : - détermination, par ledit au moins un pair client, d'un espace virtuel de navigation courant, représenté par un sous-arbre de visualisation courant dudit arbre hiérarchique ; sélection, par ledit au moins un pair client, d'au moins un pair serveur voisin présent au sein dudit espace virtuel de navigation courant, formant 25 ledit ensemble de pairs voisins ; transmission, audit pair client, par au moins un desdits pairs serveurs voisins, d'au moins un noeud de visualisation dudit sous-arbre de visualisation courant, suite à au moins une requête dudit pair client ; association d'au moins un desdits pairs serveurs voisins, dit pair serveur 30 associé, à chacun desdits noeuds dudit sous-arbre de visualisation enfonction des noeuds de visualisation contenus dans chacun desdits pairs serveur ; classement, par ledit pair client, desdits pairs associés, selon ladite taille de données desdits éléments visualisables desdits noeuds de visualisation 5 transmis, pour chacun desdits noeuds ; transmission, par lesdits pairs associés, d'au moins une donnée de visualisation desdits éléments visualisables suite à au moins une demande de transmission émise par ledit pair client, en fonction dudit classement. 4. Procédé de sélection selon la revendication 3 caractérisé en ce que ladite 10 étape de classement tient également compte d'au moins un des paramètres appartenant au groupe comprenant au moins : une quantité de bande passante disponible pour la transmission ; un temps de service ; un temps de téléchargement ; 15 - un niveau de détail dudit au moins un noeud de visualisation ; les données présentes sur lesdits pairs serveurs ; le pourcentage de chargement ; le taux d'acquittement ; la position desdits pairs serveurs. 20 5. Procédé de sélection selon l'une quelconque des revendications 2 à 4, caractérisé en ce qu'il met en oeuvre au moins un pair, dit pair de connectivité, gérant l'accès d'un pair client à un réseau de pairs, et en ce que ladite étape de détermination d'un espace virtuel de navigation courant comprend les sous-étapes suivantes : 25 - connexion dudit pair client à au moins un desdits pairs de connectivité, de façon à permettre audit pair client d'accéder audit réseau de pairs ; interrogation, par ledit pair client, d'au moins un pair dont un identifiant est fourni par au moins un desdits pairs de connectivité de façon à obtenir ledit sous-arbre de visualisation ; 30 6. Signal de données échangées entre au moins un pair serveur et au moinsun pair client, dans un procédé de sélection selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comprend au moins un champ d'information d'au moins une information représentative d'une taille de données d'au moins un desdits éléments visualisables. 7. Produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur, caractérisé en ce qu'il comprend des instructions de code de programme pour l'exécution du procédé de sélection selon l'une au moins des revendications 1 à 5, lorsqu'il est 1 0 exécuté sur un ordinateur. 8. Terminal comprenant un pair client de sélection d'au moins un pair serveur pour la transmission de données de visualisation d'un contenu au sein d'un réseau de pairs, lesdites données étant organisées sous la forme de noeuds d'un arbre hiérarchique comprenant au moins un noeud parent et 15 au moins un noeud fils, un élément visualisable étant associé à chacun desdits noeuds, caractérisé en ce qu'il comprend des moyens de sélection d'au moins un desdits pairs serveur comprenant au moins une partie desdites données de visualisation et/ou au moins une partie dudit arbre hiérarchique, ladite 20 phase de sélection tenant compte d'au moins une information représentative d'une taille de données d'au moins un desdits éléments visualisables. 9. Serveur comprenant un pair serveur pour la transmission de données de visualisation d'un contenu, à destination d'un pair client au sein d'un 25 réseau de pairs, lesdites données étant organisées sous la forme de noeuds d'un arbre hiérarchique comprenant au moins un noeud parent et au moins un noeud fils, un élément visualisable étant associé à chacun desdits noeuds, caractérisé en ce qu'il comprend des moyens de transmission, d'au moins 30 une donnée de visualisation desdits éléments visualisables suite à au moinsune demande de transmission émise par ledit pair client, en fonction d'un classement desdites données de visualisation selon une information représentative d'une taille de données d'au moins un desdits éléments visualisables.