Abstract We present a highly efficient and robust method for free boundary injective parameterization of disk‐like triangle meshes with low isometric distortion. Harmonic function–based approaches, grounded in a strong mathematical framework, are widely employed. In particular, harmonic maps are valuable for guaranteeing injectivity under suitable boundary conditions. They are also computationally efficient, as they operate within a linear subspace [FW22]. However, this restriction to a limited subspace often introduces substantial isometric distortion, especially on highly curved surfaces. In contrast, methods that explore the full space of piecewise linear maps [SPSH*17] achieve much lower isometric distortion, but at the expense of increased computational cost. We propose a hybrid method that combines the speed and robustness of harmonic maps with the generality of full‐space methods to produce injective maps with low isometric distortion up to 50 times faster than state‐of‐the‐art methods. The core concept is simple but powerful. Instead of searching for the optimal parameterization over the original mesh via a full‐space method, we simplify the input fine mesh and parameterize the coarse mesh. We then prolong the Beltrami coefficients from the coarse mesh parameterization to the fine mesh, resulting in a customized Laplacian matrix that gives rise to a harmonic map in a modified metric [WGS23, FW25]. Our method ensures injectivity, offers great computational efficiency, and produces significantly lower isometric distortion compared to harmonic maps.

Abstract We present a fast and robust method for computing an injective parameterization with low isometric distortion for disk‐like triangular meshes. Harmonic function‐based methods, with their rich mathematical foundation, are widely used. Harmonic maps are particularly valuable for ensuring injectivity under certain boundary conditions. In addition, they offer computational efficiency by forming a linear subspace [FW22]. However, this restricted subspace often leads to significant isometric distortion, especially for highly curved surfaces. Conversely, methods that operate in the full space of piecewise linear maps [SPSH*17] achieve lower isometric distortion, but at a higher computational cost. Aigerman et al. [AGK*22] pioneered a parameterization method that uses deep neural networks to predict the Jacobians of the map at mesh triangles, and integrates them into an explicit map by solving a Poisson equation. However, this approach often results in significant Poisson reconstruction errors due to the inability to ensure the integrability of the predicted neural Jacobian field, leading to unbounded distortion and lack of local injectivity. We propose a hybrid method that combines the speed and robustness of harmonic maps with the generality of deep neural networks to produce injective maps with low isometric distortion much faster than state‐of‐the‐art methods. The core concept is simple but powerful. Instead of learning Jacobian fields, we learn metric tensor fields over the input mesh, resulting in a cus‐tomized Laplacian matrix that defines a harmonic map in a modified metric [WGS23]. Our approach ensures injectivity, offers great computational efficiency, and produces significantly lower isometric distortion compared to straightforward harmonic maps.

We present a highly efficient-and-robust method for free-boundary flattening of disk-like triangle meshes in a globally injective manner. We show that by restricting the solution to a low-dimensional subspace of harmonic maps, we can dramatically accelerate the process while obtaining a low-distortion result. The algorithm consists of two main steps. A linear subspace construction, and a nonlinear nonconvex optimization for finding a low-distortion globally injective map within that subspace. The complexity of the first step dominates the algorithm's runtime and is merely that of solving a linear system. We combine recent results for computing locally-and-globally injective maps with that of harmonic maps into a conceptually simple algorithm that guarantees global injectivity. We demonstrate the great efficiency of our method over a dataset of 100 large scale models with more than 2M triangles each. Our algorithm is 10 times faster on average compared to the state-of-the-art Efficient Bijective Parameterizations (EBP) method [Su et al. 2020], on these high-resolution meshes, and more than 20 times faster on challenging examples (Figures 1,11). The speedup over [Jiang et al. 2017; Smith and Schaefer 2015] is even more dramatic.

