Source-linked AI summary
Boundary First Flattening
Rohan Sawhney, Keenan Crane
TL;DR
Existing conformal flattening methods offer limited control over the flattened shape or require expensive nonlinear optimization. BFF constructs boundary data with the Cherrier formula and Poincare-Steklov operators, then extends the map over the interior. It provides boundary-controlled flattening with substantially lower computational cost and supports several target geometries and boundary features.
Problem
Existing conformal flattening methods provide little direct control over target shape or require expensive nonlinear optimization.
Method
BFF constructs compatible boundary curvature or length data, integrates it into a boundary curve, and extends the curve over the interior using shared sparse linear systems.
Results
BFF provides full target-shape control through a single sparse matrix factorization and delivers conformal flattenings about 50x cheaper than previous boundary-controlled techniques.
Takeaways & Limitations
BFF enables interactive editing or optimization of conformal maps with direct control over boundary length or angle, including sharp corners, cone singularities, unit-disk uniformization, and arbitrary target shapes.
Takeaways & Limitations
BFF applies directly only to disk-topology domains and provides flattening over Euclidean domains, though surfaces can be cut into disks.
Abstract
from arXiv · showhide
A conformal flattening maps a curved surface to the plane without distorting angles---such maps have become a fundamental building block for problems in geometry processing, numerical simulation, and computational design. Yet existing methods provide little direct control over the shape of the flattened domain, or else demand expensive nonlinear optimization. Boundary first flattening (BFF) is a linear method for conformal parameterization which is faster than traditional linear methods, yet provides control and quality comparable to sophisticated nonlinear schemes. The key insight is that the boundary data for many conformal mapping problems can be efficiently constructed via the Cherrier formula together with a pair of Poincare-Steklov operators; once the boundary is known, the map can be easily extended over the rest of the domain. Since computation demands only a single factorization of the real Laplace matrix, the amortized cost is about 50x less than any previously published technique for boundary-controlled conformal flattening. As a result, BFF opens the door to real-time editing or fast optimization of high-resolution maps, with direct control over boundary length or angle. We show how this method can be used to construct maps with sharp corners, cone singularities, minimal area distortion, and uniformization over the unit disk; we also demonstrate for the first time how a surface can be conformally flattened directly onto any given target shape.
1 INTRODUCTION
BFF addresses the limited shape control and high cost of conformal flattening by enabling boundary-controlled maps through a single sparse matrix factorization. It supports interactive editing and diverse target-boundary specifications, with a three-step boundary-first workflow.
- Conformal flattening supports applications including remeshing, comparative analysis, computational biology, physical simulation, sensor networks, and computational design.
- Existing linear methods provide no explicit target-shape control, while nonlinear methods offer more control at significantly greater cost.
- BFF provides full target-shape control through a single sparse matrix factorization.
- BFF supports automatic flattening, boundary length or angle manipulation, sharp corners, cone parameterization, unit-disk uniformization, and mapping to a given target shape.
- The algorithm solves for compatible boundary data, integrates it into a boundary curve, and extends that curve over the interior.
- Its computation uses three sparse linear problems connected by one nonlinear change of variables, with all linear problems sharing a fixed Laplace matrix.
2 RELATED WORK
Prior conformal flattening methods either leave boundary shape uncontrolled, require nonlinear optimization, or encode boundary data through difficult metric integrability constraints. BFF instead constructs a valid closed boundary curve before extending the map.
- Early methods such as LSCM and DCP solve linear conformal-flattening objectives, while SCP improves quality through a sparse eigenvalue problem.
- Free Boundary Conditions: Free-boundary methods select unique discrete solutions without explicit boundary constraints, despite the smooth problem admitting many conformal flattenings.
- Prescribed Boundary Length/Angle: Circle patterns control boundary direction, while discrete Ricci-flow methods such as CETM control both boundary length and direction.
- Traditional methods can produce different solutions without proper boundary conditions, whereas BFF provides a canonical map with minimal area distortion nearly identical to CETM.
- Prescribed Boundary Length/Angle: Nonlinear boundary-controlled methods repeatedly factor matrices, and linearized alternatives remain at least 30x slower than BFF and may exhibit significant artifacts.
- Uniformization: Uniformization through canonical domains can be more expensive than directly editing the boundary with BFF.
- 2D Shape Editing: Planar shape-deformation methods are generally unsuitable for conformal flattening because their boundary-element methods or closed forms apply only to planar domains.
- Previous boundary-controlled methods encode flattenings through metric data requiring nonlinear integrability, while BFF only requires data describing a closed boundary curve.
3 BACKGROUND
The paper develops conformal maps from disk-like surfaces to the plane, emphasizing how boundary length or curvature data constrain realizable target shapes. It introduces discrete curvature quantities and the geometric notation needed to formulate these controls.
- 3.2 Smooth Setting: The paper studies maps from disk-like surfaces to the complex plane and seeks control over the image of the boundary curve.The boundary image is parameterized separately from the source boundary to describe the target shape.
- 3.2 Smooth Setting: Conformal maps preserve angles while allowing a uniform change in length, represented by the log conformal factor u.Holomorphicity is expressed through the Cauchy-Riemann equation, and the conformal scale factor is e^u.
- 3.2.1 Conformal Maps: A conformal map cannot arbitrarily prescribe every boundary point, so the algorithm controls either boundary length or curvature density, but not both simultaneously.These quantities provide realizable boundary data that can be manipulated into different control schemes.
- 3.3 Discrete Setting: The surface is discretized as a manifold triangle mesh with disk topology, using boundary and interior vertex sets together with dual cells and dual boundary edges.The notation also defines edge, face, corner-angle, and primal or dual length quantities.
- 3.3.1 Discrete Curvature: In the discrete setting, Gaussian angle defect measures integrated curvature near interior vertices, while boundary exterior angles encode geodesic curvature.Boundary vertices have zero Gaussian curvature density in this formulation.
- 3.3.1 Discrete Curvature: Prescribing only exterior angles does not uniquely determine a polygon; target shape requires controlling angle change per unit boundary length.The analogous interior requirement is controlling angle defect per unit area for Gaussian curvature.
4 TOOLBOX
The toolbox formulates BFF through Dirichlet- and Neumann-Poisson problems on the cotan-Laplace matrix. A single sparse factorization supports repeated solves efficiently through block structure and backsubstitution.
- 4 TOOLBOX: BFF assembles basic building blocks around careful treatment of boundary conditions for the Dirichlet-Poisson problem.The toolbox prepares the operators used by the final algorithm.
- 4 TOOLBOX: The Neumann-Poisson problem specifies a source term in the domain and normal derivatives along the boundary.Its solution is unique only up to a constant, corresponding in BFF to global scale and translation.
- 4 TOOLBOX: On triangle meshes, integrating the Poisson equation over dual cells produces a matrix system involving the cotan-Laplace matrix A.The mass matrix is unnecessary when right-hand sides are already integrated quantities.
- 4 TOOLBOX: Partitioning vertices into interior and boundary sets yields block forms for Neumann problems and an interior solve for Dirichlet boundary values.The boundary Neumann vector stores integrated normal derivatives over dual boundary edges.
- Efficient Solution: A single sparse Cholesky factorization A = LL^T supports sequences of Dirichlet- and Neumann-Poisson solves.Subsequent problems are handled by backsubstitution at a small fraction of factorization cost.
- Efficient Solution: BFF’s computational bottleneck is the single factorization of A, unlike competing approaches lacking comparable amortized gains from prefactorization.The cited comparison notes that LSCM/SCP require dense factorization or iterative solvers without amortized prefactorization benefits.
4.2 Cherrier Formula
The Cherrier formula converts conformal curvature changes into linear density relations, while Poincare-Steklov operators provide compatible boundary data. Together these tools support accurate, reusable boundary construction for BFF.
- 4.2 Cherrier Formula: The Cherrier formula relates the conformal scale factor u to interior Gaussian curvature and boundary geodesic curvature.Its boundary condition is essential because BFF depends on boundary-controlled flattening.
- 4.2 Cherrier Formula: Existing algorithms largely neglect the general Cherrier boundary condition, so BFF linearizes the relation by multiplying through by area and boundary-length densities.This produces linear relationships between source and target curvature densities.
- 4.2 Cherrier Formula: BFF obtains boundary angles directly from the discrete Cherrier formula rather than rescaling edge lengths by u values.The resulting angles exactly satisfy conditions for boundary-loop closure and target cone-angle realization.
- 4.2 Cherrier Formula: Figure 5 compares finite-difference and Poincare-Steklov evaluations of Neumann data for prescribing an angle π on a cut hemisphere.Only the Poincare-Steklov construction produces the correct angle and a seamless map.
- 4.3 Poincare-Steklov Operators: A Poincare-Steklov operator maps one boundary-data representation of a solution to another representation yielding the same solution.BFF requires Dirichlet-to-Neumann and Neumann-to-Dirichlet operators.
- 4.3.1 Dirichlet to Neumann: The Dirichlet-to-Neumann map can be evaluated with one solve using the prefactored interior matrix and basic matrix operations.For Poisson problems, it is affine and computes boundary Neumann data from Dirichlet data and the source.
- 4.3.2 Neumann to Dirichlet: The Neumann-to-Dirichlet map solves the Neumann-Poisson equation and reads off boundary values, with a pseudoinverse accounting for the additive constant.The Hilbert transform then supplies conjugate-harmonic boundary data for holomorphic maps.
- 4.3.3 Hilbert Transform: The Hilbert-transform construction fixes one harmonic coordinate and solves a Neumann-Laplace problem for its conjugate in a least-squares conformal sense.The resulting boundary expression is variationally justified despite resembling a finite difference.
4.4 Interpolation
BFF extends a boundary curve into the interior using harmonic extension and harmonic conjugation, with each strategy preserving a different invariant.
- Interpolation: Harmonic extension independently solves Laplace problems for the real and imaginary boundary coordinates of the target curve.This exactly interpolates the prescribed boundary curve but is not guaranteed to be holomorphic.
- Interpolation: Harmonic conjugation harmonically extends one coordinate and derives the other from Hilbert-transform Neumann data.The resulting map is holomorphic but may not exactly interpolate both boundary components.
- Interpolation: The two extension strategies coincide when the boundary curve comes from a holomorphic map.In practice, their different invariants make them suitable for different applications.
4.5 Curve Integration
BFF reconstructs a closed boundary curve by integrating tangent directions while minimally adjusting lengths when discretization prevents exact closure.
- Curve Integration: BFF recovers a closed boundary curve from prescribed curvature and length data without directly optimizing vertex positions.It replaces a difficult nonlinear position-optimization problem with a convex length-adjustment problem.
- Curve Integration: The curve is formed by integrating unit tangents after rescaling their speeds to enforce closure.If the original curvature already describes a closed loop, the optimal speed remains unchanged.
- Discretization: Discrete boundary integration preserves desired exterior angles while finding lengths close to the target values.The polygon is constructed from prescribed angles and approximately matched edge lengths.
- Discretization: The optimal-length correction reduces to building and inverting a 2×2 matrix, after which vertex positions follow from cumulative tangent sums.The matrix operations are negligible compared with the main sparse solves.
- Discretization: Typical adjusted-to-target length ratios are 1 ± .001, and negative corrected lengths are not observed in practice.The method therefore makes only a very small practical adjustment to the desired edge lengths.
- Pipeline: The algorithmic pipeline obtains complementary boundary data, integrates it into a curve, and extends that curve over the interior.These are the three basic stages of BFF.
5 ALGORITHM
The BFF algorithm converts either boundary scale factors or curvature into compatible complementary data, constructs a closed loop, and computes its holomorphic extension.
- Algorithm: The input is a disk-topology triangle mesh with either desired boundary scale factors or target exterior angles.The output is a piecewise linear map approximating a smooth conformal map with the supplied boundary data.
- Algorithm: BFF computes complementary boundary data using the Dirichlet-to-Neumann map or its pseudoinverse.Scale factors produce compatible angles, while prescribed angles produce compatible scale factors.
- Algorithm: The method constructs a closed loop with the desired angles and rescaled lengths, then computes its holomorphic extension.The Cherrier formula makes the resulting boundary data compatible with a conformal flattening, up to discretization error handled during integration.
- Cost: The total computation requires one factorization of the real cotan-Laplace matrix followed by three backsolves.All remaining operations use O(|B|) work at boundary vertices.
6 APPLICATIONS
BFF supports conformal flattening tasks ranging from direct boundary editing and sharp corners to cone parameterization, disk uniformization, and arbitrary target shapes.
- Minimal area distortion: Prescribing zero boundary scale factors yields a conformal flattening with minimal area distortion.BFF results are virtually indistinguishable from CETM and can preserve symmetry better than SCP in the cited examples.
- Direct Editing: Users can directly manipulate boundary angles or target edge lengths and switch between these editing modes with the Dirichlet-to-Neumann map.A spline-based editor demonstrates nonrigid texture-atlas packing while remaining conformal.
- Sharp corners: For sharp-corner targets, harmonic extension exactly reproduces requested polygon angles, while both extension choices converge to holomorphic maps under refinement.This addresses undesirable rounding produced by the standard holomorphic extension.
- Cone parameterization: Cone parameterization first flattens a surface with isolated cone points, cuts through them, and applies BFF using the resulting boundary scale factors.The construction uses one length degree of freedom for corresponding cut edges to obtain a seamless map.
- Uniformization: BFF uniformizes disk-topology surfaces over the unit disk through a fixed-point iteration that repeatedly updates target angles.The procedure converges in about 10 iterations and produces results nearly identical to nonlinear methods.
- Arbitrary Curves: An iterative curvature-density scheme maps surfaces directly to arbitrary prescribed target shapes.Sampling the target curve according to current edge lengths empirically produces rapid convergence.
7 EVALUATION AND COMPARISONS
The evaluation compares boundary-controlled conformal flattening methods on quality, runtime, boundary fidelity, and practical scope. BFF matches comparable accuracy while offering substantially faster prefactorized updates and exact boundary-data guarantees, with disk-topology and Euclidean-target limitations.
- Quality and performance: BFF and competing boundary-controlled methods produce similar conformal quality on ideal meshes, while their update costs differ substantially.Figure 14 reports quasi-conformal error Qavg identical within 0.001 across methods.
- Boundary-controlled alternatives: Linearized boundary-control modifications can introduce artifacts on imperfect meshes because their least-squares layouts do not fully respect prescribed boundary constraints.This limitation is reported for both modified CPMS and LinABF-style approaches.
- Quality and performance: BFF’s average angle distortion decreases linearly with mean edge length h, while BFF and SCP have the smallest maximum distortion among evaluated methods.The refinement trend is shared across methods, but the maximum-distortion comparison favors BFF and SCP.
- Quality and performance: 30x faster updates than Modified CPMS and 50x faster than CETM are enabled by BFF prefactorization without sacrificing conformal quality.The reported speedups concern edited conformal flattenings relative to the next-fastest and fastest previously published boundary-controlled methods.
- Boundary data: BFF exactly realizes prescribed angles under harmonic extension and exactly preserves compatibility of lengths and angles along cuts.LinABF and CPMS lack these guarantees because their least-squares layout steps ignore prescribed boundary data.
- Scope and limitations: 6 of 588 SHREC 2011 meshes contained one or two flipped triangles, with total flipped area on the order of 10^-5 after normalization to unit radius.The authors note that such flips can often be fixed or addressed through remeshing or more expensive injective methods.
- Scope and limitations: BFF applies directly only to disk-topology domains and Euclidean targets, although arbitrary-topology surfaces can be cut into disks before flattening.The method does not target spherical or hyperbolic geometry.
A EXACT ANGLE SUMS
The appendix establishes exact angle-sum properties for BFF boundary data and cone parameterizations. These results follow from integrating the Cherrier formula and applying Gauss–Bonnet and divergence arguments.
- Exact angle sums: BFF’s complementary curvatures computed in Step I always sum to exactly 2π for any given scale factors u.The proof integrates the Cherrier formula over boundary dual cells and uses Gauss–Bonnet and the divergence theorem.
- Exact angle sums: Target angles computed for cone parameterization sum to exactly the desired cone angles Θ.The proof uses the relation between target curvature and the angle contributions of regions created by cuts.
B PSEUDOCODE
The pseudocode specifies BFF for disk-topology meshes using edge lengths, boundary data, sparse Laplace solves, boundary integration, and harmonic extension. It also gives the inputs and outputs for the main computational procedures.
- Basic BFF algorithm: The basic BFF algorithm accepts a disk with edge lengths, desired boundary edge lengths, and exterior angles summing to 2π, then outputs boundary vertex positions.Boundary vertices are traversed cyclically to construct the boundary curve from scaled tangents.
- Basic BFF algorithm: The full flattening procedure accepts a disk-topology triangle mesh and either boundary scale factors or exterior angles, then outputs a flattening f: V → C.The mesh is specified by edge lengths satisfying the triangle inequality in each face.
- Linear operators: BFF constructs a zero-Neumann Laplace matrix and uses its Cholesky factorization for repeated linear solves.The matrix is built from mesh edge lengths, and the factorization is reused by back-solving routines.
- Linear operators: The Dirichlet-to-Neumann procedure maps a source term and Dirichlet boundary data to Neumann data, while the Neumann-to-Dirichlet procedure performs the reverse mapping.Both procedures take the Cholesky factor of the zero-Neumann Laplace matrix as input.
- Interior extension: The boundary curve is extended over the interior by applying a Hilbert transform, back-solving for harmonic conjugation, and returning a + ib.The extension procedure takes a closed boundary loop and produces vertex positions for the flattening.
- Supporting routines: Remaining procedures compute angles and curvature, factor the sparse matrix, and solve linear systems using standard library routines.The listed routines include InteriorAngles, DiscreteCurvature, CholeskyFactor, and BackSolve.