Octree
- Também chamado: sparse voxel octree
- Categoria: Sensing › 3D maps & reconstruction
- Tags: mapping, data-structures, 3d-perception, occupancy-mapping, point-clouds
Uma estrutura de dados em árvore que divide recursivamente o espaço 3D em oito cubos, alocando células finas apenas onde há dados, para mapas compactos e consultas espaciais rápidas.
Definição
Octree (árvore octal) é uma árvore em que cada nó representa um cubo de espaço e pode ter até oito filhos, um para cada octante obtido ao dividir o cubo pela metade ao longo dos três eixos. A raiz cobre o volume inteiro; cada nível abaixo divide pela metade o tamanho da célula. Os ramos só são subdivididos onde há algo de interesse, como pontos de superfície medidos, de modo que grandes regiões vazias ou não observadas permanecem como nós grosseiros únicos. As octrees foram descritas para modelagem de sólidos por Donald Meagher no início dos anos 1980 e hoje são padrão em computação gráfica, processamento de nuvens de pontos e mapeamento robótico.
O principal atrativo é a memória. Uma grade de voxels densa em resolução fina sobre um grande edifício precisa de armazenamento para cada célula, enquanto o armazenamento de uma octree cresce aproximadamente com a área de superfície observada. Ela também oferece acesso em múltiplas resoluções: um planejador pode consultar células grosseiras para uma verificação rápida e descer para obter detalhes. No OctoMap, uma biblioteca muito usada de Hornung e colegas, cada folha guarda um valor de ocupação probabilístico na forma de log-odds, atualizado a partir de medições de distância, de modo que o mapa distingue espaço ocupado, livre e desconhecido. Filhos com o mesmo estado são podados de volta para o pai para economizar memória.
As octrees trocam um pouco de velocidade por essa compacidade: chegar a uma folha significa percorrer a árvore para baixo, o que é mais lento que indexar um array plano. Alternativas como voxel hashing e a estrutura VDB oferecem acesso mais rápido em algumas cargas de trabalho. As octrees também são usadas para acelerar a busca de vizinhos mais próximos e a verificação de colisões em nuvens de pontos e, em sistemas recentes de mapeamento neural, organizam voxels esparsos que armazenam features aprendidas, crescendo de forma incremental à medida que chegam novos quadros de profundidade.
Por que importa
Os robôs precisam de mapas 3D que cubram grandes áreas com resolução útil sem esgotar a memória. As octrees tornam isso viável, e são a base de ferramentas comuns de mapeamento de ocupação e de verificação de colisões usadas em manipulação e navegação aérea.
Principais aplicações
- Mapeamento probabilístico de ocupação 3D com OctoMap
- Verificação de colisões para braços robóticos e drones
- Busca de vizinhos mais próximos e por raio em nuvens de pontos
- Estruturas de voxels esparsos para mapeamento implícito neural e denso
- Compressão de nuvens de pontos e renderização por níveis de detalhe
Na prática
Uma equipe que constrói um mapa 3D para um drone que voa por um armazém alimenta o OctoMap com nuvens de pontos de uma câmera de profundidade ou de um lidar, com as poses da sua odometria, a uma resolução de alguns centímetros. Cada raio marca as células que atravessa como mais provavelmente livres e a célula em que termina como mais provavelmente ocupada. O planejador consulta a ocupação na octree ao longo dos caminhos candidatos, tratando o espaço desconhecido como obstáculo. Em um braço robótico, o MoveIt pode receber o mesmo tipo de octree a partir de um sensor de profundidade para manter atualizada a cena de planejamento do braço. Os engenheiros ajustam a resolução, o alcance do sensor e as probabilidades de acerto e de erro para equilibrar detalhe, memória e a rapidez com que objetos em movimento são apagados.
Equívocos comuns
- Uma octree é o mesmo que uma grade de voxels — uma grade de voxels armazena cada célula, enquanto uma octree só subdivide onde é preciso e funde regiões uniformes
- Octrees são sempre mais rápidas que grades planas — elas economizam memória, mas cada consulta percorre a árvore, então grades densas ou com hashing podem ser mais rápidas para algumas consultas
- Espaço vazio em uma octree significa espaço livre — em octrees de ocupação, o espaço não observado é desconhecido, e os planejadores geralmente devem tratá-lo de forma diferente do espaço livre
Quem deve saber
- Engenheiros de mapeamento e de SLAM
- Desenvolvedores de planejamento de movimento e de verificação de colisões
- Engenheiros de autonomia de drones que trabalham em ambientes 3D
- Desenvolvedores de sistemas de mapeamento neural e denso
Tecnologias relacionadas
- OctoMap
- Voxel hashing (Voxel Hashing)
- OpenVDB
- Point Cloud Library (PCL)
- MoveIt
Termos relacionados
Projetos relacionados
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- OpenDroneMap: Open-source photogrammetry toolkit that turns drone images into maps and 3D models
- RTAB-Map: Versatile graph-based SLAM supporting RGB-D, stereo, and LiDAR with real-time operation
- LeGO-LOAM: Classic lightweight, ground-optimized lidar odometry and mapping baseline (IROS 2018)
- GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST
Vídeos
- Using Octrees and A* for Efficient Pathfinding: git-amend