计算机应用   2016, Vol. 36 Issue (9): 2584-2589  DOI: 10.11772/j.issn.1001-9081.2016.09.2584
0

引用本文 

洪程, 章登义, 苏科华, 武小平, 郑昌金. 改进的全局参数化方法[J]. 计算机应用, 2016, 36(9): 2584-2589.DOI: 10.11772/j.issn.1001-9081.2016.09.2584.
HONG Cheng, ZHANG Dengyi, SU Kehua, WU Xiaoping, ZHENG Changjin. Improved global parameterization method[J]. Journal of Computer Applications, 2016, 36(9): 2584-2589. DOI: 10.11772/j.issn.1001-9081.2016.09.2584.

基金项目

湖北省科技支撑计划项目(2014BAA149)

通信作者

洪程(1993-), 男, 湖北荆州人, 硕士研究生, 主要研究方向:计算机图形学, 1044510917@qq.com

作者简介

章登义(1955-), 男, 湖北荆州人, 教授, 博士, 主要研究方向:网络与通信、地理信息系统;
苏科华(1979-), 男, 湖北荆州人, 副教授, 博士, 主要研究方向:计算机图形学、地理信息系统;
武小平(1974-), 男, 湖北武汉人, 副教授, 博士, 主要研究方向:嵌入式系统安全及开发应用;
郑昌金(1992-), 男, 湖北襄阳人, 硕士研究生, 主要研究方向:计算机图形学

文章历史

收稿日期:2016-02-22
修回日期:2016-04-01
改进的全局参数化方法
洪程, 章登义, 苏科华, 武小平, 郑昌金    
武汉大学 计算机学院, 武汉 430079
摘要: 针对多亏格曲面参数化变形较大、运算复杂度高的问题,提出一种改进的基于全纯1-形式的全局参数化方法。该方法以参数化的梯度场为出发点,采用更快速的同调群和上同调群计算方法。首先,利用简化的割图法计算曲面的同调群以确定其拓扑结构;其次,定义特定的调和函数计算闭合1-形式来构造由梯度场形成的线性空间的上同调群;然后,最小化调和能量将上同调群扩散为调和1-形式;最后,线性组合调和1-形式构造出全纯1-形式并在基本域上积分即得到参数化。由上同调群、同调群相关理论分析表明,该方法所得参数化是一种全局的、边界自由的共形映射。基于多组高亏格模型的实验证明,与原有基于全纯1-形式的全局参数化算法相比,本算法视觉效果更好,平均误差更小,运算效率更高。
关键词: 全局参数化    全纯1-形式    调和能量    共形映射    割图    
Improved global parameterization method
HONG Cheng, ZHANG Dengyi, SU Kehua, WU Xiaoping, ZHENG Changjin     
College of Computer, Wuhan University, Wuhan Hubei 430079, China
Background: This work is partially supported by Hubei Science and Technology Support Program (2014BAA149)
HONG Cheng, born in 1993, M. S. candidate. His research interests include computer graphics
ZHANG Dengyi, born in 1955, Ph.D.,professor. His research interests include network and communication, geographical information system
SU Kehua, born in 1979, Ph.D., associate professor. His research interests include computer graphics, geographical information system
WU Xiaoping, born in 1974, Ph.D., associate professor. His research interests include embedded system security, development and application
ZHENG Changjin, born in 1993, M. S. candidate. His research interests include computer graphics
Abstract: Focusing on the issue that non-zero genus surface parameterization has large deformation and high computational complexity, an improved global parameterization approach based on holomorphic 1-form was proposed, which starts from the gradient field and adapts easier and faster method to compute homology and cohomology group. Firstly, a simplified cut graph method was used to construct homology group to determine the topology. Secondly, cohomology group of the linear space formed by the gradient field was calculated by defining special harmonic function to figure out closed 1-form. Thirdly, homology group was diffused to harmonic 1-form through minimizing harmonic energy. Finally, holomorphic 1-form was computed by combining linearly harmonic 1-form and the parameterization was obtained by integrating holomorphic 1-form on the surface basic domain. Theoretical analysis of homology group and cohomology group shows that the parameterization is a global, border-free conformal mapping. Experimental results based on non-zero genus model show that, compared with the former global parameterization based on holomorphic 1-form, the proposed algorithm has better visual effect, smaller average error and higher operation efficiency.
Key words: global parameterization    holomorphic 1-form    harmonic energy    conformal mapping    cut graph    
0 引言

