Triangle Rejection Sampling for Density‐Equipped Meshes on GPU
- 19 September 2025
- journal article
- Published by Wiley in Computer Graphics Forum
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.Keywords
This publication has 7 references indexed in Scilit:
- GPU Programming Primitives for Computer Graphics2023
- Visibility‐Aware Progressive Farthest Point Sampling on the GPUComputer Graphics Forum, 2019
- A Survey of Blue-Noise Sampling and Its ApplicationsJournal of Computer Science and Technology, 2015
- Performance Characterization and Optimization of Atomic Operations on AMD GPUs2011
- New Intersection Algorithm of Convex Polygons Based on Voronoi Diagrams2006
- Data parallel algorithmsCommunications of the ACM, 1986
- A new linear algorithm for intersecting convex polygonsComputer Graphics and Image Processing, 1982