Caixas delimitadoras em octrees

9

Vi que os octrees são frequentemente usados ​​para coisas como seleção de frustum e detecção de colisão em 3D. Mas não tenho certeza de como o algoritmo funciona. Certamente, todo o princípio da octree quebra quando você tenta usar caixas delimitadoras, porque qualquer caixa pode ser armazenada em um nó, mas na verdade se sobrepõe ao espaço representado por outro nó. Além disso, não tenho certeza de como isso pode funcionar para procurar caixas delimitadoras, em vez de pontos, porque, novamente, você pode ficar preso em praticamente todos os nós, derrotando o objetivo.

Então, como os octrees lidam com caixas delimitadoras?

collision-detection algorithm DeadMG
fonte

Respostas:

12

Um Octree (3D) usa os mesmos conceitos que um Quadtree (2D). Se você ler e entender o artigo da Wikipedia sobre Quadtrees, poderá aplicar os mesmos conceitos em 3D.

Essas duas árvores permitem que você use pesquisas com base em área que podem reduzir bastante o número de comparações necessárias para descobrir quais objetos estão em uma determinada área. Isso pode ser útil para visualização, ou mesmo para colisões, dependendo do seu jogo.

O conceito básico é que o espaço do mundo seja dividido em "baldes": quadrados para 2D ou cubos para 3D. Com um mundo vazio, você começa com um único quadrado ou balde de cubos que cobre o mundo inteiro. Ao adicionar objetos ao mundo, você começa no nó raiz e trabalha na árvore com base na localização e tamanho do objeto. Se o intervalo de destino atingir a capacidade, você o subdividirá dividindo quadrados em 4 quadrados menores (Quadtree) ou dividindo cubos em 8 cubos menores (Octree). Cada objeto que você adiciona ao mundo é inserido apenas tão profundamente na árvore, pois pode caber fisicamente completamente dentro dos limites do balde. Se um objeto não couber dentro dos limites do depósito atual, você deve mover o objeto para o menor depósito pai no qual ele se encaixa completamente.

Observe que o uso de um Quadtree ou Octree é um exagero se você não tiver muitos objetos em seu mundo. Existem também soluções de código aberto para ambos.

John McDonald
fonte
Eu acho que ele sabe disso. Acredito que a confusão é sobre como lidar com um volume que não se encaixa perfeitamente em uma subdivisão.
ClassicThunder
2
Mencionei que "se um objeto não se encaixa dentro dos limites, ele deve ser armazenado uma camada acima". E também parecia que o OP estava um pouco confuso sobre como Octrees trabalhava em geral, com base em sua segunda frase.
John McDonald
Isso não viola a restrição fundamental de octrees, de que existem apenas sete ou menos em cada nó?
23912 DeadMG
Quero dizer, se eu tivesse N objetos que se estendiam ao longo do limite, então eu estaria olhando para O (N) cheques para verificar cada um deles.
23412 DeadMG
@DeadMG, "Oct", como em Oito (Octagon, Octane, etc). Quando o nó raiz é dividido, ele terá 8 filhos: Nordeste acima, Nordeste abaixo, NWU, NWD, SEU, SED, SWU e SWD para um total de 9 nós, incluindo. a raiz. Se um desses nós filhos se dividir, esse nó também terá 8 subnós, um para cada quadrante como antes, perfazendo um total de 8 + 8 + 1 = 17 nós. Se todos os seus objetos couberem no limite do nó raiz e não se encaixarem em nenhum dos 8 quadrantes, sim, será O (N) e você terá que verificar todos os objetos e não poderá salvar nenhum. compara, na verdade, provavelmente custará.
22412 John McDonald
3

n-trees são o sistema de particionamento espacial mais famoso, mas não o único . Existem muitos, muitos outros. Um pouco mais de informação sobre os dados que você possui ajudaria bastante a encontrar a melhor opção. Suas caixas mudam de tamanho ou se movimentam? Quão grandes são eles? Quantos existem? Você tem muitas inserções / remoções?

desconhecido
fonte