曲面参数化是一种几何处理的基本工具,它将三维曲面投射到标准域(如平面区域、球面、多面体),从而把复杂几何模型的几何处理操作转移到简单几何模型上,大大简化数字几何处理操作,因此广泛应用于纹理映射、曲面可视化、重新网格化和曲面拟合等过程。

参数化本质是一种三维网格曲面与参数域之间的可逆映射关系,一个有效的参数化必须是双射且不能存在网格重叠。理想情况是三角网格曲面与参数域之间的映射等距, 但除可扩展曲面外绝大多数曲面难以实现, 因此在该过程中必定产生图形扭曲。保证有效性的同时使变形最小成为参数化中的关键问题。随着曲面参数化应用愈加广泛,针对不同参数性质的方法相继提出,以下是五种针对零亏格曲面的经典方法。

1) Floater[1]采用网格顶点与其相连接的顶点的凸组合表示三角网格的平面参数化,通过求解线性方程组得到结果;但是该方法要求边界必须为凸多边形,因此极大程度上限制了其实际应用。

2) 能量方程最小化方法关键在于建立能量方程,基于此, 在边界条件下求出极值得到参数化。最早由Eck等[2]引入调和映射并在连续Dirichlet积分基础上提出调和能量方程,因调和映射具有局部保角性,从而使角度变形缩小。随后,Desbrun等[3]给出基于曲面高斯曲率积分的欧拉示性函数,引进并最小化二次能量最终得到与文献[2]类似效果;该方法运算复杂度低,但需要固定边界,因此可能产生较大形变。Sander等[4]提出最大限度地减少纹理在曲面上的位置和方向偏移的最小拉伸方法,Jin等[5]将该方法推广至3D,取得了较好效果。

3) 最小二乘共形映射方法由Lévy等[6]提出,以正交性和齐次空间理论为基础定义连续的共形映射,并使用最小二乘法逼近离散的柯西黎曼方程得到参数化,取得了较好的保角效果;但不能保证结果为双射,意味着可能存在网格局部重叠。

4) Sheffer等[7]提出的保角展平方法将复杂三角网格分割为多个可展面片进行参数化,并列出一系列约束条件,以防止网格展平重叠,最终取得极小的角度形变;但计算量大,也不能解决多边界问题。

5) 最佳等距参数化方法由Hormann等[8]提出, 在原始网格和参数域之间引进线性映射,以求解带约束的非线性系统。该方法在平移、缩放、旋转等变换下度量均为定值, 无需固定边界,但是运算复杂度较高。

上述五种方法均针对零亏格曲面,而在实际应用中多亏格曲面普遍存在,因此将参数化向多亏格曲面推广十分必要。最经典的方法是Gu[9]在2003年提出的基于全纯1-形式的全局参数化方法,基于Hodge理论使用热扩散的方式计算每个上同调类的调和形式,利用Hodge星算子构成全纯形式,这是首次将参数化方法应用到高亏格曲面,为全局参数化开辟新道路。但该方法在奇点的处理效果一般,此外关于同调群和上同调群的构造过程较为复杂,处理速度偏慢。

随后出现了不少基于文献方法扩展的参数化方法及应用。2006年,受到几何处理应用的启发,Ray等[10]结合几何信息,对输入指定的正交向量场提供一种曲率自适应的参数化方法,能实现同时保面积和角度的效果,适合网格化和曲面拟合;但是该方法需指定输入,不能自动完成所有曲面的参数化。Tong等[11]推广到带有锥奇点的1形式方法并用来网格修复和平铺。2009年, Zeng等[12-13]将全纯微分方法应用于计算带多个边界的亏格为0的曲面上的共形映射以及拟共形映射。上述所有的推广方法均在奇点的处理方式提出改进,取得更好的效果,但仍存在提升空间。

除离散全纯微分外全局参数化还有另一种重要方法:里奇流(Ricci Flow),其中较为突出的是cicle packing[14]和circle pattern[15]度量方法。近几年仍有不少学者提出新的全局参数化方法并取得较好的效果。例如2012年Myles等[16]提出基于迭代压扁方式最小化ARAP(As-Rigid-As-Possible)能量的全局参数化方法,并于2014年提出采用交叉场对曲面四边形网格化,实现对任意输入曲面的参数化[17]

为了寻找更优的全局参数化方法,所面临的挑战有:一是对结构更复杂的高亏格曲面,如何准确获取其拓扑信息并降低计算复杂度;二是如何保证参数化的有效性,并最小化形变。针对以上问题,本文基于文献[9]提出以下改进:采用改进的割图法计算同调群;定义特定的调和函数求解闭合1-形式来构造上同调群。同调群和上同调群理论为改进方法的合理性和可行性提供解释,实验采用多组多亏格模型并从适用性、误差和处理速率进行比较,突出改进之处的效果。

