Hole Filling

2 min read•1 page

The first step in repairing a damaged 3D model is identifying the holes. Using the Manifold rules from the previous chapter, we simply scan the geometry for any edge that belongs to exactly one triangle. These are called Naked Edges or Border Edges.

Naked Edge Rule:

1. Break every triangle down into 3 edges. 2. Count how many triangles share each edge. 3. If count == 2, the edge is internal and solid. 4. If count == 1, the edge is on a boundary (a hole).

python

1# Border Edge Detection
2def find_border_edges(faces):
3    """Finds edges that are only shared by one face."""
4    edge_counts = {}
5    
6    # Count occurrences of each edge
7    for face in faces:
8        edges = [(face[0], face[1]), (face[1], face[2]), (face[2], face[0])]
9        for e in edges:
10            # Sort to ensure (1,2) and (2,1) count as the same edge
11            sorted_e = tuple(sorted(e))
12            edge_counts[sorted_e] = edge_counts.get(sorted_e, 0) + 1
13            
14    # Return edges with count == 1
15    borders = [e for e, count in edge_counts.items() if count == 1]
16    return borders

Highlight Borders

1.00

2 min read•1 page

After finding all Naked Edges, the algorithm chains them together end-to-end to form closed loops. However, a mesh might have an outer boundary (like the edge of a flat sheet) as well as internal holes. We must separate the holes we want to fill from the boundaries we want to keep.

Loop Filtering:

1. Chain naked edges into continuous loops. 2. Calculate the perimeter or bounding box of each loop. 3. The largest loop is usually the outer boundary of the object. 4. All smaller loops are internal holes to be repaired.

python

1# Filtering Internal vs External Loops
2def identify_holes(loops, bounding_box):
3    """Sorts boundary loops into 'outer bounds' vs 'internal holes'."""
4    holes = []
5    outer_boundary = None
6    
7    # A simple heuristic: The loop with the largest bounding box 
8    # or the longest total perimeter is usually the outer boundary.
9    max_length = 0
10    
11    for loop in loops:
12        length = calculate_perimeter(loop)
13        if length > max_length:
14            max_length = length
15            # If we already had a max, the old max was actually a hole
16            if outer_boundary is not None:
17                holes.append(outer_boundary)
18            outer_boundary = loop
19        else:
20            holes.append(loop)
21            
22    return holes, outer_boundary

Algorithm Step (All/Measure/Filter)

0.00

2 min read•1 page

Triangulating an arbitrary 3D hole is mathematically complex because the vertices might be warped in 3D space. The standard approach is to project the 3D hole onto a 2D "Best Fit Plane", perform standard 2D triangulation there, and then map the resulting triangles back to 3D.

Projection Mapping:

1. Find the Centroid (average position) of the hole's vertices. 2. Calculate the Best Fit Normal (using Newell's method or PCA). 3. Flatten the 3D vertices onto this plane to get 2D coordinates.

python

1# Finding the Best Fitting Plane
2def project_hole_to_2d(loop_vertices):
3    """Projects a 3D hole onto a 2D plane for triangulation."""
4    
5    # 1. Calculate the Centroid
6    centroid = sum(loop_vertices) / len(loop_vertices)
7    
8    # 2. Calculate the average Normal (using Newell's Method or PCA)
9    normal = calculate_best_fit_normal(loop_vertices)
10    
11    # 3. Create a 2D coordinate system on that plane
12    u_axis, v_axis = get_plane_axes(normal)
13    
14    # 4. Project all 3D points onto this 2D plane
15    points_2d = []
16    for p in loop_vertices:
17        vec = p - centroid
18        u = vec.dot(u_axis)
19        v = vec.dot(v_axis)
20        points_2d.append(Point2D(u, v))
21        
22    return points_2d, plane_matrix

Projection Amount

0.00

2 min read•1 page

With our hole safely flattened onto a 2D plane, it is treated as a simple 2D polygon. The Ear Clipping algorithm traverses the perimeter looking for "ears" — convex corners that can be sliced off to form a triangle without trapping any other vertices inside.

Ear Clipping:

1. Look at three sequential points: A, B, C. 2. Check if the interior angle is convex (< 180 degrees). 3. Check if any other point in the polygon lies inside triangle ABC. 4. If valid, save ABC as a new face, remove B from the boundary, and repeat until done.

python

