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.

Dalt

Is it a problem if the domain is oversampled? IE/ are you looking for the minimal number of points to achieve the required level of sampling? – Harrietteharrigan

Yes, the domain can be oversampled and an optimal solution is not required as long as the sampling is reasonable when we look at it. – Dalt

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.

Harrietteharrigan

Answer 2

If you don't need optimal performance (or you can precompute the points) and don't want to write much of code you can use some monte-carlo variation.

You can start from many random points inside of the model's bounding box, or organized into grid with density of your ball's radius.

Then for every point:

• Find the closest triangle and the distance
• If it's too far - discard it
• If it's not - project it on the triangle

I know it's quite heavy but the code should be relatively simple.

---

On the second thought there's another simple method:

• For every triangle compute the length of its edges.
• If the edges are too long - split the triangle (into 2, or 4 - it depends on your needs).
• Add resulting split vertex(vertices) into points list.
• Do the same with resulting triangles.
• At the end add also your mesh vertices into the list.

It won't give your ideal distribution but it's quite simple to write and should work :) .

Wheelsman

Answer 3

This task resembles image dithering - the approximation of some constant grey-level image with a random set of black dots. And as in dithering some trivial Monte-Carlo approaches do no behave good, because completely random independent points tend to cluster together creating undesirable visual patterns. More scientifically, it can be said that the spectrum of such random points is white, while blue noise is good for dithering as having small low-frequency energy.

As to unfolding the mesh back to a two dimensional representation, it is not possible in every case especially with closed surfaces having genus more than 0 (not sphere-like).

And the approach with the subdivision of long mesh edges does work good on practice, but only if after each subdivision, the mesh quality is improved locally following the ideas of Delaunay triangulation, which maximize the minimal angle in the triangles.

Here is an example:

• blue - original triangular mesh,
• green - the mesh after subdivision,
• red - vertices of subdivided mesh converted in point cloud. (The example was made in MeshInspector application based on some open-source geometric library for operations like this one.)

Galloway