non-gon: A Non-Polygonal Collision Detection Library for Real-Time Queries Between Smooth Convex Shapes
References
- Ericson C.
Chapter 2 - Collision Detection Design Issues . In: Ericson C, editor. Real-Time Collision Detection. The Morgan Kaufmann Series in Interactive 3D Technology. San Francisco: Morgan Kaufmann; 2005. pp. 7–21. Available from:https://www.sciencedirect.com/science/article/pii/B9781558607323500073 . - Schneider P, Eberly DH. Geometric tools for computer graphics. Elsevier; 2002.
- Hadap S, Eberle D, Volino P, Lin MC, Redon S, Ericson C.
Collision Detection and Proximity Queries . In: ACM SIGGRAPH 2004 Course Notes. SIGGRAPH ‘04. New York, NY, USA: Association for Computing Machinery; 2004. p. 15–es. DOI: 10.1145/1103900.1103915 - Kockara S, Halic T, Iqbal K, Bayrak C, Rowe R. Collision detection: A survey. In: 2007 IEEE International Conference on Systems, Man and Cybernetics.
IEEE ; 2007. pp. 4046–4051. DOI: 10.1109/ICSMC.2007.4414258 - Moore M, Wilhelms J. Collision detection and response for computer animation. In: Proceedings of the 15th annual conference on Computer graphics and interactive techniques. 1988. pp. 289–298. DOI: 10.1145/54852.378528
- Gregory A, Lin MC, Gottschalk S, Taylor R. A framework for fast and accurate collision detection for haptic interaction. In: ACM SIGGRAPH 2005 Courses. 2005. pp. 34–es. DOI: 10.1145/1198555.1198604
- Jiménez P, Thomas F, Torras C. 3D collision detection: a survey. Computers & Graphics. 2001;25(2):269–285. DOI: 10.1016/S0097-8493(00)00130-8
- Lopes D, Neptune R, Ambrósio J, Silva M. A superellipsoid-plane model for simulating foot-ground contact during human gait. Computer methods in biomechanics and biomedical engineering. 2016;19(9):954–963. DOI: 10.1080/10255842.2015.1081181
- Arbabi E, Boulic R, Thalmann D. Fast collision detection methods for joint surfaces. Journal of Biomechanics. 2009;42(2):91–99. DOI: 10.1016/j.jbiomech.2008.10.017
- Goudarzi P, Hassanzadeh B. Collision risk in autonomous vehicles: classification, challenges, and open research areas. Vehicles. 2024;6(1):157–190. DOI: 10.3390/vehicles6010007
- Hamidaoui M, Talhaoui MZ, Li M, Midoun MA, Haouassi S, Mekkaoui DE, et al. Survey of Autonomous Vehicles’ Collision Avoidance Algorithms. Sensors (Basel, Switzerland). 2025;25(2):395. DOI: 10.3390/s25020395
- Rubio-Largo S, Lind P, Maza D, Hidalgo R. Granular gas of ellipsoids: analytical collision detection implemented on GPUs. Computational Particle Mechanics. 2015;2(2):127–138. DOI: 10.1007/s40571-015-0042-y
- Morgan G, Storey K. Scalable collision detection for massively multiplayer online games. In: 19th International Conference on Advanced Information Networking and Applications (AINA’05) Volume 1 (AINA papers), vol. 1. Taipei, Taiwan; 2005. pp. 873–878. DOI: 10.1109/AINA.2005.302
- Ng K, Yeap Y, Tan Y, Ghauth K. Collision detection optimization on mobile device for shoot’em up game. In: 2012 International Conference on Computer & Information Science (ICCIS), vol. 1.
IEEE ; 2012. pp. 464–468. DOI: 10.1109/ICCISci.2012.6297290 - Lazaridis L, Papatsimouli M, Kollias KF, Sarigiannidis P, Fragulis GF. Hitboxes: A Survey About Collision Detection in Video Games. In: International Conference on Human-Computer Interaction.
Springer ; 2021. pp. 314–326. DOI: 10.1007/978-3-030-77277-2_24 - Andrews S, Erleben K, Ferguson Z. Contact and friction simulation for computer graphics. In: ACM SIGGRAPH 2022 Courses; 2022. pp. 1–172. DOI: 10.1145/3532720.3535640
- J. Li, Baofeng Gao, Guo S. Design of collision detection algorithms and force feedback for a virtual reality training intervention operation system. In: 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), Zhuhai, China; 2015. pp. 1660–1665. DOI: 10.1109/ROBIO.2015.7419010
- Tzafestas C, Coiffet P. Real-time collision detection using spherical octrees: virtual reality application. In: Proceedings 5th IEEE International Workshop on Robot and Human Communication. RO-MAN’96 TSUKUBA, Tsukuba, Japan; 1996. pp. 500–506. DOI: 10.1109/ROMAN.1996.568888
- Hubbard PM. Interactive collision detection. In: Proceedings of 1993 IEEE Research Properties in Virtual Reality Symposium.
IEEE ; 1993. pp. 24–31. DOI: 10.1109/VRAIS.1993.378267 - Held M, Klosowski JT, Mitchell JS. Evaluation of collision detection methods for virtual reality fly-throughs. In: Canadian Conference on Computational Geometry.
Citeseer ; 1995. pp. 205–210. - Lin MC, Manocha D, Kim YJ.
Collision and proximity queries . In: Handbook of discrete and computational geometry. Chapman and Hall/CRC; 2017. pp. 1029–1056. - Johnson DE, Cohen E. A framework for efficient minimum distance computations. In: Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No. 98CH36146), vol. 4.
IEEE ; 1998. pp. 3678–3684. DOI: 10.1109/ROBOT.1998.681403 - Gonçalves AA, Bernardino A, Jorge J, Lopes DS. A benchmark study on accuracy-controlled distance calculation between superellipsoid and superovoid contact geometries. Mechanism and Machine Theory. 2017;115:77–96. DOI: 10.1016/j.mechmachtheory.2017.04.008
- Huh S, Lee Y, Gornowicz G, Animation D, Henderson RD. Fast and Robust Continuous Collision Detection (fastCCD). Research Dreamworks Com. 2014.
- Beker O, Gürtler N, Shi J, Geist AR, Razmjoo A, Martius G, et al. A Smooth Analytical Formulation of Collision Detection and Rigid Body Dynamics With Contact. arXiv preprint arXiv:250311736. 2025;. DOI: 10.1109/IROS60139.2025.11247449
- Hofmann A, Mikelsons L, Gubsch I, Schubert C. Simulating collisions within the Modelica multibody library. 2014. DOI: 10.3384/ecp14096949
- Fiser D. libccd: Library for collision detection between two convex shapes. URL:
https://github.com/danfis/libccd (visited on 2023-07-05). 2018. - Caravantes J, Diaz–Toca GM, Fioravanti M, Gonzalez-Vega L. Solving the interference problem for ellipses and ellipsoids: New formulae. Journal of Computational and Applied Mathematics. 2022;407:114072. DOI: 10.1016/j.cam.2021.114072
- Chittawadigi RG, Saha SK. An analytical method to detect collision between cylinders using dual number algebra. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems.
IEEE ; 2013. pp. 5353–5358. DOI: 10.1109/IROS.2013.6697131 - Brozos-Vázquez M, Pereira-Sáez MJ, Souto-Salorio MJ, Tarrío-Tobar AD. Classification of the relative positions between a small ellipsoid and an elliptic paraboloid. Computer Aided Geometric Design. 2019;72:34–48. DOI: 10.1016/j.cagd.2019.05.002
- Bektas S. On the Intersection of a Hyperboloid and a Plane. International Journal of Discrete Mathematics. 2017;2(2):38–42.
- Chou CC. A closed-form general solution for the distance of point-to-ellipse in two dimensions. Journal of Interdisciplinary Mathematics. 2019;22(3):337–351. DOI: 10.1080/09720502.2019.1624064
- Kim IS. An algorithm for finding the distance between two ellipses. Communications of the Korean mathematical society. 2006;21(3):559–567. DOI: 10.4134/CKMS.2006.21.3.559
- Chen S, Xin S, He Y, Wang G. The closest and farthest points to an affine ellipse or ellipsoid. Tsinghua Science and Technology. 2012;17(4):481–484. DOI: 10.1109/TST.2012.6297594
- Zheng X, Palffy-Muhoray P. Distance of closest approach of two arbitrary hard ellipses in two dimensions. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics. 2007;75(6):061709. DOI: 10.1103/PhysRevE.75.061709
- Romer UJ, Fidlin A, Seemann W. Explicit analytical solutions for two-dimensional contact detection problems between almost arbitrary geometries and straight or circular counterparts. Mechanism and Machine Theory. 2018;128:205–224. DOI: 10.1016/j.mechmachtheory.2018.05.018
- Zheng X, Iglesias W, Palffy-Muhoray P. Distance of closest approach of two arbitrary hard ellipsoids. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics. 2009;79(5):057702. DOI: 10.1103/PhysRevE.79.057702
- Romer UJ, Fidlin A, Seemann W. The normal parameterization and its application to collision detection. Mechanism and Machine Theory. 2020;151:103906. DOI: 10.1016/j.mechmachtheory.2020.103906
- Lopes DS, Neptune R, Ambrósio J, Silva M. A superellipsoid-plane model for simulating foot-ground contact during human gait. In: Computer Methods in Biomechanics and Biomedical Engineering, vol. 19, 2016. pp. 954–963. DOI: 10.1080/10255842.2015.1081181
- Denavit J, Hartenberg RS. A kinematic notation for lower-pair mechanisms based on matrices. 1955. DOI: 10.1115/1.4011045
- Pan J, Chitta S, Manocha D, Lamiraux F, Mirabel J, Carpentier J, et al. Coal: an extension of the flexible collision library. Feb. 2025.
DOI: https://doi.org/10.5334/jors.585 | Journal eISSN: 2049-9647
Language: English
Page range: 61 - 61
Submitted on: Jun 6, 2025
Accepted on: Jul 31, 2026
Published on: Sep 4, 2026
Published by: Ubiquity Press
In partnership with: Paradigm Publishing Services
Keywords:
© 2026 Ivo Roupa, Rodrigo Damasceno, Aasam Karim, Lourenço Mourão, João Afonso, Pedro Campos, Daniel Simões Lopes, published by Ubiquity Press
This work is licensed under the Creative Commons Attribution 4.0 License.