Similar articles

Abstract: Most collision detection algorithms can be efficiently used only with solid and rigid objects, for instance, Hierarchical methods which must have their bounding representation recalculated every time deformation occurs. An alternative algorithm using particle-based method is then proposed which can detect the collision among non-rigid deformable polygonal models. However, the original particle-based collision detection algorithm might not be sufficient enough in some situations due to the improper particle dispersion. Therefore, this research presents an improved algorithm which provides a particle to detect in each separated area so that particles always covered all over the object. The surface partitioning can be efficiently performed by using LBG quantization since it can classify object vertices into several groups base on a number of factors as required. A particle is then assigned to move between vertices in a group by the attractive forces received from other particles on neighbouring objects. Collision is detected when the distance between a pair of corresponding particles becomes very small. Lastly, the proposed algorithm has been implemented to show that collision detection can be conducted in real-time.

[1] Abut, H., Gray, R.M., Rebolledo, G., 1992. Vector Quantization of Speech and Speech-like Waveforms. IEEE Transactions on Acoustics Speech and Signal Processing, ASSP-30, p.423-435.

[2] Bridson, R., Marino, S., Fedxew, R., 2003. Simulation of Clothing with Folds and Wrinkles. Proceedings of ACM/Eurographics Symposium on Computer Animation, p.28-36.

[3] Conway, J.H., Slone, N.J.A., 1993a. Bounds on Kissing Numbers. In: Sphere Packings, Lattices, and Groups, 2nd Ed., Springer-Verlag, New York.

[4] Conway, J.H., Slone, N.J.A., 1993b. The Kissing Number Problem. In: Sphere Packings, Lattices, and Groups, 2nd Ed., Springer-Verlag, New York.

[5] Cohen, J.D., Lin, M.C., Manocha, D., Ponamgi, M., 1995. I-COLLIDE: An Interactive and Exaxt Collision Detection System for Large-scale Environments. Proceedings of the Symposium on Interactive 3D Graphics, p.189-196.

[6] Gersho, A., Gray, R.M., 1992. Vector Quantization and Signal Compression. Kluwer International Series in Engineering and Computer Science, 159. Kluwer Academic Publishers.

[7] Gottschalk, S., Lin, M.C., Manocha, D., 1996. OOB Tree: A Hierachical Structure for Rapid Interference Detection. ACM Computer Graphics (Proc. SIGGRAPH’96), p.171-180.

[8] He, T.S., 1999. Fast Collision Detection Using QuOSPO Trees. Proceedings of the Symposium on Interactive 3D Graphics, p.55-62.

[9] Held, M., Klosowski, J.T., Mitchell, J.S.B., 1995. Evaluation of Collision Detection Methods for Virtual Reality Fly-troughs. Proceedings Seventh Canadian Conference on Computational Geormetry, p.205-210.

[10] Hubbard, P., 1996. Approximating polyhedra with spheres for time-critical collision detection. ACM Transactions on Graphics (TOG), 15(3):179-210.

[11] Klosowski, J.T., Held, M., Mitchell, J.S., Sowrizal, H., Zikan, K., 1998. Efficient collision detection using bounding volume hierarchies K-DOPs. IEEE Transactions on Visualization and Computer Graphics, p.21-36.

[12] Krishnan, S., Pattekar, A., Lin, M., Manocha, D., 1998. Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries. Proceedings of WAFR’98, p.287-296.

[13] Linde, Y., Buzo, A., Gray, R.M., 1980. An algorithm for vector quantizer design. IEEE Transaction on Communications, 28(1):84-95.

[14] Palmer, I., Grimsdale, R., 1995. Collision detection for animation using sphere-trees. Computer Graphics Forum, 14(2):105-116.

[15] Parent, R., 2001. Computer Animation: Algorithms and Techniques.

[16] Quinlan, S., 1994. Efficient Distance Computation between Non-convex Objects. Proceedings of IEEE International Conference on Robotics and Automation, p.3324-3329.

[17] Raghupathi, L., Cantin, V., Faure, F., Cani, M.P., 2003. Vision, Modeling and Visualization (VMV) Real-time Simulation of Self Collisions for Virtual Intestinal Surgery. Surg. Sim. & Soft Tis. Model, p.15-26.

[18] Senin, M., Kojekine, N., Savchenko, V., Hagiwara, I., 2003. Particle-based Collision Detection. EUROGRAHICS.

[19] Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.P., Faure, F., Magnenat-Thaimann, N., Strasser, W., Volino, P., 2004. Collision Detection for Deformable Objects. EUROGRAPHICS.

[20] Zachmann, G., 1998. Rapid Collision Detection by Dynamically Aligned DOP-trees. Proceedings of IEEE Virtual Reallity Annual International Symposium, p.90-97.