“Radial view based culling for continuous self-collision detection of skeletal models” by Wong, Lin, Hung, Huang and Shing-Yeu

  • ©Sai-Keung Wong, Wen-Chieh Lin, Chun-Hung Hung, Yi-Jheng Huang, and Lii Shing-Yeu

Conference:


Type:


Title:

    Radial view based culling for continuous self-collision detection of skeletal models

Session/Category Title:   Sounds & Solids


Presenter(s)/Author(s):


Moderator(s):



Abstract:


    We present a novel radial-view-based culling method for continuous self-collision detection (CSCD) of skeletal models. Our method targets closed triangular meshes used to represent the surface of a model. It can be easily integrated with bounding volume hierarchies (BVHs) and used as the first stage for culling non-colliding triangle pairs. A mesh is decomposed into clusters with respect to a set of observer primitives (i.e., observer points and line segments) on the skeleton of the mesh so that each cluster is associated with an observer primitive. One BVH is then built for each cluster. At the runtime stage, a radial view test is performed from the observer primitive of each cluster to check its collision state. Every pair of clusters is also checked for collisions. We evaluated our method on various models and compared its performance with prior methods. Experimental results show that our method reduces the number of the bounding volume overlapping tests and the number of potentially colliding triangle pairs, thereby improving the overall process of CSCD.

