《带尖锐特征的Loop细分曲面拟合系统》由会员分享，可在线阅读，更多相关《带尖锐特征的Loop细分曲面拟合系统（7页珍藏版）》请在金锄头文库上搜索。
1、第17卷第6期 2005年6月计算机辅助设计与图形学学报 JOURNAL OF COMPUTER2AIDED DESIGN 修回日期:2004-05-08基金项目:国家自然科学基金(60373034 ,60021201 ,60133020 ,69925204) ;国家重点基础研究发展规划项目(2002CB312102) ;香港城市大学战略研究项目(7001296)带尖锐特征的Loop细分曲面拟合系统李桂清1)马维银2)鲍虎军3)1)(华南理工大学计算机学院 广州 510640)2)(香港城市大学制造工程与工程管理系 香港)3)(浙江大学CAD 尖锐特征;拟合;曲面造型中图法分类号 TP391F
2、itting System Using Loop Subdivision Surfaces with Sharp FeaturesLi Guiqing1)Ma Weiyin2)Bao Hujun3)1)( School of Computer Science and Engineering , South China University of Technology , Guangzhou510640)2)( Department of Manuf acturing Engineeringsharp feature ; fitting; surface modeling1 引 言细分方法研究在
3、模式构造、 连续性分析及其在 多分辨率表示中的应用等方面已经取得了长足发 展1但细分曲面也是一种自由曲面,所能表达物体的复杂程度很有限,需要探讨三维数据的细分曲面反 插及拟合问题1注意到Doo2Sabin曲面1通过其所有控制网格面的中心,Nasri最早提出了一种Doo2Sabin曲面的 顶点和法向插值算法21 同样是从控制网格顶点的 极限位置及其法向出发,Halstead等利用反插技术 使极限位置通过指定点及法向31 考虑到规则情形Doo2Sabin曲面和Catmull2Clark曲面4的等参线分别是二次和三次B样条曲线,Nasri通过把二次和三 次B样条曲线表示成多边形复形的技术分别实现了二
4、次和三次B样条曲线网的插值5271Habib 等8则考虑了中边细分曲面的插值问题1 与上述方 法不同,Levin的方法直接构造插值参数曲线的细 分规则9,使极限曲面最终插值曲线网101 对于大规模网格数据,由于存在测量误差,精确插值并不必要,一般采用拟合方法1Hoppe等系统 地研究了基于细分曲面的重构方法11,通过简化原 始网格获得基网格,并修改基网格的顶点,使修改后 的基网格的相应细分曲面插值原始网格上的对应点1 为表达尖锐特征,他们对Loop模式进行了改造,增加了新的模板使之能生成折痕曲线1 由于采用逐步 求精的方法进行拟合,文献11的重构算法引入了 代价很高的非线性优化过程1Suzuk
5、i等12也考察了Loop曲面的拟合方法,利用交互或简化的方法获取基网格;然后以基网格对原始数据采样,调整控制网格的顶点使得新网格的极限点到相应采样点距离平方之和达到最小1不断地重复这个过程,直到满足精度要求为止1Takeuchi等基于Doo2Sabin曲面对三角网格进行了拟合,并且最终把曲面转换为G1光滑的B样条曲面片131 他们把Doo2Sabin曲面的拟合融合到网格简化过程中,使得简化的结果就是所需要的控制网格1 该方法不直观,且拟合曲面的质量也不理想1Ma等先后研究了基于Catmull2Clark曲面与B样条曲面的散乱点集拟合14和基于带尖锐特征Loop曲面的三角网格拟合151 前者采用
6、交互方法得到物体拓扑的一个线框结构,并在此基础上建立一组B样条基曲面来对散乱点进行分片和参数化16,最后建立了联合B样条和Catmull2Clark曲面的拟合系统;后者则利用改进的QEM (QuadricError Metric)三角网格简化方法得到保持尖锐特征的基网格,作一次细分对原始网格进行重采样,并以此作为细分曲面极限位置1 由于采用最小二乘拟合,从而可以得到较为光顺的曲面1本文描述一个基于文献15中方法的细分曲面拟合系统,并对原方法做了很多细致的改进1 例如,考虑到拟合曲面的质量严重依赖于控制网格的光顺性,引入了基于Laplace算子的切向分量对网格几何进行优化;其次,提供两种以基网格
7、的一次细分对原始网格重采样的新方法1 为缩小求交范围,网格简化时还保存了原始网格中与基网格顶点相关联的三角形表12 系统流程本文系统以三角网格作为输入数据1 整个过程 包括尖锐特征提取、 三角网格简化、 基网格优化、 重采样和曲面拟合等5个步骤1 首先引进下面的记号:M表示原始网格;MF表示从M提取尖锐特征后得到的网格;MFS表示对MF简化后获取的基网格;MFSO表示对MFS作几何和拓扑优化后的基网格;M1 FSO表示对MFSO作一次124细分(可用线性、Loop和蝶形细分)得到M1FSO;MR表示用M1 FSO对原始网格作重采样得到MR;MC表示通过拟合MR求出的控制网格1整个系统流程如图1
8、所示1图1 细分曲面拟合系统流程图3 基网格生成在对给定原始网格进行拟合之前,首先要确定一个与模型具有相同拓扑的基网格1 基网格的好坏直接影响生成曲面的质量,因此它的求取是算法实现比较关键的一环1 求取过程主要包括三个步骤:尖锐特征提取、 三角网格简化和几何及拓扑优化1311 尖锐特征提取尖锐特征是指曲面上C0连续的点构成的集合1由这些点构成的光滑曲线称为折痕1 生成带折痕的细分曲面时,一般先标记折痕边和相应的尖锐特征控制顶点,对折痕边采用边界细分规则1 根据折痕边的条数,网格控制顶点可以分成4类:光滑顶0811计算机辅助设计与图形学学报2005年点、 尖刺、 折痕顶点和角点1 不与折痕边相连
9、的顶点 称为光滑顶点;连入边中只有一条折痕边的顶点称 为尖刺;有两条折痕边的顶点称为折痕顶点;有三条 以上折痕的顶点称为角点1 一条边是否为尖锐边由它的两个共享三角形外法向夹角确定1 当夹角大于指定阈值时,视其为折 痕边1 当两条边界边夹角小于某个阈值时,它们的 共同顶点也标记为角点(边界角点) ,不过在边界角 点处曲面可能是一阶光滑的1312 三角网格简化本文的简化算法基于顶点删除技术1 代价函数 的主要部分为Garland等提出的二次误差171 二次误差1 对于固定顶点方法,边的二次误差代 价函数按下述方法计算15:首先定义顶点v 到v的12邻域模板的距离Q ( v, v)= fNF( v
10、)( Qf( v) )1这里NF( v)是以v为顶点的三角形面集合,而Qf( v)则是v 到 f所在平面的距离1 根据顶点v 的不同类型,其二次误差Qe( v)分别定义为(1)对光滑顶点Qe( v)=min viN1( v)( Q ( vi, v) ) ;(2)对折痕顶点,且( va, v)和( v , vb)为两条相 邻的折痕边,则Qe( v)=min i a, b( Q ( vi, v) ) ;(3)对尖刺或角点,不能被删除,无须计算1顶点删除后形成的多边形洞的剖分1 如果v N1( v)或v va, vb使得Q ( v, v)=Qe( v) ,那么除v 外所有与v相连的面点都改为与v 相
11、连,并 称v 为v的替代顶点1 替代前应作有效性检查,以 保证不会出现翻转面1 对于光滑的三角网格曲面,上述代价函数能够生成高质量的简化网格:网格面接近等边三角形,且 大小与曲面弯曲程度成正比1 但对有平面区域的模 型,由于区域内的顶点代价函数都为零,简化顺序取 决于顶点在网格顶点数组中的排列顺序,因此往往 会产生一些狭长的三角形面1 为此,我们在系统中新增了如下几个代价函数以控制简化网格的质量1 正则性代价1 单是二次误差作为代价函数有时 会导致狭长的三角形面1 一个三角形如果接近等边三 角形,则称其为正则的1 三角形t=( v0, v1, v2)的正 则性可用R ( t)= cos(v0v
12、1v2)+ cos(v1v2v0)+cos(v2v0v1)来度量181 引入Re( t)= 3 - 2R ( t) , 那么0Re( t)1有,且Re( t)越小三角形越正则1三角形集合T的正则性则定义为Re( T) =max Re( t)1 设顶点v被删除后替代顶点为v,重新剖分后v 的邻接三角形集合为NNew F( v) ,那么顶点删除前后顶 点v的正则性增量如图2所示,定义为 Re( v) =Re( NNew F( v) ) -maxRe( NF( v) ) ,Re( NF( v) ) 1图2 边( v , v)的12邻域收缩为顶点v 的12邻域面积代价1 正则性代价只约束了三角形的形
13、状,而不反映其大小1 因此,当正则性在代价函数中 占据较大份量时有可能导致三角形大小相差很大, 顶点v的面积代价定义为Ae( v) = tNF( v)area( t)1总体代价函数1 定义为上述三种代价的线性组 合: Cost ( v) =Qe( v) + Re( v) +Ae( v)1 其 中权值 , 由用户指定1 顶点删除顺序按Cost ( v)从大到小进行1简化轨迹1 以MFSO的一次细分网格对原网格MF进行采样时,要计算细分网格的顶点到MF的最近距离1 如果对MFSO的每个顶点都遍历一次MF 的网格面将会导致二阶复杂度1 一种加速方法是对MF建立包围盒1 本文通过记录简化轨迹,使得MF
14、S中的每个顶点都有一个相关联的三角形表与之对应1 具体算法见文献191313 三角网格优化即使在代价函数中增加诸如正则增量这样的惩 罚项,仍不能保证基网格一定会具有较高的质量,因 此有必要进一步优化1 优化处理分几何和拓扑两种1 几何优化1 通过移动顶点位置最小化某种能量1 实际上,大多数网格光顺算法都属于这类优化1 最简单的光顺算子是Laplace算子v =1 |N1( v)| viN1( v)( vi-v)1顶点的新位置由vnew=v+ v迭代式给出,其中 是松弛因子,一般取值在013015之间1 由于Laplace算子会导致网格收缩,为此提出了很多改进 算法201 本文采用Wood等的切
15、向投影技术21(或 称为重新参数化方法) ,设n为顶点v的单位外法 向,那么Laplace增量的切向投影为 v - ( n v) n1因此,几何优化所用的顶点迭代式为vnew= v +(v - (vn) n)118116期李桂清等:带尖锐特征的Loop细分曲面拟合系统尽管有很多平滑算法都声称能够保持尖锐特 征,但本文并不需要这样的技术1 由于所有的尖锐 特征都作了标记,因此可以采用特殊的迭代式来处 理1 首先,尖刺和角点都不移动;对于折痕顶点v , 如果( va, v)和( v , vb)为与v相邻的两条折痕边, 那么Laplace算子定义为曲线上的操作v =1 2 i a, b( vi-v)
16、(1)类似地,边界顶点也采用式(1)进行优化,以保证边界曲线的质量1 拓扑优化1 除几何优化外,本文系统还考虑了两 种拓扑操作:(1)删除入度为3的顶点1 如图3所示, v 是入度为3的顶点,记它的3个邻接三角形的单位外 法向分别为n0, n1和n2,那么可以用Error( v)= 1 -1 3( n0n1+n1n2+n2n3)来判断三个三角形共面程度1 设定一个小的阈值 0,如果Error( v)01图3 删除入度为3的顶点图4 边交换4 重采样利用第3节的基网格对原始网格进行重采样1为了进行拟合,采样顶点数应比MFSO的顶点数多,因此采样之前先用带尖锐特征的细分模式对MFSO 作一次细分1 本文系统提供了三种细分方法:线性 细分、 带尖锐特征的蝶形细分22223和带尖锐特征的 Loop细分241 直观上看用
