應用粒子群最佳化和模擬退火之多面體展開

Abstract

3D 模型分解的其中一項研究是沿著模型的邊切割，將其攤平成單個連通的平面圖形，這可以應用在減少物體體積以增加儲存的便利性，常見於紙工藝上。然而將 3D 模型拆解成一個不重疊的展開是一個困難的問題，甚至部分的 3D 模型無法透過切割邊來產生不重疊的展開。在這篇論文中，我們主要探討的是由三角形網格所形成的模型，並且加入黏貼面的設計，有助於增加重建模型的穩定性，但也提升了拆解的困難。過往基於模擬退火法進行拆解的研究，雖然可以有效拆解大部分模型，但整體需要花費較多的時間。因應這項問題，我們將粒子群最佳化合併模擬退火法，並改善原有的模擬退火法的效率及功能。在實驗結果中，我們的方法大幅減少了拆解的時間，並達到能限制平面圖形的形狀、大小的效果。

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.