Relações Espaciais, Temporais e de Ordem para Detecção de Colisão Broad Phase Genérica e Escalável
Resumo
Simulações físicas são fundamentais para a representação computacional de situações do mundo real. Neste contexto, a detecção de colisões entre objetos 3D é crucial, uma vez que provê a ilusão de que estes são sólidos, porém, não há uma solução simultaneamente capaz de eficientemente atuar genericamente e escalar de maneira competitiva. Este trabalho apresenta e valida uma nova solução otimizada para a detecção de colisão broad phase que preenche esta lacuna, a qual é baseada em uma associação entre a KD-Tree e as técnicas Sweep-and-Prune e incremental. A solução obteve resultados duas a três vezes melhores que as demais soluções do estado-da-arte, sendo robusta a variações de comportamento, tamanho e distribuição dos objetos. Além disso, mostrou-se capaz de atuar eficientemente em todos os cenários testados e escalar em ambientes com até um milhão de objetos.
Referências
Coming, D. S. and Staadt, O. G. (2005). Kinetic sweep and prune for collision detection. In Proc. of the 2nd VRIPHYS.
Coumans, E. (2018). Bullet physics: Dynamic bounding volume tree. [link].
Ericson, C. (2004). Real-time Collision Detection. CRC Press.
Glass, K. (2005). Analysis of broad-phase spatial partitioning optimizations in collision detection. Technical report, Rhodes University.
Kettner, L., Meyer, A., and Zomorodian, A. (2018). Intersecting sequences of dD iso-oriented boxes. In CGAL User and Reference Manual. CGAL Editorial Board.
Liu, F., Harada, T., Lee, Y., and Kim, Y. J. (2010). Real-time collision culling of a million bodies on graphics processing units. ACM TOG, 29(6).
Lo, S.-H., Lee, C.-R., Chung, I.-H., and Chung, Y.-C. (2013). Optimizing pairwise box intersection checking on GPUs for large-scale simulations. ACM Transactions on Modeling and Computer Simulation, 23(3).
Luque, R. G., Comba, J. L. D., and Freitas, C. M. D. S. (2005). Broad-phase collision detection using semi-adjusting BSP-trees. In Proc. of the ACM I3D, pages 179–186.
Oliveira, A. E., Serpa, Yvens R., Serpa, Ygor R., Abreu, A. P., Macedo, D. V., and Rodrigues, M. A. F. (2013). Visualização interativa 3D e simulação de dinâmica de acidentes de trânsito em forense utilizando a Blender Game Engine em um serious game. In Anais do XII SBGames, pages 39–47. SBC.
Rodrigues, M. A. F., Macedo, D. V., Serpa, Yvens R., Martins, C., Candolo, P. H. T., Gobet, T., Serpa, Ygor R., and Secundino, L. (2014). Combatendo a halitose: Um serious game multiplataforma em saúde bucal. In Anais do XIII SBGames, pages 210–219. SBC.
Rodrigues, M. A. F., Macedo, D. V., Serpa, Yvens R., and Serpa, Ygor R.(2015). Beyond fun: an interactive and educational 3D traffic rules game controlled by non-traditional devices. In Proc. of the 30th ACM SAC, pages 239–246.
Serpa, Ygor R. (2017). Algoritmos eficientes e escaláveis para detecção de colisão broad phase em CPU. Monografia de final de curso, Universidade de Fortaleza.
Serpa, Ygor R. and Rodrigues, M. A. F. (2013). Estudo comparativo entre algoritmos para detecção de colisão broadphase em CPU e GPU na Bullet. In Proc. of the 26th SIBGRAPI: Workshop of Undergraduate Works. SBC.
Serpa, Ygor R. and Rodrigues, M. A. F. (2014). Parallelizing broad phase collision detection for animation in games: A performance comparison of CPU and GPU algorithms. In Anais do XIII SBGames, pages 770–779. IEEE.
Serpa, Yvens R., Serpa, Ygor R., and Rodrigues, M. A. F. (2016). A comparative study on a novel drawcall-wise visibility culling and space-partitioning data structures. In Anais do XV SBGames, pages 36–43. 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 Proc. of the IEEE VR, pages 191–198.
