Modélisation de formes à l'aide de squelettes : échafaudages & convolution anisotrope

Skeletons have proved to be a successful tool in modeling complex shapes. They provide a basis for many processes ranging from implicit modeling, to deformation and animations. In this work we advance in two topics related with skeleton modeling: quad dominant skeleton-based meshes and smooth implicit surfaces generated from a skeleton. Given a skeleton made of line segments we describe how to obtain a coarse quad mesh of a surface that tightly encloses the skeleton and follows its structure - the scaffold. We formalize as an Integer Linear Program the problem of constructing an optimal scaffold that minimizes the total number of quads on the mesh. We prove the feasibility of the Integer Linear Program for any skeleton. In particular we can generate these scaffolds for skeletons with cycles. We additionally show how to obtain regular scaffolds, i.e. scaffolds with the same number of quad patches around each line segment, and symmetric scaffolds that respect the symmetries of the skeleton. Applications to polygonization of skeleton-based implicit surfaces are also presented. Convolution surfaces with ID skeletons have been limited to close-to-circular normal sections. The new formalism we present here increases the modeling freedom since it allows for ellipsoidal normal sections. The new anisotropy for Gl skeletal curves, chosen as circular splines, is interpolated from the rotation angles and three radii of ellipsoids at each extremity, given as user input. This lightweight model creates smooth shapes that previously required tweaking the skeleton or supplementing it with 2D pieces. The scale invariance of our formalism achieves excellent radii control and thus lends itself to approximate a variety of shapes. The construction of a scaffold is extended to skeletons with G l branches. It projects onto the convolution surface as a quad mesh with skeleton bound edge-flow. In addition to the two main contributions described above we develop further topics related to scaffolding and convolution surfaces. We discuss how spherical Laguerre diagrams may be used to improve the scaffold shapes when different incident radii is allowed at joints, and we describe how to construct volumetric hexahedral meshes for a skeleton-based model starting from a scaffold. We also introduce Creative Telescoping techniques for the computation of closed form formulas through recurrence. Finally we present PySkelton - a Python library for skeleton based modeling that implements our algorithms and provides an academic friendly programming interface.Les squelettes se sont révélés être un outil efficace pour modéliser des formes complexes. Ils fournissent une base pour de nombreux processus allant de la modélisation implicite à la déformation et aux animations. Dans ce travail, nous abordons deux sujets liés à la modélisation avec squelette : les maillages quad-dominants à base de squelette et les surfaces lisses implicites générées à partir d'un squelette. Etant donné un squelette constitué de segments de droite, nous décrivons comment obtenir un maillage quad-dominant d'une surface qui entoure étroitement le squelette et suit sa structure - l'échafaudage. Nous formalisons sous forme de programme linéaire sur les entiers le problème de la construction d'un échafaudage optimal minimisant le nombre total de quads sur le maillage. Nous prouvons la faisabilité du programme linéaire entier pour tout squelette. En particulier, nous pouvons générer ces échafaudages pour des squelettes avec des cycles. Nous montrons également comment obtenir des échafaudages réguliers, c'est-à-dire des échafaudages avec le même nombre de quads autour de chaque segment de droite, et des échafaudages symétrique respectant les symétries du squelette. Des applications à la polygonisation de surfaces implicites à base de squelettes sont également présentées. Les surfaces de convolution avec des squelettes ID ont été limitées à des sections normales presque circulaires. La nouvelle formulation que nous présentons ici augmente les possibilités de modélisation car elle permet les sections normales ellipsoïdales. Cette anisotropie est définie pour des courbes squelettales G1, choisies comme des splines circulaires, en interpolant l'angle de rotation et les trois rayons d'ellipsoïdes donnés, par l'utilisateur, à chaque extrémité de la courbe. Ce modèle léger crée des formes lisses qui nécessitaient auparavant de peaufiner le squelette ou de le compléter avec des pièces 2D. L'invariance par homothétie de notre formulation permet un contrôle fin des rayons et se prête ainsi à approximer une variété de formes. La construction d'un échafaudage est étendue aux squelettes avec des branches G l Il se projette sur la surface de convolution pour former un maillage quad-dominant avec un flux d'arrêtes qui longe le squelette. En plus des deux contributions principales décrites ci-dessus, nous développons d'autres sujets liés aux échafaudages et aux surfaces de convolution. Nous discutons la façon dont les diagrammes de Laguerre sphériques peuvent être utilisés pour améliorer la forme des échafaudages lorsque différents rayons incidents sont autorisés au niveau des articulations, et nous décrivons comment construire des maillages hexaédriques volumétriques pour un modèle basé sur un squelette à partir d’un échafaudage. Nous introduisons également les techniques de Télescopage Créatif pour le calcul par récurrence de formes closes de fonctions de convolution. Enfin, nous présentons PySkelton - une bibliothèque Python pour la modélisation basée sur le squelette qui implémente nos algorithmes et fournit une interface de programmation conviviale pour les académiques