Mesh Repair (MeshDoctor)

Overview

Meshes imported from 3D scans (STL/OBJ/PLY, reconstructed point clouds) are often dirty: duplicated vertices, degenerate or duplicate faces, orphaned vertices, inconsistent winding, stray fragments, and holes. MeshDoctor diagnoses these defects and repairs them — every pass is discrete and returns a fresh TriangleMesh.

using Rasmah
using LinearAlgebra

Diagnosis

diagnose(m) returns a MeshDiagnosis with the vertex/face counts, the defect counts, the connected-component count, area, and the watertight / manifold flags:

m = icosphere(2)
d = diagnose(m)
println(d.watertight, "  ", d.manifold)
println(d.n_degenerate_faces, "  ", d.n_duplicate_faces, "  ", d.n_boundary_edges)
println(d.n_nonmanifold_edges, "  ", d.n_nonmanifold_vertices, "  ", d.n_connected_components)

true  true
0  0  0
0  0  1

Build a deliberately broken mesh — a base triangle, a reversed duplicate, a face reusing a duplicate vertex, a degenerate face, and an orphan vertex — and count each defect:

verts = [
    0.0 1.0 0.0 1.0 9.0;
    0.0 0.0 1.0 0.0 9.0;
    0.0 0.0 0.0 0.0 9.0;
]
faces = [
    1 3 1 2;
    2 2 4 2;
    3 1 3 3;
]
bad = TriangleMesh(verts, faces)
dd = diagnose(bad)
println("faces=", dd.n_faces,
    "  degenerate=", dd.n_degenerate_faces,
    "  duplicates=", dd.n_duplicate_faces,
    "  unreferenced=", dd.n_unreferenced_vertices,
    "  dup vertices=", dd.n_duplicate_vertices)
println("watertight: ", dd.watertight)

faces=4  degenerate=1  duplicates=1  unreferenced=1  dup vertices=1
watertight: false

The predicates is_watertight / is_manifold and the nonmanifold_edges / nonmanifold_vertices / boundary_edges queries back the same checks:

println(is_watertight(m), "  ", is_manifold(m))
println(isempty(nonmanifold_edges(m).edges), "  ", isempty(nonmanifold_vertices(m)))
println(isempty(boundary_edges(m).edges))

true  true
true  true
true

The repair pipeline

clean_mesh (and its alias repair_mesh) runs the standard pipeline — weld coincident vertices → drop degenerate faces → drop duplicate faces → orient → (optionally) drop small components → (optionally) fill holes → compact:

c = clean_mesh(bad)
println(repair_mesh(bad).faces == c.faces)
d3 = diagnose(c)
println(d3.n_degenerate_faces, "  ", d3.n_duplicate_faces, "  ", d3.n_unreferenced_vertices)
println(size(c.faces, 2), " face(s), ", size(c.vertices, 2), " vertex/vertices")

true
0  0  0
1 face(s), 3 vertex/vertices

Individual passes

Each pass is also exported so a caller can run exactly the repairs it needs:

# drop degenerate (zero-area) faces
v1 = [0.0 1.0 2.0 0.0 1.0; 0.0 0.0 0.0 1.0 1.0; 0.0 0.0 0.0 0.0 0.0]
m1 = remove_degenerate_faces(TriangleMesh(v1, reshape([1, 2, 3, 1, 4, 5], 3, 2)))
println(size(m1.faces, 2))                     # 1

# drop orientation-duplicate faces
v2 = [0.0 1.0 0.0 1.0 1.0; 0.0 0.0 1.0 0.0 1.0; 0.0 0.0 0.0 0.0 0.0]
m2 = remove_duplicate_faces(TriangleMesh(v2, reshape([1, 2, 3, 1, 3, 2, 1, 4, 5], 3, 3)))
println(size(m2.faces, 2))                     # 2

# drop orphaned vertices and renumber
v3 = [0.0 1.0 0.0 9.0; 0.0 0.0 1.0 9.0; 0.0 0.0 0.0 9.0]
m3 = remove_unreferenced_vertices(TriangleMesh(v3, reshape([1, 2, 3], 3, 1)))
println(size(m3.vertices, 2))                  # 3

# orient every component consistently
v4 = [0.0 1.0 0.0; 0.0 0.0 1.0; 0.0 0.0 0.0]
m4 = orient_faces(TriangleMesh(v4, reshape([1, 2, 3, 1, 3, 2], 3, 2)))
println("oriented (2 faces)")

# connected components
v5 = [0.0 1.0 0.0 5.0 6.0 5.0; 0.0 0.0 1.0 5.0 5.0 6.0; 0.0 0.0 0.0 0.0 0.0 0.0]
comps = connected_components(TriangleMesh(v5, reshape([1, 2, 3, 4, 5, 6], 3, 2)))
println(length(comps), " components")

# drop small fragments
m6 = remove_small_components(
    TriangleMesh(
        [0.0 1.0 1.0 0.0 9.0 10.0 9.0; 0.0 0.0 1.0 1.0 9.0 9.0 10.0; 0.0 0.0 0.0 0.0 0.0 0.0 0.0],
        reshape([1, 2, 3, 1, 3, 4, 5, 6, 7], 3, 3));
    min_vertices=4)
println(size(m6.faces, 2), " face(s)")

