K-D Tree (3D)

Module defined in lua/common/kdtreebox3d.lua. K-d tree implementation for 3D axis-aligned bounding boxes (6 dimensions: xmin, ymin, zmin, xmax, ymax, zmax). Efficient spatial range queries for 3D bounding volumes.

---

Exports

Functions

kdtreebox3d.new(itemCount)

Creates a new empty 3D box k-d tree.

• Parameters:
  • itemCount - number|nil - Expected item count for pre-allocation
• Returns: kdTree - Tree object

Instance Methods

tree:preLoad(id, xmin, ymin, zmin, xmax, ymax, zmax)

Adds an item to the pre-load buffer.

• Parameters:
  • id - any - Item identifier
  • xmin, ymin, zmin, xmax, ymax, zmax - number - 3D bounding box coordinates

tree:build()

Constructs the k-d tree from pre-loaded items.

tree:query(query_xmin, query_ymin, query_zmin, query_xmax, query_ymax, query_zmax)

Returns an iterator over intersecting items. Safe for nested queries.

• Returns: function, table - Iterator

tree:queryNotNested(query_xmin, query_ymin, query_zmin, query_xmax, query_ymax, query_zmax)

Faster query reusing internal state; not safe for nesting.

• Returns: function, table - Iterator

tree:export() / tree:import(kdTreeData)

Serialization/deserialization of tree data.

tree:analytics()

Prints tree statistics.

Internal Notes

• Items stored as flat array: 7 values per item (xmin, ymin, zmin, xmax, ymax, zmax, id)
• Same LEF Select algorithm and flat-array tree structure as kdtreebox2d, extended to 6 dimensions
• Tree cycles through 3 split axes (x, y, z) alternating at each level

Additional Exports

---

See Also

• cdefDebugDraw Reference - Related reference
• cdefGpuMesh Reference - Related reference
• cdefImgui Reference - Related reference
• Common Libraries Overview - Guide