Initializing 3D Canvas...

Delaunay Triangulation

2 min read•1 page

If you have a random scattering of points, there are millions of different ways to connect them into triangles. But in 3D graphics and engineering, we hate "skinny" or sliver triangles because they cause rendering artifacts and math errors. We want fat, well-proportioned triangles.

Delaunay Optimality:

1. The Delaunay Triangulation guarantees the "fattest" possible triangles for any given set of points. 2. It achieves this using a single, elegant rule: The Empty Circumcircle Rule. 3. Every triangle has a Circumcircle (a circle that perfectly touches its 3 corners). 4. For a triangulation to be Delaunay-valid, NO other point can exist inside the circumcircle of any triangle!
python
1# The Empty Circumcircle Rule
2def is_delaunay_valid(triangle, all_points):
3    """Checks if a triangle is mathematically optimal."""
4    
5    # 1. Find the circle that perfectly touches all 3 corners
6    circumcircle = calculate_circumcircle(triangle.v0, triangle.v1, triangle.v2)
7    
8    # 2. Check every other point in the entire dataset
9    for point in all_points:
10        if point in triangle.vertices:
11            continue
12            
13        # 3. If ANY other point is inside this circle, the triangle is BAD.
14        if circumcircle.contains(point):
15            return False
16            
17    # If the circle is completely empty of other points, it is Delaunay Valid!
18    return True
Triangulation (Bad/Delaunay)
0.00
3 min read•1 page

To check the "Empty Circumcircle Rule", we first need to mathematically construct that circle for any given triangle. We need to find its Center (the Circumcenter) and its Radius.

Perpendicular Bisectors:

1. Pick any two edges of the triangle. 2. Find the exact midpoint of those edges. 3. Draw a line perpendicular (90 degrees) to the edge, starting from the midpoint. 4. Where those perpendicular lines intersect is the true mathematical center of the circle!
python
1# Calculating the Circumcenter
2def get_circumcircle(v0, v1, v2):
3    """Finds the center of a circle that touches all 3 vertices."""
4    
5    # 1. Find the exact midpoint of two edges
6    mid_A = (v0 + v1) / 2
7    mid_B = (v1 + v2) / 2
8    
9    # 2. Find the perpendicular vectors to those edges
10    perp_A = get_perpendicular_2d(v1 - v0)
11    perp_B = get_perpendicular_2d(v2 - v1)
12    
13    # 3. The Circumcenter is exactly where those two perpendicular lines intersect!
14    center = line_intersection(mid_A, perp_A, mid_B, perp_B)
15    
16    # 4. The radius is just the distance from the center to any vertex
17    radius = distance(center, v0)
18    
19    return center, radius
Algorithm Step
0.00
2 min read•1 page

To actually build a Delaunay Triangulation, the most famous algorithm is Bowyer-Watson. Instead of trying to connect points one by one, it starts with a completed triangulation and incrementally modifies it.

The Starting Canvas:

1. Find the bounding box of your point cloud. 2. Generate a Super-Triangle: A single, massive triangle that completely surrounds every point. 3. This gives the algorithm a valid "mesh" to start carving up as it inserts points one by one. 4. At the very end of the algorithm, we will delete the Super-Triangle vertices.
python
1# Bowyer-Watson Setup
2def init_delaunay(points):
3    """Creates a massive triangle that contains all points."""
4    
5    # 1. Find the Bounding Box of all our points
6    bbox = get_bounding_box(points)
7    
8    # 2. Mathematically calculate a triangle so large that 
9    # it completely engulfs the bounding box.
10    super_triangle = create_super_triangle(bbox)
11    
12    # 3. Start our triangulation list with JUST this one triangle.
13    triangulation = [super_triangle]
14    
15    return triangulation
Setup (Points/Bounding Box/Super Triangle)
0.00
2 min read•1 page

Now that we have a starting mesh (the Super-Triangle), we insert our points one by one. When we drop a new point into the mesh, it usually ruins the Delaunay validity of the triangles around it.

Carving the Cavity:

