Given an array of elements, the stream compaction algorithm creates a new array with elements that meet a certain criteria, e.g. non null. It also preserve the order of original elements.
Stream compaction is widely used in path tracing, collision detection, sparse matrix compression, etc. It can also reduce data transferred from GPU to CPU.
The C++ STL counterpart for stream compaction is std::copy_if
.
Steps
- Compute a temporary array containing 0s and 1s
- Run exclusive scan to the temporary array
- scatter
- result of scan is index into final array
- only write an element if temporary array has a 1