“Contact Detection Between Curved Fibres: High Order Makes a Difference” – ACM SIGGRAPH HISTORY ARCHIVES

“Contact Detection Between Curved Fibres: High Order Makes a Difference”

  • ©

Conference:


Type(s):


Title:

    Contact Detection Between Curved Fibres: High Order Makes a Difference

Presenter(s)/Author(s):



Abstract:


    When simulating fibre assemblies with standard techniques, we identify spurious artifacts in the contact forces which are caused by the use of low-order proxys for collision detection. We fix this issue by developing an efficient and accurate high-order detection scheme between two smooth curves, which is successfully applied to super-helices.

References:


    [1]
    Steven S. An, Doug L. James, and Steve. Marschner. 2012. Motion-driven Concatenative Synthesis of Cloth Sounds. ACM Trans. Graph. 31, 4, Article 102 (July 2012), 10 pages.

    [2]
    Tom M Apostol. 1991. Calculus, volume 1. John Wiley & Sons.

    [3]
    David Baraff. 1989. Analytical methods for dynamic simulation of non-penetrating rigid bodies. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques. 223–232.

    [4]
    David Baraff. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Computer Graphics Proceedings. ACM, New York, NY, USA, 23–34.

    [5]
    Aric Bartle, Alla Sheffer, Vladimir Kim, Danny M. Kaufman, Nicholas Vining, and Floraine Berthouzoz. 2016. Physics-driven Pattern Adjustment for Direct 3D Garment Editing. ACM Trans. Graph. 35, 4, Article 50 (July 2016), 11 pages.

    [6]
    Milan Batista. 2015. Large deflections of a beam subject to three-point bending. International Journal of Non-Linear Mechanics 69 (2015), 84–92.

    [7]
    Mikl?s Bergou, Basile Audoly, Etienne Vouga, Max Wardetzky, and Eitan Grinspun. 2010. Discrete viscous threads. ACM Transactions on graphics (TOG) 29, 4 (2010), 1–10.

    [8]
    Mikl?s Bergou, Max Wardetzky, Stephen Robinson, Basile Audoly, and Eitan Grinspun. 2008. Discrete elastic rods. In ACM SIGGRAPH 2008 papers. 1–12.

    [9]
    Florence Bertails, Basile Audoly, Marie-Paule Cani, Bernard Querleux, Fr?d?ric Leroy, and Jean-Luc L?v?que. 2006. Super-helices for predicting the dynamics of natural hair. ACM Transactions on Graphics (TOG) 25, 3 (2006), 1180–1187.

    [10]
    Florence Bertails, Basile Audoly, Bernard Querleux, Fr?d?ric Leroy, Jean-Luc L?v?que, and Marie-Paule Cani. 2005. Predicting Natural Hair Shapes by Solving the Statics of Flexible Rods. In Eurographics’05 (short papers), J. Dingliana and F. Ganovelli (Eds.). http://www-evasion.imag.fr/Publications/2005/BAQLLC05

    [11]
    Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3 (2002), 594–603. http://www.cs.ubc.ca/~rbridson/docs/cloth2002.pdf

    [12]
    Tyson Brochu, Essex Edwards, and Robert Bridson. 2012. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–7.

    [13]
    Romain Casati and Florence Bertails-Descoubes. 2013. Super Space Clothoids. ACM Transactions on Graphics (Proc. ACM SIGGRAPH’13) 32, 4, Article 48 (July 2013), 12 pages.

    [14]
    Jung-Woo Chang, Yi-King Choi, Myung-Soo Kim, and Wenping Wang. 2011. Computation of the minimum distance between two B?zier curves/surfaces. Computers & Graphics 35, 3 (2011), 677–684. Shape Modeling International (SMI) Conference 2011.

    [15]
    Min Gyu Choi. 2020. Computing the closest approach distance of two ellipsoids. Symmetry 12, 8 (2020), 1302.

    [16]
    Gabriel Cirio, Jorge Lopez-Moreno, David Miraut, and Miguel A Otaduy. 2014. Yarn-level simulation of woven cloth. ACM Transactions on Graphics (TOG) 33, 6 (2014), 1–11.

    [17]
    Alexander Clegg, Jie Tan, Greg Turk, and C. Karen Liu. 2015. Animating Human Dressing. ACM Trans. Graph. 34, 4, Article 116 (July 2015), 9 pages.

    [18]
    Gilles Daviet, Florence Bertails-Descoubes, and Laurence Boissieux. 2011. A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics. In Proceedings of the 2011 SIGGRAPH Asia Conference. 1–12.

    [19]
    Roland De La Mettrie, Didier Saint-L?ger, Geneviev?ve Loussouarn, Annelise Garcel, Crystal Porter, and Andr? Langaney. 2007. Shape variability and classification of human hair: a worldwide approach. Human biology 79, 3 (2007), 265–281.

    [20]
    Laura De Lorenzis, Peter Wriggers, and Thomas J.R. Hughes. 2014. Isogeometric contact: a review. GAMM-Mitteilungen 37, 1 (2014), 85–123. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/gamm.201410005

    [21]
    Zackory Erickson, Alexander Clegg, Wenhao Yu, Greg Turk, C. Karen Liu, and Charles C. Kemp. 2017. What does the person feel? Learning to infer applied forces during robot-assisted dressing. In 2017 IEEE International Conference on Robotics and Automation (ICRA). 6058–6065.

    [22]
    Christer Ericson. 2004. Real-time collision detection. Crc Press.

    [23]
    Ye Fan, Joshua Litven, David I. W. Levin, and Dinesh K. Pai. 2013. Eulerian-on-Lagrangian Simulation. ACM Trans. Graph. 32, 3, Article 22 (jul 2013), 9 pages.

    [24]
    Yun Fei, Christopher Batty, Eitan Grinspun, and Changxi Zheng. 2019. A multi-scale model for coupling strands with shear-dependent liquid. ACM Transactions on Graphics (TOG) 38, 6 (2019), 1–20.

    [25]
    Robert Frisch-Fay. 1962. Flexible bars. Butterworths.

    [26]
    Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, and Eitan Grinspun. 2007. Efficient simulation of inextensible cloth. In ACM Trans. Graph. (San Diego, California) (SIGGRAPH ’07). ACM, New York, NY, USA, Article 49.

    [27]
    Sunil Hadap. 2006. Oriented strands – dynamics of stiff multi-body system. In ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’06). ACM-EG SCA, 91–100.

    [28]
    Thomas J.R. Hughes, J. Austin Cottrell, and Yuri Bazilevs. 2005. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement. Computer Methods in Applied Mechanics and Engineering 194, 39 (2005), 4135–4195.

    [29]
    David E. Johnson and Elaine Cohen. 1998. A framework for efficient minimum distance computations. Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146) 4 (1998), 3678–3684 vol.4. https://api.semanticscholar.org/CorpusID:5297080

    [30]
    Danny M. Kaufman, Shinjiro Sueda, Doug L. James, and Dinesh Pai. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Trans. Graph. 27, 5, Article 164 (Dec. 2008), 11 pages.

    [31]
    Danny M. Kaufman, Rasmus Tamstorf, Breannan Smith, Jean-Marie Aubry, and Eitan Grinspun. 2014. Adaptive nonlinearity for collisions in complex rod assemblies. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–12.

    [32]
    Paul G. Kry and Dinesh K. Pai. 2003. Continuous Contact Simulation for Smooth Surfaces. ACM Trans. Graph. 22, 1 (jan 2003), 106–129.

    [33]
    Arun Lakshmanan, Andrew Patterson, Venanzio Cichella, and Naira Hovakimyan. 2019. Proximity queries for absolutely continuous parametric curves. arXiv preprint arXiv:1902.05027 (2019).

    [34]
    Eric Larsen, Stefan Gottschalk, Ming C Lin, and Dinesh Manocha. 1999. Fast proximity queries with swept sphere volumes. Technical Report TR99-018. Department of Computer Science, University of North Carolina.

    [35]
    Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy R. Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020a. Incremental potential contact: intersection-and inversion-free, large-deformation dynamics. ACM Trans. Graph. 39, 4 (2020), 49.

    [36]
    Minchen Li, Danny M. Kaufman, and Chenfanfu Jiang. 2020b. Codimensional incremental potential contact. arXiv preprint arXiv:2012.04457 (2020).

    [37]
    Zo? Marschner, Paul Zhang, David Palmer, and Justin Solomon. 2021. Sum-of-squares geometry processing. ACM Transactions on Graphics (TOG) 40, 6 (2021), 1–13.

    [38]
    Jon?s Mart?nez, M?lina Skouras, Christian Schumacher, Samuel Hornus, Sylvain Lefebvre, and Bernhard Thomaszewski. 2019. Star-Shaped Metrics for Mechanical Meta-material Design. ACM Transactions on Graphics 38, 4 (July 2019), Article No. 82 :1–13. Special issue, SIGGRAPH 2019.

    [39]
    Tyler McMillen and Alain Goriely. 2002. Tendril perversion in intrinsically curved rods. Journal of Nonlinear Science 12, 3 (2002), 241–281.

    [40]
    Christoph Meier, Wolfgang A Wall, and Alexander Popp. 2017. A unified approach for beam-to-beam contact. Computer Methods in Applied Mechanics and Engineering 315 (2017), 972–1010.

    [41]
    Ken Museth. 2020. Physics simulations: Is it Hollywood magic or rocket science. http://computeranimation.org/2020/program.html#keynote1

    [42]
    Yves Nievergelt. 2009. Computing the distance from a point to a helix and solving Kepler’s equation. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment 598, 3 (2009), 788–794.

    [43]
    Olivier Nocent and Yannick Remion. 2001. Continuous deformation energy for dynamic material splines subject to finite displacements. In EG workshop on Computer Animation and Simulation (EG CAS’01). 88–97.

    [44]
    Richard S Palmer. 1989. Computational complexity of motion and stability of polygons. Technical Report. Cornell University.

    [45]
    Astrid Pechstein and Johannes Gerstmayr. 2013. A Lagrange-Eulerian formulation of an axially moving beam based on the absolute nodal coordinate formulation. Multibody System Dynamics 30 (2013), 343–358.

    [46]
    St?phane Redon, Abderrahmane Kheddar, and Sabine Coquillart. 2002. Fast continuous collision detection between rigid bodies. In Computer graphics forum, Vol. 21. Wiley Online Library, 279–287.

    [47]
    Clarence Robbins. 2012. Chemical and physical behavior of human hair. Vol. 4. Springer.

    [48]
    Victor Romero, Micka?l Ly, Abdullah-Haroon Rasheed, Rapha?l Charrondi?re, Arnaud Lazarus, S?bastien Neukirch, and Florence Bertails-Descoubes. 2021. Physical validation of simulators in Computer Graphics: A new framework dedicated to slender elastic structures and frictional contact. ACM Transactions on Graphics 40, 4 (Aug. 2021), Article 66: 1–19.

    [49]
    Rosa M. S?nchez-Banderas, Alejandro Rodr?guez, H?ctor Barreiro, and Miguel A. Otaduy. 2020. Robust Eulerian-on-Lagrangian Rods. ACM Trans. Graph. 39, 4, Article 59 (aug 2020), 10 pages.

    [50]
    Daniel Scholz. 2011. Deterministic global optimization: geometric branch-and-bound methods and their applications. Vol. 63. Springer Science & Business Media.

    [51]
    Eston Schweickart, Doug L. James, and Steve Marschner. 2017. Animating Elastic Rods with Sound. ACM Transactions on Graphics 36, 4 (July 2017).

    [52]
    Andrew Selle, Michael Lentine, and Ronald Fedkiw. 2008. A mass spring model for hair

    [53]
    simulation. ACM Transactions on Graphics (Proc. ACM SIGGRAPH’08) 27, 3 (2008), 1–11.

    [54]
    Alvin Shi, Haomiao Wu, Jarred Parr, A. M. Darke, and Theodore Kim. 2023. Lifted Curls: A Model for Tightly Coiled Hair Simulation. Proc. ACM Comput. Graph. Interact. Tech. 6, 3, Article 42 (aug 2023), 19 pages.

    [55]
    John M Snyder, Adam R Woodbury, Kurt Fleischer, Bena Currin, and Alan H Barr. 1993. Interval methods for multi-point collisions between time-dependent curved surfaces. In Proceedings of the 20th annual conference on Computer Graphics and interactive techniques. 321–334.

    [56]
    Jonas Spillmann and Matthias Teschner. 2007. CoRdE: Cosserat rod elements for the dynamic simulation of one-dimensional elastic objects. In ACM SIGGRAPH – EG Symposium on Computer Animation (SCA’07). ACM-EG SCA, 63–72.

    [57]
    Shinjiro Sueda, Garrett L Jones, David IW Levin, and Dinesh K Pai. 2011. Large-scale dynamic simulation of highly constrained strands. In ACM SIGGRAPH 2011 papers. 1–10.

    [58]
    Brook Taylor. 1717. Methodus incrementorum directa & inversa. Inny.

    [59]
    Matthias Teschner, Stefan Kimmerle, Bruno Heidelberger, Gabriel Zachmann, Laks Raghupathi, Arnulph Fuhrmann, M-P Cani, Fran?ois Faure, Nadia Magnenat-Thalmann, Wolfgang Strasser, et al. 2005. Collision detection for deformable objects. In Computer graphics forum, Vol. 24. Wiley Online Library, 61–81.

    [60]
    Thibault Tricard, Vincent Tavernier, C?dric Zanni, Jon?s Mart?nez, Pierre-Alexandre Hugron, Fabrice Neyret, and Sylvain Lefebvre. 2020. Freely orientable microstructures for designing deformable 3D prints. ACM Transactions on Graphics (Dec. 2020).

    [61]
    Gino Van Den Bergen. 2003. Collision detection in interactive 3D environments. CRC Press.

    [62]
    Brian Von Herzen, Alan H Barr, and Harold R Zatz. 1990. Geometric collisions for time-dependent parametric surfaces. In Proceedings of the 17th annual conference on Computer graphics and interactive techniques. 39–48.

    [63]
    Li Vu-Quoc and S Li. 1995. Dynamics of sliding geometrically-exact beams: large angle maneuver and parametric resonance. Computer methods in applied mechanics and engineering 120, 1–2 (1995), 65–118.

    [64]
    Peter Wriggers and Tod A Laursen. 2006. Computational contact mechanics. Vol. 2. Springer.

    [65]
    Paul Zhang, Zo? Marschner, Justin Solomon, and Rasmus Tamstorf. 2023. Sum-of-Squares Collision Detection for Curved Shapes and Paths. In ACM SIGGRAPH 2023 Conference Proceedings (Los Angeles, CA, USA) (SIGGRAPH ’23). Association for Computing Machinery, New York, NY, USA, Article 76, 11 pages.

    [66]
    Changxi Zheng and Doug L. James. 2011. Toward High-Quality Modal Contact Sound. ACM Trans. Graph. 30, 4, Article 38 (jul 2011), 12 pages.


ACM Digital Library Publication:



Overview Page:



Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org