在本篇論文中，我們將介紹一個利用三維模型產生線條藝術的方法。當藝術家在創造線條藝術時，會藉由觀察一個實體物品，根據物品的形狀來決定線條繞行的方式。而本篇論文所提出的方法能夠利用物體的三維模型直接生成立體的線條藝術，此結果可以引導藝術家，作為線條繞行方式的參考。首先，我們使用三維的網格（mesh）模型當作輸入，藉由我們的計算方法取出網格上的邊，這些邊能夠組成許多條相互連接的線段，並且能夠大致地表現輸入模型的形狀。為了利用最少數量的連續線條繞行出物體的形狀，我們將上個步驟所產生的線段連接起來，使線段依順序連接後可以成為一條更長的連續線條，為此我們制訂了一個多旅行推銷員問題（multiple travelling salesman problem, mTSP）來實現。接著，我們希望產生出來的線條可以盡量平滑，因此制訂了另一個最佳化問題，使所產生的線條能夠更自然。最後，我們利用這些平滑線條的資訊來建造出三維網格模型，模擬藝術家利用鋼絲所創造出來的線條藝術效果。此外，我們提供了使用者介面，讓使用者能夠依據他們的喜好控制線條的繞行方式，產生出更符合所預期的結果。我們透過問卷調查讓受測者評估我們的結果，問卷結果顯示系統產生的線條藝術是具有吸引力的。

In this work we introduce a method of line art generation from 3D model. Usually, an artist creates a line art by observing the shape of an object. Our system can generate a line art directly from 3D model. The result of our system could give the artists an example before they create a line art. First, we use the 3D triangular mesh model as our input. By the extraction of the important edges on the mesh, we obtain the connected segments of edges which roughly represent the shape of the input model. In order to generate the line art with the minimum number of continuous lines, we connect the segments by the order obtained by a travelling salesman problem. Next, we formulate another optimization problem to make the continuous lines smoother. Finally, we construct the 3D mesh model of line art by the information of smooth lines, simulating the real work by artist. In addition, we propose an interface for users to control the winding of lines by their preference. The results of our work are evaluated by user study indicating that the line art generated by the system are appealing.

[1] Mario Botsch and Leif Kobbelt. A remeshing approach to multiresolution modeling. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP ’04, pages 185–192, New York, NY, USA, 2004. ACM.
[2] David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. Variational shape approximation. In ACM SIGGRAPH 2004 Papers, SIGGRAPH ’04, pages 905–914, New York, NY, USA, 2004. ACM.
[3] Doug DeCarlo, Adam Finkelstein, Szymon Rusinkiewicz, and Anthony Santella. Suggestive contours for conveying shape. In ACM SIGGRAPH 2003 Papers, SIGGRAPH ’03, New York, NY, USA, 2003. ACM.
[4] Emil Ernerfeldt. Fitting a plane to noisy points in 3d, September 2017.
[5] Ran Gal, Olga Sorkine, Niloy J. Mitra, and Daniel Cohen-Or. iwires: An analyze-andedit approach to shape manipulation. In ACM SIGGRAPH 2009 Papers, SIGGRAPH ’09, pages 33:1–33:10, New York, NY, USA, 2009. ACM.
[6] Michael Garland and Paul S. Heckbert. Surface simplification using quadric error metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’97, pages 209–216, New York, NY, USA, 1997. ACM Press/Addison-Wesley Publishing Co.
[7] Tilke Judd, Frédo Durand, and Edward H. Adelson. Apparent ridges for line drawing. ACM Trans. Graph., 26(3):19:1–19:8, 2007.
[8] Imdat Kara and Tolga Bektas. Integer linear programming formulations of multiple salesman problems and its variations. European Journal of Operational Research, 174(3):1449 – 1458, 2006.
[9] Shiwei Li, Yao Yao, Tian Fang, and Long Quan. Reconstructing thin structures of manifold surfaces by integrating spatial curves. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2887–2896, June 2018.
[10] Lingjie Liu, Duygu Ceylan, Cheng Lin, Wenping Wang, and Niloy J. Mitra. Imagebased reconstruction of wire art. ACM Trans. Graph., 36(4):63:1–63:11, July 2017.
[11] Ravish Mehra, Qingnan Zhou, Jeremy Long, Alla Sheffer, Amy Gooch, and Niloy J. Mitra. Abstraction of man-made shapes. In ACM SIGGRAPH Asia 2009 Papers, SIGGRAPH Asia ’09, pages 137:1–137:10, New York, NY, USA, 2009. ACM.
[12] Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. Fibermesh: Designing freeform surfaces with 3d curves. In ACM SIGGRAPH 2007 Papers, SIGGRAPH ’07, New York, NY, USA, 2007. ACM.
[13] Alexandrina Orzan, Adrien Bousseau, Holger Winnemöller, Pascal Barla, Joëlle Thollot, and David Salesin. Diffusion curves: A vector representation for smooth-shaded images. In ACM SIGGRAPH 2008 Papers, SIGGRAPH ’08, pages 92:1–92:8, New York, NY, USA, 2008. ACM.
[14] Yipeng Qin, Xiaoguang Han, Hongchuan Yu, Yizhou Yu, and Jianjun Zhang. Fast and exact discrete geodesic computation based on triangle-oriented wavefront propagation. ACM Trans. Graph., 35(4):125:1–125:13, July 2016.
[15] Szymon Rusinkiewicz. Estimating curvatures and their derivatives on triangle meshes. In Proceedings of the 3D Data Processing, Visualization, and Transmission, 2Nd International Symposium, 3DPVT ’04, pages 486–493, Washington, DC, USA, 2004. IEEE Computer Society.
[16] Ren Suzuki, Masaki Moriguchi, and Keiko Imai. Generation and optimization of multiviewwire art. Poster presented at the Pacific Graphics, October 2017.
[17] Fernando J. Wong and Shigeo Takahashi. A graph-based approach to continuous line illustrations with variable levels of detail. In Computer Graphics Forum (Proceedings of Pacific Graphics 2011), volume 30, pages 1931–1939, 2011.
[18] Rundong Wu, Huaishu Peng, François Guimbretière, and Steve Marschner. Printing arbitrary meshes with a 5dof wireframe printer. ACM Trans. Graph., 35(4):101:1–101:9, July 2016.
[19] Yinan Zhou and Zhiyong Huang. Decomposing polygon meshes by means of critical points. In 10th International Multimedia Modelling Conference, 2004. Proceedings., pages 187–195, 2004.