1 相关理论 1.1 同调群

给定曲面M,链复形C={Cq, q}包含曲面M的拓扑信息。CqMq维可定向单形(面、边、点)所生成的自由可交换链群,群同态q : Cq Cq-1称为边界算子,满足:q[v0, v1, …, vq]=$\sum\limits_i {{{\left( { - 1} \right)}^i}} $[v0, v1, …, vi-1, vi+1, vq]。

定义1 第q维同调群Hq(C)=Zq(C)/Bq(C),其中Zq(C)=ker q是第q维闭链群,Bq(C)=img q+1是第q维边界链群。所有第q维同调群组成曲面的同调群。

由定义1可知,同调群对各维闭链进行等价分类,反映了曲面的拓扑结构,为参数化的全局性奠定理论基础。例如,H1(C)是由曲面M上一系列非边界的闭合曲线组成,可以简单理解为“圈”的集合。

1.2 上同调群

给定曲面M,上链复形C={Cq, δq}中Cq是曲面M的上链群,q维的上链σq : CqZ是链群Cq与实数域之间的同态,所有的q维上链组成了曲面M的上链群Cq。若对于σqCq, Zq+1Cq+1, 满足:

δqσq, zq+1〉=〈σq, ∂q+1zq+1

则称δq:CqCq+1为上边界算子。

例如,一维上链σ : C1Z是指定义在M有向边上的线性函数。

定义2 第q维上同调群Hq(C)=Zq(C)/Bq(C), 其中Zq(C)=ker δq是上边界算子δq的核,每个元素Zq(C)称作第q维上同调类;Bq(C)=img δq-1是上边界算子δq-1的像,每个元素Bq(C)称作第q维恰当上链。所有q维上同调群组成了曲面的上同调群。

从定义2可知,上同调可以理解为定义在曲面上的线性函数的梯度,所有上同调组成线性空间。与上同调群相关运算有以下两种:

1) 外积运算Λ。对于ω, τH1(M), [v0, v1, v2]∈M, 有:

$\omega \Lambda \tau \left( {\begin{array}{*{20}{c}} {\omega \left( {\left[{{v_0},{v_1},{v_2}} \right]} \right)}&{\omega \left( {\left[{{v_0},{v_1},{v_2}} \right]} \right)}&{\omega \left( {\left[{{v_0},{v_1},{v_2}} \right]} \right)}\\ {\tau \left( {\left[{{v_0},{v_1},{v_2}} \right]} \right)}&{\tau \left( {\left[{{v_0},{v_1},{v_2}} \right]} \right)}&{\tau \left( {\left[{{v_0},{v_1},{v_2}} \right]} \right)}\\ 1&1&1 \end{array}} \right)$ (1)

2) Hodge星算子。对于ω1, ω2H1(M),有:

$\int_{\left[{{v_0},{v_1},{v_2}} \right]} {{\omega _1}{\Lambda ^*}{\omega _2} = \frac{1}{2}\sum\limits_{k = 0}^2 {\cot \left( {{\theta _k}} \right){\omega _1}\left( {{e_k}} \right){\omega _2}\left( {{e_k}} \right)} } $ (2)

Hodge星算子的几何意义是在局部正切空间中,将1-形式ω沿着某顶点的法向旋转90°。

1.3 调和映射

给定光滑的连通曲面M,边界为∂M,g是曲面M上的黎曼度量。假设f:MR是光滑函数,那么函数f的调和能量为:

${E_g}\left[f \right] = \frac{1}{2}\int_M {\left| {df} \right|_g^2{\rm{d}}{A_g}} $ (3)

其中:|·|g是关于度量g的范数,Ag是由g诱导的面元。调和映射就是使调和能量达到临界值的映射。

考虑到计算机处理问题的特性,需引入离散调和能量的概念[8]。设FαM, α=1, 2, …, nM上网格的集合,调和能量转化为:

${E_g}\left[f \right] = \frac{1}{2}\int_M {\left| {df} \right|_g^2{\rm{d}}{A_g} = \frac{1}{2}\sum\limits_\alpha {\int_{{F_\alpha }} {\left| {df} \right|_g^2{\rm{d}}{A_g}} } } $ (4)

对于每个面f有:

$\int_{{F_\alpha }} {\left| {df} \right|_g^2{\rm{d}}{A_g} = \frac{1}{2}\sum\limits_{i,j} {k_{{v_i},{v_j}}^\alpha {{\left| {f\left( {{v_i}} \right) - f\left( {{v_j}} \right)} \right|}^2}} } $ (5)
$k_{{v_i},{v_j}}^\alpha = \frac{1}{2}\frac{{\left( {{v_i} - {v_k}} \right) \cdot \left( {{v_j} - {v_k}} \right)}}{{\left| {\left( {{v_i} - {v_k}} \right) \times \left( {{v_j} - {v_k}} \right)} \right|}};{v_i},{v_j}{v_k} \in {F_\alpha }$ (6)
1.4 调和1-形式

定义3 对于ωH1(M),如果满足

$\Delta \omega \left| {_u} \right. = \sum\limits_{\left[{u,v} \right] \in K} {\omega \left( {\left[{u,v} \right]} \right) = 0;\forall u \in M} $

那么ω即调和1-形式,其中Δ为拉普朗斯算子。

由定义3可知,调和1-形式可理解为调和函数的梯度场,利用调和1-形式可以最小化调和能量。

定理1 给定ωH1(M),存在唯一的调和形式ω′,使得ωω′上同调。

定理2 亏格为g的曲面M,离散调和1-形式组成线性向量空间,维数为2g

1.5 全纯1-形式

定义4 如果ωH1(M)且ω为调和1-形式,那么对应的全纯1-形式为:

$\omega + {\sqrt { - 1} ^*}\omega $

由于Hodge星算子是线性的,所以全纯形式的线性关系由其实部决定。由定理2可推导得,所有全纯1-形式也组成线性空间,维数等于曲面亏格之两倍。

2 算法实现过程

本算法实现思路为:首先求出同调群,找到曲面的所有柄,以确定其拓扑结构;然后计算映射的梯度向量场,即上同调群,通过最小化调和能量将其调整为调和1-形式;最后旋转调和形式,成对组合为全纯形式后在基本域上对其积分即可得到参数化。步骤总结为:

1) 计算同调群基底H1(M)={e1, e2, …, e2g};

2) 计算上同调群基底Ω={ω1, ω2, …, ω2g};

3) 计算调和1-形式ζ={ζ1, ζ2, …, ζ2g};

4) 计算、积分全纯1-形式${\zeta _i} = {\zeta _i} + {\sqrt { - 1} ^*}{\zeta _i}$

2.1 同调群基底

从理论角度探讨,存在诸多计算同调群基底的方法。文献[9]中计算同调群基底的方法是通过诱导边界算子成为Smith标准型。首先将网格采用渐进网格算法[18]简化,例如将4 000个面的网格降为400个面的网格;当找到降采样网格的同调群基底后拉回到原始网格并检查每个顶点的邻域以保证每个基底的连通性;最后采用Dijkstra算法简化基底。

本算法用到割图(cut graph)概念,割图是指三角网格曲面上的一族边集,使得曲面去掉这些边后变成拓扑圆盘。Seifert-van Kampen理论可以证明割图的生成元就是同调群的生成元,因此可将求同调群基底转化为求割图基底。

割图相关算法有tree-cotree decomposition[19],本文基于文献[19]的思想提出用最小生成树构造割图。文献[19]通过不断迭代执行插入和删除操作,动态更新生成元且不断逼近最短割图,最终得到同调群基底。而在参数化中着重点并非寻找最短割图而是梯度场的基底构造,因此采用过程更为简单的最小生成树方法。

得到割图后利用最小生成树方法计算割图基底,对于每个叶子节点都存在到根节点的一条唯一回路,所有的回路便构成同调群的基底。

算法1  计算曲面割图。

输入:曲面M;

输出:曲面割图G

1) 计算对偶曲面${\bar M}$,顶点v的对偶为面${\bar f}$,面f的对偶为顶点${\bar v}$,边e的对偶为${\bar e}$

2) 采用广度优先搜索构造${\bar M}$的最小生成树${\bar T}$

3) 返回G={e|$\bar e \notin \bar T$}。

算法1所得割图G可迭代删除与度为1的顶点相连的边,以减少后期不必要的运算。沿割图G剪开曲面M得到曲面基本域D

算法2  计算同调群基底。

输入:割图G

输出:同调群基底H1(M)。

1) G中选定根节点v,构建最小生成树T,记每个叶子节点vi到根节点v的唯一路径为γi

2) G-T={e1, e2, …, e2g}, 对ekG-T, 且ek =[vi, vj]则存在回路lk =γi[vi, vj]γj-1;

3) 返回同调群基底H1(M)={l1, l2, …, l2g}。

