Hacker News Reader

Comment by sorenjan | Hacker News Reader

What's the best way to represent 3D data when you might have a large area with sparse geometry? I'm thinking something like a visual SLAM system, where you build up a map of the surroundings while moving through it. In 2D it should be pretty straight forward, but using a 3D grid seems like it would get out of hand fast. Is it a KD-tree with voxels? Signed Distance Fields? How do robots and self driving cars store the dynamic maps they build from sensor data?

View on HN

That is an interesting question! Whether a 3d grid gets out of hand depends how big you can make your cells. Tree based techniques are inflexible with respect to bounding volume changes, requiring some kind of complex rebalancing technique to stay efficient.

Cars or moving robots still move on a 2d surface, so projecting everything into a 2d plane works for these applications.

It's my understanding that a lot of self driving cars use LIDAR to localize themselves in a 3D map, so a 2D representation wouldn't work. Then there's bridges, tunnels, and so on. Maybe a better example is flying drones, there are consumer drones available that keeps track of the surrounding and the user. In this video[0] it looks like they use a sparse grid of some kind, but wouldn't that be a tree?

The problem with a grid is as you mention the cell size. If instead of cars we use a different example, like large scale photogrammetry, a small cell size is desirable, because you want as much detail as possible, but you might reconstruct a small city. With some tall houses you need a large grid in the z-direction, even if most of the volume will be empty, suggesting that a tree would be the better solution.

Are there any real life examples of how this problem has been solved? As far as I can tell, this project supports point clouds and mesh as the main data storage, and KD-trees from point clouds to do operations on it. I've found, but never used, Voxblox[1] and OpenVDB[2] that looks promising. Voxblox is made for robots but looks like it might use a lot of RAM for larger spaces, OpenVDB is made for visualization but maybe works for other things too? I don't really understand how it works though.

[0] https://youtu.be/Gh5pAT1o2V8?t=106

[1] https://github.com/ethz-asl/voxblox

[2] http://www.openvdb.org/about/

Are you thinking of a voxel grid when your are talking about a grid? A grid acceleration structure is different from that: each cell is a variable length list of the contents of the cell. So in case of a sparse voxel grid you would have a coarse grid with the cells pointing to voxel grids iff there is at least one non-empty voxel inside the volume. So you're only allocating memory for blocks that have some voxel information to store. The coarse grid itself is just a set of list headers which don't have a high memory requirement (a few MB maybe).

MPEG is now standardizing (progressive) point clouds for the visual SLAM scenario. They are going forward with an octree with voxels.

If you mean geometry, you can just store the points. If you mean voxels or dynamically loading and unloading of points, a kd-tree or octree is probably what you are looking for.

I mean building up geometry from scratch using different kinds of depth sensors in an expanding environment of unknown size. The data is probably in the form of point clouds to start with, but you can't really store them sequentially if you want to do any operations on it, like loop closure or rendering.

Yeah, signed distance fields:

A Volumetric Method for Building Complex Models from Range Images https://graphics.stanford.edu/papers/volrange/volrange.pdf

(cited by 2630)

Thanks for the link.

Reply on news.ycombinator.com