Octree 3D Collision Detection in Delphi

Summary

In this article, I demystify the often-intimidating Octree by drawing parallels to everyday experiences—like organizing your home into labelled drawers—and then delve into the Delphi code behind GLScene’s Octree implementation to reveal why each function exists and how it makes collision detection astonishingly efficient. You’ll discover how subdividing space into eight cubes prevents you from checking every triangle in your scene, and see the code patterns that power real-time physics and graphics.

Why Octrees Matter

Imagine you want to find a specific book in a library of thousands. Instead of scanning every shelf, librarians group books by genre, then by author, and finally by title—dramatically cutting down lookup time. Similarly, an Octree partitions 3D space into eight “bins” at each level, so collision queries only inspect a tiny subset of geometry. In large scenes with millions of triangles, this culling transforms an O(n²) brute-force problem into near O(n log n) performance.

A Relatable Analogy

Think of your game world as a city:

• Root Node: The entire metropolitan area.
• Child Nodes: Districts like Downtown, Uptown, etc.
• Leaf Nodes: Individual blocks where houses (triangles) live.

When a car (ray or sphere) drives through the city, you don’t check every house—only the blocks on its path. This selective search is what makes Octrees shine in collision detection and ray casting.

Bounding Volumes: AABB and Bounding Spheres

Before diving into detailed Octree traversal, broad-phase collision detection often starts with simple bounding volumes like Axis-Aligned Bounding Boxes and bounding spheres, which quickly eliminate pairs of objects that cannot collide.

Axis-Aligned Bounding Boxes (AABB) wrap objects in non-rotated boxes aligned to coordinate axes, enabling overlap tests by comparing min and max extents on each axis. AABB collision detection requires checking for gaps along any axis—if no gap exists, the boxes overlap, indicating potential collision. This simple test is extremely efficient (constant time per pair) and commonly used in the broad phase of physics engines to cull unlikely pairs before finer checks like triangle-triangle tests.

Bounding spheres encase objects in a rotation-invariant volume defined by a center and radius, making them ideal for rotating or moving entities without recomputing extents.
Sphere-sphere collision tests reduce to comparing the squared distance between centers against the squared sum of radii, offering constant-time checks with minimal computation.
In some pipelines, objects undergo a coarse sphere-sphere test first, followed by an AABB or Octree traversal for precise collision resolution.
While spheres are invariant to rotation and simple to update, they can vastly overestimate volumes for elongated shapes, leading to more narrow-phase checks than tightly fitting AABBs.
AABB and spheres can also be used within an Octree node as the node’s bounding volume, combining the hierarchical culling of Octrees with the speed of simple bounding tests.
These tests are often one of the first steps in collision detection tutorials and references due to their ease of implementation and effectiveness.
Together with the Octree’s spatial partitioning, bounding volumes form a robust multi-level culling strategy in real-time applications.

Key Code Components Explained

1. Splitting Space: Refine

procedure TOctree.Refine(parentNode: POctreeNode; level: Integer);
begin
  if level < MaxOlevel then
    for n:=0 to 7 do begin
      New(newnode);  // Allocate one of 8 children
      GetExtent(FlagMin[n], parentNode, newnode^.MinExtent);
      GetExtent(FlagMax[n], parentNode, newnode^.MaxExtent);
      parentNode^.ChildArray[n] := newnode;
      Refine(newnode, level+1);  // Recurse until max depth
    end;
end;

Here, Refine carves each parent cube into eight smaller ones, much like folding a map into finer and finer sections. This upfront work ensures that later queries can zoom into the exact region where collisions happen.

2. Computing Bounds: GetExtent

procedure TOctree.GetExtent(
  const flags: array of byte; ParentNode: POctreeNode; var result: TAffineFLTVector);
var
  emin, emax: TAffineFLTVector;
begin
  emin := ParentNode^.MinExtent;
  emax := ParentNode^.MaxExtent;
  for n:=0 to 2 do
    case flags[n] of
      MIN: result[n] := emin[n];
      MID: result[n] := (emin[n] + emax[n]) * 0.5;
      MAX: result[n] := emax[n];
    end;
end;

This routine uses FlagMin and FlagMax arrays to decide whether a child’s coordinate comes from the parent’s min, midpoint, or max. It’s like pinpointing a drawer’s exact boundaries when subdividing your storage box.

3. Gathering Leaf Nodes: WalkTriToLeafx

procedure TOctree.WalkTriToLeafx(
  Onode: POctreeNode; const v1, v2, v3: TAffineFLTVector);
begin
  if TriIntersectNode(Onode^.MinExtent, Onode^.MaxExtent, v1,v2,v3)
    or PointInNode(Onode^.MinExtent,Onode^.MaxExtent,v1)
    or PointInNode(...,v2) or PointInNode(...,v3) then
  begin
    if Assigned(Onode^.ChildArray[0]) then
      for m:=0 to 7 do WalkTriToLeafx(Onode^.ChildArray[m], v1,v2,v3)
    else
      ResultArray.Add(Onode);
  end;
end;

When inserting a triangle, WalkTriToLeafx descends the tree, testing only nodes whose AABB overlaps the triangle. This ensures each triangle only lands in the small cubes that truly contain it—avoiding wasted storage and checks later on.

4. Smart Culling: TriIntersectNode

function TOctree.TriIntersectNode(
  const minE,maxE,v1,v2,v3: TAffineVector): Boolean;
begin
  for n:=0 to 5 do begin
    // Build face corners
    if tri_tri_intersect(v1,v2,v3, f0,f1,f2)=1 then Exit(True)
    else if tri_tri_intersect(v1,v2,v3, f2,f3,f0)=1 then Exit(True);
  end;
  Result := False;
end;

This method applies optimized triangle-triangle intersection tests (Graphics Gems) on each AABB face, weeding out non-overlapping nodes before deeper checks.

Beyond Basics: Sphere Sweeps

function TOctree.SphereSweepIntersect(...): Boolean;
begin
  WalkSphereToLeaf(RootNode, rayStart, velocity+radius);
  // For each candidate triangle:
  // 1. Ray-plane and sphere-plane tests
  // 2. Ray-triangle tests for direct hits
  // 3. Closest-point-on-edge for glancing collisions
  // 4. Select minimal travel distance
end;

SphereSweepIntersect elevates collision detection: it sweeps a sphere through space, sliding along triangles or edges for realistic physics—even handling glancing blows accurately.

Performance Tips

• Depth vs. Leaf Size: Too deep → many nodes; too shallow → large leaf lists. Aim for 5–8 triangles per leaf for balanced performance.
• Static vs. Dynamic: Pre-build Octrees for static worlds; for moving objects, consider dynamic insert/remove or hybrid BVH-Octree approaches.
• Subdivision Threshold: Stop when triangle-count per leaf < threshold to avoid overhead.

Conclusion

Octrees pack a punch by mimicking our everyday strategies for organizing and searching large datasets. With just a few hundred lines of Delphi code, GLScene’s Octree delivers lightning-fast collision queries, bridging the gap between academic geometry algorithms and exhilarating real-time applications. Whether you’re building a physics engine, a game, or a rendering tool, mastering these patterns will supercharge your spatial queries.