Convex Hull

1 min read•1 page

Imagine wrapping a rubber band around a pegboard. The rubber band snaps tight, forming theConvex Hull of the pegs. It is the smallest possible convex shape that completely encloses a set of points.

Convex vs Concave:

1. Convex: A shape with no dents or indentations. If you draw a line between ANY two points inside the shape, the line never exits the shape. 2. Concave (Non-Convex): A shape with a dent. A line between two internal points might pass through empty space outside the shape. 3. The Convex Hull is incredibly important for physics engines (collision detection) because testing collisions against a convex shape is mathematically extremely fast.

python

1# Convex Geometry Concept
2def is_convex(shape):
3    """A shape is convex if a line between ANY two points stays inside it."""
4    
5    for p1 in shape.get_random_points():
6        for p2 in shape.get_random_points():
7            
8            line = create_line(p1, p2)
9            if not shape.contains(line):
10                return False
11                
12    return True

View (Points/Convex Hull)

0.00

2 min read•1 page

To build a Convex Hull algorithm from scratch, we must start with the most foundational math operation in Computational Geometry: The Orientation Check. Given 3 points in a sequence, does the path bend Left or Right?

The 2D Cross Product:

1. Given a line segment from p1 to p2. 2. We want to test a third point p3. 3. The 2D Cross Product returns a single number. 4. A Positive result means p3 is to the Left of the line. A Negative result means it is to the Right.

python

1# 2D Cross Product (Orientation)
2def get_turn_direction(p1, p2, p3):
3    """Determines if the path p1->p2->p3 turns Left or Right."""
4    
5    # This is a specialized 2D cross product of vectors (p2-p1) and (p3-p2)
6    cross_product = (p2.x - p1.x) * (p3.y - p2.y) - (p2.y - p1.y) * (p3.x - p2.x)
7    
8    if cross_product > 0:
9        return "Left Turn" (Counter-Clockwise)
10    elif cross_product < 0:
11        return "Right Turn" (Clockwise)
12    else:
13        return "Collinear" (Straight Line)

Point p3 Position (Left/Straight/Right)

0.00

2 min read•1 page

How do we actually build the hull using the Turn Check? One of the oldest algorithms is the Jarvis March. From our current point on the boundary, we want to find the next point that makes the widest possible "Right Turn".

Iterative Swapping:

1. Stand at the current point on the boundary. 2. Guess that point A is the next boundary point. 3. Check point B. Does the path Current->A->B turn Right? If so, B is closer to the true boundary than A! Update guess to B. 4. Check point C. Does Current->B->C turn Right? Yes? Update guess to C. 5. After checking every point, your final guess is guaranteed to be the next point on the Convex Hull.

python

1# Finding the next point on the hull
2def find_next_hull_point(current_point, all_points):
3    """Finds the most 'Rightward' point from the current position."""
4    
5    # Start by guessing the first point in the list is the next hull point
6    next_point = all_points[0]
7    
8    for candidate in all_points:
9        if candidate == current_point:
10            continue
11            
12        # If the candidate makes a Right Turn compared to our current guess,
13        # it is a BETTER guess! Swap it.
14        turn = get_turn_direction(current_point, next_point, candidate)
15        
16        if turn == "Right Turn":
17            next_point = candidate
18            
19    return next_point

Candidate Check (A/B/C)

0.00

2 min read•1 page

By repeating the Jarvis March sweep, we can "wrap" the entire set of points. We just need a starting point, and a way to know when to stop.

Closing the Loop:

1. Start: Find the point with the lowest X coordinate. It is mathematically guaranteed to be on the boundary. 2. Loop: Use the Sweep algorithm to find the next point, add it to the Hull list, and move there. 3. End: When the Sweep algorithm suggests the Start Point as the "next" point, the rubber band has snapped completely shut!

python

