Hacker News Reader

Comment by andybak | Hacker News Reader

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 ) 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.

View on HN

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-algorith....)

> 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://mathworld.wolfram.com/Unfolding.html

- http://web.york.cuny.edu/~malk/unfolding.html

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.

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

You may want to look at [1] as a start.

[1] https://michaelwalczyk.com/project-unfolding.html

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

Reply on news.ycombinator.com