Initializing 3D Canvas...

The Octree

2 min read•1 page

Octree Node:

1. Tracks 3D spatial boundaries (AABB). 2. Holds points up to node capacity limit. 3. Subdivides into 8 sub-octants when capacity is exceeded.
python
1# Octree Node structure
2class OctreeNode:
3    def __init__(self, bounds, capacity=8):
4        self.bounds = bounds       # AABB boundary (min_pt, max_pt)
5        self.capacity = capacity   # Maximum points before splitting
6        self.points = []           # Points in this node
7        self.children = None       # Array of 8 child nodes (if split)
8        self.is_leaf = True

An octree is a tree data structure in which each internal node has exactly eight children. It is most commonly used to partition a three-dimensional space by recursively subdividing it into eight octants.

2 min read•1 page

Sub-Octant Partitioning:

1. Calculate the midpoint coordinate of the bounding volume. 2. Use the 3-bit binary index (0-7) to determine child offsets. 3. Construct child boundaries using minimum, midpoint, and maximum coordinate components.
python
1# Divide bounding box into 8 sub-octants
2def get_octant_bounds(min_pt, max_pt, index):
3    mid = [(a + b) / 2 for a, b in zip(min_pt, max_pt)]
4    
5    # Binary representation of index determines sub-box bounds
6    x_min = mid[0] if (index & 1) else min_pt[0]
7    x_max = max_pt[0] if (index & 1) else mid[0]
8    
9    y_min = mid[1] if (index & 2) else min_pt[1]
10    y_max = max_pt[1] if (index & 2) else mid[1]
11    
12    z_min = mid[2] if (index & 4) else min_pt[2]
13    z_max = max_pt[2] if (index & 4) else mid[2]
14    
15    return (x_min, y_min, z_min), (x_max, y_max, z_max)

A parent node partitions its bounding box into eight child nodes by bisecting the volume along three orthogonal planes.

Octant Index (0-7)
0.00
2 min read•1 page

Subdivision Rules:

1. Insert point into leaf nodes based on coordinate bounds. 2. Subdivide if capacity exceeds limit. 3. Clear parent node points and set is_leaf flag to false.
python
1# Point insertion and node subdivision
2def insert_point(node, point):
3    if not node.is_inside(point):
4        return False
5        
6    if node.is_leaf:
7        if len(node.points) < node.capacity:
8            node.points.append(point)
9            return True
10        node.subdivide()  # Split into 8 children
11        
12    # Re-insert existing and new points to child octants
13    for p in node.points + [point]:
14        for child in node.children:
15            if child.insert_point(p):
16                break
17    node.points = []
18    node.is_leaf = False
19    return True

Points are added to leaf nodes. When a node exceeds capacity limits, it subdivides and moves its points to child sub-octants.

Subdivision Depth
1.00
2 min read•1 page

Nearest Point Search:

1. Calculate distance from target point to node's AABB bounds. 2. Sort sub-octants based on proximity. 3. Recurse down, pruning sub-trees when the distance exceeds current best.
python
1# Distance-based octant traversal
2def query_closest_point(node, target_pt, best_pt=None, best_dist=float('inf')):
3    if node is None:
4        return best_pt, best_dist
5        
6    # Check distance to node bounding box AABB
7    if distance_to_box(target_pt, node.bounds) >= best_dist:
8        return best_pt, best_dist # Prune
9        
10    if node.is_leaf:
11        for p in node.points:
12            d = sq_distance(p, target_pt)
13            if d < best_dist:
14                best_dist = d
15                best_pt = p
16        return best_pt, best_dist
17        
18    # Sort children based on proximity to target
19    sorted_children = sorted(node.children, key=lambda c: distance_to_box(target_pt, c.bounds))
20    for child in sorted_children:
21        best_pt, best_dist = query_closest_point(child, target_pt, best_pt, best_dist)
22        
23    return best_pt, best_dist

To perform spatial point queries, we traverse children sorted by distance to the target, pruning nodes whose bounding volumes are further than the current best distance.

Target X
4.00
Target Y
4.00
2 min read•1 page

Frustum Culling:

1. Match node bounding box against the 6 view frustum planes. 2. Discard if completely outside; accept if completely inside. 3. Recurse down children sub-nodes if partially intersecting.
python
1# Select octree nodes intersecting frustum planes
2def frustum_cull_octree(node, frustum, visible_nodes):
3    # Check node AABB intersection with 6 frustum planes
4    intersection = check_aabb_frustum(node.bounds, frustum)
5    
6    if intersection == OUTSIDE:
7        return
8        
9    if intersection == INSIDE:
10        # Fully inside, add all descendents without further testing
11        visible_nodes.extend(node.get_all_leaves())
12        return
13        
14    # Overlaps boundary, recurse children
15    if node.is_leaf:
16        visible_nodes.append(node)
17    else:
18        for child in node.children:
19            frustum_cull_octree(child, frustum, visible_nodes)

