Multi-core collision detection between deformable models

ABSTRACT

We present a new parallel algorithm for interactive and continuous collision detection between deformable models. Our algorithm performs incremental hierarchical computations between successive frames and parallelizes the computation among multiple cores on current CPUs. The main computations include front building and updating and performing the elementary tests between the triangle primitives. The overall algorithm can perform inter- and intra-object collisions at interactive rates on current commodity processors on models with many tens of thousands of triangles. In practice, the performance of our algorithm almost scales linearly with the number of cores.

REFERENCES

• 1: U. Assarsson and P. Stenström. A case study of load distribution in parallel view frustum culling and collision detection. In Lecture Notes in Computer Science, page 663, 2001.
• 2: Y.-K. Chen, J. Chhugani, C. J. Hughes, D. Kim, S. Kumar, V. W. Lee, A. Lin, A. D. Nguyen, E. Sifakis, and M. Smelyanskiy. High-performance physical simulations on next-generation architecture with many cores. Intel Technology Journal, 11(3), 2007.
• 3: S. Curtis, R. Tamstorf, and D. Manocha. Fast collision detection for deformable models using representative-triangles. In SI3D '08: Proceedings of the 2008 Symposium on Interactive 3D graphics and games, pages 61--69, 2008.
• 4: S. A. Ehmann and M. C. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. In of Eurographics '2001, pages 500--510, 2001.
• 5: S. Gottschalk, M. C. Lin, and D. Manocha. Obbtree: a hierarchical structure for rapid interference detection. In SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 171--180, New York, NY, USA, 1996. ACM.
• 6: I. Grinberg and Y. Wiseman. Scalable parallel collision detection simulation. Proc. of Signal and Image Processing, 2007.
• 7: D. Kim, J. Heo, and S. Yoon. PCCD: Parallel continuous collision detection. Technical report, http://sglab.kaist.ac.kr/PCCD/, Korea Advanced Institute of Science and Technology, South Korea, 2008.
• 8: Y. Kitamura, A. Smith, H. Takemura, and F. Kishino. Parallel algorithms for real-time colliding face detection. Robot and Human Communication, 1995. RO-MAN'95 TOKYO, Proceedings., 4th IEEE International Workshop on, pages 211--218, Jul 1995.
• 9: J. Klein and G. Zachmann. The expected running time of hierarchical collision detection. In SIGGRAPH '05: ACM SIGGRAPH 2005 Posters, page 117, New York, NY, USA, 2005. ACM.
• 10: J. Klosowski, M. Held, J. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. on Visualization and Computer Graphics, 4(1):21--37, 1998.
• 11: V. Kumar and A. Y. Grama. Scalable load balancing techniques for parallel computers. Journal of Parallel and Distributed Computing, 22:60--79, 1994.
• 12: T.-Y. Li and J.-S. Chen. Incremental 3d collision detection with hierarchical data structures. In VRST '98: Proceedings of the ACM symposium on Virtual reality software and technology, pages 139--144, New York, NY, USA, 1998. ACM.
• 13: M. Lin and J. Canny. A fast algorithm for incremental distance calculation. Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on, 2:1008--1014, 1991.
• 14: I. J. Palmer and R. L. Grimsdale. Collision detection for animation using sphere-trees. Computer Graphics Forum, 14(2):105--116, 1995.
• 15: M. Ponamgi, D. Manocha, and M. C. Lin. Incremental algorithms for collision detection between solid models. In SMA '95: Proceedings of the third ACM symposium on Solid modeling and applications, pages 293--304, New York, NY, USA, 1995. ACM.
• 16: M. K. Ponamgi, D. Manocha, and M. C. Lin. Incremental algorithms for collision detection between polygonal models. IEEE Transactions on Visualization and Computer Graphics, 3(1):51--64, 1997.
• 17: V. N. Rao and V. Kumar. Parallel depth-first search, part i: Implementation. International Journal of Parallel Programming, 16:6--479, 1987.
• 18: A. Reinefeld and V. Schnecke. Work-load balancing in highly parallel depth-first search. In In Scalable High Performance Computing Conference, pages 773--780, 1994.
• 19: A. Selle, J. Su, G. Irving, and R. Fedkiw. Robust high-resolution cloth using parallelism, history-based collisions, and accurate friction. IEEE Transactions on Visualization and Computer Graphics, 99(2), 2008.
• 20: M. Tang, S. Curtis, S.-E. Yoon, and D. Manocha. Interactive continuous collision detection between deformable models using connectivity-based culling. In SPM '08: Proceedings of the 2008 ACM symposium on Solid and physical modeling, pages 25--36, New York, NY, USA, 2008. ACM.
• 21: M. Tang, D. Manocha, and R. Tong. MCCD: Multi-core collision detection between deformable models using front-based decomposition. Technical report, Department of Computer Science, University of North Carolina at Chapel Hill, 2009.
• 22: M. Tang, S. Yoon, and D. Manocha. Adjacency-based culling for continuous collision detection. The Visual Computer, Proc. of CGI08 (Computer Graphics International 2008), 24(7--9):545--553, 2008.
• 23: M. Teschner, S. Kimmerle, G. Zachmann, B. Heidelberger, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnetat-Thalmann, and W. Strasser. Collision detection for deformable objects. In Eurographics State-of-the-Art Report (EG-STAR), pages 119--139. Eurographics Association, Eurographics Association, 2004.
• 24: B. Thomaszewski and W. Blochinger. Physically based simulation of cloth on distributed memory architectures. Parallel Comput., 33(6):377--390, 2007.
• 25: B. Thomaszewski, S. Pabst, and W. Blochinger. Special section: Parallel graphics and visualization: Parallel techniques for physically based simulation on multi-core processor architectures. Comput. Graph., 32(1):25--40, 2008.
• 26: O. Tropp, A. Tal, I. Shimshoni, and D. P. Dobkin. Temporal coherence in bounding volume hierarchies for collision detection. International Journal of Shape Modeling, 12(2):159--178, 2006.
• 27: G. van den Bergen. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools, 2(4):1--14, 1997.
• 28: R. Weller and G. Zachmann. Kinetic separation lists for continuous collision detection of deformable objects. In Third Workshop in Virtual Reality Interactions and Physical Simulation (Vriphys), Madrid, Spain, 6--7 November 2006.

INDEX TERMS

Keywords:
continuous collision detection, deformable models, multicore processor, parallel collision detection