Metric Optimization in Penner Coordinates

Ryan Capouellez¹, Denis Zorin¹

¹New York University

An implementation of Metric Optimization in Penner Coordinates.

Overview

This method generates an approximately isometric parameterization of an input obj mesh with parametric cone angle constraints. Retriangulation is often necessary to satisfy these constraints, so the initial mesh is intrinsically refined to produce an output mesh with a compatible parameterization.

Installation

To install this project on a Unix-based system, use the following standard CMake build procedure:

git clone https://github.com/geometryprocessing/penner-optimization.git
cd penner-optimization
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j 4

Usage

The core parameterization method is bin/optimize_metric. This executable takes the following arguments:

flag	description
mesh	Mesh filepath
cones	Target cone filepath
energy	Energy to optimize
direction	Direction to use for descent
--num_iter	Maximum number of iterations
--output	Output directory
--show_parameterization	Open polyscope viewer for the output

Supported parameter values for energy and direction are listed by bin/optimize_metric --help.

The input mesh must be a manifold surface with a single connected component. The cone file must be a list of newline separated target vertex cone angles satisfying the discrete Gauss-Bonnet condition. Methods to generate such a cone prescription will be provided soon. The output is a refined mesh with a parameterization and a file of metric coordinate values.

We also provide the executable bin/optimize_shear for generating parameterizations using explicit shear coordinate optimization (see paper for details). The executable arguments and output are the same, but the allowed directions are different. This method is in practice much slower to converge than the metric optimization method, but it does have standard formal convergence guarantees.

Figure Reproduction

Scripts to generate the figures of "Metric Optimization in Penner Coordinates" are included in figures.

The models (with cone angles) and cameras used in Metric Optimization in Penner Coordinates necessary for these scripts can be downloaded here; MPZ_closed, MPZ_open, MPZ_cut, and cameras must be copied to data/closed-Myles, data/open-Myles, data/cut-Myles, and data/cameras respectively.

A Conda environment must be activated (before compiling the code) with

conda env create -f environment.yml
conda activate penner-optimization

The figure bash scripts can then be run independently or in batch with

bash fig-all.sh

Note that most bash scripts generate an output directory with a JSON file specifying parameters for the parameterization and rendering pipeline python script scripts/_pipeline.py. Such JSON files can also be used for general batch parameterization and analysis.

Library

Many parametrization and mapping-related problems in geometry processing can be viewed as metric optimization problems, i.e., computing a metric minimizing a functional and satisfying a set of constraints, such as flatness.

Penner coordinates are global coordinates on the space of metrics on meshes with a fixed vertex set and topology, but varying connectivity, making it homeomorphic to the Euclidean space of dimension equal to the number of edges in the mesh, without any additional constraints imposed.

Crucially for practical applications, there is an efficient algorithm to convert these abstract Penner coordinates to a more familiar representation of a metric: a mesh with standard Euclidean logarithmic edge lengths. Moreover, this mesh only differs from the input mesh by a finite sequence of edge flips, and the resulting edge lengths are analytic functions of the Penner coordinates. We can thus formulate many constraints, such as vertex cone angles, on the mesh with Euclidean edge lengths as differentiable functions of Penner coordinates.

To engender future work in this exciting direction, we provide a library PennerOptimizationLib containing:

1. A representation of a mesh with Penner coordinates and cone angle constraints that supports:
   1. the computation of the corresponding mesh with Euclidean logarithmic edge lengths and the Jacobian of the logarithmic edge lengths with respect to Penner coordinates
   2. conformal projection to the cone angle constraints
2. Various energy functionals and constrained optimization methods for meshes with Penner coordinates
3. Layout and refinement methods to generate a parameterization for a mesh from arbitrary Penner coordinates, i.e., the parameterization is an embedding in the uv plane of the metric defined by the Penner coordinate.

Library Structure

• Field
  • Cross Field: Methods for generating cross fields as represented by four rotationally symmetric tangent vectors.
  • Facet Field: Methods for generating cross fields using legacy facet field file representations.
  • Field: Methods to generate field directions and cones from an nrosy field. (TODO: Move rosy and combing field functions here)
  • Forms: Methods for creating and manipulating one forms on a surface, represented as anti-symmetric halfedge values.
  • Frame Field: TODO: move assorted functions here to appropriate locations
  • Intrinsic Field: TODO: Needs cleanup
• Optimization
  • Core: Underlying methods for differentiable intrinsic metrics, including (a) area and angle values, and (b) length, Penner, shear, and conformal coordinates.
    • Area: Methods to compute the area of triangles from intrinsic lengths
    • Common: TODO
    • Cone Metric: Core representation of a differentiable intrinsic metric on an underlying halfedge mesh
    • Constraint: Methods to compute triangle inequality and differentiable cone angle constraints.
    • Flip Matrix Generator: Data structure to iteratively compute the change of coordinate matrix for intrinsic flips
    • Globals: (TODO: Put structs in relevant files)
    • Projection: Methods to project a metric conformally to cone constraints, and to project metric coordinate vectors to the tangent space of the constraint submanifold.
    • Reparametrization: Methods for changing edge and interior barycentric coordinates as determined by hyperbolic edge translations. (TODO: This name is pretty confusing in a parameterization library. Change to something better like barycentric, and move to parameterization)
    • Shear: Methods to compute the shear coordinates of a metric from Penner coordinates and shear coordinate bases, linearly independent from the conformal scaling space.
  • Metric Optimization: Methods for optimizing distortion energies for an intrinsic metric with constraints
    • Convergence: (TODO: a single function; move somewhere else)
    • Energies: Differentiable per-face energy functions with gradients for metric optimization
    • Energy Functor: Class for differentiable distortion measures supporting evaluation, gradients, and Hessians
    • Energy Weights: Methods to scale per-element values by element weights
    • Explicit Optimization: Methods to optimize a metric with angle constraints using an explicit basis complimentary to the conformal scaling space.
    • Implicit Optimization: Method to optimize distortion with constraints using a walk-on-manifold approach in a full space of metric coordinates using projection
    • Nonlinear Optimization: Methods to perform advanced nonlinear optimization, including conjugate gradient and L-BFGS-B
  • Parameterization: (TODO: move to top level. This is fundamental and common code.)
    • Interpolation: Data structures to compute pointwise maps between two intrinsic metrics.
    • Layout: Methods to layout a uv parameterization determined by intrinsic lengths (TODO: cleanup and documentation)
    • Refinement: Methods to refine a triangulation with an accompanying overlay layout sufficiently to ensure the parametrization does not have inverted elements. (TODO: replace refinement with simplification or something of this sort; check what is in the paper)
    • Translation: Method to compute hyperbolic translations determining a continuous map between two intrinsic metrics
    • Triangulation: Methods for triangulating self overlapping polygons in the plane
  • Util: TODO: Mostly utility for unit tests and validation. Redistribute this code.
• Holonomy: Library for parametrizing surfaces with full seamless constraints with arbitrary holonomy signatures
  • Core: Basic utilities for tracking dual loops on a surface
    • Boundary Basis: Basis loops for boundary alignment constraints
    • Common: Assorted utilities
    • Dual Lengths: Compute lengths of dual edges on a surface (TODO: move)
    • Dual Loop: Data structures for representing dual loops on a surface with efficient queries of edge and path intersections
    • Dual Segment: Minimal representation of dual paths on a surface as list of atomic face crossings
    • Homology Basis: Construct homology basis loops for a surface.
    • Quality: Compute triangle quality measures on a mesh (TODO: move)
    • Viewer: Assorted viewers
  • Holonomy:
    • Cones: Compute cones, as well as related queries and modification heuristics (TODO: move to field, and consolidate cone code here)
    • Constraints: Holonomy angle constraints, including cone and dual loop constraints.
    • Holonomy: Compute holonomy of dual loops on a surface with metric
    • Marked Penner Cone Metric: Differentiable cone metric with full holonomy signature constraints
    • Newton: Modified least squares Newton method for holonomy angle constraints
    • Rotation Form: Method to compute the rotation of a field across edges from a cross field (TODO: integrate with field code)
  • Similarity: TODO. It makes sense to keep this here, since it can satisfy full holonomy signature constraints, but is not integral to the codebase
• Feature: Library for parametrizing surfaces with both seamless and feature alignment constraints
  • Core
    • Boundary Path: Data structure for tracking the line of symmetry between two boundary vertices
    • Common: TODO
    • Component Mesh: Methods and data structures for splitting a disconnected mesh into separate components, as well as corresponding reindexing maps.
    • IO: Methods to write/read edges to/from file.
    • Quads: Methods to compute relevant quad mesh statistics (TODO: Only contains valence computation; Unify with other quad related code)
    • Union Meshes: Methods to combine collections of meshes into a single mesh with multiple components.
    • VF Corners: Methods for representing mesh edges using opposite corners.
    • Viewer: Assorted viewers
  • Dirichlet: Methods for enforcing hard and optimizing soft feature alignment constraints (TODO: consider renaming)
    • Angle Constraint Relaxer: Method to compute a relaxed angle constraint system that maintains total vertex angles while relaxing feature edge alignment.
    • Cone Perturber: Data structure to modify sector angle constraints for feature alignment
    • Constraints: Methods to compute feature aligned seamless constraints and associated Jacobians
    • Dirichlet Penner Cone Metric: Extension of the differentiable cone metric using Penner coordinates to include full feature aligned seamless constraints (TODO: finish documenting)
    • Optimization: Two-phase optimization method for alignment of relaxed angle constraint
  • Experimental: (TODO: Remove)
  • Feature: Methods to find
    • Error: Methods to compute feature alignment error
    • Features: Method to find feature edges on a surface and hard feature constraint subsets
    • Gluing: Methods to get cut mesh edge and vertex correspondences
  • Surgery: Methods to cut, refine, and stitch meshes and their parametrizations
    • Cut Mesh Layout: Methods to parameterize the uv components of a cut mesh
    • Cut Metric Generator: Data structure to generate fields and differentiable metrics for a mesh cut along feature lines.
    • Refinement: Data structure with limited support to refine the faces and edges of a mesh for feature alignment
    • Stitching: Method to stitch a mesh cut along feature lines and parametrized, possibly with edge refinement, into a single parametrized mesh.
  • Util: Union Find: (TODO: Move to global utility)

Citation

@article{capouellez:2023:penner,
author = {Capouellez, Ryan and Zorin, Denis},
title = {Metric Optimization in Penner Coordinates},
year = {2023},
issue_date = {December 2023},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {42},
number = {6},
issn = {0730-0301},
url = {https://doi.org/10.1145/3618394},
doi = {10.1145/3618394},
journal = {ACM Trans. Graph.},
month = {dec},
articleno = {234},
numpages = {19},
keywords = {cone metrics, conformal mapping, discrete metrics, intrinsic triangulation, parametrization, penner coordinates}
}