StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>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</p> <p>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. </p> <p>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.</p> <p>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.</p> <p>User-specified cuts can be handled as edge deletions before the tree step.</p> <p><img src="https://lh6.ggpht.com/_fJRu319XW2Q/Si3uI6phGKI/AAAAAAAAAJU/Uxxx26nH36k/s800/unfolding.png" alt="diagram of unfolding a tetrahedron"></p> <p>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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload