Full Text:   <2080>

CLC number: TP39

On-line Access: 

Received: 2006-04-11

Revision Accepted: 2006-04-24

Crosschecked: 0000-00-00

Cited: 0

Clicked: 4567

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.7 P.1225-1232


Using LBG quantization for particle-based collision detection algorithm


Affiliation(s):  Department of Computer Engineering, Faculty of Engineering, Chulalongkorn University, Thailand

Corresponding email(s):   g47nsn@cp.eng.chula.ac.th, pizzanu@cp.eng.chula.ac.th

Key Words:  Collision detection, Deformable object, Particle, LBG, Vector quantization

SAENGHAENGTHAM Nida, KANONGCHAIYOS Pizzanu. Using LBG quantization for particle-based collision detection algorithm[J]. Journal of Zhejiang University Science A, 2006, 7(7): 1225-1232.

@article{title="Using LBG quantization for particle-based collision detection algorithm",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Using LBG quantization for particle-based collision detection algorithm
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 7
%P 1225-1232
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A1225

T1 - Using LBG quantization for particle-based collision detection algorithm
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 7
SP - 1225
EP - 1232
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A1225

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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2023 Journal of Zhejiang University-SCIENCE