基于映射的多边形相容三角剖分

Size: px

Start display at page:

Download "基于映射的多边形相容三角剖分"

垒亘景
5 years ago
Views:

1 多边形高质量同构三角剖分的有效算法张冬梅 +, 刘利刚 ( 浙江大学数学系计算机图像图形研究所, 浙江杭州 3007) Effcent Approach for Hgh Qualty Compatble Trangulatons Between Polygons ZHANG Dong-Me, LIU L-Gang + (Insttute of Computer Graphcs and Image Processng, Department of Mathematcs, Zheang Unversty, Hangzhou 3007, Chna) + Correspondng author: Phn: , Fax: , E-mal: lganglu@zu.edu.cn Abstract: Ths paper presents a novel and effcent approach for buldng hgh qualty compatble trangulatons between two smple polygons. Frst, a trangulaton wth hgh qualty s easly constructed for the frst polygon by addng some Stener ponts on the boundary of and nsde the polygon. Then the connectvty of the trangulaton vertces s transferred nto the second polygon and the postons of the vertces are determned by the relatve geometrc relatonshp n the frst trangulaton. Fnally, some effcent approaches ncludng area equalzaton, edge swap, and Laplace smoothng are used to optmze the trangles n both trangulatons. The constructon of compatble trangulaton s formulated as a sparse lnear system, whch can be easly solved by some solver lbrary. Furthermore, the features of the trangulatons can be preserved by addng lnear constrants n the lnear system. Our approach s smple and fast and can obtan satsfed results for complex polygons. Many expermental results are presented to show the applcablty and flexblty of the approach. Key words: computatonal geometry; compatble trangulatons; Stener vertces; mean value coordnates; trangle optmzaton 摘要 : 本文提出了一种新的构造两个多边形的高质量同构三角剖分的有效方法. 首先通过加入一定数目的 Stener 点生成其中一个多边形的质量较好的三角剖分, 然后通过此三角网格中顶点之间的相对位置关系和邻接关系确定另一个多边形的三角剖分, 最后利用面积均等方法和其他优化方法对同构的三角剖分同时进行改进优化. 在本文算法中, 同构三角剖分的构造转化为一个稀疏线性方程组的求解, 可以用现成的程序库进行快速求解 ; 还可以通过约束一些对应特征点的位置使得生成的同构三角剖分具有较好的特征对应. 该算法计算量小, 运行效率高, 对形状复杂的多边形仍然可以得到满意的结果, 适合于 morphng 等实时的应用要求. 关键词 : 计算几何 ; 同构三角剖分 ;Stener 点 ; 平均值坐标 ; 三角形优化引言多边形同构三角剖分是计算几何中的重要问题 [-4], [5-7]. 它在计算机图形学和计算机辅助设计中都有着广泛的应用, 如 morphng,warpng 和 sweepng modelng 等两个多边形同构三角剖分的质量好坏直接影响着这些应用最后的结果, 因此如何得到两个多边形的高质量同构三角剖分是目前一个比较重要的问题 Aronov 等首次提出多边形同构三角剖分的概念, 证明了在允许加入内部点 ( 称为 Stener 点 ) 的条件 [8]. Supported by the Natonal Natural Scence Foundaton of Chna under Grant No , ( 国家自然科学基金 ); the Zheang Provncal Natural Scence Foundaton of Chna under Grant No. Y0559( 浙江省自然科学基金 ); the Natonal Grand Fundamental Research 973 Program of Chna under Grant No.00CB30( 国家重点基础研究发展规划基金 ) 作者简介 : 张冬梅 (98-), 女, 浙江大学数学系计算机图象图形研究所硕士研究生, 主要研究方向为计算机图形学与计算机辅助几何设计 ; 刘利刚 (975-), 男, 博士, 副教授, 硕士生导师, 主要研究领域为计算机图形学与计算机辅助几何设计.

