121Accesses
Abstract
We present an efficient approach to reduce the number of elementary tests for continuous collision detection between rigid and deformable models. Our algorithm exploits connectivity information and uses the adjacency relationships between triangles to perform hierarchical culling. This can be combined with table-based lookups to eliminate duplicate elementary tests. In practice, our approach can reduce the number of elementary tests by two orders of magnitude. We demonstrate the performance of our algorithm on various challenging rigid body and deformable simulations.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Baraff, D., Witkin, A., Kass, M.: Untangling cloth. In: Proc. of ACM SIGGRAPH, pp. 862–870. ACM Press, San Diego (2003)
Curtis, S., Tamstorf, R., Manocha, D.: Fast collision detection for deformable models using representative-triangles. In: SI3D ’08: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, pp. 61–69. ACM Press, Redwood City (2008)
Foskey, M., Garber, M., Lin, M., Manocha, D.: A voronoi-based hybrid planner. In: Proc. of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 67–72. IEEE Computer Society Press, Hawaii (2001)
Gottschalk, S., Lin, M., Manocha, D.: OBB-Tree: a hierarchical structure for rapid interference detection. In: Proc. of ACM Siggraph’96, pp. 171–180. ACM Press, New Orleans (1996)
Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., Manocha, D.: Collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. (Proc. of ACM SIGGRAPH)24(3), 991–999 (2005)
Hoff, K., Culver, T., Keyser, J., Lin, M., Manocha, D.: Interactive motion planning using hardware accelerated computation of generalized voronoi diagrams. In: Proceedings of IEEE Conference of Robotics and Automation, pp. 101–108. IEEE Computer Society Press, San Francisco (2000)
Hutter, M., Fuhrmann, A.: Optimized continuous collision detection for deformable triangle meshes. In: Proc. WSCG ’07, pp. 25–32. Science Press, Plzen (2007)
Klosowski, J., Held, M., Mitchell, J., Sowizral, H., Zikan, K.: Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. Vis. Comput. Graph.4(1), 21–37 (1998)
Larsson, T., Akenine-Möller, T.: A dynamic bounding volume hierarchy for generalized collision detection. Comput. Graph.30(3), 451–460 (2006)
Lauterbach, C., Yoon, S., Tuft, D., Manocha, D.: RT-DEFORM: Interactive ray tracing of dynamic scenes using BVHs. In: IEEE Symposium on Interactive Ray Tracing, pp. 39–46. IEEE Computer Society Press, Salt Lake City (2006)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006). (also available at http://msl.cs.uiuc.edu/planning/)
Lin, M., Manocha, D.: Collision and proximity queries. In: Handbook of Discrete and Computational Geometry. CRC Press LLC, Boca Raton (2003)
Pisula, C., Hoff, K., Lin, M., Manocha, D.: Randomized path planning for a rigid body based on hardware accelerated voronoi sampling. In: Proc. of 4th International Workshop on Algorithmic Foundations of Robotics, pp. 279–292. A.K. Peters, Hannover (2000)
Provot, X.: Collision and self-collision handling in cloth model dedicated to design garment. In: Graphics Interface, pp. 177–189. Canadian Human-Computer Communications Society, Kelowna (1997)
Redon, S., Kheddar, A., Coquillart, S.: Fast continuous collision detection between rigid bodies. Comput. Graph. Forum (Proc. of Eurographics)21(3), 279–288 (2002)
Redon, S., Kim, Y.J., Lin, M.C., Manocha, D.: Fast continuous collision detection for articulated models. In: Proceedings of ACM Symposium on Solid Modeling and Applications, pp. 145–156. ACM Press, Genova (2004)
Sud, A., Otaduy, M.A., Manocha, D.: DiFi: Fast 3D distance field computation using graphics hardware. Comput. Graph. Forum (Proc. Eurographics)23(3), 557–566 (2004)
Tang, M., Curtis, S., Yoon, S., Manocha, D.: Interactive continuous collision detection between deformable models using connectivity-based culling. In: Proc. of SPM08 (ACM Solid and Physical Modeling Symposium). ACM Press, Stony Brook (2008)
Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.P., Faure, F., Magnenat-Thalmann, N., Strasser, W., Volino, P.: Collision detection for deformable objects. Comput. Graph. Forum19(1), 61–81 (2005)
Van den Bergen, G.: Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools2(4), 1–14 (1997)
Volino, P., Thalmann, N.M.: Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Comput. Graph. Forum (EuroGraphics Proc.)13(3), 155–166 (1994)
Wong, W.S.K., Baciu, G.: Dynamic interaction between deformable surfaces and nonsmooth objects. IEEE Trans. Vis. Comput. Graph.11(3), 329–340 (2005)
Wong, W.S.K., Baciu, G.: A randomized marking scheme for continuous collision detection in simulation of deformable surfaces. In: Proc. of ACM VRCIA, pp. 181–188. ACM Press, Hong Kong (2006)
Yoon, S., Curtis, S., Manocha, D.: Ray tracing dynamic scenes using selective restructuring. In: Proc. of Eurographics Symposium on Rendering, pp. 73–84. Eurographics Association, Grenoble (2007)
Zhang, L., Manocha, D.: Motion interpolation with distance constraints. Tech. Rep. TR 08-001, Department of Computer Science, UNC Chapel Hill (2008)
Zhang, X., Redon, S., Lee, M., Kim, Y.J.: Continuous collision detection for articulated models using taylor models and temporal culling. ACM Trans. Graph. (Proceedings of SIGGRAPH 2007)26(3), 15 (2007)
Author information
Authors and Affiliations
Zhejiang University, Hangzhou, 310027, P.R. China
Min Tang
Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea
Sung-Eui Yoon
University of North Carolina at Chapel Hill, Chapel Hill, USA
Min Tang & Dinesh Manocha
- Min Tang
You can also search for this author inPubMed Google Scholar
- Sung-Eui Yoon
You can also search for this author inPubMed Google Scholar
- Dinesh Manocha
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toMin Tang.
Rights and permissions
About this article
Cite this article
Tang, M., Yoon, SE. & Manocha, D. Adjacency-based culling for continuous collision detection.Visual Comput24, 545–553 (2008). https://doi.org/10.1007/s00371-008-0235-y
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative