From Point Clouds to Tensors: Bijective Gridification with SquareNet

Turning irregular spatial data into regular tensors without throwing points away.

Point clouds are everywhere in scientific computing and machine learning: 3D scans, geographic data, particle simulations, spatial statistics, sampled surfaces, and many other applications.

Yet point clouds have an inconvenient property for modern tensor-based computing: their spatial structure is irregular.

A point cloud is naturally represented as a matrix X.shape == (N, D), but the points do not live on a regular computational grid. As a result, operations that are trivial on images or regular tensors — local neighborhoods, convolutions, windowed operations, contiguous memory access — often require specialized spatial data structures such as kd-trees, radius searches, spatial hashing, or explicit neighborhood graphs.

These methods are useful, but they create a mismatch between the geometry of the data and the computational structure expected by modern tensor libraries.

What if we could rearrange the points onto a regular grid without discarding any point, without duplicating any point, and without losing the ability to recover the original representation?

This is the idea behind bijective gridification.

SquareNet is an implementation of this idea.

---

The core idea

Suppose we have a point cloud:

$$X=\{x_1,\dots ,x_N\},x_i\in {\mathbb{R}}^{D}X\; =\; \backslash \{x\_1,\backslash ldots,x\_N\backslash \},\; \backslash qquad\; x\_i\; \backslash in\; \backslash mathbb\{R\}^D$$

We choose a grid containing $N$ cells. For example, 10,000 points could be mapped to a $100\times100$ grid.

Bijective gridification constructs a mapping:

$$g:\{1,\dots ,N\}\to \{1,\dots ,n_1\}\times \cdots \times \{1,\dots ,n_D\}g\; :\; \backslash \{1,\backslash ldots,N\backslash \}\; \backslash rightarrow\; \backslash \{1,\backslash ldots,n\_1\backslash \}\backslash times\backslash cdots\backslash times\backslash \{1,\backslash ldots,n\_D\backslash \}$$

where every point is assigned to exactly one grid cell and every grid cell corresponds to exactly one point. In other words: « one point $\rightarrow$ one cell. »

The important property is that the mapping is bijective. We can therefore go from the original representation to the grid and back:

$$g^{-1}(g(i))=ig^\{-1\}(g(i))\; =\; i$$

• No point is averaged away.
• No point is interpolated.
• No information about the original point indexing is lost.

This makes gridification fundamentally different from ordinary voxelization or rasterization. The grid is not intended to approximate the point cloud's geometry. It is a new computational coordinate system for the same points.

---

Why put a point cloud on a grid?

Consider a dataset with $N$ points and $C$ features per point:

X.shape == (N, C)

A conventional point-cloud algorithm might need to repeatedly answer questions such as:

• Which points are close to this point?
• Which points are inside this radius?
• What are the nearest neighbors?
• Which points belong to this spatial region?

These are inherently irregular operations. After gridification, the same data can instead be represented as:

Xgrid.shape == (n1, n2, ..., nD, C)

A local neighborhood becomes an ordinary tensor window:

window = Xgrid[i-5:i+6, j-5:j+6]

The operation is now regular. This matters because tensor libraries are extremely good at regular, batched, vectorized operations. The objective is therefore not merely to make a point cloud look like an image. The objective is to change its computational representation.

---

A bijective transformation, not a voxelization

This distinction is important. Suppose several points fall inside the same voxel. A conventional voxelization may:

• aggregate the points,
• average their features,
• keep only one representative,
• or store a variable number of points per voxel.

Information is therefore potentially lost or requires an additional irregular data structure. Bijective gridification instead imposes a different constraint:

$$\text{number of points}=\text{number of grid cells}\backslash text\{number\; of\; points\}\; =\; \backslash text\{number\; of\; grid\; cells\}$$

Every point gets its own cell. The grid contains exactly the same points, merely rearranged.

For example:

Original point cloud
p₀  p₁  p₂  p₃  p₄  p₅  ...

        ↓ gridification

┌────┬────┬────┐
│ p₇ │ p₂ │ p₄ │
├────┼────┼────┤
│ p₀ │ p₆ │ p₁ │
├────┼────┼────┤
│ p₃ │ p₅ │ p₈ │
└────┴────┴────┘

        ↓ inverse mapping
p₀  p₁  p₂  p₃  p₄  p₅  ...

The spatial arrangement changes. The dataset does not.

---

The difficult part: preserving locality

Bijectivity by itself is easy. We could simply shuffle the points randomly onto the grid. But that would make the grid useless for spatial computation.

The important additional property is locality preservation. Ideally, points that are close in the original geometry should end up close in the grid:

$$\mathrm{\mid }{x}_i-x_j\mathrm{\mid }\text{ small}⟹\mathrm{\mid }g(x_i)-g(x_j)\mathrm{\mid }\text{ usually small}\backslash vert\{\}x\_i-x\_j\backslash vert\{\}\; \backslash text\{\; small\}\; \backslash quad\backslash Longrightarrow\backslash quad\; \backslash vert\{\}g(x\_i)-g(x\_j)\backslash vert\{\}\; \backslash text\{\; usually\; small\}$$

This property is deliberately stated as an implication rather than an equivalence. The reverse direction generally cannot be guaranteed:

$$\mathrm{\mid }g(x_i)-g(x_j)\mathrm{\mid }\text{ small}⟹̸\mathrm{\mid }{x}_i-x_j\mathrm{\mid }\text{ small}\backslash vert\{\}g(x\_i)-g(x\_j)\backslash vert\{\}\; \backslash text\{\; small\}\; \backslash not\backslash Longrightarrow\; \backslash vert\{\}x\_i-x\_j\backslash vert\{\}\; \backslash text\{\; small\}$$

Why? Consider a point cloud containing a large empty region. A regular grid has no way of representing an arbitrary amount of empty space while maintaining one point per cell. Points on opposite sides of a hole can therefore become neighbors in the grid. This is one of the fundamental trade-offs of the approach.

---

Why not solve the problem with optimal transport?

One natural way of formulating gridification is as an assignment problem. We have:

• a set of points,
• a set of grid locations,
• and a cost measuring how undesirable it is to assign a point to a particular grid location.

We could then search for the globally optimal assignment. This naturally leads to optimal transport and related assignment formulations.

The problem is scale. For large point clouds, solving a global geometric assignment problem can become prohibitively expensive.

SquareNet instead uses a much simpler idea: Cartesian sorting. The goal is not to find the mathematically optimal assignment. The goal is to find a good locality-preserving assignment using operations that are cheap, vectorizable, and scalable.

---

Cartesian Sort

The basic idea is surprisingly simple. Suppose we have a 2D point cloud and a 2D grid. We associate:

• the first spatial coordinate with the first grid axis;
• the second spatial coordinate with the second grid axis.

We then repeatedly sort the points according to these Cartesian projections. Conceptually:

point cloud    
    ├── sort along x    
    ├── sort along y    
    ├── sort along x    
    ├── sort along y    
    └── ...          
         ↓      
  structured grid

Sorting along one axis partially destroys the ordering produced by the previous axis. So the process is repeated until the different coordinate orderings become mutually compatible.

Each individual operation is a one-dimensional sort. For $N$ points, this is approximately an $\mathcal{O}(N\log N)$ operation per sorting pass, rather than a global quadratic or cubic assignment procedure.

Because the operations are simple tensor operations, they can also be implemented efficiently with numerical backends. This gives a useful trade-off:

« Give up global optimality in exchange for a fast, scalable, vectorizable spatial organization. »

In practice, the default Cartesian sorting procedure typically converges in fewer than 50 iterations for the datasets considered by SquareNet.

---

What does the resulting grid preserve?

Cartesian sorting gives several useful properties:

• Spatial locality: Nearby points tend to occupy nearby grid cells. This allows a geometric neighborhood to be approximated by a small tensor window.
• Coordinate monotonicity: The resulting grid has an ordered relationship with the original Cartesian coordinates. Informally: $x$ increases along one grid direction, $y$ increases along another, etc.
• Bijectivity: Every point has exactly one grid location. The mapping can therefore be inverted exactly.
• Measure preservation: Because the transformation is bijective, discrete mass associated with the points can be preserved under reindexing.

Note: This should not be confused with preserving Euclidean geometry. A triangle in the original space does not generally become a triangle in the grid. The transformation preserves the represented set of points, not arbitrary geometric quantities such as distances, angles, or triangle areas.

---

How good is the locality?

The interesting question is therefore empirical: How large does a tensor window need to be to recover a useful fraction of the true spatial neighborhood?

In a 1-million-point 2D experiment reported by SquareNet, using the "fast" fitting mode:

The important observation is not that the grid gives an exact nearest-neighbor data structure. It does not. The observation is that a tiny fraction of the full dataset can contain most of the relevant spatial neighborhood.

For workloads dominated by local operations, this can change the computational problem substantially:

Instead of:
N points → global spatial search → dynamic neighbors

We can use:
N points → bijective grid → small tensor window

---

From spatial queries to tensor operations

This is where the idea becomes particularly interesting for machine learning. Suppose a point cloud contains features:

X.shape == (N, C)

After fitting SquareNet:

Xgrid = sn.map(X)

We obtain:

Xgrid.shape == (n1, n2, ..., nD, C)

A local neighborhood can then be extracted using standard tensor indexing. For example, in 2D:

window = Xgrid[i-5:i+6, j-5:j+6]

The same principle extends to higher dimensions. This opens the door to replacing some irregular spatial operations with operations that are already highly optimized in tensor frameworks, such as:

• local feature aggregation,
• convolution-like operations,
• windowed attention,
• kernel evaluation,
• neighborhood statistics,
• local pooling,
• spatial filtering.

The exact performance benefit depends heavily on the downstream algorithm. SquareNet does not make every point-cloud problem faster automatically. Its purpose is to provide a regular computational layout that algorithms can exploit.

---

SquareNet in Action

