“Radial view based culling for continuous self-collision detection of skeletal models” by Wong, Lin, Hung, Huang and 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