从时间复杂度上分析,文献[9]引进渐进网格算法简化的原因是在诱导中本身会产生大量计算花费,同时这种类似降采样的方式虽然能提高计算效率,但是不能完全保留原始网格信息,对同调群基底的构造具有局限性。当对亏格为g,顶点数为n的网格参数化时,简化网格的时间复杂度为o(n log n),诱导边结算子为Smith标准型的时间复杂度为o(n2),拉回到原始网格后需遍历检查每个顶点的邻域关系o(n),总的时间复杂度为o(n+n log n+n2)。而本算法只需要两次遍历,平均时间复杂度为o(n log n)。相比之下,用改进的割图法求同调群的算法过程更简单,时间复杂度更低。

2.2 上同调群基底

文献[9]先选取任意两个同调群基底并沿基底剪开曲面;然后将剪开的曲面映射到单位矩形或单位圆盘,计算其对偶1-形式;最后将对偶1-形式拉回原曲面,直至所有同调群基底遍历完毕得到上同调群基底。

本算法利用同调群和上同调群的对偶关系定义特定的调和函数计算闭合1-形式,组成上同调群的基底。首先将曲面M沿着割图G剪开得到拓扑盘${\bar M}$,每条半边$\bar h \in \bar M$都唯一对应一条半边hM。将${\bar M}$边界上的点按序排列,${\bar M}$={v0, v1, …, vk, vk+1, …, vn-1}。假定M上的半边hi+, hi-均与边e相邻,那么在${\bar M}$上:

$\bar h_i^ + = \left[{{v_k},{v_{k + 1}}} \right],\bar h_i^ - = \left[{{v_s},{v_{s + 1}}} \right]$

接着构造调和函数fi:${\bar M}$R,满足:

${f_i}\left( {{v_j}} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {0,}&{\forall {v_j} \notin \partial \bar M} \end{array}\\ \begin{array}{*{20}{c}} {1,}&{\forall {v_j} \in \partial \bar M,k < j \le s} \end{array}\\ \begin{array}{*{20}{c}} {0,}&{\forall {v_j} \in \partial \bar M,s < j \le k} \end{array} \end{array} \right.$

然后定义闭合1-形式ωi(h)=dfi(${\bar h}$),那么Ω={ω1, ω2, …, w2g}便组成了上同调群H1(M)的基底。

算法3  计算上同调基底。

输入:亏格为g的闭合曲面M;

输出:上同调群基底H1(M)。

1) 用算法1计算割图G

2) 求G最小生成树T,G-T={e1, e2, …, e2g}。

3) 将M沿着G剪开得到,有序排列边界上的点,={v0, v1, …, vk, vk+1, …, vn-1}。

4) 循环遍历G-T={e1, e2, …, e2g}中每条边ei,与ei相邻的半边为$\bar h_i^ + = \left[{{v_k},{v_{k + 1}}} \right],\bar h_i^ - = \left[{{v_s},{v_{s + 1}}} \right]$,构造函数fi:${\bar M}$R

$f\left( {{v_j}} \right) = \left\{ \begin{array}{l} \begin{array}{*{20}{c}} 1&{{v_j} \in \partial \bar M,k < j \le s} \end{array}\\ \begin{array}{*{20}{c}} {0,}&其他 \end{array} \end{array} \right.$

计算${\omega _i}\left( h \right) \leftarrow d{f_i}\left( {\bar h} \right)$

5) 返回Ω={ω1, ω2, …, ω2g}。

对于亏格为g,顶点数为n的网格,同调群基底数为2g,文献[9]循环遍历剪切网格、映射至单位矩阵,每次的剪切和映射都是针对所有网格顶点,因此工作量较大,时间复杂度为o(n2);本算法只需沿割图裁剪并遍历出割图外的叶子节点即可,时间复杂度为o(n),大大减少了处理时间。

2.3 调和1-形式

由定理1知每个上同调类均对应唯一的调和形式。给定闭合1-形式ω,可添加恰当的闭合1-形式df,使得ω+dfω上同调、ω+df转换为调和1-形式。根据1.3节中离散调和能量的表示式(4)可推出,只需求解下列方程即可得到与ω对应的调和1-形式:

$\Delta f\left( v \right) = \sum\limits_{\left[{v,w} \right] \in M} {{k_{v,w}}\left( {\omega \left( {\left[{v,w} \right]} \right) + f\left( w \right) - f\left( v \right)} \right) = 0} $ (7)

算法4计算调和1-形式的基底。

输入:亏格为g的闭合曲面M

