Hacker News new | past | comments | ask | show | jobs | submit login
Algorithm generates practical paper-folding patterns to produce any 3D structure (mit.edu)
371 points by edwinksl on June 22, 2017 | hide | past | web | favorite | 48 comments



I hope the algorithm becomes published and unencumbered by any onerous restrictions. I understand that this is a unique system, though - and likely one where patents and other "protections" could be taken out for the method and implementations.

But right now, all we have to "play with" is a window binary. I understand that there is supposed to be a paper published in the future; I would love to see this algorithm implemented into something more "universal", if nothing else.

Again, though, I can also see why such an algorithm could be protected - I am certain there are more than a few commercial applications for it, and perhaps in areas that have little to nothing to do with origami (for instance - and I am probably completely off base here - could this be applied in some manner to understanding protein folding?).


> could this be applied in some manner to understanding protein folding? Ehhh. Probably not? It's hard to say without the algorithm, really.

The main problem (apart from not modelling any of the chemistry of proteins) would be what your target shape would be. You can consider a folded protein to be the 'blob' formed by taking the surface formed by rolling a water across the outer atoms. Or you could consider just the backbone as a kind of tube.

An origami pattern for just the surface would have no internals. On the other hand, the pattern for the backbone would tell you nothing about how the sidechains and backbone interact.


Why would it? The transformation here is different. Flat, 2d manifold to a nondifferentiable surface in 3-space. Vs. 1d manifold embedded in 3-space. All they have in common is the term of art 'folding' and embedding into 3 space from q lower dimension.


Given that both authors are pure mathematicians, rather than engineers, I don't have the impression that they really care to monetize this. MIT could possibly claim patents on their behalf though.


> Given that both authors are pure mathematicians ..

Erik Demaine is a computer scientist: https://youtu.be/3e1ZF1L1VhY


theoretical computer scientist


That's the only type of computer scientist. Anything else is, say, a programmer or a software developer. Which there is nothing wrong with.


I believe he exists.


Erik could toss it to someone in CSAIL to monetize, if he wanted to. There was a group I worked with that collaborated with him for the math for some folding robots.


This is more likely to be applied to topology optimization imo


Check out [1] for videos of Erik Demaine's lectures on folding. Also, I highly recommend the videos for the algorithms and data structures courses he's taught/co-taught ([2] for example)

[1] https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[2] https://ocw.mit.edu/courses/electrical-engineering-and-compu...



