Jaroslav Křivánek

Fast Random Sampling of Triangular Meshes

Martin Šik
Charles University in Prague
Faculty of Mathematics and Physics
Jaroslav Křivánek
Charles University in Prague
Faculty of Mathematics and Physics

Our fast mesh sampling algorithm can place up to 78 million random sample points per second on a triangle mesh. We can use the algorithm, for example, to interactively distribute hair roots on a surface (a) or for sampling illumination from a complex luminaire, such as a projected HDR image, where uniform sampling produces a noisy image (b).


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.


Martin Šik and Jaroslav Křivánek. Fast Random Sampling of Triangular Meshes. Pacific Graphics, Short Papers 2013 ... DOI | BibTeX

Links and Downloads

 28MB pdf


This work was supported by the Czech Science Foundation grant P202-13-26189S and by the Charles University Grant Agency (project number 1362413).