kd-Tree

Computer Graphics · Geometry and Intersection · kd-tree.yaml

Recursively splits space rather than objects with axis-aligned planes. Nodes never overlap, which makes traversal tight, but primitives straddling a plane must be referenced twice.

• supersedescorrects · extends
• classifiesspecializes · part-of
• substitutes forapproximates · alternative-to
• depends onrequires · validates

Colour is the family; a dashed line is the second member of it.

This node

• alternative-tois a competing approach to Bounding Volume Hierarchysplits space, not objects, so nodes never overlap

References

• Background — K-d tree on Wikipedia