We present a highly efficient method for interactive volumetric meshless shape deformation. Our method operates within a low dimensional sub-space of shape-aware C ∞ harmonic maps, and is the first method that is guaranteed to produce a smooth locally injective deformation in 3D. Unlike mesh-based methods in which local injectivity is enforced on tetrahedral elements, our method enforces injectivity on a sparse set of domain samples. The main difficulty is then to certify the map as locally injective throughout the entire domain. This is done by utilizing the Lipschitz continuity property of the harmonic basis functions. We show a surprising relation between the Lipschitz constant of the smallest singular value of the map Jacobian and the norm of the Hessian. We further carefully derive a Lipschitz constant for the Hessian, and develop a sufficient condition for the injectivity certification. This is done by utilizing the special structure of the harmonic basis functions combined with a novel regularization term that pushes the Lipschitz constants further down. As a result, the injectivity analysis can be performed on a relatively sparse set of samples. Combined with a parallel GPU-based implementation, our method can produce superior deformations with unique quality guarantees at real-time rates which were possible only in 2D so far.

Abstract We present a fast algorithm for low‐distortion locally injective harmonic mappings of genus 0 triangle meshes with and without cone singularities. The algorithm consists of two portions, a linear subspace analysis and construction, and a nonlinear non‐convex optimization for determination of a mapping within the reduced subspace. The subspace is the space of solutions to the Harmonic Global Parametrization (HGP) linear system [BCW17], and only vertex positions near cones are utilized, decoupling the variable count from the mesh density. A key insight shows how to construct the linear subspace at a cost comparable to that of a linear solve, extracting a very small set of elements from the inverse of the matrix without explicitly calculating it. With a variable count on the order of the number of cones, a tangential alternating projection method [HCW17] and a subsequent Newton optimization [CW17] are used to quickly find a low‐distortion locally injective mapping. This mapping determination is typically much faster than the subspace construction. Experiments demonstrating its speed and efficacy are shown, and we find it to be an order of magnitude faster than HGP and other alternatives.

We present a method for volumetric shape interpolation with unique shape preserving features. The input to our algorithm are two or more 3-manifolds, immersed into R 3 and discretized as tetrahedral meshes with shared connectivity. The output is a continuum of shapes that naturally blends the input shapes, while striving to preserve the geometric character of the input. The basis of our approach relies on the fact that the space of metrics with bounded isometric and angular distortion is convex [Chien et al. 2016b]. We show that for high dimensional manifolds, the bounded distortion metrics form a positive semidefinite cone product space. Our method can be seen as a generalization of the bounded distortion interpolation technique of [Chen et al. 2013] from planar shapes immersed in R 2 to solids in R 3 . The convexity of the space implies that a linear blend of the (squared) edge lengths of the input tetrahedral meshes is a simple yet powerful-and-natural choice. Linearly blending flat metrics results in a new metric which is, in general, not flat, and cannot be immersed into three-dimensional space. Nonetheless, the amount of curvature that is introduced in the process tends to be very low in practical settings. We further design an extremely robust nonconvex optimization procedure that efficiently flattens the metric. The flattening procedure strives to preserve the low distortion exhibited in the blended metric while guaranteeing the validity of the metric, resulting in a locally injective map with bounded distortion. Our method leads to volumetric interpolation with superb quality, demonstrating significant improvement over the state-of-the-art and qualitative properties which were obtained so far only in interpolating manifolds of lower dimensions.

We present a novel framework for creating Möbius-invariant subdivision operators with a simple conversion of existing linear subdivision operators. By doing so, we create a wide variety of subdivision surfaces that have properties derived from Möbius geometry; namely, reproducing spheres, circular arcs, and Möbius regularity. Our method is based on establishing a canonical form for each 1-ring in the mesh, representing the class of all 1-rings that are Möbius equivalent to that 1-ring. We perform a chosen linear subdivision operation on these canonical forms, and blend the positions contributed from adjacent 1-rings, using two novel Möbius-invariant operators, into new face and edge points. The generality of the method allows for easy coarse-to-fine mesh editing with diverse polygonal patterns, and with exact reproduction of circular and spherical features. Our operators are in closed-form and their computation is as local as the computation of the linear operators they correspond to, allowing for efficient subdivision mesh editing and optimization.

