請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88254
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 顏嗣鈞 | zh_TW |
dc.contributor.advisor | Hsu-Chun Yen | en |
dc.contributor.author | 呂旻軒 | zh_TW |
dc.contributor.author | Min-Hsuan Lu | en |
dc.date.accessioned | 2023-08-09T16:13:51Z | - |
dc.date.available | 2023-11-09 | - |
dc.date.copyright | 2023-08-09 | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-07-24 | - |
dc.identifier.citation | [1] M. Bern, E. D. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink. Ununfoldable polyhedra with convex faces. Computational Geometry, 24(2):51–62, 2003.
[2] D. Bertsimas and J. Tsitsiklis. Simulated annealing. Statistical science, 8(1):10–15, 1993. [3] Y.-J. Chang and H.-C. Yen. Unfolding orthogonal polyhedra with linear refinement. In Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 415–425. Springer, 2015. [4] M. Damian and H. Meijer. Edge-unfolding orthostacks with orthogonally convex slabs. In 14th Annual Fall Workshop on Computational Geometry, pages 20–21, 2004. [5] E. D. Demaine and K. Karntikoon. Unfolding orthotubes with a dual hamiltonian path. arXiv preprint arXiv:2201.12452, 2022. [6] T.B.E.D.M.Demainez, A.Lubiwzx, M.O.-J.O.Steve, and R.S.Whitesidesyxyy. Unfolding some classes of orthogonal polyhedra. 1998. [7] T. Haenselmann and W. Effelsberg. Optimal strategies for creating paper models from 3d objects. Multimedia systems, 18:519–532, 2012. [8] F. Javidrad and M. Nazari. A new hybrid particle swarm and simulated annealing stochastic optimization method. Applied Soft Computing, 60:634–654, 2017. [9] S. Kathpal, R. Vohra, J. Singh, and R. Sawhney. Hybrid pso–sa algorithm for achieving partitioning optimization in various network applications. Procedia engineering, 38:1728–1734, 2012. [10] J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of ICNN’95-international conference on neural networks, volume 4, pages 1942–1948. IEEE, 1995. [11] T. Korpitsch, S. Takahashi, E. Gröller, and H.-Y. Wu. Simulated annealing to unfold 3d meshes and assign glue tabs. Journal of WSCG, 28(1–2):47–56, 2020. [12] L. R. Rere, M. I. Fanany, and A. M. Arymurthy. Simulated annealing algorithm for deep learning. Procedia Computer Science, 72:137–144, 2015. [13] L. Richaume, E. Andres, G. Largeteau-Skapin, and R. Zrour. Unfolding level 1 menger polycubes of arbitrary size with help of outer faces. In Discrete Geometry for Computer Imagery: 21st IAPR International Conference, DGCI 2019, Marne-la-Vallée, France, March 26–28, 2019, Proceedings 21, pages 457–468. Springer, 2019. [14] W. Schlickenrieder. Nets of polyhedra. Master’s Thesis, Technische Universität Berlin, 1997. [15] R. Straub and H. Prautzsch. Creating optimized cut-out sheets for paper models from meshes. Citeseer, 2011. [16] S. Takahashi, H.-Y. Wu, S.H. Saw, C.-C. Lin, and H.-C. Yen. Optimized topological surgery for unfolding 3d meshes. In Computer graphics forum, volume 30, pages 2077–2086. Wiley Online Library, 2011. [17] W.-j. Xia and Z.-m. Wu. A hybrid particle swarm optimization approach for the job- shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 29:360–366, 2006. | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88254 | - |
dc.description.abstract | 3D 模型分解的其中一項研究是沿著模型的邊切割,將其攤平成單個連通的平面圖形,這可以應用在減少物體體積以增加儲存的便利性,常見於紙工藝上。然而將 3D 模型拆解成一個不重疊的展開是一個困難的問題,甚至部分的 3D 模型無法透過切割邊來產生不重疊的展開。在這篇論文中,我們主要探討的是由三角形網格所形成的模型,並且加入黏貼面的設計,有助於增加重建模型的穩定性,但也提升了拆解的困難。過往基於模擬退火法進行拆解的研究,雖然可以有效拆解大部分模型,但整體需要花費較多的時間。因應這項問題,我們將粒子群最佳化合併模擬退火法,並改善原有的模擬退火法的效率及功能。在實驗結果中,我們的方法大幅減少了拆解的時間,並達到能限制平面圖形的形狀、大小的效果。 | zh_TW |
dc.description.abstract | One of the research areas in the decomposition of 3D models involves cutting along the edges of the model to unfold it into a single connected planar graph. This technique is commonly used in papercraft to reduce the volume of objects for storage convenience. However, achieving a non-overlapping unfolding of a 3D model is a challenging problem, and in some cases, it is not possible to generate a non-overlapping unfolding by cutting along the edges. In this thesis, we focus primarily on models formed by triangular faces and incorporate the design of gluetags to enhance the stability of reconstructed models, but it also increases the difficulty of the unfolding process. In the former study, the unfolding is performed using simulated annealing, which could effectively unfold the majority of models but still consumes too much time. To address this issue, we combine particle swarm optimization with simulated annealing to improve the efficiency. Also, we improve the functionality of the original simulated annealing method. In the experimental results, our approach significantly reduces the unfolding time and achieves the ability to control the shape and size of the planar graph. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-09T16:13:51Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-08-09T16:13:51Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 摘要 iii Abstract iv Contents vi List of Figures viii List of Tables x Chapter 1 Introduction 1 Chapter 2 Related Work 5 2.1 Edge Unfolding 5 2.2 General Unfolding 6 2.3 Unfolding Orthogonal Polyhedra 8 Chapter 3 3D models and their unfoldings 9 3.1 Triangular Polyhedra 9 3.2 Dual Graph and Minimum Spanning Tree 10 3.3 Bend Edge and Cut Edge 11 3.4 Gluetag 11 Chapter 4 Algorithm design for 3D mesh unfolding 13 4.1 Particle Swarm Optimization 13 4.2 Simulated Annealing 17 4.3 Workflow for 3D mesh unfolding 19 4.4 Optimise 3D Mesh unfolding 22 4.4.1 Gluetag Selection 23 4.4.2 Dynamic Gluetag Size 23 4.4.3 Improving Simulated Annealing 26 4.4.4 Some small techniques to speed up the processes 27 4.5 The Constrain Size Version of Simulated Annealing 28 4.6 Spatial Optimization 28 4.7 Stabilize Reconstructed Model 30 Chapter 5 Experimental Evaluation 31 5.1 Performance 31 5.2 Results 33 Chapter 6 Conclusion and Future Work 37 References 38 | - |
dc.language.iso | en | - |
dc.title | 應用粒子群最佳化和模擬退火之多面體展開 | zh_TW |
dc.title | Unfolding Polyhedra Using Particle Swarm Optimization and Simulated Annealing | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 郭斯彥;雷欽隆;黃士嘉 | zh_TW |
dc.contributor.oralexamcommittee | Sy-Yen Kuo;Chin-Laung Lei;Shih-Chia Huang | en |
dc.subject.keyword | 3D 模型展開,模擬退火法,粒子群最佳化, | zh_TW |
dc.subject.keyword | 3D model unfolding,Simulated annealing,Particle Swarm Optimization, | en |
dc.relation.page | 40 | - |
dc.identifier.doi | 10.6342/NTU202301837 | - |
dc.rights.note | 未授權 | - |
dc.date.accepted | 2023-07-25 | - |
dc.contributor.author-college | 電機資訊學院 | - |
dc.contributor.author-dept | 電機工程學系 | - |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf 目前未授權公開取用 | 6.41 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。