Memory Centric Reordering for 3D Spatial Computing

27 concepts17 papers

Modern hardware is built on a fundamental lie: that computer memory is a flat, one-dimensional array of bytes. For many applications, this abstraction works well enough. But when algorithms attempt to simulate, navigate, or render the three-dimensional physical world, this 1D abstraction collides with 3D reality.

When 3D spatial data is mapped naively to linear memory, points that are close together in physical space end up separated by massive strides in hardware memory. This architectural mismatch creates a severe performance bottleneck across a wide range of fields—from neural rendering and robotics to medical imaging and quantum chemistry. To overcome this, a unified paradigm has emerged: memory-centric reordering. By restructuring either the layout of 3D data or the execution order of spatial queries, researchers are transforming chaotic, high-latency memory thrashing into predictable, high-bandwidth streams.

The Dimensionality Mismatch

To understand why naive 3D algorithms fail on modern hardware, consider how a 3D grid is typically indexed in memory. A standard linear layout flattens a grid row by row, slice by slice. Moving one step along the X-axis shifts the memory address by a single element. Moving one step along the Y-axis shifts it by the width of a row. But moving one step along the Z-axis requires jumping across an entire 2D slice of data.

As Brewer and Sturtevant demonstrated in the context of 3D pathfinding, this layout severely degrades cache locality. When an agent navigates vertically through a voxel grid, every step forces the processor to jump across large, non-linear memory offsets, triggering frequent cache misses.

Standard Linear Layout (Row-Major):
[ (0,0,0), (1,0,0), (2,0,0) ... (0,1,0), (1,1,0) ... (0,0,1) ]
                                                     └─ Huge memory jump for Z-axis!

This problem is not unique to pathfinding. In computational chemistry, Andrade showed that standard linear indexing cripples real-space Density Functional Theory (DFT). Calculating kinetic energy requires stencil operations, where a point's new value depends on its immediate spatial neighbors in all directions. In a linear array, these spatial neighbors are scattered far apart in memory, causing the CPU or GPU to constantly stall while waiting for data to arrive from DRAM. Similarly, Leong et al. observed that intensity-based medical image registration suffers from the exact same non-contiguous memory access patterns when querying neighboring voxels in large 3D anatomical volumes.

The issue compounds dramatically when algorithms introduce dynamic spatial queries, such as ray-casting. Whether a system is tracing millions of sensor lines to build a robotic occupancy map, as detailed by Li and Sze, or rendering a scene via Neural Radiance Fields (NeRF), the memory access patterns become completely erratic. Generic memory management and caching strategies, as Wang noted, simply fail to account for these predictable yet geometrically complex access patterns, leading to excessive latency and energy waste.

Strategy 1: Reorganizing the Data Layout

The first major strategy to restore cache locality is to abandon linear 1D mapping in favor of spatial block decomposition.

Instead of flattening a grid slice-by-slice, the 3D volume is divided into small, localized 3D blocks (such as cubes or parallelepipeds). Within each block, the data is stored contiguously. Andrade applied this technique to real-space DFT calculations, demonstrating that grouping grid points into localized 3D blocks ensures that a stencil operation's spatial neighbors are almost always resident in the hardware cache together, drastically increasing the cache hit rate.

Spatial Block Decomposition:
[ Block A (3x3x3 local cubes) ] -> [ Block B (3x3x3 local cubes) ]
  All X, Y, Z neighbors are stored close together in memory.

On modern GPUs, this concept can be offloaded directly to hardware. Luo et al. accelerated neuroimage registration by leveraging hardware-level 3D texture memory. GPU texture units are physically designed to optimize window- and neighborhood-based operations by caching data based on 3D spatial coordinates rather than 1D linear addresses, drastically reducing memory latency during dense voxel-wise comparisons.

For larger, sparser environments—like those found in robotics or massive 3D reconstructions—explicitly caching spatial pointers provides a massive speedup. Durvasula et al. introduced VoxelCache, a technique that caches voxel block pointers directly within CPU and GPU hardware caches. Because consecutive camera frames and adjacent rays frequently query the same volumetric regions, exploiting this temporal and spatial coherence allows the system to completely bypass expensive software-defined data structure traversals (like octrees or hash tables).

When scenes grow too large to fit into GPU memory entirely, maintaining spatial grouping becomes a hard requirement for out-of-core computing. Zhong et al. showed that when training massive 3D Gaussian Splatting models with over a billion primitives, grouping data geometrically allows a system to treat GPU memory as a dynamic cache. This geometric grouping increased CPU cache hit rates from 42% to 95%, preventing the parameter transfers between SSD, CPU, and GPU from bottlenecking the system.

Strategy 2: Reorganizing the Computation

