Construção adaptativa de árvores de volumes envolventes em gpu

A criação em GPU de estruturas em árvore coloca diversos obstáculos ao nível do aproveitamento eficaz dos recursos computacionais disponíveis, em grande parte devido ao facto do trabalho ter características muito dispares nos diversos níveis da hierarquia.Neste trabalho propomos uma abordagem dirigida para três tipos distintos de nós: grandes, pequenos e intermédios. Esta classificação está relacionada com o número de elementos a processar para gerar cada nó e garante uma boa taxa de ocupação dos núcleos nos diversos níveis da hierarquia, recorrendo a kernels específicos para cada tipo de nó. Embora a proposta possa ser aplicável à construção, de cima para baixo, de árvores onde os nós resultam dum processo de redução aplicado a um conjunto de elementos, o caso de estudo é o da deteção de colisões num simulador de superfícies deformáveis, com recurso a hierarquias de volumes envolventes (BVHs).Os volumes envolventes usados são \textit{k}--DOPs, por serem os mais adequados no contexto de superfícies deformáveis, mas as soluções apresentadas permanecem válidas para outros tipos de volumes tais como Oriented Bounding Boxes (OBB), Axis Aligned Bounding Boxes (AABB) ou Bounding Spheres (BS).Para além da demonstração da eficácia da solução proposta na redução dos tempos de construção da hierarquia, apresentamos ainda um estudo comparativo da nossa solução face a uma implementação sequencial no CPU, ilustrando o enorme ganho de desempenho na utilização de GPUs.