Collision detection for deforming necklaces
Collision detection for deforming necklaces
复制标题
变形项链的碰撞检测
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Li Zhang
中科院分区：
文献类型：
--
作者：
Pankaj Agarwal;L. Guibas;A. Nguyen;Daniel Russel;Li Zhang
在本文中，我们建议研究可变形项链——柔性球链，称为珠子，其中只有相邻的球可以相交。这些对象可用于模拟物理世界中的大分子、肌肉、绳索和其他“线性”对象。在本文中，我们利用这种线性来开发与项链相关的几何结构，这在物理模拟中很有用。我们展示了如何有效地实现这些结构并在项链变形的情况下保持这些结构。特别是，我们研究了基于项链上构建的球体的包围体层次结构。正如我们的理论和实验结果所示，这种层次结构易于计算，并且适合项链变形时的维护。该层次结构可用于碰撞和自碰撞检测。特别是，我们在二维中实现了 O(nlog n) 的上限，在 d 维度 d 3 中实现了 O(n 2-2/d) 的上限，用于碰撞检查。据我们所知，这是使用预定义层次结构证明碰撞检测算法的第一个次二次界。此外，我们还表明，在一些附加机制的帮助下，功率图也可以用于以与球体层次结构互补的某些方式检测项链的自碰撞。
In this paper, we propose to study deformable necklaces --- flexible chains of balls, called beads, in which only adjacent balls may intersect. Such objects can be used to model macro-molecules, muscles, rope, and other 'linear' objects in the physical world. In this paper, we exploit this linearity to develop geometric structures associated with necklaces that are useful in physical simulations. We show how these structures can be implemented efficiently and maintained under necklace deformation. In particular, we study a bounding volume hierarchy based on spheres built on a necklace. Such a hierarchy is easy to compute and is suitable for maintenance when the necklace deforms, as our theoretical and experimental results show. This hierarchy can be used for collision and self-collision detection. In particular, we achieve an upper bound of O(nlog n) in two dimensions and O(n 2-2/d) in d-dimensions, d 3, for collision checking. To our knowledge, this is the first sub-quadratic bound proved for a collision detection algorithm using predefined hierarchies. In addition, we show that the power diagram, with the help of some additional mechanisms, can be also used to detect self-collisions of a necklace in certain ways complementary to the sphere hierarchy.