Spatial Grids

2 min read•1 page

In polygon modeling, objects exist anywhere in smooth, continuous space. In Voxelization, we force the world into a rigid, discrete Grid (like Minecraft blocks or a 3D spreadsheet). This is called Discretization.

Defining the Boundaries:

1. We cannot make an infinite grid, it would crash the computer's memory! 2. First, we find the absolute minimum and maximum coordinates of our object (its Bounding Box). 3. We choose a Cell Size (resolution). 4. We divide the bounding box by the cell size to determine exactly how many rows, columns, and layers our grid requires.

python

1# Calculating the Grid Extents
2def create_grid(points, cell_size):
3    """Defines the boundaries of our Minecraft world."""
4    
5    # 1. Find the Bounding Box of the entire point cloud
6    min_x = min([p.x for p in points])
7    max_x = max([p.x for p in points])
8    # ... repeat for Y and Z
9    
10    # 2. Divide by the cell size to find out how many 
11    # rows, columns, and layers we need!
12    count_x = math.ceil((max_x - min_x) / cell_size)
13    count_y = math.ceil((max_y - min_y) / cell_size)
14    count_z = math.ceil((max_z - min_z) / cell_size)
15    
16    return min_x, min_y, min_z, count_x, count_y, count_z

Resolution (Cell Size)

2.00

2 min read•1 page

A standard 3D point has floating-point coordinates like X: 1.2345, Y: -4.9876. These numbers are infinitely precise. Grids, however, are made of solid, countable blocks. We must convert these floats into integers. This is called Quantization.

Flooring to Integers:

1. First, shift the point so it is relative to the minimum corner of our grid. 2. Divide the coordinate by the Cell Size. For example, if X is 5.5 and Cell Size is 2.0, we get 2.75. 3. Apply a mathematical Floor function (drop the decimal). 2.75 becomes integer 2! 4. The point now officially belongs to Column 2 of the grid. Any other point that falls between 4.0 and 5.999 will also be quantized to Column 2.

python

1# Quantizing Floating Point to Integers
2def get_cell_coordinates(point, min_corner, cell_size):
3    """Converts a float (1.234, 4.567) into an integer cell index (1, 4)."""
4    
5    # 1. Shift the point relative to the bottom-left corner of the grid
6    local_x = point.x - min_corner.x
7    local_y = point.y - min_corner.y
8    local_z = point.z - min_corner.z
9    
10    # 2. Divide by the size of the cells
11    # 3. Floor the result! (Chop off all decimal places)
12    grid_x = math.floor(local_x / cell_size)
13    grid_y = math.floor(local_y / cell_size)
14    grid_z = math.floor(local_z / cell_size)
15    
16    return grid_x, grid_y, grid_z

Process (Raw / Shifted / Quantized)

0.00

2 min read•1 page

Computer memory (RAM) is not 3D. RAM is a single, massive, 1-dimensional line of data. We cannot ask the computer to "store this in box 2, 4, 3". We have to convert our 3D grid coordinate into a 1D Index.

Flattening Space:

1. We use a formula called Row-Major order flattening. 2. We calculate how many total boxes fit on a single flat layer (count_x * count_y). 3. We multiply that by our grid_z to skip all the layers below us. 4. We calculate how many boxes are in a single row (count_x) and multiply by our grid_y to skip all rows below us on this layer. 5. Finally, we add our grid_x position. 6. We have converted (2, 4, 3) into a single ID number like 342.

python

1# Flat Array Indexing
2def get_hash_key(grid_x, grid_y, grid_z, count_x, count_y):
3    """Turns a 3D index into a single 1D array index."""
4    
5    # Imagine a bookshelf:
6    # 1. Skip over all the completed 'shelves' below you (grid_z)
7    # 2. Skip over all the completed 'rows' on your shelf (grid_y)
8    # 3. Add your position in the current row (grid_x)
9    
10    index = grid_x + (grid_y * count_x) + (grid_z * count_x * count_y)
11    
12    return index

Layer Z

0.00

Row Y

0.00

Col X

0.00

2 min read•1 page

Now that every possible 3D box has a unique 1D ID number, we create a giant List in the computer's memory. The List has exactly as many slots as there are boxes. Each slot is an empty list, waiting to act as a Bucket.

Filling the Buckets:

1. We look at a massive Point Cloud of 1 million points. 2. We loop through the points one by one. 3. For every point, we calculate its Hash ID (e.g., Bucket 342). 4. We toss that point into Bucket 342. 5. After the loop finishes, we have magically sorted 1 million scattered points into perfectly organized spatial boxes.

python

