Possible Seam Algorithms

A friend recently made it obvious that good start to cutting a mesh would be to take the graph of its edges and construct something called a Minimum Spanning Tree, or MST. To visualize what an MST is, consider each edge to be a wire. The MST computes the minimum amount of wiring required to connect every vertex (Figure 7).

Figure 7

While using this set of edges as seams would be horrifying when it came time to paint it, it may be useful as a good starting point for calculating a nice simple set of seams. By iteratively removing each set of leaf nodes (vertices with only one edge connected to them), stopping when you have only two leaf nodes left, you will have the 'backbone' of the MST (Figure 8). I have not yet tested the idea, but this backbone should make a nice guide for cutting the mesh.

Figure 8

A second algorithm I'm trying is rather odd. From a set of selected polygons, the selection grows outward topologically. Once the selection wraps around the model, its borders begin to meet at certain edges. These edges are stored as seam canidates (Figure 9). While these edges alone are usually not suitable, simply extending them until they intersect at certain vertices could possibly make an adequate set of seam borders for cutting and unwrapping (Figure 10).

Figure 9

Figure 10

While neither of these methods will be perfect, one method I have not yet implemented in code may be most promising. By cutting a ring into an object at any point, then using a type of spring-based unwrapping (edges are converted into springs, so the mesh fights to expand in 2D, and organizes itself into the best shape), one may be able to find maximum stress points at polygon edges caused by the unwrapping process. These edges would, of course, be more optimal to cut than any others.