1# Ear Clipping Algorithm
2def triangulate_2d_polygon(vertices_2d):
3    """Cuts 'ears' off a 2D polygon until only a triangle remains."""
4    triangles = []
5    points = list(vertices_2d)
6    
7    while len(points) > 3:
8        for i in range(len(points)):
9            prev_pt = points[i - 1]
10            curr_pt = points[i]
11            next_pt = points[(i + 1) % len(points)]
12            
13            # Check if this corner forms an "Ear"
14            if is_convex_angle(prev_pt, curr_pt, next_pt):
15                # Ensure no other points are inside this triangle
16                if not any_point_in_triangle(points, prev_pt, curr_pt, next_pt):
17                    # It's an ear! Clip it.
18                    triangles.append([prev_pt, curr_pt, next_pt])
19                    points.pop(i)
20                    break # Restart search
21                    
22    # Add final remaining triangle
23    triangles.append(points)
24    return triangles

Clipping Steps

0.00

2 min read•1 page

The triangulation gives us a set of 2D faces. We map those faces back to the original 3D indices of the hole's perimeter. Because the patch uses the exact same vertex indices as the boundary, stitching it into the main mesh simply means appending the new faces to the master list.

Welding Process:

1. Map 2D patch triangles back to original 3D vertex indices. 2. Append new faces to the mesh. 3. Re-run the Watertight Check. The naked edges now have twins!

python

1# Stitching the Patch into the Main Mesh
2def append_patch_to_mesh(main_mesh, patch_faces, hole_vertices_3d):
3    """Adds the new faces to the mesh and updates topology."""
4    
5    # 1. We don't need to add new vertices, because the patch 
6    # uses the existing boundary vertex indices!
7    
8    # 2. Add the new triangulated faces to the main face list
9    for face in patch_faces:
10        # face contains indices pointing to main_mesh.vertices
11        main_mesh.faces.append(face)
12        
13    # 3. Re-build the Half-Edge graph
14    # The naked edges will now find their twins in the new patch!
15    main_mesh.rebuild_topology()
16    
17    return main_mesh

Stitch Patch (No/Yes)

0.00

2 min read•1 page

A planar patch will often look flat and artificial when stitched into a curved, organic surface. To make the repair invisible, we apply Laplacian Smoothing (or Fairing) specifically to the new vertices generated inside the hole, while keeping the boundary vertices firmly locked in place.

Laplacian Smoothing:

1. Identify vertices strictly inside the new patch (excluding the boundary). 2. For each vertex, calculate the average position of all its connected neighbors. 3. Move the vertex slightly towards that average. 4. Repeat for several iterations. The patch will "relax" into a smooth curve.

python

1# Laplacian Smoothing of the Patch
2def smooth_patch_vertices(mesh, patch_vertices, iterations=5):
3    """Relaxes the new vertices so they blend seamlessly."""
4    
5    # We only move the vertices that were inside the hole.
6    # The boundary vertices must stay locked to preserve the original shape.
7    
8    for _ in range(iterations):
9        for v in patch_vertices:
10            if v.is_boundary:
11                continue
12                
13            # Find all neighboring vertices connected by an edge
14            neighbors = get_connected_neighbors(mesh, v)
15            
16            # Move the vertex towards the average position of its neighbors
17            avg_pos = sum(neighbors) / len(neighbors)
18            v.position = v.position * 0.5 + avg_pos * 0.5

Smoothing Iterations

0.00

2 min read•1 page

In production environments (like preparing medical scans or 3D scanning data for 3D printing), models often contain hundreds of small micro-holes.

Automated Repair:

1. The topology graph is generated. 2. All naked loops are extracted and measured. 3. The Ear-Clipping and Laplacian algorithms run in a loop over every detected hole. 4. The output is guaranteed to be a solid, watertight manifold ready for manufacturing.

python

1# Automated Hole Filling Workflow
2def repair_mesh(mesh):
3    """Executes the full automated repair pipeline."""
4    
5    # 1. Build Topology
6    edges = build_half_edges(mesh.faces)
7    
8    # 2. Extract Holes
9    loops = extract_boundary_loops(edges)
10    holes, outer = identify_holes(loops)
11    
12    # 3. Process Each Hole
13    for hole_vertices in holes:
14        # Flatten
15        v2d, p_mat = project_hole_to_2d(hole_vertices)
16        
17        # Triangulate
18        faces_2d = triangulate_2d_polygon(v2d)
19        
20        # Stitch
21        append_patch_to_mesh(mesh, faces_2d, hole_vertices)
22        
23        # Fairing
24        smooth_patch_vertices(mesh, new_internal_vertices)
25        
26    return mesh

Execute Repair

0.00

Auto-Rotate

1.00