Search for: All records

In the plane, thewinding numberis the number of times a curve wraps around a given point. Winding numbers are a basic component of geometric algorithms such as point-in-polygon tests, and their generalization to data with noise or topological errors has proven valuable for geometry processing tasks ranging from surface reconstruction to mesh booleans. However, standard definitions do not immediately apply on surfaces, where not all curves bound regions. We develop a meaningful generalization, starting with the well-known relationship between winding numbers and harmonic functions. By processing the derivatives of such functions, we can robustly filter out components of the input that do not bound any region. Ultimately, our algorithm yields (i) a closed, completed version of the input curves, (ii) integer labels for regions that are meaningfully bounded by these curves, and (iii) the complementary curves that do not bound any region. The main computational cost is solving a standard Poisson equation, or for surfaces with nontrivial topology, a sparse linear program. We also introduce special basis functions to represent singularities that naturally occur at endpoints of open curves.

 

This paper describes a method for fast simplification of surface meshes. Whereas past methods focus on visual appearance, our goal is to solve equations on the surface. Hence, rather than approximate the extrinsic geometry, we construct a coarseintrinsic triangulationof the input domain. In the spirit of thequadric error metric (QEM), we perform greedy decimation while agglomerating global information about approximation error. In lieu of extrinsic quadrics, however, we store intrinsic tangent vectors that track how far curvature drifts during simplification. This process also yields a bijective map between the fine and coarse mesh, and prolongation operators for both scalar- and vector-valued data. Moreover, we obtain hard guarantees on element quality via intrinsic retriangulation---a feature unique to the intrinsic setting. The overall payoff is a black box approach to geometry processing, which decouples mesh resolution from the size of matrices used to solve equations. We show how our method benefits several fundamental tasks, including geometric multigrid, all-pairs geodesic distance, mean curvature flow, geodesic Voronoi diagrams, and the discrete exponential map.

 

This paper describes a numerical method for surface parameterization, yielding maps that are locally injective and discretely conformal in an exact sense. Unlike previous methods for discrete conformal parameterization, the method is guaranteed to work for any manifold triangle mesh, with no restrictions on triangulatiothat each task can be formulated as a convex problem where the triangulation is allowed to change---we complete the picture by introducing the machinery needed to actually construct a discrete conformal map. In particular, we introduce a new scheme for tracking correspondence between triangulations based on normal coordinates , and a new interpolation procedure based on layout in the light cone. Stress tests involving difficult cone configurations and near-degenerate triangulations indicate that the method is extremely robust in practice, and provides high-quality interpolation even on meshes with poor elements. 

This course provides a first introduction to intrinsic triangulations and their use in mesh processing algorithms. As geometric data becomes more ubiquitous, e.g., in applications such as augmented reality or machine learning, there is a pressing need to develop algorithms that work reliably on low-quality data. Intrinsic triangulations provide a powerful framework for these problems, by de-coupling the mesh used to encode geometry from the one used for computation. The basic shift in perspective is to encode the geometry of a mesh not in terms of ordinary vertex positions, but instead only in terms of edge lengths. Intrinsic triangulations have a long history in mathematics, but only in recent years have been applied to practical geometric computing. The course begins by giving motivation for intrinsic triangulations in terms of recent problems in computer graphics, followed by an interactive coding session where participants can make first contact with the idea of intrinsic meshes. We then give some mathematical background, and describe key data structures (overlay, signpost, normal coordinates). Using this machinery, we translate algorithms from computational geometry and scientific computing into cutting-edge algorithms for curved surfaces. For instance, we look at mesh parameterization, vector field processing, finding geodesics, solving partial differential equations (PDEs), and more. We also discuss processing of nonmanifold meshes and point clouds; participants can explore these algorithms via interactive demos. We conclude with a discussion of open questions and opportunities for future work.