Initializing 3D Canvas...

Voronoi Diagrams

2 min read•1 page

Imagine dropping several different colored dye drops onto a piece of paper. The dye spreads out evenly in all directions. Where two colors meet, they form a straight boundary line. When all the dyes stop spreading, you have a Voronoi Diagram.

Territories of Influence:

1. You start with a set of points called Seeds. 2. The Voronoi Diagram divides the entire space into "Cells" (polygons). 3. There is exactly one Cell for each Seed. 4. The golden rule: Any location inside a Seed's Cell is closer to that Seed than to any other Seed.
python
1# Distance-Based Partitioning
2def get_voronoi_cell_for_point(target_point, all_points, resolution=100):
3    """A brute-force way to understand Voronoi territories."""
4    
5    territory_pixels = []
6    
7    # Check every pixel on the screen
8    for x in range(resolution):
9        for y in range(resolution):
10            pixel = Point(x, y)
11            
12            # Find the closest "Seed" point to this pixel
13            closest = find_closest_point(pixel, all_points)
14            
15            # If the closest seed is OUR target point, this pixel belongs to us!
16            if closest == target_point:
17                territory_pixels.append(pixel)
18                
19    return territory_pixels
View (Seeds/Spreading/Borders)
0.00
1 min read•1 page

Calculating "dye spreading" or pixel-by-pixel brute force is far too slow for computers. Instead, we use a math trick: The Voronoi Diagram is the mathematical Dual of the Delaunay Triangulation.

The Duality Trick:

1. If you want a Voronoi Diagram, first calculate the Delaunay Triangulation (which we know how to do efficiently). 2. Every Triangle in the Delaunay mesh has a Circumcenter. 3. Place a point at every single Circumcenter. These new points are the Vertices of the Voronoi Cells!4. Connect the Circumcenters of neighboring triangles to form the Voronoi edges.
python
1# Dual Transformation
2def extract_voronoi_from_delaunay(delaunay_mesh):
3    """The fast way to generate Voronoi."""
4    
5    voronoi_vertices = []
6    
7    # Every triangle circumcenter becomes a Voronoi Vertex!
8    for triangle in delaunay_mesh.triangles:
9        circumcenter = triangle.get_circumcenter()
10        voronoi_vertices.append(circumcenter)
11        
12    return voronoi_vertices
View (Delaunay/Circumcenters/Voronoi)
0.00
2 min read•1 page

There is a problem with the Duality Trick. The Delaunay triangles on the outer edge of the point cloud have Voronoi boundaries that shoot off into infinity!

Clipping to Reality:

1. A cell on the very edge of the map has no neighbor to stop it from expanding forever. 2. Mathematically, these form Voronoi Rays instead of line segments. 3. To make a usable mesh, we define a Bounding Box around our entire map. 4. We cast the infinite rays outward and calculate where they hit the Bounding Box. We clip them there, turning them into finite line segments.
python
1# Infinite Ray Truncation
2def cap_voronoi_rays(voronoi_edges, bounding_box):
3    """Clips infinite edges against a bounding box."""
4    
5    clipped_edges = []
6    
7    for edge in voronoi_edges:
8        if edge.is_infinite():
9            # Find where the ray intersects the bounding box
10            intersection = bounding_box.ray_intersect(edge.origin, edge.direction)
11            
12            # Create a finite edge ending at the boundary
13            finite_edge = create_edge(edge.origin, intersection)
14            clipped_edges.append(finite_edge)
15        else:
16            clipped_edges.append(edge)
17            
18    return clipped_edges
Rays (Infinite/Clipped/Bounded)
0.00
2 min read•1 page

At this point in the algorithm, we have a giant list of disorganized line segments. Graphics engines cannot fill lines with color or calculate their area. We need closed Polygons.

Tip-to-Tail Sorting:

