The Medial Axis Transform (MAT) is a powerful tool for shape analysis and manipulation. Traditional methods for working with shapes usually define shapes as boundaries between some “inside” and some “outside” region. While this definition is simple and intuitive, it does not lend itself well to the construction of algorithms for a number of seemingly simple tasks such as classification, deformation, and collision detection. The MAT is an alternative representation of shape that defines the “inside” region by its center and thickness. We present a method of constructing the MAT which overcomes a significant limitation of its use with real-world data: instability. As classically defined, the MAT is unstable with respect to the shape boundary that it represents. For data sources afflicted by noise this is a serious problem. We propose an algorithm, LSMAT, which constructs a stable least squares approximation to the MAT. / Graduate

Computing correspondences or maps between shapes is one of the oldest problems in Computer Graphics and Geometry Processing with a wide range of applications from deformation transfer, statistical shape analysis, to co-segmentation and exploration among a myriad others. A good map is supposed to be continuous, as-bijective-as-possible, accurate if there are ground-truth corresponding landmarks given, and lowdistortionw.r.t. different measures, for example as-conformal-as-possible to preserve the angles. This thesis contributes to the area of non-rigid shape matching and map space exploration in Geometry Processing. Specifically, we consider the discrete setting, where the shapes are discretized as amesh structure consisting of vertices, edges, and polygonal faces. In the simplest case, we only consider the graph structure with vertices and edges only. In this thesis, we design algorithms to compute soft correspondences between discrete shapes. Specifically, (1)we propose different regularizers, including orientation-preserving operator and the Resolvent Laplacian Commutativity operator, to promote the shape correspondences in the functional map framework. (2) We propose two refinement methods, namely BCICP and ZoomOut, to improve the accuracy, continuity, bijectivity and the coverage of given point-wisemaps. (3)We propose a tree structure and an enumeration algorithm to explore the map space between a pair of shapes that can update multiple high-quality dense correspondences.

This thesis proposes machine learning algorithms for processing geometry by example. Each algorithm takes as input a collection of shapes along with exemplar values of target properties related to shape processing tasks. The goal of the algorithms is to output a function that maps from the shape data to the target properties. The learned functions can be applied to novel input shape data in order to synthesize the target properties with style similar to the training examples. Learning such functions is particularly useful for two different types of geometry processing problems. The first type of problems involves learning functions that map to target properties required for shape interpretation and understanding. The second type of problems involves learning functions that map to geometric attributes of animated shapes required for real-time rendering of dynamic scenes. With respect to the first type of problems involving shape interpretation and understanding, I demonstrate learning for shape segmentation and line illustration. For shape segmentation, the algorithms learn functions of shape data in order to perform segmentation and recognition of parts in 3D meshes simultaneously. This is in contrast to existing mesh segmentation methods that attempt segmentation without recognition based only on low-level geometric cues. The proposed method does not require any manual parameter tuning and achieves significant improvements in results over the state-of-the-art. For line illustration, the algorithms learn functions from shape and shading data to hatching properties, given a single exemplar line illustration of a shape. Learning models of such artistic-based properties is extremely challenging, since hatching exhibits significant complexity as a network of overlapping curves of varying orientation, thickness, density, as well as considerable stylistic variation. In contrast to existing algorithms that are hand-tuned or hand-designed from insight and intuition, the proposed technique offers a largely automated and potentially natural workflow for artists. With respect to the second type of problems involving fast computations of geometric attributes in dynamic scenes, I demonstrate algorithms for learning functions of shape animation parameters that specifically aim at taking advantage of the spatial and temporal coherence in the attribute data. As a result, the learned mappings can be evaluated very efficiently during runtime. This is especially useful when traditional geometric computations are too expensive to re-estimate the shape attributes at each frame. I apply such algorithms to efficiently compute curvature and high-order derivatives of animated surfaces. As a result, curvature-dependent tasks, such as line drawing, which could be previously performed only offline for animated scenes, can now be executed in real-time on modern CPU hardware.

This thesis proposes machine learning algorithms for processing geometry by example. Each algorithm takes as input a collection of shapes along with exemplar values of target properties related to shape processing tasks. The goal of the algorithms is to output a function that maps from the shape data to the target properties. The learned functions can be applied to novel input shape data in order to synthesize the target properties with style similar to the training examples. Learning such functions is particularly useful for two different types of geometry processing problems. The first type of problems involves learning functions that map to target properties required for shape interpretation and understanding. The second type of problems involves learning functions that map to geometric attributes of animated shapes required for real-time rendering of dynamic scenes. With respect to the first type of problems involving shape interpretation and understanding, I demonstrate learning for shape segmentation and line illustration. For shape segmentation, the algorithms learn functions of shape data in order to perform segmentation and recognition of parts in 3D meshes simultaneously. This is in contrast to existing mesh segmentation methods that attempt segmentation without recognition based only on low-level geometric cues. The proposed method does not require any manual parameter tuning and achieves significant improvements in results over the state-of-the-art. For line illustration, the algorithms learn functions from shape and shading data to hatching properties, given a single exemplar line illustration of a shape. Learning models of such artistic-based properties is extremely challenging, since hatching exhibits significant complexity as a network of overlapping curves of varying orientation, thickness, density, as well as considerable stylistic variation. In contrast to existing algorithms that are hand-tuned or hand-designed from insight and intuition, the proposed technique offers a largely automated and potentially natural workflow for artists. With respect to the second type of problems involving fast computations of geometric attributes in dynamic scenes, I demonstrate algorithms for learning functions of shape animation parameters that specifically aim at taking advantage of the spatial and temporal coherence in the attribute data. As a result, the learned mappings can be evaluated very efficiently during runtime. This is especially useful when traditional geometric computations are too expensive to re-estimate the shape attributes at each frame. I apply such algorithms to efficiently compute curvature and high-order derivatives of animated surfaces. As a result, curvature-dependent tasks, such as line drawing, which could be previously performed only offline for animated scenes, can now be executed in real-time on modern CPU hardware.

Em simulações físicas baseadas em partículas, a informação sobre quais partículas pertencem à fronteira do sistema e quais são consideradas internas é, em geral, uma informação útil porém difícil de ser obtida eficientemente. Esta informação pode ser usada na geração da superfície livre de um fluido ou no cálculo da tensão superficial o mesmo, entre outras aplicações. Técnicas encontradas na literatura podem apresentar resultados satisfatórios, mas em geral são sensíveis à escala do problema, distribuição das partículas e envolvem operações computacionalmente caras como inversão de matrizes. O objetivo deste trabalho é estudar os métodos existentes e apresentar uma alternativa com custo computacional mais baixo e que seja capaz de lidar com problemas de diferentes escalas e naturezas de forma mais simples que os métodos existentes. / In particle-based physics simulations, the information about which particles belong to the boundary of the system and which are considered internal is, in general, an information that is useful but hard to obtain in an efficient way. This information can be applied to generate the free surface of the fluid or to compute the surface tension, among other applications. Techniques found in the literature may present satisfactory results, but in general they are sensible to the problem scale, particle distribution and involve computationally expensive operations such as matrix inversion. The goal of this study is to analyze the existing methods and present an alternative with lower computational cost and which is capable of handling problems with different scales and nature in a simpler way than the existing methods.

Em simulações físicas baseadas em partículas, a informação sobre quais partículas pertencem à fronteira do sistema e quais são consideradas internas é, em geral, uma informação útil porém difícil de ser obtida eficientemente. Esta informação pode ser usada na geração da superfície livre de um fluido ou no cálculo da tensão superficial o mesmo, entre outras aplicações. Técnicas encontradas na literatura podem apresentar resultados satisfatórios, mas em geral são sensíveis à escala do problema, distribuição das partículas e envolvem operações computacionalmente caras como inversão de matrizes. O objetivo deste trabalho é estudar os métodos existentes e apresentar uma alternativa com custo computacional mais baixo e que seja capaz de lidar com problemas de diferentes escalas e naturezas de forma mais simples que os métodos existentes. / In particle-based physics simulations, the information about which particles belong to the boundary of the system and which are considered internal is, in general, an information that is useful but hard to obtain in an efficient way. This information can be applied to generate the free surface of the fluid or to compute the surface tension, among other applications. Techniques found in the literature may present satisfactory results, but in general they are sensible to the problem scale, particle distribution and involve computationally expensive operations such as matrix inversion. The goal of this study is to analyze the existing methods and present an alternative with lower computational cost and which is capable of handling problems with different scales and nature in a simpler way than the existing methods.

La création et la compréhension des déformations de surfaces sont des thèmes récurrent pour le traitement de géométrie 3D. Comme les surfaces lisses peuvent être représentées de multiples façon allant du nuage ​​de points aux maillages polygonales, un enjeu important est de pouvoir comparer ou déformer des formes discrètes indépendamment de leur représentation. Une réponse possible est de choisir une représentation flexible des surfaces déformables qui peut facilement être transportées d'une structure de données à une autre.Dans ce but, les "functional map" proposent de représenter des applications entre les surfaces et, par extension, des déformations comme des opérateurs agissant sur des fonctions. Cette approche a été introduite récemment pour le traitement de modèle 3D, mais a été largement utilisé dans d'autres domaines tels que la géométrie différentielle, la théorie des opérateurs et les systèmes dynamiques, pour n'en citer que quelques-uns. Le principal avantage de ce point de vue est de détourner les problèmes encore non-résolus, tels que la correspondance forme et le transfert de déformations, vers l'analyse fonctionnelle dont l'étude et la discrétisation sont souvent mieux connues. Cette thèse approfondit l'analyse et fournit de nouvelles applications à ce cadre d'étude. Deux questions principales sont discutées.Premièrement, étant donné deux surfaces, nous analysons les déformations sous-jacentes. Une façon de procéder est de trouver des correspondances qui minimisent la distorsion globale. Pour compléter l'analyse, nous identifions les parties les moins fiables du difféomorphisme grâce une méthode d'apprentissage. Une fois repérés, les défauts peuvent être éliminés de façon différentiable à l'aide d'une représentation adéquate des champs de vecteurs tangents.Le deuxième développement concerne le problème inverse : étant donné une déformation représentée comme un opérateur, comment déformer une surface en conséquence ? Dans une première approche, nous analysons un encodage de la structure intrinsèque et extrinsèque d'une forme en tant qu'opérateur fonctionnel. Dans ce cadre, l'objet déformé peut être obtenu, à rotations et translations près, en résolvant une série de problèmes d'optimisation convexe. Deuxièmement, nous considérons une version linéarisée de la méthode précédente qui nous permet d'appréhender les champs de déformation comme agissant sur la métrique induite. En conséquence la résolution de problèmes difficiles, tel que le transfert de déformation, sont effectués à l'aide de simple systèmes linéaires d'équations. / Creating and understanding deformations of surfaces is a recurring theme in geometry processing. As smooth surfaces can be represented in many ways from point clouds to triangle meshes, one of the challenges is being able to compare or deform consistently discrete shapes independently of their representation. A possible answer is choosing a flexible representation of deformable surfaces that can easily be transported from one structure to another.Toward this goal, the functional map framework proposes to represent maps between surfaces and, to further extents, deformation of surfaces as operators acting on functions. This approach has been recently introduced in geometry processing but has been extensively used in other fields such as differential geometry, operator theory and dynamical systems, to name just a few. The major advantage of such point of view is to deflect challenging problems, such as shape matching and deformation transfer, toward functional analysis whose discretization has been well studied in various cases. This thesis investigates further analysis and novel applications in this framework. Two aspects of the functional representation framework are discussed.First, given two surfaces, we analyze the underlying deformation. One way to do so is by finding correspondences that minimize the global distortion. To complete the analysis we identify the least and most reliable parts of the mapping by a learning procedure. Once spotted, the flaws in the map can be repaired in a smooth way using a consistent representation of tangent vector fields.The second development concerns the reverse problem: given a deformation represented as an operator how to deform a surface accordingly? In a first approach, we analyse a coordinate-free encoding of the intrinsic and extrinsic structure of a surface as functional operator. In this framework a deformed shape can be recovered up to rigid motion by solving a set of convex optimization problems. Second, we consider a linearized version of the previous method enabling us to understand deformation fields as acting on the underlying metric. This allows us to solve challenging problems such as deformation transfer are solved using simple linear systems of equations.

No description available.

[pt] A aquisição de malhas triangulares normalmente introduz ruídos indesejados. A remoção de ruído de malhas é uma tarefa da área de processamento geométrico que serve para remover esse tipo de distorção. Para preservar a fidelidade em relação à malha desejada, um algoritmo de remoção de ruído de malha deve preservar detalhes enquanto remove altas frequências indesejadas sobre a superfície. Vários algoritmos foram propostos para resolver este problema usando um esquema de filtragem bilateral. Neste trabalho, propomos um algoritmo de dois passos que usa vizinhança adaptativa e filtragem bilateral para remover ruído do campo normal e, em seguida, atualizar as posições dos vértices ajustando os triângulos às novas normais. A nossa contribuição principal é a computação da vizinhança adaptativa. Essa computação é formulada como problemas locais de otimização quadrática que podem ser controlados para obter o comportamento desejado da vizinhança. A proposta é comparada visual e quantitativamente com vários algoritmos propostos na literatura, usando dados sintéticos e reais. / [en] The acquisition of triangular meshes typically introduces undesired noise. Mesh denoising is a geometry processing task to remove this kind of distortion. To preserve the geometric fidelity of the desired mesh, a mesh denoising algorithm must preserve true details while removing artificial high-frequencies from the surface. Several algorithms were proposed to address this problem using a bilateral filtering scheme. In this work, we propose a two-step algorithm which uses adaptive patches and bilateral filtering to denoise the normal field, and then update vertex positions fitting the faces to the denoised normals. The computation of the adaptive patches is our main contribution. We formulate this computation as local quadratic optimization problems that we can control to obtain a desired behavior of the patch. We compared our proposal with several algorithms proposed in the literature using synthetic and real data.

La simulation numérique des écoulements est une étape essentielle de la conception des turbines à gaz équipant les hélicoptères. La recherche permanente de la performance a conduit à des géométries de turbines très complexes et il devient de plus en plus difficile de modéliser des grilles de simulation qui épousent parfaitement la CAO des moteurs. La technique chimère permet de s’affranchir des contraintes de recollement parfait des différentes grilles en autorisant leur chevauchement. Cependant elle soulève de nouveaux problèmes lors de la phase de post-traitement, lorsqu’il s’agit d’exploiter les résultats de simulation afin de faire de nouveaux calculs ou de les visualiser, parce que les outils usuels ne sont pas adaptés à ces configurations particulières. Dans le cadre des deux premiers projets du programme MOSART du pôle de compétitivité Aerospace Valley, respectivement MACAO et OSMOSES, nous avons travaillé en collaboration avec l’entreprise Turbomeca à la conception d’une méthode de reconstruction volumique afin de traiter les résultats de simulations à base chimère. Nous avons ainsi proposé une méthode innovante permettant de reconstruire une partition de l’espace de simulation exempte de chevauchement entre grilles. La nouvelle partition conserve le maximum de propriétés des grilles d’origine et assure en tout point la conformité aux bords. La complexité théorique est linéaire avec la taille des grilles d’origine et nous permet d’obtenir des temps de traitement de l’ordre de la seconde pour des grilles de plusieurs centaines de milliers de mailles. Le principal intérêt de ce travail est de rendre exploitables les résultats de simulations à base chimère par les outils de post-traitement, qu’il s’agisse d’outils maison ou des nombreux logiciels commerciaux ou OpenSource disponibles, condition indispensable pour l’adoption de la méthode chimère par les bureaux d’études. / Computationnal fluid dynamics is an essential step in gas turbine modelling. Continuous optimization of turbines has led to sophisticated geometries, which raises severe issues for the design of adapted simulation grids. The chimera technique aims at relaxing geometry matching constraints by allowing grids overlap. However, post-processing of simulation results performed over chimera grids raises new issues because usual tools are not tuned for this particular geometricconfigurations. In the framework of the MOSART programme of the world competitiveness cluster Aerospace Valley, we have been working in collaboration with Turbomeca in order to develop a technique for the volumetric reconstruction of chimerasimulation results. We propose an innovative method that allows us to build a collection of non-overlapping grids while preserving the main properties of the former simulation grids and featuring boundary conforming property everywhere.The theorical complexity of our algorithms has proved to be linear in the size of the former grids and leads to computation times of a few seconds for grids of hundreds of thousands of cells. The main impact of this work leads in the possibility of using any post-processing tool, including a large number of OpenSource solutions, for post-processing chimera simulation results, which is a mandatory condition for the wide acceptance of this method by industry actors.