“Fast proximity computation among deformable models using discrete Voronoi diagrams” by Sud, Govindaraju, Gayle, Kabul and Manocha

We present novel algorithms to perform collision and distance queries among multiple deformable models in dynamic environments. These include inter-object queries between different objects as well as intra-object queries. We describe a unified approach to compute these queries based on N-body distance computation and use properties of the 2nd order discrete Voronoi diagram to perform N-body culling. Our algorithms involve no preprocessing and also work well on models with changing topologies. We can perform all proximity queries among complex deformable models consisting of thousands of triangles in a fraction of a second on a high-end PC. Moreover, our Voronoi-based culling algorithm can improve the performance of separation distance and penetration queries by an order of magnitude.

1. Agarwal, P., Guibas, L., Nguyen, A., Russel, D., and Zhang, L. 2004. Collision detection for deforming necklaces. Computational Geometry: Theory and Applications 28, 2-3, 137–163. Google ScholarDigital Library
2. Baraff, D., and Witkin, A. 2001. Physically Based Modeling. ACM SIGGRAPH Course Notes.Google Scholar
3. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. Proc. of ACM SIGGRAPH, 862–870. Google ScholarDigital Library
4. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treament for collisions, contact and friction for cloth animation. Proc. of ACM SIGGRAPH, 594–603. Google ScholarDigital Library
5. Cohen, J., Lin, M., Manocha, D., and Ponamgi, M. 1995. I-COLLIDE: An interactive and exact collision detection system for large-scale environments. In Proc. of ACM Interactive 3D Graphics Conference, 189–196. Google ScholarDigital Library
6. Dobkin, D., Hershberger, J., Kirkpatrick, D., and Suri, S. 1993. Computing the intersection-depth of polyhedra. Algorithmica 9, 518–533.Google ScholarCross Ref
7. Ehmann, S., and Lin, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics’2001) 20, 3, 500–510.Google Scholar
8. Ericson, C. 2004. Real-Time Collision Detection. Morgan Kaufmann. Google ScholarDigital Library
9. Fischer, I., and Gotsman, C. 2005. Fast approximation of high order Voronoi diagrams and distance transforms on the GPU. Technical report CS TR-07-05, Harvard University.Google Scholar
10. Fisher, S., and Lin, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. Proc. of EG Workshop on Computer Animation and Simulation, 99–111. Google ScholarDigital Library
11. Govindaraju, N., Redon, S., Lin, M., and Manocha, D. 2003. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Proc. of ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware, 25–32. Google ScholarDigital Library
12. Govindaraju, N., Knott, D., Jain, N., Kabal, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Collision detection between deformable models using chromatic decomposition. ACM Trans. on Graphics (Proc. of ACM SIGGRAPH) 24, 3, 991–999. Google ScholarDigital Library
13. Heidelberger, B., Teschner, M., Keisner, R., Mueller, M., and Gross, M. 2004. Consistent penetration depth estimation for deformable collision response. Proc. of Vision, Modeling and Visualization, 315–322.Google Scholar
14. Hoff, K., Zaferakis, A., Lin, M., and Manocha, D. 2002. Fast 3d geometric proximity queries between rigid and deformable models using graphics hardware acceleration. Tech. Rep. TR02-004, Department of Computer Science, University of North Carolina.Google Scholar
15. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. Proc. of ACM SIGGRAPH, 393–398. Google ScholarDigital Library
16. Johnson, D. E., and Cohen, E. 2004. Unified distance queries in a heterogeneous model environment. In ASME DETC.Google Scholar
17. Kawachi, K., and Suzuki, H. 2000. Distance computation between non-convex polyhedra at short range based on discrete Voronoi diagrams. IEEE Geometric Modeling and Processing, 123–128. Google ScholarDigital Library
18. Kim, Y. J., Otaduy, M. A., Lin, M. C., and Manocha, D. 2002. Fast penetration depth computation for physically-based animation. In Proc. of ACM/Eurographics Symposium on Computer Animation, 23–31. Google ScholarDigital Library
19. Knott, D., and Pai, D. K. 2003. CInDeR: Collision and interference detection in real-time using graphics hardware. Proc. of Graphics Interface, 73–80.Google Scholar
20. Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Distance queries with rectangular swept sphere volumes. Proc. of IEEE Int. Conference on Robotics and Automation, 3719–3726.Google Scholar
21. Larsson, T., and Akenine-Möller, T. 2001. Collision detection for continuously deforming bodies. In Eurographics, 325–333.Google Scholar
22. Lin, M., and Canny, J. F. 1991. Efficient algorithms for incremental distance computation. In IEEE Conference on Robotics and Automation, 1008–1014.Google Scholar
23. Lin, M. C., and Manocha, D. 2004. Collision and proximity queries. In Handbook of Discrete and Computational Geometry, 2nd Ed., J. E. Goodman and J. O’Rourke, Eds. CRC Press LLC, Boca Raton, FL, ch. 35, 787–807.Google Scholar
24. Mirtich, B. 1998. V-Clip: Fast and robust polyhedral collision detection. ACM Transactions on Graphics 17, 3 (July), 177–208. Google ScholarDigital Library
25. Mueller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformation based on shape matching. Proc. of ACM SIGGRAPH, 471–478. Google ScholarDigital Library
26. Okabe, A., Boots, B., and Sugihara, K. 1992. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, Chichester, UK. Google ScholarDigital Library
27. Quinlan, S. 1994. Efficient distance computation between non-convex objects. In Proceedings of International Conference on Robotics and Automation, 3324–3329.Google ScholarCross Ref
28. Redon, S., and Lin, M. 2006. A fast method for local penetration depth computation. Journal of Graphics Tools, To Appear.Google ScholarCross Ref
29. Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. 2004. Fast continuous collision detection for articulated models. In Proceedings of ACM Symposium on Solid Modeling and Applications. Google ScholarDigital Library
30. Sigg, C., Peikert, R., and Gross, M. 2003. Signed distance transform using graphics hardware. In Proceedings of IEEE Visualization, 83–90. Google ScholarDigital Library
31. Sud, A., Otaduy, M. A., and Manocha, D. 2004. DiFi: Fast 3D distance field computation using graphics hardware. Computer Graphics Forum (Proc. Eurographics) 23, 3, 557–566.Google ScholarCross Ref
32. Sud, A., Govindaraju, N., Gayle, R., and Manocha, D. 2006. Interactive 3d distance field computation using linear factorization. In Proc. ACM Symposium on Interactive 3D Graphics and Games, 117–124. Google ScholarDigital Library
33. Sud, A., Govindaraju, N., Gayle, R., and Manocha, D. 2006. Surface distance maps. Tech. Rep. TR06-011, Dept of Computer Science, University of North Carolina.Google Scholar
34. Sundaraj, K., and Laugier, C. 2000. Fast contact localization of moving deformable polyhedra. In Proc. of IEEE Int. Conference on Control, Automation, Robotics and Vision.Google Scholar
35. Teschner, M., Heidelberger, B., Muller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. Proc. of Vision, Modeling and Visualization, 47–54.Google Scholar
36. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics Forum 19, 1, 61–81.Google ScholarCross Ref
37. van den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4, 1–14. Google ScholarDigital Library
38. Volino, P., and Thalmann, N. M. 2000. Accurate collision response on polygon meshes. In Proc. of Computer Animation, 154. Google ScholarDigital Library