Creating sample points on a 3d shape

Question

Can somebody recommend an algorithm that creates a point sample from a 3D solid which is represented by triangles? The point sample should be nearly uniformly distributed on the surface and it should be guaranteed that no ball with some given radius fits through the point sample.

Answer 1

The simplest method that I know of for doing this is a two stage process. 1) unfold the mesh back to a two dimensional representation, and 2) use a sampling technique that results in approximately uniformly distributed points on the surface.

The unfolding process is most likely going to be the most challenging step if you need to implement everything yourself. Tools like blender and meshlab include tools to do this because the problem is related to generation of UV texture co-ordinates in 3D graphics. I believe there are a number of algorithms and techniques for approaching such problems, but selecting the best may be a case of trial and error depending on how degenerate your triangles are.

The uniform distribution of points on the resultant unfolded mesh is then easy - you can use a low discrepancy sampling sequence (such as the Halton or Hammersly sequence) to produce an almost uniform distribution of points over your space, and rejection sampling to remove any points that don't fall within the unfolded mesh.

You'll need to do some extra checks that the seams of your mesh in the unfolding retain an appropriate level of sampling to ensure that your requirements of the minimal ball are met, when it is refolded.

From past experience the caveat of this approach is that if your mesh isn't manifold (ie/ it has cracks, self intersections or t-junctions), you'll almost certainly have to clean these up before you start. For very large data sets this can be prohibitively time consuming.