一类复杂区域的网格优化算法
2017-08-08李丹,曹敬
李 丹, 曹 敬
(河海大学 计算机与信息学院, 南京 210098)
一类复杂区域的网格优化算法
李 丹, 曹 敬
(河海大学 计算机与信息学院, 南京 210098)
近年来自由曲面设计得到了广泛应用，尤其在建筑曲面设计领域。逼近自由曲面的方法有很多种，一种方法是采用平面四边形网格(PQ网格)逼近自由曲面，所以平面四边形网格的质量直接影响了自由曲面设计的质量。介绍了一种平面四边形网格优化算法，判断出复杂区域，采用局部采样点加密和光顺方法相结合进行处理，在整体上采用平面化和细分方法相结合策略优化网格。通过该方法，生成的自由曲面不仅质量得到了提高而且具有了美学效果。
自由曲面设计； 平面四边形网格； 细分； 光顺
0 引言
近年来,在自由曲面设计、三维动画、计算机辅助几何设计，真实感图形绘制等领域,平面四边形网格(PQ网格)得到了越来越多的应用。同三角网格较为自由的拓扑连接关系不同,四边形网格的连接更为规则,并且根据实际的需要大都沿着主曲率方向分布,所以相比三角形网格更能反映网格所表示几何形体的形状变化,符合人们对形状的自然感知。所以比三角形网格更为直接地应用在几何造型、细分曲面、建筑设计等方面。所以生成有效且质量高的平面四边形网格(PQ网格)非常重要。PQ网格的几何性质和优化过程由KOBBEL.TOL[1]给出。根据以往研究知道具有PQ网格的自由曲面结构要优于具有三角形或非平面四边形网格的自由曲面结构，所以平面四边形网格具有研究价值。但是在以往的研究中，并没有考虑四边形网格的拐角或是皱痕部分等复杂区域，所以在本文中我们会着重处理四边形网格的复杂区域。
PQ网格作为自由曲面设计的基础具有很多的约束，不仅要求网格面是平面，还要符合一定的美学要求。在一些版本中，PQ网格也可以看作曲面上的共轭曲线网格，共扼曲线网格定义为曲面上的两组单参数曲线v，w，它们在曲面上任意一个顶点x上的切向量互相共扼。这两组切向量场构成了一个交叉场，我们称之为共扼方向场。
对于四边形网格的提取,我们采用Alliez等人[1]提出的各向异性四边形网格化算法,在模型的各向异性区域,根据预定的采样密度,逐条导出各向异性分布的主曲率线,据此生成各向异性四边形网格,在球面或平面区域则均匀布点,生成三角形网格,最终得到各向异性的四边形主导的主曲率网格。尽管得到的网格不能保证网格面是平面，但是至少是逼近平面的。像这样的主曲率网格可以作为我们算法的输入网格。
四边形网格化是在曲面上生成四边形网格的过程。利用曲面上的交叉向量场，追踪曲线或全局参数化方法生成四边形网格[2-11]。在本文中，我们采用从平滑的主曲率线提取四边形网格的方法来生成四边形主导的主曲率网格。
1.2 相关工作
平面四边形网格化近年来已成为热点，关于如何生成高品质的平面四边形网格的研究很多。香港大学的刘等人[12]在ACM transactions on Graphics发表的Geometric Modeling with Concal Meshes and Developable Surfaces提出了从主曲率线中提取四边形网格,扰动与细分相结合的算法获得四边形网格的平面性。
微软亚洲研究院的刘等人[13]在ACM transactions on Graphics发表的General Planar Quadrilateral Mesh Design Using Conjugate Direction Field提出了允许存在k/4个奇点的共轭方向场(CDF)的研究。将自由曲面三角形离散化，计算满足用户方向和角度限制的近似平滑的共轭方向场，采用四边形网格化和平面化技术相结合生成PQ网格。
德国亚琛工业大学的Bommes等人在ACM transactions on Graphics发表的Mixed-integer quadrangulation提出的保证交叉区域与主曲率线对齐，通过连续离散优化将四边形网格和主曲率线对齐，得到了近似平面的网格。
1 平面化
1.1 平面性优化
(1)
另外，该算法引入两个能量项确保得到的平面网格有光顺的形状。为了设计的美学要求，采用光顺项ffair和f2nd，其简化了网格的行和列的多边形弯曲能量,为式(2)(3)。
(2)
(3)
在边界上不是所有的点都需要计算，所以规定没有定义的点的平方值设为零。PQ网格需要贴近原始网格Φ，因此要保证扰动的点与原始网格Φ的距离要最短,如式(4)。
(4)
其中，yi,j是网格Φ上关于原始点vi,j的优化后得到的点。
将以上所有项定义成Lagrangian函数为式(5)。
(5)
此时将平面化算法转化成了非线性带约束问题。
序列二次规划法求w1ffair+w2f2nd+w3fclose的最小能量值，其中令约束cpq=0。也就是说最小值给出了一个PQ网格，其有一个光顺的形状并贴近原始网格。这个最小值是Lagrangian函数fpq的拐点，其中w1、w2和w3是用户用来控制网格光顺程度和质量的。
对于实际更新步长αh我们使用平滑的线性搜索算法得到，其中0<α≤1，x更新为x*=x+αh。
对于输入的网格近似为共轭曲线网络时，该算法的效果明显。若输入网格不理想时，则通过此算法优化的网格与原始网格有很大的偏差。所以输入网格一般采用主曲率网格,如图1所示。
图1 主曲率网格
图1主曲率线四边形网格应用PQ扰动，保证了几乎所有的面都是平面四边形。但是我们可以看出标出的四边形网格平面性质量不是很好。
1.2 细分方法
对于细分算法我们选用Catmull-Clark细分。Catmull-Clark细分是最早提出的一种细分曲面算法。由于细分规则的简单性和理论基础的完备性，Catmull-Clark细分曲面至今仍是最受关注、应用最广泛的细分曲面造型方法之一,如图2所示。
(a)
(b)
(c)
1.3 点邻域平坦度计算
当k(vi)
图3
在一般情况下，复杂区域具有更高的噪音影响和更复杂的拓扑结构，平坦区域很容易实现网格的平面性等一些属性，在曲率较大的复杂区域则很难得到同样的效果。所以在复杂区域我们需要对每个点的邻域进行细化，满足原始网格特征的同时，也获得该区域的平滑性和平面性。所以在复杂区域我们需要增加采样点并且保证该区域的光顺性，很自然地我们想到采样点加密和光顺相结合的策略。
本文采用类似浙江大学的王仁芳[15]提出的基于球面参数化的点模型渐变算法实现采样点加密。首先对我们提取出的复杂区域模型进行球面参数化，使得参数化之后的模型嵌入到单位球面上，然后在球面上自适应地对齐模型间的相应特征点，并将球面映射到矩形参数域上，基于该域建立模型间采样点的对应关系，采用拉普拉斯算子计算出中间点模型的几何位置，最后利用移动最小二乘曲面进行动态采样，实现采样点加密。
对于光顺方法我们采用清华大学的胡事民[16]提出的基于曲率流的四边形主导网格的光顺方法来实现,如图4所示。
(a)初始网格(b)提取出的复杂区域(c)多次应用采样点加密和光顺算法得出的网格
图4 光顺方法
由此可以看出经过采样点加密和光顺算法的应用复杂区域有了明显的改善。
2 细分与平面化结合
上文处理了复杂区域，在整体上我们采用Catmull-Clark细分方法和平面化算法相结合的策略，对网格模型进行平面化处理。首先完成初始网格的细分，细分的程度可根据情况而定。接下来是平面化。因为细分过程会破坏平面性，通过平面化算法又保证了平面性。此过程反复应用，直到达到所需的平面和细分程度,如图5所示。
(a)原始网格模型(b)一次迭代细分与平面化(c)二次迭代
图5 平面和细分程度
3 总结
相对于之前的不分区域的平面化和细分方法结合算法，在加入区域划分之后的算法可以对网格质量有很好的提高.首先对复杂区域进行采样点加密和光顺，然后整体上应用细分与平面化相结合的策略满足了网格模型的质量要求。但是若输入网格不理想时，通过此算法优化的网格与原始网格有很大的偏差。所以在本文中我们选择主曲率线网格。复杂区域不仅包括曲率较大区域，还包括奇异点邻域。本文没有考虑奇异点邻域，这也是以后本文研究的重点。
[1] BOMMERS D., VOSSEMER T., KOBBELTo L. Quadrangular parameterization for reverse engineering[C]//Proc. of the MMCS 2008. LNCS 5862, 2010.
[2] ALLIEZ P.,COHEN-STEINER D.,DEVILLERS O.,et al.Anisotropic polygonal remeshing[J].ACM Trans. On Graphics,2003,22(3):485-493.
[3] MARINOV M.,KOBBELT L.Direct anisotropic quad-domint remeshing[C]//12th Pacific Conference on Computer Graphics and Applications.2004.
[4] RAY N.,LI W.,LEVY B.,et al.Periodic global parameterization[J].ACM Trans.on Graphics,2006,25(4):1460-1485.
[5] DONG S.,KIRCHER S.,GARLAND M.Hannonic functions for quadrilateral remeshing of arbitrary manifolds[J].Computer-Aided Geometrie Design.2005,22(4):292-423.
[6] TONG Y.,ALLIEZ P.,COHEN-STEINER D.,DESBRUN M.Designing quadrangulations with discrete hamonic forms[C]//Eurographics Symposium on Geometry Proeessing.2006.
[7] EBKE H.,BOMMES D.,CAMPEN M.,et al.Robust quad mesh extration[J].ACM Trans GraPh.2013,32(6):2504-2507.
[8] HUANG H.,ZHANG M.,MA J.,et al．Spectral Quadrangulation with Orientation and Alignment Control[J]．ACM Transactions on Graphics.2008,27(5),1-9.
[9] KALBERER F.,NIESER M.,POLTHIER K.Quadcover-surface parameterization using branched coverings[J]. Computer Graphics Forum, 2007, 26(3):375-384.
[10] BOMMES D., ZIMMER H., KOBBELT L.Mixed-Integer quadrangulation[J]. ACM Transactions on Graphics, 2009,28(3):1-10.
[11] LAI Y., KOBBELT L., HU S.An incremental approach to feature aligned quad dominant remeshing[C]//Proc. of the 2008 ACM Symp. on Solid and Physical Modeling. 2008.
[12] YANG Y.,LAI Y.,HU S.,et al.Robust principal curvaturesv on multiple scales[C]//Proceedings of 4th Eurographics Symposium on Geometry Processing Eurographics Association.2006.
[13] LIU L.,XU W.,WANG J.,et al.General Planar Quadrilateral Mesh Design Using Conjugate Direction Field[J].ACM Transactions on Graphics.2011,30(6), 140:1-140:10.
[14] LIU Y.,HELMUT P., WALLNER J.,et al.Geometric Modeling with Concal Meshes and Developable Surfaces[J].ACM Trans.Graphics.2006,25(3):681-689.
[15] 王仁芳,张三元,叶修梓.基于球面参数化的点模型渐变[J].中国图象图形学报,2009,14(3):552-559.
[16] 胡事民，来煜坤，杨永亮，基于曲率流的四边形主导网格的网格方法[J].计算机学报,2008,31(9):1622-1628.
Mesh Optimization Algorithm for a Class of Complex Regions
Li Dan, Cao Jing
(College of Computer and Information, Hohai University, Nanjing 210098, China)
In recent years,freeform design has been widely used，especially in the field of architectural freeform design. There are many kinds of methods to approximate a freeform shape. One method is to approximate a freeform shape with a planar quadrilateral (PQ) mesh. So the quality of the PQ mesh directly affects the quality of the freeform shape design. This paper describes a planar quadrilateral mesh optimization algorithm. We first determine the complex regions, and combine up-sampling and fairing algorithms, then totally combine planar quad mesh with subdivision method. By this method, the freeform shapes not only improve the quality, but also have the aesthetic.
Freeform shape design; Planar quad mesh; Subdivision surface; Fairing
李 丹(1971-),男,硕士研究生，研究方向:计算机图形学。 曹 敬(1968-)，男,工学博士，教授，研究方向:分布式处理及其软硬件混同设计、网络与信息安全等。
1007-757X(2017)07-0052-03
TP39
A
2016.12.20)
