Octree

Uma octree (do latim octo 'oito' e árvore do inglês 'árvore' ) é uma estrutura de dados em ciência da computação . Uma octree é uma árvore enraizada cujos nós cada um tem oito descendentes diretos ou nenhum descendente.

Octrees são usados ​​principalmente em computação gráfica para subdividir hierarquicamente conjuntos de dados tridimensionais. A raiz representa todos os dados, todos os outros nós representam um octante dos dados de seu predecessor direto. Isso os torna adequados para implementar a estratégia de dividir para conquistar .

Octrees podem ser vistos como extensões de árvores binárias e quadtrees : árvores binárias subdividem dados unidimensionais, quadtrees bidimensionais e octrees tridimensionais; Ocasionalmente, uma generalização para dados de qualquer dimensão é chamada de N-Tree . Uma versão mais generalizada, onde as dimensões não são fixas, é a B-tree .

usar

Esquema de uma octree. À esquerda, a subdivisão do volume em forma de cubo, à direita a octree resultante.

O exemplo a seguir ilustra o uso mais comum de uma octree, ou seja, para a estrutura uniforme de um espaço de dados em forma de cubo: A raiz representa o cubo inteiro. O cubo é dividido em oito cubos menores - os octantes - e cada sucessor da raiz representa um deles. Cada um desses cubos menores é, por sua vez, cortado em oito cubos ainda menores e assim por diante. A subdivisão de um cubo parcial termina quando nenhuma divisão adicional é possível ou desnecessária.

O volume original não precisa ser em forma de cubo, mas também pode ser geralmente cubóide. Também é possível dividir os volumes em partes desiguais. Como regra, informações adicionais sobre os nós subordinados são armazenadas nos nós. Portanto, contém z. Por exemplo, cada nó da forma especial min-max-octree tem o mínimo e o máximo da subárvore a seguir, o que permite pesquisas eficientes.

Outras áreas de aplicação

As áreas gerais de aplicação para octrees são:

• Representação de imagem
• Indexação espacial (por exemplo, em sistemas de informação geográfica )
• Agrupamento de partículas em dinâmica molecular / simulações DEM
• Remoção de superfície oculta de dados do terreno
• Detecção de colisão em jogos de computador 3D
• Splatting hierárquico
• Resolução adaptativa de equações diferenciais, e. B. corpos deformáveis
• Estimativa de estado

Formulários especiais

Vazio-Não-Vazio-Octree

O valor vazio ou não vazio é armazenado em cada nó em uma octree vazia-não-vazia . Vazio indica que o volume de dados representado pelo nó não contém nenhum dado que valha a pena ser processado; não vazio indica que o volume de dados associado deve ser processado. Normalmente, vazio também é o critério de encerramento para a subdivisão; Como o volume de dados associado não contém mais nenhuma informação interessante, também não vale a pena subdividi-lo mais.

Min-Max-Octree

Esquema de uma octree min-max. Cada nó contém o mínimo (parte superior) e o máximo (parte inferior) de sua subárvore. Ao pesquisar o valor 3, apenas os volumes de dados dos nós marcados em amarelo precisam ser pesquisados.

Em um min-max-octree, o mínimo e o máximo da subárvore do nó são armazenados em cada nó. Min-Max-Octrees são, portanto, adequados para pesquisas eficientes com base no exemplo de árvores binárias. A subárvore de um nó só é pesquisada se o valor pesquisado estiver entre o mínimo e o máximo do nó. Desta forma, partes da árvore podem ser deixadas de fora e a busca pode ser acelerada.

Para o caso especial em que o mínimo e o máximo são iguais em um nó, a pesquisa na subárvore também pode ser deixada de fora, porque toda a subárvore do nó contém o valor que você está procurando. Normalmente, o caso de mínimo igual a máximo também é o critério de encerramento para a subdivisão, ou seja, o volume de dados associado não é subdividido posteriormente.

Por exemplo, octrees mín-máx são usados ​​em gráficos de volume para acelerar o algoritmo do cubo em marcha . Aqui, todos os sub-cubos da octree são pesquisados ​​que contêm um determinado valor de limite. Este valor limite é uma densidade de material para a qual uma isosuperfície deve ser extraída dos dados de voxel.

Campos tensores

Do ponto de vista matemático, octrees são particularmente adequados para estruturar campos de tensores . Uma grade voxel com valores cinza, por exemplo, é um campo tensor de ordem zero como um campo escalar , uma grade voxel com três valores de cores de acordo com o esquema RGB e um componente alfa é um campo tensor de primeira ordem como um campo vetorial .

Links da web

Evidência individual

1. ↑ Martin Seiler et al., A Threefold Representation for the Adaptive Simulation of Embedded Deformble Objects in Contact , Journal of WSCG, Pilsen, Czech Republic, February, 2010.
2. ↑ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edimburgo, Reino Unido, julho de 2010. (PDF; 3.2 MB)