This thesis presents a particular set of spheres as new representation of the shape of a 3D solid. The spheres considered are maximal inscribed spheres in the solid and their centres are chosen in such a way that at most one sphere centre lies in a cubic region of space.The shape representation proposed is a discretization of the medial surface transform of a solid. Part I of this thesis presents algorithms for the computation of this representation given a boundary representation of a solid by approximating its medial surface transform. Properties of those medial spheres that are not detected by our algorithm in 3D are described and a complete characterization of those medial circles that are not detected by a 2D version of our algorithm is given. In Part II, recent results from differential geometry are used to compute principal curvatures and principal curvature directions on the boundary of the smooth solid represented using the union of medial spheres. This computation is performed using only the medial sphere centres and a pair of points on each medial sphere that lies on the surface of the solid being modeled. It is shown how the union of medial spheres allows a part-based description of the solid, with a significance measure associated with each part. In Part III, it is shown that our shape representation can offer a tight volumetric fit to a polyhedron, using a small number of spheres. The spheres used in our representation can be quickly updated as the solid undergoes a certain class of deformations. It is shown how our set of medial spheres allows efficient and accurate proximity queries between polyhedra. / Cette thèse présente une nouvelle représentation de la forme de solides 3D, décrite par un ensemble spécifique de sphères. Les sphères de cette représentation sont des sphères inscrites maximalement dans le solide et leur centre est choisi de telle manière que tout au plus un seul centre de sphère occupe une région cubique de l'espace. La représentation de forme proposée est une discrétisation de la surface médiane d'un solide. La première partie de cette thèse présente des algorithmes pour le calcul de cette représentation à partir d'une description de la frontière d'un solide, en approximant sa surface médiane. Certaines propriétés des sphères médianes qui ne sont pas détectées par notre algorithme en 3D sont décrits, ainsi qu'une caractérisation complète des cercles médians qui ne sont pas détectés par une version 2D de l'algorithme.En deuxième partie, des résultats récents en géométrie différentielle sont utilisés pour calculer les courbures principales et les directions principales de courbure sur la surface d'un solide lisse représenté par une union de sphères médianes. Ce calcul est effectué en utilisant seulement le centre et une paire de points relatifs à chaque sphère médiane qui se trouve sur la surface du solide. Il est aussi démontré comment l'union des sphères médianes permet une description par partie du solide, tout en donnant une mesure de l'importance associée à chaque partie.En troisième partie, il est démontré que notre représentation de forme peut servir à l'ajustement volumétrique serré d'un polyèdre, tout en utilisant un nombre restreint de sphères. Les sphères utilisées dans notre représentation peuvent être rapidement adaptées au solide lorsqu'il est sujet à une certaine classe de déformations. Notre ensemble de sphères médianes permet d'effectuer des requêtes de proximité efficaces et précises entre des polyèdres.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.106357 |
| Date | January 2012 |
| Creators | Stolpner, Svetlana |
| Contributors | Kaleem Siddiqi (Supervisor1), Sue Whitesides (Supervisor2) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Doctor of Philosophy (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0023 seconds