Movatterモバイル変換


[0]ホーム

URL:


Skip to main content
Springer Nature Link
Log in

Adjacency-based culling for continuous collision detection

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

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

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

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

  1. Baraff, D., Witkin, A., Kass, M.: Untangling cloth. In: Proc. of ACM SIGGRAPH, pp. 862–870. ACM Press, San Diego (2003)

    Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. 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)

    Google Scholar 

  4. 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)

    Google Scholar 

  5. 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)

    Article  Google Scholar 

  6. 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)

    Google Scholar 

  7. Hutter, M., Fuhrmann, A.: Optimized continuous collision detection for deformable triangle meshes. In: Proc. WSCG ’07, pp. 25–32. Science Press, Plzen (2007)

    Google Scholar 

  8. 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)

    Article  Google Scholar 

  9. Larsson, T., Akenine-Möller, T.: A dynamic bounding volume hierarchy for generalized collision detection. Comput. Graph.30(3), 451–460 (2006)

    Article  Google Scholar 

  10. 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)

    Chapter  Google Scholar 

  11. LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006). (also available at http://msl.cs.uiuc.edu/planning/)

    MATH  Google Scholar 

  12. Lin, M., Manocha, D.: Collision and proximity queries. In: Handbook of Discrete and Computational Geometry. CRC Press LLC, Boca Raton (2003)

    Google Scholar 

  13. 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)

  14. 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)

    Google Scholar 

  15. Redon, S., Kheddar, A., Coquillart, S.: Fast continuous collision detection between rigid bodies. Comput. Graph. Forum (Proc. of Eurographics)21(3), 279–288 (2002)

    Article  Google Scholar 

  16. 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)

    Google Scholar 

  17. 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)

    Article  Google Scholar 

  18. 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)

    Google Scholar 

  19. 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)

    Article  Google Scholar 

  20. Van den Bergen, G.: Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools2(4), 1–14 (1997)

    MATH  Google Scholar 

  21. 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)

    Article  Google Scholar 

  22. Wong, W.S.K., Baciu, G.: Dynamic interaction between deformable surfaces and nonsmooth objects. IEEE Trans. Vis. Comput. Graph.11(3), 329–340 (2005)

    Article  Google Scholar 

  23. 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)

    Google Scholar 

  24. 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)

    Google Scholar 

  25. Zhang, L., Manocha, D.: Motion interpolation with distance constraints. Tech. Rep. TR 08-001, Department of Computer Science, UNC Chapel Hill (2008)

  26. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Zhejiang University, Hangzhou, 310027, P.R. China

    Min Tang

  2. Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea

    Sung-Eui Yoon

  3. University of North Carolina at Chapel Hill, Chapel Hill, USA

    Min Tang & Dinesh Manocha

Authors
  1. Min Tang

    You can also search for this author inPubMed Google Scholar

  2. Sung-Eui Yoon

    You can also search for this author inPubMed Google Scholar

  3. Dinesh Manocha

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toMin Tang.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement


[8]ページ先頭

©2009-2025 Movatter.jp