Abstract We present a planar harmonic cage‐based deformation method with local injectivity and bounded distortion guarantees, that is significantly faster than state‐of‐the‐art methods with similar guarantees, and allows for real‐time interaction. With a convex proxy for a near‐convex characterization of the bounded distortion harmonic mapping space from [ LW16 ], we utilize a modified alternating projection method (referred to as ATP) to project to this proxy. ATP draws inspiration from [ KABL15 ] and restricts every other projection to lie in a tangential hyperplane. In contrast to [ KABL15 ], our convex setting allows us to show that ATP is provably convergent (and is locally injective). Compared to the standard alternating projection method, it demonstrates superior convergence in fewer iterations, and it is also embarrassingly parallel, allowing for straightforward GPU implementation. Both of these factors combine to result in unprecedented speed. The convergence proof generalizes to arbitrary pairs of intersecting convex sets, suggesting potential use in other applications. Additional theoretical results sharpen the near‐convex characterization that we use and demonstrate that it is homeomorphic to the bounded distortion harmonic mapping space (instead of merely being bijective).

We present a method for locally injective seamless parametrization of triangular mesh surfaces of arbitrary genus, with or without boundaries, given desired cone points and rational holonomy angles (multiples of 2π/ q for some positive integer q ). The basis of the method is an elegant generalization of Tutte's "spring embedding theorem" to this setting. The surface is cut to a disk and a harmonic system with appropriate rotation constraints is solved, resulting in a harmonic global parametrization (HGP) method. We show a remarkable result: that if the triangles adjacent to the cones and boundary are positively oriented, and the correct cone and turning angles are induced, then the resulting map is guaranteed to be locally injective. Guided by this result, we solve the linear system by convex optimization, imposing convexification frames on only the boundary and cone triangles, and minimizing a Laplacian energy to achieve harmonicity. We compare HGP to state-of-the-art methods and see that it is the most robust, and is significantly faster than methods with comparable robustness.

We present a highly efficient planar meshless shape deformation algorithm. Our method is based on an unconstrained minimization of isometric energies, and is guaranteed to produce C ∞ locally injective maps by operating within a reduced dimensional subspace of harmonic maps. We extend the harmonic subspace of [Chen and Weber 2015] to support multiply-connected domains, and further provide a generalization of the bounded distortion theorem that appeared in that paper. Our harmonic map, as well as the gradient and the Hessian of our isometric energies possess closed-form expressions. A key result is a simple-and-fast analytic modification of the Hessian of the energy such that it is positive definite, which is crucial for the successful operation of a Newton solver. The method is straightforward to implement and is specifically designed to harness the processing power of modern graphics hardware. Our modified Newton iterations are shown to be extremely effective, leading to fast convergence after a handful of iterations, while each iteration is fast due to a combination of a number of factors, such as the smoothness and the low dimensionality of the subspace, the closed-form expressions for the differentials, and the avoidance of expensive strategies to ensure positive definiteness. The entire pipeline is carried out on the GPU, leading to deformations that are significantly faster to compute than the state-of-the-art.

We present a framework for designing shapes from diverse combinatorial patterns, where the vertex 1-rings and the faces are as rotationally symmetric as possible, and define such meshes as regular. Our algorithm computes the geometry that brings out the symmetries encoded in the combinatorics. We then allow designers and artists to envision and realize original meshes with great aesthetic qualities. Our method is general and applicable to meshes of arbitrary topology and connectivity, from triangle meshes to general polygonal meshes. The designer controls the result by manipulating and constraining vertex positions. We offer a novel characterization of regularity, using quaternionic ratios of mesh edges, and optimize meshes to be as regular as possible according to this characterization. Finally, we provide a mathematical analysis of these regular meshes, and show how they relate to concepts like the discrete Willmore energy and connectivity shapes.

Planar shape interpolation is a classic problem in computer graphics. We present a novel shape interpolation method that blends C ∞ planar harmonic mappings represented in closed-form. The intermediate mappings in the blending are guaranteed to be locally injective C ∞ harmonic mappings, with conformal and isometric distortion bounded by that of the input mappings. The key to the success of our method is the fact that the blended differentials of our interpolated mapping have a simple closed-form expression, so they can be evaluated with unprecedented efficiency and accuracy. Moreover, in contrast to previous approaches, these differentials are integrable, and result in an actual mapping without further modification. Our algorithm is embarrassingly parallel and is orders of magnitude faster than state-of-the-art methods due to its simplicity, yet it still produces mappings that are superior to those of existing techniques due to its guaranteed bounds on geometric distortion.