2 下两个顶点个数相同的多边形总是存在同构三角剖分, 并且给出了两种构造同构三角剖分的算法, 但是两 [6] 种算法都导致加入的 Stener 点过多. Surazhsy 等改进了 Aronov 等的 Spdeweb 算法, 大大减少了加入 [] Stener 点的数目. Kranas 等提出了两种与他们不同的构造同构三角剖分的方法, 两种方法加入的 Stener [3] 点数目都依赖于多边形内射点的数目. Gupta 等提出了一种基于多边形内部最短链路的算法, 大大降低了加入的 Stener 点的数目, 但是复杂度太高, 运行效率低. 以上算法都只是考虑怎样使得加入的 Stener 点的数目尽可能少, 并不考虑得到的同构三角剖分质量的 [5-7] [5] 好坏, 使得它在 morphng 和 sweepng modelng 等方面的应用受到很大的限制. Alexa 等为了得到较好的形状过渡效果, 基于 Aronov 等的方法得到的同构三角剖分进行优化来提高同构三角剖分的质量, 但是由于 Aronov 等的算法引入的 Stener 点太多, 且三角剖分的顶点疏密程度很不均匀, 经优化后仍不能得 [6,8] [3] 到很好的结果. Surazhsy 等改进了 Gupta 等的基于多边形内部最短链路的算法得到初步同构三角剖分, 然后在此基础上采用了一系列三角网格光顺的方法来提高同构三角剖分的质量, 此算法对一般形状简单多边形得到的结果还算比较好, 不过复杂度高, 运行效率太低. 其实这两种得到高质量同构三角剖分的方法存在的最大问题都是对形状复杂的多边形不能得到满意的结果, 而且复杂度高, 使得 morphng 应用时不能达到实时的要求. 不同于以前方法的思路, 本文提出一种生成高质量同构三角剖分的有效算法. 首先通过加入适当的 Stener 点生成其中一个多边形的高质量的三角剖分, 然后将其 Stener 点和三角网格结构传递到另一个多边形内部. 在传递的过程中, 保持三角网格顶点与其 - 邻域顶点之间的相对几何位置关系, 从而保证第二个多边形的三角剖分也具有较好的质量. 然后通过面积均等方法边交换边分割和 Laplace 光顺等方法进一步提高三角网格的质量. 本文的方法主要是求解一个稀疏线性方程组, 可以利用高效的程序库得以快速求解, 并且可以在线性系统中增加任意的线性约束使得同构的三角剖分满足实际应用中的线性约束条件. 高质量同构三角剖分算法设 Γ = { u, u, L, u } 和 Γ = { v, v, L, v } 为个具有一一对应顶点的多边形, 其中 n 为顶点个数, u, v, =,, L, n, 分别为个多边形的顶点. n n. 生成多边形 Γ 的高质量三角剖分对一个多边形生成高质量的三角剖分, 已有很多工作对此进行了研究不同的算法通过加入一定数目的 Stener 点后, 可以生成不同要求的高质量的三角剖分, 如限制三角网格中三角形的最长边长, 最小角度和最大面积等我们采用限制三角形的最小角度和最大面积的方法对多边形 Γ 进行三角剖分, 从而 [9,0]. [9,0]. 得到多边形 Γ 的较高质量的三角剖分, 记为 T = { P, E}, 其中 P 为三角网格的顶点集合, E 为边集合. 如图所示,(a) 为一顶点数为 7 的多边形,(b) 和 (c) 为其在不同限制条件下 ( 三角形的最小角度和最大面积 ) 的高质量三角剖分.

对于位于多边形 Γ 边界上的 Stener 点, 设其位于边 uu, n上, 则按照点 p 位于边 p + uu 的比例相应地在多边形的边 vv 上增加对应的 Stener + Γ + 点 q, 即 Γ q pu u p = + v uu + v + uu + +.