References:


    1. Baran, I., and Popović, J. 2007. Automatic rigging and animation of 3D characters. ACM Transactions on Graphics 30, 7, 2087–2096. Google ScholarDigital Library
    2. Barbič, J., and James, D. L. 2010. Subspace self-collision culling. ACM Transactions on Graphics 29, 3, 81:1–81:9. Google ScholarDigital Library
    3. Bradshaw, G., and O’Sullivan, C. 2004. Adaptive medial-axis approximation for sphere tree construction. ACM Transactions on Graphics 23, 1, 1–26. Google ScholarDigital Library
    4. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics 21, 3, 594–603. Google ScholarDigital Library
    5. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. Interactive skeleton-driven dynamic deformations. ACM Transactions on Graphics 21, 3, 586–593. Google ScholarDigital Library
    6. Capell, S., Burkhart, M., Curless, B., Duchamp, T., and Popović, Z. 2005. Physically based rigging for deformable characters. In Symposium on Computer Animation, 301–310. Google ScholarDigital Library
    7. Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, 61–69. Google ScholarDigital Library
    8. Fisher, S., and Ming, C.-L. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. In Eurographics Workshop on Computer Animation and Simulation, 99–111. Google ScholarDigital Library
    9. Frisken, S. F., Perry, R. N., Rockwood, A. P., and Jones, T. R. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of ACM SIGGRAPH, 249–254. Google ScholarDigital Library
    10. Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Transactions on Graphics 24, 3, 991–999. Google ScholarDigital Library
    11. Heo, J.-P., Seong, J.-K., Kim, D.-S., Otaduy, M. A., Hong, J.-M., Tang, M., and Yoon, S.-E. 2010. FASTCD: Fracturing-aware stable collision detection. In Symposium on Computer Animation, 149–158. Google ScholarDigital Library
    12. Kavan, L., O’Sullivan, C., and Žára, J. 2006. Efficient collision detection for spherical blend skinning. In Proceedings of the 4th International Conference on Computer Graphics and Interactive Techniques in Australasia and Southeast Asia, 147–156. Google ScholarDigital Library
    13. Kim, D., Heo, J., Huh, J., Kim, J., and Yoon, S. 2009. HPCCD: Hybrid parallel continuous collision detection using CPUs and GPUs. Computer Graphics Forum 28, 7, 1791–1800.Google ScholarCross Ref
    14. Klosowski, J., Held, M., Mitchell, J., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics 4, 1, 21–36. Google ScholarDigital Library
    15. Knott, D., and Pai, K. 2003. Cinder: collision and interference detection in real-time using graphics hardware. In Graphics Interface, 73–80.Google Scholar
    16. Kopperman, R., Meyer, P., and Wilson, R. 1991. A Jordan Surface Theorem for three-dimensional digital spaces. Discrete & Computational Geometry 6, 2, 155–161.Google ScholarDigital Library
    17. Larsson, T., and Akenine-Möller, T. 2006. A dynamic bounding volume hierarchy for generalized collision detection. Computers & Graphics 30, 3, 450–459. Google ScholarDigital Library
    18. Mezger, J., Kimmerle, S., and Etzmuss, O. 2003. Hierarchical techniques in collision detection for cloth animation. Journal of WSCG 11, 2, 322–329.Google Scholar
    19. Redon, S., Kheddar, A., and Coquillart, S. 2002. Fast continuous collision detection between rigid bodies. In Computer graphics forum, vol. 21(3), 279–288.Google Scholar
    20. Schvartzman, S., Gason, J., and Otaduy, M. 2009. Bounded normal trees for reduced deformations of triangulated surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 75–82. Google ScholarDigital Library
    21. Schvartzman, S., Pérez, A. G., and Otaduy, M. A. 2010. Star-contours for efficient hierarchical self-collision detection. ACM Transactions on Graphics 29, 3. Google ScholarDigital Library
    22. Sundar, H., Silver, D., Gagvani, N., and Dickinson, S. 2003. Skeleton based shape matching and retrieval. In Proceedings of the Shape Modeling International, 130–142. Google ScholarDigital Library
    23. Tang, M., Curtis, S., Yoon, S., and Manocha, D. 2009. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Transactions on Visualization and Computer Graphics 15, 4, 544–557. Google ScholarDigital Library
    24. Tang, M., Manocha, D., and Tong, R. 2009. Multi-core collision detection between deformable models. In SIAM/ACM Joint Conference on Geometric and Physical Modeling, 355–360. Google ScholarDigital Library
    25. Tang, M., Manocha, D., and Tong, R. 2010. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 7–13. Google ScholarDigital Library
    26. Tang, C., Li, S., and Wang, G. 2011. Fast continuous collision detection using parallel filter in subspace. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 71–80. Google ScholarDigital Library
    27. Tang, M., Manocha, D., Lin, J., and Tong, R. 2011. Collision-streams: Fast GPU-based collision detection for deformable models. In ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 63–70. Google ScholarDigital Library
    28. Tang, M., Manocha, D., Yoon, S.-E., Du, P., Heo, J.-P., and Tong, R. 2011. VolCCD: Fast continuous collision culling between deforming volume meshes. ACM Transactions on Graphics 30, 5. Google ScholarDigital Library
    29. 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. In Computer Graphics Forum, 61–81.Google Scholar
    30. UNC Gamma Group. SelfCCD: Continuous collision detection for deforming objects. http://gamma.cs.unc.edu/SELFCD.Google Scholar
    31. Volino, P., and Magnenat-Thalmann, N. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. In Computer Graphics Forum, 155–166.Google Scholar
    32. Wong, S.-K., and Baciu, G. 2005. Dynamic interaction between deformable surfaces and non-smooth objects. IEEE Transactions on Visualization and Computer Graphics 11, 3, 329–340. Google ScholarDigital Library
    33. Wong, S.-K., and Baciu, G. 2006. A randomized marking scheme for continuous collision detection in simulation of deformable surfaces. In Proceedings of the ACM Int’l Conf. on Virtual Reality Continuum and Its Applications, 181–188. Google ScholarDigital Library
    34. Yu, W., and Li, X. 2011. Computing 3D shape guarding and star decomposition. Computer Graphics Forum 26, 3, 1–8.Google Scholar
    35. Zachmann, G., and Weller, R. 2006. Kinetic bounding volume hierarchies for deformable objects. In ACM Int’l Conf. on Virtual Reality Continuum and Its Applications, 14–17. Google ScholarDigital Library
    36. Zhang, X., and Kim, Y. 2012. Simple culling methods for continuous collision detection of deforming triangles. IEEE Transactions on Visualization and Computer Graphics 18, 7, 1146–1155. Google ScholarDigital Library
    37. Zheng, C., and Doug, J. L. 2012. Energy-based self-collision culling for arbitrary mesh deformations. ACM Transactions on Graphics 31, 4. Google ScholarDigital Library


ACM Digital Library Publication:



Overview Page: