3 ms·

Does anyone know what the name of the algorithm would be for unfolding arbitrary polyhedra? I've wanted to implement this for my own library ( https://github.co

Does anyone know what the name of the algorithm would be for unfolding arbitrary polyhedra? I've wanted to implement this for my own library ( https://github.com/IxxyXR/polyhydra-core https://github.com/IxxyXR/polyhydra-core ) and I could never find the right thing to search for. I'm assuming it reduces to a problem in graph traversal with some additional spatial constraints but I wanted to find some references before I tried to do my own dumb brute force solution.

Someone 4y ago
> Does anyone know what the name of the algorithm would be for unfolding arbitrary polyhedra? AFAIK Shepard’s conjecture “every convex polyhedron has an unfolding without overlap” is still open, so I’m not sure that exists. Links you may or may not have seen: - https://en.wikipedia.org/wiki/Net_(polyhedron) https://en.wikipedia.org/wiki/Net_(polyhedron) - https://mathworld.wolfram.com/Unfolding.html https://mathworld.wolfram.com/Unfolding.html - http://web.york.cuny.edu/~malk/unfolding.html http://web.york.cuny.edu/~malk/unfolding.html
- andybak 4y ago
  Yeah. I'm under no illusions that there's always a single connected solution to be easily found. I suppose I'm wondering if there's a good strategy other than just breadth-first trial and error. Thanks for the links. I'll check them out.
viscousviolin 4y ago
I found a book on folding algorithms a while back. It's called "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" by Demaine and O'Rourke. I haven't gone through it myself yet, but I feel like they should have an answer for you. (They also have a really nice course on MIT's Open Courseware that covers their book: https://ocw.mit.edu/courses/6-849-geometric-folding-algorithms-linkages-origami-polyhedra-fall-2012/ https://ocw.mit.edu/courses/6-849-geometric-folding-algorith....)
virtualritz 4y ago
You may want to look at [1] as a start. [1] https://michaelwalczyk.com/project-unfolding.html https://michaelwalczyk.com/project-unfolding.html
YeGoblynQueenne 4y ago
I'm going to take a big, wild guess on a subject I know nothing about and bet that it's probably a giant ball of heuristics guiding a search (probably DFS with iterative deepening) over the space of unfoldings, or something dumb, but effective, like that. After all, the point here is to turn a 3d model into a papercraft model. That's not a formal problem, like tying your shoelaces so they don't get easily untied is not a knot theory problem, as such, or putting all your stuff in your bag is not the knapsack problem. Anyway strong heuristics are the bread and butter of Computer Science, or in any case we have far more heuristics than we have principled algorithms. So I think I have a good chance to win my bet :P
alanbernstein 4y ago
Not sure about arbitrary polyhedra, but you may be interested in this: https://www.win.tue.nl/~vanwijk/myriahedral/ https://www.win.tue.nl/~vanwijk/myriahedral/

Someone 4y ago

> Does anyone know what the name of the algorithm would be for unfolding arbitrary polyhedra? AFAIK Shepard’s conjecture “every convex polyhedron has an unfolding without overlap” is still open, so I’m not sure that exists. Links you may or may not have seen: - https://en.wikipedia.org/wiki/Net_(polyhedron) https://en.wikipedia.org/wiki/Net_(polyhedron) - https://mathworld.wolfram.com/Unfolding.html https://mathworld.wolfram.com/Unfolding.html - http://web.york.cuny.edu/~malk/unfolding.html http://web.york.cuny.edu/~malk/unfolding.html

andybak 4y ago
Yeah. I'm under no illusions that there's always a single connected solution to be easily found. I suppose I'm wondering if there's a good strategy other than just breadth-first trial and error. Thanks for the links. I'll check them out.

viscousviolin 4y ago

I found a book on folding algorithms a while back. It's called "Geometric Folding Algorithms: Linkages, Origami, Polyhedra" by Demaine and O'Rourke. I haven't gone through it myself yet, but I feel like they should have an answer for you. (They also have a really nice course on MIT's Open Courseware that covers their book: https://ocw.mit.edu/courses/6-849-geometric-folding-algorithms-linkages-origami-polyhedra-fall-2012/ https://ocw.mit.edu/courses/6-849-geometric-folding-algorith....)

virtualritz 4y ago

You may want to look at [1] as a start. [1] https://michaelwalczyk.com/project-unfolding.html https://michaelwalczyk.com/project-unfolding.html

YeGoblynQueenne 4y ago

I'm going to take a big, wild guess on a subject I know nothing about and bet that it's probably a giant ball of heuristics guiding a search (probably DFS with iterative deepening) over the space of unfoldings, or something dumb, but effective, like that. After all, the point here is to turn a 3d model into a papercraft model. That's not a formal problem, like tying your shoelaces so they don't get easily untied is not a knot theory problem, as such, or putting all your stuff in your bag is not the knapsack problem. Anyway strong heuristics are the bread and butter of Computer Science, or in any case we have far more heuristics than we have principled algorithms. So I think I have a good chance to win my bet :P

alanbernstein 4y ago

Not sure about arbitrary polyhedra, but you may be interested in this: https://www.win.tue.nl/~vanwijk/myriahedral/ https://www.win.tue.nl/~vanwijk/myriahedral/