Abstract Implicit surface representations have regained popularity because of their use in machine learning. A common component in optimization is regularization, penalizing the deviation of the surface from its original shape. The popular as‐rigid‐as‐possible (A rap ) energy strikes a good compromise between realistic deformation behavior and efficient computation, at least for piecewise linear meshes. We develop an approach for computing the A rap energy of a deformation function based on point sampling of the surface. The implicit representation is exploited to provide differentials in each sample. The evaluation is efficient and exact in each sample (up to numerical precision). We demonstrate the general applicability of the method to neural shape processing in several applications and contrast its properties with alternatives from the literature.

Abstract The well‐established As‐Rigid‐As‐Possible (ARAP) energy has various forms. For surface deformation, commonly used energies contain an implicit bending penalty. We present a natural, continuous generalization that incorporates multiple ARAP versions with an implicit, user‐controllable bending penalty. We discretize an intuitive variant of the energy and demonstrate that it is independent of mesh resolution and produces comparable results to those of competing methods that include an explicit bending penalty term. We validate our method and demonstrate that, despite its computational overhead, it converges among the fastest of all ARAP variants.

We investigate the construction of visually smooth spline surfaces that interpolate the vertices of triangulations by blending local patches. Each triangle star carries a locally interpolating surface patch. The patches are only required to interpolate the vertex, whereas in previous methods the patches are often defined per edge, imposing multiple constraints on local approximations. We adopt simple rational blend functions for the triangular domains, that are constructed so that they retain the interpolation and tangent behavior on the patch boundaries. Decoupling local approximation from blending facilitates the exploration of visually pleasing constructions, while controlling the complexity.

We show how the problem of creating a triangulation in d -dimensional space that conforms to constraints given as sub-simplices can be turned into the problem of computing the lower hull of a sum of wedge functions. This sum can be interpreted as a Weighted Delaunay Triangulations, necessarily containing the constraints as unions of its elements. Intersections of wedges lead to Steiner points. As the number of such intersections is polynomial in the number of wedges, and the number of wedges per element is typically 1 (at most d ), this proves that the complexity of the output is polynomial. Moreover, we show that the majority of wedge intersections is unnecessary for a conforming triangulation and further heuristically reduce the number of Steiner points. Using appropriate data structures, the function can be evaluated in quasi-linear time, leading to an output-sensitive algorithm.

Differentiable rendering has become a key ingredient in solving challenging inverse problems in computer graphics and vision. Existing systems can simulate and differentiate the spatial propagation of light. We exploit the duality of light transport simulations and geometric acoustics to apply differential rendering techniques to established acoustic simulation methods. The resulting system is capable of simulating sound according to the geometrical acoustics model and computing derivatives of the output energy spectrograms with respect to arbitrary parameters of the scene, including materials, emitters, microphones, and scene geometry. Contrary to current differentiable transient rendering, we can handle arbitrary simulation depths and achieve constant memory and linear execution times by presenting a temporal extension of Path Replay Backpropagation [Vicini et al. 2021]. We verify our model against established simulation software, and demonstrate the capabilities of optimization with gradients at examples of inverse acoustics and optimizing room parameters. This opens up a new field of research for acoustic optimization that could be as impactful for the acoustic community as differentiable rendering was for the graphics community.

Affine subspaces of Euclidean spaces are also referred to as flats. A standard task in computer vision, or more generally in engineering and applied sciences, is fitting a flat to a set of points, which is commonly solved using the PCA. We generalize this technique to enable fitting a flat to a set of other flats, possibly of varying dimensions, based on representing the flats as squared distance fields. Compared to previous approaches such as Riemannian centers of mass in the manifold of affine Grassmannians, our approach is conceptually much simpler and computationally more efficient, yet offers desirable properties such as respecting symmetries and being equivariant to rigid transformations, leading to more intuitive and useful results in practice. We demonstrate these claims in a number of synthetic experiments and a multi-view reconstruction task of line-like objects.

Abstract A parameterization of a triangle mesh is a realization in the plane so that all triangles have positive signed area. Triangle mesh parameterizations are commonly computed by minimizing a distortion energy, measuring the distortions of the triangles as they are mapped into the parameter domain. It is assumed that the triangulation is fixed and the triangles are mapped affinely. We consider a more general setup and additionally optimize among the intrinsic triangulations of the piecewise linear input geometry. This means the distortion energy is computed for the same geometry, yet the space of possible parameterizations is enlarged. For minimizing the distortion energy, we suggest alternating between varying the parameter locations of the vertices and intrinsic flipping. We show that this process improves the mapping for different distortion energies at moderate additional cost. We also find intrinsic triangulations that are better starting points for the optimization of positions, offering a compromise between the full optimization approach and exploiting the additional freedom of intrinsic triangulations.

Abstract As‐rigid‐as‐possible (ARAP) surface modelling is widely used for interactive deformation of triangle meshes. We show that ARAP can be interpreted as minimizing a discretization of an elastic energy based on non‐conforming elements defined over dual orthogonal cells of the mesh. Using the intrinsic Voronoi cells rather than an orthogonal dual of the extrinsic mesh guarantees that the energy is non‐negative over each cell. We represent the intrinsic Delaunay edges extrinsically as polylines over the mesh, encoded in barycentric coordinates relative to the mesh vertices. This modification of the original ARAP energy, which we term iARAP , remedies problems stemming from non‐Delaunay edges in the original approach. Unlike the spokes‐and‐rims version of the ARAP approach it is less susceptible to the triangulation of the surface. We provide examples of deformations generated with iARAP and contrast them with other versions of ARAP. We also discuss the properties of the Laplace‐Beltrami operator implicitly introduced with the new discretization.

We provide a set of tools for generating planar embeddings of triangulated topological spheres. The algorithms make use of Schnyder labelings and realizers. A new representation of the realizer based on dual trees leads to a simple linear time algorithm mapping from weights per triangle to barycentric coordinates and, more importantly, also in the reverse direction. The algorithms can be implemented so that all coefficients involved are 1 or -1. This enables integer computation, making all computations exact. Being a Schnyder realizer, mapping from positive triangle weights guarantees that the barycentric coordinates form an embedding. The reverse direction enables an algorithm for fixing flipped triangles in planar realizations, by mapping from coordinates to weights and adjusting the weights (without forcing them to be positive). In a range of experiments, we demonstrate that all algorithms are orders of magnitude faster than existing robust approaches.

Abstract Extending the ARAP energy with a term that depends on the face normal, energy minimization becomes an effective stylization tool for shapes represented as meshes. Our approach generalizes the possibilities of Cubic Stylization: the set of preferred normals can be chosen arbitrarily from the Gauss sphere, including semi‐discrete sets to model preference for cylinder‐ or cone‐like shapes. The optimization is designed to retain, similar to ARAP, the constant linear system in the global optimization. This leads to convergence behavior that enables interactive control over the parameters of the optimization. We provide various examples demonstrating the simplicity and versatility of the approach.

The classical Stable Roommates problem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigate Stable Roommates with complete (i.e., every agent can be matched with any other agent) or incomplete preferences, with ties (i.e., two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms for Stable Roommates that are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity-Stable Roommates remains NP-complete.