A área de detecção de colisão é responsável por detectar interseções geométricas e, de forma geral, relações de proximidade entre objetos geométricos. Permeia uma extensa variedade de aplicações, tais como, simulações físicas, planejamento de rotas, controle de agentes, simulação de multidões, entre...

A área de detecção de colisão é responsável por detectar interseções geométricas e, de forma geral, relações de proximidade entre objetos geométricos. Permeia uma extensa variedade de aplicações, tais como, simulações físicas, planejamento de rotas, controle de agentes, simulação de multidões, entre outras, sendo de vital importância para a geração de cenas com objetos interagindo entre si, de forma realista. Estes objetos podem ser uniformemente ou não-uniformemente distribuídos, as cenas podem ser predominantemente estáticas ou completamente dinâmicas, com objetos de tamanhos e formatos similares ou distintos, etc. Para simplificar o processo da detecção de colisão, inicialmente, são considerados apenas os volumes envoltórios das geometrias reais dos objetos, fase conhecida como broad phase, em seguida, são realizados testes mais precisos entre pares de objetos colidentes. Contudo, poucas soluções que refletem o estado-da-arte dedicam-se a resolver o problema, simultaneamente, de forma geral e eficiente (muitas são eficientes apenas no caso estático, ou quando há uma distribuição uniforme de objetos). Este trabalho apresenta duas contribuições principais para a área de detecção broad phase: uma nova solução em CPU, a qual atende simultaneamente aos requisitos de eficiência, escalabilidade e generalidade; e uma metodologia nomeada Broadmark, implementada como um ambiente de software aberto para análise comparativa de algoritmos. Mais especificamente, a nova solução em CPU é um híbrido entre árvores K-dimensionais e os algoritmos Sweep-and-Prune e de detecção de colisão incremental, orquestrado por um eficiente algoritmo idempotente de atualização. Por usa vez, Broadmark engloba um gerador extensível de cenários de colisão e uma ferramenta de execução e análise, que acompanha implementações originais, da academia e indústria, em nível de CPU e GPU, incluindo a nova solução híbrida. Utilizando Broadmark, um estudo comparativo foi realizado, mostrando que os desempenhos das soluções seriais e paralelas são similares, sendo sugestivo de que hardwares paralelos podem ser melhor explorados. Além disso, os resultados mostram que a nova solução híbrida é eficiente, sendo a mais competitiva entre as soluções seriais e, para cenários estáticos, mais eficiente que as soluções em GPU. Adicionalmente, esta provou ser geral e escalável, em cenários coerentes e incoerentes, bem como em distribuições uniformes e não uniformes de objetos. Com estas contribuições, espera-se que a validação de novas soluções possa ser feita de forma muito mais simples, fomentando a criação de soluções mais genéricas e eficientes, para que o problema torne-se cada vez menos sensível às aplicações.

The collision detection field is responsible for detecting geometrical intersections and, in general, proximity relations among geometrical objects. It permeates a wide range of applications, such as, physical simulations, route planning, agent control, crowd simulations and others, being of...

The collision detection field is responsible for detecting geometrical intersections and, in general, proximity relations among geometrical objects. It permeates a wide range of applications, such as, physical simulations, route planning, agent control, crowd simulations and others, being of paramount importance to the generation of scenes with interacting objects, in a realistic way. These objects can be uniformly or non-uniformly distributed, scenes can be mostly static or completely dynamic, with objects of similar or varied sizes and shapes, etc. To simplify the collision detection process, initially, only the bounding volumes of the real objects' geometries are considered, step known as broad phase, following it, more precise tests are performed among colliding object pairs. However, few state-of-the-art solutions are dedicated to solving this problem, simultaneously, in a general and efficient way (several solutions are efficient only on the static case, or when objects are uniformly distributed). This work presents two main contributions to the broad phase detection field: a new CPU solution, which satisfies the efficiency, scalability and generality requirements; and a methodology named Broadmark, implemented as an open software environment for the comparative analysis of algorithms. More specifically, the new CPU solution is a hybrid between KD-trees and the Sweep-and-Prune and incremental collision detection algorithms, being orchestrated by an efficient and idempotent updating algorithm. In turn, Broadmark spans an extensible generator of collision scenarios and an execution and analysis tool, which bundles original, academic and industrial implementations, on CPU and GPU, along with the new hybrid solution. Using Broadmark, a comparative study has been performed, showing that the serial and parallel solutions performances are similar, being suggestive that parallel hardware can be better explored. Additionally, the results show that the new hybrid solution is efficient, being the most competitive among the serial solutions and, in static scenes, more efficient than GPU based solutions. Moreover, the solution proved to be general and scalable, in coherent and incoherent scenes, as well as in uniformly and non-uniformly object distributions. With these contributions, it is expected that the validation of new solutions can be done in a simpler way, supporting the creation of more generic and efficient solutions, so that the problem becomes less and less sensitive to the applications.