Fast storage format for huge point clouds (fast read/write)

Question

I am working with huge point clouds (1 billion points). I need to process and display them but because of the size of the data, I can't have it all in memory at the same time.

First of all, I am not asking for a tech that does that (CloudCompare, Potree, Terrasolid, etc.). I'm asking about a file format solution to this storage problem.

I plan on storing the point clouds in an octree with multi-resolution versions of the point cloud. Each node contains a "section" of the point cloud(s) at a given resolution. Each node should be able to contain multiple point clouds (preferably separated so I can load one without having to load the others). Each point clouds is composed of points which can have attributes (at least x, y, z, t, g, b but in the future I'll add some so it must be flexible enough to allow that).

I'll be displaying the point clouds, so I need a very fast access to the node (as in, I don't want to parse 10GB of file before I find the node I asked for). And I'll be processing and modifying the data, so I need to b able to grow the nodes, modify the data. Even in the "middle" of the file, which means that it must support some kind of paging/chunking of the data to allow fast insertions.

The file format is not meant to be sharable between computer. It will just act as a cache while the program is running and the performances in read & write access are the most important.

Right now I've found some "solutions" :

• completely custom file format: I takes conception & development time, I may be reinventing the wheel but it will do what I want
• directory structure : I use the file system to do the work for me. I define the octree structure using directories and I store each of my point clouds as a file in the directories. Since each node is a small subset of the original point cloud (maybe 10k points), the writes won't take long, but to load a node, I need to read all the files in the directory which is not efficient. If I merge all the point clouds in a single file in each node, then it is not efficient to write to it if I want to modify a single point cloud
• HDF5 based format : Looks promising, I can store my whole octree in a single file, the lib handles for me all the chunking, fast access and management of the data, but I've heard some bad things about it (only one implementation which is hard to understand, complicated specifications). It may be overkill for my needs.
• database : Something like the pgPointCloud module for PostgreSGL.

The softwares I talked about earlier are :

• potree : uses a directory representation of the octree then store each node in a LAS or LAZ file. LAS/LAZ files are good for storing the data but not really to work on it (process & modification).
• Terrasolid : uses FBI (Fast Binary Format) files. I have trouble finding information on this file format but its name sounds promising. I don't think it is open but if you have resources on this format, that would be great.

I would prefer sticking with the octree structure (which has many advantages for me), but if an already existing format for storing spatially ordered data does what I need, feel free to mention it!

At the moment I'm leaning toward the HDF5 solution, but before I try running real tests, I'd like to have your opinion on the question. Did I missed some solutions ? Are some solutions inefficient for my needs (like maybe the database solution ?). Do you have any experience on the subject that could help me ?

Thanks in advance !

(I posted here but maybe is there a more appropriate stackexchange forum dedicated to storage ? Sorry if I posted in the wrong place).

Answer 1

I'm not an expert in the field, nor do I know your exact constraints/data, but I may have an idea. Or at least something that would be worth trying if the points are spread more or less uniformely.

Instead of octree, there exists a simpler concept called "spatial hashing". Basically, using your x,y,z, you compute an approximation of its location by rounding it and use it as a hash.

Basically, instead of a recusrsive octree you have a huge hash map filled with points. You just have to pick a coordinate rounding that fits well. This technique is however not appropriate if the point distribution is very skewed.

Persistent maps are easier to find than octree implementations. (Shameless self-promotion: if you're using python you can try mine if you want to give this a quick shot, it should be pretty efficient https://github.com/dagnelies/pysos). Of course, if performance is crucial, a tailored implementation would be fastest.

I also advise against using the filesystem to build huge octrees, it'll kill performance. Some DBs on the other hand have support for spatial indexes, that would probably be a good option too.