We're not done with point clouds

A recent research team has taken a published idea of mine and improved upon it, outpacing my original work in several key benchmarks. I'm sharing the details of their advancements and my subsequent efforts to reimplement their solution. Their solution centers around a data structure designed to efficiently validate collisions between robots and their environments represented as point clouds.

Point clouds, which are collections of data points in space, are often used to model the world in robotics applications. However, determining collisions between these point clouds and robot geometries can be computationally intensive.

The original approach I proposed, the CAPT, was a collision-checker designed to work with point clouds. It functioned like a nearest-neighbor search structure, but with additional optimizations to speed up collision detection. Despite its efficiency, CAPT faced significant drawbacks due to its construction time. When dealing with dense point clouds, the construction process became prohibitively slow, scaling poorly and making real-time planning for robotic applications challenging.

Enter Ching Chen and Tsung-Tai Yeh, two researchers who sought to address these issues. They abandoned the traditional nearest-neighbor search tree approach that CAPT relied on. Instead, they partitioned the space into a grid of voxels, each containing a list of points that fall within its boundaries. This voxel-based approach eliminated the need for duplicate point storage, as points were only stored once per voxel.

By using three layers of a sparse tree to manage the voxels, they achieved a more memory-efficient structure called the Multilevel Voxel Table (MVT).

The MVT structure inherits the parallelization capabilities of the CAPT, allowing for simultaneous processing of multiple voxels using SIMD (Single Instruction, Multiple Data) operations. This means that the collision checker can quickly determine if a robot's configuration collides with the environment by examining the points within the relevant voxels. The MVT's simplicity and efficiency made it an attractive choice for implementation in various programming languages.

For my own implementation, I focused on creating a Rust version of the MVT, which brought several benefits. Rust's ownership system and memory safety features made the code easier to write and maintain compared to the original C++ implementation. I also simplified the memory management by using a Box instead of the complex pointer tapestry found in the original C++ code.

Furthermore, I made the structure mutable, allowing for dynamic updates without the significant performance overhead typically associated with mutable structures.

My implementation provided users with both an immutable version of the MVT and a mutable variant, known as MutableMvt. This flexibility allowed developers to choose the structure that best suited their specific use cases. To optimize performance, I introduced different voxel sizes, which required users to balance query speed against the potential inefficiencies of too many small voxels.