We present a framework for global parametrization that utilizes the edge lengths (squared) of the mesh as variables. Given a mesh with arbitrary topology and prescribed cone singularities, we flatten the original metric of the surface under strict bounds on the metric distortion (various types of conformal and isometric measures are supported). Our key observation is that the space of bounded distortion metrics (given any particular bounds) is convex, and a broad range of useful and well-known distortion energies are convex as well. With the addition of nonlinear Gaussian curvature constraints, the parametrization problem is formulated as a constrained optimization problem, and a solution gives a locally injective map. Our method is easy to implement. Sequential convex programming (SCP) is utilized to solve this problem effectively. We demonstrate the flexibility of the method and its uncompromised robustness and compare it to state-of-the-art methods.

Computation of mappings is a central building block in many geometry processing and graphics applications. The pursuit to compute mappings that are injective and have a controllable amount of conformal and isometric distortion is a long endeavor which has received significant attention by the scientific community in recent years. The difficulty of the problem stems from the fact that the space of bounded distortion mappings is nonconvex. In this paper, we consider the special case of harmonic mappings which have been used extensively in many graphics applications. We show that, somewhat surprisingly, the space of locally injective planar harmonic mappings with bounded conformal and isometric distortion has a convex characterization. We describe several projection operators that, given an arbitrary input mapping, are guaranteed to output a bounded distortion locally injective harmonic mapping that is closest to the input mapping in some special sense. In contrast to alternative approaches, the optimization problems that correspond to our projection operators are shown to be always feasible for any choice of distortion bounds. We use the boundary element method (BEM) to discretize the space of planar harmonic mappings and demonstrate the effectiveness of our approach through the application of planar shape deformation.

We present a framework for the computation of harmonic and conformal mappings in the plane with mathematical guarantees that the computed mappings are C ∞ , locally injective and satisfy strict bounds on the conformal and isometric distortion. Such mappings are very desirable in many computer graphics and geometry processing applications. We establish the sufficient and necessary conditions for a harmonic planar mapping to have bounded distortion. Our key observation is that these conditions relate solely to the boundary behavior of the mapping. This leads to an efficient and accurate algorithm that supports handle-based interactive shape-and-image deformation and is demonstrated to outperform other state-of-the-art methods.

We establish a framework to design triangular and circular polygonal meshes by using face-based compatible Möbius transformations. Embracing the viewpoint of surfaces from circles, we characterize discrete conformality for such meshes, in which the invariants are circles, cross-ratios, and mutual intersection angles. Such transformations are important in practice for editing meshes without distortions or loss of details. In addition, they are of substantial theoretical interest in discrete differential geometry. Our framework allows for handle-based deformations, and interpolation between given meshes with controlled conformal error.

We present an algorithm for mapping a triangle mesh, which is homeomorphic to a disk, to a planar domain with arbitrary fixed boundaries. The algorithm is guaranteed to produce a globally bijective map when the boundary is fixed to a shape that does not self-intersect. Obtaining a one-to-one map is of paramount importance for many graphics applications such as texture mapping. However, for other applications, such as quadrangulation, remeshing, and planar deformations, global bijectively may be unnecessarily constraining and requires significant increase on map distortion. For that reason, our algorithm allows the fixed boundary to intersect itself, and isguaranteedto produce a map that is injective locally (if such a map exists). We also extend the basic ideas of the algorithm to support the computation of discrete approximation for extremal quasiconformal maps. The algorithm is conceptually simple and fast. We demonstrate the superior robustness of our algorithm in various settings and configurations in which state-of-the-art algorithms fail to produce injective maps.

Planar shape interpolation is widely used in computer graphics applications. Despite a wealth of interpolation methods, there is currently no approach that produces shapes with a bounded amount of distortion with respect to the input. As a result, existing interpolation methods may produce shapes that are significantly different than the input and can suffer from fold-overs and other visual artifacts, making them less useful in many practical scenarios. We introduce a novel shape interpolation scheme designed specifically to produce results with a bounded amount of conformal (angular) distortion. Our method is based on an elegant continuous mathematical formulation and provides several appealing properties such as existence and uniqueness of the solution as well as smoothness in space and time domains. We further present a discretization and an efficient practical algorithm to compute the interpolant and demonstrate its usability and good convergence behavior on a wide variety of input shapes. The method is simple to implement and understand. We compare our method to state-of-the-art interpolation methods and demonstrate its superiority in various cases.

