We're not done with point clouds

We're not done with point clouds

Clayton Ramsey - 2026-08-10

If you wait long enough to solve a problem, someone else might just solve it for you.<br>At least that’s what I tell myself about the dishes in my sink.

While in Vienna for a conference, I found another set of researchers who did just that for me: they took some work I had published two years ago and ran with it, and they beat me on just about every benchmark.<br>I’m writing up this article to draw some attention to their work and, a little selfishly, to yap about the things I learned while reimplementing their work.<br>In short, they made a data structure for collision-checking against point clouds that runs really fast while also being extremely cheap in memory and construction time.

If you don’t care about details, you can jump straight to the paper or to the original C++ implementation.<br>I’ve also published a Rust implementation with my own optimizations, with source code on GitHub and a package on crates.io.

Recapt

A Franka Emika Panda robot and its spherized collision-checking representation.

I spend a lot of my time thinking about motion planning: finding ways for robots to find collision-free motions from a start state to a goal state.<br>There are a million different ways to solve motion planning problems, but once you’ve read enough papers they all kind of look the same.<br>You sample some configurations, test if they’re valid, and try to do a big path search over all possible configurations.<br>Every one of those algorithms requires configuration validation: given a robot’s configuration , determine whether a robot in position collides with the world geometry.<br>Since robots often work in perceived environments, that world geometry typically comes to us as a point cloud.<br>If our robot’s geometry is simplified to a bunch of spheres, we can further simplify the problem to spherical collision checking: for any configuration, just check if any of the spheres on the robot collide with the perceived point cloud.

Problem statement:<br>Given some list of points and a set of spheres , determine whether any sphere in collides with in minimal time.

A few years ago, I proposed a data structure called the CAPT, which is designed to make configuration validation against point clouds really fast.<br>In short, it’s a collision-checker between spheres and point clouds.<br>It’s a nearest-neighbor search structure, much like a -d tree, but we do extra work at construction time to avoid backtracking through the search tree.<br>The net result is that we have a -d tree with a batch-parallel search algorithm, supporting SIMD-accelerated branchless queries.

The big problem with CAPTs was the construction time: dense point clouds require a lot of duplicated data to avoid backtracking.<br>Once point clouds get dense enough, CAPT construction scales at , which is disastrous for a user’s hopes of getting planning at control-loop frequencies.<br>The data layout for CAPTs requires each leaf of the search tree, which represents some region in space, to store duplicate copies of many points in the point cloud.<br>Those duplicate copies start to dominate the data structure’s footprint, which in turn balloons construction time.

Thinking inside the box

Via Chen and Yeh, a voxel-based collision-checking scheme.

Ching Chen and Tsung-Tai Yeh, two other robotics researchers, decided to fix the problems with CAPTs for themselves.<br>To do so, they started by ditching nearest-neighbor search trees entirely.<br>Instead of with a space-partitioning tree, you can cut up the space into a grid of voxels, each storing a list of points that they contain.<br>The benefit here is twofold: first, you can tell which voxel a query sphere lies in with simple arithmetic, and second, you don’t have to duplicate any points, as finding adjacent voxels is trivial.

But naïvely just storing every voxel in the workspace doesn’t work.<br>If the workspace is a hundred voxels long in every dimension, then you’d have to store the information for a million voxels to record a single point cloud, which after filtering only contains a few thousand points.<br>To keep things under control, Chen and Yeh sparsely store only occupied voxels in a three-layer sparse tree, where each layer is segmented by one dimension.

Put together with a few axis-aligned bounding box tests, the resulting structure is a multilevel voxel table, or MVT.<br>Like the CAPT, MVTs are parallelizable using single-instruction, multiple-data parallelism (SIMD).<br>For any given voxel, the collision checker can do a big batch check for collision withh all the points contained in the voxel for a free constant speedup.

Patching some flat tiers

Flat as a board

The original implementation of MVTs had some gnarly C++-isms: namely, the voxel tables used a tapestry of pointers to each row of tables.<br>In addition to being kind of unhinged in general, this made memory management quite difficult, and also was not very size-efficient.<br>The original C++...