Self-collision Detection for Rigid Non-convex Multi-link Model

摘要

This paper presents an efficient algorithm to perform continuous self-collision detection for rigid non-convex multi-link model. Our algorithm precomputes the oriented bounding box (OBB) and the bounding volume hierarchy (BVH) of convex hulls for each link based on the surface convex decomposition and constructs the dynamic bounding volume hierarchies with axis-aligned bounding boxes (AABBs). Given two discrete configurations of the links, we use motion interpolation between two successive time steps and check the resulting trajectory for collisions. We employ the conservative advancement and temporal culling to calculate the potentially colliding links, and adopt spatial culling to reduce the conservative advancement iterations. If collision occurs, the algorithm reports the first time of contact as well as colliding features (vertex/ face or edge/edge contacts). We implement the algorithm on the avatar model consisting of many links and tens of thousands, the results demonstrate the algorithm is efficient to perform continuous self-collision detection between the rigid non-convex multi-link model.