This paper presents a new method for efficient collision detection using bounding volume hierarchies (BV-trees) of discrete orientation polytopes (k-dops). The method is designed for objects moving within complex environments. A k-dop is a convex polytope whose facets are determined by halfspaces with normals from a fixed set of k orientations. The paper compares various methods for constructing BV-trees of k-dops and proposes algorithms for maintaining effective BV-trees for moving objects and performing fast collision detection using BV-trees of both moving objects and the environment. The authors implemented and tested their algorithms, showing that their approach yields significantly faster collision detection than previous methods. The paper discusses the design of BV-trees, the choice of k-dops, and the splitting rules for building hierarchies. It also addresses the issue of updating k-dops as objects rotate and the efficiency of collision detection algorithms. The paper highlights the trade-offs between different design choices, such as the degree of the tree, the choice of splitting axis, and the depth of the hierarchy. It also discusses the cost of updating k-dops and the efficiency of intersection tests between them. The authors propose two methods for updating k-dops: a hill-climbing algorithm and an approximation method. They find that the hill-climbing method is more accurate but more computationally expensive, while the approximation method is less accurate but faster. The paper also presents a tree traversal algorithm for collision detection, which recursively checks for overlaps between bounding volumes and performs triangle-triangle intersection tests when necessary. The algorithm is efficient and effective, with experimental results showing that it performs well on a variety of datasets. The paper concludes that the use of k-dops in BV-trees provides a promising approach for efficient collision detection in complex environments. The authors suggest that further research is needed to optimize the choice of k and the design of BV-trees for different applications.This paper presents a new method for efficient collision detection using bounding volume hierarchies (BV-trees) of discrete orientation polytopes (k-dops). The method is designed for objects moving within complex environments. A k-dop is a convex polytope whose facets are determined by halfspaces with normals from a fixed set of k orientations. The paper compares various methods for constructing BV-trees of k-dops and proposes algorithms for maintaining effective BV-trees for moving objects and performing fast collision detection using BV-trees of both moving objects and the environment. The authors implemented and tested their algorithms, showing that their approach yields significantly faster collision detection than previous methods. The paper discusses the design of BV-trees, the choice of k-dops, and the splitting rules for building hierarchies. It also addresses the issue of updating k-dops as objects rotate and the efficiency of collision detection algorithms. The paper highlights the trade-offs between different design choices, such as the degree of the tree, the choice of splitting axis, and the depth of the hierarchy. It also discusses the cost of updating k-dops and the efficiency of intersection tests between them. The authors propose two methods for updating k-dops: a hill-climbing algorithm and an approximation method. They find that the hill-climbing method is more accurate but more computationally expensive, while the approximation method is less accurate but faster. The paper also presents a tree traversal algorithm for collision detection, which recursively checks for overlaps between bounding volumes and performs triangle-triangle intersection tests when necessary. The algorithm is efficient and effective, with experimental results showing that it performs well on a variety of datasets. The paper concludes that the use of k-dops in BV-trees provides a promising approach for efficient collision detection in complex environments. The authors suggest that further research is needed to optimize the choice of k and the design of BV-trees for different applications.