Hierarquia de volume delimitador - Bounding volume hierarchy

Um exemplo de hierarquia de volume delimitador usando retângulos como volumes delimitadores.

Uma hierarquia de volume delimitador ( BVH ) é uma estrutura de árvore em um conjunto de objetos geométricos . Todos os objetos geométricos são embalados em volumes delimitadores que formam os nós de folha da árvore. Esses nós são então agrupados como pequenos conjuntos e incluídos em volumes delimitadores maiores. Estes, por sua vez, também são agrupados e incluídos em outros volumes delimitadores maiores de maneira recursiva, resultando eventualmente em uma estrutura de árvore com um único volume delimitador no topo da árvore. Hierarquias de volume delimitador são usadas para oferecer suporte a várias operações em conjuntos de objetos geométricos de forma eficiente, como detecção de colisão e traçado de raio .

Embora envolver objetos em volumes delimitadores e realizar testes de colisão neles antes de testar a própria geometria do objeto simplifique os testes e possa resultar em melhorias de desempenho significativas, o mesmo número de testes de pares entre volumes delimitadores ainda está sendo executado. Organizando os volumes delimitadores em uma hierarquia de volume delimitador, a complexidade do tempo (o número de testes realizados) pode ser reduzida a logarítmico no número de objetos. Com essa hierarquia em vigor, durante o teste de colisão, os volumes-filho não precisam ser examinados se seus volumes-pai não forem interceptados (por exemplo, se os volumes delimitadores de dois carrinhos de choque não se interceptarem, os volumes delimitadores dos próprios para-choques seriam não tem que ser verificado para colisão).

Problemas de design do BVH

A escolha do volume limite é determinada por uma compensação entre dois objetivos. Por um lado, gostaríamos de usar volumes delimitadores que têm uma forma muito simples. Portanto, precisamos apenas de alguns bytes para armazená-los, e os testes de interseção e cálculos de distância são simples e rápidos. Por outro lado, gostaríamos de ter volumes delimitadores que se ajustassem muito bem aos objetos de dados correspondentes. Um dos volumes delimitadores mais comumente usados ​​é uma caixa delimitadora mínima alinhada ao eixo . A caixa delimitadora mínima alinhada ao eixo para um determinado conjunto de objetos de dados é fácil de calcular, precisa de apenas alguns bytes de armazenamento e testes de interseção robustos são fáceis de implementar e extremamente rápidos.

Existem várias propriedades desejadas para um BVH que devem ser levadas em consideração ao projetar um para uma aplicação específica:

  • Os nós contidos em qualquer subárvore devem estar próximos uns dos outros. Quanto mais baixo na árvore, mais próximos os nós devem estar uns dos outros.
  • Cada nó no BVH deve ter o volume mínimo.
  • A soma de todos os volumes delimitadores deve ser mínima.
  • Maior atenção deve ser dada aos nós próximos à raiz do BVH. A poda de um nó próximo à raiz da árvore remove mais objetos de consideração posterior.
  • O volume de sobreposição de nós irmãos deve ser mínimo.
  • O BVH deve ser balanceado com relação à estrutura do nó e ao seu conteúdo. O balanceamento permite que o máximo possível do BVH seja podado sempre que um galho não for atravessado.

Em termos da estrutura do BVH, deve-se decidir em que grau (o número de filhos) e altura usar na árvore que representa o BVH. Uma árvore de baixo grau terá maior altura. Isso aumenta o tempo de passagem da raiz para a folha. Por outro lado, menos trabalho deve ser despendido em cada nó visitado para verificar se há sobreposição em seus filhos. O oposto é válido para uma árvore de alto grau: embora a árvore seja de altura menor, mais trabalho é gasto em cada nó. Na prática, as árvores binárias (grau = 2) são de longe as mais comuns. Um dos principais motivos é que as árvores binárias são mais fáceis de construir.

Construção

Existem três categorias principais de métodos de construção de árvore: métodos de cima para baixo, de baixo para cima e de inserção.

