三角网格模型

2024-06-07

三角网格模型（共7篇）

三角网格模型篇1

摘要：纹理映射可以在不增加三维模型复杂度的前提下很好地表现三维模型表面的纹理细节,提高三维模型的视觉效果。针对三维网格模型,提出一种用基于纹理图册的方法将模型进行分片,并利用最小二乘保形映射对分割得到的每一片进行平面参数化,控制了形变。再通过建立二维坐标系与纹理坐标系的关系,确定三维模型各个顶点的纹理坐标,从而对三维模型进行纹理映射。实验证明,该方法能得到较好的纹理映射效果,增强了三维模型的真实感。

关键词：纹理映射,平面参数化,纹理坐标,三维模型分割,纹理重建

0 引言

在计算机应用领域,对现实世界中三维物体的模拟重建是最主要的研究方向之一。计算机辅助设计、动画制作、虚拟现实等领域都希望在计算机上实现对真实物体的逼真再现。除了几何细节,真实的三维物体还有丰富的表面纹理信息,所以三维物体重建并不仅限于几何重建,还包括纹理重建。只有将几何信息和纹理信息融合在一起才能完整重建出高度逼真的三维彩色物体模型。纹理映射技术可以在不增加模型复杂度的前提下很好地表现模型表面的纹理细节,提高视觉效果,是重建真实感三维物体的重要技术之一。

纹理映射是将已获得的包含纹理信息的二维纹理图像映射到三维物体表面[1]。在映射过程中,纹理图像的各个像素通过三维网格模型各个顶点的纹理坐标被分配到三维网格的对应顶点,从而将整个纹理图像映射到三维模型上。所以纹理映射的本质是对三维网格模型的二维参数化,即求三维网格模型中每个三维点的纹理坐标[11]( 每个三维点在二维纹理空间中的坐标) 。

在纹理映射领域,针对参数曲面,早期的纹理映射算法有递归分割参数曲面的Catmull算法和反向纹理映射的Blinn算法[4]。对于非参数化模型,Bier等提出了两步纹理映射方法[4]。Song Yong Park等人通过物体不同姿态来获取轮廓和表面信息,最后通过多视觉建模完成了纹理映射[4]。纹理映射需要解决的主要问题一是纹理图像准确定位到相应的几何模型上; 二是纹理重建过程中纹理的扭曲和变形。如在模型曲率较大的地方,会出现比较严重的纹理变形。对于用三角网格表示的三维模型,减少变形的主要方法就是对三维模型的参数化过程进行优化。三角网格模型参数化的主要的方法有: 平面参数化、球面参数化[5]。球面参数化主要将网格参数化到它拓扑同构的球面,研究者提出了基于网格简化,基于松弛等球面参数化方法。但算法的时间复杂度较高,在将球面模型映射到二维的纹理空间时,会引入新的形变。而平面参数化方法以其简单稳定的特点成为学术研究和工程应用最为广泛的方法[5]。

平面参数化即把三角网格尽可能均匀的展平到二维区域中。在平面参数化中研究者又提出了等积映射、调和映射、保角映射等方法来减小变形失真[5]。而大多数研究者只是研究如何将单个开放面片参数化到平面中,然后进行纹理映射。本文以由三角网格表示的三维非规则封闭模型作为研究对象。采用一种用基于纹理图册的方法将模型进行分片,并利用最小二乘保形映射作为每片的平面参数化方法,再建立二维坐标系与纹理坐标系的关系,从而确定三维顶点的纹理坐标系,得到了较好的纹理映射效果。

1 纹理映射原理介绍

1. 1 纹理映射

纹理映射就是建立从二维纹理坐标空间到三维物体拓扑空间的映射[1],它一般遵循如下几个步骤:

1) 建立二维纹理到简单几何体的映射;

2) 建立简单几何体到三维物体拓扑空间的映射;

3) 通过简单几何体,建立起从三维物体拓扑空间到二维纹理空间的纹理映射。

而平面参数化方法即选用平面作为中间简单几何体,如图1 所示。

因此基于平面参数化的纹理映射过程如图2 所示,其中,( 1) 平面参数化; ( 2) 平面空间到纹理空间; ( 3) 纹理空间到三维几何空间。

1. 2 保形映射

如果曲面S上的任意两条曲线的夹角与相应参数域中的对应夹角相等,即说明从曲面S到对应平面的映射是保形映射[7]。如图3 所示,二维空间中的点( u,v) 经过X关系映射到三维曲面上一点X( u,v) ,如果对于二维空间中所有的点( u,v) ,X映射都满足式( 1) ,则X映射即为保形映射。向量N表示三维曲面的单位法向量。

定理从曲面S到平面S*的映射X是保形映射当且仅当这个映射X的第一基本形式JX的系数的变化比例相同,即σ1= σ2。即二维平面上的单位圆经过保形映射到三维曲面上仍然是一个圆,如图4 所示,图中,二维空间中的点u映射到三维空间上的点p,同时二维空间中的以点u为圆心,r为半径的圆映射到p的切平面上成为一个以p为中心的椭圆,长短轴分别为σ1和 σ2。

2 本文算法

本文采用了一种用基于纹理图册的方法将模型进行分片,并利用最小二乘保形映射作为每片的平面参数化的纹理映射方法,算法流程如图5 所示。

本文采用的纹理映射方法是先将闭合曲面分割成一组同构于圆盘的可展曲面,然后再对分割后的每个曲面进行平面参数化。为了不使纹理映射后的模型由于此步而出现明显接缝,本文选择在形状和光照变化比较大的高曲率处进行分割,然后利用LSCM方法[7]参数化分割生成的一组可展曲面,并根据特征点的信息。通过最小化投影误差,得到相应的信息,从而求得从三维模型到二维纹理的映射关系,用得到的映射关系将三维模型重新映射到二维纹理上得到三维模型每一点在此二维纹理上的位置,最终得到带有纹理的三维几何模型。

2. 1 三维模型分割

由于基于保形映射的平面参数化只适用于等价于圆盘的可展曲面,所以必须先将闭合曲面分割成一组等价于圆盘的可展曲面。然后才可以对分割后的每个曲面进行平面参数化。为了不使纹理映射后的模型由于曲面分割而出现明显接缝,选择在形状和光照变化比较大的高曲率处进行分割,可以减小接缝对于最终纹理映射真实感的影响。因此本文选用的三维模型分割方法是一种基于曲率的特征曲线网格分割算法———DFEC( detect feature expand charts) 算法[8]。具体算法如下:

1) 通过基于边关联面的法向量夹角( SOD) 检测特征曲线,为避免获得过多特征曲线,设定最小特征长度阈值,只保留部分满足条件的特征曲线;

2) 以特征曲线为边界,从边界向内传播,计算其他三角面到特征曲线的距离;

3) 以距离函数的极值点作为种子点,使用多源Dijkstra算法,同时从多个种子点进行区域扩展;

4) 如果两个区域在距离种子点距离足够小的地方相遇,则合并这两个区域。

由于此算法没有迭代过程,因此具有较高效率,而且分割结果完全可以满足平面参数化算法的需要。

2. 2 利用LSCM( Least Squares Conformal Maps) 方法参数化

在得到一组可展并等价于圆盘的曲面后,需要对这些曲面进行参数化处理,将曲面参数化到同一个平面,形成一个用于纹理映射的空白的纹理Atlas图。本文采用最小二乘保形映射( LSCM) 方法[7]对曲面进行平面参数化处理。该算法的原理是对于每一个三角面片通过最小二乘逼近Cauchy-Riemann等式,使其满足保形映射要求。算法具体过程如下:

1) T表示拓扑等价于圆盘的三角网格模型:

其中,表示n个顶点,Γ 表示顶点组成的三角形。

2) 为每个三角形构建一个位于三角形所在平面的局部正交基( x,y) ,法向量同向于z轴。

3) 对于每一个三角面片T,都可以用上步定义的局部正交基表示,因此,映射u( R3 - > R2 的映射) 可以表示为( x,y) - >( u,v) 。根据Cauchy-Riemann方程,u为保形映射当且仅当满足下式:

由于不可能使每一个三角面片严格满足等式( 4) ,因此需要构造整体最小二乘约束的保形映射,即使式( 5) 的值达到最小:

4) 假设映射u在每个三角面片上都是线性映射,式( 5) 可以改写为:

其中,A( T) 为三角面片T的面积。

5) 假设ui= ui+ ivi( i = 1,2,…,n) ,可以将C( k) 化简为二次型形式:

其中u = ( u1,u2,…,un) ,M为m × n矩阵。

6) 为了使等式有唯一解,需要固定p个顶点( p > = 2) ,将向量分成uf、up,M = ( Mf,Mp) ,式( 7) 可改写为:

其中Mf是m × ( n - p) 阶矩阵,Mp是m × p阶矩阵。

7) 通过共轭梯度法求解上式的平方和最小化问题,并将平面参数化后的各个平面归一化到同一平面,生成一个空白待映射的纹理Atlas图,并得到每个三维顶点在此图中的坐标( u,v) 。

