See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/226683830

Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge

Hammering, and Face Lifting

Chapter · January 2009

DOI: 10.1007/978-3-642-04319-2_2

CITATIONS READS
12 957

2 authors:

Soji Yamakawa Kenji Shimada

Carnegie Mellon University Carnegie Mellon University
34 PUBLICATIONS 455 CITATIONS 256 PUBLICATIONS 4,156 CITATIONS

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Architectural applications of my framework for anisotropic general patterns on building envelopes: roofs and facades. View project

Optimizing Human-Powered Pumps for Deployment in Developing Countries View project

All content following this page was uploaded by Kenji Shimada on 11 June 2014.

The user has requested enhancement of the downloaded file.

Removing Self Intersections of a Triangular Mesh
by Edge Swapping, Edge Hammering, and Face
Lifting

Soji Yamakawa and Kenji Shimada

The Department of Mechanical Engineering

Carnegie Mellon University

Abstract.
This paper describes a computational method for removing self intersections
of a triangular mesh. A self intersection is a situation where a part of a surface
mesh collides with another part of itself, i.e., two mesh elements intersect each
other. It destroys the integrity of the mesh and makes the mesh unusable for
certain applications. A mesh generator often creates a self intersection when a
relatively large element size is specified over a region with a narrow clear-
ance. There has been no automated method that automatically removes self
intersections, and such self intersections needed to be corrected by manually
editing the mesh. The proposed method automatically resolves a self intersec-
tion by re-connecting edges and adjusting node locations. This technique re-
moves a typical self intersection and recovers the integrity of the triangular
mesh. Experimental results show the effectiveness of the proposed method.

1. Introduction
This paper describes a computational method for removing self intersections
of a triangular mesh. A self intersection is a situation where a part of a surface
mesh collides with another part of itself, i.e., at least two mesh elements inter-
sect each other. A self intersection destroys the integrity of the surface mesh
and makes the surface mesh unusable for certain applications. The proposed
method removes such self intersections and recovers the integrity of the mesh.
A triangular mesh is used for many applications such as finite element
analysis, visualization, and so on. Many of those applications require the
mesh to be free of self intersections. A self intersection in a triangular mesh
could cause failure of the finite element analysis or make unwanted artifacts in
the visualization.
A triangular mesh is also used as a boundary of a tetrahedral mesh, and
such a triangular mesh must not include a self intersection. A tetrahedral
2 Soji Yamakawa and Kenji Shimada

mesh is usually created by first creating a triangular mesh of the boundary of

the target volume and then filling the inside of the triangular mesh with tetra-
hedral elements. If the boundary triangular mesh includes a self intersection,
the mesh no longer defines a legitimate volume, and the tetrahedral mesh gen-
erator may create severely distorted elements or even fail to create a mesh at
all. Therefore, a self intersection in a triangular mesh is very problematic and
needs to be removed.
Theoretically, the best approach for removing self intersections is to mesh
the original CAD model with more appropriate mesh sizing. However, it is
often impossible to choose adequately short edge length. For example, some
types of analyses require minimum edge length longer than certain threshold.
For those analyses, minimum edge length condition is more important than the
boundary fidelity. The original CAD model is sometimes not available to the
analyst due to confidentiality issues. When an analysis needs to be performed
on a very old geometry, or a legacy model, the original CAD model may no
longer exist, and the model may be available only in the form of a mesh.
Therefore, self-intersections need to be removed by modifying the mesh in
many real-world problems.
There has been, however, no automated method for removing self intersec-
tions of a triangular mesh. Hence, the appropriate care must have been taken
before a triangular mesh was created to avoid self intersections. The input
geometric model needed to be de-featured, geometric constraints needed to be
appropriately added or removed, and a non-uniform sizing function was often
necessary. If those pre-conditioning measures were not adequate, a surface
mesh generator would yield self intersections, which needed to be removed by
manually editing the mesh.
The proposed method effectively removes typical self intersections created
due to a defective CAD model or a very narrow clearance and recovers integ-
rity of the triangular mesh. The proposed method takes as input a triangular
mesh, open or closed, and applies to the mesh a sequence of three types of op-
erations: (1) edge swapping, (2) edge hammering, and (3) face lifting. The
edge-swapping operation has been used mainly for mesh-quality improvement
and is used for reducing self intersections in this context. The edge-
hammering and face-lifting operations adjust locations of the nodes used by an
intersecting triangular element. These operations calculate new node locations
based on the neighboring nodes and the locations of intersections. The node is
moved to the new location if the move reduces the number of intersecting
elements without making a new intersecting element.
The organization of the paper is as follows. Section 2 presents previous
work. Section 3 describes typical sources of self intersections. Section 4 ex-
plains details of the proposed method, and Section 5 discusses some potential
expansions and discussions. Some experimental results are presented in Sec-
tion 6. Section 7 concludes the paper.
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 3