1. Insert a new point. 2. Check the Circumcircle of every existing triangle in the mesh. 3. If the new point falls inside a triangle's circumcircle, that triangle is now "Bad". 4. Select all the Bad triangles. They form a contiguous polygon hole called the Cavity. 5. We delete the Bad triangles!
python
1# Finding Bad Triangles
2def find_bowyer_watson_cavity(new_point, current_triangles):
3    """Finds all triangles whose circumcircle contains the new point."""
4    
5    bad_triangles = []
6    
7    for triangle in current_triangles:
8        # If the new point violates the Delaunay rule for this triangle...
9        if triangle.circumcircle_contains(new_point):
10            # ...flag it for deletion!
11            bad_triangles.append(triangle)
12            
13    # The area occupied by the bad triangles forms a polygonal 'Cavity'
14    return bad_triangles
Process (Insert/Test/Delete)
0.00
1 min read•1 page

Once the Bad triangles are deleted, we are left with a polygon-shaped hole (the Cavity) inside our mesh, with our New Point sitting exactly in the middle of it.

Healing the Mesh:

1. Look at the outer edges of the Cavity. 2. Connect our New Point to every single edge of that boundary. 3. This completely seals the hole with a fan of brand new triangles. 4. Mathematically, the Bowyer-Watson algorithm guarantees that all of these new triangles perfectly satisfy the Delaunay Empty-Circle rule!
python
1# Repairing the Cavity
2def triangulate_cavity(new_point, cavity_edges, mesh):
3    """Fills the hole with new, Delaunay-valid triangles."""
4    
5    for edge in cavity_edges:
6        # Connect the new point to every edge of the cavity polygon
7        v0 = edge.start_vertex
8        v1 = edge.end_vertex
9        v2 = new_point
10        
11        new_triangle = create_triangle(v0, v1, v2)
12        mesh.add_triangle(new_triangle)
State (Hole/Filled)
0.00
2 min read•1 page

Once we have inserted every point from our dataset, the algorithm is almost finished. However, our mesh is still attached to the giant Super-Triangle we created in Step 3!

Removing Scaffolding:

1. Loop through every single triangle in our final mesh. 2. Check its 3 vertices. Are any of them the vertices of the Super-Triangle? 3. If yes, that triangle is artificial scaffolding. Delete it! 4. What remains is a perfectly convex, Delaunay-valid mesh of our exact point cloud.
python
1# Finalizing the Mesh
2def finalize_delaunay(mesh, super_triangle):
3    """Removes the artificial boundary to reveal the final mesh."""
4    
5    final_triangles = []
6    
7    for triangle in mesh.triangles:
8        # Does this triangle touch any of the 3 vertices of the Super-Triangle?
9        shares_vertex = triangle.shares_any_vertex_with(super_triangle)
10        
11        if shares_vertex:
12            # Delete it! It was just scaffolding.
13            continue
14        else:
15            final_triangles.append(triangle)
16            
17    mesh.triangles = final_triangles
18    return mesh
State (With Super/Cleaned)
0.00
2 min read•1 page

The most common use of Delaunay Triangulation in computer graphics is generating Terrain or Topography. LiDAR scanners or drones capture millions of points on the ground. By running Delaunay on those points in 2D (ignoring height), and then lifting the vertices to their true 3D height, we generate a perfect landscape.

5D Meshing:

1. If we ran Delaunay in full 3D, it would build solid chunks of volume (tetrahedrons) out of the points. 2. We only want a surface, not a volume. 3. We project all points flat to the ground, connect them optimally, and then pull them back up!
python
1# 2.5D Delaunay Elevation
2def generate_terrain(point_cloud_2d, elevation_data):
3    """Lifts a flat Delaunay mesh into 3D topography."""
4    
5    # 1. Run Delaunay on the X,Y coordinates only (ignore Z)
6    mesh = run_bowyer_watson(point_cloud_2d)
7    
8    # 2. Now that we have perfectly fat triangles, apply the Z heights
9    for vertex in mesh.vertices:
10        vertex.z = elevation_data.get_height(vertex.x, vertex.y)
11        
12    return mesh
Auto-Rotate
1.00
Elevation (2D/3D)
0.00