To optimize rendering pipelines, spatial nodes that fall outside the camera's view frustum are quickly discarded, focusing resources only on visible zones.

Camera FOV Angle
45.00
2 min read•1 page

Ray Traversal:

1. Calculate ray overlap entry and exit points on the node bounds. 2. If the ray misses the bounding volume, prune the subtree. 3. Recurse down children intersected along the ray's travel segment.
python
1# Slab-method Ray-AABB intersection traversal
2def ray_octree_intersect(node, ray_origin, ray_dir):
3    t_min, t_max = intersect_slabs(node.bounds, ray_origin, ray_dir)
4    
5    if t_max < 0 or t_min > t_max:
6        return [] # No intersection
7        
8    if node.is_leaf:
9        return [node] # Intersects leaf node
10        
11    # Traverse child nodes that overlap the ray path interval [t_min, t_max]
12    intersections = []
13    for child in node.children:
14        intersections.extend(ray_octree_intersect(child, ray_origin, ray_dir))
15        
16    return intersections

Ray tracing applications walk along the ray direction, testing parametric line intersections against node AABB boundary slabs to locate intersecting leaf cells.

Ray Y Offset
0.00
1 min read•1 page

Voxel Extraction:

1. Traverse tree down to occupied leaf nodes. 2. Extract cell center and bounding dimension parameters. 3. Render leaf boxes representing spatial occupancy.
python
1# Convert octree leaf nodes to voxel grid
2def get_octree_voxels(node, resolution):
3    voxels = []
4    
5    def traverse(n):
6        if n.is_leaf:
7            if n.points: # Only export occupied cells
8                center = n.bounds.center()
9                voxels.append((center, n.bounds.size()))
10            return
11        for child in n.children:
12            traverse(child)
13            
14    traverse(node)
15    return voxels

An octree can act as a multi-resolution voxelizer. By rendering the bounding volumes of occupied leaf nodes, we construct a discrete volumetric representation of continuous shape models.

Voxel Grid Size
6.00
2 min read•1 page

Clash Detection:

1. Test boundary overlap of Node A and Node B. 2. If they overlap, recursively traverse active children. 3. If both are leaf nodes, register overlap boundaries.
python
1# Intersect two Octrees recursively to detect overlaps
2def intersect_octrees(nodeA, nodeB, overlaps):
3    if not boxes_overlap(nodeA.bounds, nodeB.bounds):
4        return
5        
6    if nodeA.is_leaf and nodeB.is_leaf:
7        if len(nodeA.points) > 0 and len(nodeB.points) > 0:
8            overlaps.append((nodeA.bounds, nodeB.bounds))
9        return
10        
11    # Traverse children of overlapping nodes
12    for i in range(8):
13        childA = nodeA.children[i] if not nodeA.is_leaf else nodeA
14        childB = nodeB.children[i] if not nodeB.is_leaf else nodeB
15        intersect_octrees(childA, childB, overlaps)

Clash detection processes intersect two octrees to locate overlapping regions. By testing bounding boxes hierarchically, we discard non-overlapping branches and isolate intersections efficiently.

Bunny Offset Separation
6.00
2 min read•1 page

LooseBounds(center, half_size, k):

1. Half Size: Standard node cell half-dimension. 2. Looseness (k): Boundary overlap multiplier. 3. Expanded Bounds: Computes overlapping cell envelopes enclosing objects seamlessly.
python
1def get_loose_cell_bounds(center, half_size, k=2.0) -> tuple:
2    # Expand half_size by looseness factor k (usually 2.0 or 1.5)
3    loose_half = half_size * k
4    min_pt = [c - loose_half for c in center]
5    max_pt = [c + loose_half for c in center]
6    return min_pt, max_pt

A Loose Octree expands the boundary of each octant cell by a looseness factor k (typically k=2.0). This prevents moving objects that cross boundaries from thrashing between adjacent cells, keeping them inside a single node's enlarged volume.

Moving Sphere Center X
0.80

Related Concepts

Algorithms

Computational geometry algorithms, spatial structures, and physical simulations

Explore concept →
Spatial Trees

KD-Trees, Octrees, and BVHs.

Explore concept →
Trees & Searches

Hierarchical structures, point, range, and proximity search types.

Explore concept →