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,

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 https://youtu.be/Gh5pAT1o2V8?t=106 [1] https://github.com/ethz-asl/voxblox https://github.com/ethz-asl/voxblox [2] http://www.openvdb.org/about/ http://www.openvdb.org/about/