Point transformers (Point Transformer v3)

"I stopped hunting for each point's neighbors and simply asked them to stand in a sensible line. The line was wrong just often enough to be right on time."

A Serializing AI Agent

This section assumes you know how self-attention works from Chapter 15 and how voxelization and sparse tensors organize a point cloud from Section 42.2. Our narrow job here is to explain why naive point attention fails, how serialization rescues it, and what the PTv3 block actually computes. We treat the detection and segmentation heads that sit on top of this backbone as given and defer them to Section 42.5.

Why attention on raw points is hard

A point cloud is a set of \(N\) points \(\{\mathbf{p}_i\}\) with no canonical order and no grid. The earliest point transformers (PTv1 and PTv2) applied attention the geometrically honest way: for each point, find its \(k\) nearest neighbors with a k-d tree, then attend within that local neighborhood using vector attention weighted by relative position. This respects the data, and it works, but it is punishingly slow. The k-nearest-neighbor query is an irregular gather: neighboring points in space live at arbitrary, scattered memory addresses, so every attention block pays for cache misses and pointer chasing that a GPU hates. On a full outdoor scan the neighbor search alone can dominate runtime, and the receptive field stays small because widening \(k\) makes the gather quadratically worse.

The core realization behind PTv3 is that this precision is not worth its price. If we can impose any ordering on the points that keeps spatial neighbors mostly close together in the ordering, then "attend to nearby points" becomes "attend to a contiguous window of the sequence," which is a dense, coalesced memory read. We accept that the ordering will occasionally place two spatially-distant points side by side, and two spatially-close points far apart. That error is the price; scale is what we buy.

Serialization: a space-filling curve turns 3D into 1D

The tool that makes this work is a space-filling curve: a mapping that threads a single continuous path through every cell of a voxel grid so that cells adjacent along the path tend to be adjacent in space. PTv3 uses two, the Z-order (Morton) curve and the Hilbert curve. The Morton code of a voxel is computed by interleaving the bits of its integer \((x,y,z)\) coordinates; sorting points by this scalar code produces the serialization. The Hilbert curve preserves locality even better (it never makes long jumps) at slightly higher encoding cost.

Concretely, quantize each point to an integer grid coordinate with bit-depth \(b\) per axis, then interleave:

where \(x_j\) is the \(j\)-th bit of \(x\). The resulting integer is a 1D address that a radix sort orders in linear time. Because the interleaving mixes the high bits of all three axes first, points that share a coarse spatial region get contiguous codes. The code below builds a Morton ordering and demonstrates the locality it induces.

import numpy as np

def morton_encode(coords, bits=10):
    """Interleave bits of integer (x,y,z) voxel coords into one Morton code."""
    coords = coords.astype(np.int64)
    code = np.zeros(len(coords), dtype=np.int64)
    for j in range(bits):
        for axis in range(3):
            bit = (coords[:, axis] >> j) & 1
            code |= bit << (3 * j + axis)
    return code

# A toy scan: 20k points quantized to a 1024^3 grid (10 bits/axis).
rng = np.random.default_rng(0)
pts = rng.random((20000, 3)) * 50.0                  # meters
vox = np.floor(pts / (50.0 / 1024)).astype(np.int64) # integer voxel coords
order = np.argsort(morton_encode(vox, bits=10))      # the serialization
pts_sorted = pts[order]

# Neighbors in the sequence are usually neighbors in space:
step = np.linalg.norm(np.diff(pts_sorted, axis=0), axis=1)
print(f"median gap between consecutive points along curve: {np.median(step):.3f} m")
print(f"median gap for a random ordering:                  "
      f"{np.median(np.linalg.norm(np.diff(pts, axis=0), axis=1)):.3f} m")

Running the snippet shows the median spatial gap between sequence-adjacent points collapses by roughly an order of magnitude versus a random ordering. That gap is the whole game: it means a contiguous window of the serialized sequence is a good stand-in for a true spatial neighborhood, and attention over that window approximates local attention without a single k-d tree query.

Inside the PTv3 block

With points serialized, a PTv3 layer looks almost like a 1D vision transformer. The sequence is partitioned into non-overlapping patches (windows) of a fixed size, typically 1024 points, and standard self-attention runs within each patch. Three design choices adapt this to geometry. First, shuffled orders: PTv3 keeps several serializations (Morton and Hilbert, each in a few axis permutations) and rotates through them across layers. Because each curve breaks locality in different places, alternating them heals the seams; a boundary that splits two close points in the Morton order is interior to the Hilbert order. Second, xCPE (extended conditional positional encoding): rather than the additive relative-position tables that made PTv2 slow, PTv3 injects position with a lightweight sparse depthwise convolution applied to the values before attention, cheaply reintroducing exact local geometry. Third, the backbone is a U-Net: patches are pooled by grid coarsening between stages, so deep layers attend over larger physical regions.

The receptive field arithmetic is what pays off. A sparse-conv backbone reaches a given range only by stacking enough \(3^3\) kernels; PTv3 reaches over a thousand points in a single patch and, through pooling and shuffled curves, achieves an effective receptive field far larger than PTv2 at a fraction of the cost. This is the same "make the sequence cheap, then make it long" philosophy that drives the linear-time sequence models of Chapter 16, applied to 3D geometry instead of time.

When to reach for PTv3 versus sparse convolution

PTv3 is the strong default when accuracy on large scenes matters and you have GPU memory to train it: dense semantic segmentation, panoptic tasks, and any setting where long-range context (a lane's continuity, a wall's extent) drives the label. It also shines as a pretraining backbone, since its scale lets it soak up large unlabeled corpora. Sparse convolution from Section 42.3 remains the pragmatic pick for tight latency and memory budgets, especially the anchor-free detectors that must run at sensor frame rate on an embedded automotive computer, where the deployment constraints of Chapter 59 dominate the choice. A useful habit: prototype with PTv3 to establish an accuracy ceiling, then decide whether a distilled or sparse-conv student can hit your latency target. Whichever backbone you pick, evaluate it with the geographically-split, leakage-safe protocol from Section 42.7; serialized attention can quietly memorize a single city's layout if train and test tiles overlap.

What's Next

In Section 42.5, we put a backbone like PTv3 or a sparse-conv net to work: attaching detection, segmentation, and tracking heads that turn a per-point feature map into 3D bounding boxes, semantic masks, and object trajectories, and measuring them with the metrics the field actually reports.