That is a spectacularly well-presented paper (and I haven't even attempted to read it yet!). I love the visual overview of the algorithm in figure 3.


Thanks for finding it!


Gah, I won't even read it. I was thinking about that for a while, I don't want to spoil myself. Happy to see Demaine at it again.


Ages ago...

I wrote print production (prepress) software. One of my inventions was an algorithm that converted book binding steps into impositions, as needed. (All previous solutions relied on catalogs of manually created "templates", for reuse, customization, etc.)

https://en.wikipedia.org/wiki/Imposition

I'm now very curious if this general purpose origami algorithm can be used for the same purpose.


There was a really great NOVA episode, "The Origami Revolution" [1][2], that I believe covered this exact same algorithm. As I recall at the time of the recording for the NOVA episode it was still under development.

[1] http://www.pbs.org/wgbh/nova/physics/origami-revolution.html

[2] http://www.pbs.org/video/2365955827/


Wait is the algorithm/paper out already? I'm really interested in getting my hands on it. As I understand it Demaine and Tomohiro Tachi are presenting it at the Symposium on Computational Geometry, July 4-7. I thought the paper comes out then?

EDIT: teechap found it


NO! There is now a pay wall for me to view the videos! $5 or more more a month donation levels.

Is this nation wide or only for my local area?


For what it's worth I got it too. Is this just for some content?


A video of one of the authors folding a bunny model like the one in the article:

https://www.youtube.com/watch?v=GAnW-KU2yn4


Excellent find, and I'd wager since it's one of the authors (Tachi) it IS the bunny model from the paper.


we need a folding robot.


So this is a computer that is a 3D Paper Printer?

Jokes aside [1] the mathematics of paper folding is extremely interesting. The most interesting thing is that you can solve fourth degree equations with origami [2] .

[1]https://en.wikipedia.org/wiki/Mathematics_of_paper_folding [2] https://en.wikipedia.org/wiki/Huzita%E2%80%93Hatori_axioms


The science-fiction fan in me is now imagining a robot whose structure is a flat sheet of material, that can reconfigure itself into any form it needs.


You could use shape memory alloys to control join orientation, have one per orientation at the joint and have the correct one "remember" to allow a structure to reconfigure itself.


Exactly. Transformers comming up


I was wondering what Robert Lang [1] makes of this. Looks like he approves of it. “It’s very impressive stuff,” says Robert Lang, one of the pioneers of computational origami and a fellow of the American Mathematical Society, who in 2001 abandoned a successful career in optical engineering to become a full-time origamist. “It completes what I would characterize as a quest that began some 20-plus years ago: a computational method for efficiently folding any specified shape from a sheet of paper. Along the way, there have been several nice demonstrations of pieces of the puzzle: an algorithm to fold any shape, but not very efficiently; an algorithm to efficiently fold particular families of tree-like shapes, but not surfaces; an algorithm to fold trees and surfaces, but not every shape. This one covers it all! The algorithm is surprisingly complex, but that arises because it is comprehensive. It truly covers every possibility. And it is not just an abstract proof; it is readily computationally implementable.”

[1] [ https://en.wikipedia.org/wiki/Robert_J._Lang ]


Solving origami (2d) was the task of 2017 ICFP programming contest. I wonder how this MIT approach would work for that task.

http://icfpc2016.blogspot.com.au/2016/08/task-description.ht...


Anyone have recommendations on: "How to Fold It: The Mathematics of Linkages, Origami, and Polyhedra" by Joseph O'Rourke?

http://howtofoldit.org/


Beautiful book, my copy came folded in half (I really appreciate what I hope was an ironic FU from the Amazon drone).

It would make a great book around computational art, rapid prototyping, kinematics, etc. The nice thing about origami is that it adds a physicality to mathematics that makes it tangible and approachable.


I would love to use this to build airfoils and flying devices .. anyone had a chance to play with it? Is it feasible to import a plane model, and end up with a 3D paper airplane like never seen before?


would be amazing to see the Rubic'sCube and Chess speed solvers burn this algorithm into their heads and start a competition to replicate a provided item.


I'm guessing the difference between this and something like pepakura (http://www.tamasoft.co.jp/pepakura-en/) is it doesn't use cuts?


It looks like it just goes low-poly, all triangles as is pretty normal. Then maybe links some of the triangles together, ultimately telling you how many paper triangles how many different sizes to make.


No, they put a low-poly mesh into the algorithm (I presume so it'd be foldable in a reasonable amount of time).

"Maybe links some of the triangles together" is the difficult part, especially since they guarantee the boundary of the paper folds to the boundary of the mesh.


Thanks for sharing this article. It was an interesting read about the progression of the idea into the tool available. I'm going to try out the software when I get a chance.


Could this be applied to UV/texture mapping? I can see reversing the folding would be really helpful to texture map more easily.


I doubt it. In texture mapping cuts are allowed, so it is not origami.


Actually I think it could be quite relevant. The mere fact that origami doesn't allow cuts is what makes this so attractive from a texturing standpoint.

From what I can tell, it appears that there are many locations where the original plane overlaps. If it is possible to easily calculate adjacency for those triangles, you would be able to properly do filtering lookups.

Another question is how much overlapping there is. The more there is, the more you potentially waste texture resolution.

Still, cool idea...


That would be cool if there was any graduate students working on this topic. I sure would like to work on a topic like this!


Can we build homes of sheet metal with this?


I assume you're talking about more than just the metal. I can imagine the heat transfer would be terribly high.


That's a great point. I hadn't considered that. What about paper homes? Highly compressed cardboard, sprayed with a clearcoat afterward to make it waterproof.


Joints will be your enemy! You might want some windows and doors for example.

What about a lower(ish) tech solution involving say wood and mud? My aunt and uncle's previous house was largely that plus straw and (reed|straw) thatching and was originally built in the 1630's. It's not a particularly old example but one that springs to mind. We don't see many earthquakes, for example, here nor many forest fires but that house has stood through at least one or two 1 in say 300 year weather events - not least a bit of a cold spell in the 18th C and a few somewhat windy episodes.

That house has been patched up once or twice and I suspect that might be quite hard with your paper/card jobbie. The clearcoat will probably discolour badly and degrade within <10 years but obviously you could reapply it regularly. Swallows and House Martens or similar might also nick bits of it for their nests. I don't know what sort of insects you have to deal with where you are but they could also get nasty with a paper abode 8)


You don't usually want homes to be complex shapes, though. Rectilinear floor plans and wedge-shaped roofs are popular for a lot of reasons.

I suppose for disaster relief, cylindrical huts or igloo domes could be useful to minimize footprint, materials, and heating costs. But for permanent housing, most people will prefer vertical walls and right-angle corners.


Even Wams?


If you can't make them yourself no algorithm will help you.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: