{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:05:13Z","timestamp":1740107113712,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T00:00:00Z","timestamp":1715904000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T00:00:00Z","timestamp":1715904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006447","name":"University of Zurich","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006447","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis Comput"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Folding a discrete geometry from a flat sheet of material is one way to construct a 3D object. A typical creation pipeline first designs the 3D object, unfolds it, prints and cuts the unfold pattern from a 2D material, and then refolds the object. Within this work we focus on the unfold part of this pipeline. Most current unfolding approaches segment the input, which has structural downsides for the refolded result. Therefore, we are aiming to unfold the input into a single-patched pattern. Our algorithm applies tabu search to the topic of unfolding. We show empirically that our algorithm is faster and more reliable than other methods unfolding into single-patched unfold patterns. Moreover, our algorithm can handle any sort of flat polygon as faces, while comparable methods are bound to triangles.<\/jats:p>","DOI":"10.1007\/s00371-024-03395-2","type":"journal-article","created":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T15:01:58Z","timestamp":1715958118000},"page":"1141-1154","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Unfolding polyhedra via tabu search"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5730-4361","authenticated-orcid":false,"given":"Lars","family":"Zawallich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,17]]},"reference":[{"issue":"4","key":"3395_CR1","doi-asserted-by":"publisher","first-page":"102:1","DOI":"10.1145\/2010324.1964997","volume":"30","author":"M Alexa","year":"2011","unstructured":"Alexa, M., Wardetzky, M.: Discrete laplacians on general polygonal meshes. ACM Transaction on Graphics 30(4), 102:1\u201310 (2011). https:\/\/doi.org\/10.1145\/2010324.1964997","journal-title":"ACM Transaction on Graphics"},{"issue":"6","key":"3395_CR2","doi-asserted-by":"publisher","first-page":"1466","DOI":"10.1109\/TRO.2018.2862882","volume":"34","author":"B An","year":"2018","unstructured":"An, B., Miyashita, S., Tolley, M.T., Aukes, D.M., Meeker, L., Demaine, E.D., Demaine, M.L., Wood, R.J., Rus, D.: An end-to-end approach to self-folding origami structures. IEEE Transactions on Robotics 34(6), 1466\u20131473 (2018). https:\/\/doi.org\/10.1109\/TRO.2018.2862882","journal-title":"IEEE Transactions on Robotics"},{"issue":"5","key":"3395_CR3","doi-asserted-by":"publisher","first-page":"1357","DOI":"10.1007\/s00373-017-1849-5","volume":"33","author":"M Damian","year":"2017","unstructured":"Damian, M., Demaine, E.D., Flatland, R., O\u2019Rourke, J.: Unfolding genus-2 orthogonal polyhedra with linear refinement. Graphs and Combinatorics 33(5), 1357\u20131379 (2017). https:\/\/doi.org\/10.1007\/s00373-017-1849-5","journal-title":"Graphs and Combinatorics"},{"issue":"1","key":"3395_CR4","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/s00373-007-0701-8","volume":"23","author":"M Damian","year":"2007","unstructured":"Damian, M., Flatland, R., O\u2019Rourke, J.: Epsilon-unfolding orthogonal polyhedra. Graphs and Combinatorics 23(1), 179\u2013194 (2007). https:\/\/doi.org\/10.1007\/s00373-007-0701-8","journal-title":"Graphs and Combinatorics"},{"key":"3395_CR5","unstructured":"Demaine, E.D., Demaine, M.L., Eppstein, D., O\u2019Rourke, J.: Some polycubes have no edge zipper unfolding. In: Proceedings Canadian Conference in Computational Geometry, pp. 101\u2013105. Saskatchewan, Saskatoon, Canada (2020)"},{"key":"3395_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511735172","author":"ED Demaine","year":"2007","unstructured":"Demaine, E.D., O\u2019Rourke, J.: Geometric Folding Algorithms: Linkages, Origami. Polyhedra. Cambridge University Press (2007). https:\/\/doi.org\/10.1017\/CBO9780511735172","journal-title":"Polyhedra. Cambridge University Press"},{"key":"3395_CR7","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., Tachi, T.: Origamizer: A practical algorithm for folding any polyhedron. In: International Symposium on Computational Geometry, vol.\u00a077, pp. 34:1\u201316. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2017.34","DOI":"10.4230\/LIPIcs.SoCG.2017.34"},{"key":"3395_CR8","unstructured":"D\u00fcrer, A.: Underweysung Der Messung Mit Dem Zirkel Und Richtscheyt. Hieronymus Andreae, N\u00fcremberg (1525)"},{"issue":"5","key":"3395_CR9","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F Glover","year":"1986","unstructured":"Glover, F.: Future paths for integer programming and links to artificial intelligence. Computers & Operations Research 13(5), 533\u2013549 (1986). https:\/\/doi.org\/10.1016\/0305-0548(86)90048-1","journal-title":"Computers & Operations Research"},{"issue":"6","key":"3395_CR10","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s00530-012-0273-1","volume":"18","author":"T Haenselmann","year":"2012","unstructured":"Haenselmann, T., Effelsberg, W.: Optimal strategies for creating paper models from 3d objects. Multimedia Systems 18(6), 519\u2013532 (2012). https:\/\/doi.org\/10.1007\/s00530-012-0273-1","journal-title":"Multimedia Systems"},{"key":"3395_CR11","first-page":"7:1","volume":"14","author":"Y Hao","year":"2018","unstructured":"Hao, Y., Kim, Y., Xi, Z., Lien, J.M.: Creating foldable polyhedral nets using evolution control. In: Robotics: Science and Systems 14, 7:1-9 (2018)","journal-title":"In: Robotics: Science and Systems"},{"key":"3395_CR12","doi-asserted-by":"publisher","unstructured":"Hormann, K., L\u00e9vy, B., Sheffer, A.: Mesh parameterization: Theory and practice. In: ACM SIGGRAPH 2007 Courses, p. 1-es. Association for Computing Machinery (2007). https:\/\/doi.org\/10.1145\/1281500.1281510","DOI":"10.1145\/1281500.1281510"},{"issue":"6","key":"3395_CR13","doi-asserted-by":"publisher","first-page":"200:1","DOI":"10.1145\/3414685.3417835","volume":"39","author":"A Ion","year":"2020","unstructured":"Ion, A., Rabinovich, M., Herholz, P., Sorkine-Hornung, O.: Shape approximation by developable wrapping. ACM Transactions on Graphics 39(6), 200:1\u201312 (2020). https:\/\/doi.org\/10.1145\/3414685.3417835","journal-title":"ACM Transactions on Graphics"},{"issue":"1\u20132","key":"3395_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.24132\/JWSCG.2020.28.6","volume":"28","author":"T Korpitsch","year":"2020","unstructured":"Korpitsch, T., Takahashi, S., Gr\u00f6ller, E., Wu, H.Y.: Simulated annealing to unfold 3d meshes and assign glue tabs. Journal of WSCG 28(1\u20132), 47\u201356 (2020). https:\/\/doi.org\/10.24132\/JWSCG.2020.28.6","journal-title":"Journal of WSCG"},{"key":"3395_CR15","volume-title":"The Complete Book of Origami: Step-By-Step Instructions In Over 1000 Diagrams: 37 Original Models","author":"RJ Lang","year":"1988","unstructured":"Lang, R.J.: The Complete Book of Origami: Step-By-Step Instructions In Over 1000 Diagrams: 37 Original Models. Dover Publications, Dover Origami Papercraft (1988)"},{"issue":"2","key":"3395_CR16","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Operations Research 21(2), 498\u2013516 (1973). https:\/\/doi.org\/10.1287\/opre.21.2.498","journal-title":"Operations Research"},{"issue":"3","key":"3395_CR17","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1145\/1015706.1015711","volume":"23","author":"J Mitani","year":"2004","unstructured":"Mitani, J., Suzuki, H.: Making papercraft toys from meshes using strip-based approximate unfolding. ACM Transactions on Graphics 23(3), 259\u2013263 (2004). https:\/\/doi.org\/10.1145\/1015706.1015711","journal-title":"ACM Transactions on Graphics"},{"key":"3395_CR18","doi-asserted-by":"publisher","unstructured":"Poranne, R., Tarini, M., Huber, S., Panozzo, D., Sorkine-Hornung, O.: Autocuts: Simultaneous distortion and cut optimization for uv mapping. ACM Transactions on Graphics 36(6) (2017). https:\/\/doi.org\/10.1145\/3130800.3130845","DOI":"10.1145\/3130800.3130845"},{"key":"3395_CR19","unstructured":"Robinson, N.: The Origami Bible: A Practical Guide to The Art of Paper Folding. North Light Books (2004)"},{"issue":"6","key":"3395_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1038\/s41578-018-0009-8","volume":"3","author":"D Rus","year":"2018","unstructured":"Rus, D., Tolley, M.T.: Design, fabrication and control of origami robots. Nature Reviews Materials 3(6), 101\u2013112 (2018). https:\/\/doi.org\/10.1038\/s41578-018-0009-8","journal-title":"Nature Reviews Materials"},{"key":"3395_CR21","doi-asserted-by":"publisher","unstructured":"Sawhney, R., Crane, K.: Boundary first flattening. ACM Transactions on Graphics 37(1), 5:1-5:14 (2017). https:\/\/doi.org\/10.1145\/3132705","DOI":"10.1145\/3132705"},{"key":"3395_CR22","unstructured":"Schlickenrieder, W.: Nets of polyhedra. Diploma thesis, Technische Universit\u00e4t Berlin, Stra\u00dfe des 17. Juni 135, 10623 Berlin (1997)"},{"issue":"9","key":"3395_CR23","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1007\/s00371-006-0067-6","volume":"22","author":"I Shatz","year":"2006","unstructured":"Shatz, I., Tal, A., Leifman, G.: Paper craft models from meshes. The Visual Computer 22(9), 825\u2013834 (2006). https:\/\/doi.org\/10.1007\/s00371-006-0067-6","journal-title":"The Visual Computer"},{"issue":"4","key":"3395_CR24","doi-asserted-by":"publisher","first-page":"77:1","DOI":"10.1145\/3197517.3201303","volume":"37","author":"O Stein","year":"2018","unstructured":"Stein, O., Grinspun, E., Crane, K.: Developability of triangle meshes. ACM Transactions on Graphics 37(4), 77:1\u201314 (2018). https:\/\/doi.org\/10.1145\/3197517.3201303","journal-title":"ACM Transactions on Graphics"},{"key":"3395_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5445\/IR\/1000025577","volume":"36","author":"R Straub","year":"2011","unstructured":"Straub, R., Prautzsch, H.: Creating optimized cut-out sheets for paper models from meshes. Karlsruhe Reports in Informatics 36, 1\u201315 (2011). https:\/\/doi.org\/10.5445\/IR\/1000025577","journal-title":"Karlsruhe Reports in Informatics"},{"issue":"2","key":"3395_CR26","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1109\/TVCG.2009.67","volume":"16","author":"T Tachi","year":"2009","unstructured":"Tachi, T.: Origamizing polyhedral surfaces. IEEE Transactions on Visualization and Computer Graphics 16(2), 298\u2013311 (2009). https:\/\/doi.org\/10.1109\/TVCG.2009.67","journal-title":"IEEE Transactions on Visualization and Computer Graphics"},{"issue":"7","key":"3395_CR27","doi-asserted-by":"publisher","first-page":"2077","DOI":"10.1111\/j.1467-8659.2011.02053.x","volume":"30","author":"S Takahashi","year":"2011","unstructured":"Takahashi, S., Wu, H.Y., Saw, S.H., Lin, C.C., Yen, H.C.: Optimized topological surgery for unfolding 3d meshes. Computer Graphics Forum 30(7), 2077\u20132086 (2011). https:\/\/doi.org\/10.1111\/j.1467-8659.2011.02053.x","journal-title":"Computer Graphics Forum"},{"issue":"C","key":"3395_CR28","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.cag.2016.05.022","volume":"58","author":"Xi Z","year":"2016","unstructured":"Z, Xi., Kim, Y.H., Kim, Y.J., Lien, J.M.: Learning to segment and unfold polyhedral mesh from failures. Computers & Graphics 58(C), 139\u2013149 (2016). https:\/\/doi.org\/10.1016\/j.cag.2016.05.022","journal-title":"Computers & Graphics"},{"key":"3395_CR29","doi-asserted-by":"publisher","unstructured":"Xi, Z., Lien, J.M.: Continuous unfolding of polyhedra - a motion planning approach. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 3249\u20133254 (2015). https:\/\/doi.org\/10.1109\/IROS.2015.7353828","DOI":"10.1109\/IROS.2015.7353828"},{"key":"3395_CR30","doi-asserted-by":"publisher","unstructured":"Yao, M., Belke, C.H., Cui, H., Paik, J.: A reconfiguration strategy for modular robots using origami folding. International Journal of Robotics Research 38(1), 73\u201389 (2019). https:\/\/doi.org\/10.1177\/0278364918815757","DOI":"10.1177\/0278364918815757"},{"key":"3395_CR31","doi-asserted-by":"publisher","unstructured":"Zhou, Q., Jacobson, A.: Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797 (2016). https:\/\/doi.org\/10.48550\/arXiv.1605.04797","DOI":"10.48550\/arXiv.1605.04797"}],"container-title":["The Visual Computer"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-024-03395-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00371-024-03395-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00371-024-03395-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,3]],"date-time":"2025-02-03T12:36:08Z","timestamp":1738586168000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00371-024-03395-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,17]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["3395"],"URL":"https:\/\/doi.org\/10.1007\/s00371-024-03395-2","relation":{},"ISSN":["0178-2789","1432-2315"],"issn-type":[{"type":"print","value":"0178-2789"},{"type":"electronic","value":"1432-2315"}],"subject":[],"published":{"date-parts":[[2024,5,17]]},"assertion":[{"value":"28 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest. This work involved no human participants or animals.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}