2. Previous Work
The proposed method pertains to facet-repair techniques, which repair defects
included in a surface mesh. A surface mesh may include two types of defects,
geometric defects and topological defects. A self intersection is one of the
common geometric defects, and a common topological defect is a gap or a
hole located where the mesh needs to be closed.
Since facet-repair techniques have been of great interest in the industry,
substantial research has been done. Nonetheless, most of the attention has
been paid to the topological aspect of the problem.
The majority of the published facet-repair techniques are gap-closure and
hole-filling techniques. If a triangular mesh has a gap or hole located where
the mesh needs to be closed, such a gap or hole needs to be closed. Barequet
and Sharir have presented a method for closing gaps and holes of a polyhedral
surface [1]. Barequet and Kumar have presented a method for repairing a
geometric model defined by a triangular mesh [2]. Gueziec et al. have pre-
sented a method for converting a polygonal surface to a manifold surface [3].
Branch et al. have presented a method for filling holes of a triangular mesh
[4]. Li et al. have presented a method for repairing holes of a triangular mesh
[5]. Those gap-closure and hole-filling techniques identify gaps and holes that
need to be closed and then insert triangular elements and/or stitch the edges
together so that gaps and holes are filled by triangular elements.
Gap closure and hole filling are important to recover the topological integ-
rity of a triangular mesh. However, it is also necessary to remove self inter-
sections and recover the geometric integrity. Self-intersection avoidance has
been relying mainly on a priori methods. In other words, adequate pre-
conditioning needed to be performed before a triangular mesh was created so
that the mesh generator would not yield a self intersection.
One of the common sources of a self intersection is a very small feature,
which is usually irrelevant to the purpose of the mesh. Ribelles et al. have
presented a method that automatically removes features of a geometric model
[6]. Lee et al. also have presented another approach for small-feature suppres-
sion [7].
A self-intersection can also be avoided by identifying features and appro-
priately adding geometric constraints near the features. Numerous researches
have been done for feature-line identification [8-12]. Jiao has presented a
method for identifying features of a geometric model and preserves them dur-
ing the mesh-generation process [13].
Alternatively, a self-intersection can be avoided by creating smaller ele-
ments near small features. Quadros et al. have presented a method for auto-
matically creating an element-sizing function based on the input geometry
[14].
4 Soji Yamakawa and Kenji Shimada

Self intersections can be avoided by embedding intersection curves on a

mesh and then dividing the mesh into a set of non-intersecting sub-meshes
[15]. This method, however, divides a mesh into multiple meshes and can be
utilized only in limited types of applications.
Despite the extensive research on automatic feature identification and re-
moval techniques, those techniques are not always adequate for avoiding all
self intersections. If the mesh generator could not avoid creation of self inter-
sections in a triangular mesh, the user needed to manually edit the mesh to re-
move those self intersections.
The proposed method modifies a triangular mesh and reduces self intersec-
tions. It is useful for reducing the manual mesh editing when the mesh gen-
erator can not avoid self intersections.

3. Typical Sources of a Self Intersection

Even when the CAD model itself does not include a self intersection, there is a
possibility that the mesh generator creates a self intersection when an exces-
sively large element size is specified. A large element size yields a large error
(in distance) between the mesh surface and the original surface. In two di-
mensions, when a curve is discretized into line segments, an expected error
between a curve and its discretization is calculated as:
1
e = − (1/κ ) 2 − (h / 2) 2 ,
κ
where h is the length of a segment of the discretization and κ is the curvature
of the curve as shown in Figure 1.
In three dimensions, an expected error between a surface and its triangula-
tion is calculated as:
1
e = − (1/κ ) 2 − (h 2 / 3) ,
κ
where h is the edge length, and κ is the principal curvature of the surface.
The assumption is the curvature does not change rapidly and the triangular
element is equilateral.
Assume that an equilateral triangle with edge length of h is lying on X-Y
plane as shown in Figure 2. The coordinates of the three corners are (0,0,0) ,
(h,0,0) , and (h / 2,0,( 3 / 2)h) , and the center of the triangle is (h / 2,0,( 3 / 6)h) .
The center of one of its circumscribed spheres with radius of r = (1/κ ) is lo-
cated at (h / 2,0,( 3 / 6)h) . Since the distance from the center to the origin,
where one of the triangle corners is located, is equal to the radius, the follow-
ing equation is derived:
2
⎛h⎞
2
⎛ 3 ⎞ h2
r 2 = ⎜ ⎟ + y 2 + ⎜⎜ h ⎟⎟ = + y 2 .
⎝2⎠ ⎝ 6 ⎠ 3
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 5