# fill holes (fan-fill boundary loops from the centroid)
hole = TriangleMesh([0.0 1.0 0.0; 0.0 0.0 1.0; 0.0 0.0 0.0], reshape([1, 2, 3], 3, 1))
filled = fill_holes(hole)
println(is_watertight(filled), "  ", size(filled.faces, 2), " faces")

1
2
3
oriented (2 faces)
2 components
2 face(s)
true  4 faces

fill_holes respects max_hole_size: loops longer than the limit are left alone. It also accepts method=:earclip (the default — triangulate the loop directly) or :fan (cone to the loop centroid).

Non-manifold repair, self-intersections, and remeshing

orient_outward reorients every component to outward normals (positive signed volume); repair_nonmanifold splits a bowtie vertex or a fin edge by duplicating the offending vertex; stitch_borders welds split seams:

bm = surface_mesh(box(1.0, 1.0, 1.0))
inward = TriangleMesh(bm.vertices, bm.faces[[3, 2, 1], :])
sv(m) = sum(dot(m.vertices[:, m.faces[1, j]], cross(
    m.vertices[:, m.faces[2, j]], m.vertices[:, m.faces[3, j]])) / 6 for j in axes(m.faces, 2))
println(sv(inward) < 0, "  →  ", sv(orient_outward(inward)) > 0)

# bowtie: two triangles sharing only vertex 1
bowtie = TriangleMesh(
    [0.0 1.0 0.0 -1.0 0.0; 0.0 0.0 1.0 0.0 0.0; 0.0 0.0 0.0 0.0 0.0],
    reshape([1, 2, 3, 1, 4, 5], 3, 2))
println(nonmanifold_vertices(bowtie))                    # [1]
fixed = repair_nonmanifold(bowtie)
println(isempty(nonmanifold_vertices(fixed)), "  ", size(fixed.vertices, 2), " vertices")
# the individual passes:
println(isempty(nonmanifold_vertices(duplicate_nonmanifold_vertices(bowtie))))
fin = TriangleMesh(
    [0.0 1.0 0.0 0.0 0.0; 0.0 0.0 1.0 0.0 0.0; 0.0 0.0 0.0 0.0 1.0],
    reshape([1, 2, 3, 1, 2, 4, 1, 2, 5], 3, 3))
println(isempty(nonmanifold_edges(duplicate_nonmanifold_edges(fin)).edges))

# a split seam (near-coincident vertices) welded back together
seam = TriangleMesh(
    [0.0 1.0 0.0 1.0 1e-4 1.0; 0.0 0.0 1.0 0.0 1e-4 1.0; 0.0 0.0 0.0 0.0 0.0 0.0],
    reshape([1, 2, 3, 4, 5, 6], 3, 2))
println(size(boundary_edges(seam).edges, 2), " → ", size(boundary_edges(stitch_borders(seam; tol=1e-3)).edges, 2))

true  →  true
[1]
true  6 vertices
true
true
6 → 4

self_intersections finds crossing faces; remove_self_intersections repairs them; voxel_remesh re-meshes through a voxel grid:

crossed = TriangleMesh(
    [0.0 2.0 0.0 2.0 1.0 1.0; 0.0 0.0 2.0 2.0 1.0 1.0; 0.0 0.0 0.0 0.0 -1.0 1.0],
    reshape([1, 2, 3, 4, 5, 6], 3, 2))
println(self_intersections(crossed))                     # [(1, 2)]
println(isempty(self_intersections(icosphere(2))))

r = voxel_remesh(surface_mesh(box(1.0, 1.0, 1.0)); n=20)
println(is_watertight(r), "  ", is_manifold(r))
println(size(remove_self_intersections(bm).faces, 2) == size(bm.faces, 2))

[(1, 2)]
true
true  true
true

doctor is the one-shot pipeline: it runs clean → non-manifold split → outward orient → fill → self-intersection removal → compact, returning the repaired TriangleMesh (inspect it with diagnose):

dirty = TriangleMesh(
    [0.0 1.0 0.0 1.0 9.0; 0.0 0.0 1.0 0.0 9.0; 0.0 0.0 0.0 0.0 9.0],
    [1 3 1 2; 2 2 4 2; 3 1 3 3])
repaired = doctor(dirty; fill=true)
d = diagnose(repaired)
println(d.n_degenerate_faces == 0, "  ", d.n_duplicate_faces == 0, "  ", is_watertight(repaired))
println(size(repaired.faces, 2), " faces")

# keep only the largest connected component (drop scan-noise fragments)
frags = TriangleMesh(
    [0.0 1.0 0.0 5.0 6.0 5.0; 0.0 0.0 1.0 5.0 5.0 6.0; 0.0 0.0 0.0 0.0 0.0 0.0],
    reshape([1, 2, 3, 4, 5, 6], 3, 2))
println(length(connected_components(frags)), " → ", size(keep_largest_component(frags).faces, 2), " face(s)")

# repair_polygon_soup: the full raw-soup pipeline (weld → clean → orient →
# stitch → fill → self-intersections), returning a watertight, manifold mesh
soup = repair_polygon_soup(icosphere(2))
println(is_watertight(soup), "  ", is_manifold(soup))

true  true  true
10 faces
2 → 1 face(s)
true  true

Next steps

STL / OBJ / PLY — where dirty scan meshes typically come from.
Watertight marching cubes — producing clean meshes in the first place.