|
L. Guibas, A. Nguyen, D. Russel, and L. Zhang, Collision detection for deforming necklaces, Proceedings of 18th ACM Symposium on Computational Geometry, 2002
Abstract:
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(n\log n)$
in two dimensions and $O(n^{2-2/d})$ in $d$-dimensions, $d\geq 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.
Bibtex:
@inproceedings{gnrz-cddn-02,
author = {Leonidas Guibas and An Nguyen and Daniel Russel and Li Zhang},
title = {Collision detection for deforming necklaces},
booktitle = {SCG '02: Proceedings of the eighteenth annual symposium on Computational geometry},
year = {2002},
isbn = {1-58113-504-1},
pages = {33--42},
location = {Barcelona, Spain},
doi = {http://doi.acm.org/10.1145/513400.513405},
publisher = {ACM Press},
address = {New York, NY, USA},
}
|
 |