⎛h ⎞
Z ⎜ , y, 3 h ⎟
⎜2 6 ⎟
⎝ ⎠

1 ⎛h ⎞
r= ⎜ , y, 3 h ⎟
κ ⎜2 ⎟
h e ⎝ 2 ⎠
⎛ ⎞
⎜ h ,0, 3 h ⎟
⎜2 6 ⎟
⎝ ⎠
Y e=r − y
(1/κ ) 2 − (h / 2) 2
1/κ (h,0,0)
X

Figure 1 Expected error between a Figure 2 Expected error between a curved sur-
curve and its discretization face and its discretization
It can be solved for y as:
h2
y= r2 − .
3

Since the expected error can be calculated as the difference between the ra-
dius and the distance between the element to the center of the sphere, the ex-
pected error becomes:
1
e = − (1/κ ) 2 − (h 2 / 3) . (1)
κ
Therefore, when two surfaces are separated with a small clearance d, the edge
length h should be small enough so that the expected error is smaller than d.
However, in practice, element size is often decided based on the application
in which the mesh is used, and it can be way too large for the surface clear-
ance of the original geometric model. Such a large element size yields self in-
tersections in the mesh. For example, Figure 3 (a) shows a CAD model that
includes two co-axial cylindrical surfaces. The radii of the outer and inner cy-
lindrical surfaces are 5.0 and 4.8, respectively. Therefore, the clearance be-
tween the two surfaces is 0.2. The curvature of the outer surface is
1.0/5.0=0.2. From equation (1), the edge length of the mesh needs to be less
than 2.42. Figure 3 (b) shows a triangular mesh created from this CAD model
with an average edge length of 2.42, and it does not include a self intersection.
However, if the same geometry is meshed with average edge length of 3, some
self intersections are clearly visible as shown in Figure 3 (c). In this particular
case, self intersections can be avoided by identifying cylindrical surfaces and
adding some mesh constraints on the surface. Figure 3 (d) shows some new
constrained edges added by the polygon-crawling method [12]. The mesh
6 Soji Yamakawa and Kenji Shimada

generator preserves those constrained edges, and the output triangular mesh
does not include a self intersection as shown in Figure 3 (e).
Ideally, a sufficiently small element size needs to be chosen or appropriate
mesh constraints need to be added for the regions of small clearance. How-
ever, some of such ill conditions are often overlooked. Particularly, such ill
conditions tend to be left untreated if they are:
1. contained within a very small feature, or
2. away from the point of interest for the application in which the mesh is
used.
Such less-visible ill conditions are most likely left untreated before the
model is given to the mesh generator. Even if all of those ill conditions are
detected, a complex model could have hundreds of them and could take sub-
stantial manual operations to correct or add constraints to all of them. As dis-
cussed in Section 2, if such an ill condition was overlooked and the mesh gen-
erator created self intersections, the user needed to manually correct those self
intersections.
The next section explains an automated method for removing self intersec-
tions included in a triangular mesh. The method substantially reduces the
manual operations required to eliminate self intersections to recover the integ-
rity of the mesh.

Intersecting elements
(a) Original CAD model (b) Triangular mesh with av- (c) Triangular mesh with
erage edge length of 2.42 average edge length of 3.
New constrained edges

(d) Additional constrained (e) Triangular mesh with average edge length of
edges added by the polygon- 3. Additional constrained edges have successfully
crawling method prevented self intersections
Figure 3 A narrow clearance causing self intersections
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 7

4. Detail of the Proposed Method

4.1. Improvement Criteria

The proposed method uses three types of operations, edge swapping, edge
hammering and face lifting, which are explained later in this section. Al-
though the three operations are effective in reducing self intersections, those
operations cannot always guarantee the successful reduction of self intersec-
tions. In the worst case, those operations could make the situation worse.
Therefore, the proposed method needs criteria to test the improvement, and the
proposed method will not apply the operations if the criteria cannot be met.
The improvement criteria used by the proposed method are as follows:
1. The number of intersecting triangles decreases.
2. No new intersecting triangle is created.
The first criterion guarantees that the process terminates within finite compu-
tational time. The mesh has a finite number of intersecting triangles, and the
edge-swapping, edge-hammering and face-lifting operations do not change the
total number of triangles. Therefore, the process terminates when no more re-
duction of the intersecting triangles is possible.
The second condition prevents the effect of the edge-swapping, edge-
hammering, and face-lifting operations from propagating through the mesh. If
the number of intersecting triangles is reduced by creating a new intersecting
triangle, the new intersection needs to be removed by a subsequent edge-
swapping, edge-hammering, or face-lifting operation. As a result, the effect of
those operations could propagate through the mesh. Such propagation can be
prevented by the second condition.