Abstract We propose the space of axis‐aligned deformations as the meaningful space for content‐aware image retargeting. Such deformations exclude local rotations, avoiding harmful visual distortions, and they are parameterized in 1D. We show that standard warping energies for image retargeting can be minimized in the space of axis‐aligned deformations while guaranteeing that bijectivity constraints are satisfied, leading to high‐quality, smooth and robust retargeting results. Thanks to the 1D parameterization, our method only requires solving a small quadratic program, which can be done within a few milliseconds on the CPU with no precomputation overhead. We demonstrate how the image size and the saliency map can be changed in real time with our approach, and present results on various input images, including the RetargetMebenchmark. We compare our results with six other algorithms in a user study to demonstrate that the space of axis‐aligned deformations is suitable for the problem at hand.

Abstract Conformal maps are widely used in geometry processing applications. They are smooth, preserve angles, and are locally injective by construction. However, conformal maps do not allow for boundary positions to be prescribed. A natural extension to the space of conformal maps is the richer space of quasiconformal maps of bounded conformal distortion. Extremal quasiconformal maps, that is, maps minimizing the maximal conformal distortion, have a number of appealing properties making them a suitable candidate for geometry processing tasks. Similarly to conformal maps, they are guaranteed to be locally bijective; unlike conformal maps however, extremal quasiconformal maps have sufficient flexibility to allow for solution of boundary value problems. Moreover, in practically relevant cases, these solutions are guaranteed to exist, are unique and have an explicit characterization. We present an algorithm for computing piecewise linear approximations of extremal quasiconformal maps for genus‐zero surfaces with boundaries, based on Teichmüller's characterization of the dilatation of extremal maps using holomorphic quadratic differentials. We demonstrate that the algorithm closely approximates the maps when an explicit solution is available and exhibits good convergence properties for a variety of boundary conditions.

Abstract Barycentric coordinates are an established mathematical tool in computer graphics and geometry processing, providing a convenient way of interpolating scalar or vector data from the boundary of a planar domain to its interior. Many different recipes for barycentric coordinates exist, some offering the convenience of a closed‐form expression, some providing other desirable properties at the expense of longer computation times. For example, harmonic coordinates, which are solutions to the Laplace equation, provide a long list of desirable properties (making them suitable for a wide range of applications), but lack a closed‐form expression. We derive a new type of barycentric coordinates based on solutions to the biharmonic equation. These coordinates can be considered a natural generalization of harmonic coordinates, with the additional ability to interpolate boundary derivative data. We provide an efficient and accurate way to numerically compute the biharmonic coordinates and demonstrate their advantages over existing schemes. We show that biharmonic coordinates are especially appealing for (but not limited to) 2D shape and image deformation and have clear advantages over existing deformation methods.

Abstract Barycentric coordinates are very popular for interpolating data values on polyhedral domains. It has been recently shown that expressing them as complex functions has various advantages when interpolating two‐dimensional data in the plane, and in particular for holomorphic maps. We extend and generalize these results by investigating the complex representation of real‐valued barycentric coordinates, when applied to planar domains. We show how the construction for generating real‐valued barycentric coordinates from a given weight function can be applied to generating complex‐valued coordinates, thus deriving complex expressions for the classical barycentric coordinates: Wachspress, mean value, and discrete harmonic. Furthermore, we show that a complex barycentric map admits the intuitive interpretation as a complex‐weighted combination of edge‐to‐edge similarity transformations, allowing the design of “home‐made” barycentric maps with desirable properties. Thus, using the tools of complex analysis, we provide a methodology for analyzing existing barycentric mappings, as well as designing new ones.