三维模型及其平面参数化处理后的结果如图6 所示。

2. 3 计算从三维模型到二维纹理的变换关系

计算从三维模型到二维纹理的变换关系即通过约束点计算恢复相机的参数,得到变换关系。然后用得到的变换关系将整个模型重新映射到二维图像上,得到每一点在图像上的位置。即通过式( 9)[9]计算三维模型上的点在二维纹理上的位置。

其中K为相机的标定矩阵( 相机的内部参数信息) ,R为一个旋转矩阵,C为一个平移矢量,通过最小化误差函数式( 10) 来得到变换关系T 。

由于本文对三维模型进行纹理映射的二维纹理图像和三维模型的状态不能高度一致。如果对所有顶点都采用同一个全局变换关系进行变换,会导致模型和图像不能准确对应,结果产生很大变形。因此为了使二维图像能够准确映射到三维模型相应位置上,本文采用的算法是根据每个顶点到约束点的欧式距离,得到每个点的权重,为每个顶点计算一个变换关系。而随之出现的相邻顶点的变换关系相差很大而导致纹理变形问题可以通过按一定顺序处理各个顶点的方法来解决。计算三维模型每个点变换关系的具体算法过程如下:

1) 计算顶点v到约束点pi的距离D( v,pi) ,并且计算顶点v对于约束点pi的权重:

其中,α = 10-3,β = 2 。

2) 在顶点v处的变换关系为:

( 1) 式( 12) 可以用相机模型改写为:

其中,为从三维空间到二维图片的投影矩阵,c( v)∈ R2为二维平面上的变换矩阵,而且m1(v) Tm2(v)= 0 。假定相机在x、y轴上有相同的缩放比例,则

( 2) 通过最小化误差函数求得M和c ,从而得到每个顶点的最优的变换关系,即求在该点处的一个变换关系,使所有约束点对( pi- qi) 在该关系下的误差和达到最小,即使式( 15) 达到最小:

( 3) 式( 15) 可以改写为:

使误差和式( 16) 达到最小,即可求得该点处的变换关系。

为防止可能出现的由于相邻顶点的变换关系很不同而导致纹理变形。本文通过这样的处理顺序来依次处理每个顶点: 选取到所有约束点距离之和最小的顶点为中心点,其余点按照广度优先排序,每个点v的M( v)的初始估计值为定义为该点在广度优先搜索树中父节点u的M值( 中心点v0的M值的初始估计值通过奇异值分解的方式求得) 。

2. 4 颜色映射

通过以上算法,可以得到从三维模型到二维参数域和从三维模型到二维图像的变换关系。最后需要把二维纹理图像上的颜色信息添加到参数域中的相应点上,如图7 所示。

将二维纹理图像上的颜色信息映射到二维空白atlas上,atlas中的每个像素用二维纹理图像中的IS( T( TA-1( qA) ) ) 处的颜色信息映射。

3 实验结果及分析

本文使用Kinect扫描获取真实的三维模型数据,使用相机获取二维纹理信息,在Windows环境下,结合VC ++ 、VTK和Open NL实现了上述算法。将与三维模型不高度对应的二维纹理信息准确映射到三维模型的相应位置,提高了三维模型的真实感。图8、图9 三维模型纹理映射上的效果图。

由图可以看到,二维纹理信息和三维模型的初始位置不同,本文映射方法可以较好地将二维纹理信息映射到三维模型上,增强了三维模型的真实感,为三维模型的进一步应用提供了很好的基础。

4 结语

本文针对三角网格模型提出一种基于保形映射的平面参数化和逐点计算变换关系的纹理映射方法,并通过实验验证了本文方法的有效性。该方法不要求二维纹理和三维模型初始位置高度对应,能够得到很好地映射效果,而且大大减少了传统方法中的纹理变形问题,增强了三维模型的真实感。该方法仍存在很多不足,如在计算三维到二维变换关系是需要人为指定约束点,虽然提高了约束点的准确性,但是自动化程度不高,能够自动准确标定约束点,使得该算法有待进一步的改进,是未来研究的方向。

三角网格模型篇2

三角网格模型是一种被广泛应用于3D建模和计算机图形中的三维模型表示方法, 它将模型的不规则曲面划分成一个个大大小小的边相邻的三角形的片元, 通过存储片元上的顶点和边的信息来构建三维模型, 相比于相等精度的体素模型, 能够大大减小模型的存储量, 提高模型的绘制速度, 并且能够根据需要调整片元的大小来提高模型的精度。

三角网格模型可以通过各种方法产生, 可以用3D扫描仪扫描物体表面获取点云, 再通过对点云进行曲面拟合形成面模型, 也可以对体素数据进行目标分割, 对分割后的结果进行面重建形成网格模型。但是, 由于产生网格模型的方法的局限性, 例如因为3D扫描仪扫描物体局部区域的点云缺失, 或者因为体素数据分割造成的目标物体不完整, 又或者是因为面重建算法本身的缺陷, 可能会产生具有空洞的非完全封闭的网格模型。这种模型不符合实际物体构造也不符合审美观, 最重要的是可能会对后续的处理如模型平滑、细化等产生不良影响, 所以必须对这种带空洞的非封闭模型进行修正, 填补面模型中缺失的部分, 形成封闭的网格模型[10]。

1 相关工作

目前, 很多研究人员都对网格模型的空洞填补做过研究, 提出了很多方法, 这些方法主要可以分为两类:一类是基于体素模型的空洞填补方法, 另一类是直接基于网格模型的空洞填补方法。基于体素模型的方法首先将原始的网格模型表面进行离散体素化, 然后根据一定的方法计算空洞附近的体素, 将空洞封闭, 再对已经封闭的模型进行内部体素填充, 从而形成原模型的一个完整的没有缺失的体素模型, 最后利用面重建算法对体素模型进行重建, 重新恢复成网格模型, 因为体素化过程中已经进行了空洞填补, 所以最后形成的网格模型是一个封闭的无空洞的模型。基于体素模型的方法有多种实现方法, James Davis等人通过在体素中定义一个表示网格模型表面的符号距离函数, 使用一种扩散的过程使符号距离函数的零水平集封闭网格模型表面的空洞, 从而定义出无空洞网格模型[1]。Tao Ju[2]和Joshua Podolak等人[3]利用BSP树对网格模型进行划分, 直到一定的粒度, 再通过对BSP树探测网格模型的空洞边缘, 对空洞进行填补, 然后再利用BSP树进行面重建, 重构网格模型, 形成封闭模型。基于体素模型的空洞填补方法可以处理很复杂的模型, 但是一般比较耗费时间, 同时, 基于体素模型的方法可能改变原网格模型的拓扑形状, 并且可能引入其它拓扑异常。此外还有一些方法根据面模型提取其点云, 全局移动最小二乘法进行面重构[8], 但是这种方法比较适合于精度较高的面模型。

基于网格模型的空洞填补方法一般直接探测出网格模型的空洞的边缘, 然后针对空洞的边缘进行填补, 通过封闭空洞的边缘产生封闭模型[11,12]。对于一些简单的空洞边缘, 直接对边缘进行三角化即可以完成空洞的填补, 但是很多模型都具有复杂边缘的空洞, 一般的三角化方法, 如德劳内三角化, 割耳法[6]都可能产生拓扑异常的填补面, 这时需要更复杂的方法。Paul Louis等人提出了一种基于边缘的渐进三角化的方法[4], 但是这种方法难以处理一些复杂边缘, 可能引入异常拓扑的片元。Chun-Yen Chen等人使用一种基于径向基函数的插值方法来产生一个足够平滑的隐式曲面来近似填补空洞[5]。Alan Brunton等人利用最小能量先将空洞边缘展开到一个平面上, 然后在平面上利用德劳内三角化方法填补空洞边缘, 再将三角化后的平面重新覆盖回空洞边缘[7], 但是该方法对于一些特殊情况的空洞边缘不能完全地展开到一个平面上。

2 基于三角网格模型的空洞填补

2.1 提取空洞边缘

三角网格模型由一个空间顶点集和连接这些点的三角形边的边集构成, 这些三角形互相邻接构成曲面。在三角网格模型中, 如果两个三角形共用一条边, 那么这两个三角形称为邻接三角形。在网格模型中, 一条边通常被两个三角形所使用, 如图1所示, 如果一条边只被一个三角形使用, 那么这条边称为边界边, 它可能构成一个空洞的边界。如图2所示, 所有共用一个顶点的边统称为环边;环边上的顶点 (除了共用的那个顶点) 统称为环点;所有共用同一个顶点的三角形统称为环三角形。

