Page 301 - 《软件学报》2020年第10期

金耀 等:距离约束的网格曲面曲线设计方法 3277

本文算法最为耗时的部分为迭代中所涉及的线性方程组的求解与局部投影计算.由于该算法在整体与局部阶
段均采用了加速策略,因此求解效率相对较高.表1列出了在各个模型上设计曲线的运行时间.由表1可见:算法效率
与网格模型的规模相关度较小,而主要取决于曲线的离散采样点的数目,且总体效率可满足交互应用的要求.

Table 1 Cost time of generating curve on various models
表 1 各个模型上曲线的生成时间

网格模型(顶点数/面片数) 离散点数目(初始/最终) 运行时间(ms)
人脸(1415/2752) 229/312 24.3
兔子(14290/28576) 518/756 104
雕像(50002/100000) 783/914 117.2
Fandisk(7229/14454) 325/401 30.5
怪兽(6752/13500) 173/303 6.0
瓶(50002/100000) 320/488 27.8
梨(10754/21504) 400/587 25.2
脚(10010/19974) 304/419 44.0
狗头(3716/7428) 328/466 60.9
8 字-1(3070/6144) 570/790 85.3
8 字-2(3070/6144) 165/258 12.5
鸭(9640/19276) 240/359 55.0
鱼(6787/13456) 240/356 65.1
牛-1(4315/8626) 185/221 15.4
牛-2(4315/8626) 120/181 16.3
4 结 语

本文提出了一种针对网格曲面的高效且实用的曲线设计方法,该方法将流形约束松弛为点到切平面距离的约
束,并将所有约束共同描述成一个优化问题进行求解.该方法鲁棒、高效,适用范围广,可用于任意复杂拓扑(如多亏
格)的网格曲面.此外,相比于前沿算法,本文方法不仅能够设计闭合与开曲线、插值与光顺曲线,而且在效率上占有
明显优势,能够满足交互响应要求.
本文方法通过采用局部线搜索策略控制迭代步长,能够保证算法收敛,但是该策略由于对步长进行了限制,有
时未能充分松弛曲线形状,从而可能陷入局部最优解.在今后,我们将探索更好的收敛策略,在保证收敛性的同时,更
好地控制曲线形状.此外,本文算法的复杂度与曲线采样点的个数相关,对于设计采样密度较大的曲线,其效率将成
为一个瓶颈.因此,这也是未来需要研究的工作.

References:
[1] Ji Z, Liu L, Chen Z, Wang G. Easy mesh cutting. Computer Graphics Forum, 2006,25(3):283−291.
[2] Kaplansky L, Tal A. Mesh segmentation refinement. Computer Graphics Forum, 2009,28(7):1995−2003.
[3] Zachow S, Gladilin E, Sader R, Zeilhofer HF. Draw and cut: Intuitive 3D osteotomy planning on polygonal bone models. Int’l
Congress Series, 2003,1256:362−369.
[4] Lawonn K, Gasteiger R, Rossl C, Preim B. Adaptive and robust curve smoothing on surface meshes. Computers & Graphics, 2014,
40:22−35.
[5] Liu B, Huang CB, Lin JY, et al. Interpolation of geodesic B-spline curves on manifold triangulation. Jixie Gongcheng Xuebao
(Chinese Journal of Mechanical Engineering), 2011,47(19):136−142 (in Chinese with English abstract).
[6] Han L, Liu B. Design and reuse of curves on manifold triangulation based on discrete exponential maps. China Mechanical
Engineering, 2012,23(23):2852−2857 (in Chinese with English abstract).
[7] Zehnder J, Coros S, Thomaszewski B. Designing structurally-sound ornamental curve networks. ACM Trans. on Graphics, 2016,
35(4):99.
[8] Liu YJ, Chen Z, Tang K. Construction of iso-contours, bisectors, and voronoi diagrams on triangulated surfaces. IEEE Trans. on
Pattern Analysis and Machine Intelligence, 2011,33(8):1502−1517.