How can I sample uniformly from a surface? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T19:08:08Z http://mathoverflow.net/feeds/question/9991 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface How can I sample uniformly from a surface? Hadley 2009-12-29T00:11:45Z 2010-07-07T01:36:29Z <p>Given an equation of a parametric surface, is there a general way to sample of points uniformly distributed on that surface?</p> <p>I'm interested in this problem for purposes of visualisation - rather than attempting to attempt to triangulate the surface and display with polygons, display a dense sample of points. This makes it easier to generalise to >3d.</p> <p>Here's an example of a surface I'd like to display: the Klein bottle. </p> <pre><code>u = [-pi, pi] v = [-pi, pi] x1 = (r * cos(v) + a) * cos(u), x2 = (r * cos(v) + a) * sin(u), x3 = r * sin(v) * cos(u/2), x4 = r * sin(v) * sin(u/2) </code></pre> <p>(where r and a are parameters that control the shape of the overall surface)</p> http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface/9993#9993 Answer by lhf for How can I sample uniformly from a surface? lhf 2009-12-29T01:14:52Z 2009-12-29T01:14:52Z <p>Triangulate it and sample each triangle with a density relative to the total area.</p> http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface/9994#9994 Answer by David Eppstein for How can I sample uniformly from a surface? David Eppstein 2009-12-29T01:20:14Z 2009-12-29T01:20:14Z <p>It's not quite the same as generating a single random point, but: if you generate (a Poisson sample of) uniformly random lines and then take all intersection points of the lines with the surface, you'll get (a Poisson sample of) uniformly random points on the surface.</p> http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface/10001#10001 Answer by fedja for How can I sample uniformly from a surface? fedja 2009-12-29T04:13:16Z 2009-12-29T04:13:16Z <p>The problem boils down to the simulation of the point in a 2D domain with the density proportional to some easily computable function $f(x)$ (the area distortion coefficient of the mapping from the parameter domain to the surface). The simplest way is to simulate a random point $x$ in some square containing the domain, look at whether the point is in the domain, and, if it is, keep it with the probability $f(x)/M$ where $M$ is some number greater than all values of $f$. If the parameterization is reasonable enough, this should work pretty well. What examples do you have in mind?</p> http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface/10005#10005 Answer by fuzzytron for How can I sample uniformly from a surface? fuzzytron 2009-12-29T05:19:16Z 2009-12-29T05:19:16Z <p>This paper may be of interest to you:</p> <p>J. Arvo, <a href="http://www.ics.uci.edu/~arvo/papers/notes2001.pdf" rel="nofollow">Stratified Sampling of 2-Manifolds</a></p> <p>It directly answers your question, though you may need to do some of the computations numerically depending on how complicated your surfaces are. Moreover, stratifying your samples will help the sampling <em>look</em> uniform -- sampling uniformly over the entire domain tends to look blotchy.</p> http://mathoverflow.net/questions/9991/how-can-i-sample-uniformly-from-a-surface/10032#10032 Answer by Alekk for How can I sample uniformly from a surface? Alekk 2009-12-29T12:54:38Z 2009-12-29T12:54:38Z <p>just to develop what Fedja said above:</p> <p>say you have a map $\phi(x,y)=(u(x,y),v(x,y),w(x,y))$ from $D = [a;b]^2$ to $\mathbb{R}^3$ that represents a surface (Klein bottle in your initial example). The infinitesimal surface $(x;x+dx) \times (y;y+dy)$ is mapped to a surface of area $|\partial_x \Phi \wedge \partial_y \Phi| dx dy = A(x,y) dx dy$. So it would suffice to sample points inside $D$ distributed according to a probability distribution $p(x,y) \propto A(x,y) dx dy$.</p> <p>1: as Fedja mentioned it, you can use a <a href="http://en.wikipedia.org/wiki/Rejection%5Fsampling" rel="nofollow">rejection sampling</a> approach - you just need to find a bound on $\|A\|_{\infty}$, which should be very easy since $D$ is simple.</p> <p>2: you can use a <a href="http://en.wikipedia.org/wiki/Metropolis%25E2%2580%2593Hastings%5Falgorithm" rel="nofollow">MCMC</a> approach, which is equally easily implemented (e.g. independence sampler) - might be a little bit faster. </p>