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.