Source-linked AI summary
Bijective Mappings Of Meshes With Boundary And The Degree In Mesh Processing
Yaron Lipman
TL;DR
Injectivity is hard to guarantee for simplicial mesh mappings, and orientation consistency alone is insufficient. The paper establishes three sufficient-condition sets, from a bijective-boundary criterion to linear constraints for a polytope and an added boundary-orientation condition. These yield bijectivity under their respective conditions, although the interior-injectivity result does not ensure boundary injectivity.
Problem
Method
The paper uses mapping degree and proves three sufficient-condition sets, including a bijective-boundary criterion and polytope constraints with an optional boundary-orientation requirement.
Source: §1 · p. 2, §2 · pp. 3–5Results
The conditions guarantee bijectivity when their respective assumptions hold, while the linear-constraint result without boundary orientation guarantees interior injectivity and target coverage but not necessarily boundary injectivity.
Source: §2 · pp. 3, 5Takeaways & Limitations
The linear constraints permit boundary maps to adjust while guaranteeing interior injectivity and coverage of the target polytope.
Source: §2 · pp. 3, 5The interior-injectivity result does not in general guarantee that the boundary map is injective.
Source: §2 · p. 5
Abstract
from arXiv · showhide
This paper introduces three sets of sufficient conditions, for generating bijective simplicial mappings of manifold meshes. A necessary condition for a simplicial mapping of a mesh to be injective is that it either maintains the orientation of all elements or flips all the elements. However, these conditions are known to be insufficient for injectivity of a simplicial map. In this paper we provide additional simple conditions that, together with the above mentioned necessary conditions guarantee injectivity of the simplicial map. The first set of conditions generalizes classical global inversion theorems to the mesh (piecewise-linear) case. That is, proves that in case the boundary simplicial map is bijective and the necessary condition holds then the map is injective and onto the target domain. The second set of conditions is concerned with mapping of a mesh to a polytope and replaces the (often hard) requirement of a bijective boundary map with a collection of linear constraints and guarantees that the resulting map is injective over the interior of the mesh and onto. These linear conditions provide a practical tool for optimizing a map of the mesh onto a given polytope while allowing the boundary map to adjust freely and keeping the injectivity property in the interior of the mesh. The third set of conditions adds to the second set the requirement that the boundary maps are orientation preserving as-well (with a proper definition of boundary map orientation). This set of conditions guarantees that the map is injective on the boundary of the mesh as-well as its interior. Several experiments using the sufficient conditions are shown for mapping triangular meshes. A secondary goal of this paper is to advocate and develop the tool of degree in the context of mesh processing.
1. Introduction
The paper develops practical sufficient conditions for bijective simplicial mesh maps, addressing the difficulty of guaranteeing injectivity and of prescribing a bijective boundary map. Its three condition sets range from a bijective-boundary requirement to linear constraints and, finally, boundary orientation preservation.
1. Introduction
- Earlier inversion results often require smoothness, local injectivity, or a bijective boundary map, which can be difficult to construct and may constrain energy-minimizing maps.Source: §1 · p. 1
- Consistent orientation of all elements is necessary for injectivity, but is not sufficient on its own.Source: §1 · p. 2
- The first condition set guarantees bijectivity when a non-degenerate, orientation-preserving map has a bijective boundary map.It generalizes global inversion theorems to meshes without requiring smoothness or local injectivity.Source: §1 · p. 2
- The second condition set uses linear constraints to guarantee injectivity in the mesh interior and coverage of the target polytope while allowing boundary maps to vary.It does not generally guarantee that the boundary map is injective.Source: §1 · p. 2
- The third condition set adds orientation preservation on boundary maps to guarantee injectivity over the entire mesh, including its boundary.Source: §1 · p. 2
- The paper also develops mapping degree for mesh processing; related sufficient conditions for disk-type triangular meshes do not extend to higher dimensions or non-convex targets.The cited related work is Floater, which generalizes Tutte’s drawing.Source: §1 · pp. 1–2
2. Preliminaries and Main Results
Consistent orientation of all mesh elements is necessary but insufficient for injectivity, so the paper establishes three sufficient-condition sets for mappings onto polytopes. These range from a prescribed bijective boundary map to linear boundary constraints, with a final condition ensuring injectivity on the boundary as well.
Necessary condition
- Injectivity requires non-degenerate elements with a consistent orientation, but consistent orientation alone does not guarantee injectivity.The paper gives triangular-mesh counterexamples and notes analogous examples for tetrahedral meshes.Source: §2 · p. 3
First sufficient-condition set
- A non-degenerate orientation-preserving simplicial map is bijective onto the target when its boundary map is bijective.This extends global inversion results to meshes without smoothness or local-injectivity requirements.Source: §2 · p. 3
Boundary assignment and constraints
- The second condition set assigns each boundary face to a target face while allowing it to slide, replacing a fixed boundary map with linear constraints.The constraints use affine closures of assigned target faces; for triangular meshes, edges lie on supporting lines and shared vertices may be restricted to polygon vertices.Source: §2 · pp. 3–4
Second sufficient-condition set
- With a topologically feasible boundary assignment and linear constraints, the map is injective in the mesh interior and covers the target polytope.The assignment requires an orientation-preserving boundary homeomorphism satisfying the assignment, though the map itself need not be known.Source: §2 · pp. 4–5
- Theorem 2 does not guarantee boundary injectivity, even when the map is injective in the interior and covers the target.The paper notes that this boundary failure is possible but rare in practice.Source: §2 · p. 5
Third sufficient-condition set
- Adding orientation preservation on the boundary makes the map a bijection between the mesh and target polytope.Source: §2 · p. 5
Degree in mesh processing
- The proof strategy develops mapping degree as a pre-image-counting tool, with degree counting how many times the mapped boundary wraps around a point.Source: §2 · p. 5
3. The Cycle Degree and Pre-image counting argument
The paper defines degree for simplicial maps restricted to cycles and uses it to relate boundary behavior to preimage counts. This counting argument supports the later sufficient conditions for injectivity.
Degree on cycles
- The paper defines degree for the projected map Φq restricted to a cycle, interpreting it as how many times the cycle wraps over the sphere Sq.It adopts a de Rham differential-forms approach to define the degree and prove its properties.Source: §3 · pp. 6–7
- For a cycle, the defined degree is integer-valued, agrees with Brouwer degree for piecewise-linear manifold cycles, and admits a preimage-counting characterization.The proposition also gives an additivity property for cycles.Source: §3 · p. 8
Pre-image counting argument
- For a simplex, the degree of its boundary is one when q lies in its image and zero when q lies outside.This follows from the degree's preimage-counting property and the convexity of the mapped simplex.Source: §3 · p. 9
- A non-degenerate orientation-preserving simplicial map is open, a property used to extend injectivity arguments across measure-zero sets.The cycle-degree counting argument is introduced to prove the sufficient injectivity conditions that follow.Source: §3 · pp. 6, 9
- The preimage count is bounded by the degree on the boundary, though the inequality can be strict, as one point has one preimage while its boundary degree is two.The example identifies the degree with the winding number of the image boundary polygon around the point.Source: §3 · p. 9
4. Sufficient conditions for Injectivity
The paper gives three sufficient-condition sets for mapping a compact mesh onto a polytope: a bijective boundary map, linear boundary constraints, and those constraints plus boundary orientation preservation. The latter two relax the need to prescribe a particular boundary map while retaining full bijectivity when boundary orientation is imposed.
Setting
- The conditions are presented for orientation-preserving maps; the orientation-reversing case is treated similarly..Source: §4 · p. 10
First set of sufficient conditions
- A non-degenerate orientation-preserving map with a bijective boundary map is a bijection from the mesh onto the target polytope.This extends classical global inversion conditions to the piecewise-linear mesh setting.Source: §4 · p. 10
Second set of sufficient conditions
- The linear-constraint formulation permits a collection of boundary mappings instead of requiring a fixed boundary map.The paper notes this flexibility can be useful when seeking lower-distortion mappings.Source: §4 · p. 10
- Linear constraints on assigned boundary faces, together with non-degeneracy and orientation preservation, guarantee injectivity in the mesh interior and coverage of the target polytope.The boundary assignment is topologically feasible, and the proof reduces to the bijective-boundary case using a homotopy argument.Source: §4 · pp. 10–11
Third set of sufficient conditions
- Adding orientation preservation on the boundary to those linear constraints guarantees a bijection between the mesh and the polytope.The second condition set guarantees interior injectivity and coverage but does not itself guarantee a bijective boundary map.Source: §4 · pp. 11–12
5. Numerical Experiments
The experiments apply orientation-preserving constraints and Theorem 2’s linear boundary conditions to optimize mesh mappings. Planar and surface examples show boundary-map optimization and its effect on Dirichlet energy.
5. Numerical Experiments
- Theorem 2 uses linear constraints and a topologically feasible assignment instead of requiring a prescribed bijective boundary map.The conditions guarantee exact target coverage and injectivity over the mesh interior.Source: §5 · pp. 12–13
- Vertex images determine each triangle’s affine map, while convex orientation-preservation constraints are optimized using second-order cone constraints.The method also bounds each map’s condition number, using K = 15 for planar mappings and K = 5 for the parameterization example.Source: §5 · pp. 12–13
- In four planar examples, Theorem 2’s boundary conditions optimize the boundary map to reduce Dirichlet energy compared with fixed uniform boundaries.Figure 7 also color-codes gradient norms, with red indicating large gradients and blue small gradients.Source: §5 · pp. 13–14, Figure 7 · p. 14
- A 3D surface mesh is parameterized onto a planar polygonal domain, with Theorem 2’s boundary conditions allowing the boundary map to be chosen for low Dirichlet energy.The assignment constrains the optimization.Source: §5 · p. 14
6. Conclusions
The paper uses degree of simplicial maps over cycles to formulate three sufficient conditions for bijective mesh mappings onto polytopes. The conditions support supplied or optimized boundary maps, but do not permit complete boundary-map freedom.
6. Conclusions
- Degree over cycles underpins three sufficient conditions for bijective simplicial mappings of meshes with boundary into polytopes.Figure 8 illustrates injective parameterization of a surface mesh onto a planar polygonal domain using Theorem 2’s conditions.Source: §6 · p. 14, Figure 8 · p. 15
- The conditions apply when mapping onto a known polytope with a supplied boundary map or one that needs optimization.Theorem 2’s linear conditions support the optimized-boundary case.Source: §6 · p. 15, Figure 8 · p. 15
- Boundary faces cannot slide between faces of the target polytope, limiting how freely the boundary map can be optimized.Allowing such movement could further reduce energy.Source: §6 · p. 15
- The paper treats meshes with boundary; bijective mapping of manifold meshes without boundary is left as a future topological problem.Source: §6 · p. 15
7. Appendix
The appendix proves that a non-degenerate orientation-preserving simplicial map is open. Its proof uses a point’s 1-ring and Brouwer degree to show nearby target points have pre-images.
7. Appendix
- For an interior point, the 1-ring is the union of d-dimensional simplices containing that point.The proof restricts attention to the intersection of this 1-ring with an open set around the point.Source: §7 · p. 16
- Lemma 2 states that a non-degenerate orientation-preserving simplicial map from a compact mesh into R^d is open.Source: §7 · p. 16
- The proof uses Brouwer degree and homotopy invariance to show nearby target points have pre-images, establishing openness.It first obtains positive degree at a point outside the images of lower-dimensional faces, then extends that degree to the neighborhood.Source: §7 · p. 16