Gostaria de ser capaz de renderizar uma grande população de pequenos objetos que se movem de forma independente em tempo real. Eles podem se mover como um enxame, mas suas posições relativas não serão coerentes – sua posição pode mudar arbitrariamente dentro de um enxame e os enxames podem se dividir e se reformar a qualquer momento.
Qual abordagem para construir uma hierarquia de volume delimitadora seria mais adequada para essa situação? uma maneira de manter uma hierarquia subótima, mas boa o suficiente, que requer apenas uma atualização parcial de cada quadro? Ou existe uma maneira de construir uma hierarquia a partir do zero para cada quadro que seja rápida o suficiente para uma animação suave?
O número de objetos será muito grande para renderizar sem uma hierarquia, mas pelo mesmo motivo, espero que construir a hierarquia seja demorado.
Seguindo o comentário de John Calsbeek, se meu o foco nas hierarquias de volume delimitador está equivocado, e há uma abordagem melhor de particionamento de espaço para esta situação, por favor responda de acordo. Estou procurando algo que possa lidar com o que descrevo, incluindo qualquer coisa que não tenha pensado.
Comentários
- Você está restringindo intencionalmente a questão das hierarquias de volume limitantes ou você está aberto a outras formas de particionamento espacial?
- @JohnCalsbeek I ‘ editei para esclarecer – obrigado por apontar meu restrição inadvertida.
- Considere tratar um ” enxame ” como uma única unidade, quando os enxames se fundem; fundi-los em um único enxame, quando um solitário vagueia para longe, ele se torna um ” enxame ” de um. Isso funciona melhor se os enxames tendem a ser coesos e os solitários tendem a ser raros. Há muitas maneiras interessantes de brincar com o ” enxame é uma única unidade “, como permitir que os membros mudem de enxame apenas quando estão em contato uns com os outros, a lista continua indefinidamente.
Resposta
Considere o uso de hashing espacial, especialmente se seus objetos têm tamanhos semelhantes.
Basicamente, divida seu mundo em células de grade de tamanhos uniformes (2D e 3D são possibilidades válidas dependendo da quantidade de movimento vertical). A cada atualização, atribua seu objeto a cada compartimento sobreposto – se as células forem decentemente dimensionadas em relação aos objetos, a maioria dos objetos deve terminar em um único compartimento.
Cada compartimento é inserido em uma tabela hash, com a chave sendo as coordenadas da caixa. (Você também pode pensar nisso como uma tabela hash com vários valores para a mesma chave e inserir um objeto uma vez para cada célula que se sobrepõe.)
Não há hierarquia a ser reconstruída neste esquema, o que o torna adequado para cenas dinâmicas. Você ainda pode testar as dimensões da célula contra o tronco ou contra oclusores em um nível grosseiro e descartar muitos objetos de uma vez. Além disso, é mais fácil gerenciar essa estrutura de forma incremental – você pode manter a tabela hash igual quadro a quadro e apenas mover objetos de um compartimento para outro quando eles cruzarem os limites de uma célula.
Resposta
Você pode tentar simplesmente tornar os volumes delimitadores um pouco maiores do que o necessário para que os objetos não cruzem seus limites em cada movimento, mas, novamente, você teria que reconstruir a estrutura de vez em quando, de qualquer maneira.
Ou, há Hierarquia de intervalo delimitador que tenta abordar precisamente isso cenário.
Ou o artigo de Ingo Wald, Solomon Boulos e Peter Shirley intitulado Ray Tracing Deformable Scenes Using Dynamic Bounding Volume Hierarchies pode ser de interesse.
Resposta
Eu gostaria de adicionar alguma perspectiva prática para isso.
Vamos prefácio que estou operando com informações limitadas aqui:
- Não sei como quaisquer objetos com os quais você está lidando.
- Não sei exatamente para que serve a sua estrutura de aceleração. Abate de Frustum? Rastreamento de raio? Detecção de colisão entre objetos no BVH?
Daqui para frente, vou assumir que você está falando sobre o frustum abatendo alguns milhares de objetos.
O número de objetos será muito grande para renderizar sem uma hierarquia, mas pelo mesmo motivo, espero que construir a hierarquia seja demorado.
Eu diria que se você tiver que visitar todos os objetos em cada quadro para calcular um BVH, selecioná-los diretamente e sem um BVH é realmente mais rápido. Claro que isso depende de sua implementação de seleção de frustum. Os volumes delimitadores de todos os objetos devem ser armazenados de forma contígua na memória. Isso resulta em uma utilização mais eficiente do cache da CPU e permite uma otimização adicional usando instruções SIMD. A DICE tem uma apresentação completa sobre este assunto: Eliminando o campo de batalha: Design orientado a dados na prática
A apresentação também menciona acelerar ainda mais a seleção, usando uma grade simples.
Uma vez que suponho que a maioria das bases de código 3D / simulação / jogo já tenha algum tipo de Classe BVH e eu não sei o quão crítico é para você obter o MELHOR desempenho de seleção, gostaria de apresentar alguns argumentos para manter um BVH:
Dependendo do método que você usa, construindo um BVH pode ser rápido e simples.
Minha implementação atual de um BVH binário (cada nó pode ter apenas zero ou dois filhos e cada nó folha armazena apenas um item) que é projetado para a construção leva cerca de 0,18 ms para 1137 objetos em um único encadeamento de um i7-5960X a 3,89 GHz . Tenho certeza de que pode ser mais rápido. A construção é realizada sem realocar a memória no processo (isso dobrou o desempenho da construção).
Embora o SAH possa gerar o melhor BVH, leva muito tempo. O SAH é bom para coisas que você pode pré-calcular, como malhas de colisão. Em tempo de execução, você pode colocar as malhas de colisão em um BVH que seja mais adequado para construção em tempo real.
Uma abordagem de construção de BVH rápida e simples (aquela que eu “m usando atualmente) é classificar todos os objetos em um eixo (por exemplo, o eixo mais longo do AABB pai) e dividir a coleção no meio.
Para acelerar ainda mais as coisas, calcule os AABBs do nó DEPOIS de construir a árvore, combinando os dois AABBs do nó filho de um nó pai. Isso evita a iteração por todos os objetos (outro aumento de 2x). No entanto, isso só é possível se seu critério de divisão não depender do AABB do pai.