views:

823

answers:

3

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.

+5  A: 
eed3si9n
Awesome! Thanks.
Nick Johnson
I needed this to unwrap my meshes' net texture space into an atlas. You're a lifesaver.
Mads Elvheim
+3  A: 
Theran
Good answer, thanks! It's not explicit from your answer that you intend that edges be removed until the graph is a tree, but that seems to be the implication. I presume a minimum-spanning-tree algorithm is appropriate.Also, your answer implies you've written this before - personal project, or is it available somewhere? :)
Nick Johnson
Actually, minimum spanning tree doesn't work because it doesn't minimize the number of folds from the center. I've updated my answer to clarify this. As far as removing edges from the mesh goes, this algorithm doesn't modify the original mesh. I found it easier to just generate the flattened mesh from scratch rather than maintain all the correct invariants while splitting edges.Lastly, I have indeed written this before as a Blender plug-in with the intent of releasing it, but got distracted before finishing the tabs part. I'll grab it off my old HD and post it.
Theran
Ok, I finally pulled it out and put it up at http://code.google.com/p/unfolder/
Theran
A: 

I know this is not an answer, but it is related. Ex-SGI graphics guy Paul Haeberli's Lamina program is a solution for this problem.

goger
Wow. Neat program, but $353 is a bit much for use in papercraft. ;)
Nick Johnson