FR 2788361 A1 20000713 FR 9900304 A 19990111 Procédé de simplification d'un maillage source, tenant compte de la courbure locale et de la dynamique géométrique locale, et applications correspondantes. I. Domaine de l'invention et applications 1.1 Domaine de l'invention Le domaine de l'invention est celui du codage de structures de données géométriques, ou maillages, notamment de grande taille. Plus précisément, l'invention concerne la représentation et le codage d'objets ou de scènes en trois dimensions. Plus précisément encore, l'invention concerne une technique d'approximation d'un maillage source en trois dimensions pouvant être utilisée seul, ou en combinaison avec d'autres techniques connues. Dans ce dernier cas, le procédé de l'invention peut constituer une étape avantageuse d'initialisation. Un maillage est classiquement défini par un ensemble de sommets et de faces orientées définissant une topologie. De tels maillages sont par exemple utilisés en graphisme sur ordinateur, pour modéliser des objets en trois dimensions avec une complexité géométrique limitée. L'approximation d'un maillage M consiste à trouver un maillage M' dont la complexité géométrique est moindre que celle du maillage M, et qui approche au mieux la géométrie de M. 1.2 Exemples d'applications L'invention trouve des applications dans tous les domaines o il est souhaitable de réduire le nombre d'informations nécessaires pour représenter et/ou manipuler efficacement un objet en trois dimensions ou un ensemble d'objets, par exemple pour l'analyser, le stocker et/ou le transmettre et/ou en assurer le rendu. A titre indicatif, l'invention peut notamment s'appliquer au domaine de la réalité virtuelle (visites ou boutiques virtuelles, loisirs, télémanipulation, etc...). Dans ce type d'application, l'approximation de maillages permet de réduire le coût de rendu de scènes complexes, en particulier en définissant la notion d'échelonnabilité sur les maillages (fonction du point de vue, des capacités graphiques, du taux de rafraîchissement souhaité,...). Dans le cas de la réalité virtuelle distribuée ou partagée, cela permet également d'adapter la complexité d'une scène aux capacités de rendu et de stockage des différents terminaux, ainsi qu'aux débits des réseaux; la simulation scientifique (éléments finis, CAO, etc. ). La réduction de la complexité géométrique des modèles permet une accélération des temps de calcul, une prise de décisions plus rapide, notamment lors de la conception en CAO, et l'élimination des informations redondantes dans une base de données 3D; la modélisation (scanner 3D (reconstruction de surfaces à partir de points non organisés), scanners volumiques, reconstruction de surfaces à partir de photos stéréoscopiques ou de séquences vidéo, de modèles numériques de terrains (imagerie satellite ou radar), etc...). Un modèle numérique de terrain permet ainsi l'obtention d'un maillage représentant la topologie d'une région. Un tel maillage est obtenu par l'échantillonnage régulier d'une image stockant l'information d'altitude en chaque point. Il en résulte une quantité de données importante, comprenant des informations inutiles pour la simulation scientifique, ou trop coûteuse pour le rendu (dans le cas de simulateurs). L'approximation de maillages..DTD: 3 2788361 réduit la quantité de données, tout en garantissant une bonne fidélité géométrique aux données initiales et la conservation de la topologie. 2. Art antérieur 2.1 Les familles d'algorithmes Plusieurs techniques d'approximation de maillages sont déjà connues. Les plus répandues peuvent être classées en trois grandes familles d'algorithmes selon qu'elles fonctionnent par: décimation; ré-échantillonnage sous-critique; subdivision adaptative. 2.1.1 décimation La décimation consiste à retirer de manière itérative des sommets et/ou des faces d'un maillage. Cette opération est appelée opération élémentaire de simplification. Les méthodes mettant en oeuvre ce principe de décimation peuvent également optimiser les positions des sommets après ou pendant la simplification, cette dernière étant choisie de manière à préserver au mieux la topologie du maillage. 2.1.2 ré-échantillonnage sous-critique Le ré- échantillonnage consiste à échantillonner un modèle original, soit en prenant des points aléatoirement sur sa surface et en retriangulant ensuite soit en définissant une grille tridimensionnelle et en agglomérant les sommets dans chaque boîte élémentaire de la grille. Le modèle ainsi généré est simplifié, et doit approximer au mieux les données initiales. Cette technique est rapide, mais ne conserve pas la topologie ni les caractéristiques visuellement importantes des maillages. 2.1.3 subdivision adaptative La subdivision adaptative commence avec un modèle comportant une géométrie très simple, que l'on subdivise récursivement ensuite, en ajoutant à chaque itération un détail dans les régions ou l'erreur d'approximation est maximale. 2.1.4 combinaisons d'algorithmes De façon à permettre une approximation d'un maillage avec une qualité de reconstruction satisfaisante, il est nécessaire de combiner une décimation et une optimisation des positions des sommets conservés. En d'autres termes, l'objectif de base d'un procédé de codage d'un maillage source étant de maximiser la qualité de l'approximation pour une complexité géométrique donnée, celui- ci doit notamment présenter les propriétés suivantes: - décimation; - préservation de la topologie; optimisation des positions, suivant un critère d'erreur prédéfini. On connaît ainsi une première méthode appelée " remaillage ", répondant à ces critères. Elle est notamment présentée dans le document " re-tiling polygonal surfaces " par Greg TURK (SIGGRAPH 92 Conference proceedings, p. 55-64, 92). Elle fonctionne par échantillonnage, décimation et optimisation des positions. Une autre technique connue, appelée " codages progressifs de maillages ", a été développée par Hugues HOPPE, dans le document " Progressive meshes " (SIGGRAPH 96 Conference proceedings, p. 99-108, 1996). Elle repose sur la décimation et l'optimisation des points. Encore une autre technique est décrite dans la demande de brevet FR-98 13090 déposée le 15/10/98, et non encore publiée. 3. Objectifs de l'invention L'invention concerne plus particulièrement la technique de décimation, mise en oeuvre, par exemple par ces différentes techniques. L'invention a notamment pour objectif de pallier les différents inconvénients des techniques connues. Ensuite, un objectif de l'invention est de fournir un procédé de simplification de maillage par décimation (fusion d'arêtes), qui soit plus efficace, en termes de qualité perceptuelle, que les techniques connues. En d'autres termes, un objectif de l'invention est de fournir un tel procédé présentant, jusqu'à un niveau élevé de décimation, une conservation des singularités des maillages, et une préservation de la topologie. L'invention a également pour objectif de fournir un tel procédé, qui soit simple à mettre en oeuvre, en termes de calculs à effectuer, et qui présente une bonne vitesse d'exécution. Selon un premier aspect de l'invention, un autre objectif est de fournir un tel procédé, qui puisse être utilisé seul, afin de fournir une méthode rapide de simplification de maillages. Selon un second aspect de l'invention, un objectif est de fournir un tel procédé de décimation, qui puisse être utilisé, de façon à l'améliorer, dans un procédé d'optimisation géométrique de maillage. 4. Caractéristiques principales de l'invention Ces objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints à l'aide d'un procédé de simplification d'un maillage source M formé d'une pluralité de surfaces définies par des sommets, des faces et des orientations sur ces dernières, ledit procédé mettant en oeuvre une étape de décimation par fusion d'arête, consistant à associer à une arête à décimer, définie par deux sommets, un sommet unique, de façon à obtenir un maillage simplifié M', et comprenant une étape de sélection d'une fusion d'arête à effectuer, parmi toutes les fusions d'arête possibles, tenant compte: - d'au moins une information représentative de la courbure définie localement autour de l'arête considérée; - d'au moins une information représentative de la dynamique géométrique définie localement. La prise en compte de ces deux critères permet, comme on le verra par la suite, d'optimiser le choix des fusions à effectuer, en supprimant en priorité les éléments les moins significatifs perceptuellement. De façon préférentielle, ladite étape de sélection met en oeuvre une queue de priorité des arêtes à fusionner, en fonction d'un critère prioritaire, ladite information représentative de la courbure, puis d'un critère secondaire, ladite information représentative de la dynamique géométrique. Cette hiérarchie de critères permet d'atteindre une bonne efficacité. Avantageusement, ladite étape de sélection gère un seuil de courbure, seules les arêtes ayant une courbure inférieure audit seuil étant considérées pour l'application dudit critère secondaire, ledit seuil étant augmenté lorsqu'aucune arête ne présente plus une courbure inférieure à ce dernier. Selon différents modes de réalisation particuliers, ladite information représentative de la dynamique géométrique peut appartenir au groupe comprenant: - longueur de l'arête considérée; - une moyenne des surfaces des faces avoisinant ladite arête considérée; - une moyenne des longueurs des arêtes adjacentes aux sommets formant ladite arête considérée; - une combinaison de longueurs d'arêtes et/ou de surfaces de faces; - toute autre grandeur caractéristique reliée à la densité locale. Comme on le verra par la suite, la prise en compte de la longueur de l'arête est une technique simple, et fournissant de très bons résultats. La décimation peut notamment être interrompue en fonction d'un des critères appartenant au groupe comprenant: - un taux de compression atteint; - une complexité géométrique atteinte, exprimée par un nombre de sommets ou de faces; - un seuil de courbure atteint. De façon avantageuse, le procédé de l'invention comprend également une étape de pseudo-optimisation, après ladite étape de décimation par fusion d'une arêtes, assurant le positionnement du sommet résultant de ladite fusion de manière à réduire la déviation géométrique entre ledit maillage source M et ledit maillage simplifié M. Ladite étape de pseudo-optimisation peut avantageusement consister à dénombrer les arêtes vives autour des deux sommets formant l'arête à fusionner, et à distinguer les deux cas suivants: - si les nombres d'arêtes vives sont les mêmes autour des deux sommets, on place le sommet résultant de la fusion au milieu du segment reliant lesdits sommets; 8 2788361 si les nombres d'arêtes vives sont différents, on place le sommet résultant de la fusion sur le sommet présentant le plus grand nombre d'arêtes vives. Selon un premier mode de mise en oeuvre de l'invention, le procédé de simplification d'un maillage source constitue une étape d'initialisation d'un procédé d'optimisation géométrique d'un maillage. L'invention concerne également un tel procédé d'optimisation géométrique d'un maillage source, comprenant une étape d'initialisation mettant en oeuvre le procédé de simplification décrit ci-dessus. Selon un second mode de mise en oeuvre de l'invention, le procédé de simplification d'un maillage source peut être utilisé seul. 5. 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 illustre le principe d'une fusion d'arête; - la figure 2 illustre le principe de la queue de priorité combinant la courbure et la dynamique géométrique définies localement, selon l'invention; - la figure 3 illustre le dénombrage des arêtes vives autour d'un sommet du maillage; - la figure 4 présente le principe de la pseudo optimisation entre fusion d'arêtes, selon l'invention. 6. Description d'un mode de réalisation de l'invention 6.1. Simplification géométrique 9 2788361 Ainsi qu'indiqué précédemment, l'invention concerne notamment une nouvelle technique de simplification d'un maillage 3D, reposant sur la mise en oeuvre d'une queue de priorité combinant la courbure locale et la dynamique géométrique locale. Cette technique présente notamment l'avantage de conserver jusqu'à un niveau élevé de décimation, les singularités sur les maillages. Elle possède de plus une vitesse d'exécution intéressante. Selon l'invention, on construit une queue de priorité gérant l'opérateur topologique de fusion d'arêtes. Cette queue de priorité combine les critères de courbure locale et de dynamique géométrique locale, afin d'exploiter au mieux le degré de liberté donné par l'ordre des transformations à réaliser sur le maillage. La simplification d'un maillage M consiste à construire un maillage M' de complexité géométrique réduite, qui conserve une faible déviation géométrique avec M. L'algorithme de simplification géométrique doit permettre de spécifier une résolution géométrique au sommet prêt. Pour cela, on choisi un opérateur topologique élémentaire de simplification présentant de bonnes propriétés: conservation de la topologie dans une certaine mesure de décimation, et absence de création de trous sur les surfaces, et conservation des orientations. Cet opérateur topologique élémentaire est la fusion d'arêtes, tel que défini par exemple par HOPPE (document déjà cité) qui est illustré en figure 1. La fusion d'arêtes 10 consiste à fusionner les deux sommets adjacents 11 et 12 en un sommet 13, à supprimer les deux faces 14 et 15 et 2788361 à positionner le sommet 13 résultant de la fusion. On notera que cette transformation est réversible (possibilité d'insertion 16 d'un sommet). Chaque transformation élémentaire décime le maillage approximant M'. La qualité de l'approximation se dégrade donc au cours de la décimation, ou reste au mieux invariante. Afin de limiter les dégradations apportées au maillage, on souhaite bien sûr effectuer tout d'abord les transformations affectant le moins possible le modèle. Pour cela, on définit une queue de priorité contenant toutes les transformations réalisables sur le maillage (soit approximativement le nombre d'arêtes). Durant la décimation, la transformation de moindre coût de la queue de priorité est réalisée, puis supprimée de la queue. Le coût dans le voisinage modifié par l'opération précédente est alors recalculé, et les nouvelles transformations potentielles sur le maillage sont insérées dans la queue de priorité, après en avoir calculé le coût. Les singularités géométriques, qui sont des parties très informatives, doivent être conservées le plus longtemps possible pendant la décimation. En particulier, les régions de forte courbure apparaissent comme très informatives. En conséquence, le premier critère de tri sur les transformations élémentaires est donc lié à la courbure locale autour de l'arête à fusionner. On appelle courbure C(Xi) autour d'un sommet Xi l'angle maximal entre les normales à deux faces adjacentes autour du sommet Xi. On appelle ensuite courbure autour d'une arête (repérée par deux sommets Xi et Xj) la moyenne de ces critères évaluée en chaque sommet. Un second critère basé sur la longueur de l'arête à fusionner, permettant de réduire la densité géométrique du maillage et d'obtenir un bon rapport d'aspect sur les triangles résultants, est mis en oeuvre. On peut également utiliser une formule usuelle représentative de la compacité. Cependant, la longueur de l'arête à fusionner présente les avantages: - de fournir un maillage de densité uniforme dans les régions de courbure voisine; - de conserver une bonne compacité des triangles, puisque ce critère tend à créer des triangles équilatéraux; - de présenter un faible coût de calcul. En d'autres termes, la queue de priorité selon l'invention repose simultanément sur la prise en compte des deux aspects suivants: - un petit triangle n'est intéressant que dans une région hautement informative (soit une région de forte courbure); - il est souhaitable de réduire la densité d'un maillage afin d'en réduire sa complexité. Les deux critères pris en compte selon l'invention sont combinés de manière à obtenir le comportement illustré par la figure 2. Cette figure est une échelle de la courbure, graduée de 0 à 7, en radians. Sur les régions de faible courbure 21, inférieures au premier seuil 22, la densité est réduite, et la compacité obtenue est raisonnable, puisque les arêtes de longueur minimale sont fusionnées. Le seuil définissant une faible courbure est ensuite augmenté (23), lorsqu 'il n'y a plus de transformation possible sur le segment de faible courbure 21. Ainsi, sur les niveaux de décimation les plus faibles, la contrainte de courbure est automatiquement relâchée, afin d'atteindre la complexité géométrique fixée. La queue de priorité possède donc deux niveaux de contrainte, organisés suivant une hiérarchie: la courbure en est le critère prioritaire, et la densité en est le critère secondaire. 6.2 Pseudo-optimisation Après une opération de fusion d'arêtes, on s'autorise à placer le sommet résultant de la fusion sur la position de l'optimum probable. Pour cela, on introduit la notion d'arête vive: une arête est vive lorsque l'angle formé par les normales aux deux faces adjacentes est supérieur à un seuil fixé paramétrable. On dénombre ensuite le nombre d'arêtes vives autour des sommets de l'arête à fusionner, ainsi que cela est illustré en figure 3. Le sommet 31 n'est associé à aucune arête vive, le sommet 32 à deux arêtes vives et le sommet 33 à trois arêtes vives. On déduit de ce dénombrement deux cas pour l'initialisation, ainsi que cela est illustré en figure 4: - si les nombres d'arêtes vives autour de Xaet autour de Xbsont identiques, on effectue l'initialisation au milieu du segment formant l'arête à fusionner. Sur les zones planes de faible courbure, cela permet de conserver une bonne compacité sur les triangles voisins. Sur une arête vive régulière (nombres d'arêtes vives égaux à 2), cela permet de positionner le sommet proche de l'arête vive qui sera conservé au cours de l'optimisation; - si les nombres d'arêtes vives autour de Xaet autour Xbsont différents, l'initialisation est effectuée sur le sommet présentant le plus grand nombre d'arêtes vives. Dans les cas les plus courants, l'optimum est atteint à partir de cette position initiale. Dans l'exemple de la figure 4, dans lequel le maillage source correspond à un parallélépipède 41, on constate que cette heuristique place le sommet: - sur le coin du parallélépipède lorsque l'arête à fusionner forme un coin 43; - et sur l'arête vive régulière du parallélépipède lorsque l'arête commence sur la région plane et se termine sur l'arête vive 45. Les situations o le nombre d'arêtes vives est le même autour des deux sommets sont illustrés en 42 et 44. 6.3 Applications Comme indiqué précédemment, la technique de simplification de l'invention (avec ou sans la pseudo optimisation) peut être mise en oeuvre seule, pour offrir une technique d'approximation de maillage, ou comme une étape d'initialisation d'une procédure plus complète d'optimisation géométrique, telle que par exemple celle décrite dans la demande de brevet FR-98 13090, déjà citée. REVENDICATIONS 1. Procédé de simplification d'un maillage source M formé d'une pluralité de surfaces définies par des sommets, des faces et des orientations sur ces dernières, ledit procédé mettant en oeuvre une étape de décimation par fusion d'arête, consistant à associer à une arête à décimer, définie par deux sommets ( 1, 12), un sommet unique (13), de façon à obtenir un maillage simplifié M', caractérisé en ce qu'il comprend une étape de sélection d'une fusion d'arête à effectuer, parmi toutes les fusions d'arête possibles, tenant compte: - d'au moins une information représentative de la courbure définie localement autour de l'arête considérée; - d'au moins une information représentative de la dynamique géométrique définie localement. 2. Procédé de simplification d'un maillage source selon la revendication 1, caractérisé en ce que ladite étape de sélection met en oeuvre une queue de priorité des arêtes à fusionner, en fonction d'un critère prioritaire, ladite information représentative de la courbure, puis d'un critère secondaire, ladite information représentative de la dynamique géométrique. 3. Procédé de simplification d'un maillage source selon la revendication 2, caractérisé en ce que ladite étape de sélection gère un seuil de courbure, seules les arêtes ayant une courbure inférieure audit seuil étant considérées pour l'application dudit critère secondaire, ledit seuil étant augmenté lorsqu'aucune arête ne présente plus une courbure inférieure à ce dernier. 4. Procédé de simplification d'un maillage source selon l'une quelconque des revendications I à 3, caractérisé en ce que ladite information représentative de la dynamique géométrique appartient au groupe comprenant: 2788361 - longueur de l'arête considérée - une moyenne des surfaces des faces avoisinant ladite arête considérée; - une moyenne des longueurs des arêtes adjacentes aux sommets formant ladite arête considérée; - une combinaison de longueurs d'arêtes et/ou de surfaces de faces. 5. Procédé de simplification d'un maillage source selon l'une quelconque des revendications I à 4, caractérisé en ce que la décimation est interrompue en fonction d'un des critères appartenant au groupe comprenant: - un taux de compression atteint; - une complexité géométrique atteinte, exprimée par un nombre de sommets ou de faces; un seuil de courbure atteint. 6. Procédé de simplification d'un maillage source selon l'une quelconque des revendications I à 5, caractérisé en ce qu'il comprend une étape de pseudo- optimisation après ladite étape de décimation par fusion d'une arêtes, positionnant le sommet résultant de ladite fusion de manière à réduire la déviation géométrique entre ledit maillage source M et ledit maillage simplifié M'. 7. Procédé de simplification d'un maillage source selon la revendication 6, caractérisé en ce que ladite étape de pseudo- optimisation consiste à dénombrer les arêtes vives autour des deux sommets formant l'arête à fusionner, et à distinguer les deux cas suivants - si les nombres d'arêtes vives sont les mêmes autour des deux sommets, on place le sommet résultant de la fusion au milieu du segment reliant lesdits sommets (42, 44); - si les nombres d'arêtes vives sont différents, on place le sommet résultant de la fusion sur le sommet présentant le plus grand nombre d'arêtes vives (43, 45). 8. Procédé de simplification d'un maillage source selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'il constitue une étape d'initialisation d'un procédé d'optimisation géométrique d'un maillage. 9. Procédé d'optimisation géométrique d'un maillage source, caractérisé en ce qu'il comprend une étape d'initialisation mettant en oeuvre le procédé de simplification de l'une quelconque des revendications 1 à 7.