Os métodos top-down continuam particionando o conjunto de entrada em dois (ou mais) subconjuntos, limitando-os no volume delimitador escolhido e, em seguida, mantendo o particionamento (e delimitação) recursivamente até que cada subconjunto consista em apenas um único primitivo (nós folha são alcançados). Os métodos top-down são fáceis de implementar, rápidos de construir e de longe os mais populares, mas não resultam nas melhores árvores possíveis em geral.

Os métodos bottom-up começam com a entrada definida como as folhas da árvore e, em seguida, agrupam dois (ou mais) deles para formar um novo nó (interno), proceda da mesma maneira até que tudo tenha sido agrupado em um único nó (o raiz da árvore). Os métodos ascendentes são mais difíceis de implementar, mas provavelmente produzirão árvores melhores em geral. Alguns estudos recentes (por exemplo) indicam que em espaço de baixa dimensão, a velocidade de construção pode ser amplamente melhorada (o que corresponde ou supera as abordagens de cima para baixo) classificando objetos usando a curva de preenchimento de espaço e aplicando agrupamento aproximado com base nesta ordem sequencial.

Os métodos top-down e bottom-up são considerados métodos off-line , pois ambos exigem que todas as primitivas estejam disponíveis antes do início da construção. Os métodos de inserção constroem a árvore inserindo um objeto por vez, começando em uma árvore vazia. O local de inserção deve ser escolhido de forma que a árvore cresça o menos possível de acordo com uma métrica de custo. Os métodos de inserção são considerados métodos on-line, pois não exigem que todas as primitivas estejam disponíveis antes do início da construção e, portanto, permitem que as atualizações sejam realizadas no tempo de execução.

Uso

Os BVHs são frequentemente usados ​​no traçado de raio para eliminar candidatos potenciais de interseção dentro de uma cena, omitindo objetos geométricos localizados em volumes delimitadores que não são interceptados pelo raio atual. Além disso, como otimização de desempenho comum, quando apenas a interseção mais próxima do raio é de interesse, como o algoritmo de travessia de traçado de raio é nós descendentes e vários nós filhos estão cruzando o raio, o algoritmo de travessia considerará o volume mais próximo primeiro, e se encontrar interseção lá, que é definitivamente mais próxima do que qualquer interseção possível no segundo (ou outro) volume (ou seja, os volumes não são sobrepostos), ele pode ignorar com segurança o segundo volume. Otimizações semelhantes durante a travessia de BVH podem ser empregadas ao descer para os volumes filho do segundo volume, para restringir o espaço de pesquisa adicional e, assim, reduzir o tempo de travessia.

Além disso, muitos métodos especializados foram desenvolvidos para BVHs, especialmente aqueles baseados em AABB (caixas delimitadoras alinhadas ao eixo), como construção paralela, travessia acelerada SIMD , boas heurísticas de divisão (SAH - heurística de área de superfície é frequentemente usada em traçado de raio), árvores largas (árvores 4 e 16 árias fornecem alguns benefícios de desempenho, tanto no desempenho de construção quanto no desempenho de consulta para cenas práticas) e atualização rápida da estrutura (em aplicativos em tempo real, os objetos podem estar se movendo ou deformando espacialmente de forma relativamente lenta ou estar parados, e mesmo BVH pode ser atualizado para ser ainda válido sem fazer uma reconstrução completa do zero).

Os BVHs também suportam naturalmente a inserção e remoção de objetos sem reconstrução completa, mas com o BVH resultante tendo geralmente um desempenho de consulta pior em comparação com a reconstrução completa. Para resolver esses problemas (bem como a atualização rápida da estrutura ser subótima), o novo BVH pode ser construído de forma assíncrona em paralelo ou de forma síncrona, após a detecção de mudança suficiente (a sobreposição de folhas é grande, o número de inserções e remoções ultrapassou o limite e outras heurísticas mais refinadas).

Os BVHs também podem ser combinados com métodos de gráfico de cena e instanciação de geometria , para reduzir o uso de memória, melhorar a atualização da estrutura e o desempenho de reconstrução total, bem como orientar melhor o objeto ou divisão primitiva.

Veja também

Referências

links externos