1. Select a Seed. 2. Filter the giant list of edges to find only the ones that form the border of this Seed's cell. 3. These edges are mixed up: (A-B), (D-C), (B-C), (E-A), etc. 4. Write a sorting loop that connects them tip-to-tail: A-B-C-D-E-A. 5. Now you have a perfectly sorted array of vertices. You can finally create a Polygon mesh and fill it!
python
1# Gathering the Polygon
2def gather_voronoi_cell(seed_index, voronoi_edges):
3    """Sorts disorganized lines into a closed polygon loop."""
4    
5    # Get all edges that border this specific seed's territory
6    cell_edges = get_edges_for_seed(seed_index, voronoi_edges)
7    
8    # They are in random order. We must sort them so they connect tip-to-tail
9    sorted_vertices = []
10    
11    current_edge = cell_edges[0]
12    sorted_vertices.append(current_edge.start)
13    
14    while len(sorted_vertices) <= len(cell_edges):
15        next_vertex = current_edge.end
16        sorted_vertices.append(next_vertex)
17        
18        # Find the next edge that starts at 'next_vertex'
19        current_edge = find_connected_edge(next_vertex, cell_edges)
20        
21    return sorted_vertices
Assembly (Lines/Sorted/Polygon)
0.00
2 min read•1 page

If you generate a Voronoi diagram from purely random points, it looks messy. Some cells are huge, others are tiny slivers. In nature (like mud cracks, giraffe spots, or bee honeycombs), Voronoi patterns are highly regular. We can simulate this using Lloyd's Relaxation.

Centroid Shifting:

1. Generate a Voronoi diagram. 2. Calculate the exact Center of Area (Centroid) of every polygon cell. 3. Because the original Seed was placed randomly, it is almost never at the exact center of its cell. 4. Move the Seed to the Centroid. 5. Recalculate the Voronoi diagram. 6. Repeat this process a few times. The cells will magically push against each other until they form a perfect, uniform honeycomb lattice!
python
1# Lloyd's Relaxation Algorithm
2def relax_voronoi(seeds, iterations=5):
3    """Turns a random scattered Voronoi into a beautiful honeycomb."""
4    
5    for i in range(iterations):
6        # 1. Calculate the Voronoi Diagram
7        voronoi_cells = generate_voronoi(seeds)
8        
9        new_seeds = []
10        for cell in voronoi_cells:
11            # 2. Find the Center of Mass (Centroid) of the polygon cell
12            centroid = calculate_polygon_centroid(cell.vertices)
13            
14            # 3. Move the Seed to the Centroid!
15            new_seeds.append(centroid)
16            
17        seeds = new_seeds
18        
19    return seeds
Iteration (Start/Shift/Relaxed)
0.00
1 min read•1 page

In 3D graphics (especially shaders and procedural textures), we often don't want hard polygon lines. Instead, we want soft, organic patterns. We achieve this by converting Voronoi logic into a Distance Field.

Smooth Voronoi:

1. Instead of asking "Which cell do I belong to?", we ask "How far am I from my closest Seed?" 2. If a pixel is exactly on top of a Seed, its distance is 0 (we color it White). 3. As you move away from the seed, the distance increases (it fades to Black). 4. At the border between two cells, the distance to Seed A equals the distance to Seed B. This creates sharp, mountain-ridge-like borders between smooth, dark valleys!
python
1# Distance Fields
2def evaluate_distance_field(pixel, seeds):
3    """Calculates color based on distance to the closest seed."""
4    
5    # 1. Find the distance to the closest seed
6    closest_dist = get_distance_to_closest(pixel, seeds)
7    
8    # 2. Map that distance to a color gradient (e.g. 0=White, Far=Black)
9    color = map_distance_to_color(closest_dist)
10    
11    return color
Mode (Flat/Distance Field)
0.00
2 min read•1 page

In modern rendering, calculating true polygon meshes for Voronoi cells is rarely done on the CPU. Instead, it is calculated per-pixel on the GPU using a Shader. This allows for millions of moving, shifting points to generate biological, alien, or magical glowing effects in real-time.

GPU Cellular Noise:

1. Voronoi noise (often called Cellular Noise or Worley Noise) is the foundation of procedural materials like water ripples, lizard skin, and cracking lava. 2. The GPU calculates the Distance Field for every pixel on the screen simultaneously. 3. By moving the Seeds over time (using sine waves or physics), the entire diagram shifts and recalculates at 60 FPS!
python
1# Realtime Voronoi Shader
2def fragment_shader(pixel_uv, time):
3    """How modern game engines render Voronoi effects instantly."""
4    
5    # Generate moving seed points based on Time
6    seeds = generate_moving_points(time)
7    
8    # Calculate distance to closest seed
9    dist = calculate_voronoi_distance(pixel_uv, seeds)
10    
11    # Add a glowing edge effect at the borders
12    edge_glow = smoothstep(0.9, 1.0, dist)
13    
14    return edge_glow
Number of Seeds
10.00
Simulation Speed
1.00