Conformal maps are considered very desirable for planar deformation applications, since they allow only local rotations and scale, avoiding shear and other visually disturbing distortions of local detail. Conformal maps are also orientation-preserving C ∞ diffeomorphisms, meaning they are extremely smooth and prevent unacceptable "foldovers" in the plane. Unfortunately, these maps are also notoriously difficult to control, so working with them in an interactive animation scenario to achieve specific effects is a significant challenge, sometimes even impossible. We describe a novel 2D shape deformation system which generates conformal maps, yet provides the user a large degree of control over the result. For example, it allows discontinuities at user-specified boundary points, so true "bends" can be introduced into the deformation. It also allows the prescription of angular constraints at corners of the target image. Combining these provides for a very effective user experience. At the heart of our method is a very natural differential shape representation for conformal maps, using so-called "conformal factors" and "angular factors", which allow more intuitive control compared to representation in the usual spatial domain. Beyond deforming a given shape into a new one at each key frame, our method also provides the ability to interpolate between shapes in a very natural way, such that also the intermediate deformations are conformal. Our method is extremely efficient: it requires only the solution of a small dense linear system at preprocess time and a matrix-vector multiplication during runtime (which can be implemented on a modern GPU), thus the deformations, even on extremely large images, may be performed in real-time.

Barycentric coordinates are heavily used in computer graphics applications to generalize a set of given data values. Traditionally, the coordinates are required to satisfy a number of key properties, the first being that they are real and positive. In this paper we relax this requirement, allowing the barycentric coordinates to be complex numbers. This allows us to generate new families of barycentric coordinates, which have some powerful advantages over traditional ones. Applying complex barycentric coordinates to data which is itself complex-valued allows to manipulate functions from the complex plane to itself, which may be interpreted as planar mappings. These mappings are useful in shape and image deformation applications. We use Cauchy’s theorem from complex analysis to construct complex barycentric coordinates on (not necessarily convex) polygons, which are shown to be equivalent to planar Green coordinates. These generate conformal mappings from a given source region to a given target region, such that the image of the source region is close to the target region. We then show how to improve the Green coordinates in two ways. The first provides a much better fit to the polygonal target region, and the second allows to generate deformations based on positional constraints, which provide a more intuitive user interface than the conventional cage-based approach. These define two new types of complex barycentric coordinates, which are shown to be very effective in interactive deformation and animation scenarios.

A space deformation is a mapping from a source region to a target region within Euclidean space, which best satisfies some userspecified constraints. It can be used to deform shapes embedded in the ambient space and represented in various forms -- polygon meshes, point clouds or volumetric data. For a space deformation method to be useful, it should possess some natural properties: e.g. detail preservation, smoothness and intuitive control. A harmonic map from a domain ω ⊂ R d to R d is a mapping whose d components are harmonic functions. Harmonic mappings are smooth and regular, and if their components are coupled in some special way, the mapping can be detail-preserving, making it a natural choice for space deformation applications. The challenge is to find a harmonic mapping of the domain, which will satisfy constraints specified by the user, yet also be detail-preserving, and intuitive to control. We generate harmonic mappings as a linear combination of a set of harmonic basis functions, which have a closed-form expression when the source region boundary is piecewise linear. This is done by defining an energy functional of the mapping, and minimizing it within the linear span of these basis functions. The resulting mapping is harmonic, and a natural "As-Rigid-As-Possible" deformation of the source region. Unlike other space deformation methods, our approach does not require an explicit discretization of the domain. It is shown to be much more efficient, yet generate comparable deformations to state-of-the-art methods. We describe an optimization algorithm to minimize the deformation energy, which is robust, provably convergent, and easy to implement.

We present an efficient O( n ) numerical algorithm for first-order approximation of geodesic distances on geometry images, where n is the number of points on the surface. The structure of our algorithm allows efficient implementation on parallel architectures. Two implementations on a SIMD processor and on a GPU are discussed. Numerical results demonstrate up to four orders of magnitude improvement in execution time compared to the state-of-the-art algorithms.

Abstract We describe a system for the animation of a skeleton‐controlled articulated object that preserves the fine geometric details of the object skin and conforms to the characteristic shapes of the object specified through a set of examples. The system provides the animator with an intuitive user interface and produces compelling results even when presented with a very small set of examples. In addition it is able to generalize well by extrapolating far beyond the examples.