12
$\begingroup$

Given an equation of a parametric surface, is there a general way to sample of points uniformly distributed on that surface?

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.

Here's an example of a surface I'd like to display: the Klein bottle.

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)

(where r and a are parameters that control the shape of the overall surface)

$\endgroup$

5 Answers 5

7
$\begingroup$

This paper may be of interest to you:

J. Arvo, Stratified Sampling of 2-Manifolds

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 look uniform -- sampling uniformly over the entire domain tends to look blotchy.

$\endgroup$
2
  • $\begingroup$ Perfect - exactly what I was looking for. $\endgroup$
    – Hadley
    Dec 29, 2009 at 8:31
  • 4
    $\begingroup$ For anyone following this old thread, the link above is dead, but the article can still be found e.g. at this link. $\endgroup$ Jan 23, 2014 at 13:48
5
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ For the fun, I just tried this approach with a spherical cap. There is no problem with the simulation speed or the distribution of points but the output looks quite terrible to the eye: some strange collection of dots that undergoes incomprehensible transformations when rotating the picture. Certainly not something you would want to "display"... $\endgroup$
    – fedja
    Dec 29, 2009 at 4:40
  • $\begingroup$ I'm not sure I understand your approach. What is the area distortion coefficient? $\endgroup$
    – Hadley
    Dec 29, 2009 at 8:15
  • $\begingroup$ If $\psi$ is the parameterization map, it is just the square root of the determinant of $(D\psi)^TD\psi$ where $D$ is the differential of $\psi$. I call it the area distortion coefficient because the image of a small neighborhood of a point $x$ in the parameterization domain has the area approximately equal to this coefficient times the area of the neighborhood. The advantage here is that you do not need to convert your parameterization into an area-preserving map (which asks for integration, etc), just to make sure that the area distortion coefficient doesn't vary too much. $\endgroup$
    – fedja
    Dec 29, 2009 at 14:05
  • $\begingroup$ Ah, I see. Thanks for the explanation. $\endgroup$
    – Hadley
    Dec 29, 2009 at 15:46
2
$\begingroup$

Triangulate it and sample each triangle with a density relative to the total area.

$\endgroup$
2
  • $\begingroup$ Note that you want to triangulate the region of R^2 you are parameterizing by, but then map each triangle in by the parametric equations. So your surface will still be curved, and will not look like a bunch of triangles. $\endgroup$ Dec 29, 2009 at 1:57
  • $\begingroup$ This is what I meant. Thanks for the details. $\endgroup$
    – lhf
    Dec 29, 2009 at 10:58
1
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ But computing intersections of lines with a parametrized surface is "fun"... $\endgroup$ Dec 29, 2009 at 1:22
0
$\begingroup$

Just to develop what Fedja said above:

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

  1. as Fedja mentioned it, you can use a rejection sampling approach - you just need to find a bound on $\|A\|_{\infty}$, which should be very easy since $D$ is simple.

  2. you can use a MCMC approach, which is equally easily implemented (e.g. independence sampler) - might be a little bit faster.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.