Broad Phase Collision Detection: New Methodology and Solution for Standardized Analysis of Algorithms
Resumo
Collision detection is a computational problem focused on the identification of geometric intersections between objects and, in general, proximity relationships among them. Despite its notorious relevance and applications in various computing fields, few authors have proposed solutions that are both general and scalable. Additionally, until the time of publication of the results of this work, there was no standard methodology for the analysis of algorithms, neither in academia nor in the industry: only proprietary scenes and comparative studies had been developed, making it difficult to reproduce and compare results. To tackle the issues previously mentioned, we present a new general and scalable solution for broad phase collision detection and a new methodology for comparative analysis of algorithms, named Broadmark, whose open-source code is publicly available, with the goal of transferring knowledge to academia, industry, and society, so far lacking in the scientific literature. Thus, by doing so, we aim to contribute to the generation of robust and multi-faceted solutions applied to various scenarios and, consequently, to greater transparency, ease of modification/extension and reproducibility of results.1Referências
D. M. Ming C. Lin and Y. J. Kim, "Collision and proximity queries," in Handbook of Discrete and Computational Geometry, 3rd ed. CRC Press, 2017, ch. 39. 2016. Figure 2: Scalability analysis up to one million objects. asset generation for games: A study on pixel art sprite sheets," in Anais do SBGames’19. IEEE, 2019, pp. 182–191.
C. Ericson, Real-time Collision Detection. CRC Press, 2004.
D. H. Eberly, Game physics. CRC Press, 2010.
Y. R. Serpa and M. A. F. Rodrigues, "Flexible use of temporal and spatial reasoning for fast and scalable CPU broad-phase collision detection using KD-Trees," Computer Graphics Forum (CGF), vol. 38, no. 1, pp. 1–14, 2017.
G. Capannini and T. Larsson, "Adaptive collision culling for massive simulations by a parallel and context-aware Sweep and Prune algorithm," TVCG, vol. 24, no. 7, pp. 2064–2077, 2018.
F. Liu, T. Harada, Y. Lee, and Y. J. Kim, "Real-time collision culling of a million bodies on graphics processing units," ACM Trans. on Graphics (TOG), vol. 29, no. 6, pp. 1–8, 2010.
L. Kettner, A. Meyer, and A. Zomorodian, "Intersecting sequences of dD iso-oriented boxes," in CGAL User and Reference Manual, 5.0 ed., 2019.
R. G. Luque, J. a. L. D. Comba, and C. M. D. S. Freitas, "Broad-phase collision detection using semi-adjusting BSP-trees," in Proceedings of the 2005 Symposium on Interactive 3D Graphics and Games (I3D). ACM, 2005, pp. 179–186.
M. Woulfe and M. Manzke, "A framework for benchmarking interactive collision detection," in Proc. of the 25th Conf. on Computer Graphics. ACM, 2009, pp. 205–212.
M. Baker, "Reproducibility crisis?" Nature, vol. 533, no. 26, pp. 353–66,
Y. R. Serpa, "Detecção de colisao broad phase: Nova solução e metodologia implementadas para análise padronizada de algoritmos," Master’s thesis, Programa de Pós-Graduação em Informática Aplicada (PPGIA). Universidade de Fortaleza (UNIFOR). Defesa: 19/12/2019, 2019.
Y. R. Serpa and M. A. F. Rodrigues, "Broadmark: A testing framework for broad-phase collision detection algorithms," Computer Graphics Forum (CGF), vol. 39, no. 1, pp. 436–449, 2019.
S.-H. Lo, C.-R. Lee, I.-H. Chung, and Y.-C. Chung, "Optimizing pairwise box intersection checking on GPUs for large-scale simulations," ACM Transactions on Modeling and Computer Simulation (TOMACS), vol. 23, no. 3, pp. 1–22, 2013.
D. J. Tracy, S. R. Buss, and B. M. Woods, "Efficient large-scale Sweep and Prune methods with AABB insertion and removal," in Proceedings of the 2009 IEEE Virtual Reality Conference (VR). Lafayette, LA, USA: IEEE, 2009, pp. 191–198.
G. Capannini and T. Larsson, "Efficient collision culling by a succinct bi-dimensional Sweep and Prune algorithm," in Proceedings of the 32nd Spring Conference on Computer Graphics (SCCG). Smolenice castle, Slovakia: ACM, 2016, pp. 25–32.
D. J. Tracy and S. Brown, "Accelerating physics in large, continuous virtual environments," Concurrency and Computation: Practice & Ex- perience, vol. 24, no. 2, pp. 125–134, 2012.
Q. Avril, V. Gouranton, and B. Arnaldi, "Fast collision culling in large- scale environments using GPU mapping function," in Proc. of the 2012 Eurographics Symposium (EG). Cagliari, Italy: The Eurographics Association, 2012, pp. 71–80.
——, "Collision detection: broad phase adaptation from multi-core to multi-GPU architecture," Journal of Virtual Reality and Broadcasting, vol. 6, no. 11, pp. 1–13, 2014.
——, "Dynamic adaptation of broad phase collision detection algo- rithms," in 2011 IEEE International Symposium on VR Innovation, March 2011, pp. 41–47.
——, "Synchronization-free parallel collision detection pipeline," in Proceedings of the 20th International Conference on Artificial Reality and Telexistence, Adelaide, Australia, Dec. 2010, pp. 1–7.
A. Zomorodian and H. Edelsbrunner, "Fast software for box intersec- tions," in Proceedings of the 16th Annual Symposium on Computational Geometry (SoCG). Clear Water Bay, Hong Kong: ACM, 2000, pp. 129– 138.
E. Coumans, "Bullet Physics," github.com/bulletphysics/bullet3, 2018.
Unity Technologies, "Unity 2019.2," unity.com, 2019.
D. V. Macedo, Y. R. Serpa, and M. A. F. Rodrigues, "Fast and realistic reflections using screen space and GPU ray tracing—a case study on rigid and deformable body simulations," ACM Computers in Entertainment (CIE), vol. 16, no. 4, p. 5, 2018.
Y. R. Serpa, M. B. Nogueira, H. Rocha, D. V. Macedo, and M. A. F. Rodrigues, "An interactive simulation-based game of a manufactur- ing process in heavy industry," Entertainment Computing (ENTCOM), vol. 34, pp. 1–11, 2020.
Y. R. Serpa, L. A. Pires, and M. A. F. Rodrigues, "Milestones and new frontiers in deep learning," in Proceedings of the SIBGRAPI-T 2019. IEEE, 2019, pp. 22–35.
Y. R. Serpa and M. A. F. Rodrigues, "Towards machine-learning assisted asset generation for games: A study on pixel art sprite sheets," in Anais do SBGames’19. IEEE, 2019, pp. 182–191.
C. Ericson, Real-time Collision Detection. CRC Press, 2004.
D. H. Eberly, Game physics. CRC Press, 2010.
Y. R. Serpa and M. A. F. Rodrigues, "Flexible use of temporal and spatial reasoning for fast and scalable CPU broad-phase collision detection using KD-Trees," Computer Graphics Forum (CGF), vol. 38, no. 1, pp. 1–14, 2017.
G. Capannini and T. Larsson, "Adaptive collision culling for massive simulations by a parallel and context-aware Sweep and Prune algorithm," TVCG, vol. 24, no. 7, pp. 2064–2077, 2018.
F. Liu, T. Harada, Y. Lee, and Y. J. Kim, "Real-time collision culling of a million bodies on graphics processing units," ACM Trans. on Graphics (TOG), vol. 29, no. 6, pp. 1–8, 2010.
L. Kettner, A. Meyer, and A. Zomorodian, "Intersecting sequences of dD iso-oriented boxes," in CGAL User and Reference Manual, 5.0 ed., 2019.
R. G. Luque, J. a. L. D. Comba, and C. M. D. S. Freitas, "Broad-phase collision detection using semi-adjusting BSP-trees," in Proceedings of the 2005 Symposium on Interactive 3D Graphics and Games (I3D). ACM, 2005, pp. 179–186.
M. Woulfe and M. Manzke, "A framework for benchmarking interactive collision detection," in Proc. of the 25th Conf. on Computer Graphics. ACM, 2009, pp. 205–212.
M. Baker, "Reproducibility crisis?" Nature, vol. 533, no. 26, pp. 353–66,
Y. R. Serpa, "Detecção de colisao broad phase: Nova solução e metodologia implementadas para análise padronizada de algoritmos," Master’s thesis, Programa de Pós-Graduação em Informática Aplicada (PPGIA). Universidade de Fortaleza (UNIFOR). Defesa: 19/12/2019, 2019.
Y. R. Serpa and M. A. F. Rodrigues, "Broadmark: A testing framework for broad-phase collision detection algorithms," Computer Graphics Forum (CGF), vol. 39, no. 1, pp. 436–449, 2019.
S.-H. Lo, C.-R. Lee, I.-H. Chung, and Y.-C. Chung, "Optimizing pairwise box intersection checking on GPUs for large-scale simulations," ACM Transactions on Modeling and Computer Simulation (TOMACS), vol. 23, no. 3, pp. 1–22, 2013.
D. J. Tracy, S. R. Buss, and B. M. Woods, "Efficient large-scale Sweep and Prune methods with AABB insertion and removal," in Proceedings of the 2009 IEEE Virtual Reality Conference (VR). Lafayette, LA, USA: IEEE, 2009, pp. 191–198.
G. Capannini and T. Larsson, "Efficient collision culling by a succinct bi-dimensional Sweep and Prune algorithm," in Proceedings of the 32nd Spring Conference on Computer Graphics (SCCG). Smolenice castle, Slovakia: ACM, 2016, pp. 25–32.
D. J. Tracy and S. Brown, "Accelerating physics in large, continuous virtual environments," Concurrency and Computation: Practice & Ex- perience, vol. 24, no. 2, pp. 125–134, 2012.
Q. Avril, V. Gouranton, and B. Arnaldi, "Fast collision culling in large- scale environments using GPU mapping function," in Proc. of the 2012 Eurographics Symposium (EG). Cagliari, Italy: The Eurographics Association, 2012, pp. 71–80.
——, "Collision detection: broad phase adaptation from multi-core to multi-GPU architecture," Journal of Virtual Reality and Broadcasting, vol. 6, no. 11, pp. 1–13, 2014.
——, "Dynamic adaptation of broad phase collision detection algo- rithms," in 2011 IEEE International Symposium on VR Innovation, March 2011, pp. 41–47.
——, "Synchronization-free parallel collision detection pipeline," in Proceedings of the 20th International Conference on Artificial Reality and Telexistence, Adelaide, Australia, Dec. 2010, pp. 1–7.
A. Zomorodian and H. Edelsbrunner, "Fast software for box intersec- tions," in Proceedings of the 16th Annual Symposium on Computational Geometry (SoCG). Clear Water Bay, Hong Kong: ACM, 2000, pp. 129– 138.
E. Coumans, "Bullet Physics," github.com/bulletphysics/bullet3, 2018.
Unity Technologies, "Unity 2019.2," unity.com, 2019.
D. V. Macedo, Y. R. Serpa, and M. A. F. Rodrigues, "Fast and realistic reflections using screen space and GPU ray tracing—a case study on rigid and deformable body simulations," ACM Computers in Entertainment (CIE), vol. 16, no. 4, p. 5, 2018.
Y. R. Serpa, M. B. Nogueira, H. Rocha, D. V. Macedo, and M. A. F. Rodrigues, "An interactive simulation-based game of a manufactur- ing process in heavy industry," Entertainment Computing (ENTCOM), vol. 34, pp. 1–11, 2020.
Y. R. Serpa, L. A. Pires, and M. A. F. Rodrigues, "Milestones and new frontiers in deep learning," in Proceedings of the SIBGRAPI-T 2019. IEEE, 2019, pp. 22–35.
Y. R. Serpa and M. A. F. Rodrigues, "Towards machine-learning assisted asset generation for games: A study on pixel art sprite sheets," in Anais do SBGames’19. IEEE, 2019, pp. 182–191.
Publicado
07/11/2020
Como Citar
SERPA, Ygor Rebouças; RODRIGUES, Maria Andréia Formico.
Broad Phase Collision Detection: New Methodology and Solution for Standardized Analysis of Algorithms. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 33. , 2020, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 43-49.
DOI: https://doi.org/10.5753/sibgrapi.est.2020.12982.