a a
d d
T2 T1

T2
b T1
c b
c

Figure 4 Removing a self intersection by edge swapping

8 Soji Yamakawa and Kenji Shimada

(a) Five triangles are intersecting with another (b) Intersections are removed
triangle. Dashed lines are behind the outside by Edge Hammering
layer of the triangular mesh.
Figure 5 An Example of edge hammering

4.2. Edge Swapping

Edge swapping reconnects an edge shared by two triangles. When an edge
connecting nodes a and b is shared by two triangles T1 and T2, and if triangle
T1 is using nodes a, b, and c, and T2 is using b, a, and d, triangles T1 and T2
are replaced with triangles cad and dbc as shown in Figure 4. Edge swapping
removes edge ab and creates edge cd. The proposed method applies edge
swapping to an edge used by an intersecting triangle if it satisfies the im-
provement criteria.

4.3. Edge Hammering

Edge Hammering moves a node and corrects an edge sticking out of another
triangle. When a triangular mesh is created from two curved surfaces with a
small clearance, a self intersection can be created as shown in Figure 5 (a). In
this example, five edges from the inside-layer triangles are sticking out of an
outside-layer triangle. Such a self intersection can be removed by moving the
node of the intersecting edges as shown in Figure 5 (b).
If an edge is intersecting with another triangle at one point, the intersection
on the edge will disappear by moving one of the edge nodes toward the other
node beyond the intersecting point. For example, in Figure 6 (a), edge ab is
intersecting with triangle T4 at x4. Edge ab will no longer have an intersection
if node a is moved toward node b beyond x4 as shown in Figure 6 (b). In this
example, this move also makes triangles T 2 , T 3 , T 4 , and abd free of intersec-
tion. The new location of node a can be anywhere between x4 and b to make
edge ab intersection-free. The mid point, (x4+b)/2, is advantageous because it
does not make edge ab too short and makes a reasonable clearance from x4.
If an edge is intersecting with other triangles at more than one point, the in-
tersection may be reduced by moving one of the edge nodes toward the other
node beyond the first intersecting point before reaching the second. For ex-
ample, edge ac in Figure 6 (a) is intersecting with triangles T 1 and T 2 at x1
and x2, respectively. If node a is moved toward node c beyond x2 before x1,
intersection x2 disappears, and triangles T 2 , T 3 , T 4 , and abd become free of
intersection as shown in Figure 6 (c). However, if node a is moved beyond x1,
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 9

a new intersection x5 will be created as shown in Figure 6 (d). From this ob-
servation, if an edge intersects with other triangles at more than one point, one
of the edge nodes should be moved toward the other node beyond the first in-
tersection to reduce the number of intersections. However, moving the node
beyond the second intersection will create a new intersection. Node a can be
moved to anywhere between the first and second closest intersections. The
simplest choice of the point is the mid point of the first two intersections.
Since a node can be connected to more than one intersecting edge, the node
can have multiple candidate points. If edge abn is the nth intersecting edge
connected to node a, the nth candidate point a'n is calculated as:
(a) If edge abn is intersecting with another triangle at a single point x,
candidate point a'n is calculated as a'n=(x+bn)/2, and
(b) If edge abn is intersecting with other triangles at multiple points x1,
x2, …, and xk, and x1 and x2 are the first and second closest intersec-
tion to node a, candidate point a'n is calculated as a'n=(x1+x2)/2.
The proposed method moves node a to the average of the candidate points:
a'= ∑ a'n / n ,

if the move satisfies the improvement criteria described in Section 4.1.

