Research on Collision Detection for Rigid Object in Deformable Environment
Ying Wei · Chinese Journal of Computers · 2001
Collision Detection for rigid object in deformable environment is very popular in the field of virtual reality such as surgery simulation and so on, but few research has been made. This paper proposes a collision detection method based on fixed direction hull bounding volume tree which provides an effective way for such problem. Fixed direction hulls is a special convex hull whose outward normal of facets comes from a fixed direction set. It overcomes limitations of other bounding volumes and makes a promise between tightness and simpleness. It can be determined that two fixed direction hull bounding volumes do not overlap by checking if one of their bound intervals on direction axis defined by the fixed direction set does not overlap. Thus the intersection test between two bounding volumes need only at most n comparisons ( n is the size of fixed direction set).Updating bounding volumes after rotation is an important problem of hierarchical bounding volume approach. An updating algorithm based on linear programming is proposed in this paper based on the definition and property of fixed direction hulls. This method need not add any additional computation and memory during building bounding volume hierarchies. It can update a bounding volume through 3 n multiplications. Deformation of object is a difficulty in collision detection. This paper analyses two kinds of deformations and proposes resolving method respectively. A bottom up updating method is proposed especially which can compute the bounding volume of parent node through bounding volumes of the two children only by n comparisons.It is proved through experiment that our method can not only solve collision detection between rigid objects efficiently but also solve collision detection between rigid objects and deformable objects.