Octrees, Kd-Trees, BSP só fazem sentido para geometria estática?

7

Ainda estou implementando meu gráfico de cena (veja esta pergunta ). Agora, eu me pergunto se uma representação espacial como uma Kd-Tree ou Octree para fazer o View Frustum Culling (VFC) faz sentido apenas com geometria estática. A razão da minha dúvida é que geralmente a geometria dinâmica é uma pequena parte da cena, enquanto a geometria estática pode ser muito grande, e a geometria dinâmica se força a lidar com atualizações na representação espacial em cada quadro.

Suas opiniões?

Tunnuz

performance scene-graph tunnuz
fonte

Respostas:

9

Geralmente, usei uma árvore de partição separada para objetos estáticos e dinâmicos ou simplesmente a desconsiderei para objetos dinâmicos. Isso fornece os benefícios dos dois mundos:

  • Objetos estáticos não requerem recálculo da árvore em cada quadro
  • Objetos dinâmicos requerem apenas o recálculo de uma árvore mínima

Se desenhar objetos dinâmicos o tempo todo não causa muito impacto no desempenho, às vezes pode ser melhor dispensar o recálculo de uma árvore para cada quadro.

Outra otimização é recalcular apenas a árvore quando os objetos se moverem a uma certa distância ou estiverem viajando a velocidades suficientemente altas; caso contrário, você provavelmente acabará com a mesma árvore a cada quadro de qualquer maneira.

Sean James
fonte
Ótima resposta, eu esperava algo assim. Você costuma usar estruturas de dados diferentes para geometria dinâmica e estática? Existe algum procedimento ad-hoc para fazer com que as duas estruturas se encontrem ao fazer a detecção de colisões entre objetos estáticos e dinâmicos?
tunnuz
2
O uso da mesma estrutura de dados geralmente é mais fácil porque a implementação já está gravada e, portanto, também há menos oportunidades de surgir erros. Às vezes, no entanto, a verificação de esferas limitadas é suficiente para objetos dinâmicos, em comparação com a sobrecarga de construção de uma árvore inteira, especialmente se os objetos estão se movendo muito. Nessa linha, pode ser benéfico escrever um sistema de particionamento menos agressivo para objetos dinâmicos para manter os tempos de cálculo baixos e usar um algoritmo mais agressivo, mas intensivo em cálculos, para objetos estáticos.
Sean James
2
Descobri que as grades funcionam particularmente bem para objetos dinâmicos. Eles são simples e rápidos.
Toad