Библиотека pcl_octree предоставляет эффективные методы построения иерархической древовидной структуры данных на основе данных облака точек. Это позволяет выполнять пространственное разбиение, прореживание и поиск в наборе точек. Каждый узел октодерева имеет либо восемь дочерних узлов, либо ни одного. Корневой узел задаёт кубическую ограничивающую рамку, охватывающую все точки. На каждом уровне дерева это пространство подразделяется вдвое, что приводит к увеличению разрешения вокселей.
Реализация pcl_octree предоставляет эффективные алгоритмы поиска ближайших соседей, такие как «Поиск соседей внутри вокселя», «Поиск K ближайших соседей» и «Поиск соседей в радиусе». Она автоматически подстраивает свои размеры под набор точек. Набор классов листовых узлов предоставляет дополнительные возможности, например проверку пространственной «занятости» и «плотности точек на воксель». Функции сериализации и десериализации позволяют эффективно кодировать структуру октодерева в бинарный формат. Кроме того, реализация пула памяти сокращает количество затратных операций выделения и освобождения памяти в сценариях, где октодеревья требуется создавать с высокой частотой.
На следующем рисунке показаны ограничивающие рамки вокселей узлов октодерева на нижнем уровне дерева. Воксели октодерева окружают каждую трёхмерную точку на поверхности кролика. Красные точки обозначают данные облака точек. Изображение создано с помощью octree_viewer (visualization/tools/octree_viewer).