SquareNet is an open-source implementation of bijective gridification. It supports arbitrary dimensions and is designed to work with large point clouds.

Install it with:

pip install squarenet

A minimal example

The basic workflow is:

from squarenet import SquareNet
import numpy as np

# 4D point cloud
N = 5 * 11 * 7 * 13
D = 4
X = np.random.rand(N, D)

# Choose the target grid
sn = SquareNet(gridshape=(5, 11, 7, 13))

# Fit the spatial mapping
sn.fit(X)

# Rearrange the point cloud
Xgrid = sn.map(X)

# Recover the original representation
Xback = sn.invert_map(Xgrid)
assert np.allclose(Xback, X)

The important part is that map() does not interpolate the data. It rearranges it. And invert_map() recovers the original ordering exactly.

Mapping indices instead of data

The transformation can also be used purely as an indexing structure. Suppose we have selected a subset of points:

sel = np.where(points[:, 0]**2 + points[:, 1]**2 <= 100)

These are indices in the original flat representation. SquareNet can map them to their grid locations:

gridsel = sn.mapidx(sel)

And later recover the original indices:

selback = sn.invert_mapidx(np.stack(gridsel, axis=1))

This is useful when the point features themselves should remain elsewhere in memory while the grid acts as a spatial indexing layer.

Approximate spatial lookup

Once the point cloud has been organized into a Cartesian grid, SquareNet also provides an approximate search operation:

point = np.random.rand(D)
index = sn.search_sorted(point)

This can be thought of as an $N$-dimensional generalization of the intuition behind one-dimensional searchsorted. The result is a grid cell corresponding to the approximate location of the query point.

Different fitting modes

SquareNet provides several fitting strategies:

The default is:

sn = SquareNet(gridshape=..., method="fast")

The more advanced methods trade computation time for potentially improved mappings. In particular, "ultimate" can require substantially more iterations and may become expensive on million-point datasets.

---

Arbitrary dimensions

The construction is not intrinsically two-dimensional. A point cloud can live in $D$ dimensions and be mapped to a $D$-dimensional grid. For example, gridshape = (5, 11, 7, 13) contains:

$$5\times 11\times 7\times 13\text{ cells}5\; \backslash times\; 11\; \backslash times\; 7\; \backslash times\; 13\; \backslash text\{\; cells\}$$

The same machinery can therefore be used for:

• 2D spatial data,
• 3D point clouds,
• higher-dimensional feature spaces,
• scientific simulation data,
• multidimensional parameter spaces.

The essential requirement is that the grid contain enough cells for the points being represented.

---

What SquareNet does not do

It is tempting to interpret gridification as a universal replacement for spatial data structures. It is not. There are several important limitations:

• It is not optimal transport: The Cartesian sorting algorithm is a heuristic. If you require the globally optimal assignment under a particular transport cost, SquareNet is not a replacement for an optimal transport solver.
• Locality is not symmetric: Large holes, clusters, boundaries, and strongly non-uniform sampling can create artificial grid neighbors.
• Angles and distances are distorted: A bijection between two point sets does not preserve their Euclidean geometry. The purpose of the mapping is computational locality, not isometry.

---

When should you use it?

SquareNet is particularly interesting when your downstream computation benefits from regular memory access:

• Point-cloud processing: Use local tensor windows instead of repeatedly constructing irregular neighborhood structures.
• Kernel methods: Exploit the grid to organize spatial interactions and potentially reduce the cost of large kernel computations.
• Deep learning: Convert flat point datasets into structured tensors that can be consumed by CNN-like or window-based architectures.
• Large-scale numerical computing: Replace some irregular indexing patterns with regular tensor operations that can be vectorized and parallelized.

« The geometry is irregular, but the computation does not have to be. »

---

Conclusion

Point clouds are naturally irregular. Tensor computation is naturally regular. Bijective gridification provides a bridge between the two.

Instead of voxelizing a point cloud, interpolating it onto an image, or constructing an explicit neighborhood graph, we can rearrange its points onto a regular grid while maintaining an exact mapping back to the original representation.

The resulting structure is:

• bijective — one point, one cell;
• invertible — the original indexing can be recovered;
• approximately locality-preserving — nearby points tend to remain nearby;
• dimension-independent — the construction generalizes beyond 2D and 3D;
• tensor-friendly — neighborhoods become regular windows;
• scalable — the underlying operations are based on sorting rather than global assignment.

$$\text{irregular spatial data}⟶\text{bijective grid}⟶\text{regular tensor computation}\backslash text\{irregular\; spatial\; data\}\; \backslash longrightarrow\; \backslash text\{bijective\; grid\}\; \backslash longrightarrow\; \backslash text\{regular\; tensor\; computation\}$$

The grid is not the data. It is a computational coordinate system for the data.

---

Try it out

• GitHub: ArmanddeCacqueray/SquareNet
• Install: pip install squarenet

If you work with point clouds, spatial statistics, geometric deep learning, or large-scale tensor computations, I'd be particularly interested in seeing what kinds of algorithms can take advantage of this representation.

SquareNet is released under the MIT license.