3 ( a ) ( b ) () c 图. 多边形 (a) 及其在不同限制条件下的高质量三角剖分 (b,c).. 生成多边形 Γ 对应的三角剖分三角网格的顶点包含了多边形 Γ 的顶点以及新增加的 Stener 点. 我们构作多边形的三角剖分 T T 与 P, 使得 T T 具有相同个数而且相互对应的 Stener 点, 并且具有同构的三角网格结构. 三角网格 T 的顶点 P 中的 Stener 点包含两类, 一类位于多边形 Γ 的边界上, 另一类位于多边形 Γ 的内部. 对于位于多边形 Γ 边界上的 Stener 点, 设其位于边 uu, n上, 则按照点 p 位于边 p + uu 的比例相应地在多边形的边 vv 上增加对应的 Stener + Γ + 点 q, 即 Γ q pu u p = + v uu + v + uu + +. () 对于位于多边形 Γ 内部的 Stener 点 p, I, 设其 - 邻域的顶点为 p,, 为 p 的 - 邻域顶点的下标集合. 点 p 相对于其 - 邻域顶点 p, 的相对位置可以表示为如下的线性组合关系 : 其中 λ p λ p = 0, 为权系数 ( 亦称为重心坐标 ), 满足 λ 0, 顶点相对于其 λ =. - 邻域顶点的重心坐标的取法有多种方法 [, ], 这里我们采用平均值坐标方法 []. () 设 v0, v, v,..., v 是一平面点集, v, v,..., v 为点 v0 的 - 邻域顶点. 如图所示, 取 λ = ω = ω, (3) 3

4 tan( α ) + tan( α ) 其中 ω=, =,,..., v v 0 α 如图中所示. 可以证明, [] v 0 v, = = = λ λ =. 实数 λ, λ,..., λ 称为 v0 关于 v, v,..., v 的平均值坐标. 平均值坐标计算方法简单, 计算量小, 而且能较好地体现此顶点相对于其 - 邻域顶点的几何相对位置关系. v + v 0 α α v v v0 v v,,..., v 图. 顶点关于其 - 邻域的平均值坐标对于多边形 Γ, 其边界上的 Stener 点已由式 () 确定, 现欲决定其内部的 Stener 点, I, 其中 q 与 Γ 内部的 Stener 点 p 一一对应, 且 q 之间具有 p 之间相同的连接关系, 从而得到两个同构的三角网格. q 对任一 Γ 内部的 Stener 点, 令它在其 - 邻域顶点 q, 的重心坐标与点的重心坐标相同, 即满足式 (): q λ q = 0, I, (4) p q 其中权系数 λ 由 (3) 决定. 注意到 Γ 的顶点与边界上的 Stener 点均为已知, 由式 (4) 就得到关于未知量 q, I 的一个稀疏线性方程组. 可以证明这个线性方程组的系数矩阵是非退化的程组 (4) 唯一求解出 q. [], 因此可通过求解线性方我们的方法通过求解一稀疏线性方程组可唯一求解出多边形 Γ 的内部 Stener 点, 然后根据 Γ 的三角剖分的顶点之间的连接关系可得多边形 Γ 的三角剖分, 从而得到了 Γ 和 Γ 的同构三角剖分. 由于 Γ 的三角剖分质量较好, 其顶点之间的几何位置关系通过方程 (4) 被传递到了 Γ 的三角剖分的顶点, 因此能得到 Γ 的较好质量的三角剖分..3 增加顶点约束条件在有些应用中, 需要约束多边形 Γ 内部的某些点 p, J 对应于多边形 Γ 内部的某些点 q, J. 这时可以使, J 成为 Γ 的三角剖分的内部 Stener 点, 然后使 Γ 三角剖分的对应点 q, J p 满足顶 4