1# Creating the Storage Array
2def insert_points_into_grid(points, total_cell_count):
3    """Sorts all points into their respective boxes."""
4    
5    # 1. Create a giant empty list of lists (Buckets)
6    grid_buckets = [ [] for _ in range(total_cell_count) ]
7    
8    # 2. Put every point into a bucket based on its Hash ID
9    for pt in points:
10        # Get coordinates
11        gx, gy, gz = get_cell_coordinates(pt)
12        
13        # Get ID
14        bucket_id = get_hash_key(gx, gy, gz)
15        
16        # Add the point to the bucket
17        grid_buckets[bucket_id].append(pt)
18        
19    return grid_buckets

Insert Points

0.00

3 min read•1 page

Why did we do all of this math just to put points in boxes? Speed.If you have a 1-Million point cloud, and you want to find all points within a 2-meter radius of your mouse cursor, checking every single point would require 1 million distance calculations per frame. Your computer would freeze.

Skipping 99% of the Work:

1. We take our Mouse Cursor position and Quantize it to find out which Box we are in. 2. We know our Search Radius is 2 meters, and our Grid Cells are 1 meter wide. Therefore, we only need to look in the boxes immediately adjacent to us! 3. We calculate the Hash IDs of those 27 nearby boxes, and we grab their point lists. 4. Instead of checking 1 million points, we only check the 50 points that happen to be inside those 27 boxes. 5. The game runs at a smooth 60 Frames Per Second.

python

1# Extremely Fast Searching
2def find_points_in_radius(query_pt, radius, grid_buckets, cell_size):
3    """How to search 1 million points without lagging."""
4    
5    found_points = []
6    
7    # 1. Which box is our query point in?
8    qx, qy, qz = get_cell_coordinates(query_pt)
9    
10    # 2. How many boxes do we need to check? (Radius / CellSize)
11    box_range = math.ceil(radius / cell_size)
12    
13    # 3. Only look inside the nearby boxes!
14    for x in range(qx - box_range, qx + box_range + 1):
15        for y in range(qy - box_range, qy + box_range + 1):
16            for z in range(qz - box_range, qz + box_range + 1):
17                
18                bucket_id = get_hash_key(x, y, z)
19                points_to_check = grid_buckets[bucket_id]
20                
21                # Check actual distance (Math.sqrt) only for these few points
22                for pt in points_to_check:
23                    if distance(query_pt, pt) <= radius:
24                        found_points.append(pt)
25                        
26    return found_points

Search Radius (Boxes)

1.00

1 min read•1 page

Spatial Grids are not just for searching. They are the first step in converting a Point Cloud (like LiDAR scan data) back into a solid 3D mesh. To do this, we need to know which parts of the grid are "Solid" and which are "Empty Air".

Thresholding:

1. We look at every Bucket in our grid. 2. We count how many points landed inside it. 3. If a Bucket has 0 points, it is clearly empty air. 4. If a Bucket has 1 or 2 points, it might just be sensor noise or dust. 5. If a Bucket has 10 points, it is definitely part of a solid surface! 6. We set a Density Threshold. Any box with more points than the threshold is rendered as a solid Minecraft block.

python

1# Calculating Grid Density
2def calculate_voxel_density(grid_buckets):
3    """How full is each box?"""
4    
5    dense_voxels = []
6    
7    for bucket in grid_buckets:
8        # Check how many points fell into this box
9        point_count = len(bucket.points)
10        
11        # If it has more than 5 points, we consider it "Solid"
12        if point_count > 5:
13            dense_voxels.append(bucket)
14            
15    return dense_voxels

Density Threshold

3.00

2 min read•1 page

When we combine Discretization, Quantization, Hash Mapping, and Density Thresholding, we get a completeVoxelization pipeline. We can take any raw, messy Point Cloud scan and turn it into a solid, organized block structure.

Volumetric Data:

1. A Voxel (Volumetric Pixel) is exactly what we have been building: a 3D grid cell that has a value (solid or empty). 2. Voxels are incredibly useful because they have a strict, predictable size. 3. You can easily do physics collisions against voxels (Minecraft block physics), whereas doing physics against 1 million raw points is impossible. 4. The downside? Voxels look blocky. In the next article, we will learn how to turn these blocks back into a smooth mesh!

python

1# Point Cloud Voxelization
2def voxelize_bunny(bunny_points, resolution):
3    """Minecraft-ifies a high-res 3D scan."""
4    
5    # 1. Create the grid based on the Bunny's bounding box
6    grid = create_grid(bunny_points, resolution)
7    
8    # 2. Toss all the points into the buckets
9    buckets = insert_points(bunny_points, grid)
10    
11    # 3. Find the dense boxes
12    solid_voxels = calculate_voxel_density(buckets)
13    
14    return solid_voxels

Grid Resolution (Low/Med/High)

0.00