As part of my master thesis, I worked with CAD models — specifically, triangular meshes — from ShapeNet [] to learn shape completion of cars. One of the problems with the models in ShapeNet is their complexity. As illustrated below, these models may be very detailed — comprising several hundred thousand faces and vertices — and not watertight (e.g. due to missing windows). In order to "learn" shape completion using deep neural networks, for example, I needed to voxelize car models — which required watertight meshes, and simplified ones for efficiency. Figure 1 shows some examples of complex models.
Figure 1: Examples of very complex car models (left) and examples of the semi-convex hull algorithm for simplification (right).
For the discussion of watertight meshes, we first need to formally define what makes up a proper triangular mesh (e.g. following []):
Definition. A triangular mesh $\mathcal{M} = (V, F)$ is defined by a set of vertices $V \subseteq \mathbb{R}^3$ and a set of triangular faces $F \subseteq \{1,\ldots,|V|\}^3$ such that $f = (f_1, f_2, f_3) \in F$ defines a triangular face enclosed by the corresponding vertices $v_{f_1}$, $v_{f_2}$ and $v_{f_3}$. Faces implicitly also define the edges $E(F)$ between the vertices.
The concepts of adjacency and incidency are naturally extended to triangular meshes. We note that a triangular mesh only defines the surface of an object. Without additional constraints it is generally hard to reason about the interior and exterior of the surface — and whether the surface is closed. This question naturally leads to the concept of watertight meshes. In the literature, for examples in [], watertight meshes are usually defined as 2-manifold meshes without boundary edges.
However, an exact definition — especially one that I could use in my master thesis — was not very easy to find. In the end, I additionally read parts of [] and [] to make the following definitions:
Definition.
- A self intersection is an intersection of two faces of the same mesh.
- A non-manifold edge has more than two incident faces.
- The star of a vertex is the union of all its incident faces.
- A non-manifold vertex is a vertex where the corresponding star is not connected when removing the vertex.
- A mesh is 2-manifold if it does contain neither self intersections, nor non-manifold edges, nor non-manifold vertices.
Figure 2: Non-manifold vertex (left) and non-manifold edge (right); both from [].
Illustrations of these somewhat abstract definitions can be found in Figure 2 (originally by []). In general, 2-manifold meshes are preferable to arbitrary meshes as many algorithms and applications are not applicable to non-manifold meshes. In our case, however, the definition of 2-manifold meshes is only motivated by the need to formally define watertight meshes (which are sometimes also referred to as closed meshes). Intuitively, the only constraint missing from 2-manifold meshes is a notion of "closedness" — meaning a clear interior and exterior. This becomes apparent when considering the definition of a non-manifold edge which also allows edges with only one incident faces, so-called boundary edges.
Definition. A 2-manifold mesh is called watertight if each edge has exactly two incident faces, i.e. no boundary edges exist.
The above definitions, while appearing abstract, are also useful in practice. In software, e.g. in MeshLab, it is easy to identify and label non-manifold vertices, edges as well as boundary edges to help design and work with triangular meshes.
From the above definition, we can also deduce that "closedness" is essentially a design choice. This means that we cannot extract watertight meshes from non-watertight meshes algorithmically. For my application, however, I assumed that all meshes are supposed to be "closed", however, may contain complex details within the model — for example, cars that are modeled as "closed" exterior but also include interior. In this case, I decided to tackle simplification and the problem of watertightness together by using a semi-convex hull approximation. Results of this approximation can be found in Figure 1.
- [] Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno Levy. Polygon Mesh Processing. AK Peters, 2010.
- [] H. Edelsbrunner. Surface Reconstruction by Wrapping Finite Sets in Space. Springer Verlag, 2003.
- [] P. Giblin. Graphs, Surfaces and Homology. Cambridge University Press, 2010.
- [] Angel X. Chang, Thomas A. Funkhouser, Leonidas J. Guibas, Pat Hanrahan, Qi-Xing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, Fisher Yu: ShapeNet: An Information-Rich 3D Model Repository. CoRR abs/1512.03012 (2015)