5 点位置坐标约束条件 : q = q, J. (5) 将约束条件 (5) 加入到线性方程组 (4) 中, 这时方程组成为一个关于未知量 q, I 的超限线性方程组 Α Α Q=b. (6) 由于上述方程组的系数矩阵是列满秩的, 方程组 (6) 能在最小二乘意义下得到较好的解 Τ - T Q= ( Α Α) A b. 此外, 通过加大方程 (5) 的权可以使得方程组 (6) 的最小二乘解能尽量满足约束条件 (5). 由以上分析可知, 只要我们在方程组 (4) 中加入任何关于顶点坐标的线性约束条件, 则构建的线性方程组都可以用最小二乘法进行求解..4 求解算法中最耗时部分是求解稀疏线性方程组 (4) 或 (6), 我们采用一个非常有效的求解大型稀疏线性方程组的程序库 Taucs [4] 来求解. 利用 Taucs 程序库, 我们可以很快求解稀疏线性方程组 (4) 或 (6), 从而得到两个多边形的同构三角剖分, 运行效率很高. [3] 3 同构三角剖分的优化对大部分的多边形 Γ 和 Γ, 上述方法都能生成高质量的同构三角剖分. 但在有些情况下, 虽然 Γ 的三角剖分质量很好, 但由于多边形 Γ 边界的任意性, 通过上述方法得到的 Γ 的同构三角剖分中有些三角形质量还是不好, 如会发生三角形翻转, 三角形形状狭长等现象. 为此, 我们需进一步优化的三角网格的质量. 3. 基于面积均等的优化方法首先, 我们通过面积均等的方法来优化 Γ 的三角剖分, 即移动三角网格内部顶点的位置使得它的所有邻接三角形的面积趋于平均化 [8]. 不妨设 v = ( x, y ) 0 是三角网格的一内部顶点, v, v,..., v 是 v0 的所有 - 邻域顶点,( x, y ) 是 v 的坐标, S ( x, y) 是 vvv 0 + 的面积, 其中 v = + v, S 是多边形 vv... v 的面 Γ 积, 即 : x y S( x, y) = x+ y+, S = S ( x, y). = x y 我们选取使得如下目标函数极小化 mn S S ( x, y) ( xy, ) =, 的 ( x, y ) 作为顶点 v 0 的新坐标. 实践例子证明利用面积均等的方法能很好地去除三角形翻转的问题. 5

6 3. 基于边交换, 边分割和光顺的优化方法由上面我们得到的两个多边形和 Γ 的同构三角剖分, 有时质量还不是非常令人满意, 还可以对两 Γ 个三角网格同时做优化. 对三角网格内部的每一边 (, ), 如果两个网格中与 (, ) 邻接的四个三角形的最小角小于一固定角度 [4] ( 取为 30 o 即可 ), 而且对 (, ) 实施边交换之后可以使最小角变大, 则两个网格同时对 (, ) 实施边交换操作, 如图 3(a) 所示. 记三角网格 T 和 T 的平均边长分别为 l 和 l. 若中某边的长度大于 T l α ( 比值 α 一般取为.8), 则在此边上增加若干点将其分割成若干短边, 并且进行适当三角化 ; 同时也需对 T 中对应的边作同样的分割 T 操作, 如图 3(b) 所示. 对中的边也类似可作分割操作. 另外, 对三角网格和 T 还可进行各种光顺优化操作, 如 Laplace 光顺方法, 来提高三角网格的质量 [5-7], 如图 3(c) 所示. T ( a ) ( c) 图 3. 三角形优化方法. (a) 边交换 ;(b) 边分割 ;(c) Laplace 光顺方法. 4 实例与应用 ( a) 图 4. 用本文方法得到的两个多边形的同构三角剖分图 4 是按照本文算法实现的两个多边形同构三角剖分的结果, 其中 (a) 中的三角网格是加入 Stener 点得到的, 而 (b) 中的三角网格是通过第二节方法求得的. 可以看出得到的三角网格的质量是令人满意的. 6

7 图 5 中, 我们对两个多边形用文献的算法得到的同构三角剖分如 (a),(b) 所示, 三角网格中具有很多细长的三角形, 并且三角形的大小和疏密程度很不均匀. 用本文方法得到的两个多边形同构三角剖分的结果如 (c) 和 (d) 所示, 质量远远优于 (a),(b) 的结果. ( a) ( c ) ( d ) 图 5. (a),(b) 为两个多边形用文献中的算法做同构三角剖分的结果 ; (c),(d) 为两个多边形用本文方法做同构三角剖分的结果. ( a) 图 6. 用本文方法得到的多边形同构三角剖分 ( a) 图 7. (a) 基于图 4 同构三角剖分的结果用文献的方法得到的 morphng 结果 ; (b) 顶点线性插值方法得到的 morphng 结果. [5] 7

