Premium
Rapid and Accurate Contact Determination between Spline Models using ShellTrees
Author(s) -
Krishnan S.,
Gopi M.,
Lin M.,
Manocha D.,
Pattekar A.
Publication year - 1998
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.00278
Subject(s) - bounding volume , computer science , bounding overwatch , algorithm , minimum bounding box , collision detection , bézier curve , spline (mechanical) , line (geometry) , computer graphics (images) , geometry , mathematics , artificial intelligence , collision , computer security , structural engineering , engineering , image (mathematics)
In this paper, we present an efficient algorithm for contact determination between spline models. We make use of a new hierarchy, called ShellTree , that comprises of spherical shells and oriented bounding boxes. Each spherical shell corresponds to a portion of the volume between two concentric spheres. Given large spline models, our algorithm decomposes each surface into Bézier patches as part of pre‐processing. At runtime it dynamically computes a tight fitting axis‐aligned bounding box across each Bézier patch and efficiently checks all such boxes for overlap. Using off‐line and on‐line techniques for tree construction, our algorithm computes ShellTrees for Bézier patches and performs fast overlap tests between them to detect collisions. The overall approach can trade off runtime performance for reduced memory requirements. We have implemented the algorithm and tested it on large models, each composed of hundred of patches. Its performance varies with the configurations of the objects. For many complex models composed of hundreds of patches, it can accurately compute the contacts in a few milliseconds.