kDOPs

A kDOP is a convex bounding volume used in computer graphics and computational geometry. It generalizes bounding boxes by restricting face normals to a fixed set of directions. The polytope is defined as the intersection of half-spaces whose normals are from this fixed set. Each direction yields a pair of parallel planes that bound the object along that direction.

Construction: Given a set D = {d1,...,dk} of unit vectors, for each direction dj compute projections of all vertices v: p = dot(dj, v). Let p_min_j and p_max_j be the minimum and maximum projections. The KDOP is the intersection over j of the slabs p_min_j ≤ dot(dj, x) ≤ p_max_j.

Properties and use: KDOPs are convex; their complexity scales with k. More directions yield tighter fitting volumes but cost more to test. They are used as broad-phase bounding volumes in collision detection. Intersection tests reduce to interval overlap checks on each direction; if a pair’s projections do not overlap on any direction, the objects do not collide; if they overlap on all directions, collision is possible but not guaranteed, requiring a more precise check.

Dynamics and updates: KDOPs can be updated efficiently for rigid motion by recomputing the affected projections or transforming the vertex set. For deformable objects, recomputation of min/max per direction may be necessary. Variants exist that optimize for dynamic scenes or specific hardware.

Variants and choices: The set of directions is fixed at construction. In 3D, common choices include 13-DOP or 26-DOP, yielding 26 or more bounding planes. KDOPs are widely used in physics engines, robotics, and computer-aided design as a flexible, tunable alternative to axis-aligned or oriented bounding volumes.