Uniform mesh sampling

[mweatherley]

Objective

Allow random sampling from the surfaces of triangle meshes.

Solution

This has two parts.

Firstly, rendering meshes can now yield their collections of triangles through a method Mesh::triangles. This has signature

pub fn triangles(&self) -> Result<Vec<Triangle3d>, MeshTrianglesError> { //... }

and fails in a variety of cases — the most obvious of these is that the mesh must have either the TriangleList or TriangleStrip topology, and the others correspond to malformed vertex or triangle-index data.

With that in hand, we have the second piece, which is UniformMeshSampler, which is a Vec3-valued distribution that samples uniformly from collections of triangles. It caches the triangles' distribution of areas so that after its initial setup, sampling is allocation-free. It is constructed via UniformMeshSampler::try_new, which looks like this:

pub fn try_new<T: Into<Vec<Triangle3d>>>(triangles: T) -> Result<Self, ZeroAreaMeshError> { //... }

It fails if the collection of triangles has zero area.

The sum of these parts means that you can sample random points from a mesh as follows:

let triangles = my_mesh.triangles().unwrap();
let mut rng = StdRng::seed_from_u64(8765309);
let distribution = UniformMeshSampler::try_new(triangles).unwrap();
// 10000 random points from the surface of my_mesh:
let sample_points: Vec<Vec3> = distribution.sample_iter(&mut rng).take(10000).collect();

Testing

Tested by instantiating meshes and sampling as demonstrated above.

---

Changelog

• Added Mesh::triangles method to get a collection of triangles from a mesh.
• Added UniformMeshSampler to bevy_math::sampling. This is a distribution which allows random sampling over collections of triangles (such as those provided through meshes).

---

Discussion

Design decisions

The main thing here was making sure to have a good separation between the parts of this in bevy_render and in bevy_math. Getting the triangles from a mesh seems like a reasonable step after adding Triangle3d to bevy_math, so I decided to make all of the random sampling operate at that level, with the fallible conversion to triangles doing most of the work.

Notably, the sampler could be called something else that reflects that its input is a collection of triangles, but if/when we add other kinds of meshes to bevy_math (e.g. half-edge meshes), the fact that try_new takes an impl Into<Vec<Triangle3d>> means that those meshes just need to satisfy that trait bound in order to work immediately with this sampling functionality. In that case, the result would just be something like this:

let dist = UniformMeshSampler::try_new(mesh).unwrap();

I think this highlights that most of the friction is really just from extracting data from Mesh.

It's maybe worth mentioning also that "collection of triangles" (Vec<Triangle3d>) sits downstream of any other kind of triangle mesh, since the topology connecting the triangles has been effectively erased, which makes an Into<Vec<Triangle3d>> trait bound seem all the more natural to me.