输出:调和1-形式群的基底。

1) 用算法3计算上同调群基底Ω={ω1, ω2, …, ω2g};

2) 循环遍历上同调群的每个基底ωiΩ,通过解方程(7)得以找到fi : MR, 对于所有vM,并计算ωi ωi+dfi

3) 返回Ω={ω1, ω2, …, ω2g}。

2.4 全纯1-形式

由定义6知,可通过调和1-形式和它的共轭估算全纯1-形式。对于亏格为g的闭合曲面M,调和1-形式群为Ω={ω1, ω2, …, ω2g},调和1-形式ω和其共轭*ω能表示为:

$\omega = \sum\limits_{k = 1}^{2g} {{\lambda _k}{\omega _k}{,^*}\omega = \sum\limits_{k = 1}^{2g} {{\mu _k}{\omega _k}} } $

线性系数{μk}可通过解下列方程算出:

$\int_M {{\omega _i}{\Lambda ^*}\omega = \sum\limits_k {{\mu _k}{\omega _k};i = 1,2,\cdots ,2g} } $ (8)

等价于:

$\left( {\begin{array}{*{20}{c}} {\int_M {{\omega _1}\Lambda {\omega _1}} }&{\int_M {{\omega _1}\Lambda {\omega _2}} }& \cdots &{\int_M {{\omega _1}\Lambda {\omega _{2g}}} }\\ {\int_M {{\omega _2}\Lambda {\omega _1}} }&{\int_M {{\omega _2}\Lambda {\omega _2}} }& \cdots &{\int_M {{\omega _2}\Lambda {\omega _{2g}}} }\\ \vdots & \vdots &{}& \vdots \\ {\int_M {{\omega _{2g}}\Lambda {\omega _1}} }&{\int_M {{\omega _{2g}}\Lambda {\omega _2}} }& \cdots &{\int_M {{\omega _{2g}}\Lambda {\omega _{2g}}} } \end{array}} \right)\left( {\begin{array}{*{20}{c}} {{\mu _1}}\\ {{\mu _2}}\\ \vdots \\ {{\mu _{2g}}} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {\int_M {{\omega _1}{\Lambda ^*}\omega } }\\ {\int_M {{\omega _2}{\Lambda ^*}\omega } }\\ \vdots \\ {\int_M {{\omega _{2g}}{\Lambda ^*}\omega } } \end{array}} \right)$

算法5  计算全纯1-形式。

输入:闭合曲面M;

输出:全纯1-形式的基底。

1) 用算法4计算调和1-形式的基底Ω={ω1, ω2, …, ω2g};

2) 循环遍历ωiΩ,将ωi转换成二值向量形式wi

3) 循环遍历fiM*w(f)←nf×w(f);

4) 循环遍历ωiΩ时,遍历每个面fM,计算sksk+wk(f*wk(fnf Af

5) 循环遍历ωi, ωjΩ, i < j,计算wiΛwj, aij ← ∫wiΛwj, aji ←-aij

6) 解方程(aij)(μj)=(si);

7) *ω←∑μkωk*ω即共轭调和1-形式基底;

8) ${\zeta _k} \leftarrow {\omega _k} + {\sqrt { - 1} ^*}{\omega _k}$,返回{ζ1, ζ2, …, ζ2g}。

对全纯1-形式积分是参数化的最后一步,也是纹理映射可视化的过程。选定根节点v0,对其余每个顶点v,在该点到根节点的路径上对全纯1-形式积分,用公式表示为:

$f\left( {{v_i}} \right) = \int_{{v_0}}^{{v_i}} {{\omega _1} + {{\sqrt { - 1} }^*}{\omega _1}} $ (9)

算法6全纯1-形式的可视化。

输入:全纯1-形式{ζ1, ζ2, …, ζ2g};

输出:复形实值函数f: MC

1) 沿割图G剪开曲面M得到基本域;

2) 在${\bar M}$上选取根节点v0,插入顶点队列Qv0

3) While Q!=null,do

    v←pop Q;

    For each [v, w]∈M do

      If w has not been accessed then

        f(w)←f(v)+ω([v, w]);

        Qw;

      End

    End

  End

3 实验结果与分析

实验环境为Windows 8.1操作系统,Intel i5 4200处理器,1.6 GHz主频,4 GB内存。使用VS2010、C++编程实现,采用图形处理库openMesh 3.3,矩阵计算工具Eigen 3.2.4。输入的网格文件格式为off格式,显示网格的可视化软件为基于开源软件MeshViewer二次开发的miniMeshViewer。实验分析将从本算法对高亏格曲面的适用性和对数据的处理效率两方面入手。

