Bounding volume hierarchies for level-of-detail collision handling

Abstract

Enforcing solidity of objects within simulations is a major computational overhead. Detecting interactions between bodies is a large part of this overhead. Many researchers have used hybrid collision detection algorithms to address this issue. Such algorithms use multiple phases, first to eliminate object pairs that cannot be interacting and then to narrow in on the regions of the objects that are in contact. The second phase of these algorithms, the narrow phase, typically uses a hierarchical representation of the objects. A tree traversal algorithm narrows in on the regions of contact. While many different geometric primitives have been used for these hierarchies, spheres have some distinct advantages, especially for interruptible collision detection systems. However, large numbers of spheres are often required to approximate the objects' geometries. Octrees and medial axis techniques have been utilised for the construction of hierarchies of spheres, known as sphere-trees. This thesis presents a number of improvements to both these techniques. Existing methods have been critically analysed to determine their strengths and weaknesses and new algorithms, which build upon them, have been developed. As the sphere-trees are intended for use in an interruptible collision detection system, which uses the spheres to approximate the collisions as accurately as it can within an allowable time-slice, the main focus is on the close approximation of the object and fast traversal of the hierarchies. The main contributions of this thesis include the development of an adaptive medial axis approximation algorithm that allows areas of the medial axis to be constructed as required. This allows a finer approximation of the medial axis in detailed areas and allows more detail to be added to the approximation when there is insufficient information to closely approximate the object. A sphere-tree optimisation algorithm, which further improves the tightness of the representation, is also presented. An optimiser based algorithm, which constructs sphere-trees similar to those generated from the medial axis without requiring its approximation, is detailed. Finally sphere-trees generated with the various algorithms are compared in an interruptible collision detection system.