Initializing 3D Canvas...

The Octree

1 min read•1 page

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.

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
2 min read•1 page

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

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)
Octant Index (0-7)
0.00
2 min read•1 page

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

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
Subdivision Depth
1.00
2 min read•1 page

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.

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
Target X
4.00
Target Y
4.00
2 min read•1 page

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

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)
Camera FOV Angle
45.00
2 min read•1 page

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

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 Y Offset
0.00
1 min read•1 page

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 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
Voxel Grid Size
6.00
2 min read•1 page

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

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)
Bunny Offset Separation
6.00