Decomposing a 3d mesh into a 2d net
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
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
