李明，张湘玉，马希青

(河北工程大学机电工程学院，河北邯郸056038)

现有骨架提取方法主要有拓扑细化法、距离变换法、Voronoi图和Reeb图法，以及手工提取方法等［1－8］。这些方法大多应用于模型骨骼关节动画中的整体骨架提取，有的可以实现骨架的自动提取但算法比较复杂;有的通过交互方式得到骨架，算法简单但交互过程过于繁琐，甚至得到的骨架不够精确。另外，现实中在对一些模型进行运动模拟或变形设计时，往往并不需要对模型进行整体骨架提取，而只需要针对其局部区域进行变形，如:只考虑动物四肢的运动，只进行椅子扶手的设计，只修改水壶壶嘴的形状等等。因此，本文提出一种三维网格模型局部区域骨架交互式提取方法，并应用于自行开发的骨架驱动变形软件中，实现了模型局部骨架的精确提取。

1 局部骨架的提取流程

当三维网格模型整体或局部具有近似圆柱体的形状时，可认为其是广义圆柱体。此时骨架曲线可认为是广义圆柱体的轴线［9］。本文利用截交线求骨架点的方法就是基于上述观点。首先对三维网格模型是广义圆柱体的局部区域作几何截面，得到几何截面与模型的截交线，然后求取截交线的几何中心得到骨架点，最后顺次连接各骨架点即得到局部骨架。图1是局部骨架提取流程图。

2 局部骨架的交互式提取方法

骨架提取算法需要对模型上局部区域的边界点进行拾取，然后通过拾取不在一直线上的三点确定出初始截平面。因此，网格顶点的拾取是成功实现局部骨架提取的基础。

2.1 基于OpenGL的网格顶点拾取

为了利用OpenGL拾取网格顶点，须先对各个顶点使用不同的ID进行命名，定义鼠标所在位置的拾取矩阵，然后在选择模式下对网格进行虚拟绘图。在具体操作中，由于可能会拾取到鼠标点附近的多个顶点，故需要对选中的顶点进行深度处理，以保证顶点的准确拾取。

选择模式下，顶点拾取绘图函数为

对空间三维网格顶点定义了相应的类，点类定义如下:

至此，由于每个网格顶点ID的赋予规则与相应存储在vector中的索引号相一致，故一旦选中某个顶点，就可以根据其ID得到其在vector中的位置，继而得到该顶点的相关信息。

拾取顶点的结构体定义如下:

在拾取过程中，有时会出现同时选中多个顶点的情况，如封闭网格和S形网格等。此时应对所有拾取到的顶点进行深度分析，并从中找出深度值最小的顶点ID，此顶点即为选中对象，它与观察者的距离最小。

2.2 确定模型的局部区域

确定模型的局部区域其实就是对三维网格模型的顶点和三角面片信息进行采集。即:先划定局部区域边界，然后在边界内用种子生长算法确定局部区域［10－11］。具体实现步骤如下:

在拟提取区域边界位置处，按一定方向拾取若干个网格顶点。

利用Dijkstra算法，求解网格上相邻两拾取顶点的最短路径，并按顺序首尾相连各最短路径折线段，即得局部区域的边界曲线。同时将边界曲线上的网格顶点存入边界点集K0。

在骨架提取区域内拾取一网格顶点作为种子点，并将该点分别存入点集K和K1;同时将种子顶点所在三角面片不重复保存到三角面片集合J中。

对点集K中各顶点进行1－环邻域(顶点1－环邻域是指该顶点及与其相邻接的边和面所构成的局部网格)搜索，将搜索到的且不属于点集K0和K1的顶点保存到点集K1和清空后的点集K中;这时需要判断点集K中各顶点所在三角面片是否已存在三角面片集合J中。若没有，不重复保存到三角面片集合J中。

判断点集K是否为空集。若是，结束算法;否则，重复执行上一步骤。

由此得到的点集K1和三角面片集合J即为所需要的骨架提取区域的网格信息。

2.3 截平面的生成

三维网格模型局部区域截平面生成的好坏直接影响获得骨架点位置准确性。故下面两类截平面的生成至关重要。

初始截平面。在骨架提取区域两端位置处的网格表面拾取三个不共线的网格顶点，据此确定出初始截平面。图2给出了在圆桌腿部区域确定的两个初始截平面。

等分截平面。在骨架提取区域两端初始截平面中间进行插值，得到若干等分截平面。其实现的步骤如下:

首先对两端初始截平面S0和S1的法向量n0和n1进行叉乘，得到旋转轴。然后由空间向量夹角公式得到旋转角度α。

根据要插入的等分截平面个数，这里不妨设为m－1个，对旋转角度α进行m等分。

求解S0和S1两初始截平面中心点(求解过程详见第2.4和2.5)，将其连接线段m等分，分别得到m－1个等分顶点Ci(i=1，2，…，m－1)。

由初始截平面S0的法向量n0分别绕旋转轴旋转角度值 α·i/m(i=1，2，…，m －1)，得到各等分截面的法向量 qi(i=1，2，…，m －1)。

根据各等分顶点Ci(等分截面上的点)和等分截面的法向量qi，可求得各等分点处截平面。

图3给出了等分截平面生成示意图。

2.4 截交线的求解

