Jaroslav Křivánek

Fast Random Sampling of Triangular Meshes

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).

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.

Publication

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

Links and Downloads

paper

28MB pdf

Acknowledgments

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