kDOP

A k-DOP, or k-directional oriented polytope, is a convex bounding volume used in computer graphics and collision detection to efficiently prune potential intersections. It is defined as the intersection of half-spaces bounded by planes whose normals come from a fixed set of directions. For each chosen direction, the object’s points have a minimum and a maximum projection; these extremal values determine the two bounding planes along that direction. If there are m directions, the k-DOP has k = 2m faces.

Construction and directions: A set D = {d1, …, dm} of m unit direction vectors is fixed for all objects in a scene. For every di in D, compute the minimum and maximum values of di·x over all points x of the object. The k-DOP is the region of space satisfying min_i ≤ di·x ≤ max_i for all i = 1..m. The planes are perpendicular to the chosen directions, yielding a convex polytope with k faces; common practice refers to the volume by the number of faces (for example, a 6-DOP has 6 faces and uses 3 directions, a 14-DOP uses 7 directions, etc.).

Use in collision detection: In broad-phase culling, two k-DOPs are tested by comparing their projections onto each direction in D. If there exists a direction di for which the projection intervals of the two volumes do not overlap, the volumes (and thus their objects) do not intersect. If all directions show overlapping intervals, the volumes may intersect, and a more precise test may be required. This approach provides a conservative test: it never misses a potential collision but can produce false positives that require closer checking.

Trade-offs and relationship to other volumes: k-DOPs offer tighter bounds than axis-aligned bounding boxes for many shapes while remaining faster to update than full convex hulls. The number of directions (and thus the number of planes) controls tightness, memory usage, and update cost. A 6-DOP is equivalent to an axis-aligned box for its chosen directions, while higher-order DOPs yield progressively tighter fits.