Originally published at: https://developer.nvidia.com/blog/learn-more-about-reservoir-sampling-in-free-ray-tracing-gems-ii-chapter/
As the August 4 release date for Ray Tracing Gems II nears, NVIDIA is offering another free chapter from the book to celebrate. This time, the topic is reservoir sampling, which is a family of algorithms that, given a stream of N elements, randomly select a K-element subset in a single pass. Usually, K is defined as a small constant, but N need not be known in advance.