Random sampling inside a closed mesh

[stla]

Hello,

I'd like to have your advice about the following algorithm to sample some points inside the volume bounded by a closed mesh:

• decompose the mesh into convex parts
• decompose each convex part into tetrahedra with Delaunay
• once the above is done, sample as follows:
  • pick one tetrahedron with probability proportional to its volume
  • sample one point inside this tetrahedron

This should be correct, but maybe you have a better idea, a more efficient method?

[sloriot]

I would randomly sample points within the bbox of the mesh and use Side_of_triangle_mesh to keep only random points in the volume bounded by the mesh.

[stla]

You mean a rejection sampling, right? That indeed could be more efficient in some cases, but not always, when the mesh occupies a small fraction of the bounding box. E.g. a torus with a big hole. Worst if it is not "aligned" with the axes (that would enlarge the bounding box).

[MaelRL]

You could use a grid or an octree instead of a bbox, and only sample cells that intersect your volume to avoid these cases