T 2 x2 a x4
x1 T4
x2 x4 x4
x1
c c c
T3 x3 x3
a
b x1 d
b
T1 (Schematic drawing)
d
(a) Three edges connected to node a are intersecting (b) Moving node a to
with other triangles. (x4+b)/2 reduces intersections
x2 x5
x1 a
c a
c
d x6 d
b b
(c) Moving node a to (x1+ x2)/2 re- (d) Moving node a beyond x1 yields
duces intersections new intersections.
a
x2 x4
x1 x3 a'
a'2 c
c a'3 d
a'1
d (a'1+a'2+a'3)/3 b
b
(e) Three candidate locations (d) Moving node a to the average of the three
candidate locations reduces intersections with-
out creating a new intersecting triangle.
Figure 6 Calculating candidate points to which a node is moved
10 Soji Yamakawa and Kenji Shimada

(a) A triangle intersecting with (b) Face-lifting operation removes

multiple edges the intersections
Figure 7 Face-lifting operation
In the example shown in Figure 6, three candidate locations, a'1 and a'2 are
calculated as:
a'1=(x4+b)/2
a'2=(x1+x2)/2
a'3=(x3+d)/2,
as shown in Figure 6 (e), and node a is moved to a'=(a'1+a'2+a'3)/3 because
triangles T 2 , T 3 , T 4 , and abd become intersection free without making a new
intersecting triangle. Although triangles T 1 , acb, and acd are still intersect-
ing, the move yields no new intersecting triangles, and the three remaining in-
tersecting triangles can be made intersection free by subsequent edge hammer-
ing and face lifting operations.

4.4. Face Lifting

The face lifting operation moves a triangle at a time to reduce the number of
intersections. For example, a highlighted triangle in Figure 7 (a) is intersect-
ing with multiple edges. The face-lifting operation moves the triangle to its
normal direction and removes the intersections as shown in Figure 7 (b).
Assume that triangle T1, consisting of three nodes t1, t2, and t3, is intersect-
ing with one or more edges, and the nodes p1, p2, …, pn are the nodes used by
the intersecting edges. The unit normal vector of T1 is n1, and ε is the given
clearance requirement between a triangle and a node.
The minimum and maximum of the signed distances of nodes pi {i=1 to n}
relative to T1, denoted as dmin and dmax respectively, are then calculated as:
dmin=min( (pi − t1)⋅n1 ),

dmax=max( (pi − t1)⋅n1 ).

The proposed method moves triangle T1 to two possible new locations, by

offsetting n1(d max + ε ) and n1(d min −ε ) from the original location. And for each
new location, the proposed method tests if the move satisfies the improvement
criteria described in Section 4.1.
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 11

a T1 T2 T3
T2 b n1
c T3 dmax
a b a b
e
d c c
f
T1 T1 dmin
d e f d e f
(Schematic drawing) (b) Computing the minimum
(a) Triangle T1 intersecting with six edges, ad, ae, and maximum of the signed
be, bf, cd,and cf. heights of nodes a, b, c, d, e,
and f based upon T1.
n1(d min −ε )

n1(d max + ε )
T1 T1
T2 T3
(c) Moving T1 by n1(d max + ε ) re- (d) Moving T1 by n1(d min − ε ) makes T1
moves all the intersections free of intersections. However, it makes
new intersecting triangles, T2 and T3.
Figure 8 Calculating possible new locations of an intersecting triangle
If only one of the two new locations satisfies the improvement criteria, tri-
angle T1 is moved to the new location that satisfies the improvement criteria.
If both moves satisfy the improvement criteria (implies that the intersecting
edges are disconnected from the other part of the mesh that T1 belongs to,) T1
is moved to the new location that makes the move smaller.
For example, in Figure 8 (a), triangle T1 intersects with six edges, ad, ae,
be, bf, cd, and cf. The minimum and maximum of the signed heights of the
nodes of the intersecting edges are calculated as shown in Figure 8 (b). If the
triangle T1 is moved by n1(d + ε ) , triangle T1 becomes free of intersection
max

without making a new intersecting triangle as shown in Figure 8 (c). There-

fore, it satisfies the improvement criteria described in Section 4.1. However,
if T1 is moved by n1(d −ε ) as shown in Figure 8 (d), triangles T2 and T3,
min

which were intersection free before the move, intersect with some of the
edges. Therefore, it violates the improvement criterion. In this case, triangle
T1 is thus moved by n1(d + ε ) from the original location.
max

4.5. Order-Dependency Issues

The result of edge-swapping, edge-hammering, and face-lifting operations de-
pends on the order in which the operations are applied. If the operations are
applied to the mesh in an inappropriate order, they may either make an unnec-
essarily large deformation to the mesh or simply fail to reduce the self inter-
12 Soji Yamakawa and Kenji Shimada

sections. However, it is virtually impossible to find the ideal order of the op-
erations.
In this research, we have tested several different measures in an attempt to
reduce the adverse effect caused by the order dependency. In the first ap-
proach, we have applied edge swapping first, edge hammering second, and
face lifting last. Since edge swapping does not move nodes, it seemed to have
the least impact on the geometry. Edge hammering moves one node at a time
while face lifting moves three nodes at a time. Edge hammering thus seems to
have less impact on the geometry compared to face lifting. Although this ap-
proach gave somewhat good results, it often gave less than satisfactory results.
That led to the two-phase approach described below.
To reduce the adverse effect caused by the order-dependency, the proposed
method applies a sequence of edge-swapping, edge-hammering, and face-
lifting operations in two phases: (1) cost-calculation phase and (2) implemen-
tation phase.
In the cost-calculation phase, a sequence of edge-swapping, edge-
hammering, and face-lifting operations are applied to all applicable edges,
nodes, and elements. After each operation, the cost of the operation is calcu-
lated, and then the modifications made to the mesh by the operation are re-
tracted back to the original state of the mesh. Therefore, the mesh does not
change before and after the cost-calculation phase.

