Triangular meshes are the most popular representation for discrete surfaces, due to their flexibility, efficiency, and direct support in rasterization hardware. Different applications demand different meshes, ranging from extremely coarse for collision proxies, to high-resolution and high-quality for accurate physical simulation. For this reason, the adaptation of a triangle mesh to a specific set of criteria (surface remeshing) is a core building block in geometry processing, graphics, physical simulation, and scientific computing.
In most applications, the triangular mesh is equipped with attributes, such as textures, displacements, physical properties, and boundary conditions (Figure 1). Whenever remeshing is needed, these properties must be transferred on the new mesh, a task which has been extensively studied in the literature and for which robust and generic solutions are still lacking (Section 2). Defining a continuous bijective map, more precisely, a homeomorphism where the inverse is also continuous, between two geometrically close piecewise-linear meshes of the same topology is a difficult problem, even in its basic form, when one of these meshes is obtained by adapting the other in some way (e.g., coarsening, refining, or improving triangle shape).a Common approaches to this problem are Euclidean projection [Jiao and Heath 2004], parametrization
Fig. 1. A low-quality mesh with boundary conditions (a) is remeshed using our shell (b) to maintain a bijection between the input and the remeshed output. The boundary conditions (arrows in (a)) are then transferred to the high-quality surface (c), and a non-linear elastic deformation is computed on a volumetric mesh created with TetGen (e). The solution is finally transferred back to the original geometry (d). Note that in this application setting both surface and volumetric meshing can be hidden from the user, who directly specifies boundary conditions and analyses the result on the input geometry.
on a common domain [Kraevoy and Sheffer 2004;Lee et al. 1998;Praun et al. 2001], functional maps [Ovsjanikov et al. 2012], and generalized barycentric coordinates [Hormann and Sukumar 2017]. However, the problem is not fully solved, as all existing methods, as we discuss in greater detail in Section 2, often fail to achieve bijectivity and/or sufficient quality of the resulting maps when applied to complex geometries. Our focus is on correspondences between meshes obtained during a remeshing procedure, instead of solving the more general problem of processing arbitrary mesh pairs. In this work, we propose a general construction designed to enable attribute mapping between geometrically close (in a welldefined sense) meshes by jointly constructing: (1) a shell S around triangle mesh T spanned by a set of prisms, inducing a volumetric vector field V in its interior and (2) a projection operator P that bijectively maps surfaces inside the shell to T , as long as the dot product of the surface face normals and V is positive (we call such a surface a section of S). Given a surface mesh T and its shell S, it is now possible to exploit the bijection induced by P in many existing remeshing algorithms by adding to them an additional constraint ensuring that the generated surface is a section of a given shell.
As long as the generated mesh is a section, the projection operator P can be used to transfer application-specific attributes. At a higher level, the middle surface of our shell can be seen as a common parametrization domain shared by sections within the shell: differently from other methods that map the triangle meshes to a disk, region of a plane, a canonical polyhedron, or orbifolds, our construction uses an explicit triangle mesh embedded in ambient space as the common parametrization domain. This provides additional flexibility since it is adaptive to the density of the mesh and naturally handles models with high genus, while being numerically stable under floating-point representation (and exact if evaluated with rational arithmetic). The downside is that it is defined only for sections contained within the shell. The construction and optimization of our shell, and corresponding bijective mapping, is computationally more expensive than remeshing-only methods: our algorithms takes seconds to minutes on small and medium sized models, and might take hours on the large models in our tests.
We evaluate the robustness of the proposed approach by constructing shells for a subset of the models in Thingi10k [Zhou and Jacobson 2016] and in ABC [Koch et al. 2019] (Section 4). We also integrate it in six common geometry processing algorithms to demonstrate its practical applicability (Section 5):
(1) Proxy. The creation of a proxy, high-quality remeshed surface to solve PDEs (e.g., to compute geodesic distances or deformations), avoiding the numerical problems caused by a low-quality input in commonly used codes. Bijective projection operators associated with a shell enable us to transfer boundary conditions to the proxy mesh, compute the solution on the proxy, and then transfer the solution back to the original geometry. (2) Boolean operations. The remeshing of intermediate results of Boolean operations, to ensure high-quality intermediate meshes while preserving a bijection to transfer properties between them. (3) Displacement Mapping. The automatic conversion of a dense mesh into a coarse approximation and a regularly sampled displacement height map. Our method generates a bijection that allows us to bake the geometric details in a displacement map. (4) Tetrahedral Meshing. The conversion of a surface mesh of low quality into a high-quality tetrahedral mesh, with bijective correspondence. (5) Geometric Textures. Generation of complex topological structures using volumetric textures mapped to the volumetric parametrization of a simplified shell defined by P. Our analysis on the initial shell also complements the literature on shell maps. (6) Nested Cages. A robust approach to generate a coarse approximation of a surface for collision checking, cage-based deformation, or multigrid approaches.
Our contributions are:
(1) An algorithm to build a prismatic shell and the corresponding projection operator around an orientable, manifold, selfintersection free triangle mesh with arbitrary quality;
(2) A new definition of bijective maps between close-by discrete surfaces;
(3) A reusable, reference implementation provided at https:// github.com/jiangzhongshi/bijective-projection-shell.
We review works in computer graphics spanning both the realization of maps for attribute transfer (Section 2.1), and the explicit generation of boundary cages (Section 2.2), which are closest to our work.
Transferring attributes is a common task in computer graphics to map colors, normals, or displacements on discrete geometries. The problem is deeply connected with the generation of UV maps, which are piecewise maps that allow to transfer attributes from the planes to surfaces (and composition of a UV map with an inverse may allow transfer between surfaces). We refer to [Floater and Hormann 2005;Hormann et al. 2007;Sheffer et al. 2006] for a complete overview, and we review here only the most relevant works.
Projection. Modifying the normal field of a surface has roots in computer graphics for Phong illumination [Phong 1975], and tessellation [Boubekeur and Alexa 2008]. Orthographic, spherical, and cage based projections are commonly used to transfer attributes, even if they often leads to artifacts, due to their simplicity [Community 2018;Nguyen 2007]. Projections along a continuously-varying normal field has been used to define correspondences between neighbouring surfaces [Ezuz et al. 2019;Kobbelt et al. 1998;Lee et al. 2000;Panozzo et al. 2013], but it is often discontinuous and non-bijective. While the discontinuities are tolerable for certain graphics applications (and they can be reduced by manually editing the cage), these approaches are not usable in cases where the procedure needs to be automated (batch processing of datasets) or when bijectivity is required (e.g., transfer of boundary conditions for finite element simulation). These types of projection may be useful for some remeshing applications to eliminate surface details [Ebke et al. 2014], but it makes these approaches not practical for reliably transferring attributes. Our shell construction, algorithms, and associated projection operator, can be viewed as guaranteed continuous bijective projection along a field.
Common Domains. A different approach to transfer attributes is to map both the source and the target to a common parametrization domain, and to compose the parametrization of the source domain with the inverse parametrization of the target domain to define a map from source to target. In the literature, there are methods that map triangular meshes to disks [Floater 1997;Tutte 1963], region of a plane [Aigerman et al. 2014[Aigerman et al. , 2015;;Campen et al. 2016;Fu and Liu 2016;Gotsman and Surazhsky 2001;Jiang et al. 2017;Litke et al. 2005;Maron et al. 2017;Müller et al. 2015;Rabinovich et al. 2017;Schmidt et al. 2019;Schüller et al. 2013;Smith and Schaefer 2015;Surazhsky and Gotsman 2001;Weber and Zorin 2014;Zhang et al. 2005], a canonical coarse polyhedra [Kraevoy and Sheffer 2004;Praun et al. 2001], orbifolds [Aigerman et al. 2017;Aigerman andLipman 2015, 2016], Poincare disk [Jin et al. 2008;Kharevych et al. 2006;Springborn et al. 2008;Stephenson 2005], spectral basis [Ovsjanikov et al. 2012[Ovsjanikov et al. , 2017;;Shoham et al. 2019], and abstract domains [Kraevoy and Sheffer 2004;Pietroni et al. 2010;Schreiner et al. 2004]. While these approaches allow mappings between completely different surfaces, this is a hard problem to tackle in full generality fully automatically, with guarantees on the output (even some instances of the problem of global parametrization, i.e. maps from a specific type of almost everywhere flat domains to surfaces, lack a fully robust automatic solution).
Our approach uses a coarse triangular domain embedded in ambient space as the parametrization domain, and uses a vector fieldaligned projection within an envelope to parametrize close-by surfaces bijectively to the coarse triangular domain. Compared to the methods listed above, our approach has both pros and cons. Its limitation is that it can only bijectively map surfaces that are similar to the domain, but on the positive side, it: (1) is efficient to evaluate, (2) guarantees an exact bijection (it is closed under rational computation), (3) works on complex, high-genus models, even with low-quality triangulations, (4) less likely to suffer from high distortion (and the related numerical problems associated with it), often introduced by the above methods. We see our method not as a replacement for the fully general surface-to-surface maps (since it cannot map surfaces with large geometric differences), but as a complement designed to work robustly and automatically for the specific case of close surfaces, which is common in many geometry processing algorithms, as well as serve as a foundation for generating such close surfaces (e.g., surface simplification and improvement, see Section 5) Attribute Tracking. In the specific context of remeshing or mesh optimization, algorithms have been proposed to explicitly track properties defined on the surface [Cohen et al. 1997;Dunyach et al. 2013;Garland and Heckbert 1997] after every local operation. By following the operations in reverse order, it is possible to resample the attributes defined on the input surface. These methods are algorithm specific, and provide limited control over the distortion introduced in the mapping. Our algorithm provides a generic tool that enables any remeshing technique to obtain such a map with minimal modifications.
The generation of shells (boundary layer meshes) around triangle meshes has been studied in graphics and scientific computing.
Envelopes. Explicit [Cohen et al. 1997[Cohen et al. , 1996] ] or implicit [Hu et al. 2016] envelopes have been used to control geometric error in planar [Hu et al. 2019a], surface [Cheng et al. 2019;Guéziec 1996;Hu et al. 2017], and volumetric [Hu et al. 2019b[Hu et al. , 2018] ] remeshing algorithms. Our shells can be similarly used to control the geometric error introduced during remeshing, but they offer the advantage of providing a bijection between the two surfaces, enabling to transfer attributes between them without explicit tracking [Cohen et al. 1997]. We show examples of both surface and volumetric remeshing in Section 5. Also, [Bajaj et al. 2002;Barnhill et al. 1992] utilize envelopes for function interpolation and reconstruction, where our optimized shells can be used for similar purposes. Shell Maps. 2.5D geometric textures, defined around a surface, are commonly used in rendering applications [Chen et al. 2004;Huang et al. 2007;Jin et al. 2019;Lengyel et al. 2001;Peng et al. 2004;Porumbescu et al. 2005;Wang et al. 2003Wang et al. , 2004]]. The requirement is to have a thin shell around the surface that can be used to map an explicit mesh copied from a texture, or a volumetric density field used for ray marching. Our shells are naturally equipped with a 2.5D parametrization that can be used for these purposes, and have the advantage of allowing users to generate coarse shells which are efficient to evaluate in real-time. The bijectivity of our map ensures that the volumetric texture is mapped in the shell without discontinuities. We show one example in Section 5.
Boundary Layer. Boundary layers are commonly used in computational fluid dynamics simulations requiring highly anisotropic meshing close to the boundary of objects. Their generation is considered challenging [Aubry et al. 2017[Aubry et al. , 2015;;Garimella and Shephard 2000]. These methods generate shells around a given surface, but do not provide a bijective map suitable for attribute transfer.
Collision and Animation . Converting triangle meshes into coarse cages is useful for many applications in graphics [Sacht et al. 2015], including proxies for collision detection [Calderon and Boubekeur 2017] and animation cages [Thiery et al. 2012]. While not designed for this application, our shells can be computed recursively to create increasingly coarse nested cages. We hypothesize that a bijective map defined between all surfaces of the nested cages could be used to transfer forces from the cages to the object (for collision proxies), or to transfer handle selections (for animation cages). [Botsch and Kobbelt 2003;Botsch et al. 2006] uses a prismatic layer to define volumetric deformation energy, however their prisms are disconnected and only used to measure distortion. Our prisms could be used for a similar purpose since they explicitly tesselate a shell around the input surface.
The closest works, in terms of applications, to our contribution are the recent algorithms enabling black-box geometry processing pipelines to solve PDEs on meshes in the wild. [Dyer et al. 2007;Liu et al. 2015] refines arbitrary triangle meshes to satisfy the Delaunay mesh condition, benefiting the numerical stability of some surface based geometry processing algorithms. These algorithms are orders of magnitude faster than our pipeline, but, since they are refinement methods, cannot coarsen dense input models. While targeting a different application, [Sharp et al. 2019] offers an alternative solution, which is more efficient than the extrinsic techniques [Liu et al. 2015] since it avoids the realization of the extrinsic mesh (thus naturally maintaining the correspondence to the input, but limiting its applicability to non-volumetric problems) and it alleviates the introduction of additional degrees of freedom. [Sharp and Crane 2020] further generalizes [Sharp et al. 2019] to handle non-manifold and non-orientable inputs, which our approach currently does not support. TetWild [Hu et al. 2019b[Hu et al. , 2018] ] can robustly convert triangle soups into high-quality tetrahedral meshes, suitable for FEM analysis. Their approach does not provide a way to transfer boundary conditions from the input surface to the boundary of the tetrahedral mesh. Our approach, when combined with a tetrahedral mesher that does not modify the boundary, enables to remesh low-quality surface, create a tetrahedral mesh, solve a PDE, and transfer back the solution (Figure 1). However, our method does not support triangle soups, and it is limited to manifold and orientable surfaces.
[Chazal and Cohen-Steiner 2005;Chazal et al. 2010] presents conditions for two sufficiently smooth surfaces to be isotopic. Specifically, the projection operator is a homeomorphism. [Mandad et al. 2015] extends this idea to make an approximation mesh that is isotopic to a region. However, they did not realize a map suitable for transferring attributes.
Our algorithm (Figure 2) converts a self-intersection free, orientable, manifold triangle mesh T = {V T , F T }, where V T are the vertex coordinates and F T the connectivity of the mesh, into a shell composed of generalized prisms S = {(B S , M S ,T S ), F S }, where B S , M S , T S are bottom, middle, and top surfaces of the shell, consisting of bottom, middle, and top triangles of the prisms, and F S is the connectivity of the prisms (Figure 3). The algorithm initially generates a shell S whose middle surface M S has the same geometry as the input surface T (possibly with refined connectivity), and then optimizes it while ensuring that T is contained inside and projects bijectively to M S . The shell induces a volumetric vector field V and a projection operator P in the interior of each of its prisms (Section 3.1). This output can be used directly in many geometry processing tasks, as we discuss in detail in Section 5.
We first introduce the definition of our projection operator P and the conditions required for bijectivity of its restrictions to sections of the shell (Section 3.1). We then define shell validity (Section 3.2), present our algorithm for creating an initial shell (Section 3.3) and optimizing it to decrease the number of prisms (Section 3.4). To simplify the exposition, we initially assume that our input triangle mesh does not contain singular points (defined in Section 3.3) and boundary vertices, and we explain how to modify the algorithm to account for these cases in sections 3.5 and 3.6. . Each tetrahedron has a constant vector field in its interior (pointing toward the top surface), which is parallel to the only pillar of the prism that contains the point.
Let us consider a single generalized prism ∆ in a prismatic layer S (Figure 4 left). The generalized prism ∆ is defined by the position of the vertices of three triangles, one at the top, with coordinates t 1 , t 2 , t 3 , one at the bottom, with coordinates b 1 , b 2 , b 3 , and one in the middle, implicitly defined by a per-vertex parameter
2, 3. We will call the top (bottom) łhalfž of the prism top (bottom) slab (we refer to Appendix E for an explanation on why we need two slabs). For brevity, we will refer to a generalized prism as a prism.
Decomposition in Tetrahedra. We decompose each prism ∆ into 6 tetrahedra (3 in the top slab and 3 in the bottom one, Figure 4 middle), using one of the patterns in [Dompierre et al. 1999, Figure 4]. The patterns are identified by the orientation (rising/falling) of the two edges cutting the side faces of the prism. While, for a single prism, any decomposition would be sufficient for our purposes, we need a consistent tetrahedralization between neighboring prisms to avoid inconsistencies in the projection operator. To resolve this ambiguity, we use the technique proposed in [Garimella and Shephard 2000]: we define a total ordering over the vertices of the middle surface of ∆ (naturally, we use the vertex id) and split (for each half of the prism) the face connecting vertices v 1 and v 2 with a rising edge if v 1 < v 2 and a falling edge otherwise. Forward and Inverse Projection. We define a piecewise constant vector field V inside the decomposed prism, by assigning to each tetrahedron T ∆ j , j = 1, . . . , 6, the constant vector field defined by the only edge of T ∆ j which is a oriented pillar of ∆ connecting the bottom surface to the top surface passing through the middle surface). That is, for any p ∈ T
(1) where i is the index of the vertex corresponding to the pillar edge of T ∆ j . Note that V is constant on each tetrahedron and might be discontinuous on the boundary: we formally define the value of V on the boundary as any of the values of the incident tetrahedra. This choice does not affect our construction. There is exactly one integral (poly-)line passing through each point of the prism if all the decomposed tetrahedra have positive volumes (Theorem 3.2). This allows us to define the projection operator P (p) for a point p ∈ ∆ as the intersection of the integral line f p (t ) of the vector field V passing through p, with the middle surface of ∆ (Figure 5). Intuitively, we can project any mesh that does not fold in each prism (Figure 6) to the middle surface. Formally, we introduce the following definition, to describe this property in terms of the triangle normals of the mesh.
With a slight abuse of the notation, for meshes and collections of prisms A and B, we use A ∩ B to denote the intersection of their corresponding geometry. Definition 3.1. A section T of a prism ∆ is a manifold triangle mesh whose intersection with ∆ is a simply connected submesh T ∩ ∆ whose single boundary loop is contained in the boundary of ∆, excluding its top and bottom surface, and such that for every point p ∈ T ∩ ∆ the dot product between the face normal n(p) and the vector field V (p) is strictly positive. Similarly, a triangle mesh T is a section of a shell S, if it is a section of all the prisms of S. ( P S 1 (x )) with x ∈ S 1 , of a direct and an inverse projection operator defines a bijection between two sections S 1 and S 2 .
Note that this definition implies that all sections are contained inside the shell. Additionally, the definition implies that the section does not intersect with either bottom or top surface. However, our definition allows for the bottom or top surface to self-intersect. The intersection of the shell does not invalidate the local definition of projection since it is defined per prism. Allowing intersections is crucial to an efficient implementation of our algorithm since it allows us to take advantage of a static spatial data structure in later stages of the algorithm (Section 3.4).
Theorem 3.2. If all 6 tetrahedra T ∆ j in a decomposition of a prism ∆ have positive volume, then the projection operator P defines a bijection between any section T of ∆ and the middle triangle of the prism (M in Figure 7).
Proof. We prove this theorem in Appendix A.1. □
The inverse projection operator P -1 is defined for a section T as the inverse of the forward projection restricted to T . It can be similarly computed by tracing the vector field in the opposite direction, starting from a point in the middle surface of the prism. Note that, differently from the inverse Phong projection [Kobbelt et al. 1998;Panozzo et al. 2013], whose solution depends on the root-finding of a quadric surface, our shell has an explicit form for the inverse and does not require a numerical solve. The combination of forward and inverse projection operators allows to bijectively map between any pair of sections, independently of their connectivity (Figure 7). An interesting property of our forward and inverse projection algorithm, which might be useful for applications requiring a provably bijective map, is that our projection could be evaluated exactly using rational arithmetic.
Shell, projection operator, section definitions, and the bijectivity condition (Theorem 3.2) are dependent on a specific tetrahedral decomposition, which depends on vertex numbering.
To ensure that our shell construction is independent from the vertex and face order, we define the validity of a shell by accounting for all 6 possible tetrahedral decompositions [Dompierre et al. 1999, Figure 4]. Definition 3.3. We say that a prismatic shell S is valid with respect to a mesh T if it satisfies two conditions for each prism. I1 Positivity. The volumes of 24 tetrahedra (Appendix A.2) corresponding to 6 tetrahedral decompositions are positive. I2 Section. T is a section of S for all 6 decompositions. If a shell is valid, from I1, I2, then by Theorem 3.2, it follows that any map between sections induced by the projection operator P is bijective.
I2 ensures that the input mesh is a valid section independently from the decomposition, that is, we require the dot product to be positive with respect to all three pillars of a prism inside the convex hull. An interesting and useful side effect of this validity condition is that it ensures the bijectivity of a natural nonlinear parametrization of the prism interior (Appendix D, Figure 25).
We now introduce an algorithm to compute a valid prismatic shell S = {(B S , M S ,T S ), F S } with respect to a given triangle mesh T = {V T , F T } such that T is geometrically identical to the middle surface of S. We assume that the faces of the triangle mesh are consistently oriented.
Extrusion Direction. The first step of the algorithm is the computation of an extrusion direction for every vertex of T . These directions are optimized to be pointing towards the outside of the triangle mesh (which we assume to be orientable), that is, they must have a positive dot product with the normals of all incident faces. More precisely, for a vertex v, we are looking for a direction d v such that d v • n f > 0 for each adjacent face f with normal n f . We can formulate this as the optimization problem max
(2)
A solution, if it exists, can be found solving the following quadratic programming problem (Appendix C)
with d v = x/∥x ∥ and C the matrix whose rows are the normals n f of the faces in the 1-ring N v of vertex v. Solutions not satisfying ∥x ∥ ≤ 1/ϵ needs to be discarded (Appendix C). The QP can be solved with an off-the-shelf solver [Cheshmi et al. 2020;Stellato et al. 2017], and in particular it can be solved exactly [Gärtner and Schönherr 2000] to avoid numerical problems. Note that the Problem (2) is studied in a similar formulation in [Aubry and Löhner 2008] but their solution requires tolerances in multiple stages of the algorithm to handle cospherical point configurations.
The admissible set of (2) might be empty for a vertex v, that is, no vector d v satisfies Cd v ≥ ϵ. In this case we call v a singularity. For example, Figure 12 shows a triangle mesh containing a singularity: there exist no direction whose dot product with the adjacent face normals is positive. To simplify the explanation, we assume for the remainder of this section that T does not contain singularities and also that it does not contain boundaries: we postpone their handling to sections 3.5 and 3.6. Proposition 3.4. Let T be a closed (without boundary) triangle mesh without singularities and N be a per-vertex displacement field satisfying CN i > 0 for every vertex v i of T . Then there exist a strictly positive per-vertex thickness δ i such that vertices t i and b i obtained by displacing v i by δ i in the direction of N i and in the opposite direction, define a shell that satisfies invariant I1.
Proof. We provide a proof in Appendix A.2. □ Initial Thickness. We first show that a strictly positive per-vertex thickness δ exists for a shell S with T as its middle surface, and then discuss a practical algorithm to realize it.
Theorem 3.5. Given a closed, orientable, self-intersection free triangle mesh T such that for all its vertices Problem (2) has a solution, a shell S exists such that T is the middle surface and there exist a strictly positive per-vertex thickness δ .
Proof. We provide a proof in Appendix A.3. □
To find a valid per-vertex thickness δ i to construct the top surface, we initially cast a ray in the direction of N for each vertex and measure the distance to the first collision with T (and cap it to a user-defined parameter δ max if no collision is found). An initial top mesh is built with this extrusion thickness; then we test whether any triangle in the top surface intersects T , through triangle-triangle overlap test [Guigue and Devillers 2003], and iteratively shrink δ i in this triangle by 20% until we find a thickness that prevents intersections between the input and the top surface. Analogously, we build the bottom shell along the opposite direction. Note that the thickness of a vertex for the top and bottom surface can be different.
Validity of the Initial Shell. Proposition 3.4 and Theorem 3.5 ensure that the initial shell constructed using a displacement field N obtained by solving (3), satisfies property I1. However, T might not formally satisfy the conditions for being a section of S, despite being identical to the middle surface of S, due to our definition of the projection operator P. The reason for this can be seen in Figure 8. After the initialization, the middle surface is the input mesh. Thus every prism ∆ corresponds to a triangle T ∆ of T . The intersection ∆ ∩ T , required to check if T is a section of ∆ (Definition 3.1) contains points from both T ∆ and its 1-ring neighborhood.
The projection operator (and thus the definition of the section) is based on all tetrahedral decompositions of ∆; it is possible that multiple tetrahedra (with different vector field values in V) overlap on the boundary of ∆.
Depending on the dihedral angles in the mesh T , it is possible that the dot product between one of the pillars (orange in Figure 8) and the face normals of some of the triangles from 1-ring neighborhood (green in Figure 8) is negative. While it may seem that this problem could be addressed by changing the definition so that each edge is assigned to one of the incident triangles, so that the field direction only in one incident tetrahedron needs to be considered, this problem is more significant than it may seem, as it leads to instability under small perturbations (e.g., due to floating-point rounding of coordinates). Such small perturbations can change the set of triangles intersecting a prism and thus violate the validity of the shell and, consequently, the bijectivity of P. We propose instead Fig. 8. The vector field aligned with the pillar edge (orange) has a negative dot product with the green triangle normal; the tetrahedron with this field direction meets the green triangle at the red vertex. As a consequence, the mid-surface is not a section. After topological beveling, the shell becomes valid since the dot product between the green normal and the new pillar (purple) is positive.
Fig. 9. The beveling patterns used to decompose prisms for which T is not a section.
to refine T , without changing its geometry, so that the shell corresponding to the refined mesh satisfies I2 (i.e., its middle surface is a section).
Topological Beveling. We identify a prism ∆ v for which I2 does not hold and use a beveling pattern [Conway et al. 2016;Coxeter 1973;Hart 2018] to decompose ∆ v in a way that T becomes a section for all 6 decompositions (I2). We refer to this operation as topological beveling, as it does not change the geometry of the mesh, only its connectivity (Figure 10). We use the pattern in Figure 9a for ∆ v , and we use the other two patterns (b) and (c) on the adjacent prisms to ensure valid mesh connectivity. The positions of the vertices are computed using barycentric coordinates (we used t = 0.2, i.e., the orange dot is at 1/5 of the horizontal edge), and the normals of the newly inserted vertices are copied from the closest vertex (in Figure 9, the internal vertices have the normal of the triangle corner with the same color).
Theorem 3.6. Suppose T is the middle surface of S, and neither T S or B S intersects with T . After topological beveling, I2 holds, that is, T is a section of the shell S for all 6 decompositions.
Proof. We provide a proof in Appendix A.4. □
Output. The output of this stage is a valid shell with respect to T (Section 3.2), that is, it satisfies I1 and I2.
During shell optimization, we perform local operations (Figure 11) on a valid shell to reduce its complexity and increase the quality. Before applying every operation, we check the validity of the operation to ensure that: (1) the resulting middle surface will be manifold [Dey et al. 1999] and (2) the shell will be valid with respect to T (to ensure a bijective projection). We forbid any operation that does not pass these checks. We would like to remark that, while there are different choices to guide the shell modification, we experimentally discovered that allowing shell simplification and optimization consistently leads to thicker shells with a richer space of sections.
Theorem 3.7. Let S be a valid shell with respect to a mesh T and let C = {∆ i } i ∈I ⊂ S be a collection of prisms such that the middle surface M C of C is a simply connected topological disk.
Let O be an operation replacing C with a new collection of prisms C ′ = {∆ ′ i } i ∈I ′ , preserving both geometry and connectivity of the sides of the prism collection C, and ensuring that M C ′ is a simply connected topological disk.
If these three assumptions hold:
(1) property I1 holds for C ′ , (2) the top and bottom surfaces of
i is a simply connected topological disk. In other words, T is a section of the new shell S ′ obtained by applying the operation O to S.
Proof. We prove this theorem in Appendix A.5. □
We note that assumption (2) in Theorem 3.7 prevents the input surface from crossing the bottom/top surface, thus avoiding it to move in the interior of a region covered by more than one prism.
Our local operations (satisfying the definition of O in Theorem 3.7) are translated from surface remeshing methods [Dunyach et al. 2013] since our shell can be regarded as a triangle mesh (middle surface) extruded through a displacement field N . All the local operations described below directly change the middle surface, and consequently affect the extruded shell. After every operation, the middle surface is recomputed by intersecting T with the edges of the prisms in S. Shell Quality. We measure the quality of the shell S using the MIPS energy [Hormann and Greiner 2000] of its middle surface M S .
For each triangle T of the middle surface, we build a local reference frame, and compute the affine map J T transforming the triangle into an equilateral reference triangle in the same reference frame. The energy is then measured by
.
This energy is invariant to scaling, thus allowing the local operations to coarsen the shell whenever possible while encouraging the optimization to create well-shaped triangles. Good quality of the middle surface decreases the chances, for the subsequent operations, to violate the shell invariants.
Shell Connectivity Modifications. We translate three operations for triangular meshes to the shell settings (Figure 11 top). Edge collapse, split, and flip operations can be performed by simultaneously modifying the top and bottom surfaces and retrieve the positions for the middle surface through the intersection. We only accept the operations if they pass the invariant check.
Vertex Smoothing. Due to the additional degree of freedom on vertex-pairs (position, direction, and thickness), we decompose the smoothing operations into three components (Figure 11 bottom). Pan moves the positions of the top and bottom vertex at the same time, minimizing the MIPS quality of the middle surface. Neither the thickness or direction will be changed. Rotate re-aligns the local direction to be the average of the neighboring ones while keeping the position of the middle vertex fixed. Zoom keeps the direction and position of the middle vertex, and set the thickness of both top and bottom to be 1.5 times of the neighbor average, capped by the input target thickness.
Invariant Check. We use exact orientation predicates [Shewchuk 1997] to make sure all the prisms satisfy positivity (I1). Further, we ensure that the original surface T is not intersecting with the bottom and top surface, except at the prescribed singularities. The check is done using the triangle-triangle overlap test [Guigue and Devillers 2003], accelerated using a static axis-aligned bounding box tree constructed from T . To accelerate the checks for normal condition, for each prism ∆ i , we maintain a list triangles overlapping with its convex hull (an octahedron), and check their respective normals against all the three pillars of ∆ i . These three checks ensure that the three conditions in Theorem 3.7 are satisfied. Note that the vertex smoothing operation is continuous, in the sense that any point between the current position and the optimal one improves the shell. We, however, handle it as a discrete operation to check our conditions: we attempt a full step, and if I1 is not satisfied, we perform a bisection search for a displacement that does. We avoid bisection for the other two conditions since they are expensive to evaluate.
Projection Distortion. An optional invariant to maintain (not necessary for guaranteeing bijectivity, but useful for applications), is a bound on the maximal distortion D P (∆) of P for a prism ∆. We measure it as the maximal angle between the normals of the set C containing the faces of T intersecting ∆ and V:
where ∠ is the unsigned angle in degrees. This quantity is bounded from below by the smallest dihedral angle of T , making it impossible to control exactly. However, we can prevent it from increasing by measuring it and discarding the operations that increase it. In our experiments, we use a threshold of 89.95 degrees.
Scheduling and Termination. Our optimization algorithm is composed of two nested loops. The outer loop repeats a set of local operations until the face count between two successive iteration decreases by less than 0.01%. In the inner loop we: (1) flip every edge of S decreasing the MIPS energy and avoiding high and low vertex valences [Dunyach et al. 2013] ; (2) smooth all vertices which include pan, zoom, and rotate; and (3) collapse every edge of S not increasing the MIPS energy over 30. Note that for every operation, we check the invariants, the projection distortion, and manifold preservation and reject any operation violating them. After the outer iteration terminates (i.e. the shell cannot be coarsened anymore), we further optimize the shell with 20 additional iterations of flips and vertex smoothing.
Singularities, i.e. vertices of T for which the constraints set of problem (2) is empty, are surprisingly common in large datasets (Figure 12 shows an example). For instance, in our subset of Thingi10k [Zhou and Jacobson 2016], although only 0.01% vertices are singular, 8% of the models have at least one singular point. This has been recently observed as a limitation for the construction of nested cages [Sacht et al. 2015, Appendix A], and it is a well-known issue when building boundary layers [Aubry et al. 2017[Aubry et al. , 2015;;Garimella and Shephard 2000]. There are two main situations that give rise to singular points. The first one naturally generates a singular point when more than two ridge-lines meet (e.g., figures 12 and 30), thus making the point a feature point. The second one is a pocket-like mesh artifact, often produced as a result of mesh simplification (Figure 13).
While singularities might seem fixable by applying local smoothing or subdivision as a pre-process, it is not desirable in the case of a feature point, and is likely to introduce self-intersection or more serious geometric inconsistency. Therefore, to the above reasons and observing that they are very uncommon, we propose to extend our theory (Appendix B) and algorithm to handle isolated singularities by pinching the thickness of the shell. Note that in the rare case where two singular points are sharing the same edge, they are automatically separated by our topological beveling.
Pinching. We extend our definition of the shell by allowing it to have zero thickness on singularities, thus tessellating the degenerate prism with 4 instead of 6 tetrahedra (Figure 13). We further remark that these isolated points must be excluded from Definition 3.1. In the implementation, this requires to change the intersection predicates to skip the singular vertices. With this change, the singularity becomes a trivial point of the projection operator P, and the rest of our shell can still be used in applications without further changes. Since singularities tends to be isolated (they are usually located at the juncture of multiple sharp features), this solution has minimal effects on applications: for example, when our shell is used for remeshing, pinching the shell at singularities will freeze the corresponding isolated vertices while allowing the rest of the mesh to be freely optimized.
The topological beveling algorithm is changed most significantly: for singularities, there is no pillar to copy from. In this case, we apply an additional edge split, to use the pattern in the inset (with the singularity marked by a white dot) in the one-ring neighborhood of the singularity. The newly inserted vertices lie either inside a triangle (uncircled red and orange dots), or in the interior of an edge (circled red and orange dots). Therefore, we assign to the orange vertices the average normal of the two adjacent triangles, and to red the pillar of the connected orange one.
Side View A B D A B D A' Fig. 14. AA ′ is a direction with positive dot product with respect to all its neighboring faces. However, no valid shell can be built following that direction.
Thingi10k #40010 Fig. 15. An example of a mesh with boundary.
Additionally, the edges connecting singularities will always be beveled/split after beveling. Therefore no prism will contain more than one singular point. We discuss the technical extensions for our proofs to shells with pinched prisms in Appendix B.
We introduced our algorithm, assuming that the input mesh does not have boundaries. We will now extend our construction to handle this case, which requires minor variations to our algorithm.
For some vertices on the boundary, it might be impossible to extrude a valid shell (Figure 14), even if problem (2) has a solution, as Theorem 3.5 does not apply in its original form. We identify such cases by connecting every edge in the 1-ring neighborhood of the boundary vertex to the extruded point and check if they collide with the existing 1-ring triangles (e.g., the triangle A ′ AB intersects the existing input triangle in Figure 14). If it is the case, we consider this vertex as a singularity, and we pinch the shell. Note that this is an extremely rare case and, in our experiments, we detected it only for models where the loss of precision in the STL export introduces rounding noise on the boundary.
Once we pinch all boundary singularities, our construction extends naturally to the boundary. The only necessary modification is in the shell optimization (Section 3.4), where we skip all operations acting on boundary vertices to maintain the bijectivity of the induced projection operator (Figure 15). We thus freeze these vertices and never allow them to move or be affected by any other modification of the shell. Note that, in certain applications, it might also be useful to freeze additional non-boundary vertices to ensure that these remain on the middle surface during optimization (e.g., to exactly represent a corner of a CAD model).
Our algorithm is implemented in C++ and uses Eigen [Guennebaud et al. 2010] for the linear algebra routines, CGAL [The CGAL Project ACM Trans. Graph.,Vol. 39,No. 6, Article 1. Publication date: December 2020. [Lévy 2015] for predicates and spatial searching, and libigl [Jacobson et al. 2016] for basic geometry processing routines. We run our experiments on cluster nodes with a Xeon E5-2690 v2 @ 3.00GHz. The reference implementation used to generate the results is attached to the submission and will be released as an open-source project.
Robustness. For each dataset, we selected the subset of meshes satisfying our input assumptions: intersection-free, orientable, manifold triangle meshes without zero area triangles (tested using a numerical tolerance 10 -16 ). We test self-intersections by two criteria: a ball of radius 10 -10 around each vertex does not contain non-adjacent triangles; and all the dihedral angles are larger than 0.1 degrees.
We tested our algorithm on two datasets: (1) Thingi10k dataset [Zhou and Jacobson 2016] containing, after the filtering due to our input assumptions, 5018 models; and (2) the first chunk of for the ABC dataset [Koch et al. 2019] with 5545 models. The only usercontrolled parameter of our algorithm is the target thickness of our shell; in all our experiments (unless stated otherwise), we use 10% of the longest edge of the bounding box. In Figure 16, we show how the target thickness influences the usage of the shell: a thicker shell provides a larger class of sections, thus accommodates more processing algorithms, while a thinner one offers a natural bound on the geometric fidelity of the sections.
Our algorithm successfully creates shells for all 5018 models for Thingi10k and 5545 for ABC. We show a few representative examples of challenging models for both datasets in Figure 17, including models with complicated geometric and topological details. In all cases, our algorithm produces coarse and thick cages, with a bijective projection field defined.
We report as a scatter plot the number of output faces, the timing, and the memory used by our algorithm (Figure 18). In total, the number of prisms generated by our algorithm is 7% and 2% of the number of input triangles for the Thingi10k and ABC dataset respectively and runs with no more than 4.7 GB of RAM. The generation and optimization of the shell takes 5min and 59s in average and up to 8.6 hours for the largest model. 50% of the meshes finish in 3 minutes and 75% in 6 minutes and 15 seconds.
Comparison to Simple Baselines. In Figure 19 we compare to two baseline methods based on [Garland and Heckbert 1998]. For each method, we generate a coarse mesh, uniformly subdivide it for visualization purposes, and query the corresponding spatial position on the original input to form the subdivided mesh. The UV based method is a conventional way of establishing correspondence in the context of texture mapping. However, the robust generation of a UV atlas satisfying a variety of user constraints is still an open problem. We use the state-of-the-art methods [Jiang et al. 2017;Li et al. 2018] to generate a low-distortion bijective parametrization, and use seam-aware decimation technique [Liu et al. 2017] to generate the coarse mesh. Due to the complex geometry and the length of the seam (Figure 19 second figure), the simplification is not able to proceed beyond the prescribed seam while maintaining the bijectivity, making the pipeline inadequate especially for building computational domains.
We also set up a baseline of the Naive Cage method by creating a simplified coarse mesh with [Garland and Heckbert 1998] and use Phong projection to establish the correspondence [Kobbelt et al. 1998;Panozzo et al. 2013]. Such attribute transfer is not guaranteed to be bijective; some face may not be projected (Figure 19 third image). With our method, we can generate a coarse mesh while having a low-distortion bijective projection (Figure 19 fourth image).
Numerical accuracy. To evaluate the numerical error introduced by our projection operator when implemented with floating-point arithmetic, we transfer the vertices of the input mesh to the middle surface and inverse transfer them from the middle surface back to the input mesh. We measure the Euclidean distance with respect to the source vertices (Figure 20). We compare the same experiment with the Phong projection [Kobbelt et al. 1998]. This alternative approach exhibits distance errors up to 10 -5 even after ruling out the outliers for which the method fails due to its lack of bijectivity. The maximal error of our projection is on the order of 10 -8 ; this error could be completely eliminated (for applications requiring an exact bijection) by implementing the projection operator and its inverse using rational arithmetic.
Using our shell S, we implement the following predicates and functions:
• is_inside(p): returns true if the point p ∈ R 3 is inside S.
• is_section(T ): returns true if the triangle mesh T is a section of S. • P (p): returns the prism id (pid), the barycentric coordinates (α, β) in the corresponding triangle of the middle surface, and the relative offset distance from the middle surface (h, which is -1 for the bottom surface, and 1 for the top surface) of the projection of the point p • P -1 (pid, α, β, h) is the inverse of P (p).
• P T (tid, α, β ) = P (q), where q is the point in the triangle tid of the mesh T , with barycentric coordinates α, β. • P -1 T (pid, α, β ) is the inverse of P T . As explained in Section 3, our shell may self-intersect and we opted to simply exclude the overlapping regions. In practice this affects only the function is_inside(p) which needs to check if p is contained in two or more non-adjacent prisms.
These functions are sufficient to implement all applications below, demonstrating the flexibility of our construction and how easy it is to integrate in existing geometry processing workflows. ACM Trans. Graph.,Vol. 39,No. 6, Article 1. Publication date: December 2020. Remeshing. We integrated our shell in the meshing algorithm proposed in [Dunyach et al. 2013] by adding envelope checks ensuring that the surface is a section after every operation. After simplification, we can use the projection operator to transfer properties between the original and remeshed surface (e.g., figures 22, 23). Since the remeshed surface is a section, a very practical side effect of our construction is that the remeshed surface is guaranteed to be free of self-intersections, As shown in Figure 21, the constraints enforced through our shell prevents undesirable geometric configurations (intersections, pockets, or triangle flips).
Proxy. A particularly useful application of our shell is the construction of proxy domains for the solutions of PDEs on low-quality meshes. Additionally, by specifying the target thickness parameter (Figure 16), we are able to bound the geometry approximation error to the input as well. Using our method, we can (1) convert a low-quality mesh to a proxy mesh with higher quality and desired density, (2) map the boundary conditions from the input to the proxy using the bijective projection map, (3) solve the PDE on the proxy (which is a standard mesh), and ( 4) transfer back the solution on the input surface (Figure 22). Our algorithm can be directly used to solve volumetric PDEs. by calling an existing tetrahedral meshing algorithm between steps 2 and 3 (figures 1, 23). In this case, we control the geometric error by setting the target thickness (we use 2% of the longest edge of the bounding box).
Boolean Operations. The mesh arrangements algorithm enables the robust and exact (up to a final floating-point rounding) computation of Boolean operations on PWN meshes [Zhou et al. 2016]. However, the produced meshes tend to have low triangle quality that might hinder the performance of downstream algorithms. By interleaving a remeshing step performed with our algorithm after every operation, we ensure high final quality and more stable runtime. The composition of the bijections enables us to transfer properties between different nodes of the CSG tree (Figure 24). Displacement Mapping. The middle surface of the shell is a coarse triangular mesh that can be directly used to compress the geometry of the input mesh, storing only the coarse mesh connectivity and adding the details using normal and displacement maps (Figure 25). A common way to build such displacement is to project [Collins and Hilton 2002;Kobbelt et al. 1998] the dense mesh on the coarser version. As shown in Appendix D, our method guarantees that this natural projection is also bijective as long as the coarse mesh is a section. This alleviates the loss of information even on challenging geometry configurations, and our shell can thus be used to automate the creation of projection cages and displacement maps.
Geometric Textures. The inverse projection operator provides a 2.5D parametrization around a given mesh and can be used to apply a volumetric texture (Figure 26). Note that we build the volumetric texture on the simplified shell, while still being able to bijectively transfer the texture coordinates.
Input with Self-Intersections. Up to this point, we assumed that our input meshes are without self-intersections. This requirement is necessary to guarantee a bijection between any section (e.g., the input mesh) and the middle surface. Such bijection is essential for a key target application, the transfer of boundary conditions for solving PDEs on meshes or mesh-bounded domains.
However, our method can be easily extended to meshes containing self-intersections, broadening the class of meshes it can be applied to, at the cost of making the resulting shell usable in fewer application scenarios: for example, if it is used for remeshing, it will likely generate a new surface that still contains self-intersections.
If T contains self-intersections, our algorithm can be trivially extended to generate a shell which will be locally injective, and the bijectivity of the mapping between sections still holds but with respect to the immersion. The only change required is to modify the invariance checks (Section 3.4): we have to replace the global intersection check with checking whether local triangles overlap with the current prisms. Figure 27 shows an example of a mesh T with self-intersections, the generated shell, and the isolines of geodesic transferred on the coarser middle surface.
Resolving Shell Self-Intersections. For certain applications it might be preferable to have a shell whose top and bottom surfaces do not self-intersect: for example, in the construction of nested cages [Sacht et al. 2015] (useful for collision proxies and animation cages), we want to iteratively build nested shells while ensuring no intersections between them (Figure 28). With a small modification, our algorithm can be used to generate nested cage automatically and robustly, with the additional advantage of being able to map any quantity bijectively across the layers and to the input mesh. In contrast, [Sacht et al. 2015] does not provide guarantees on the success (e.g., the reference implementation of [Sacht et al. 2015] fails on Figure 19, probably due to the presence of a singularity).
To resolve the self-intersections of the top (bottom) surface, we identify the regions covered by more than one prism by explicitly testing intersections between the tetrahedralized prisms, accelerated using [Zomorodian and Edelsbrunner 2000]. For every detected prism, we reduce the thickness by 20%, and iterate until no more intersections are found. Differently from the procedure in Section 3.3, where reducing the thickness of the shell always maintains the validity of the shell, at this stage, the shrinking of the shell may make the shell invalid, since T may not be contained anymore in S. Whenever this happens, we perform one step of red-green refinement [Bank et al. 1983] on the regions we wish to thin, and we iterate until we succeed. This procedure is guaranteed to terminate since, on the limit of the refinement, the middle surface will be geometrically identical to T , and thus Theorem 3.5 holds. In the worst case, the procedure terminates when the size of triangles on the middle surface is comparable to the input; then no refinement is required to shrink below the minimum separation of the input. Optionally, we can complete the shell using our Boolean construction.
Figure 29 shows how the intersecting shell between the legs of the camel can be shrunk to generate an intersection-free shell.
Pinching Alternative. For certain applications, such as boundary layer meshing, it is necessary to have a shell with non-zero thickness everywhere, including at singularities, and it is tolerable to lose bijectivity at the vicinity of a singularity. For these cases, we propose a Boolean construction to fill the shell around singularities, and to extend the projection operator P inside these regions. That is, every point in the filled region will project to the singularity.
Without loss of generality, let us assume that T has a single singularity (Figure 30). We initially construct a pinched shell, with zero thickness at the singularity, construct a valid shell (Section 3), and then perform a corefinement [Loriot et al. 2020] between a tetrahedron (centered at the singularity and whose size is smaller than the minimal thickness of the neighboring vertices) and the shell. The result of the corefinement operation (Figure 30 middle) consists of triangles belong to the tetrahedron, or the shell surface. The remaining part of the tetrahedron is a star-shaped polyhedron with the singularity in its kernel, and sharing a part of its boundary with the shell. This polyhedron can be easily tetrahedralized by connecting its triangulated boundary faces (one of them is highlighted in red in Figure 30 middle) with the singularity. For every point p in these tetrahedra, the projection operator P projects p to the singularity. The remaining triangles are divided into two groups: the triangles with only one new vertex complete the degenerate prisms (one of them is highlighted in blue in Figure 30 middle), while the others map to the edges they are attached to.
Currently, our algorithm is limited to manifold and orientable surfaces: its extension to non-manifold and/or non-orientable meshes is a potential venue for future work. With such an extension, the integration of shells with robust tetrahedral meshers [Hu et al. 2019b[Hu et al. , 2018] ] would allow to solve PDEs on imperfect triangle meshes without ever exposing the user to the volumetric mesh, allowing them to directly work on the boundary representation to specify boundary conditions and to analyze the solution of the desired PDE. Since we rely on the additional checks for the bijective constraints, our method is slower than classical surface mesh adaptation algorithms and it is not suitable for interactive applications.
Integrating our approach into existing mesh processing algorithms might lose some of their guarantees or properties since our shell might prevent some local operations. Other surface processing algorithms guarantee some properties under some regularity assumptions on the input, which might not hold when our bijective constraints are used. For example, QSlim [Garland and Heckbert 1997] might not be able to reach the desired target number of vertices and [Dey and Ray 2010] might not be able to achieve the bounded aspect ratio. A practical limitation is that integrating our approach into existing remeshing or simplification implementations requires code level access.
Our shell is ideal for triangle remeshing algorithms employing incremental changes: not every geometry processing algorithm requiring a bijective map can use our construction. For example, it is unclear how isosurface-extraction methods [Hass and Trnkova 2020] could use our shell or how global parametrization algorithms [Alliez et al. 2003;Bommes et al. 2013;Kraevoy and Sheffer 2004;Schreiner et al. 2004] could benefit from our method since they already compute a map to a common domain.
We introduce an algorithm to construct shells around triangular meshes and define bijections between surfaces inside the shell. We proposed a robust algorithm to compute the shell, validated it on a large collection of models, and demonstrated its practical applicability in common applications in graphics and geometry processing.
We believe that many applications in geometry processing could benefit from bijectively mapping spatially close surfaces, and that the idea of using an explicit mesh as a common parametrization domain could be extended to the more general case of computing cross-parametrizations between arbitrary surfaces. To foster research in this direction, we will release our reference implementation as an open-source project.
in C and C ′ and denote the enclosing prism in C as ∆ q and the corresponding one in C ′ as ∆ ′ q . It follows from the positivity of the volumes of ∆ q and ∆ ′ q (Assumption 1), that there is ε > 0 such that the half-ball (for sufficiently small ε) Ball(q, ε) ∩ ∆ q coincides with Ball(q, ε) ∩ ∆ ′ q . Futhermore, the validity of the initial shell guarantees that there exists an interior point q ∈ Ball(q, ε ) ∩ ∆ • q ∩ T , and q ∈ ∆ ′• q ∩ T ⊂ C ′• ∩ T . Since neither p or q lies on the boundary side triangles of ∂C ′ (since p, q ∂T C ), therefore there exists an interior path P (i.e., a path both in T C and in T C ′ ) that connects p and q. By continuity the path P it will cross ∂C ′ at some point p i ∈ T C . Since the ∂T C ′ = ∂T C is a fixed boundary loop (by the definition of O), and does not contain interior points, p i can only cross on the top surface or bottom surface of C ′ which contradicts Assumption 2. The roles of C and C ′ can be inverted to complete the proof.
We then map M C to a regular planar n-gon D, with vertices on ∂M C mapped cyclically to the vertices of ∂D. It follows from [Floater 2003, Corollary 6.2] that such a convex combination mapping φ : M C → D is bijective. Then, similarly to the construction in Theorem 3.2, we define ϕ : C → D × [-1, 1] through affine mapping induced by the thetrahedralization of the prisms ∆ i . Similarly, we define ψ : C ′ → D × [-1, 1]. The mapping ψ is also bijective because of Assumption 1 and the definition of O it follows that the codomain of ψ is the same as ϕ. Note that in both cases, the map transforms vector field V (p) to the constant vector field e z = (0, 0, 2), and the projection is P z , as defined in Appendix A.1.
The dot product condition (Assumption 3) ensures that P z defines a bijection between D and ψ (T C ); and further, the image satisfies P z (ψ (∆ ′ i ∩ T )) = ψ (M ′ i ) where M ′ i is the middle surface (a single triangle) of ∆ ′ i . Therefore, since ψ and P z are both continuous and bijective, they are homeomorphisms which preserve topology, thus ∆ ′ i ∩ T is a simply connected topological disk.
Most of the proofs and definition in Section 3 easily extends to meshes with singularity or pinched shells. For instance, both Theorem 3.2 and Definition 3.3 apply to pinched shells by just considering a prism made of 4 (2 for the top and 2 for the bottom slab) instead of 6. Propositions 3.4 and 3.5 both rely on per-vertex properties; by just excluding singular vertices (and neighboring prism) from the statements the proofs (and our algorithm) still holds. Theorem 3.7 requires some minor additional considerations. As a consequence of beveling, no two singularities are adjacent. Therefore, we can always find a point q ∈ ∂T C that belongs to a single prism (Appendix A.5) since every prism will have a positive volume because no singularities are adjacent.
Finally Proposition 3.6 requires a new proof since the beveling pattern used for singularities is different.
Proof. In Figure 31 right, we highlight in red and orange the triangles not covered by the discussion in Appendix A.4. The prism corresponding to an orange middle triangle intersects the edgeadjacent triangle. And since the new pillars are computed as the average of the normals of the two adjacent triangles with dihedral angle strictly less than 360 • (Section 3.5 inset), each dot product is positive. The prism for a pink middle triangle intersects only the interior of the original triangle, and the dot product between the pillars and the triangle normal are positive by construction. □
With slack variable t, Problem 2 can be rewritten as max t t; d v n f ≥ t, ∥d v ∥ = 1, t ≥ ϵ.
In the admissible region, substituting t = 1/s, min s s; sd v n f ≥ 1, ∥d v ∥ = 1, 0 < s ≤ 1/ϵ.
Substituting x = sd v (thus ∥x ∥ = s ∥d ∥ = s), we obtain the QP problem 3. Note that the lower bound on s is implied from sd v n f ≥ 1, and the upper bound ∥x ∥ < 1/ϵ is checked a posteriori.
In this section, we show that the isoparametric transformation of prismatic finite element [Ciarlet 1991] is also bijective if I1 holds. We follow the notation from Appendix A.2. The map is defined as (for the top slab) f (u, v, η) = ue 1 + ve 2 + ηn 0 + uηn 01 + vηn 02 , det J f = ⟨(1uv)n 0 + un 1 + vn 2 , e 1 + ηn 01 , e 2 + ηn 02 ⟩, where η is the variable corresponding to the thickness direction, and n i j = n jn i . Observe that det J f (u, v, η 0 ) is linear in u, v for fixed η 0 , the extrema will only be achieved at the corner points [Knabner and Summ 2001]. Therefore, it is sufficient to check the signs at three edges (0, 0, η), (1, 0, η), (0, 1, η) for η ∈ [0, 1]. det J f (0, 0, η) = ⟨n 0 , (1η)e 1 + η(e 1 + n 1n 0 ), (1η)e 2 + η(e 2 + n 2n 0 )⟩ = (1η) 2 ⟨n 0 , e 1 , e 2 ⟩ + (1η)η⟨n 0 , e 1 , e 2 + n 2 ⟩ + (1η)η⟨n 0 , e 1 + n 1 , e 2 ⟩ + η 2 ⟨n 0 , e 1 + n 1 , e 2 + n 2 ⟩ = (1η) 2 vol 4 + (1η)η(vol 3 + vol 1 ) + η 2 vol 2 > 0. By symmetry, it is easy to verify that the following are positive, detJ f (1, 0, η) = (1η) 2 vol 6 + (1η)η(vol 7 + vol 5 ) + η 2 vol 8 , detJ f (0, 1, ζ ) = (1η) 2 vol 11 + (1η)η(vol 9 + vol 10 ) + η 2 vol 12 ,
In Section 3.1, we explain that we want to ensure that our shell validity is independent from the enumeration of the faces; for this reason, we require that the conditions I1 and I2 are satisfied for all possible decompositions. Without using the double slab, different decompositions of the prism will result in different intersections with the middle surface. In other words, the projection operator will project the input mesh to a different set of triangles on the middle surface. The double slab makes the middle surface independent of the decomposition by construction. We note that Theorem 3.6 is valid only for double-slab prisms since the statement requires that one prism contains only one triangle.
ACM Trans. Graph., Vol. 39, No. 6, Article 1. Publication date: December 2020.
ACM Trans. Graph., Vol. 39, No. 6, Article 1. Publication date: December 2020.1:18 • Zhongshi Jiang, Teseo Schneider, Denis Zorin, and Daniele Panozzo