Spatial hashing based contact detection for numerical manifold method

Abstract

A spatial hashing method was introduced to accelerate the contact detection process in the numerical manifold method. All objects (blocks) in the work space are hashed to a one dimensional hash table based on a spatial grid, then only blocks within the same place in the hash table need to do contact detection. The proposed method has a time complexity of O(n). Experiments show that the spatial hashing contact detection has a significant improvement in performance.

Keywords:

• contact detection
• spatial hashing
• numerical manifold method
• speedup

Acknowledgements

The authors would thank Dr. Gen-hua Shi, who is the inventor of Numerical Manifold Method, for his instructions and kindly help. This work was supported by projects of National Natural Science Fund of China (61004090, 60902098, 11102222) and China National Science and Technology Major Project (2011ZX05056).