Rapid and accurate contact determination between spline models using ShellTrees

In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree, th at comprises of spherical shells and oriented bounding boxes. Each spherica l shell corresponds to a portion of the volume between two concentric spher es. Given large spline models, our algorithm decomposes each surface into B ezier patches as part of preprocessing. At runtime it dynamically computes a tight fitting axis-aligned bounding boa across each Bezier patch and effi ciently checks all such boxes for overlap. Using off-line and on-line techn iques for tree construction, our algorithm computes ShellTrees for Bezier p atches and performs fast overlap tests between them to detect collisions. T he overall approach can trade off runtime performance for reduced memory re quirements. We have implemented the algorithm and tested it on large models , each composed of hundred of patches. As performance varies with the confi gurations of the objects. For many complex models composed of hundreds of p atches, it can accurately compute the contacts in a few milliseconds.