1# Full 2D Convex Hull
2def jarvis_march(points):
3    """Wraps the points until we hit the start again."""
4    
5    hull = []
6    
7    # 1. Find the leftmost point (guaranteed to be on the hull)
8    start_point = find_leftmost_point(points)
9    current_point = start_point
10    
11    while True:
12        hull.append(current_point)
13        
14        # 2. Find the next point using our Sweep method
15        next_point = find_next_hull_point(current_point, points)
16        
17        # 3. If the next point is our Start Point, we've closed the loop!
18        if next_point == start_point:
19            break
20            
21        current_point = next_point
22        
23    return hull

Algorithm Loop

0.00

2 min read•1 page

In 3D, we can't just connect lines. We have to build a polyhedron (a mesh of triangles). The 3D equivalent of "Gift Wrapping" is the QuickHull algorithm.

Seeing the Horizon:

1. Imagine we have a small starter hull, and we want to add a new point outside of it. 2. Imagine a lightbulb is placed at that new point. It illuminates the side of the hull facing it. 3. The boundary between the illuminated faces and the dark faces forms a continuous loop of edges. This is the Horizon. 4. We delete all the illuminated faces, and create new triangles connecting the Horizon edges to the new point!

python

1# 3D Horizon Edge Detection
2def find_horizon(hull_faces, new_point):
3    """Finds the 'terminator line' visible from the new point."""
4    
5    horizon_edges = []
6    
7    for face in hull_faces:
8        # A face is 'visible' if the new point is in front of it
9        # (checked using the Dot Product of the face normal and the point vector)
10        is_visible = is_face_visible(face, new_point)
11        
12        if is_visible:
13            for edge in face.edges:
14                # If the neighboring face across this edge is NOT visible,
15                # then this edge is on the Horizon!
16                if not is_face_visible(edge.neighbor_face, new_point):
17                    horizon_edges.append(edge)
18                    
19    return horizon_edges

Auto-Rotate

1.00

Show (Illuminated/Horizon)

0.00

2 min read•1 page

Once the Horizon is found, the actual geometry update is simple. We delete the old faces that are "inside" the new expanded volume, and build a new cone of triangles to seal the hole.

Stitching the Mesh:

1. Delete all faces that the "lightbulb" point could see. 2. This leaves a jagged hole in the mesh. The edges of this hole are exactly the Horizon edges. 3. Stitch new triangles from each Horizon edge to the new point. 4. Repeat this for every point in the cloud until all points are inside the hull!

python

1# QuickHull 3D Step
2def add_point_to_hull(mesh, horizon_edges, new_point):
3    """Deletes visible faces and builds a new 'cone' to the new point."""
4    
5    # 1. Delete all faces that were visible to the lightbulb
6    mesh.delete_faces(visible_faces)
7    
8    # 2. For every edge on the Horizon loop, create a new triangle 
9    # connecting that edge to the new point.
10    for edge in horizon_edges:
11        v0 = edge.start_vertex
12        v1 = edge.end_vertex
13        v2 = new_point
14        
15        # Ensure the winding order is correct so normals face outward!
16        new_face = create_face(v0, v1, v2)
17        mesh.add_face(new_face)
18        
19    return mesh

Assembly (Hole/Cone/Complete)

0.00

1 min read•1 page

Why do we care about the Convex Hull? In physics simulations (like dropping a Stanford Bunny into a box), calculating collisions against the bunny's true mesh (thousands of concave triangles) is painfully slow.

Collision Proxies:

1. Before the physics simulation starts, we calculate the Convex Hull of the model. 2. The Hull has far fewer triangles than the original mesh. 3. Because the Hull is perfectly convex, we can use lightning-fast algorithms (like GJK) to check for collisions. 4. The physics engine uses the Hull to bounce the bunny around, while the graphics engine draws the true high-res mesh!

python

1# Collision Proxies
2def create_physics_hull(mesh):
3    """Creates a fast collision shape from a high-poly mesh."""
4    
5    # Extract just the raw points from the mesh
6    point_cloud = mesh.get_vertices()
7    
8    # Run the QuickHull algorithm
9    hull_mesh = generate_quickhull(point_cloud)
10    
11    return hull_mesh

Auto-Rotate

1.00

View (Bunny/Hull/Both)

0.00