Two triangles deleted Two triangles created by A tetrahedron enclosed by

by the operation the operation the four triangles
(a) Cost of the edge-swapping operation
Tn T 'n

Triangles before Triangles after A volume enclosed by the triangles

the operation the operation before and after the operation
(b) Cost of the edge-hammering operation
Tn T T 'n T'

Triangles before the Triangles after A volume enclosed by the triangles

operation the operation before and after the operation
(c) Cost of the face-lifting operation
Figure 9 Cost of the edge-swapping, edge-hammering, and face-lifting operations
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 13

The cost of an operation is a measurement that evaluates the magnitude of

deformation of the mesh made by the operation, which can be measured as a
change of volume made by the operation. The cost of the edge-swapping op-
eration is the volume of a tetrahedron enclosed by the two triangles deleted by
the operation and the two new triangles created by the operation as shown in
Figure 9 (a).
The cost of the edge-hammering operation is calculated as follows. Let T 1 ,
T 2 , …, Tn be the triangles sharing the node to be moved by the operation.
The operation moves the node, and Tn becomes T 'n . The cost of the edge-
hammering operation is the volume enclosed by T 1 , T 2 , …, Tn , and T '1 ,
T '2 ,…, T 'n as shown in Figure 9 (b).
The cost of the face-lifting operation is calculated as follows. Let T be the
triangle to be moved by the operation and T 1 , T 2 , …, Tn be the triangles shar-
ing at least one node with T . The operation moves T to T ' , and Tn becomes
T 'n . The cost of the edge-hammering operation is the volume enclosed by T ,
T ' , T 1 , T 2 , …, Tn , and T '1 , T '2 ,…, T 'n as shown in Figure 9 (c).
Then, in the implementation phase, the edge-swapping, edge-hammering,
and face-lifting operations are applied to the mesh in the order of ascending
cost.

5. Potential Expansions and Discussions

5.1. Expanding the Proposed Method for a Quadrilateral Mesh

The proposed method can easily be expanded so that it can deal with a quadri-
lateral mesh by the following steps:
1. Tessellate every quadrilateral by adding a diagonal edge while keeping
track of which triangle comes from which quadrilateral.
2. Apply the proposed method.
3. Merge triangles to re-construct the quadrilaterals.
However, there are two remaining issues that need to be addressed for this
expansion as follows.
(a) Edge preservation vs. effectiveness
Some quadrilaterals may not be re-constructed after applying the proposed
method due to edge swapping. To guarantee the re-construction, edge
swapping needs to be carefully applied so that edges of the original quadri-
laterals are preserved. However, this limitation could reduce the effective-
ness of the proposed method.
(b) Non-planar quadrilateral
Four nodes of a quadrilateral element may not be co-planar, and the ge-
ometry of a quadrilateral element is a bi-linear surface. Therefore, tessel-
lating a quadrilateral into two triangles changes the geometry, and some
14 Soji Yamakawa and Kenji Shimada

self intersections may not be detected after the tessellation. Or, even if the
triangular mesh is made self-intersection free by the proposed method, it
does not guarantee that the quadrilateral mesh is also self-intersection free
after quadrilateral elements are re-constructed.
Further research is needed for addressing these issues.

5.2. Locally Adjusting the Clearance Requirement

The proposed method takes the parameter ε , a clearance requirement for the
face-lifting operation, as input. The face-lifting operation moves an intersect-
ing triangular element in its normal direction so that it will have a clearance of
ε.
However, in some cases, it is ideal to vary ε over the domain. For exam-
ple, if the thickness of the geometry substantially changes over the domain, ε
should be proportional to the local thickness of the domain.
The proposed method can be adapted to such requirement with a small
modification. When triangle T 1 is being moved by the face-lifting operation,
instead of taking ε as a user input, it can be calculated as follows.
Assume triangle T 1 consists of nodes p1 , p 2 , and p3 , and its normal is n .
tn is the distance that a ray travels from pn in the direction −n until it hits an-
other triangular element as shown in Figure 10. If the ray does not hit another
triangle, tn is zero. Each of tn gives a rough estimation of the thickness at pn .
If at least two of the three tn s are non-zero, ε is taken from the median of tn s.
If only one tn is non-zero, ε is taken from the non-zero tn . If all three tn s are
zero, the face-lifting operation is not attempted, and this intersection is de-
ferred to the edge-swapping and edge-hammering operations.
In some applications, the clearance can also be specified relative to the edge
length of the triangle to be moved. For example, if the triangular mesh is used
as the boundary of a tetrahedral mesh, and if the maximum aspect ratio of the
tetrahedral mesh needs to be smaller than γ , the required clearance ε must be
1/γ times the longest edge length of the triangle. In this application, a similar
adaptation is also possible for the edge-hammering operation.