从图1中可以看出, 网格的空洞是由一系列的边界边构成的, 这些边界边互相首尾相连, 最后形成一个三维空间中的边环。这些边界边上的顶点称为边界顶点。所以提取空洞边缘, 我们只需要检测出空洞边界上的边界点, 再根据提取的边界点探测出边界边的信息即可。根据以上的定义, 边界点可以很容易地提取出来, 如图2所示, 因为对于一个顶点, 如果其处于一个封闭的曲面上, 那么其环点个数与环三角形的个数必定相同, 所以环点的数量不等于环三角形的数量的点必定为边界顶点。从而可以从三角网格模型的点集和边集中提取出空洞边缘的边界顶点和边。

2.2 剔除空洞边界异常点和边

在构建一个三角网格模型时, 可能由于本身数据的缺陷, 也可能由于面重建算法的本身的缺陷, 使三角网格模型产生孤立点 (没有被任何边使用的顶点) 、孤立边 (没有被任何三角形使用过的边) 或未形成环的边。如图3所示, 在提取空洞边缘的时候, 这些孤立点、孤立边和未形成环的边都会被当作是边界点和边界边被提取, 形成不规则的异常的空洞边缘。

由图1可以看出, 空洞的边界边都是首尾相连形成一个边界环, 所以对于提取出的边界, 检测其中的每个顶点, 如果该点最多只被一条边使用, 那么删除该点及与该点相连的边 (如果有) , 如此重复, 直到所有顶点都被至少一条以上的边所使用。设V={v1, v2, …, vn}为边界顶点集, E={e1, e2, …, en}为边界边集。主要算法流程如下:

Step1检测V中顶点, 获取一个最多只被一条边使用的顶点vi;若无满足条件的顶点, 退出算法;

Step2若使用顶点vi的边为ei, 从V中删除顶点vi, 从E中删除边ej;

Step3返回step 1。

以上算法流程剔除独立的顶点以及未封闭的边和顶点, 保留首尾相接的完整的空洞边界。

2.3 剔除空洞边界异常点和边

如图4所示, 对于一个三角网格模型, 可能拥有多个不同的空洞, 并且这些空洞可能存在复杂的相连情况, 可能两个或多个空洞的边界在一个或者多个顶点互相连接, 也可能被一条或多条边界边所连接。我们需要从多个空洞边界集中单独提取出每个空洞边界顶点及边界边, 针对每个空洞进行填补。

单独提取空洞边界的算法需要在已剔除异常值的空洞边界顶点集和边集基础上, 根据边的相邻接情况分离出单个空洞边界。如图4, 可能当前的空洞边界中还存在连接两个空洞边界的点或边, 所以还需要在单独提取空洞边界的过程中剔除这些多余的边, 从中单独提取每个空洞边界。其主要算法流程如下:

Step1从空洞顶点集V中挑选一个至少被两条边使用的顶点vi, 将顶点vi放入顶点探测历史记录集H中, 如果无满足条件的顶点, 退出算法;

Step2从使用vi的任一条未被标记的边开始, 依次从相连的边探测每个顶点, 标记探测过的边, 并把探测过的顶点放入顶点探测历史记录集H中;

Step3如果当前探测点vk在顶点探测历史记录集H={vj…vj-1, vj…vs}中出现过, 即vk=vj, 则顶点集vj…vs依次连接形成一个空洞的边界, 将该边界单独保存在独立空洞边界集R中;

Step4在边集E中删除顶点vj…vs间被标记的边, 在顶点探测历史记录集H中删除顶点vj…vs。如果顶点vj在边集E中仍被有未标记的边所使用, 将vj作为当前探测点vi, 否则以vj-1作为当前探测点vi, 返回Step2。如果记录集H为空, 返回Step1。

以上算法将空洞边界以顶点的形式提取在集R中, 提取每一个顶点集中的点都顺次相接, 形成一个封闭的空洞边界。

2.4 独立提取空洞边缘

对于单个空洞的填补相当于对三维多边形的进行三角化。Barequet和Sharir首次描述了一个三维多边形的三角化通用算法[8], 该算法通过最小化加权函数构造三维多边形的三角网格, 从而填补空洞。在这里, 我们采用一种改进的加权函数来实现三维多边形的三角化。

