Animation showing live progress of the multi dimensional cartesian sort algorithm for point cloud gridification. Bijective gridification allow to convert the raw key of the points to spatially coherent mulit dimensional key, enabling tensor based ML algorithms to work on arbitrary point clouds (source code in the comments).
During a research internship, I ran into a problem involving massive neighbor queries on a GPU for a large particle-dynamics simulation. This led me to experiment with and develop SquareNet, an open-source Python package for NumPy/JAX/PyTorch.
Its core sorting algorithm (Cartesian sort) enables fast, greedy multidimensional reordering of raw point sets — essentially a form of gridification. Raw points, e.g. (x, y, z, ...), are mapped to unique grid multi-indices [i, j, k, ...] while trying to preserve local geometry, somewhat like a multidimensional generalization of a space-filling curve.
The collection of all multi-indices forms a grid lattice that can be processed efficiently with ML tensor-based frameworks, even when the initial dataset is an irregular point cloud.
I’m wondering whether this could be useful in contexts such as convolutional networks, non uniform fourier transform or ANN search on irregular LiDAR data.
The target use case is approximate but fast and scalable assignment preprocessing, then the grided/tensorized version of the dataset is exploited by standard tensor based frameworks, and result is converted back to the points. High-quality procedures for the assignement part already exist and are well established, such as optimal transport, but they were intractable in my context due to their O(N²/N³) complexity. Cartesian sort, by contrast, runs in O(N log N). It is specifically designed for grid assignment in a greedy setting, trading global optimality for speed and scalability.
In my practical application, involving millions of points processed in a dynamic context (Gaussian blue noise), this simple approach turned out to work well: it provided a ~100× speedup compared to exact brute-force computation of particle interactions, with negligible approximation error (I can provide more details about this experiment if useful).
One caveat is that a single gridification pass introduces a slight axis bias and can produce some distortion/outliers, which can be problematic for challenging distributions where exact geometric precision is required. If exact accuracy is critical, one possible approach would therefore be to build an ensemble of gridifications, each using a different viewpoint/rotation.
Empirically, something like 8 randomly chosen viewpoints seems to give near-perfect recovery of local geometry in a 3D test evaluated with a freud analysis (second link below). However, in the Gaussian blue noise context, where the geometry is smoother, a single viewpoint was already sufficient.
I built an interactive demo on Hugging Face (first link below) to showcase the approach. I’d really appreciate any feedback, especially on whether this idea has already been explored in related computer vision / point-cloud literature, or whether you see potential applications or obvious better alternatives that I may be missing.
In Monte Carlo methods, statistical physics, and related areas, people often look for well-distributed point sets.
A common idea is blue noise: point patterns with low density fluctuations (like a crystal) but no regular periodic structure (like a gas). Many sampling methods exist to generate this kind of distribution.
A related question is: how do we sample points that are both well distributed and follow a given target density?
The target can be an image, a Gaussian, or any arbitrary shape. This is often called stippling: replacing a continuous density with a set of points whose local density matches it.
It also has a strong visual aspect, and connects well with how we perceive images. There are some artistic examples as well, like Shāoshāng Xiǎo Gē:
https://www.instagram.com/reel/DMp-WoeIyMH/?hl=fr
Good and fast stippling methods are still relatively rare. One example is here:
https://www.joesfer.com/?p=108
I made a small Python package to make this easier, where image-to-point sampling is just:
blue_sampler.im2points(image="zebra.jpg")
https://pypi.org/project/blue-sampler/
Any other good open-source stippling or blue-noise tools you’d recommend?
Behind any spatial dataset — a point process, a cloud of correlated samples, or observations drawn from a complex distribution — there may exist a hidden D-dimensional grid.
This is the intuition behind optimal transport: building a mapping between a complex geometry and a simpler reference space with strong mathematical and numerical structure. Here, the reference space is a Cartesian lattice.
Once such a mapping is found, initially “flat” indices (0,1,2,...) can be lifted into rich tensor coordinates such as (0,0), (0,1), ....
This makes it possible to define rows and columns, apply convolutions, query local neighborhoods, or process irregular point clouds using grid-based algorithms.
The following checkerboard visualizations illustrate a gridification method based on iterative 1D sorting operations.
Code and implementation are open-source
(SquareNet on GitHub / PyPI).