3.1 适用性

第一组实验模型如图 1所示,从上到下、从左至右编号为1~6,亏格分别为1、2、3、5、6、7。本算法和文献[9]算法的参数化结果对比如图 2所示。

图 1 第一组实验模型
图 2 本算法和文献[9]的参数化结果对比

一般衡量参数化之好坏主要使用以下两种方法,第一种是通过视觉上的平滑效果进行主观判定,但人眼无法分辨更细微的差异;另一种是采用度量的方法,计算三维网格和参数域之间的几何度量偏差[20],得以衡量整体形变。

首先通过直接的观察判断两种算法的整体效果,由图 2所示知两者对非边界区域的处理均较为合理,无明显的变形。现放大边界处区域进行仔细对比,由于本算法与文献[9]均采用梯度场的方法,生成的同调群基底各有所异,故现在分别考量割图同伦群基底即衔接之处的细节,图 3展示编号为1、3、6模型的局部放大结果。

图 3 本算法和文献[9]的参数化局部放大对比

图 3可知,两者在割图分裂之处均存在不连贯细节,原因在于两种方法均立足于全纯微分方法,差异在于获取曲面拓扑结构和梯度场的构造方法。仔细观察文献[9]所展示的锯齿状更为明显,黑白棋盘的交错更加剧烈,究其根源是采用了渐进算法简化网格,而本算法利用改进的割图方法去构造同伦群基底更加精准,保留曲面的所有信息,故而取得相对连贯的效果,但仍存在改进空间。

然后通过计量顶点和面积的平均相对偏差来估量两者孰优孰劣,计算公式[20]如下:

$\begin{array}{l} Dis{t_{{\rm{area}}}} = \sum\limits_j {{{\left[{\frac{{S\left( {{T_j}} \right)}}{{\sum\limits_{{T_i} \in M} {S\left( {{T_i}} \right)} }} - \frac{{S\left( {T_j^*} \right)}}{{\sum\limits_{{Y_i} \in M} {S\left( {T_i^*} \right)} }}} \right]}^2}} \\ Dis{t_{{\rm{angle}}}} = \sum\limits_j {\left( {\sum\limits_{i = 1,2,3} {{{\left( {\frac{{{A_i}}}{{2\pi }} - \frac{{A_i^*}}{{2\pi + e}}} \right)}^2}} } \right)} \end{array}$

其中: j为网格的三角形个数指标,SA是三角形面积和角度,e表示三角形的角盈。该误差测量是一个整体变形度量,实验数据如表格1所示。

表 1可对比得,当曲面亏格越高,两者的误差差距更加明显,证实本文算法相对文献[9]取得更小的平均误差。其中缘由在于本文算法采用调和函数计算闭合1-形式去构造梯度场的基底,更贴近曲面的真实情况,文献[9]基于映射到单位矩形或单位圆盘求对偶1-形式的方法不可避免会对梯度场造成扭曲,故而产生额外的误差。综合直观效果和误差数据分析,总体上说,本文算法实现了对高亏格曲面的参数化,并取得较小的形变误差。

表 1 本算法与文献[9]算法的误差对比
3.2 处理效率

为了凸显本文算法效率的提高,第二组实验采取数据规模更大的实验模型,如图 4所示,从上到下、从左至右编号分别为7~12。关于第二组实验模型的数据属性和实验结果如表 2所示。因每次实验需随机取点以计算同调群基底,而其所生之基底皆相异,所以采用平均时间来度量。

图 4 第二组实验模型
表 2 本文算法与文献[9]算法的处理效率对比

表 2可知,随着亏格和曲面的规模越来越高,计算时间的差异越来越大,可知本文算法相对于文献[9]所述方法,在计算速度上有较大提高。考虑算法本身的平均时间复杂度是o(g3n log n),与网格的大小(点、边、面数)、亏格g有关,取得提升的根本原因得益于求同调群和上同调群过程的简化。一方面,基于割图的思想且绕开寻找最优割图采用最实用的最小生成树方法计算割图及其基底,降低了构造同调群的时间花销;另一方面,采用特定的调和函数逐一计算同调群基底的对偶形式,避免重复剪开、映射曲面的中间过程,精简了计算过程。

4 结语

本文基于文献[9]改进的全局参数化方法利用同调群和上同调群的理论对多亏格曲面实现了更连贯的视觉效果和更高的处理效率,并且能控制角度和面积平均误差在更小的范围内,因此提高了在实际应用如纹理映射中的适用性。但是在曲面同伦群基底的边界处理上仍有提升的空间,未来将深入探究如何在不同的参数化结果中筛选最优解。

