Brevet FR2945645A1 — publié le 20101119

PROCEDE DE CODAGE D'UNE VARIABLE REPRESENTATIVE D'UNE GRANDEUR PHYSIQUE OBSERVABLE LORS DE LA MODELISATION DE LA DEFORMATION D'UN OBJET A N DIMENSIONS La présente invention se rapporte à un procédé de codage d'une variable x avec une précision A x donnée, la variable x étant représentative d'une grandeur physique observable lors de la modélisation de la déformation d'un objet à n dimensions, et plus particulièrement d'un objet en trois dimensions tel qu'un véhicule automobile en situation de choc. Elle se rapporte également à un procédé de codage d'une grille G à n dimensions ayant pour coordonnées x1, X2,...Xn_1, xn utilisant le procédé conforme à l'invention, et à un procédé de décodage associé. Dans le domaine automobile, il est classique de procéder à des simulations numériques de choc sur les véhicules automobiles par modélisation de la déformation du véhicule en trois dimensions. Les résultats des calculs de chocs sont cependant très volumineux en espace mémoire si bien qu'ils nécessitent un espace mémoire conséquent, contribuant ainsi fortement au coût du matériel informatique nécessaire pour de telles simulations, et qu'ils impliquent des délais pour accéder aux données souvent jugés trop longs pour une analyse ultérieure des ces données. L'espace mémoire des résultats est important car les calculs de chocs sont des simulations informatiques de véhicules constituées d'un grand nombre de points connectés entre eux, appelés � nœuds et éléments �, pour une représentation du véhicule sous la forme d'un maillage tridimensionnel. La méthode de calcul dite des � éléments finis � permet d'observer la déformation d'une structure ainsi qu'un grand nombre de grandeurs physiques en chaque noeud ou élément du maillage. Les déplacements, les contraintes, les forces de contact, les énergies internes, la température et la masse sont quelques grandeurs physiques observables lors de la modélisation de la déformation du véhicule formant un maillage tridimensionnel. II en résulte un nombre total de valeur à stocker correspondant environ au produit du nombre de nœuds par le nombre de grandeurs physiques et par le nombre d'instants ; la déformation du véhicule étant observée à différents instants entre le début et la fin du choc. Ce grand nombre de valeurs est écrit dans un ou plusieurs fichiers selon un certain ordre défini au préalable ; cet ordre n'influant pas l'espace mémoire. De manière classique dans les simulations de choc de véhicule automobile, une valeur est codée en utilisant la norme IEEE 32 bits qui constitue un standard pour la représentation des nombres à virgule flottante en binaire, nommée � float � pour la suite de la description ; ce standard définissant un format de représentation des nombres à virgule flottante (signe, mantisse, exposant, nombres dénormalisés) et valeurs spéciales (infinis et NaN), en même temps qu'un ensemble d'opérations sur les nombres flottants. Ce standard décrit aussi quatre modes d'arrondi et cinq exceptions (comprenant les conditions dans lesquelles une exception se produit, et ce qu'il se passe dans ce cas), avec pour le format 32 bits : 1 bit de signe, 8 bits d'exposant (-126 à 127) et 23 bits de mantisse. Avec un tel codage, l'ensemble des informations nécessaires à la détermination de l'espace mémoire (en bits et en Méga octets) peut être déterminé pour le résultat d'une simulation de chocs. Par exemple, pour une simulation composée de 500 000 noeuds (nombre de noeuds classiquement employé pour le maillage 3D d'un véhicule automobile), de sept grandeurs physiques (dont trois pour des déplacements en trois dimensions ou les coordonnées x, y, z, et quatre relatives par exemple aux efforts et contraintes) et de 50 instants, il en résulte 500 000 x 7 x 50 x 32 = 5,6.108 = 5340 x 106 bits soit 667 Mo d'espace mémoire. L'ensemble des valeurs � float � qui constitue un résultat de calcul de choc est stocké selon un certain ordre dans des fichiers. La taille fréquemment rencontrée d'un résultat dans le domaine automobile est d'environ 600Mo. L'objectif de la présente invention est de réduire l'espace des résultats de calculs, autrement dit de fournir un procédé de codage ou de � compression � qui permette de réduire l'espace mémoire qu'occupe le fichier traité sans dégrader l'information contenue par rapport au rendu visuel final de la simulation choc. Elle concerne plus particulièrement un procédé de codage d'une ou plusieurs variables x sur moins de bits que le codage IEEE 32 bits décrit ci-dessus. A cet effet, elle propose un procédé de codage d'une variable x avec une précision Ox donnée, la variable x étant représentative d'une grandeur physique observable lors de la modélisation de la déformation d'un objet en trois dimensions et ayant des valeurs comprises entre une valeur minimale min(x) et une valeur maximale max(x), ledit procédé étant caractérisé en ce qu'il consiste à déterminer un ensemble réduit A(x) de valeurs V(x, N) acceptables pour le codage de la variable x avec la précision Ax, où : - N est un entier compris entre 1 et Nmax= E[X/Ax], E désignant la fonction partie entière ; - V(x, N) = min(x) + Ax.(N ù 1) ; et - X correspond à l'étendue de l'ensemble réduit A(x) avec : X = max(A(x)) ù min(A(x)) = V(x, Nmax) ù V(x, 1) = L x.(Nmax ù 1). 10 Dans ce procédé, l'entier N peut prendre une valeur parmi Nmax possibilités. Le nombre de bits minimum NB pour coder ces Nmax possibilités est issu de l'opération NB = log(2) [Nmax]. Pour Nmax = 1000, avec par exemple X = 100 et Ax=0,1, le nombre de bits minimum NB = log(2) [1000] = 15 9,96. En prenant la valeur entière supérieure ou égale, 10 bits permettent ainsi de coder une valeur de l'ensemble réduit A(x) alors que dans le codage IEEE 32 bits actuel il en aurait fallu 32. Le procédé de codage IEEE 32 bits classique et le procédé de codage conforme à l'invention ont en commun d'utiliser 2n possibilités pour 20 désigner une valeur dans un ensemble construit. La différence entre les deux procédés réside donc essentiellement dans la façon de construire l'ensemble. La construction de l'ensemble pour la norme IEEE classique permet d'obtenir une étendue très importante au détriment d'une précision qui se dégrade à mesure que les valeurs s'écartent de zéro. Cet ensemble est très 25 bien adapté à la réalisation de calculs car l'étendue des variables intermédiaires n'est pas connue. Cet ensemble est donc volontairement surdimensionné. La construction de l'ensemble pour le procédé selon l'invention permet d'obtenir une précision constante au détriment d'une étendue qui devra 30 être au plus juste. Cet ensemble est très bien adapté à l'observation des résultats. La précision dégradée et l'étendue au stricte nécessaire permet à coup sûr de réduire le nombre de bits nécessaires par rapport à la norme IEEE classique. En résumé, le principe de ce procédé de codage est d'utiliser 35 toutes les combinaisons d'une suite de n bits soit un nombre de 2n possibilités, pour désigner une valeur dans un ensemble réduit. L'ensemble réduit est construit grâce aux faits que l'étendue des valeurs (écart max- écart min) et la précision (ou l'erreur admise) sur une valeur sont connues. Selon une caractéristique, la variable x est représentative d'une grandeur physique observable lors de la modélisation de la déformation d'un véhicule automobile en situation de choc. L'invention concerne également un procédé de codage d'un espace E(n) à n dimensions ayant pour coordonnées x1, x2,...xn_1, xn avec une précision Lx donnée, où les coordonnées x; constituent des ensembles réduits déterminés selon le procédé de codage conforme à l'invention tel que décrit ci- dessus à partir de variables représentatives de grandeurs physiques observables lors de la modélisation de la déformation d'un objet en trois dimensions, i étant un entier compris 1 et n, chaque coordonnée x; ayant des valeurs comprises entre une valeur minimale min(xi) et une valeur maximale max(x;), ledit procédé consistant à associer à chaque point de coordonnées (xi, x2,..., Xn_1, )(n) un numéro de point N(x1, x2,...xn_1, )(n) au sein d'une grille G de codage, ledit procédé comprenant les étapes suivantes - pour chaque coordonnée x;, détermination d'une coordonnée intermédiaire x'; par la relation suivante, avec 1 Le procédé de codage d'un espace E(n) conforme à l'invention comprend ainsi une première partie qui consiste à mettre en oeuvre le procédé de codage d'une variable selon l'invention aux coordonnées x1, x2,...xn-1, xn. Cette première partie présente l'avantage déjà décrit d'utiliser un codage des valeurs sur moins de bits que le codage IEEE 32 bits classique. Cette première partie permet donc de réduire l'espace mémoire à allouer pour une variable ; la question étant de savoir ce qu'il en est des espaces à n dimensions, comme par exemple les coordonnées d'un point dans un espace en trois dimensions. En effet, en appliquant la première partie du procédé et en considérant qu'une coordonnée est une variable à traiter, alors n arrondis à la valeur entière supérieure ou égale de l'opération log(2)[étendue] seront effectués pour un point. Ces n arrondis peuvent dans le pire des cas générer un surplus de quasiment n bits. Le procédé de codage d'un espace E(n) comprend ainsi une deuxième partie qui consiste à établir une grille G de points numérotés N(x1, x2,...xn-1, )(n). L'objectif de cette seconde partie du procédé est de diminuer le surplus de bits en supprimant la coordonnée de chaque dimension pour ne conserver qu'un seul numéro, c'est-à-dire dit le numéro de point N(x1, x2,...xn 1, )(n) dans la grille G. Concernant la détermination de l'étendue, les trois réalisations suivantes sont envisageables. Dans une première réalisation, la détermination de tout ou partie des étendues X; est obtenue par la relation suivante, avec 1 De façon avantageuse, le procédé comprend, lors de l'étape b) de codage de la différence entre deux nœuds successifs, une étape de réalisation des différences sur des coordonnées des nœuds traités � correctement �, le traitement � correct � consistant à soustraire le nœud de référence aux autres nœuds puis d'arrondir les coordonnées des autres nœuds à la précision Lx choisi. Selon une caractéristique, les coordonnées x; constituent des ensembles réduits déterminés à partir de variables représentatives de grandeurs physiques observables lors de la modélisation de la déformation d'un véhicule automobile en situation de choc. L'invention concerne également un procédé de décodage d'une grille G de codage obtenue selon un procédé de codage d'un espace E(n) conforme à l'invention, ladite grille G de codage étant caractérisée par des numéros de point N(x,, x2,...xn_,, )(n), ledit procédé comprenant les étapes suivantes : - calcul d'un terme intermédiaire x'n selon la relation suivante : - calcul des coordonnée intermédiaire x'i successives avec les relations 25 suivantes, avec 1 r,. s mira ( x i . ) D'autres caractéristiques et avantages de la présente invention apparaîtront à la lecture de la description détaillée ci-après d'un exemple de mise en œuvre non limitatif, avec à titre illustratif en figure 1 une représentation d'une grille de codage pour un ensemble à deux dimensions obtenue avec un procédé de codage conforme à l'invention. La présente invention porte sur un procédé de codage ou de compression des résultats de calculs numériques qui se décompose en deux parties : - une première partie qui consiste à réaliser le codage des variables ou réels 15 sur un minimum de bits, en l'occurrence sur moins de bits que le codage IEEE 32 bits classique ; et - une deuxième partie qui consiste à réaliser une diminution du surplus de bits issus de la première partie su procédé lorsque le codage est effectué sur un espace E(n) à n dimensions. 20 La description de la première partie est faite ci-après. Considérons une variable x ayant des valeurs comprises entre min(x) = -10 et max(x) = +90 sur lesquelles il est possible de négliger une variation de 0,1 ; la précision du codage étant Lx = 0,1. N'importe quelle valeur de x s'approche par l'une des valeurs de l'ensemble réduit suivant : 25 A(x)=[-10;-9,9;-9,8;... ;+89,8;+89.9;+90]. L'ensemble réduit A(x) forme le plus petit des ensembles de valeurs V(x, N) acceptables, il peut être construit par la valeur min(x) minimale de x, l'étendue X de l'ensemble réduit A(x) où X = max(A(x)) ù min(A(x)), et la 30 précision Lx=0,1 par la relation suivante : V(x, N) = min(x) + Ax.(N ù 1) où N est un entier compris entre 1 et Nmax= E[X/Ox], E ésignant la fonction partie entière. 35 Dans cet exemple, N peut prendre une valeur parmi Nmax = 1000 possibilités. Le nombre de bits minimum pour coder ces 1000 possibilités correspond à la valeur entière supérieure ou égale au résultat de l'opération log(2) [Nmax] = 9.96, autrement dit seulement 10 bits sont nécessaires pour coder une valeur V(x, N) de l'ensemble réduit A(x). Cette première partie permet donc de réduire l'espace mémoire à allouer pour une variable. Qu'en est-il des espaces E(n) à n dimensions comme les coordonnées d'un point dans un espace en trois dimensions ? En appliquant la première partie et en considérant qu'une coordonnée est une variable à traiter, alors n arrondis à la valeur entière supérieure ou égale de l'opération log(2)[étendue] seront effectués pour un point. Ces n arrondis peuvent dans le pire des cas générer un surplus de quasiment n bits. L'objectif de la seconde partie est de diminuer le surplus de bits en supprimant la coordonnée de chaque dimension pour ne conserver qu'un seul numéro N dans une grille G dite de codage. La description de la seconde partie est faite ci-après et concerne un procédé de codage d'un espace E(n) à n dimensions ayant pour coordonnées x1, x2,...xn_1, xn qui consiste en la détermination d'une grille G de points N(x1, x2,...xn_1, )(n) et plus particulièrement en une méthode de calcul du numéro de point. Soit un maillage qui désigne un espace E(n) à n dimension construit à partir des n ensembles réduits x1, x2,...xn_1, xn déterminés lors de la première partie. Dans le cas de la figure 1, le maillage de 5 par 5 a pour coordonnées x et y. Le point de coordonnées x=3 et y=2 correspond au point numéro N=14 sur la grille G de codage obtenue lors de la deuxième partie du procédé, de sorte que ce numéro de point N=14 code pour le point de coordonnées (x=3 ; y=2). Les formules suivantes permettent pour cet exemple de calculer : - le numéro de point N(x, y) à partir des coordonnées (x, y) du point, on parle alors de codage des coordonnées ; ou bien - les coordonnées (x, y) d'un point à partir du numéro de point N(x, y) de la grille G, on parle alors de décodage de la grille G. L'étendue X est calculée selon la relation suivante : X = max(x) û min(x) + 1 =4û0+1 =5 Les relations entre les coordonnées (x, y) et le numéro N(x, y) sont les suivantes : y = E [(N-1)/X] =t û =.Xû , et y,X�x -:1. Ainsi, pour le point de coordonnées (x=3 ; y=2), on obtient bien le numéro de point N=2x5+3+1=14, et inversement pour le numéro de point N=14 on retrouve bien y=E [(14-1)/5]=E [2,6]=2 et x=14-2x5-1=3. Dans le cas général, soit un maillage qui désigne un espace E(n) à 10 n dimension construit à partir des n ensembles réduits x1, x2,..., xn 1, xn déterminés lors de la première partie, ledit maillage formant ainsi une grille de n dimensions ayant pour coordonnées successives x1, x2,..., )41, xn et pour précision A x. Le procédé de codage de la seconde partie consiste à associer à 15 chaque point de coordonnées (xi, x2,..., xn_1, )(n) un numéro de point N(x1, x2,...xn-1, )(n) au sein de la grille G de codage, et comprend les étapes suivantes pour calculer les numéros de point N : - pour chaque coordonnée x;, détermination d'une coordonnée intermédiaire x'; par la relation suivante, avec 1 = ?,.. As } mira Is.xi). Concernant la méthode de détermination de la précision : la précision n'est pas une grandeur calculable car elle relève du niveau de perception des utilisateurs. Pour chacune des grandeurs physiques observées il existe une valeur en dessous de laquelle l'utilisateur ne perçoit pas de différence pour son interprétation. La précision est donc obtenue par un accord commun des utilisateurs pour chacune des grandeurs physiques. Concernant la méthode de détermination de l'étendue : il existe trois méthodes pour connaitre l'étendue . Selon la méthode employée le gain en mémoire peut fortement varié. L'étendue est une grandeur qui peut être fixée pour toujours ou déterminée a posteriori. Dans un premier mode de réalisation de détermination de l'étendue, l'étendue est fixée en fonction de la taille de la structure. En effet, s'il est envisageable d'attribuer une taille maximale pour les structures modélisées d'un domaine, alors l'étendue pourra être fixée pour toujours dans ce domaine. Ceci peut aussi s'appliquer aux grandeurs physiques comme par exemple les températures pour qui l'étendue est assez restreinte. Dans un second mode de réalisation de détermination de l'étendue, l'étendue est fixée en fonction de la taille d'un élément fini. En choisissant un noeud de référence codé de façon classique avec trois � float �, il est possible de coder les coordonnées de tous les noeuds du modèle en ne codant que la différence entre deux noeuds successif et en fixant un ordre de parcours des noeuds. Cet ordre de parcours des noeuds est issu de la connectivité des éléments finis, tel que les distances des noeuds successifs soient minimales. De plus l'homogénéité de la taille des éléments finis est un critère de qualité de maillage qui permet d'affirmer qu'une grande part de l'ordre de 95% des éléments ont une taille inférieure à une distance � dmax �. L'étendue est ici fixée à la valeur de � dmax �. Pour la minorité d'éléments de taille supérieure à � dmax �, il est nécessaire de coder sur un peu plus de bits et donc de préparer une zone de stockage spécifique dans laquelle pourra également contenir le noeud de référence. Dans ce codage dit � de la différence entre deux noeuds successifs �, il faut faire attention de ne pas cumuler les erreurs d'arrondis au risque d'avoir une erreur rapidement significative sur le nième noeuds. Pour cela, la Demanderesse recommande de réaliser les différences sur des coordonnées des noeuds traités "correctement" ; le traitement "correct" consistant à soustraire le noeud de référence aux autres noeuds puis d'arrondir les coordonnées des autres noeuds à la précision choisi. Dans un troisième mode de réalisation de détermination de l'étendue, l'étendue est déterminée à posteriori. En post-traitant les résultats stockés selon par exemple la norme IEEE, il est possible de connaître la valeur maximale et minimale d'un résultat pour déterminer l'étendue. En sophistiquant, il est aussi possible de diminuer l'étendue en déterminant le plus petit parallélépipède circonscrit aux points d'un modèle éléments finis. Les directions du parallélépipède correspondent aux directions principales de la matrice d'inertie des points. L'étendue déterminée a posteriori présente l'inconvénient d'un stockage intermédiaire selon la norme IEEE. La description ci-dessous concerne l'application du procédé de codage selon l'invention à un modèle représentatif d'un véhicule automobile en trois dimensions employé pour une simulation de choc. Pour cela, est choisie une grille cubique de coté 41,6m et d'une précision de 0,1 mm qui permet de contenir des véhiucles automobiles avec une précision satisfaisante. Le choix de prendre une taille de grille aussi importante vient du fait qu'en choc, le véhicule tourne sur ses axes, se déplace mais surtout qu'il existe des chocs entre deux véhicules. Dans ce mode de réalisation, l'étendue X; est déterminée selon la relation X; = max(x';) + 1 où 1 Le deuxième tableau suivant détaille le calcul du nombre d'octets nécessaire et du rapport de compression sur les grandeurs énumérés ci-dessus : ,z. e ts >:inntn)d P stIque Èt~S ..~--i. .ndk.. 4 . 2 y.'_@i.a t{? Z ^ i"'.@ 25 û? X2'5 .m 0 1 0.1 0.1 y~y 3 f,MR k- z.> k~st3. sz ~ _~ 250 250 1562510 0 k+.Zk. es Es.. dl k ts .'f 7.97 7.97 23.90 #fit :?i-.'E+c rs 8 24,00 B 8 oc,ets I I 4':~?;?&?i~r i~4iess (.t s?Ct �ri ?r:3 ? fict t ) II est à noter que la seconde partie du procédé de codage selon l'invention ne permet ici pas de gain supplémentaire. 10 Sur les autres grandeurs physiques les gains sont les mêmes que précédemment. A l'issue de la première partie du procédé, le rapport de compression obtenu sur les fichiers animations est de 10/24 = 2.4 soit un gain de 60%. 15 Bien entendu l'exemple de mise en œuvre évoqué ci-dessus ne présente aucun caractère limitatif et d'autres détails et améliorations peuvent être apportés aux procédés de codage selon l'invention, sans pour autant sortir du cadre de l'invention. REVENDICATIONS1. Procédé de codage d'une variable x avec une précision Ax donnée, la variable x étant représentative d'une grandeur physique observable lors de la modélisation de la déformation d'un objet en trois dimensions et ayant des valeurs comprises entre une valeur minimale min(x) et une valeur maximale max(x), ledit procédé étant caractérisé en ce qu'il consiste à déterminer un ensemble réduit A(x) de valeurs V(x, N) acceptables pour le codage de la variable x avec la précision Ox, où : - N est un entier compris entre 1 et Nmax= E[X/Ax], E désignant la fonction partie entière ; - V(x, N) = min(x) + Ox.(N ù 1) ; et - X correspond à l'étendue de l'ensemble réduit A(x) avec : X = max(A(x)) ù min(A(x)) = V(x, Nmax) ù V(x, 1) = Ox.(Nmax ù 1). 15 2. Procédé de codage selon la revendication 1, dans lequel la variable x est représentative d'une grandeur physique observable lors de la modélisation de la déformation d'un véhicule automobile en situation de choc. 20 3. Procédé de codage d'un espace E(n) à n dimensions ayant pour coordonnées x1, x2,...xn_1, xn avec une précision Ox donnée, où les coordonnées x; constituent des ensembles réduits déterminés selon le procédé de codage conforme à la revendication 1 ou 2 à partir de variables 25 représentatives de grandeurs physiques observables lors de la modélisation de la déformation d'un objet en trois dimensions, i étant un entier compris 1 et n, chaque coordonnée x; ayant des valeurs comprises entre une valeur minimale min(x;) et une valeur maximale max(x;), ledit procédé consistant à associer à chaque point de coordonnées (xi, 30 x2,..., Xn_1, )(n) un numéro de point N(x1, x2,...xn_1, )(n) au sein d'une grille G de codage, ledit procédé comprenant les étapes suivantes : - pour chaque coordonnée x;, détermination d'une coordonnée intermédiaire x'; par la relation suivante, avec 1 4. Procédé de codage selon la revendication 3, dans lequel la détermination de tout ou partie des étendues X; est obtenue par la relation 10 suivante, avec 1 5. Procédé de codage selon la revendication 3, dans lequel tout ou partie des étendues X; correspond à une grandeur fixe. 15 6. Procédé de codage selon la revendication 3, dans lequel la détermination de tout ou partie des étendues X; est obtenue de la façon suivante : a) choisir un nœud de référence codé de la grille avec trois valeurs ; 20 b) coder les coordonnées de tous les nœuds du modèle de grille en ne codant que la différence entre deux nœuds successif et en fixant un ordre de parcours des nœuds, cet ordre de parcours des nœuds étant issu de la connectivité des éléments finis, tel que les distances des nœuds successifs soient minimales ; 25 c) fixation de l'étendue à une distance dmax choisie de sorte qu'une partie des éléments finis de la grille a une taille inférieure à cette distance dmax. 7. Procédé de codage selon la revendication 6, comprenant, lors de l'étape b) de codage de la différence entre deux nœuds successifs, une 30 étape de réalisation des différences sur des coordonnées des nœuds traités � correctement �, le traitement � correct � consistant à soustraire le noeud de référence aux autres nœuds puis d'arrondir les coordonnées des autres noeuds à la précision Lx choisi. 8. Procédé de codage selon l'une quelconque des revendications 3 à 7, dans lequel les coordonnées x; constituent des ensembles réduits déterminés à partir de variables représentatives de grandeurs physiques observables lors de la modélisation de la déformation d'un véhicule automobile en situation de choc. 9. Procédé de décodage d'une grille G de codage obtenue selon un procédé de codage d'un espace E(n) conforme à l'une quelconque des revendications 3 à 8, ladite grille G de codage étant caractérisée par des numéros de point N(x,, x2,...xn_,, )(n), ledit procédé comprenant les étapes suivantes : - calcul d'un terme intermédiaire x'n selon la relation suivante : ù l- x'. =E - calcul des coordonnée x; à partir des coordonnée intermédiaire x'; par la relation suivante, avec 1