Pantheon Repositório Institucional da UFRJ
Coleta, preserva e divulga a produção acadêmica digital em todas as áreas do conhecimento.
São os ativos do repositório, além de teses e dissertações da UFRJ, artigos científicos, livros eletrônicos, capítulos de livros e trabalhos apresentados em eventos por professores, pesquisadores, funcionários administrativos e alunos de mestrado e doutorado.
Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/11422/23858| Tipo: | Trabalho de conclusão de graduação |
| Título: | Algoritmo Gilbert-Johnson-Keerthi: suas melhorias e modificações |
| Autor(es)/Inventor(es): | Jales, Luís Fernando Garcia |
| Orientador: | Sá, Vinícius Gusmão Pereira de |
| Resumo: | Algoritmos de detecção de colisão são muito importantes em várias áreas, tais como robótica, física computacional, computação gráfica, e outras. Ao longo do tempo, o número de vértices de modelos tridimensionais vem aumentando cada vez mais. Isso acaba demandando algoritmos cada vez mais rápidos em detecção de colisão de fase estreita. Um dos algoritmos mais versáteis e rápidos para isso é o algoritmo Gilbert-Johnson-Keerthi, ou simplesmente GJK, que é um algoritmo famoso para computar a distância entre dois politopos convexos. O objetivo principal desse trabalho é revisar o artigo original do algoritmo GJK, apresentando uma descrição completa e a prova de sua corretude (e que o algoritmo sempre termina). Como esse algoritmo depende de um subalgoritmo de distância, uma descrição completa do subalgoritmo de distância de Johnson e uma revisão da prova de sua corretude e que o algoritmo sempre termina também estão inclusos aqui. Ademais, esse trabalho também apresenta uma descrição completa de uma melhoria que usa hill climbing para alcançar uma complexidade de tempo quase constante e uma modificação para computar um eixo de separação, além de mencionar brevemente outras modificações: a primeira serve para resolver detecção de colisão contínua; a outra é o Algoritmo da Expansão de Politopo, ou simplesmente EPA, para computar a profundidade de penetração. |
| Palavras-chave: | Detecção de colisão Algoritmo Collision detection Algorithm |
| Assunto CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
| Unidade produtora: | Instituto de Computação |
| Editora: | Universidade Federal do Rio de Janeiro |
| Data de publicação: | 23-Ago-2024 |
| País de publicação: | Brasil |
| Idioma da publicação: | por |
| Tipo de acesso: | Acesso Aberto |
| Aparece nas coleções: | Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| LFGJales.pdf | 488.74 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.