Compact and efficient implicit representations
Représentations implicites compactes et efficientes
Résumé
In the perspective of manipulating geometric objects, there exists two main representations of curves and surfaces: parametric and implicit representations. Both are useful for different purposes and thus complement each other. Parametric representations are efficient in sampling points on an object; implicit representations are efficient in determining whether a point belongs to an object or not. Because of that, having both representations of the same objects at the same time maximizes the range of operations one can do with geometric objects. Switching from one representation to another is not an easy task. It usually requires the use of algebraic properties. Thus, there is a strong link between algebra and geometry, symbolised by the algebraic varieties: they are geometric objects described by an algebraic structure.
This thesis explores new kinds of implicit representations and algorithms for computing implicit representations. We show that different methods are adapted to different situations even when it comes to the choice of an implicit representation amongst several possibilities. Space curves can thus be described implicitly by conical surfaces, moving lines and/or moving quadrics... each description having different geometrical properties and practical usage. As there is not one implicit representation or implicitization algorithm that would be the best in any situation, we develop methods that fit to different kinds of informations known about the object we want to represent. As we show, objects constructed by sweeping a rigid body can be represented using the knowledge of that nature. Similarly, very particular curves may have a complicated algebraic structure. Depending on our tolerance to approximation, such curves can thus be perturbed to simplify greatly their algebraic structure or, on the contrary, be represented by a rich implicit representation format.
Dans l'optique de manipuler des objets géométriques, il existe deux méthodes principales de représentation de courbes et de surfaces : les paramétriques et les implicites. Chacune de ces méthode est utile pour différents objectifs et sont donc complémentaires. Les représentations paramétriques sont aptes à générer des points de l'objet ; les représentations implicites sont aptes à déterminer si un point est sur un objet ou non. De ce fait, il est utile d'avoir accès à ces deux types de représentations et ainsi maximiser les possibilités d'effectuer divers types d'opérations sur les objets géométriques. Passer d'une méthode de représentation à une autre n'est pas une tâche aisée. Cela requiert généralement l'utilisation de méthodes algébriques. Il y a donc un lien fort entre l'algèbre et la géométrie qui est symbolisé par la notion de variété algébrique : il s'agit d'objets géométriques décrites par une structure algébrique.
Cette thèse explore de nouveaux types de représentations implicites et d'algorithmes produisant des représentations implicites. Nous montrons que différentes méthodes sont adaptées à différentes situations même pour ce qui est du choix de la représentation implicite à choisir parmi plusieurs possibilités. Les courbes dans l'espace tri-dimensionnel peuvent ainsi être décrites implicitement par des surfaces coniques, par des surfaces mobiles de différents degrés... chaque type de description ayant des propriétés géométriques et des usages pratiques différents. Comme il n'y a pas d'unique représentation implicite ou d'unique algorithme d'implicitisation qui serait le meilleur dans toutes les situations, nous développons aussi des méthodes qui s'adaptent à différents types d'informations connues à propos de l'objet que nous souhaitons représenter. Ainsi que nous le montrons, les objets construits en tant que rémanence d'une structure rigide au cours d'un mouvement continu peuvent être représentés en employant cette information sur la nature de leur construction. Similairement, certaines courbes très particulières possèdent une structure algébrique compliquée. Selon notre tolérance à l'approximation, de telles courbes peuvent être légèrement modifiées pour simplifier grandement leur structure algébrique ou, au contraire, être représentées par une forme riche de représentation implicite.
Fichier principal
Thesis_CompactAndEfficientImplicitRepresentations.pdf (4.24 Mo)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)