n p3
n
t3 p1 T1
p2
p1 T1
t1 p2 t2
t1
t2

(a) Intersection (b) Schematic drawing

Figure 10 Estimating the clearance requirement from the local thickness
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 15

5.3. Boundary Fidelity Issue

The edge-hammering and face-lifting operations move nodes of the input tri-
angular mesh. The mesh generator usually places nodes exactly on the origi-
nal surfaces. However, the nodes may be moved away from the original sur-
faces by the proposed method. In other words, edge-hammering and face-
lifting operations trade the boundary fidelity for removal of self intersections.
It raises an obvious question: if it is allowed to sacrifice boundary fidelity to
remove self intersections.
A surface mesh needs to satisfy multiple requirements including edge
length, clear of self-intersection, element quality, in addition to boundary fi-
delity. As presented in Section 6, self intersections in a boundary triangular
mesh yield a tetrahedral mesh that is utterly unusable in the finite element
simulation. It implies that self intersections can be more problematic than loss
of the boundary fidelity. If the boundary fidelity is very important, another
option is to make smaller elements so that no self intersection is created as
discussed in Section 3.
In summary, those mesh requirements, edge length, clear of self intersec-
tion, element quality, and boundary fidelity, are in the relation of trade offs
and may not be satisfied all together. Priorities of those requirements must be
considered based on the best outcome of the application in which the mesh is
used. It is possible that boundary fidelity is not the top priority, and then di-
verting the nodes away from the original surface to remove self intersections
can be justified.
Loss of the boundary fidelity could impact the outcome of the application in
which the mesh is used, and therefore the diversion should be kept as small as
possible. Nonetheless, a certain loss of boundary fidelity should be tolerated
in order to obtain the best outcome in the application.

6. Examples
This section presents some examples to demonstrate the effectiveness of the
proposed method. Figure 11 (a) shows a thin-walled solid with ribs and a
screw hole. Such a shape frequently appears in a geometric model of a plas-
tic-casing. Figure 11 shows a triangular mesh with an average edge length of
1.5. This mesh does not include self intersections. However, the number of
elements can be too many for the application in which the mesh is used. The
number of elements can be reduced by specifying larger element size. Figure
11 (c) shows a triangular mesh with an average edge length of 3mm. The
middle section of the outer surface of the screw hole is collapsed to a single
edge, and it intersects with the inside wall. Some inside-wall elements also
collide with the outer-wall of the fillet. The proposed method successfully
removes all self intersections as shown in Figure 11 (d). Figure 11 (e) shows a
16 Soji Yamakawa and Kenji Shimada

tetrahedral mesh created from the triangular mesh shown in Figure 11 (c).
Due to the self intersections in the input triangular mesh, the output tetrahedral
mesh has some exterior edges that are shared by more than two exterior trian-
gular elements. Figure 11 (f) shows a tetrahedral mesh created from the trian-
gular mesh shown in Figure 11 (d). Since no self intersection is included in
the triangular mesh, the output tetrahedral mesh is a valid and usable in the fi-
nite element analysis.
Figure 12 (a) shows a CAD model of a plastic casing of a telephone. Figure
12 (b) is a triangular mesh of the model meshed with an average edge length
of 4mm. With this edge length, the mesh generator does not create a self in-
tersection. Figure 12 (c) is a triangular mesh with 10mm average edge length.
This edge length yields numerous self intersections as shown in Figure 12 (d).
Note that the majority of the elements are intersection free. Only a small frac-
tion of the elements are intersecting. Despite the small percentage of inter-
secting elements, these self intersections could make the mesh utterly unusable
for the application. The proposed method successfully removes all the inter-
sections. The changes made by the proposed method are hardly visible with-
out zooming into the specific locations. Figure 12 (e) shows a close up look
of two of the self intersections included in the 10mm mesh, and the proposed
method removes them as shown in Figure 12 (f).

