point-to-grid data structure for point cloud preprocessing

[ArmanddeCacqueray]

Hi everyone,

I’m working on a point-to-grid sorting algorithm that I think could be useful as a preprocessing step for large unstructured point clouds in various geometric tasks.

The idea is essentially a generalized sorting procedure, where points are assigned a multi-index that follow the spatial structure, e.g. "P[i,j,k]", instead of a single index "P[i]". The multi-index is constructed through greedy 1D sorting procedures.

In my use case, this provides an efficient approximate neighbor-query structure for massive point clouds (millions of points), particularly on GPUs using tensor operations. For example, I’ve been using it for Gaussian blue-noise sampling, where it gives roughly a 100× speedup over brute-force Gaussian blue noise algorithm, with very little noticeable approximation error.

The gridification step itself is simple and intuitive, and I wonder whether a similar structure could be useful for other geometric algorithms — for example CNN-style operations, segmentation, spatial indexing, or other point-cloud processing tasks.

Do you see any potential applications for this kind of sorting/gridification approach in Open3D? I’d be very happy to try implementing it and see how it could fit into the ecosystem.

Here is the repo: https://github.com/Space-filling-net/Cartesian-Sort