Binned lookup from a position on a layer to the sensitive surfaces near it.

Acts::SurfaceArray answers one question: given where a track crosses a layer, which sensitive surfaces could it hit. It holds the surfaces of one layer in a two-dimensional grid drawn on a representative surface and returns, for a position and a direction, the surfaces registered in the bins around the crossing point.

The figures for the two things that decide whether that works - which bins hold a surface, and how far from the crossing bin the module it hits can be - are on a separate, interactive page: filling and lookup, in figures. Everything below is the written description; the page carries the pictures and the measurements.

Overview

A layer holds its sensitive surfaces in a SurfaceArray, and navigation asks the array instead of testing every module:

Acts::SurfaceArrayCreator builds it, through Acts::SurfaceArrayCreator::surfaceArrayOnCylinder, Acts::SurfaceArrayCreator::surfaceArrayOnDisc or Acts::SurfaceArrayCreator::surfaceArrayOnPlane, usually called from Acts::LayerCreator.
Acts::Layer owns it and queries it from Acts::Layer::compatibleSurfaces. This is the Gen1 navigation path.
Acts::SurfaceArrayNavigationPolicy builds one for a Gen3 layer volume and feeds the result into the navigation stream.

Both consumers call Acts::SurfaceArray::neighbors with the geometry context, the position and the direction, and receive a std::span of surface pointers. The array does not intersect the surfaces it returns. It narrows the candidates; the caller intersects them.

The single-surface constructor builds an array without a grid. Every lookup returns that one surface.

The grid

The grid is drawn on a representative Acts::RegularSurface that the creator derives from the extent of the surfaces:

Layer	Representative surface	Axis 0	Axis 1
Cylinder	Acts::CylinderSurface	phi, Closed	z, Bound
Disc	Acts::DiscSurface	r, Bound	phi, Closed
Plane	Acts::PlaneSurface	first in-plane direction, Bound	second in-plane direction, Bound

The axes are Acts::IAxis objects, equidistant or variable, and every lookup implementation is templated on both axis types behind the ISurfaceGridLookup interface. The boundary type (Acts::AxisBoundaryType) fixes what happens at the edge. A Closed axis wraps: the bin after the last phi bin is the first, and a neighborhood of an edge bin continues on the other side. A Bound axis clamps: a position past the edge lands in the edge bin and a neighborhood stops there. Each axis also carries an underflow and an overflow bin, so Acts::SurfaceArray::size returns (n0 + 2) * (n1 + 2).

Bin edges are expressed in the local frame of the representative surface. On a cylinder and a disc the creator rotates that frame so that the phi seam at +-pi falls between modules, never on a module center.

Surface local versus grid local

The grid is binned in the quantities the axes name. The bound-local coordinates of the representative surface are not always those: a Acts::CylinderSurface measures arc length R * phi along its first local coordinate while the grid bins phi. surfaceToGridLocal and gridToSurfaceLocal divide and multiply by the cylinder radius; on a disc and a plane they are the identity. Both maps are linear, so they carry a displacement the same way as a position.

Filling

The array registers every surface in every bin its projection onto the representative surface overlaps. fillSurfaceFootprint does this once per surface at construction:

Confirm that the surface belongs to the layer: its reference position must project onto the representative surface within the layer tolerance.
Take the outline from Acts::Surface::polyhedronRepresentation and walk each edge in 32 samples. A straight edge in space is not straight in grid coordinates, so the vertices alone are not enough.
Project each sample along the normal of the representative surface onto it, convert to grid coordinates and to a bin. Samples in the underflow or overflow bins are dropped.
Group the sampled bins into columns keyed by the closed axis. Per column keep the lowest and highest bin along the other axis, and register the surface in every bin of every column span.

The footprint is sampled, so sufficiently fine bins can be missed between samples. Filling the span can also include extra cells for a concave outline. Keying the columns by the axis that wraps prevents a span across the phi seam: a module straddling +-pi produces columns at both ends, each with its own span along the bound axis.

The optional overfill argument of Acts::SurfaceArray, Acts::SurfaceArrayCreator and Acts::LayerCreator expands every matched cell during construction. It defaults to zero. A value of one also fills the immediate neighbors, including diagonals; two reaches the next neighbors, and n reaches all cells within n bin steps on each axis. Closed axes wrap, and expansion stops at nonperiodic grid edges. Underflow and overflow cells remain empty. Overlapping contributions are deduplicated.

Overfilling changes the stored contents returned by at() as well as neighbors(). It is independent of NeighborWindow: the latter gathers those contents around the lookup cell. Overfilling can provide a margin for alignment or sampling gaps, at the cost of more candidates; it does not guarantee that a sampled footprint covers arbitrarily fine grids.

