Decomposing a 3d mesh into a 2d net

Question

Suppose you have a 3 dimensional object, represented as a 3d mesh in some common file format. How would you devise an algorithm to decompose the mesh into one or more 2d 'nets' - that is, a 2-dimensional representation that can be cut out and folded to create the original 3d object.

Amongst other things, the algorithm would need to account for:

• Multiple possible decompositions for any given object
• Handling fitting a mesh into fixed size canvases (sheets of paper).
• Recognizing when two panels in the net would overlap (and are thus invalid).
• Breaking a mesh up into multiple nets if they can't be represented as a single one, due to overlap or page size constraints.
• Generating tabs in the appropriate places, for attaching adjacent faces.

The obvious degenerate case is simply to create one net per face, with tabs on half the edges. This isn't ideal, obviously: The ideal case is a single continuous net. The reality for complex shapes is likely to be somewhere in the middle.

I realize that finding the optimal net (fewest nets / least pages) is probably computationally expensive, but a good heuristic for finding 'good enough' nets would suffice.

Answer 1

When I read your question, the words "automatic papercraft algorithm" came to me. So I googled it and found Papercraft Models using Generalized Cylinders (pdf) by Massarwi et al.

We propose a new method for producing unfolded papercraft patterns of rounded toy animal figures from triangulated meshes by means of strip-based approximation. Although in principle a triangulated model can be unfolded simply by retaining as much as possible of its connectivity while checking for intersecting triangles in the unfolded plane, creating a pattern with tens of thousands of triangles is unrealistic. Our approach is to approximate the mesh model by a set of continuous triangle strips with no internal vertices. Initially, we subdivide our mesh into parts corresponding to the features of the model. We segment each part into zonal regions, grouping triangles which are similar topological distances from the part boundary. We generate triangle strips by simplifying the mesh while retaining the borders of the zonal regions and additional cut-lines. The pattern is then created simply by unfolding the set of strips. The distinguishing feature of our method is that we approximate a mesh model by a set of continuous strips, not by other ruled surfaces such as parts of cones or cylinders. Thus, the approximated unfolded pattern can be generated using only mesh operations and a simple unfolding algorithm. Furthermore, a set of strips can be crafted just by bending the paper (without breaking edges) and can represent smooth features of the original mesh models.

There is also an earlier related paper called Paper craft models from meshes (9MB pdf) by Shatz et al.

This paper introduces an algorithm for segmenting a mesh into developable approximations. The algorithm can be used in various applications in CAD and computer graphics. This paper focuses on paper crafting and demonstrates that the algorithm generates approximations that are developable, easy to cut, and can be glued together. It is also shown that the error between the given model and the paper model is small.

Source: http://www.ee.technion.ac.il/~ayellet/images/sel-papers-pic-5.jpg

Answer 2

The algorithms eed3si9n linked to will generate nice reasonable papercraft meshes from complicated geometry. If you'd like to unfold the mesh exactly as it is modeled, such as for polyhedra models, then here's a relatively simple technique for unfolding any mesh as it stand

Construct a graph from your source mesh where each face is a vertex in the graph, and two vertices are connected if they share a common edge in the mesh. One of these graphs represents an unfoldable mesh if and only if it has no loops, i.e. it is a tree.

A good tree represents the fewest fold lines to get to the farthest face from the starting point, since each fold represents error that will accumulate in the finished model. Dijkstra's algorithm is good here, but minimum spanning tree doesn't work. With each edge equally weighted all trees are minimum spanning trees, even one that would unfold your mesh into one big spiral. As you glued the model together, errors would build up until the last few faces didn't fit at all.

Once you have the tree, start by drawing your starting face at the origin. Then walk the tree and add the new faces by calculating the new vertex as the intersection of two circles with radii corresponding to the lengths of the edges in the original mesh. Locations for tabs correspond to edges that were in the original mesh, but are not in the flattenable tree.

User-specified cuts can be handled as edge deletions before the tree step.

Some downsides of this technique are that it will happily create overlapping parts in the flat pattern, and it is dependent on finding a good starting face. I tried Floyd-Warshal to find a minimum-diameter face to start from, but its O(n^3) behavior made for excessively long coffee breaks. The overlapping parts could be dealt with by marking that branch of the tree as "incomplete", skipping it, and re-running the algorithm on all incomplete faces again.