Champ distance d'un solide paramétrique

Ce mémoire présente une méthode novatrice de calcul du champ distance d'un solide paramétrique. Bien que de nombreux travaux aient déjà été préalablement réalisés sur le champ distance d'une géométrie polygonale, aucune solution n'avait encore été apportée pour obtenir celui d'une géométrie paramétrique. Le champ distance est un ensemble compact et fermé d'un espace euclidien, pour lequel est dénie en tout point la distance euclidienne minimale permettant de rejoindre la surface d'un solide. Le champ distance est calculé numériquement en résolvant une équation de transport basée sur l'équation Eikonal. L'équation Eikonal est une équation aux dérivées partielles du premier ordre, dites d'Hamilton-Jacobi. La résolution de l'équation Eikonal est un problème hyperbolique et non linéaire. Notre méthode repose sur le transport de conditions limites qui dépendent de la géométrie. L'information se propage le long des courbes caractéristiques à partir des conditions limites. Le caractère non linéaire du problème conduit à la formation de chocs, selon la loi de conservation hyperbolique. Nous avons utilisé une méthode de balayage, appelée Fast-Sweeping, pour résoudre l'équation Eikonal. Cette méthode consiste à discrétiser l'espace autour du solide à l'aide d'une grille cartésienne, puis à propager les conditions frontières en résolvant numériquement l'équation Eikonal selon un schéma de Godunov. La méthode de résolution peut être subdivisée en deux étapes. Dans un premier temps, il est nécessaire d'initialiser les conditions frontières. Dans un deuxième temps, l'équation Eikonal est résolue en utilisant plusieurs balayages alternés de Gauss-Seidel L'initialisation des conditions frontières est l'étape la plus importante et aussi la plus dicile à mettre en oeuvre lors du calcul du champ distance d'un solide. Les conditions limites sont constituées des noeuds limitrophes à la géométrie. Nous avons donc dû développer un algorithme permettant de détecter et d'initialiser précisément les noeuds frontières. Ces noeuds sont initialisés avec la valeur de la plus courte distance euclidienne permettant de rejoindre le solide. Cette distance minimale est obtenue en mesurant la longueur entre le noeud et sa projection sur la surface du solide.

Abstract

In this thesis we propose a novel method for computing the distance field of parametric shapes. Although many works related to distance field of polygonal geometries have been published, no solution has still been brought to obtain the distance field of parametric geometries. Distance fields are defined as spatial fields of scalar distances to a surface geometry. At each point within the field, we know the distance from that point to the closest point on any object within the domain. In addition to distance, other properties may be derived from the distance field, such as the direction to the surface. When the distance field is signed, we may also determine if the point is internal or external to objects within the domain. There is no closed form analytical formulas for computing the distance field of a manifold. Numerical methods are then necessary for computing the distance eld of such complex shapes. We use a front propagation method using the Eikonal equation to propagate the parametric surfaces. We use an iterative algorithm, called the Fast Sweeping method, for computing the numerical solution for Eikonal equation on a rectangular grid. The main idea of this method is to use a nonlinear Godunov upwind difference scheme to discretize the partial differental equation, and Gauss-Seidel iterations. Information propagates along characteristics from the boundary. Due to the nonlinearity of the propagation problem, characteristics may intersect like the formation of shocks in a hyperbolic conservation law. Boundary conditions are defined as the set of the closest grid nodes from the parametric surfaces. The initialisation of boundary conditions is the most difficult and the upmost critical step. Indeed we present a novel method for detecting boundary nodes on a rectangular grid using grid properties and projection criterias. We also present a new algorithm for the projection of points on rational Bezier surfaces using an euclidien distance optimisation.