求解截交线其实就是求解几何截面与三维网格模型局部区域三角面片交点的有序集合。本文求解截交线分为两步:(1)确定与几何截面相交的三角面片。(2)确定几何截面与相交三角面片的交点。

确定相交三角面片。几何截面与三角面片的相交情况分为五种，如图4所示。

空间截平面方程为

将三维网格模型三角面片的A、B、C三个顶点坐标分别代入方程(1)，顶点相对几何截面的空间位置不同，F的值也各不相同。表1中给出了几何截面与三角面片相交的五种情况下，对应三角面片三个顶点的不同F值。据此就可以提取出局部区域内所有与几何截面相交的三角面片。

表1 不同相交情况下三角面片顶点F值Tab.1 Triangular patches of different vertex Fvalues intersect case

求解交点。得到所有与截平面相交的三角面片后，还需要求解截平面与所有这些三角面片的交点，将这些交点按一定顺序连接即得到截交线。在确定相交三角面片环节得到的初始相交三角面片集合中包含了图4中的1、2、3、4四种情况，欲求解交点，需要首先对初始相交三角面片集合进行相应处理，然后结合搜索、求交算法得到交点。

对初始相交三角面片集合进行预处理。针对图4中第1种情况的两个共边相交三角面片，集合中只保留其中一个三角面片，对另一个进行删除;对于第2种情况的相交三角面片全部进行删除，这样处理后得到相交三角面片集合V。

从相交三角面片集合V中，任意指定某一三角面片S作为起始搜索三角面片S0，定义已搜索三角面片集合VS初始为空。

搜索与S相邻(含有共同顶点，非VS集合内)的三角面片T。

记录S与T两个相邻三角面片共同顶点的个数p，判断S与T相同顶点是否位于截平面上或相交线段是否与截平面相交，若是，执行下一步骤;否则，转上一步骤。

若p=1，则S与T相交共同顶点即所求截交线上的点;若p=2，则S与T相交线段与截平面的交点即为所求，将求得交点保存至交点集合U内。

保存S至已搜索三角形集合VS内，更新搜索三角形S=T，判断S与起始搜索三角形S0是否为同一三角形，若是，算法结束，否则转第3步骤。

图5中给出了几何截面与相邻三角面片相交的七种情况。通过以上算法，就可以得到截平面与所有相交三角面片的交点集合U，顺序连接U中各点即可生成截交线。图6所示给出了圆桌腿部网格模型表面初始截交线及放大图。

2.5 生成骨架线

三维模型的骨架是模型的中心曲线，曲线上每个点是模型相应几何截面的中心。本文首先根据网格模型与初始及等分截平面求交获得若干截交线，然后分别计算这些截交线上顶点的几何中心，即得到若干骨架点，将这些骨架点按顺序连接生成局部骨架线。

3 骨架提取实例

分别选取单峰骆驼腿部、圆桌腿部和茶壶的壶嘴作为模型局部骨架提取区域。模型局部骨架提取效果，如图7、图8、图9所示。

从上述模型的局部骨架提取效果图，可以看出本文基于截交线的骨架提取算法可以实现对三维网格模型局部骨架的精确提取。

4 结论

1)与传统手工提取骨架相比，该方法通过人机交互生成初始截平面，自动插值获得中间等分截平面，交互更为方便、快捷。

2)根据截平面与模型相交线确定骨架点，可以实现对三维模型局部骨架的精确提取，所提取骨架位于模型的中心位置。

3)该方法算法简单，易于控制。

4)该方法也存在一些不足之处，比如:当三维网格模型局部区域顶点分布很不均匀时，所提取到的骨架与预期骨架之间存在一定差距。

［1］曾荣军.基于聚类分析的三维网格骨架提取［D］.中南大学，2011.

［2］刘俊涛，刘文予，吴彩华，等.一种提取物体线形骨架的新方法［J］.自动化学报，2008，34(6):617 －622.

［3］刘小凤，吴艳兰，胡海.面状要素的多层次骨架线提取［J］.测绘学报，2013，42(4):588 －594.

［4］CEM DIREKOGLU，ROZENN DAHYOT ，MICHAEL MANZKE.On using anisotropic diffusion for skeleton extraction［J］ .International Journal of Computer Vision，2012，100(2):170 ～189.

［5］林佼，李 重，金小刚，等.基于凸壳与有向包围盒的骨架提取方法［J］.计算机辅助设计与图形学学报，2012，24(6):793 －798.

［6］马锐，伍铁如.基于广义势场的三维形体多层次线骨架构建［J］.计算机应用，2011，31(1):16－19.

［7］黄香，程筱胜，戴宁，等.基于骨架驱动的牙齿形态设计［J］.东南大学学报:医学版，2012，31(1):18－23.

［8］CAO J，TAGLIASACCHI A，OLSON M，et al.Point cloud skeletons via laplacian based contraction［C］.Shape Modeling International Conference(SMI)，2010.IEEE，2010:187－197.

［9］王海强，毛天露，王兆其，等.运动状态下虚拟人全身皮肤实时变形方法［J］.计算机辅助设计与图形学学报，2005，17(12):2722 －2728.

［10］张湘玉.基于细分的曲线曲面变形技术研究［D］.南京:南京航空航天大学，2011.

［11］郭来德，刘辉林，刘兰哲，等.农业信息搜索引擎设计与实现［J］.河北工程大学学报:自然科学版，2007，24(3):41－43.