7. Conclusions
This paper has presented a computational method for removing self intersec-
tions included in a triangular mesh. The method systematically applies edge-
swapping, edge-hammering, and face-lifting operations to the input triangular
mesh. The proposed method has been applied to many test cases, and the re-
sults showed the effectiveness of the proposed method.
 Removing Self Intersections of a Triangular Mesh by Edge Swapping, Edge
Hammering, and Face Lifting 17

(a) Original geometric model (b) Triangular mesh with 1.5mm average edge
length does not include a self intersection

(c) Triangular mesh with 3mm average (d) Triangular mesh with 3mm average edge
edge length including numerous self inter- length repaired with the proposed method. The
sections. mesh includes no self intersection.

(e) Tet mesh created from a triangular mesh (f) Tet mesh created from a triangular mesh
with self intersections repaired by the proposed method
Figure 11 Sample model with ribs and a screw hole

(a) Input geometric model (b)Triangular mesh with (c) 10mm average edge
4mm average edge length does length yields numerous
not include a self intersection. self intersections.

(d) Intersecting triangular (e) Close up of intersect- (f) Intersection removed

elements ing elements by the proposed method
Figure 12 Sample model of a plastic casing of a telephone
 18 Soji Yamakawa and Kenji Shimada

References
[1] G. Barequet and M. Sharir, "Filling Gaps in the Boundary of a Polyhedron",
Computer Aided Geometric Design, vol. 12, pp. 207-229, 1995.
[2] G. Barequet and S. Kumar, "Repairing CAD Models," Proceedings of IEEE
Visualization '97, pp. 363-370, 1997.
[3] A. Gueziec, G. Taubin, F. Lazarus, and B. Horn, "Cutting and Stitching:
Converting Sets of Polygons to Manifold Surface", IEEE Transactions on
Visualization and Computer Graphics, vol. 7, pp. 136-151, 2001.
[4] J. Branch, F. Prieto, and P. Boulanger, "A Hole-Filling Algorithm for Trian-
gular Meshes Using Local Radial Basis Function," Proceedings of 15th In-
ternational Meshing Roundtable, pp. 411-431, 2006.
[5] F. Li, B. Chen, and W.-h. Leng, "A Hole Repairing Method for Triangle
Mesh Surfaces," Proceedings of International Conference on Computational
Intelligence and Security, pp. 972-975, 2006.
[6] J. Ribelles, P. Heckbert, M. Garland, T. Stahovich, and V. Srivastava, "Find-
ing and Removing Features from Polyhedra," Proceedings of ASME Design
Automation Conference, pp., 2001.
[7] K. Y. Lee, C. G. Armstrong, M. A. Price, and J. H. Lamont, "A Small Fea-
ture Suppression/Unsuppression System for Preparing B-Rep Models for
Analysis," Proceedings of ACM Symposium on Solid and Physical Model-
ing, pp. 113-124, 2005.
[8] M. Nomura and N. Hamada, "Feature Edge Extraction from 3D Triangular
Meshes Using a Thinning Algorithm," Proceedings of SPIE - Vision Geome-
try X, pp. 34-41, 2001.
[9] X. Jiao and M. T. Heath, "Feature Detection for Surface Meshes," Proceed-
ings of 8th International Conference on Numerical Grid Generation in Com-
putational Field Simulations, pp. 705-714, 2002.
[10] T. J. Baker, "Identification and Preservation of Surface Features," Proceed-
ings of 13th International Meshing Roundtable, pp. 299-309, 2004.
[11] S. Yoshizawa, A. Belyaev, and H.-P. Seidel, "Fast and Robust Detection of
Crest Lines on Meshes," Proceedings of ACM Symposium on Solid and
Physical Modeling, pp. 227-232, 2005.
[12] S. Yamakawa and K. Shimada, "Polygon Crawling: Feature-Edge Extraction
from a General Polygonal Surface for Mesh Generation," Proceedings of
14th International Meshing Roundtable, pp. 257-275, 2005.
[13] X. Jiao, "Volume and Feature Preservation in Surface Mesh Optimization,"
Proceedings of 15th International Meshing Roundtable, pp. 359-373, 2006.
[14] W. R. Quadros, V. Vyas, M. Brewer, S. J. Owen, and K. Shimada, "A Com-
putational Framework for Generating Sizing Function in Assembly Mesh-
ing," Proceedings of 14th International Meshing Roundtable, pp. 55-72,
2005.
[15] J. Glimm, S. R. Simanca, D. Tan, F. M. Tangerman, and G. Vanderwoude,
"Front Tracking Simulations of Ion Deposition and Resputtering", SIAM
Journal on Scientific Computing, vol. 20, pp. 1905-1920, 1999.

View publication stats