Análise de Desempenho de Algoritmos para Detecção de Colisão em Ambientes Gráficos Interativos
Resumo
Ambientes gráficos interativos, contendo um grande número de objetos 3D, necessitam de métodos para detecção de colisão rápidos, precisos e com alta escalabilidade. Este trabalho apresenta uma análise de desempenho detalhada de algoritmos para detecção de colisão broad phase: Força Bruta, Grid, Octree, e Sweep & Prune. O algoritmo de broad phase com melhor desempenho (Sweep & Prune) foi integrado a um algoritmo de narrow phase baseado em Sphere-Trees, compondo um algoritmo híbrido para detecção de colisão. Os resultados obtidos mostram que este algoritmo é rápido, preciso e escalável, portanto, sendo recomendado para aplicações interativas que contêm um grande número de objetos colidentes com geometria complexa.Referências
Bandi, S. e Thalmann, D. (1995). An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies. CGF, 14(3):259–270.
Bergen, G. V. D. (2004). Collision Detection in Interactive 3D Environments. Morgan and Kaufmann Publishers.
Bradshaw, G. (2003). Sphere-Tree Construction Toolkit. [link].
Bradshaw, G. e O’Sullivan, C. (2004). Adaptive Medial-Axis Approximation for Sphere-Tree Construction. ACM Transactions on Graphics, 23(1):1–26.
Cohen, J. D., Lin, M. C., Manocha, D., e Ponamgi, M. K. (1995). I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments. In Proc. of the Symposium on Interactive 3D Graphics, pages 189–196, USA. ACM Press.
Ericson, C. (2005). Real-Time Collision Detection. Morgan and Kaufmann Publishers.
Gottschalk, S., Lin, M. C., e Manocha, D. (1996). OBBTree: A Hierarchical Structure for Rapid Interference Detection. Computer Graphics, 30:171–180.
Hubbard, P. M. (1996). Approximating Polyhedra with Spheres for Time-Critical Collision Detection. ACM Transactions on Graphics, 15(3):179–210.
Klosowski, J. T., Held, M., Mitchell, J. S., Sowizral, H., e Zikan, K. (1998). Efficient Collision Detection using Bounding Volume Hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics, 4(1):21–36.
Lawlor, O. S. e Kalée, L. V. (2002). A Voxel-Based Parallel Collision Detection Algorithm. In Proc. of the 16th International Conference on Supercomputing, pages 285–293, New York, USA. ACM Press.
Luque, R. G., Comba, J. L. D., e Freitas, C. M. D. S. (2005). Broad-Phase Collision Detection using Semi-Adjusting BSP-Trees. In Proc. of the Symposium on Interactive 3D Graphics and Games, pages 179–186. SIGGRAPH, ACM Press.
O’Sullivan, C. e Dingliana, J. (1999). Real-Time Collision Detection and Response Using Sphere-Trees. In Proc. of the 15th Spring Conference on Computer Graphics, pages 83–92, Budmerice, Slovakia.
Redon, S. (2004). Continuous Collision Detection for Rigid and Articulated Bodies. Tutorial. ACM SIGGRAPH Course Notes.
Rocha, R. S. (2006). Avaliação Experimental de Métodos para Detecção de Colisão em Ambientes Gráficos Interativos. Monografia de Final de Curso, Universidade de Fortaleza, UNIFOR.
Rocha, R. S. e Rodrigues, M. A. F. (2005). Ambientes Interativos com Detecção de Colisão Broad Phase Utilizando Grids. In Anais do III Workshop de Iniciação Científica do XVIII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), Natal, RN. Meio digital.
Rocha, R. S. e Rodrigues, M. A. F. (2006a). Detecção de Colisão Broad Phase utilizando Grids para Ambientes Interativos. Revista Eletrônica de Iniciação Científica (REIC), 6(2):1–17.
Rocha, R. S. e Rodrigues, M. A. F. (2006b). Investigating Broad Phase Collision Detection Methods for 3D Scenarios Using Force Feedback Devices. In Proc. of the XXXII Latin-American Conference on Informatics (CLEI), Santiago do Chile, Chile. Meio digital.
Rocha, R. S., Rodrigues, M. A. F., e Taddeo, L. S. (2006). Performance Evaluation of a Hybrid Algorithm for Collision Detection in Crowded Interactive Environments. In Proc. of the XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), pages 86–93, Manaus, AM, Brazil. IEEE CS Press.
Rowe, G. W. (2001). Computer Graphics with Java. Grassroots Series. Palgrave.
Bergen, G. V. D. (2004). Collision Detection in Interactive 3D Environments. Morgan and Kaufmann Publishers.
Bradshaw, G. (2003). Sphere-Tree Construction Toolkit. [link].
Bradshaw, G. e O’Sullivan, C. (2004). Adaptive Medial-Axis Approximation for Sphere-Tree Construction. ACM Transactions on Graphics, 23(1):1–26.
Cohen, J. D., Lin, M. C., Manocha, D., e Ponamgi, M. K. (1995). I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments. In Proc. of the Symposium on Interactive 3D Graphics, pages 189–196, USA. ACM Press.
Ericson, C. (2005). Real-Time Collision Detection. Morgan and Kaufmann Publishers.
Gottschalk, S., Lin, M. C., e Manocha, D. (1996). OBBTree: A Hierarchical Structure for Rapid Interference Detection. Computer Graphics, 30:171–180.
Hubbard, P. M. (1996). Approximating Polyhedra with Spheres for Time-Critical Collision Detection. ACM Transactions on Graphics, 15(3):179–210.
Klosowski, J. T., Held, M., Mitchell, J. S., Sowizral, H., e Zikan, K. (1998). Efficient Collision Detection using Bounding Volume Hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics, 4(1):21–36.
Lawlor, O. S. e Kalée, L. V. (2002). A Voxel-Based Parallel Collision Detection Algorithm. In Proc. of the 16th International Conference on Supercomputing, pages 285–293, New York, USA. ACM Press.
Luque, R. G., Comba, J. L. D., e Freitas, C. M. D. S. (2005). Broad-Phase Collision Detection using Semi-Adjusting BSP-Trees. In Proc. of the Symposium on Interactive 3D Graphics and Games, pages 179–186. SIGGRAPH, ACM Press.
O’Sullivan, C. e Dingliana, J. (1999). Real-Time Collision Detection and Response Using Sphere-Trees. In Proc. of the 15th Spring Conference on Computer Graphics, pages 83–92, Budmerice, Slovakia.
Redon, S. (2004). Continuous Collision Detection for Rigid and Articulated Bodies. Tutorial. ACM SIGGRAPH Course Notes.
Rocha, R. S. (2006). Avaliação Experimental de Métodos para Detecção de Colisão em Ambientes Gráficos Interativos. Monografia de Final de Curso, Universidade de Fortaleza, UNIFOR.
Rocha, R. S. e Rodrigues, M. A. F. (2005). Ambientes Interativos com Detecção de Colisão Broad Phase Utilizando Grids. In Anais do III Workshop de Iniciação Científica do XVIII Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), Natal, RN. Meio digital.
Rocha, R. S. e Rodrigues, M. A. F. (2006a). Detecção de Colisão Broad Phase utilizando Grids para Ambientes Interativos. Revista Eletrônica de Iniciação Científica (REIC), 6(2):1–17.
Rocha, R. S. e Rodrigues, M. A. F. (2006b). Investigating Broad Phase Collision Detection Methods for 3D Scenarios Using Force Feedback Devices. In Proc. of the XXXII Latin-American Conference on Informatics (CLEI), Santiago do Chile, Chile. Meio digital.
Rocha, R. S., Rodrigues, M. A. F., e Taddeo, L. S. (2006). Performance Evaluation of a Hybrid Algorithm for Collision Detection in Crowded Interactive Environments. In Proc. of the XIX Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI), pages 86–93, Manaus, AM, Brazil. IEEE CS Press.
Rowe, G. W. (2001). Computer Graphics with Java. Grassroots Series. Palgrave.
Publicado
30/06/2007
Como Citar
ROCHA, Rafael de Sousa; RODRIGUES, Maria Andréia Formico.
Análise de Desempenho de Algoritmos para Detecção de Colisão em Ambientes Gráficos Interativos. In: CONCURSO DE TRABALHOS DE INICIAÇÃO CIENTÍFICA DA SBC (CTIC-SBC), 26. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1925-1934.
