Triangle Rejection Sampling for Density‐Equipped Meshes on GPU

Abstract Non‐uniform random point sampling on 3D surfaces offers a powerful framework to capture complex distributions such as fur seeds, scattered geometric instances or light emitter flux. As most other on‐surface signals, practitioners design such distribution by the means of 2D maps, parameterized over the surface, and indicating locally the desired point density that should be synthesized, along with any primitive‐specific attribute such as fiber thickness or instance size. Numerous application scenarios imply large such point sets which would ideally be generated in real‐time to be consumed immediately by downstream applications. We propose a method to distribute such white noise point sets under non‐uniform densities, designed to cope with parallel GPU execution and able to produce, in real time, hundreds of millions of density‐constrained samples over arbitrary 3D triangle meshes. At the core of our method, we introduce a stratified rejection sampling scheme where triangles act as strata, greatly improving the locality of the sampling process, and significantly diminishing the probability of rejecting a sample. Our method relies on a series of simple GPU kernels, introducing a new fast and exact texel‐triangle overlap computation method as well as the notion of unordered cumulative sum. As a result, our approach provides real‐time systems with the ability to tailor, on‐the‐fly, highly dynamic density distributions in the form of procedural or raster maps. We illustrate its application with interactive fur design, geometry instancing, and Monte Carlo light sampling.