SurfaceArray array(gctx, surfaces, representative, tolerance, axes,
                   SurfaceArray::NeighborWindow{{0, 0}, {2, 2}},
                   /*overfill=*/2);

A module projected onto a disc grid, the two point tests the footprint fill replaced, and what each of them costs in bins are in the figures.

After all surfaces are filled the bin contents are sorted and deduplicated, checkGrid verifies that every input surface landed in at least one bin, and the neighbor cache is built. The filling grid is scratch; its contents survive as the zero-distance packs of the cache.

Lookup

neighbors(gctx, position, direction) is the navigation entry point:

Intersect the representative surface along direction from position (findCrossing). No intersection means an empty result.
Convert the crossing to grid coordinates and to a bin.
Compute the neighbor distance per axis (crossingNeighborDistance).
Return the cached pack for that bin and distance.

at(gctx, position, direction) skips step 3 and returns the content of the crossing bin alone.

Why a window

The lookup happens where the track crosses the representative surface; a module is registered where it projects onto that surface. Between the two the track moves along the layer, the further the shallower the crossing, and the window around the crossing bin spans that movement.

crossingNeighborDistance derives the slide from the crossing geometry:

The array is built with a tolerance, the half thickness of the layer. A track with direction d meeting the representative surface with normal n travels tolerance / |n . d| inside the layer on each side of the surface.
Dropping the component along n leaves the part of that path that runs along the layer: slide = (tolerance / |n . d|) * (d - (n . d) n).
The slide is a global displacement. Acts::Surface::localCartesianToBoundLocalDerivative maps it into the bound-local frame of the representative surface with the curvilinear scaling included: (d(R phi), dz) on a cylinder, (dr, dphi) on a disc, (dx, dy) on a plane. surfaceToGridLocal turns that into a step in grid coordinates.
The bins at +slide and -slide from the crossing point give the distance per axis, in bins, following the signed displacement across a closed-axis seam. A full turn covers the axis rather than wrapping the distance to zero. The larger of the two sides is kept.

The derivative supplies the local metric. This is a first-order estimate on curved surfaces, bounded by the configured window. At a coordinate singularity, an undefined displacement opens the affected axis to its configured bound.

The same crossing, in r-z and on the bin grid, and the miss rate each window policy carries across the barrel, are in the figures.

Below an incidence |n . d| of 1e-4 the track runs along the layer and the window opens to its bound.

The neighbor window

Acts::SurfaceArray::NeighborWindow bounds the distance per axis:

struct NeighborWindow {
  std::array<std::uint8_t, 2> min = {0, 0};
  std::array<std::uint8_t, 2> max = {2, 2};
};

The computed distance is clamped into [min, max] on each axis. max also sizes the neighbor cache, so it is a cost as well as a bound. The defaults set by Acts::SurfaceArrayCreator and Acts::LayerCreator are:

Layer	max	Meaning
Cylinder	{1, 2}	one bin in phi, two in z
Disc	{2, 1}	two bins in r, one in phi
Plane	{2, 2}	two bins in either direction

min is {0, 0} everywhere. The floor exists for lookups under a geometry context the fill did not see. The fill runs once, in the construction context; a lookup under an alignment context sees moved surfaces, and a floor of one bin keeps them reachable. {1, 1} for both min and max reproduces the fixed 3x3 lookup the array used before the window was sized by the crossing angle. When min equals max the angle is not evaluated.

Constructing a NeighborWindow from a single std::uint8_t is deprecated; it sets max to that value on both axes and min to one, or to zero if the bound is zero. Acts::SurfaceArray::maxNeighborDistance is deprecated in favor of Acts::SurfaceArray::neighborWindow.

The neighbor cache

The set of surfaces reachable from a bin at a given distance is fixed once the array is filled. populateNeighborCache precomputes it for every valid bin and every (distance0, distance1) up to max. Each result is a sorted, deduplicated pack of surface pointers. Identical packs are stored once, found through a hash table that reads packs back through their offsets, and the index array holds (offset, count) pairs of 32-bit integers.

A lookup is therefore one index computation, bin * stridePerBin + distance0 * stride1 + distance1, and a span into the pack storage. No gather over neighboring bins happens at lookup time.

The index array has (n0 + 2) * (n1 + 2) * (max0 + 1) * (max1 + 1) entries. Both this index and the pack contents cost memory: each pack lists the surfaces of up to (2 max0 + 1) * (2 max1 + 1) bins. On the generic detector at the default bounds the cache is 13.6 MB. A lookup on a toy barrel costs about 80 ns; what that is made of is in the figures.

SurfaceArray is also used by Acts::SurfaceArrayNavigationPolicy in Gen3 geometry.