×

A hierarchical detection framework for computational contact mechanics. (English) Zbl 1295.74097

Summary: A novel methodology consisting of three hierarchical levels is proposed for the detection phase of contact mechanics simulations. The top level of the hierarchy uses kinematic information from the objects involved in the simulation to determine approximate collision times. These instants then determine when the engine resumes operation for further detection. By using bounding volume hierarchies, the second level of detection precludes contact by computing simple exclusion tests on bounding volumes of increasing tightness. When contact cannot be ruled out by using simple tests, the final level of detection comes into effect by using thorough checks on finite element primitives. To that purpose, a robust optimization-based formulation that does not rely on orthogonal projections is outlined. The detection framework can be used to predict the exact collision time among finite element discretizations. The performance of the proposed methodology is investigated with a set of examples.

MSC:

74S05 Finite element methods applied to problems in solid mechanics
74M15 Contact in solid mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Hertz, H., ber die berührung fester elastischer körper, Journal für die reine und angewandte Mathematik, 92, 92, 156-171 (1881) · JFM 14.0807.01
[2] Schweizerhof, K.; Nilsson, L.; Hallquist, J., Crashworthiness analysis in the automotive industry, International Journal of Computer Applications in Technology, Special Issue on the Industrial Use of Finite-element Analysis, 5, 2/3/4, 134-156 (1992)
[3] Doltsinis, I. S., Aspects of modelling and computation in the analysis of metal forming, Engineering Computations, 7, 1, 2-20 (1990)
[4] Stupkiewicz, S.; Mróz, Z., A model of third body abrasive friction and wear in hot metal forming, Wear, 231, 1, 124-138 (1999)
[5] Benson, D. J.; Hallquist, J. O., A single surface contact algorithm for the post-buckling analysis of shell structures, Computer Methods in Applied Mechanics and Engineering, 78, 2, 141-163 (1990) · Zbl 0708.73079
[6] Camacho, G.; Ortiz, M., Adaptive lagrangian modelling of ballistic penetration of metallic targets, Computer Methods in Applied Mechanics and Engineering, 142, 3-4, 269-301 (1997) · Zbl 0892.73056
[7] Yang, B.; Laursen, T., A contact searching algorithm including bounding volume trees applied to finite sliding mortar formulations, Computational Mechanics, 41, 189-205 (2008) · Zbl 1162.74481
[8] Attaway, S. W.; Hendrickson, B. A.; Plimpton, S. J.; Gardner, D. R.; Vaughan, C. T.; Brown, K. H.; Heinstein, M. W., A parallel contact detection algorithm for transient solid dynamics simulations using PRONTO3D, Computational Mechanics, 22, 143-159 (1998) · Zbl 0927.74064
[9] Hubbard, P., Collision detection for interactive graphics applications, IEEE Transactions on Visualization and Computer Graphics, 1, 3, 218-230 (1995)
[10] Klosowski, J.; Held, M.; Mitchell, J.; Sowizral, H.; Zikan, K., Efficient collision detection using bounding volume hierarchies of k-dops, IEEE Transactions on Visualization and Computer Graphics, 4, 1, 21-36 (1998)
[12] Boyse, J. W., Interference detection among solids and surfaces, Communications of the ACM, 22, 1, 3-9 (1979)
[13] Cameron, S., Approximation hierarchies and s-bounds, (Proceedings of the First ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications, SMA ’91 (1991), ACM: ACM New York, NY, USA), 129-137
[14] Eberly, D. H., 3D game engine design, (A Practical Approach to Real-Time Computer Graphics. A Practical Approach to Real-Time Computer Graphics, The Morgan Kaufmann Series in Interactive 3D Technology (2006), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA)
[16] Gilbert, E.; Johnson, D.; Keerthi, S., A fast procedure for computing the distance between complex objects in three-dimensional space, IEEE Journal of Robotics and Automation, 4, 2, 193-203 (1988)
[17] Cameron, S., Collision detection by four-dimensional intersection testing, IEEE Transactions on Robotics and Automation, 6, 3, 291-302 (1990)
[18] Thibault, W. C.; Naylor, B. F., Set operations on polyhedra using binary space partitioning trees, (Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’87 (1987), ACM: ACM New York, NY, USA), 153-162
[19] Naylor, B.; Amanatides, J.; Thibault, W., Merging bsp trees yields polyhedral set operations, (Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’90 (1990), ACM: ACM New York, NY, USA), 115-124
[20] Bentley, J. L., Multidimensional binary search trees used for associative searching, Communications of the ACM, 18, 9, 509-517 (1975) · Zbl 0306.68061
[21] Friedman, J. H.; Bentley, J. L.; Finkel, R. A., An algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software, 3, 3, 209-226 (1977) · Zbl 0364.68037
[23] Samet, H., The quadtree and related hierarchical data structures, ACM Computer Survey, 16, 2, 187-260 (1984)
[24] Moore, M.; Wilhelms, J., Collision detection and response for computer animation, (Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’88 (1988), ACM: ACM New York, NY, USA), 289-298
[25] Noborio, H.; Fukuda, S.; Arimoto, S., Fast interference check method using octree representation, Advanced Robotics, 3, 3, 193-212 (1988)
[26] Beckmann, N.; Kriegel, H.-P.; Schneider, R.; Seeger, B., The \(R^⁎\)-tree: an efficient and robust access method for points and rectangles, (Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, SIGMOD ’90 (1990), ACM: ACM New York, NY, USA), 322-331
[27] Garcia-Alonso, A.; Serrano, N.; Flaquer, J., Solving the collision detection problem, IEEE Computer Graphics and Applications, 14, 3, 36-43 (1994)
[28] Gottschalk, S.; Lin, M. C.; Manocha, D., Obbtree: a hierarchical structure for rapid interference detection, (Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’96 (1996), ACM: ACM New York, NY, USA), 171-180
[29] Ehmann, S. A.; Lin, M. C., Accurate and fast proximity queries between polyhedra using convex surface decomposition, Computer Graphics Forum, 20, 3, 500-511 (2001)
[31] Jiménez, P.; Thomas, F.; Torras, C., 3d collision detection: a survey, Computers and Graphics, 25, 269-285 (2000)
[32] 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, Computer Graphics Forum, 24, 1, 61-81 (2005)
[33] Ericson, C., (Real-Time Collision Detection. Real-Time Collision Detection, The Morgan Kaufmann Series in Interactive 3-D Technology (2004), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA)
[34] Baraff, D., Analytical methods for dynamic simulation of non-penetrating rigid bodies, (Proceedings of the 16th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’89 (1989), ACM: ACM New York, NY, USA), 223-232
[35] Baraff, D., Fast contact force computation for nonpenetrating rigid bodies, (Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’94 (1994), ACM: ACM New York, NY, USA), 23-34
[36] Kaufman, D. M.; Edmunds, T.; Pai, D. K., Fast frictional dynamics for rigid bodies, (ACM SIGGRAPH 2005 Papers, SIGGRAPH ’05 (2005), ACM: ACM New York, NY, USA), 946-956
[37] Baraff, D.; Witkin, A., Dynamic simulation of non-penetrating flexible bodies, (Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’92 (1992), ACM: ACM New York, NY, USA), 303-308
[38] Pauly, M.; Pai, D. K.; Guibas, L. J., Quasi-rigid objects in contact, (Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’04 (2004), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 109-119
[39] Galoppo, N.; Otaduy, M. A.; Mecklenburg, P.; Gross, M.; Lin, M. C., Fast simulation of deformable models in contact using dynamic deformation textures, (Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’06 (2006), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 73-82
[40] Baraff, D.; Witkin, A., Large steps in cloth simulation, (Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’98 (1998), ACM: ACM New York, NY, USA), 43-54
[42] Bridson, R.; Fedkiw, R.; Anderson, J., Robust treatment of collisions, contact and friction for cloth animation, (Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’02 (2002), ACM: ACM New York, NY, USA), 594-603
[43] Kaldor, J. M.; James, D. L.; Marschner, S., Efficient yarn-based cloth with adaptive contact linearization, (ACM SIGGRAPH 2010 Papers, SIGGRAPH ’10 (2010), ACM: ACM New York, NY, USA), 105:1-105:10
[44] Chen, Z.; Feng, R.; Wang, H., Modeling friction and air effects between cloth and deformable bodies, ACM Transactions on Graphics, 32, 4 (2013), 88(1-88), pp. 8 · Zbl 1305.68325
[45] Heo, J.-P.; Seong, J.-K.; Kim, D.; Otaduy, M. A.; Hong, J.-M.; Tang, M.; Yoon, S.-E., Fastcd: fracturing-aware stable collision detection, (Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’10 (2010), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 149-158
[46] Glondu, L.; Schvartzman, S. C.; Marchal, M.; Dumont, G.; Otaduy, M. A., Efficient collision detection for brittle fracture, (Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’12 (2012), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 285-294
[47] Bertails-Descoubes, F.; Cadoux, F.; Daviet, G.; Acary, V., A nonsmooth newton solver for capturing exact coulomb friction in fiber assemblies, ACM Transactions on Graphics, 30, 1 (2011), 6(1-6), pp. 14
[48] Daviet, G.; Bertails-Descoubes, F.; Boissieux, L., A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics, (Proceedings of the 2011 SIGGRAPH Asia Conference, SA ’11 (2011), ACM: ACM New York, NY, USA), 139:1-139:12
[49] Gascón, J.; Zurdo, J. S.; Otaduy, M. A., Constraint-based simulation of adhesive contact, (Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’10 (2010), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 39-44
[50] Kaufman, D. M.; Sueda, S.; James, D. L.; Pai, D. K., Staggered projections for frictional contact in multibody systems, (ACM SIGGRAPH Asia Papers, SIGGRAPH Asia ’08 (2008), ACM: ACM New York, NY, USA), 164:1-164:11
[51] Harmon, D.; Vouga, E.; Smith, B.; Tamstorf, R.; Grinspun, E., Asynchronous contact mechanics, (ACM SIGGRAPH 2009 Papers, SIGGRAPH ’09 (2009), ACM: ACM New York, NY, USA), 87:1-87:12
[52] Otaduy, M. A.; Lin, M. C., Clods: dual hierarchies for multiresolution collision detection, (Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP ’03 (2003), Eurographics Association: Eurographics Association Aire-la-Ville, Switzerland), 94-101
[53] Larsson, T.; Akenine-Möller, T., Bounding volume hierarchies of slab cut balls, Computer Graphics Forum, 28, 8, 2379-2395 (2009)
[54] Heinstein, M. W.; Mello, F. J.; Attaway, S. W.; Laursen, T. A., Contact-impact modeling in explicit transient dynamics, Computer Methods in Applied Mechanics and Engineering, 187, 3-4, 621-640 (2000) · Zbl 0990.74064
[55] Wriggers, P., Computational Contact Mechanics (2006), Springer · Zbl 1104.74002
[56] Hughes, T., The finite element method: linear static and dynamic finite element analysis, Dover Civil and Mechanical Engineering Series (2000), Dover Publications · Zbl 1191.74002
[57] Zienkiewicz, O. C.; Taylor, R. L.; Zhu, J. Z., The Finite Element Method: Its Basis and Fundamentals (2005), Butterworth-Heinemann · Zbl 1307.74005
[58] Ritter, J., An efficient bounding sphere, (Glassner, A. S., Graphics Gems (1990), Academic Press Professional Inc.: Academic Press Professional Inc. San Diego, CA, USA), 301-303
[59] Larsson, T., Fast and tight fitting bounding spheres, (Proceedings of The Annual SIGRAD Conference (2008), Linköping University Electronic Press), 27-30
[60] Schwartz, J. T., Fin ding the minimum distance between two convex polygons, Information Processing Letters, 13, 4/5, 168-170 (1981)
[62] Bergen, G.v.d., Efficient collision detection of complex deformable models using aabb trees, Journal of Graphics Tools, 2, 4, 1-13 (1997) · Zbl 0927.68100
[63] Nocedal, J.; Wright, S. J., Numerical Optimization (2000), Springer
[65] Cohen, J. D.; Lin, M. C.; Manocha, D.; Ponamgi, M., I-collide: an interactive and exact collision detection system for large-scale environments, (Proceedings of the 1995 Symposium on Interactive 3D Graphics, I3D ’95 (1995), ACM: ACM New York, NY, USA), 189
[66] Kraft, D., Algorithm 733: tomp–fortran modules for optimal control calculations, ACM Transactions on Mathematical Software, 20, 3, 262-281 (1994) · Zbl 0888.65079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.