<  Back to the Polytechnique Montréal portal

Champ distance d'un solide paramétrique

Xavier Mankovsky

Master's thesis (2009)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (10MB)
Show abstract
Hide abstract

Abstract

In this thesis we propose a novel method for computing the distance field of parametricshapes. Although many works related to distance field of polygonal geometrieshave been published, no solution has still been brought to obtain the distance fieldof 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 closestpoint on any object within the domain. In addition to distance, other propertiesmay be derived from the distance field, such as the direction to the surface. Whenthe distance field is signed, we may also determine if the point is internal or externalto objects within the domain.There is no closed form analytical formulas for computing the distance field of amanifold. Numerical methods are then necessary for computing the distance eldof such complex shapes. We use a front propagation method using the Eikonalequation to propagate the parametric surfaces. We use an iterative algorithm, calledthe Fast Sweeping method, for computing the numerical solution for Eikonalequation on a rectangular grid. The main idea of this method is to use a nonlinearGodunov upwind difference scheme to discretize the partial differental equation,and Gauss-Seidel iterations. Information propagates along characteristics from theboundary. Due to the nonlinearity of the propagation problem, characteristics mayintersect like the formation of shocks in a hyperbolic conservation law.Boundary conditions are defined as the set of the closest grid nodes from theparametric surfaces. The initialisation of boundary conditions is the most difficultand the upmost critical step.Indeed we present a novel method for detecting boundary nodes on a rectangulargrid using grid properties and projection criterias. We also present a new algorithmfor the projection of points on rational Bezier surfaces using an euclidien distanceoptimisation.

Résumé

Ce mémoire présente une méthode novatrice de calcul du champ distance d'unsolide paramétrique. Bien que de nombreux travaux aient déjà été préalablementréalisés sur le champ distance d'une géométrie polygonale, aucune solution n'avaitencore é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, pourlequel est dénie en tout point la distance euclidienne minimale permettant derejoindre la surface d'un solide.Le champ distance est calculé numériquement en résolvant une équation de transportbasée sur l'équation Eikonal. L'équation Eikonal est une équation aux dérivéespartielles du premier ordre, dites d'Hamilton-Jacobi. La résolution de l'équationEikonal est un problème hyperbolique et non linéaire. Notre méthode repose sur letransport de conditions limites qui dépendent de la géométrie.L'information se propage le long des courbes caractéristiques à partir des conditionslimites. Le caractère non linéaire du problème conduit à la formation de chocs, selonla loi de conservation hyperbolique.Nous avons utilisé une méthode de balayage, appelée Fast-Sweeping, pour résoudrel'é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ésolvantnumériquement l'équation Eikonal selon un schéma de Godunov. La méthode deré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'équationEikonal est résolue en utilisant plusieurs balayages alternés de Gauss-SeidelL'initialisation des conditions frontières est l'étape la plus importante et aussi laplus 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. Nousavons donc dû développer un algorithme permettant de détecter et d'initialiserprécisément les noeuds frontières. Ces noeuds sont initialisés avec la valeur de laplus courte distance euclidienne permettant de rejoindre le solide. Cette distanceminimale est obtenue en mesurant la longueur entre le noeud et sa projection surla surface du solide.
Department: Department of Computer Engineering and Software Engineering
Program: Génie informatique
Academic/Research Directors: François Guibault
PolyPublie URL: https://publications.polymtl.ca/173/
Institution: École Polytechnique de Montréal
Date Deposited: 15 Feb 2010 14:42
Last Modified: 22 Nov 2022 01:06
Cite in APA 7: Mankovsky, X. (2009). Champ distance d'un solide paramétrique [Master's thesis, École Polytechnique de Montréal]. PolyPublie. https://publications.polymtl.ca/173/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item