Detecção de Colisão Broad Phase: Nova Solução e Metodologia para Análise Padronizada de Algoritmos
Resumo
Detecção de colisão é um problema computacional focado na identificação de interseções geométricas entre objetos e, em geral, relações de proximidade entre os mesmos. Apesar de sua notória relevância para várias áreas do conhecimento, poucos autores propuseram soluções simultaneamente gerais e escaláveis. Adicionalmente, não havia uma metodologia padrão, nem na academia, nem na indústria: somente modelos próprios de cenários e de análises comparativas tinham sido desenvolvidos, dificultando a reprodução e a comparação dos resultados. Neste contexto, apresentamos uma nova solução genérica e escalável para a detecção de colisão broad phase e uma nova metodologia para a análise comparativa de algoritmos, nomeada Broadmark, cujo código open-source está disponível publicamente, visando a transferência de conhecimento para a academia, indústria e sociedade. Assim, almejamos contribuir para a geração de soluções robustas e multi-facetadas aplicadas a cenários diversos e, portanto, para uma maior transparência, facilidade de modificação/extensão e reprodutibilidade dos resultados.
Referências
Capannini, G. and Larsson, T. (2018). Adaptive collision culling for massive simulations by a parallel and context-aware Sweep and Prune algorithm. TVCG, 24(7):2064-2077.
Coumans, E. (2018). Bullet Physics. github.com/bulletphysics/bullet3.
Kettner, L., Meyer, A., and Zomorodian, A. (2019). Intersecting sequences of dD iso-oriented boxes. In CGAL User and Reference Manual. 5.0 edition.
Liu, F., Harada, T., Lee, Y., and Kim, Y. J. (2010). Real-time collision culling of a million bodies on graphics processing units. ACM Trans. on Graphics (TOG), 29(6):1-8.
Luque, R. G., Comba, J. a. L. D., and Freitas, C. M. D. S. (2005). Broad-phase collision detection using semi-adjusting BSP-trees. In Proceedings of the 2005 Symposium on Interactive 3D Graphics and Games (I3D), pages 179-186. ACM.
Macedo, D. V., Serpa, Y. R., Rodrigues, M. A. F., et al. (2018). 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), 16(4):5.
Ming C. Lin, D. M. and Kim, Y. J. (2017). Collision and proximity queries. In Handbook of Discrete and Computational Geometry, chapter 39. CRC Press, 3rd edition.
Serpa, Y. R. (2019). Detecc ̧ao de colisão broad phase: Nova solução e metodologia implementadas para analise padronizada de algoritmos. Dissertação de Mestrado. Universidade de Fortaleza (UNIFOR). Defesa: 19/12/2019.
Serpa, Y. R., Nogueira, M. B., Rocha, H., Macedo, D. V., and Rodrigues, M. A. F. (2020). An interactive simulation-based game of a manufacturing process in heavy industry. Entertainment Computing (ENTCOM), 34:1-11.
Serpa, Y. R., Pires, L. A., and Rodrigues, M. A. F. (2019). Milestones and new frontiers in deep learning. In Proc. of SIBGRAPI-T 2019, pages 22-35. IEEE.
Serpa, Y. R. and Rodrigues, M. A. F. (2017). Flexible use of temporal and spatial reasoning for fast and scalable CPU broad-phase collision detection using KD-Trees. Computer Graphics Forum (CGF), 38(1):1-14.
Serpa, Y. R. and Rodrigues, M. A. F. (2019a). Broadmark: A testing framework for broad-phase collision detection algorithms. Comp. Graphics Forum (CGF), 39(1):436-449.
Serpa, Y. R. and Rodrigues, M. A. F. (2019b). Towards machine-learning assisted asset generation for games: A study on pixel art sprite sheets. In Anais do SBGames’19, pages 182-191. IEEE.
Tracy, D. J., Buss, S. R., and Woods, B. M. (2009). Efficient large-scale Sweep and Prune methods with AABB insertion and removal. In Proceedings of the 2009 IEEE Virtual Reality Conference (VR), pages 191-198, Lafayette, LA, USA. IEEE.
Woulfe, M. and Manzke, M. (2009). A framework for benchmarking interactive collision detection. In Proc. of the 25th Conf. on Computer Graphics, pages 205-212. ACM.