假设构成空洞边缘的三维多边形为P={v0, v1, …vn-1, vn=v0}, Φ (i, j, k) 为在三角化过程中产生的任意三角形vivjvk的权重大小, Wi, j (0≤i

Step1 for i=0, 1, …, n-2, 使Wi, j+1:=0;for i=0, 1, …, n-3, 使Wi, i+2:=Φ (i, i+1, i+2) 。使j:=2;

Step2使j:=j+2, for i=0, 1, …, n-j-1, 使k:=i+j, Wi, k:=mini

使Oi, k等于获得的最小权重的下标值m;

Step3 if j

Step4使S:=Ф, 并且调用如下递归函数Trace (0, n-1) 三角化三维多边形。

最后集合S中包含了三角化三维多边形的三角面片。在以上算法中, Barequet和Sharir将权重函数Φ (i, j, k) 设为三角形vi, vj, vk的面积[7], 但是该方法可能生成一些狭小细长的三角形, 所以在Barequet和Sharir的基础上, 我们再计算三角形的最大最小内角作为权重的其中一个衡量标准, 所以我们把Φ (i, j, k) 定义为:Φ (i, j, k) = (α, A) 。其中α为三角形 (vi, vj, vk) 的最大最小内角, A为三角形 (vi, vj, vk) 的面积。而Φ (i, j, k) 的比较顺序如下:

(α1, A1) < (α2, A2)  (α1>α2) ∨ (α1=α2∧A1

使用这个权重函数, 以上三维多边形的三角化算法可以产生最大化最小内角的三角形。

3 实验结果

VTK[9] (Visualization Toolkit) 是一个开源的用于三维计算机图形学、图像处理和可视化的软件库, 为验证算法的有效性, 我们基于VS2010和VTK 5.8.0为实验平台, 在CPU主频为2GHz, 内存为2GB的电脑上, 对从一系列的腹部扫描CT图片面重建产生的有空洞的腹部脏器模型进行空洞填补, 图5给出了空洞填补整个过程的示例, 图5 (a) 为原空洞面模型, 图5 (b) 为从原空洞面模型中提取的边界边, 图5 (c) 为剔除了异常值, 并且分别提取的空洞边缘, 图5 (d) 为最后对空洞进行填补的效果。表1给出了各阶段处理所需的时间。图6给出了用vtk完成的空洞填补算法vtk Fill Holes Filter的填补效果, 该算法使用德劳内三角化的方法填补空洞。

可以看出, 本文的算法能够处理一些具有复杂结构, 异常值, 复杂空洞边缘的面型。并且能够填补出较为平滑的空洞面。较之其他类型的空洞填补算法, 本算法能够处理复杂的空洞边缘, 并且对于一些孤立点、孤立边及未封闭边等异常值有更强的抗干扰性, 具有更强的鲁棒性, 能够识别出全部的空洞, 如图6所示, vtk中的空洞填补算法不能识别一些较大的空洞。对于meshlab及3DMax等3D建模和编辑软件, 对以上一些模型或者不能识别一些较大的空洞, 或者因为一些异常值的存在而对模型空洞填补产生异常错误 (程序崩溃或产生的填补面自相交) , 图7给出了对另外一个具有更大空洞的面模型的空洞填补效果。

4 结语

具有空洞的三角网格模型无论从三维建模角度还是从审美角度看, 都不具备完整性。但是, 受目前三维建模数据的采集设备以及面重建算法的限制, 产生具有空洞的三维网格模型在某些情况下难以避免, 这将对三维网格模型的某些后续处理产生重大影响。本文提出一种鲁棒性很强的方法, 根据三角网格模型空洞的一些固有性质提取并分离出每个空洞边缘, 针对空洞的边缘进行空洞填补, 使网格模型恢复封闭性, 形成一个完整的模型。因为使用了计算三角形最大最小内角和三角形面积的策略来进行边缘三角化, 所以在实际应用过程中可能需要稍微长一点的时间进行空洞填补, 所以本算法很适合于填补较小空洞或者是具有较少空洞的模型填补。同时该方法能够处理具有任意空间复杂程度的模型, 具有很好的适应性。

摘要：为解决三角网格模型的空洞填补问题, 提出一种识别、提取、分离空洞边缘的方法流程, 并且利用一种改进的三维多边形三角化算法进行空洞填补。首先, 根据网格模型空洞边缘的固有性质, 对网格模型的边界边进行提取;然后, 对提取的边界边集合进行包括孤立点、非封闭边等异常值的消除;再利用空洞边缘封闭的性质单独分离每个空洞边缘;最后, 利用一种改进的三维多边形三角化算法对每个分离出来的空洞边缘进行填补。与通常的空洞填补算法相比, 所提出的方法具有更好的鲁棒性, 能够处理更复杂更大的空洞边缘和三角网格模型, 并且能够最大限度地保持原型, 同时对空洞有较平滑的填补效果, 在恢复医学三维模型以及数字三维扫描模型的完整性中有很好的应用。

关键词：三角网格模型,空洞填补,三角化

参考文献

[1]IEEE.First International Symposium on 3D Data Processing, Visualization, and Transmission, Padua Italy, June 19-21, 2002[C].Conference Publications, 2002.

[2]Tao Ju.Robust Repair of Polygonal Models[J].ACM Transactions on Graphics (TOG) -Proceedings of ACM SIGGRAPH, 2004, 23:888-895.

[3]ACM Siggraph.Symposium on Geometry Processing, Vienna Austria, July 4-6, 2005[C].Conference Publications, 2005.

[4]Paul Louis George, Eric Seveno.The Advancing-Front Mesh Generation Method Revisited[J].International Journal for Numerical Methods in Engineering, 1994, 37:3605-3619.

[5]ISG.Eurographics, Dublin Ireland, August 29-September 2, 2005[C].Conference Publications, 2005.

[6]David Eberly.Triangulation by Ear Clipping[EB/OL].http://www.geom etrictools.com/Documentation/TriangulationByEarClipping.pdf.

[7]Alan Brunton, Stefanie Wuhrer, Chang Shu, et al.Filling Holes in Triangular Meshes by Curve Unfolding[C].Shape Modeling International, Beijing, 2009.

[8]Lavanya Sita Tekumalla, Elaine Cohen.A Hole-Filling Algorithm for Triangular Meshes[EB/OL].http://citeseerx.ist.psu.edu/viewdoc/download d?doi=10.1.1.142.3960&rep=rep1&type=pdf.

[9]Kitware.VTK User’s Guide[M].USA:Kitware, 2010.

[10]ISG.A Practical Gudie to Polygon Mesh Repairing Eurographics, Cagliari Italy, May 13-18, 2012[C].Conference Publications, 2012.

[11]IEEE.IEEE International Conference on Shape Modeling and Application (SMI) , Beijing China, June 26-28, 2009[C].IEEE, 2009.

三角网格模型篇3

关键词：神经网络,逆向工程,孔洞修补

逆向工程 (Reverse Engineering) 是利用实物模型测得的数据构造CAD模型, 继而进行分析制造。在逆向工程中, 三角网格模型是一种非常通用的数据模型。利用测量设备可获得实体的点云数据, 然后对点云数据进行三角网格化处理就可得到三角网格模型。由于测量设备及模型特征等的限制, 生成的点云数据常因信息量不足而产生孔洞, 从而造成三角网格重建后的模型出现孔洞。孔洞的出现, 使建模的质量受到严重影响, 不利于对模型进行有限元分析、快速原型制造等后续处理。因此, 孔洞修补在逆向工程建模中是一个重要的数据处理步骤。

一些学者利用BP神经网络实现了孔洞的修补, 但BP神经网络的构建复杂, 参数确定工作量大, 且网络训练结果不稳定。径向基函数 (RBF) 神经网络是近几年来应用较多的一种神经网络模型。RBF网络构建简单, 训练时间短, 网络结构和参数调整方便, 具有较好的局部逼近能力, 且网络训练结果稳定。本文将RBF神经网络应用于三角网格模型孔洞修补工作, 取得了较好的效果。

1 径向基函数 (RBF) 神经网络

RBF神经网络在分类、学习速度、函数逼近能力等方面均优于BP神经网络。Hornik[1]证明了单隐层的RBF网络可以逼近任意的非线性函数。

1.1 神经网络结构

RBF网络是由输入层、隐层和输出层组成的三层前向神经网络。隐层节点由高斯核函数构成, 输入层到隐层的变化是非线性的, 而隐层到输出层则是简单的线性关系。假设N、M、L分别是网络的输入节点数、隐层节点数以及输出节点数。隐层常用的函数形式是高斯核函数。

其中X= (x1, x2, ···, xM) T

X——输入矢量

Ri——第i个隐层节点的输出

Ci——隐层第i个高斯单元的中心矢量

σi——第i个中心矢量的半径

RBF神经网络的输出可表示为:

其中Wj——隐层到输出层的权值

1.2 神经网络的学习

RBF神经网络的学习算法主要分两步:首先, 根据输入样本确定高斯核函数的中心Ci和半径σi, 可采用K-均值聚类算法;其次, 求出隐层和输出层之间的权值Wj, 可采用递推最小二乘法 (RLS) 计算。

2 利用RBF神经网络实现三角网格曲面的孔洞修补

本文采用的孔洞修补算法主要分为三步:首先, 检测出三角网格模型的孔洞, 并采集孔洞周围的三角片顶点, 用采集到的三角片顶点作为学习样本训练RBF神经网络;接着, 对孔洞多边形进行平面填充, 获得新增三角片的顶点;最后, 用已训练好的RBF神经网络使其优化, 将平面填充后三角片顶点向三维空间映射, 实现三角网格孔洞的修补。

2.1 三角网格孔洞检测

对于封闭结构的三角网格模型, 可利用拓扑关系搜索到孔洞的边界[2]:先找到一条仅属于一个三角片的边, 则该边即为构成孔洞多边形界边, 称之为边界边。以这条边界边作为种子边来寻找其相邻的边界边, 搜索完整的三角网格模型, 最终找到由边界边首尾相连组成的封闭空间多边形, 则该多边形为模型的一个孔洞。

2.2 特征面的填充

特征面的填充实际上是一个投影多边形平面三角化的过程。本文采用如下算法[3]: (1) 用孔洞边界顶点构造一最小二乘平面, 并以孔洞多边形的重心为原点, 在最小二乘平面上任取两个相互垂直的单位向量与该平面的法矢量建立一局部坐标系。 (2) 构造新的三角片。每次寻找投影多边形夹角最小的一对邻边, 构造新的三角片;更新孔洞多边形, 直至新增三角片覆盖整个孔洞。 (3) 将新增三角片的顶点由局部坐标系下的坐标变换到全局坐标系下。

2.3 训练样本的采集

采集需要修补的孔洞多边形的顶点, 以及其相邻几层 (一般为三层) 的三角片的顶点作为学习样本训练RBF神经网络, 使其能表示孔洞周围曲面的函数形式。本文采用的方法如下:step1.定义K为孔洞多边形顶点组成的集合, 在K中任取一三角片的顶点, 寻找与其相邻的三角片顶点;step2.将不在集合K中的顶点放入另一集合中, 当搜索完K中顶点后, N便为孔洞多边形向外扩展的第一层三角片的顶点;step3.重复step1和step2, 直至向外采集达到所设定的层数为止。

2.4 利用RBF神经网络实现孔洞的修补

在三维空间中, 曲面可用函数关系式z=f (x, y) 表示, 训练好的RBF网络能精确映射样本函数z=f (x, y) 。用采集到的孔洞多边形顶点及相邻三角片顶点的x、y分量作为网络输入, z分量作为目标输出, 训练网络, 使其能映射孔洞曲面函数z=f (x, y) 。特征面的填充实现了对孔洞多边形的平面三角网格化过程, 而孔洞修补的主要原理是通过建立空间孔洞多边形的特征面来完成孔洞多边形的填充。在允许的误差范围内, 将新增三角片顶点坐标的x、y分量输入到已训练好的RBF网络, 则可认为RBF网络的输出就是新增三角片顶点的z分量。这样, 就可获得孔洞区域内全局坐标系下新增三角片顶点的坐标, 实现将平面填充后三角片顶点向三维映射的目的, 从而完成了三角网格孔洞的修补。

3 应用实例

为了验证算法的有效性, 用本文的算法对一具有真实孔洞的鸭子模型三角网格曲面, 如图1所示, 进行了修补, 修补后其效果图如图2所示。

4 结论

本文提出一种利用RBF神经网络实现三角网格孔洞的修补算法。利用孔洞边界周围的三角片顶点作为训练样本训练RBF神经网络, 然后用已训练好的网络将平面填充获得的新增三角片顶点映射到三维空间, 最终实现孔洞的修补。

参考文献

[1]Horni K.Approximation capabilities of multiplayerfeed-forward network[J].Networks, 1991, 4 (2) :251-257.

[2]王宏涛, 张丽艳, 李忠文, 等.基于RBF神经网络的三角网格曲面孔洞修补[J].中国机械工程, 2005, 16 (12) :2072-2075.

渐次插入三角网格化方法篇4

1 Delaunay三角网

有很多方法可进行三角剖分, 但是国际上公认俄国科学家Delaunay提出的算法最好, 它尽可能避免了病态三角形的出现。

Delaunay三角网定义:有公共边的Voronoi多边形称为相邻Voronoi多边形, 连接所有相邻的Voronoi多边形的生长中心所形成的三角网称为Delaunay三角网。

Delaunay三角网的基本性质:

(1) 最大最小角性质:在由点集V中所能形成的三角网中, Delaunay三角网中三角形的最小角度是最大的。

(2) 外接圆性质:在点集所形成的三角网中, 其每个三角形的外接圆均不包含点集中的其他任意点。

2 生成方法

根据实现过程, 将Delaunay三角剖分分成三类:分而治之算法、三角网增长算法和逐点插入算法。

逐点插入算法的思路是将未处理的点加入到己经存在的狄洛尼三角网中, 然后判断点所在的三角形, 如果点在三角形内, 连接点与三角形的各顶点, 基于离散点的不规则三角网的生成算法研究Delaunay三角剖分准则, 找出影响区域, 删除影响区域中的边, 对影响区域利用Delaunay三角剖分准则重新构网, 直到区域中所有的点都加入到三角网中。

该算法的基本步骤如下:

Step 1首先定义一个包含所有数据点的初始多边形, 即包含所有数据点的凸闭包。

Step 2在凸闭包中构建初始狄洛尼三角网。

Step 3从内部数据点中取出一点加入到三角网中。

Step 4搜寻包含该点的三角形, 将该点与此三角形的3个顶点相连, 形成3个三角形。

Step5利用Delaunay三角网的剖分准则, 找出影响区域, 从里到外更新所有生成的三角形。

Step 6重复步骤step3, step4, step5直到处理完点集中所有点。

该算法的时间复杂度在一般情况下为O (N3/2) , 最坏情况下达到O (N2) , 同样该算法的时间效率低, 优点是算法思路较简单, 占用内存空间较小, 空间性能较好。

确定边界多边形, 即凸包建立方法:

首先, 检索点集中的所有点, 从中找出xy坐标最大和最小的点, 并且按照y最小, x最小, y最大, x最大的顺序存入凸包数组;然后, 依次从数组中选出两个点, 按照逆时针方向在其右侧 (也就是点集的外部) 找到离此直线最远的点, 并把它插入这两点中间。按照这种方法不断增加凸包数组, 直到无点可加。

凸包建立后, 先在包含所有数据点的一个多边形中建立初始三角网, 然后将余下的点逐一插入, 用LOP算法确保其成为Delaunay三角网。本算法的基本步骤如图1所示。

(1) 定义一个包含所有数据点的初始多边形。

(2) 在初始多边形中建立初始三角网, 然后迭代以下步骤, 直至所有数据点被处理。

(3) 插入一个数据点P, 在三角网中找出包含P点的三角形, 把P点与三角形的3个顶点相连, 生成新的三角形。

(4) 用LOP算法优化三角网。

Lawson提出的局部优化过程 (Local Optimization Procedure) 算法是为了生成Delaunay三角网。从理论上说, 不论用何种方法生成三角网, 只要用LOP算法进行处理, 就能使它变成Delaunay三角网。算法的基本含义为:对由2个公共边组成的四边形进行判断, 如果其中一个三角形的外接圆包含第4个顶点, 则将这个四边形的对角线交换。如图2所示。

判断四点是否共圆, 一种可行的方法是先求出三角形外接圆心坐标, 下面给出一个求给定三角形外接圆的算法:

设三角形的3个顶点分别为: (x1, y1) ; (x2, y2) ; (x3, y3) ;r为外接圆半径, 则有:

经变换则有:

3 编程要点

3.1 数据结构

数据结构采用以下形式:

边结构的定义:

3.2 关键方法

LOP算法的编程实现:

3.3 运行效果

现有一组数据点如表1所示, 经本程序三角网络化生成的Delaunay网络图如图3所示。

目测检验也是一种重要的检验方法, 可以看出本算法在处理复杂点分布方面性能较好, 基本可以满足一般性的三角剖分需要。

4 结语

三角网格模型篇5

上述网格点被称作上三角网格, 记作SU.

2 基于上三角网格的Pad’e-type rational插值

2.1 插值函数的构造

设已知x0<x1<…<xn, f (j) (xi) =fi (j) , (j=0, 1, …, si-1;i=0, 1, …, n) , 为了构造满足插值条件的复合重心有理插值公式, 我们首先介绍一下文献[12]中的一元Pade型逼近方法:

设极点已知的被插函数Ai (yj) 为区间[x0, xN]内充分光滑的已知函数, 插值节点分别为x0, x1, …, xN, 并设式,

最后建立优化模型, 求权。

2.2 满足插值条件

定理2若所有权wi (i=0, 1, …, n) 均不为零, 则满足插值条件:

证明反复利用牛顿插值公式可知

由定理可得:

3 数值实例

(1) 基于上三角网格的二元重心有理插值法

(2) 基于上三角网格的Pad?e–type rational混合插值法:

(3) 文献[2]中的Thiele-Barycentric法

(4) 文献[2]中的Newton-Barycentric法

比较与被插值函数的误差, 结果见表1。

由表1可见, 本文方法的逼近效果优于文献[5]中的方法。

比较易见, 新方法的有效性。

4 总结

本文在插值点的上三角网格上基于重心有理插值与Pad’e-type插值来构造新的二元有理插值, 所得二元混合有理插值继承了重心有理插值的计算量小、数值稳定性好、没有极点以及可以避免不可达点等优点, 同时给出了误差分析。给出的数值实例表明了新方法的有效性。

摘要：与Thiele型连分式相比, 重心有理插值具有很多优点, 像小的计算量、数值稳定性好、无极点、无不可达点、有任意高的逼近阶等。本文基于Pade型重心有理插值构造了基于上三角网格的二元重心有理插值与Pade型混合有理插值。数值实例表明新方法的有效性。

关键词：重心有理插值,Pade型,二元混合有理函数,偏差商,误差

参考文献

[1]Jieqing Tan, Shuo Tang.Composite schemes for multivariate blending rational interpolation[J].J.Com.AppI.Math, 2002, 144 (1-2) :263-275.

[2]YuXiaolei, Construction of new bivariate blending rational interpolation over the triangular grids[J].2010.

[3]Zhao Q J, Tan J Q.Block based Newton-like blending rational interpolation[J].Journal of Computational Mathematics, 2006, 24 (4) :515-526.

[4]Siemaszko W, Thiele-type branch continued fractions for two variate functions[J].J.Comput.Appl.Math., 1983, 9:137-153.

[5]TanJ, Bivariateblendingrationalinterpolants[J].Approx.Theory&Its Appl.15 (2) (1999) :74-83.

[6]Tan J, Fang Y, Newton-Thiele’s rational interpolants[J].Numerical Algorithms.24 (2000) :141-157.

[7]Schneider C, Werner W.Some new aspects of rational interpolation[J].Math.Comp.47 (1986) , no.175:285-299.

[8]Berrut J.-P, Trefethen, L.N.Barycentric Lagrange interpolation[J].SIAM Rev.46 (2004) :501-517.

三角网格模型篇6

关键词：三角网格表面,圆弧样条刀轨,最小二乘,拟合精度修正,数控加工

0 引言

数控刀轨规划常用的方法有等参数法、等平面法、等残留高度法等。等参数法适用于参数表面, 方法简便, 但不太适合组合表面加工, 对于组合表面加工, 通常将参数表面转换为三角网格表面[1,2,3,4]。另一方面, 在逆向工程中, 测量点数据通常不经过表面拟合, 而直接重建成三角网格表面, 用于原型设计或数控加工[2,3]。三角网格模型的STL格式文件在CAD/CAM系统和快速成形系统中得到了广泛的应用。等平面法、等残留高度法适用于参数表面和三角网格表面刀轨规划, 基于刀位点规划的等平面法生成的刀轨为平面内折线[4], 等残留高度法生成的刀轨通常为空间折线[5], 这些方法生成的刀轨的光顺性较差, 数控程序量大, 切削效率不高。因此, 在进行数控加工 (特别是高速加工) 之前, 需要对刀位点进行光顺处理, 或者采用圆弧、NURBS曲线对刀位点进行拟合处理。杨旭静等[6]研究了自由曲线轮廓的圆弧样条刀轨生成方法, 但需要已知轮廓曲线的NURBS表示形式;田立检[7]采用最小二乘圆来拟合非圆齿轮节线, 但圆弧段之间只保持G0连续;Yeung等[8]采用双圆弧曲线来拟合凸轮轮廓, 但拟合得到的圆弧段数不一定最少;赵吉宾等[9]采用NURBS曲线来拟合STL切片数据, 但当拟合的数据点位于或近似位于直线或圆弧上时, NURBS曲线拟合并不适宜, 此外, 还需要数控系统支持NURBS插补。

本文提出了三角网格表面数控加工圆弧样条刀轨生成算法。

1 圆弧样条刀轨生成基本流程

三角网格表面圆弧样条刀轨生成基本流程如下:

(1) 模型光顺处理。由扫描点重建的三角网格模型通常不能直接用于数控加工, 需要对模型进行光顺处理, 常用的方法有Laplacian法、曲率均匀法、最小能量法、微平面法等[10]。

(2) 模型等距。采用基于顶点法矢的等距方法对网格模型进行等距处理, 基于顶点法矢的等距方法计算简便, 且自交处理量少[3,4]。

(3) 直线刀轨刀位点计算。用一系列截平面和等距面求交, 得到直线刀轨的刀位点。采用单调链法[3]去除自交刀轨后得到新的刀位点, 根据残留高度确定刀轨行距。

(4) 基于最小二乘法的刀位点分段拟合。对直线刀轨刀位点处的拟合精度进行修正, 采用最小二乘法进行分段拟合, 去除冗余的刀位点, 得到直线-圆弧刀轨。

(5) 直线-圆弧刀轨尖角及行间过渡。对直线-圆弧刀轨的尖角进行圆弧过渡, 得到圆弧样条刀轨, 在刀轨行之间用直线或圆弧过渡。

2 无干涉直线刀轨刀位点计算

如图1所示, Vi为网格模型中的顶点, Ni为顶点单位法矢。设NV1 (i) 为顶点Vi一环邻域顶点集合, NT1 (i) 为其一环邻域三角片集合, 三角片数量为n;Aij为NT1 (i) 中第j个三角片Tij的面积, Nij为三角片单位法矢;αij为法矢Ni和Nij的夹角;Voi为顶点Vi等距后的点;ωij为法矢Nij的面积权重, dn为三角片法向等距距离 (对于球头刀即为刀具半径) , 则有

记三角片Tij的3个顶点到其等距后的三角片的距离和法向等距距离差值的绝对值为εt (t=1, 2, 3) , 则等距精度为所有三角片εt值的平均值。刀轨行距的计算方法如下:设截平面平行于XOZ平面, 1条无自交刀轨上的刀位点为Pi (xi, zi) (i=1, 2, …, n) , 设刀轨边PiPi+1所在的三角片为Tij, 在下一条刀轨中, 与刀轨边PiPi+1相邻的刀轨边设为P′iP′i+1, 当刀轨行距较小时, 刀轨边PiPi+1和P′iP′i+1位于同一三角片上, 设θi为三角片Tij与刀轨间隔方向 (Y轴正向) 的夹角, 则当前刀轨行距为

$l = \min (2 \cos θ_{i} \sqrt{2 r h - h^{2}})$ (2)

式中, r为球头刀半径;h为残留高度。

3 基于最小二乘法的圆弧样条刀轨生成

3.1 刀位点分类

将刀位点Pi (xi, zi) 分为3种类型, 如图2所示。第Ⅰ类为相邻刀位点距离为0或小于拟合精度δ的刀位点;第Ⅱ类为位于直线上或在拟合精度δ范围内近似位于直线上的刀位点;第Ⅲ类为位于圆弧上或在拟合精度δ范围内近似位于圆弧上的刀位点。在生成圆弧样条刀轨过程中, 在去除第Ⅰ类刀位点中多余刀位点的基础上, 用直线段和圆弧段代替第Ⅱ类和第Ⅲ类刀位点, 从而去除第Ⅱ、Ⅲ类刀位点中多余的刀位点。

3.2 基于最小二乘圆的刀位点分段拟合

设Pi (xi, zi) (i=1, 2, …, n) 不包含第Ⅰ类刀位点中多余的刀位点, 在拟合精度δ范围内能够拟合为K段圆弧, 设为Cj (j=1, 2, …, K) , 对应的圆弧半径为rj, 圆心为Oj (xCj, zCj) , Ps, Ps+1, …, Ps+m-1为拟合圆弧对应的刀位点, 数量为m, s为起始拟合点序号, 如图3所示。设d (j) k (k=1, 2, …, m) 为第j段圆弧的圆心到对应刀位点的距离, 为方便计算, 以 ( (d (j) k) 2-r $_{j}^{2}$ ) 2代替 (d (j) k-rj) 2, 则目标函数为

$E_{j} = \sum_{i = s}^{s + m - 1} [(x_{i} - x_{C j})^{2} + (z_{i} - z_{C j})^{2} - r_{j}^{2}]$ (3)

令a=-2xCj, b=-2zCj, c=x $_{C j}^{2}$ +z $_{C j}^{2}$ -r $_{j}^{2}$ , 要使式 (3) 取最小值, 对其求导数并令导数为0, 解所得方程组 $(\sum_{i = s}^{s + m - 1}$ 记为∑) , 得

由式 (4) 可计算出圆心坐标为 (-a/2, -b/2) , 半径为 $\sqrt{a^{2} + b^{2} - 4 c} / 2$ 。

拟合圆弧和对应刀位点之间的偏差 (简称拟合偏差) 应满足精度控制条件:

$e_{j} = \max | \sqrt{(x_{i} - x_{C j})^{2} + (z_{i} - z_{C j})^{2}} - r_{j} | \leq δ (5)$

用参与拟合的起始刀位点和最小二乘圆的圆心的连线来与最小二乘圆求交点, 得到一段圆弧的起点和终点, 记为Psj、Pej。在得到一段拟合圆弧之后, 去除第Ⅱ类刀位点中多余的刀位点, 基本步骤如下:

(1) 设Ps+m-1, Ps+m, …, Ps+m+k-2为k个第Ⅱ类刀位点, k=2;

(2) 构造以直线Ps+m-1Ps+m+k-2为对称轴、以|Ps+m-1Ps+m+k-2|为长、以2δ为宽的矩形R $_{k}^{(j)}$ ;

(3) 在刀位点Ps+m-1, Ps+m, …, Ps+m+k-2中, 采用夹角之和检验法[11]判断刀位点和矩形R (j) k的位置关系, 若刀位点均位于矩形R (j) k内, 则k←k+1, 转 (2) , 直至存在一个刀位点位于矩形R (j) k外。

此时, Ps+m+k-2为下一段拟合圆弧的起始点。在相邻两段圆弧之间, 以直线段代替, 整条刀轨由直线段和圆弧段组成, 称为直线-圆弧刀轨。

3.3 刀位点拟合精度修正

由于拟合的圆弧段不完全过刀位点, 只控制拟合偏差不一定能保证直线刀轨和圆弧段之间的偏差在精度范围内。如图4所示, 设圆心到线段PsPs+1, …, Ps+m-2Ps+m-1的距离为h (j) k (k=1, 2, …, m-1) , 则对应的弦高为d (j) k, 称为刀轨偏差。

分析直线刀轨和圆弧段之间的位置关系可知:当直线刀轨在圆弧段的“外侧” (图4a) , 即h (j) k>rj时, 如果拟合偏差e (j) k、e (j) k+1在精度范围δ内, 则不需要控制刀轨偏差d (j) k;当直线刀轨在圆弧段的“内侧” (图4b) , 即h (j) k≤rj时, 拟合偏差e (j) k、e (j) k+1在精度范围内不一定能保证刀轨偏差d (j) k在精度范围内 (图4b中只给出了直线刀轨和圆弧段分离的情况, 若直线刀轨和圆弧段相交, 同样不一定能保证刀轨偏差d (j) k在精度范围内) 。因此, 有刀轨偏差控制条件:

d (j) k=rj-hj (k) ≤δ (6)

由图4b可得

e (j) k=rj-h (j) k/sin α (j) k (7)

将求满足刀轨偏差控制条件的拟合偏差的过程称为偏差映射。因此, 由式 (6) 、式 (7) , 将刀轨偏差映射到刀位点拟合偏差后, 刀位点处允许的拟合精度修正为

式中, α (j) k为向量Ps+kPs+k+1和向量Ps+kOj的夹角。

因此, 精度控制条件修正为

e (j) k≤δ (j) k (9)

采用式 (9) 对拟合精度进行修正后, 在不同的刀位点处拟合的精度是不同的, 保证了拟合的圆弧段在精度范围内。在完成一段圆弧拟合后, 计算e (j) k, 若该段圆弧拟合的刀位点中存在e (j) k>δ (j) k的点, 则以δ (j) k为拟合精度, 重新进行圆弧拟合, 直至满足e (j) k≤δ (j) k为止。因为过3点必能拟合一段圆弧, 此时有e (j) k=0, d (j) k=δ, 因此, 至少存在3点, 使得拟合的圆弧满足修正后的精度控制条件。

3.4 直线-圆弧刀轨尖角过渡

采用上述算法得到的直线-圆弧刀轨之间存在着尖角, 应对尖角进行圆弧过渡处理, 以保证整条刀轨G1连续, 过渡后得到的刀轨称为圆弧样条刀轨。首先确定过渡圆弧半径。在图5a中, 设圆弧段为Cj, 直线段为PejPsj+1。PejPtj为过圆弧Cj终点Pej的切线。设γj为向量PejPtj与向量PejPsj+1之间的夹角, 则有

$r_{t j} = c_{0} \frac{δ s i n (γ_{j} / 2)}{1 - s i n (γ_{j} / 2)}$ (10)

式中, c0为过渡半径调节系数, 取c0∈[0, 1]。

在图5b中, 设直线PejPsj+1 方程为ajx+bjz+cj=0, 过渡圆弧为Ctj圆心为 Otj (xtj, ztj) , 半径为rtj。将圆弧段所在的圆向外 (内) 等距rtj, 直线段所在的直线向上 (下) 等距rtj, 等距后的圆和直线的交点为过渡圆弧的圆心, 其位置最多可有8种情况[11]。经几何关系推导, 可得

计算各过渡圆弧Ctj的切点坐标, 若切点在圆弧段Cj和直线段PejPsj+1上, 则对应的圆心坐标即为所求。

4 实例验证

以玩具轿车 (简称轿车) 模型为实例验证本文算法。轿车模型的STL数据由CAM软件转换得到, 毗邻误差为0.05mm, 其中顶点数量为5603, 三角片数量为9795, 毛坯尺寸为210mm×110mm×70mm, 刀具半径为8mm, 拟合精度为0.05mm, 加工允差为0.10mm, 残留高度为0.01mm。

图6a所示为采用文中方法生成的精加工圆弧样条刀轨;图6b为直线-圆弧刀轨的尖角过渡处理, 为表示清晰, 未作裁剪处理。图7所示为刀轨行之间采用双向圆弧过渡, 以适应高速加工。

下面对直线刀轨 (变行距) 、双圆弧刀轨[8]和文中圆弧样条刀轨的加工精度和切削效率进行对比分析。采用VERICUT软件对轿车模型进行仿真加工, 加工参数为:主轴转速2000r/min, 进给速度1000mm/min。图8所示为采用文中圆弧样条刀轨进行仿真加工的结果。相关的数据见表1、表2。

加工误差由加工结果和原模型进行比较来确定。轿车模型的原模型指由CAM软件转换前的模型。这里的加工误差包括模型误差、等距误差和拟合偏差等原理误差。模型误差指网格模型及其原模型之间的误差, 即毗邻误差。本例中, 轿车的模型误差为0.05mm。

表1所示为轿车模型的等距精度及拟合精度是否修正时的拟合偏差和刀轨偏差比较, 为保证加工后表面和原模型之间的精度, 拟合精度取δ的一半, 即0.025mm。表1中数据表明:①等距精度加上拟合精度后小于加工允差, 能够满足加工精度要求, 本例中, 等距精度小于加工允差的15%;②拟合精度修正前, 拟合的圆弧刀轨中存在刀轨偏差大于拟合精度的情况;③拟合精度修正后, 刀位点处的拟合偏差和刀轨偏差均小于允许的拟合精度。

表2所示为直线刀轨、双圆弧刀轨[8]和本文的圆弧样条刀轨仿真加工的加工误差 (最大值) 、刀轨段数量和所需时间的比较, 双圆弧刀轨和圆弧样条刀轨采用相同的拟合精度。表2中数据表明:①在不增加新刀位点的条件下, 圆弧样条刀轨的加工精度高于直线刀轨、双圆弧刀轨的加工精度;②圆弧样条刀轨的段数 (直线段和圆弧段) 小于直线刀轨、双圆弧刀轨的段数, 所需的加工时间小于直线刀轨、双圆弧刀轨的加工时间。

5 结论

针对三角网格表面, 在得到无干涉直线刀轨刀位点的基础上, 采用分段拟合的最小二乘法, 在拟合的过程中去除多余的刀位点, 把刀轨偏差映射为刀位点拟合偏差, 对刀位点拟合精度进行了修正, 对直线-圆弧刀轨进行过渡处理后得到的圆弧样条刀轨, 拟合精度高, 刀轨段数量少, 刀轨的光顺性好。根据文中方法规划的刀轨在数控加工时具有较高的加工精度和切削效率。

参考文献

[1]周济, 周艳红.数控加工技术[M].北京:国防工业出版社, 2002.

[2]Sun Yuwen, Guo Dongming, Jia Zhenyuan, et al.Iso-parametric Tool Path Generation from TriangularMeshes for Free-form Surface Machining[J].Int.J.Adv.Manuf.Technol., 2006, 28 (7) :721-726.

[3]Jun C S, Ki m D S, Park S.A New Curve-basedApproach to Polyhedral Machining[J].Computer-aided Design, 2002, 34 (5) :379-389.

[4]Park S C.Sculptured Surface Machining Using Tri-angular Mesh Slicing[J].Computer-aided Design, 2004, 36 (3) :279-288.

[5]Feng H Y, Li Hui wen.Constant Scallop-heightTool Path Generation for Three-axis SculptureMachining[J].Computer-aided Design, 2002, 34 (9) :647-654.

[6]杨旭静, 钟志华, 陈泽忠.自由曲线轮廓加工的圆弧样条刀具路径研究[J].中国机械工程, 2006, 17 (12) :1277-1282.

[7]田立检.非圆齿轮节线曲线设计的新方法[J].机械工程学报, 1997, 33 (6) :95-102.

[8]Yeung M K, Walton D J.Curve Fitting with ArcSplines for NC Toolpath Generation[J].Computer-aided Design, 1994, 26 (11) :845-849.

[9]赵吉宾, 刘伟军, 王越超.基于NURBS曲线的STL模型截面轮廓平滑处理技术研究[J].小型微型计算机系统, 2005, 26 (3) :496-499.

[10]熊歆斌, 王亚平.逆向工程中数控加工刀具轨迹生成的简化方法研究[J].工程图学学报, 2006, 27 (1) :35-39.

网格资源模型综述篇7

随着互联网技术的快速发展和广泛应用,对广域分布的资源之间的共享和协同需求不断增加,网格技术已成为近年来分布式技术领域的一个研究热点。网格具有资源分布广、资源间的连接需要通过广域网连接、资源类型和数量巨大,而且要求协同工作等特点。因此,需要对网格计算中的资源建立模型,主要的研究内容包括对网格环境中的计算资源进行有效地描述、组织和管理,使用户可以高效地为计算任务寻找合适的资源。

在资源描述方面,资源描述框架RDF(Resource Description Framework)[1]是W3C推荐的用于描述网络资源元数据的模型。凡是被RDF描述的事物都叫资源,一个RDF文件包含多个资源描述,每个资源描述是由资源、属性值、属性构成的三元组语句构成。RDF具有通用性、智能准确性和独立性等特点,它的通用性使得数据的共享能提供更大的价值。RSL(Resource Specification Language)[2]是Globus用于描述资源的通用的可交换的语言,它提供了一个框架性的语法描述,可用来组成复杂的资源描述。RSL语法的核心是关系,关系由属性名和它的值组成,它提供了在资源请求中可执行元素的名字。在RSL可描述更复杂的资源,而且它的语法提供便利引入并且废除了字符串变量。WSDL(Web Service Description Language)[3]是Web Service发展过程中提出的服务描述语言,并由W3C做了标准化,并且用XML文档来描述。WSDL可以描述复杂的资源,具有良好的可扩展性,技术比较成熟,并且已经是一个工业标准,但在互操作性、可用性、安全性等方面有待完善。

2资源模型和资源发现机制

资源模型的重点是要建立一种不依赖集中控制的、分布式、可扩展、能适应资源动态变化并且定位性能好的资源发现机制,本章主要介绍当前主要的一些资源发现机制。

2.1基于资源路由的发现机制

织女星网格操作系统是中国国家网格系统软件核心部分,作为国内大型网格系统,非常具有典型性。从技术水平上讲,在网格软件体系结构、编程环境、安全、数据管理、资源定位与路由方面具有自己的特色,并已经在中国国家网格中完成安装和部署,成功运行了多个网格应用。

织女星网格采用的是基于资源路由的发现机制[4,5],它用于资源表示的EVP模型包括三个层次:有效资源层(E)、虚拟资源层(V)和物理资源层(P)。资源的最终使用发生在物理层,虚拟层主要解决全局一体的问题,有效层主要解决好用性的问题。有效资源空间采用单用户多资源的模式,虚拟资源空间支持多用户多资源,资源空间支持多用户单资源。由于EVP模型是具有一般性的抽象模型,在应用时需将其具体化。

在用户层中,考虑“通用服务”的原则,网格中部署的资源以及使用这些资源的应用程序在资源的表示方式上可能不尽相同,在用户层部署一个统一的命名空间是难以实现的,因此资源发现机制允许不同的应用使用不同的资源请求表示方式,但这也使得给出一个用户层资源表示的一般视图变得很困难。同时有必要将用户层资源表示与路由器层表示分离,将资源表示转换为一种全局一致的表示方式,用于路由器层。在实际应用中,用户层资源往往是由某种规范来描述的,如RDF和WSDL。如果理解规范的含义,就可以在用户层本地完成对请求描述的转换,并保证转换的结果在传到设备端时仍然是有效的。在织女星网格中,要支持某一特定资源表示方式的虚拟设备提供者,应实现针对该方式的用户层表示到路由器层表示转换的解析器。此解析器,作为该虚拟设备驱动程序的一部分,部署在网格客户端设备。解析器将用户层的资源描述转换成了该类资源状态空间的一个点或子空间,同时避开了远程解析可能造成的瓶颈,有助于提高资源定位的效率。

在路由器层,资源按其提供服务的类型别分类,每类资源都有属于本分类的表示格式。路由器层提供了一个简单的模板规范,利用该规范提供的语法,每类资源可以定义各自的模板,每一个资源在路由器层的信息都是自己所在分类的模板的一个实例。

在物理层上,资源的表示应包含物理访问的位置信息,使用Internet中现有的资源定位方式,如URL和IP地址加端口号的形式可以很好的满足这一需求。提供相同服务的资源,尽管其内部可能是异构的,但都应以统一的服务接口封装,并且以一致的格式向资源路由器报告状态信息。所有的资源提供者和用户都通过连接到某个路由器来加入织女星网格,而通过路由器之间的互联,也可以实现网格的动态扩展,所有的路由器在逻辑上是平等的。为适应网格中结点、资源自主控制和动态变化的特点,资源路由器在运行时,需要有动态改变拓扑的能力。为此,资源路由器上运行了一个包含注册、定时更新、超时探测、注销及相应的应答报文的协议。

2.2超拓扑空间模型

网格资源的超拓扑空间模型(Resource Model Based on Hyper Topology Space,RMHTS)是从超拓扑空间角度审视网格资源模型的内在机理与结构[6],研究如何描述资源、抽象资源以及提供单一系统映像,利用其所提供的聚类方法能够自动实现各种异构资源的统一描述和访问,同时允许资源自由地加入或退出网格环境。

从整体上看, 它是一个超拓扑空间,RMHTS资源模型分为三层,,即:特征信息层、特征处理层和功能层。各层有着不同的组织形式与拓扑结构, 并且进一步可细分为若干亚层。各层功能如下:

(1)特征信息层

含有网格资源的全部信息,这些信息用超结点予以表示,一个结点只表示独立使用的单个资源的相应信息。因此该层实际上是一个信息空间,然而这里的信息不是普通的信息,而是一种特征信息。信息空间能够根据网格的实际情况来构建,包括资源的特征信息和资源间的相互连接。然而,该空间是无序的,没有统一映像,难于使用。因此有必要提出一种特殊有序化的空间形式——超拓扑空间来改变这种随机的空间结构。

(2)特征处理层

特征信息元素的集族——信息空间形成了一个原始的拓扑结构,而在该原始拓扑结构基础上建立起来的第二层拓扑结构,是以信息空间上的所有子集做成的集族而形成的拓扑结构,这就是特征处理层。超拓扑空间使信息空间的内在结构发生质变后的高级组织形式,脱离了原信息空间中各个信息元素或子空间之间毫不相关、互相独立存在的那种初级随机组合形式,而使得整个信息空间内部的元素组成一个统一的有机整体,并使得这个整体内部在高级层次上产生出新的重要性质。在一个信息空间中,如果用超拓扑结构中的某种关系来分解这个空间的话,依据这种关系可以将整个空间划分成若干相关等价关系,而由某个拓扑等价关系所确定的等价类集合所对应的那个空间族,叫做由这个等价关系所定义而产生的商空间。在不同的拓扑等价关系映射下可以产生不同的商空间结构。生成商空间后,会产生新的高阶的空间结构,这种结构会将原来系统中隐藏的特性显露出来。利用这种拓扑相关等价关系,将信息空间进行分解,然后重新组合和排序,就会产生一种新的有序化的拓扑结构形式:按等价类排序后的商空间的拓扑结构形式。这种重新有序化的聚合过程,乘坐信息空间的聚类反应。其规律是:同类自动相聚。

(3)功能层

该层位于模型三层结构的顶层,是各种应用的用户接口,如同网格服务。应用的所有资源需求都可以在这里得到满足。并且这一层提供了统一的服务,屏蔽了资源之间的异构特性。应用执行时,用户不必再考虑资源选择的琐碎细节。一般而言,功能层的最终服务将被聚合为三种:Human(人力)、information(信息)、artificial object(人工事物),从而实现了顶层资源的统一划分。

2.3网格和P2P混合模型

网格和P2P(Peer to Peer)是当前分布式领域的两个研究热点,它们有共同的目标:共享和协同分布在网络中的硬件和软件资源。现阶段的网格系统实现还是以C/S结构为主,资源发现主要是基于集中或分层模型进行,存在单点故障问题,扩展性不强。网格与P2P混合模型可以很好的解决单点故障、资源搜索等问题,同时增强网格的可扩展性[7]。

如图1所示,模型分为网格层和P2P层两层。下层的P2P资源被视为一种虚拟的网格资源,网格服务可以作为下层P2P资源的一个包装器或者作为普通网格服务进入下层P2P网络的一个入口,这样可利用P2P层的资源在网格层映射一个网格服务。总的来说,网格层负责提供服务,并且是调度者和管理者,而P2P层主要作为一个资源池并且在底层提供资源的发现和聚集。

由于OGSA/OGSI和GT3已经成熟,在模型中采用GT3作为网格服务架构平台。对于P2P层,选择使用JXTA开发平台。JXTA是一个具有一组支持P2P应用程序标准的框架,致力于提供一个基本的P2P架构。这个框架包含一套协议,这些协议与语言、平台、网络都是无关的。

网格层主要以网格服务的形式存在,为用户应用程提供访问接口,网格节点之间通过SOAP(Simple Object Access Protocol)协议通信。P2P层主要有结点控制器和网格服务包装器两个模块。结点控制器将一个网格结点映射成P2P层的一个结点,并且这个结点能够和P2P结点共同组建P2P网络,在P2P层映射的所有网格结点使用P2P通信技术。网格服务包装器将P2P的PC资源通过包装虚拟化为一个网格服务,用户可以通过这个虚拟的网格服务接口直接使用P2P资源,这样普通的PC就可以在没有安装网格中间件软件包的情况下为上层提供网格资源,解决了当前情况下普通PC不能安装复杂的网格中间件问题。

混合模型的一种实现方式是在每个自治资源域中运行着一个匹配引擎,各个匹配引擎连接形成P2P覆盖网络,每个节点或用户都通过所在域的匹配引擎来发现整个网格环境中的资源[8],模型框架如图2所示。匹配引擎是运行在自治管理域中某个超级节点上的一种服务,负责本域内以及跨域间的资源发现任务。对于用户发来的每个资源请求,匹配引擎会先从本域内搜索,如果找不到合适的资源,则会将请求转发到最佳邻居匹配引擎上,继续这个搜索过程。通过将匹配引擎组织成P2P网络,分散了资源发现请求,不再需要昂贵的高性能服务器,具有P2P搜索技术所带来的可扩展性、健壮性、负载均衡等优点,提高网格资源发现服务对资源变化和网络结构变化的适应能力,适用于大规模动态自治的网格环境。

2.4基于网格距离的资源模型

Ma等还提出了基于网格距离的资源模型[9],该模型将网格资源分成2类:系统资源和网络资源,网络资源是用来传输数据,除此以外的所有资源统称为系统资源,系统资源为任务实现具体的功能。

系统资源从属于一个节点,一个节点可以向网格提供多个资源。资源可以用系统资源所属节点作为顶点,网络资源作为边的无向图表示其状态。同样,应用可以用其所包含的若干任务作为顶点,两个任务之间的通信需求作为边的无向图表示其状态。在这个模型下,资源的调度就体现为一个从任务图到资源图的映射函数。

基于网格距离的优化算法即是在任务k的候选系统资源集合中选择与任务所在节点间网格距离函数值最小的那一个。实验证明,在资源调度中,网格距离达到了选择距离较近、费用较低的资源,有利于提高整个网格资源调度的性能,在任务的完成上也表现出较好的特性,能够达到调度优化的目的。

3结束语

网格环境中的资源模型与资源发现机制,是一个具有重要理论研究价值和广泛的实际应用背景的课题。它涉及到资源的查找的调度,好的资源模型能够对用户屏蔽资源的位置等物理信息,并且具有较好的定位性能和可扩展性,能够适应网格资源自主控制、动态变化的特点,可以较方便地解决请求转发的负载平衡问题,使得互联网中的管理者、运营者和使用者都能够获益。

参考文献

[1]Resource Description Framework.http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/.

[2]The Globus Resource Specification Language RSL v1.0.http://www.globus.org/toolkit/docs/2.4/gram/rsl-spec1.html.

[3]W3C.Web Service Description Language(WSDL)1.1.http://www.w3.org/TR/wsdl.

[4]李伟,徐志伟.一种网格资源空间模型及其应用.计算机研究与发展.2003,40(12):1756-1762

[5]董方鹏,龚奕利,李伟,查礼.网格环境中资源发现机制的研究.计算机研究与发展.2003,40(12):1749-1755

[6]鲁斌.网格资源的超拓扑空间模型.计算机工程与应用.2006(29):133-135,150

[7]左东石,孙龙清.网格与P2P计算混合模型研究.微计算机信息,2006,22(12-3):126-128

[8]刘扬,何华灿.基于匹配引擎覆盖网络的网格资源发现模型.计算机工程,2008,24(2):154-156,180

【三角网格模型】推荐阅读：

网格模型07-09

3D网格模型09-01