参考文献
[1] FLOATER M S. Parametrization and smooth approximation of surface triangulations[J]. Computer Aided Geometric Design, 1997, 14 (3) : 231-250. doi: 10.1016/S0167-8396(96)00031-3 (0)
[2] ECK M, DEROSE T, DUCHAMP T, et al. Multiresolution analysis of arbitrary meshes [C]// SIGGRAPH '95: Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1995: 173-182. (0)
[3] DESBRUN M, MEYER M, ALLIEZ P. Intrinsic parameterizations of surface meshes[J]. Computer Graphics Forum, 2002, 21 (3) : 209-218. doi: 10.1111/cgf.2002.21.issue-3 (0)
[4] SANDER P V, SNYDER J, GORTLER S J, et al. Texture mapping progressive meshes [C]// SIGGRAPH '01: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2001: 409-416. (0)
[5] JIN Y, QIAN G P, ZHAO J Y, et al. Stretch-minimizing volumetric parameterization[J]. Journal of Computer Science and Technology, 2015, 30 (3) : 553-564. doi: 10.1007/s11390-015-1545-y (0)
[6] LÉVY B, MALLET J L. Non-distorted texture mapping for sheared triangulated meshes [C]// SIGGRAPH '98: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques. New York:ACM, 1998: 343-352. (0)
[7] SHEFFER A, DE STURLER E. Parameterization of faceted surfaces for meshing using angle-based flattening[J]. Engineering with Computers, 2001, 17 (3) : 326-337. doi: 10.1007/PL00013391 (0)
[8] HORMANN K, GREINER G. MIPS: an efficient global parametrization method [EB/OL]. [2015-11-23]. http://www.inf.usi.ch/hormann/papers/Hormann.2000.MAE.pdf. (0)
[9] GU X, YAU S T. Global conformal surface parameterization [C]// SGP '03: Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. Aire-la-Ville, Switzerland: Eurographics Association, 2003: 127-137. (0)
[10] RAY N, LI W C, LÉVY B, et al. Periodic global parameterization[J]. ACM Transactions on Graphics, 2006, 25 (4) : 1460-1485. doi: 10.1145/1183287 (0)
[11] TONG Y, ALLIEZ P, COHEN-STEINER D, et al. Designing quadrangulations with discrete harmonic forms [C]// SGP '06: Proceedings of the 4th Eurographics Symposium on Geometry Processing. Aire-la-Ville, Switzerland: Eurographics Association, 2006: 201-210. (0)
[12] ZENG W, YIN X, ZHANG M, et al. Generalized Koebe's method for conformal mapping multiply connected domains [C]// SPM '09: Proceedings of the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling. New York: ACM, 2009: 89-100. (0)
[13] ZENG W, LUO F, YAU S T, et al. Surface quasi-conformal mapping by solving Beltrami equations [M]// HANCOCK E R, MARTIN R R, SABIN M A. Mathematics of Surfaces XIII, LNCS 5654. Berlin: Springer, 2009: 391-408. (0)
[14] RODIN B, SULLIVAN D. The convergence of circle packings to the Riemann mapping[J]. Journal of Differential Geometry, 1987, 26 (26) : 349-360. (0)
[15] KHAREVYCH L, SPRINGBORN B, SCHRÖDER P. Discrete conformal mappings via circle patterns[J]. ACM Transactions on Graphics, 2006, 25 (2) : 412-438. doi: 10.1145/1138450 (0)
[16] MYLES A, ZORIN D. Global parametrization by incremental flattening[J]. ACM Transactions on Graphics, 2012, 31 (4) . (0)
[17] MYLES A, PIETRONI N, ZORIN D. Robust field-aligned global parametrization[J]. ACM Transactions on Graphics, 2014, 33 (4) . (0)
[18] HOPPE H. View-dependent refinement of progressive meshes [C]// SIGGRAPH '97: Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1997: 189-198. (0)
[19] EPPSTEIN D. Dynamic generators of topologically embedded graphs [C]// SODA '03: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: SIAM, 2003: 599-608. (0)
[20] 胡国飞, 方兴, 彭群生. 凸组合球面参数化[J]. 计算机辅助设计与图形学学报, 2004, 16 (5) : 632-637. ( HU G F, FANG X, PENG Q S. Convex combi nation spherical parameterization[J]. Journal of Computer-Aided Design and Computer Graphics, 2004, 16 (5) : 632-637. ) (0)