GPUGridIndexQuery

Overview

GPUGridIndexQuery selects stable object IDs from cells intersecting a GPU-resident point, bounds, or radius query. It publishes a capacity-bounded candidate list, the full stored-index candidate count, an overflow flag, and an optional source-ID-addressed mask. The result feeds visibility, compaction, picking policy, or an exact application predicate without CPU readback.

The word candidate is essential. A uniform grid indexes cells, not exact object geometry. A point query returns every object in the containing cell; bounds and radius queries return every object in an intersecting cell. This deliberately permits false positives so the index remains independent of whether an ID represents a point, label, particle, span, polygon, or object with its own bounds.

At a glance

Question	Answer
Problem	Publish stable candidate IDs from cells intersecting a point, bounds, or radius query.
Reads / writes	Reads a GPUGridIndex and query parameters; writes IDs, full candidate count, overflow, and optional mask.
Ownership	Public inputs and outputs are caller-owned; scratch storage is graph-owned transient memory.
Output contract	Capacity is fixed at compilation; counts and diagnostics report incomplete or overflowed output.
Expected work	Visits intersecting cells and their indexed ID ranges.
Chunks	Independent cell, ID, output, and mask chunks retain canonical source IDs.
Conditions / budgets	May be conditioned with its dependent branch; encoding, submission, and publication remain application-owned.
Neighborhood	GPUGridIndex + query → GPUGridIndexQuery → exact GPUPointSpatialFilter or consumer.

CostCell coverage and local density determine candidate work.

Common mistakeCandidates are not exact geometry hits; refine when exactness matters.

Concepts

Narrow first, test exactly second

Spatial acceleration is usually a two-stage operation:

grid cell query → conservative candidate IDs → exact object predicate → visibility or picking

The grid stage should be cheap and reusable. An exact stage can then fetch application-owned data for only those candidates: point distance for a radius, object bounds for an intersection, or screen-space geometry for picking. Keeping those contracts separate prevents GPUGridIndexQuery from embedding one object representation or claiming that cell overlap is an exact hit.

This matters most for large, selective queries. If a query covers most cells—or runs only once—an unindexed GPU scan may do less total work because it avoids index construction and candidate materialization.

Query kinds

The packed float32 query view is mutable between graph encodings:

Kind	Query layout	Cell rule	Typical use
point	2D: [x, y]; 3D: [x, y, z]	The one cell containing the point	Nearby labels, cursor candidates, simulation lookup
bounds	Minima followed by maxima	Every cell touching the query bounds	Rectangle selection, viewport candidates, box neighborhoods
radius	Center followed by radius	Every cell whose bounds intersect the circle or sphere	Proximity, collision broad phase, local influence

Point coordinates use the same boundary rule as construction: a point on an internal boundary selects the upper cell, while the domain maximum selects the final cell. Invalid point, reversed bounds, non-finite values, and negative radii produce no candidates.

Lists, masks, and overflow

The candidate output preserves stable IDs from GPUGridIndex, but atomic append order is unspecified. count reports how many candidates exist in the stored index prefix even if the output list is smaller. overflow becomes 1 when either the source index was truncated or the candidate output lacks capacity. Source-index overflow is propagated even when the stored prefix contains no match, because that apparently empty result may be incomplete.

An optional outputMask is cleared on every encoding and sets row objectId to 1 when that ID fits the mask length. This form composes directly with GPUMask and GPUVisibilityWorkflow when IDs address source rows. Sparse or application-global IDs may exceed the mask; they remain present in the candidate list but do not write outside it.

When to use it

Use candidate lists when the next pass should visit only spatially plausible IDs. Use the mask when the next workflow already operates source-aligned over every row. A list is usually better for a selective exact test; a mask is convenient for intersecting spatial membership with time, LOD, hierarchy, or selection decisions.

Cell size remains the dominant tradeoff. Very small cells increase index offsets, clearing, and the number of cells touched by broad queries. Very large cells return many false positives. The right size depends on object density, query radius, update rate, and how many queries amortize one build; the API does not pretend one grid is universally optimal.

Usage

const index = new GPUGridIndex({
  positions,
  gridSize: [64, 64],
  bounds: [-180, -90, 180, 90],
  cellOffsets,
  objectIds: indexedObjectIds,
  count: indexCount,
  overflow: indexOverflow
});
graph.add(index);

graph.add(new GPUGridIndexQuery({
  index,
  kind: 'radius',
  query: centerAndRadius, // packed float32 [x, y, radius]
  output: candidateIds,
  count: candidateCount,
  overflow: candidateOverflow,
  outputMask: candidateMask
}));

For three dimensions, a radius query contains [x, y, z, radius]; bounds contain [minX, minY, minZ, maxX, maxY, maxZ]. Updating the query buffer and encoding the compiled graph again changes the candidates without rebuilding graph structure.

The primitive neither builds the index nor applies exact object tests. It does not submit, grow capacity, sort or deduplicate IDs, or download results. Queries over an overflowed source index are explicitly marked incomplete.

Chunked storage

Cell offsets, indexed object IDs, candidate outputs, and the optional source-ID mask may each use independent vector partitions. Queries borrow adjacent cell starts/ends across seams, assign each selected stored ID one global destination, then route results to output chunks. The mask covers every selected stored ID even when candidate capacity is zero or truncated. Count and overflow retain their scalar contracts, and index overflow propagates to the query result. Query parameters remain a small atomic record.