Browsing by Author "Alexa, Marc"

Now showing 1 - 8 of 8
  • No Thumbnail Available
    Item
    ARAP Revisited Discretizing the Elastic Energy using Intrinsic Voronoi Cells
    (© 2023 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd., 2023) Finnendahl, Ugo; Schwartz, Matthias; Alexa, Marc; Hauser, Helwig and Alliez, Pierre
    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 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 , 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.
  • No Thumbnail Available
    Item
    Constrained Modelling of 3‐Valent Meshes Using a Hyperbolic Deformation Metric
    (© 2017 The Eurographics Association and John Wiley & Sons Ltd., 2017) Richter, Ronald; Kyprianidis, Jan Eric; Springborn, Boris; Alexa, Marc; Chen, Min and Zhang, Hao (Richard)
    Polygon meshes with 3‐valent vertices often occur as the frame of free‐form surfaces in architecture, in which rigid beams are connected in rigid joints. For modelling such meshes, it is desirable to measure the deformation of the joints' shapes. We show that it is natural to represent joint shapes as points in hyperbolic 3‐space. This endows the space of joint shapes with a geometric structure that facilitates computation. We use this structure to optimize meshes towards different constraints, and we believe that it will be useful for other applications as well.Polygon meshes with 3‐valent vertices often occur as the frame of free‐form surfaces in architecture, in which rigid beams are connected in rigid joints.
  • Thumbnail Image
    Item
    The Diamond Laplace for Polygonal and Polyhedral Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2021) Bunge, Astrid; Botsch, Mario; Alexa, Marc; Digne, Julie and Crane, Keenan
    We introduce a construction for discrete gradient operators that can be directly applied to arbitrary polygonal surface as well as polyhedral volume meshes. The main idea is to associate the gradient of functions defined at vertices of the mesh with diamonds: the region spanned by a dual edge together with its corresponding primal element - an edge for surface meshes and a face for volumetric meshes. We call the operator resulting from taking the divergence of the gradient Diamond Laplacian. Additional vertices used for the construction are represented as affine combinations of the original vertices, so that the Laplacian operator maps from values at vertices to values at vertices, as is common in geometry processing applications. The construction is local, exactly the same for all types of meshes, and results in a symmetric negative definite operator with linear precision. We show that the accuracy of the Diamond Laplacian is similar or better compared to other discretizations. The greater versatility and generally good behavior come at the expense of an increase in the number of non-zero coefficients that depends on the degree of the mesh elements.
  • Thumbnail Image
    Item
    Efficient Computation of Smoothed Exponential Maps
    (© 2019 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd, 2019) Herholz, Philipp; Alexa, Marc; Chen, Min and Benes, Bedrich
    Many applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.Many applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.
  • Thumbnail Image
    Item
    Fast Updates for Least-Squares Rotational Alignment
    (The Eurographics Association and John Wiley & Sons Ltd., 2021) Zhang, Jiayi Eris; Jacobson, Alec; Alexa, Marc; Mitra, Niloy and Viola, Ivan
    Across computer graphics, vision, robotics and simulation, many applications rely on determining the 3D rotation that aligns two objects or sets of points. The standard solution is to use singular value decomposition (SVD), where the optimal rotation is recovered as the product of the singular vectors. Faster computation of only the rotation is possible using suitable parameterizations of the rotations and iterative optimization. We propose such a method based on the Cayley transformations. The resulting optimization problem allows better local quadratic approximation compared to the Taylor approximation of the exponential map. This results in both faster convergence as well as more stable approximation compared to other iterative approaches. It also maps well to AVX vectorization. We compare our implementation with a wide range of alternatives on real and synthetic data. The results demonstrate up to two orders of magnitude of speedup compared to a straightforward SVD implementation and a 1.5-6 times speedup over popular optimized code.
  • Thumbnail Image
    Item
    Gauss Stylization: Interactive Artistic Mesh Modeling based on Preferred Surface Normals
    (The Eurographics Association and John Wiley & Sons Ltd., 2021) Kohlbrenner, Maximilian; Finnendahl, Ugo; Djuren, Tobias; Alexa, Marc; Digne, Julie and Crane, Keenan
    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.
  • Thumbnail Image
    Item
    Poisson Manifold Reconstruction - Beyond Co-dimension One
    (The Eurographics Association and John Wiley & Sons Ltd., 2023) Kohlbrenner, Maximilian; Lee, Singchun; Alexa, Marc; Kazhdan, Misha; Memari, Pooran; Solomon, Justin
    Screened Poisson Surface Reconstruction creates 2D surfaces from sets of oriented points in 3D (and can be extended to codimension one surfaces in arbitrary dimensions). In this work we generalize the technique to manifolds of co-dimension larger than one. The reconstruction problem consists of finding a vector-valued function whose zero set approximates the input points. We argue that the right extension of screened Poisson Surface Reconstruction is based on exterior products: the orientation of the point samples is encoded as the exterior product of the local normal frame. The goal is to find a set of scalar functions such that the exterior product of their gradients matches the exterior products prescribed by the input points. We show that this setup reduces to the standard formulation for co-dimension 1, and leads to more challenging multi-quadratic optimization problems in higher co-dimension. We explicitly treat the case of co-dimension 2, i.e., curves in 3D and 2D surfaces in 4D. We show that the resulting bi-quadratic problem can be relaxed to a set of quadratic problems in two variables and that the solution can be made effective and efficient by leveraging a hierarchical approach.
  • Thumbnail Image
    Item
    Properties of Laplace Operators for Tetrahedral Meshes
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Alexa, Marc; Herholz, Philipp; Kohlbrenner, Max; Sorkine-Hornung, Olga; Jacobson, Alec and Huang, Qixing
    Discrete Laplacians for triangle meshes are a fundamental tool in geometry processing. The so-called cotan Laplacian is widely used since it preserves several important properties of its smooth counterpart. It can be derived from different principles: either considering the piecewise linear nature of the primal elements or associating values to the dual vertices. Both approaches lead to the same operator in the two-dimensional setting. In contrast, for tetrahedral meshes, only the primal construction is reminiscent of the cotan weights, involving dihedral angles.We provide explicit formulas for the lesser-known dual construction. In both cases, the weights can be computed by adding the contributions of individual tetrahedra to an edge. The resulting two different discrete Laplacians for tetrahedral meshes only retain some of the properties of their two-dimensional counterpart. In particular, while both constructions have linear precision, only the primal construction is positive semi-definite and only the dual construction generates positive weights and provides a maximum principle for Delaunay meshes. We perform a range of numerical experiments that highlight the benefits and limitations of the two constructions for different problems and meshes.