Fixing the data layout is only half the battle. If the execution flow of an algorithm remains chaotic, memory performance will still suffer. The second strategy is to reorder the computation to match the data's physical layout.

Ray Sorting and Predictive Traversal

In traditional ray tracing, rays are processed in the order they are generated (usually pixel-by-pixel). However, rays shot from a camera quickly diverge, hitting entirely different parts of a scene and causing severe memory thrashing.

As surveyed by Xu et al., ray sorting reorganizes these rays into coherent bundles based on their spatial or directional similarity. By grouping rays that traverse the same physical space, a system can load a specific scene segment into memory once and process thousands of ray intersections before that data is evicted from the cache.

Pixel-Centric Execution (Incoherent):
Ray 1 (Pixel 1) -> Loads Block A
Ray 2 (Pixel 2) -> Loads Block B (Evicts A)
Ray 3 (Pixel 3) -> Loads Block A (Evicts B) -> Thrashing!

Memory-Centric Execution (Coherent):
Bundle 1 (Rays 1 & 3) -> Loads Block A -> Processes both rays
Bundle 2 (Ray 2)      -> Loads Block B -> Processes ray

We can also use spatial coherence to predict where data lookups should begin. Gupta et al. developed a mechanism for volumetric depth images that uses the search results of adjacent rays to estimate the starting position for lookups in the current ray. Because 3D data is spatially smooth, neighboring rays enter volumetric segments at similar depths. Leveraging this prediction reduces expensive memory lookups by roughly 40%.

From Pixel-Centric to Memory-Centric Streaming

The most radical shift in computation reordering is occurring in neural rendering (NeRFs and 3D Gaussian Splatting). Traditional graphics pipelines are pixel-centric or tile-centric: for a given pixel or tile on the screen, the system fetches all corresponding 3D primitives from memory to calculate its color. As Zhang et al. pointed out, this requires repeatedly transferring sorted primitive lists to and from external memory, creating massive DRAM traffic.

To solve this, a series of hardware-software co-designs have inverted the rendering loop into a memory-centric streaming dataflow.

Instead of asking "Which primitives affect this pixel?", a streaming architecture asks "Which pixels are affected by this memory block?"

  • Cicero: Feng et al. designed a system that groups 3D scene data into spatial blocks and maintains an index table of ray samples intersecting each block. Instead of processing rays pixel-by-pixel, the hardware streams the spatial blocks sequentially, transforming random memory accesses into a continuous, high-bandwidth stream that maximizes on-chip buffer efficiency.
  • Potamoi: Feng et al. extended this concept into a unified streaming architecture that streams scene representations—like voxels or Gaussians—sequentially from memory. This completely eliminates irregular DRAM accesses and hardware stalls, making real-time neural rendering viable on low-power mobile devices.
  • StreamingGS: Zhang et al. applied this to 3D Gaussian Splatting by partitioning the scene into discrete voxels. The primitives within these voxels are streamed sequentially into on-chip buffers, and intermediate pixel values are accumulated locally until the final calculation is complete. This shift achieved a 45.7× speedup and a 62.9× energy saving over traditional mobile GPUs.

As Li et al. observed in their work on Uni-Render, the computational complexity of modern spatial workloads is no longer driven by raw mathematical throughput, but rather by data indexing and reduction patterns.

Why It Works: The Intuition of Cache Reuse

The core philosophy behind memory-centric reordering can be summarized by a simple rule of hardware efficiency: Never load a piece of data from main memory unless you intend to do as much work with it as possible before letting it go.

When an algorithm operates in a naive, pixel-centric, or linearly indexed fashion, it treats the hardware cache as a lottery—hoping the next piece of data happens to be there. Memory-centric reordering turns this into a guarantee. By reshaping data into 3D blocks, sorting queries into coherent bundles, or streaming geometry sequentially, these architectures ensure that whenever a segment of the 3D world is brought into the processor's local memory, every calculation, ray intersection, or stencil operation associated with that segment is executed immediately.

By aligning the geometry of our algorithms with the linear reality of our hardware, memory-centric reordering bridges the gap between physical space and computational efficiency.

Key Foundational Work

Real-Space Density Functional Theory on Graphical Processing Units: Computational Approach and Comparison to Gaussian Basis Set Methods (2013) — contributed 3 concept elements to this direction.
Special issue on real-time 3D imaging and processing (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_spatial_ray_sorting_dc94c27c,
  title = {spatial ray sorting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spatial-ray-sorting/rdr_dc94c27ca0b242eca0ffd6f92c20fbe1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_spatial_ray_sorting_dc94c27c_v1,
  title = {spatial ray sorting},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/spatial-ray-sorting/rdr_dc94c27ca0b242eca0ffd6f92c20fbe1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake