Robust Mesh Repair for 3D-Printing Models
Qingnan Zhou
New York University

Winding number measures how many times
a point is enclosed by a given surface. It isoften used for determining if a point is insideof a 3D model. Mathmatically, 3D winding
number is defined as:

Key Concepts

Mesh Arrangements

Winding Number02

10−1

A mesh arrangement is a collection of (possibily
non-manifold, open boundary, self-intersecting, withdegenerate faces, etc.) meshes partitioning thespace into a number of cells.

Multiple Components

We test our algorithm with
10,000 models from Thingiverse.
No isolated vertices

100%

No duplicated faces

92%

Orientable

90%

Closed

89%

PWN

86%

Edge manifold

86%

No degenerated faces

84%

Vertex manifold

78%

Single component

74%

No coplanar intersection
No self−intersection
Solid
0%

69%

55%
50%

25%

50%

75%

100%

Models with multiple, possibly
overlapping or nested, components make up 26% of our dataset.
Processing each component separately
disregards
theirnesting/overlapping relationship andmay produce incorrect results.
Winding number provides an elegant way of determining if agiven point is inside (|w|>0) or
outside (|w|=0) of the shape.
It is even possible to have regions that are “twice inside”
due to overlapping components.

Intersection Resolution
The intersection of two triangles can be
empty, a point, a segment or a convex polygon. Intersection must be compute exactly
to avoid trouble down the pipeline. Specifically, rounding to float may
re-introduce intersections, create degeneracies or rotate an edge by
upto 90 degrees. General positioning assumption is not valid for 3D
printing models, where 31% of the input contain coplanar intersections.
Once intersection is computed, triangles involved must besplitted so that intersection are represented by meshvertices/edges/faces. Because constrained delaunay triangulation is not unique, coplanar faces must be triangulated together.

Self-Intersections

Self-intersection is detected in 45% of themodels in our dataset. Most existing geometry processing algorithms consider
meshes with self-intersections as invalid
despite their large presence in realworld models.
In our algorithm, we make no distinction between self-intersection
and mesh-mesh intersection. Allintersections are resolved exactly.
If the input mesh is PWN, the resolved mesh represents a valid arrangement that partition space intocells, each with piecewsise-constantwinding number.

Facet order around an edge

Pipeline

PWN Mesh: is any mesh that induces a Piecewiseconstant Winding Number field. PWN mesh could
contain multiple overlapping components with degenerate faces, self-intersections. PWN mesh can be
non-manifold and topologically open. Our algorithm
takes one or more PWN meshes as input.
Solid Mesh: is the non-degenrate boundary of a solid
sub-region of R3. It is a subset of PWN meshes that induces a {0,1} winding number field and is free of degenerate faces, self-intersections and duplicatedfaces. Out algorithm guarantees to output a solidmesh.

where Ωf(p) is the solid angle at point p in the tetrahedron formedby p and the triangle f. [Jacobson 2013] generalized winding
number concept to open meshes, and demonstrated winding
number is robust against common geometric artifects.

DatasetAlec Jacobson
Columbia University

465723

Input PWN meshes

Resolve intersections

Non-manifoldness is very common for 3D
printing models. In our dataset, 14% of
the models are not edge-manifold, and
22% of the models are not vertexmanifold.

Due to the presence of nearly degenerate
faces, surface normals are not reliable. Facetordering must be computed solely with exact
predicates. Symbolic perturbation is used tobreak ties caused by duplicated faces.

For each pair of components (c1, c2), we findthe closest object on c2 to a point, p, sampledfrom c1. We show that all cases can be reduced to determine the cyclical order of a pivot
facet created by connecting p with an edgethat touches the closes object.

[0,0]

Propagate winding
numberExtract boundaryof output solid meshIn our settings, exactly degenerate faces
can be ignored because it does noteffect the induced winding number field.
The resulting topological seam isclosed when resolving intersections.
Because all intersections are computed exactly, and our algorithm does
not rely on surface normal. Nearly degenerate faces does not pose any challenges.

Mesh arrangements and winding number
are well-defined for non-manifold meshes.

To correctly construct mesh arrangement, onemust extract all faces boudning a given partition or R3, which relies on consistent cyclicalorder of facets around all non-manifold edges.
Computing such ordering is misleadingly innocuous.

Partition into cells[1,0]

Exactly Degenerate faces appear in 16% of
the models in our dataset. Nearly degenerate
faces are even more ubiquitous. They areparticularly hard to handle because evenbasics quantities such as face normal is
not well-defined or numerically stable.

While non-manifoldness could arise frommodeling errors, there are many valid
usages of non-manifold meshes. For example, multi-material printers require
separate mesh from each material. The
example on the right is designed to illustrate triangles and squares of
cuboctehedron in different material.

For mesh with multiple
components, it is important to determine their
nesting relationship so
winding number can becorrectly propagated.

0

[0,1]

Degeneracies

Non-Manifoldness

Nesting Relationship

1

[1,1]

Results
Postconditions, self-union of 8616 meshes
produced a result...
our method
CGAL
Carve
QuickCSG
CorkAttene

without open boundaries
with zero total signed edge-incidence
without self-intersections

Resources

100%

Code:
Mesh boolean: https://github.com/libigl/libigl
Comparison: https://github.com/qnzhou/PyMesh
Dataset:https://ten-thousand-models.appspot.com/
Publication:
Zhou, Q., Grinspun, E., Zorin, D., Jacobson, A. 2016.
Mesh arrangements for solid geometry. Conditionally accepted to ACM SIGGRAPH.
Zhou, Q., Jacobson, A. 2016. Thingi10K: A dataset of
10,000 3D-printing models. Submitted to SGP.