Abstract
We present a simple and fast algorithm for generating randomly distributed points on a triangle mesh with probability density specified by a two-dimensional texture. Efficiency is achieved by resampling the density texture on an adaptively subdivided version of the input mesh.
This allows us to generate the samples up to 40x faster than the rejection sampling algorithm, the fastest existing alternative. We demonstrate the algorithm in two applications: fast placement of hair roots on a surface and sampling of illumination from a complex luminaire.
Part of our mesh sampling procedure is a new general acceleration technique for drawing samples from a 1D discrete probability distribution whose utility extends beyond the mesh sampling problem.