Detecção de Colisão Broad Phase com RAY KD-Tree: Uma Abordagem Eficiente e Adaptativa
Resumo
Vários algoritmos rápidos para a detecção de colisão Broad Phase têm sido propostos, mas poucos deles possuem aplicabilidade diversificada sendo, na maioria das vezes, limitados a uma pequena classe de cenários e/ou de difícil configuração. Neste trabalho, descrevemos RAY KD-Tree, uma nova solução baseada no uso de árvores k-dimensionais para uma execução eficiente, genérica e facilmente configurável, a qual é capaz de adaptar-se automaticamente aos cenários de teste e à dinâmica dos seus objetos.
Referências
Bergen, G.V.D. (2004), “Collision Detection in Interactive 3D Environments”. Morganand Kaufmann Publishers.
Cohen, J.D. e Lin, M.C. (1995) “I-Collide: An Interactive and Exact Collision DetectionSystem for Large-Scale Environments”, In Proc. of I3D’95, pages 189-ff, New York.
Coumans, E. (2008). “btDBVT Documentation”..
Coumans, E. (2015) “Bullet Physics Library”. Disponível em:. Último acesso em: 24/04/2015.
Coutinho, M. G. (2001) “Dynamic Simulations of Multibody Systems”. Los Angeles, CA: Springer-Verlag.
He, L., Ortiz, R., Enquobahrie, A., e Manocha, D. (2015). “Interactive Continuous Collision Detection for Topology Changing Models Using Dynamic Clustering”. In Proc. of the I3D’15, pages 47–54, NY, USA, ACM.
Kettner, L., Meyer, A., Zomorodian, A. (2015). “Intersecting Sequences of dD Isooriented Boxes”. In CGAL User and Reference Manual. CGAL Edit. Board, 4.6 Ed.
Liu, F., Harada, T., Lee, Y., Kim Y. J. (2010). “Real-time Collision Culling of a Million Bodies on Graphics Processing Units”. ACM TOG, 29(6), p. 154:1-154:8.
Lo, S. –H., Lee, C.-R., Chung. I.-H., e Chung. Y.-C. (2013). “Optimizing Pair-Wise Box Intersections Checking on GPUs for Large-scale Simulations”. ACM TOMACS, 23(3), p. 19:1-19:22, ACM Press, NY, USA.
Mirtich, B. (1997) “Efficient Algorithms for Two-Phase Collision Detection”, Technical Report, December.
Oliveira, A.E.; Serpa, Yvens. R.; Serpa, Ygor, R.; Abreu, A.P.; Macedo, D.V.; 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”. Em Anais do SBGames’13, Arte & Design, SP, p. 244-252.
Rocha, R.S. (2010) “Algoritmos Rápidos de Detecção de Colisão Broad Phase Utilizando KD-Trees”. Dissertação de Mestrado, Pós-Graduação em Informática Aplicada (PPGIA), Universidade de Fortaleza (UNIFOR), Fortaleza-CE.
Rodrigues, M.A.F.; Macedo, D.V.; Serpa, Yvens. R.; Martins, C.; Candolo, P.H.T.; Gobet, T.; Serpa, Ygor, R.; Secundino, L. (2014). “Combatendo a Halitose: Um Serious Game Multiplataforma em Saúde Bucal”. Em Anais do SBGames’14, Arte & Design, RGS, p. 210-219.
Rodrigues, M.A.F.; Macedo, D.V.; Serpa, Ygor, R.; Serpa, Yvens. R. (2015). “Beyond Fun: An Interactive and Educational 3D Traffic Rules Game Controlled by Nontraditional Devices”. In Proc. of the ACM SAC’15, Salamanca, Spain, v. 1, p. 1-8.
Serpa, Ygor, R.; Rodrigues, M.A.F. (2013) “Estudo Comparativo entre Algoritmos para Detecção de Colisão Broadphase em CPU e GPU na Bullet”. Em Anais do Workshop of Undergraduate Works (WUW) do SIBGRAPI’13, Arequipa, Peru, p. 1-6.
Serpa, Ygor, R.; Rodrigues, M.A.F. (2014). “Parallelizing Broad Phase Collision Detection for Animation in Games: A Performance Comparison of CPU and GPU Algorithms”. In Proc. of the SBGames’14, Computação, RGS, p. 770-779.
Zomorodian. A., Edelsbrunner, H. (2000). “Fast Software for Box Intersections”. In Proc. of the SCG’00. ACM Press, p. 129-138, NY, USA.
Cohen, J.D. e Lin, M.C. (1995) “I-Collide: An Interactive and Exact Collision DetectionSystem for Large-Scale Environments”, In Proc. of I3D’95, pages 189-ff, New York.
Coumans, E. (2008). “btDBVT Documentation”.
Coumans, E. (2015) “Bullet Physics Library”. Disponível em:
Coutinho, M. G. (2001) “Dynamic Simulations of Multibody Systems”. Los Angeles, CA: Springer-Verlag.
He, L., Ortiz, R., Enquobahrie, A., e Manocha, D. (2015). “Interactive Continuous Collision Detection for Topology Changing Models Using Dynamic Clustering”. In Proc. of the I3D’15, pages 47–54, NY, USA, ACM.
Kettner, L., Meyer, A., Zomorodian, A. (2015). “Intersecting Sequences of dD Isooriented Boxes”. In CGAL User and Reference Manual. CGAL Edit. Board, 4.6 Ed.
Liu, F., Harada, T., Lee, Y., Kim Y. J. (2010). “Real-time Collision Culling of a Million Bodies on Graphics Processing Units”. ACM TOG, 29(6), p. 154:1-154:8.
Lo, S. –H., Lee, C.-R., Chung. I.-H., e Chung. Y.-C. (2013). “Optimizing Pair-Wise Box Intersections Checking on GPUs for Large-scale Simulations”. ACM TOMACS, 23(3), p. 19:1-19:22, ACM Press, NY, USA.
Mirtich, B. (1997) “Efficient Algorithms for Two-Phase Collision Detection”, Technical Report, December.
Oliveira, A.E.; Serpa, Yvens. R.; Serpa, Ygor, R.; Abreu, A.P.; Macedo, D.V.; 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”. Em Anais do SBGames’13, Arte & Design, SP, p. 244-252.
Rocha, R.S. (2010) “Algoritmos Rápidos de Detecção de Colisão Broad Phase Utilizando KD-Trees”. Dissertação de Mestrado, Pós-Graduação em Informática Aplicada (PPGIA), Universidade de Fortaleza (UNIFOR), Fortaleza-CE.
Rodrigues, M.A.F.; Macedo, D.V.; Serpa, Yvens. R.; Martins, C.; Candolo, P.H.T.; Gobet, T.; Serpa, Ygor, R.; Secundino, L. (2014). “Combatendo a Halitose: Um Serious Game Multiplataforma em Saúde Bucal”. Em Anais do SBGames’14, Arte & Design, RGS, p. 210-219.
Rodrigues, M.A.F.; Macedo, D.V.; Serpa, Ygor, R.; Serpa, Yvens. R. (2015). “Beyond Fun: An Interactive and Educational 3D Traffic Rules Game Controlled by Nontraditional Devices”. In Proc. of the ACM SAC’15, Salamanca, Spain, v. 1, p. 1-8.
Serpa, Ygor, R.; Rodrigues, M.A.F. (2013) “Estudo Comparativo entre Algoritmos para Detecção de Colisão Broadphase em CPU e GPU na Bullet”. Em Anais do Workshop of Undergraduate Works (WUW) do SIBGRAPI’13, Arequipa, Peru, p. 1-6.
Serpa, Ygor, R.; Rodrigues, M.A.F. (2014). “Parallelizing Broad Phase Collision Detection for Animation in Games: A Performance Comparison of CPU and GPU Algorithms”. In Proc. of the SBGames’14, Computação, RGS, p. 770-779.
Zomorodian. A., Edelsbrunner, H. (2000). “Fast Software for Box Intersections”. In Proc. of the SCG’00. ACM Press, p. 129-138, NY, USA.
Publicado
20/07/2015
Como Citar
SERPA, Ygor; RODRIGUES, Maria Andréia.
Detecção de Colisão Broad Phase com RAY KD-Tree: Uma Abordagem Eficiente e Adaptativa. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 34. , 2015, Recife.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2015
.
p. 81-90.
