Three.js Blocks

Home
Documentation
Examples
Tools

ComputePrefixSum

@three-blocks/coreWebGPU
new ComputePrefixSum(dataBuffer : StorageBufferNode, options : Object)

GPU-accelerated parallel prefix sum (exclusive scan) for Three.js TSL compute shaders.

ComputePrefixSum implements the Blelloch scan algorithm for computing prefix sums entirely on the GPU. It's designed as a building block for more complex parallel algorithms like radix sort.

Features

  • Fully GPU-accelerated: All operations execute as compute shaders
  • Hierarchical: Handles arrays larger than a single workgroup via recursive block sums
  • Work-efficient: O(n) work complexity using Blelloch algorithm
  • WebGPU only: Requires workgroup shared memory (not available in WebGL)

Algorithm

The Blelloch scan operates in two phases:

  1. Up-sweep (reduce): Build a tree of partial sums from leaves to root
  2. Down-sweep: Propagate prefix sums from root back to leaves

For arrays larger than workgroup capacity, the algorithm:

  1. Computes local prefix sums per workgroup
  2. Extracts block sums (total per workgroup)
  3. Recursively computes prefix sum on block sums
  4. Adds block prefix sums back to each element

Usage

Constructor Parameters
dataBufferStorageBufferNode
The storage buffer containing uint elements.
optionsoptionalObject
Configuration options.
Default is {}.
  • workgroupSizeoptionalnumber
    The workgroup size for compute shaders. Each workgroup processes 2 * workgroupSize elements. Must be a power of 2.
    Default is 128.
Example
import { instancedArray } from 'three/tsl';
import { ComputePrefixSum } from '@three-blocks/core';

// Create a buffer of uint values
const data = instancedArray(new Uint32Array([3, 1, 4, 1, 5, 9, 2, 6]), 'uint');

// Create prefix sum instance
const prefixSum = new ComputePrefixSum(data);

// Compute prefix sum
prefixSum.compute(renderer);
// Result: [0, 3, 4, 8, 9, 14, 23, 25]

Properties

.dataBuffer : StorageBufferNode

The storage buffer to compute prefix sum on (modified in place).

.count : number

Number of elements in the buffer.

.workgroupSize : number

Number of threads per workgroup.

.itemsPerWorkgroup : number

Number of elements processed per workgroup (2 per thread).

.workgroupCount : number

Number of workgroups needed.

.localStorage : WorkgroupArrayNode

Workgroup shared memory for local scan.

.blockSumsBuffer : StorageBufferNode

Buffer storing each workgroup's total sum.

.blockPrefixSum : ComputePrefixSum

Recursive prefix sum for block sums.

.localScanFn : ComputeNode

Local scan compute function.

.addBlockSumsFn : ComputeNode

Add block sums compute function.

.initialized : boolean

Whether initialized.

Methods

init#

init(renderer : WebGPURenderer)

Initializes the prefix sum for the given renderer.

Parameters
rendererWebGPURenderer
The Three.js WebGPU renderer.

compute#

compute(renderer : WebGPURenderer)

Computes the prefix sum in a single call.

Parameters
rendererWebGPURenderer
The Three.js WebGPU renderer.

dispose#

dispose()

Disposes of GPU resources held by this instance.