8 在图 6 中, 两个多边形的原始顶点是分别按照两个相反的时针顺序排列对应的, 我们的算法仍能生成较好的同构三角网格, 因为我们的方法是与初始多边形顶点排列顺序无关的. 图 7(a) 是基于本文方法得到的同构三角剖分的结果用文献的方法得到的 morphng 结果,(b) 是直接线性插值多边形对应顶点得到的 morphng 结果. 显然, 线性插值方法造成舞蹈者中间形状的胳膊的萎缩, 而基于三角剖分的方法由于考虑了形状内部而有效避免了形状的萎缩的现象. [5] 5 结论本文提出了一种有效的生成高质量的同构三角剖分的算法. 不同于以前所有的算法, 是同时对两个多边形进行三角剖分, 我们的算法是先得到其中一个多边形的高质量三角剖分, 然后根据它三角剖分的结果得到另一个多边形的三角剖分, 最终得到它们的同构三角剖分. 本文算法复杂度低, 容易实现, 而且通过许多例子证明它不仅适用于形状简单的多边形, 对形状非常复杂的多边形仍然可以得到很好的结果, 这正是 morphng,warpng 等很多方面应用所需要的. References: B. Aronov, R. Sedel, and D. L. Souvane. On compatble trangulatons of smple polygons. Computatonal Geometry: Theory and Applcatons, 993, 3:7 35. [] E. Kranas and J. Urruta. Isomorphc trangulatons wth small number of Stener ponts. Internatonal Journal of Computatonal Geometry and Applcatons, 999, 9():7 80. [3] H. Gupta and R. Wenger. Constructng pecewse lnear homeomorphsms of smple polygons. J. Algorthms, 997, ():4 57. [4] O. Achholzer, F. Aurenhammer, F. Hurtado, and H. Krasser. Towards compatble trangulatons. Theoretcal Computer Scence, 003, 96:3-3. Specal Issue. [5] M. Alexa, D. Cohen-Or and D. Levn. As-rgd-as possble shape nterpolaton. Proceedngs of SIGGRAPH 000, pp [6] V. Surazhsy and C. Gotsman. Guaranteed ntersecton-free polygon morphng. Computers and Graphcs, 00, 5(): [7] V. Surazhsy and C. Gotsman. Controllable morphng of compatble planar trangulatons. ACM Trans Graphcs, 00, 0:03 3. [8] V. Surazhsy and C. Gotsman. Hgh qualty compatble trangulatons. Engneerng wth Computers, 004, 0: [9] Jm Ruppert. A Delaunay Refnement Algorthm for Qualty -Dmensonal Mesh Generaton. Journal of Algorthms, 995, 8(3): [0] J.R. Shewchu. Delaunay Refnement Algorthms for Trangular Mesh Generaton. Computatonal Geometry: Theory and Applcatons, 00, (-3):-74. [] M. S. Floater. Parameterzaton and smooth approxmaton of surface trangulaton. Computer Aded Geometrc Desgn, 997, 4:3 50. [] M. S. Floater. Mean value coordnates. Computer Aded Geometrc Desgn, 003, 0:9-7. [3] S.C. Mal. Mathematcal Analyss[M]. New Yor, JohnWley & Sons, Inc., 984: [4] S. Toledo. Taucs: a lbrary of sparse lnear solvers. In Tel-Avv Unversty, 003. ( [5] D.A. Feld. Laplacan smoothng and Delaunay trangulatons. Communcatons n Appled Numercal Methods, 988, Vol.4, pp [6] L.Fretag. On combnng Laplacan and optmzaton based mesh smoothng technques. AMD Trends n Unstructured Mesh Generaton, ASME, 997, vol. 0, [7] L.A. Fretag and M.J., Plassmann. An effcent parallel algorthm for mesh smoothng. 4 th Internatonal Meshng Roundtable, 995, pp Sanda Natonal Laboratores. [8] T.Zhou and K.Shmada. An Angle-Based Approach to Two-Dmensonal Mesh Smoothng. 9th Internatonal Meshng Roundtable, 000, pp Sanda Natonal Laboratores. 8

基于词语关联度的查询缩略*

基于词语关联度的查询缩略* * 基于词语关联度的查询缩略陈炜鹏 1, 付瑞吉 1, 胡熠 2, 秦兵 1, 刘挺 (1. 哈尔滨工业大学计算机科学与技术学院社会计算与信息检索研究中心, 黑龙江省哈尔滨市,150001; 2. 腾讯公司搜索平台部, 广东省深圳市,518057) 摘要 : 冗