I have a list a vertices and a list of triangles. I'd like to split this single mesh into, say 5, randomly shaped meshes. When the 5 randomly shaped meshes are in place the sphere should all line up and look like 1 solid mesh.
I need a algorithm to do this programmatically, not a tool to do it form me. Any pointers would be great!
Select 3 random points and split along that plane. What is the problem?
You could make a crack by walking a random walk across the edges, until the number of pieces you want is achieved. If you want to have mostly big pieces, you could modify the randomness of the walk by reducing the attractiveness of edges that are close to an existing crack.
Similar to Svante's proposal but a slightly different approach:
This appears to me to be the simplest to implement, while still resulting in nice puzzle pieces. For added random-ness, you could add a probability, of visiting each adjacent vertex.
Nevertheless, any "too random" approach might result in heavily concave pieces, like very long pieces consisting only of a long strip of single triangles; and pieces with deep ugly thin cuts into them. You should possibly specify another question on how to make nice puzzle pieces (and what nice puzzle pieces are!) if you care for that.
When you split a triangle along a plane you end up in one of two situations: either the plane doesn't intersect either line segments in the triangle or it intersects exactly two line segments. Only triangles that are intersected are interesting.
If you have triangle (A, B, C), with A, B and C being vertices.
Assume that the plane intersects the line segments (A, B) and (A, C) in the points D and E. Define a vertex, F, between B and C (for example B + (C - B) / 2), but any vertex on the line segment between B and C will do).
Your new triangles are then the following (A, D, E), (B, D, F), (D, E, F) and (C, E, F)