一种基于凸壳与OBB包围盒的骨架提取方法.docx

一种基于凸壳与OBB包围盒的骨架提取方法林佼"，李重°,金小刚2),李亮I)1)数学科学系，浙江理工大学，杭州，浙江,3100182) CAD&CG国家重点实验室，浙江大学，杭州，浙江,310058摘要：线性骨架作为几何及拓扑信息表示的一种常用形式，在三维模型研究领域中有着广泛应用本文 提出一种基于凸壳与OBB包围盒的线性骨架提取方法:首先将三维网格模型进行分割，生成多个子网格模 型；接着对各子网格中的点集求取凸壳，作为该子网格点集的近似，凸壳顶点的形心构成原始骨架点；然 后用OBB包围盒进行重脅计算，求出相交点集，用以生成关节骨架点；最后对原始骨架点与关节骨架点进 行连接,最终形成完整骨架实验结果表明，本算法快速、有效，提取出的骨架能保证连通性与中心性， 且能很好地提取出关节骨架点，可为蒙皮关节动画、模型形状分析等提供有效信息关键词：骨架；凸壳；有向包围盒：分割A skeleton extraction algorithm based on convex hull and OBBLIN Jiao0, LIZh()n『)，JIN Xiaogang2), LI Liang01) Department of Mathematical Sciences. Zhejiang Sci-Tech University, Hangzhou, 3100182) State Key Lab of CAD&CG, Zhejiang University, Hangzhou, 310058Abstract: Skeleton as a simplification representation of the geometryr and topology fora 3D object, is widely used in the field of 3D model research・ Tn this paper, we present a skeleton extraction algorithm based on the convex hull and the oriented bounding box (OBB). It firstly divides the mesh into several parts; computes the convex hull of each part，s point set as its approximation, and uses the convex hulfs centroid as the original skeleton point. Tlien we find out the overlapping point set between two adjacent parts by using OBB. detennine the centroid of the overlapping point set as the joint point. We finally connect original skeleton points with joint points lo get the entire curve-skeleton. Experimental results show that our skeleton extraction method is simple, last and effective. It guarantees the connectivity and centrality of the skeleton, which can provide useful intonnation for skinning joint animation, 3D model shape analysis, etc.Key words: Skeleton; Convex Hull; Oriented bounding box; Segmentation0 引言3D模型的线性骨架提取是计算机图形学及口J视化研究中的一个重要研究课题。

线性骨 架，即一维骨架，是3D物体几何和拓扑信息的--维表示，可应用于三维模型的形状分析中， 在计算机动画、对彖识别和匹配、模型重建、虚拟导航等领域中也有着重要的应用价值皿1 近年來，己有多种算法应用于网格模型的线性骨架提取，常用方法有：(1)细化算法通过 多次迭代收缩，在不破坏物体连通性的情况下剔除边界点，II确保不剔除端点，最终推进到 物体内部形成骨架2)基于计算几何和图论的方法Amenta等人⑴提出了基于Voronoi图 及其对偶图Delaunay三角化的中轴提収方法，该方法可以从点云模型提収中轴Leymari[2J基金项目：国家自然科学基金(60903143, 51075421)：浙江省自然科学基金(Y1090141)；浙江省钱江人才D 类项目资助(QJD0902006)«提出的Shock图方法也属于儿何方法中的一种这两类儿何方法都是以中值而或中轴线为基 础，其缺点是对噪声点非常敏感，计算量大3)基于Reeb图的方法近年來该方法収得很 大进展其思想是在网格农面定义一个连续函数，计算每个模型顶点的函数值，将具有相同 函数值的顶点聚合成一个顶点，得到模型的骨架Hilaga等人⑶提出了 MRG算法，其定义 的连续函数为顶点到-整个模型衣面所有顶点的最短距离与面积之积的和。

该方法能有效地描 述三维模型的整体拓扑分支结构，但缺乏表面细节特性的保留；尤其在主体与分支的连接区 域缺乏有效的判断4)基于广义场函数方法如Wu等人⑷的基于可见反力场算法，山于 考虑更大范围的模型边界点的作用，该方法对噪声点不敏感，但计算量大5)交互方法 如Verroust和Lazarus⑸提出一种从多边形网格上抽収骨架曲线的方法：输入一些3D数据 点集,通过用户对源点(骨架曲线的起点)的选収和采样，生成树状曲线集合该算法相对复 杂，且需要大量人工操作本文提出一种基于凸壳与0BB包围盒的快速骨架提収方法首先分割网格生成多个子网 格，然后对各子网格求取凸包,对凸包顶点求取0BB包围盒,用0BB的中心点作为骨架点, 连接生成初始骨架；然后对相邻网格求取0BB相交范围内的点集，用该点集的中心作为关节 点；最后连接骨架点与相应的关节点，从『U形成完整骨架°与现有的骨架捉取方法相比，本 算法简单、可行，并II能够有效地提収出关节骨架点1 本文算法对于给定的三维网格模型，我们通过网格分割、凸包近似、确定初始骨架、生成完整骨 架四个步骤提取英线骨架，如图1所示，具体实施方式如下所述图1.算法主要步骤1.1网格分割对一桀体网格模型，我们采用基于特征的区域生长网格分割算法⑹对网格进行分割。

首 先输入一个整体网格模型，调榮好视角后，用鼠标选収“前娥标注工具”，在屏幕上想耍分剤 岀的区域上划出"前景线”，如图2(“)中头部的蓝色直线；然后选収’'背景标注工具”，在 其他网格区域划出“背景线”，如图2(a)中躯干部位的绿色直线然后计算从视点发出的射 线通过前后“背景线”与网格的交点，定义为C = {CF,Cj,其中C「Cb分别为“前景线” 与“背景线”的投影点集，其中的点分别用'F，与帘'标志山此，网格上所有顶点S分为两类：c与N,其中N二s-C我们使用Isophotic度量⑺距离进行区域增长olsophotic度量公式化离散形式表述为:dv(p,q) = \p-q\ + ⑷知 _僞| + g) ( 1)其中d「(p,q)为P，q两点的Isophotic度量距离；np.為分别为两点的法向量；轨为曲/(^)=匕no你＜0而沿线石 方向的曲率；血、血'为权重，一般设为5； /运算定义如下:(2)下面开始以Cf、Cb为“种子点”进行区域增长:(1) 将N中所有顶点用三元组｛v, m, d｝表示，其中v为顶点,d为顶点v到C中最近顶点V*的Isophotic距离，m为『的标志，初始所有N中顶点的山设定为Undown, d为MAX;(2) 初始化队列Q为空，对于C中每个顶点几，计算几在N中的各邻接顶点的d值，将d 值最小的邻接顶点加入到队列Q中，并将该邻接顶点的m设定为化的标志，若其邻接 顶点均不在N中，则将pc从C中删除；(3) 找到Q中具有最小d值的三元组｛%『 %in' 心｝，将该顶点％in标记为%in，并 加入到C中，且从N中删去该顶点；(4) 如此重复步骤(2) (3),直到N为空结束。

山几何知识可知，物体不同部分交界处点的曲率一般为负的极小值，山公式(1)(2) 可推得，此时Isophotic度量会相当大，故交界处点之间的Isophotic距离会较大，山上述 算法可知，交界处顶点会最后分类.(a) (b) (c)图2人体网格分割山此我们将网格模型所有顶点分为两类，相应边界也就确定了°在边界处，应用基于蛇 （Snake）曲线⑻的最大化能量方法进行边界优化，最终生成所要的分割结果如图2所示, 绿线为背景曲线，蓝色为前景曲线a）中将网格分为头部与身体两个部分；（b）中再上一步 的基础上进 步将四肢划分出來；（c）为最后的分割效果，相邻子网格之间用不同种类的颜 色加以区分1.2凸壳近似凸壳（Convex Hull）,也称最小凸包，是包含点集合S中所有对象的最小凸集凸包的构 造涉及到两个问题，即从点集S中筛选凸壳顶点以及建立各顶点之间的拓扑关系⑼本文采 用改进的增量算法來构建三维凸包，该算法简单易用具体思想如下：遍历点集S,取出x坐标瑕大与最小的两点，与y坐标最大和z坐标报大的点构建一初 始四面体（若有重复，则进行相应调整），这样将尽可能多的点包括在初始四面体内，减少 后续而与棱边的添加与删除操作，简化计算。

然后进行各而顶点的逆吋针排列操作山四而 体四个顶点口可求出该四面体中心点pe二丄工门易知，四面体各面的面法向量与面上4 /•=!一端点到代的向量的点积必为负数假设某一面的顶点初始排列为P\ Pl P3 ' P\P1 X P1P3 与门代的点积若不为负数，则说明三点不是逆吋针排列，将后两点交换位置即可将四面 体每个面的三个顶点都进行逆时针排列后，每次从点集S中取出一-个点，对该点进行“可见 性判断”若该点对于所有面都"不可见”，说明该点位于凸包内，不做处理；若有可见面， 则遍历棱边；若该棱边的两个邻接面均可见，则删除该棱边；若该棱边只有一个可见面，则 用新加入的点与该棱边创建新面，对面上三点作逆时针排列操作，并创建两条新边，最后删 除所有可见面，这样依次加入新点，直至点集s为空图3点〃相对于面的“可见性判断”可见性判断用而法向量与而上一端点到待检测点向量的点积判断，若一点p对一三角 面可见，则该点必位于三角形各顶点的“上方”如图3所示，三角形顶点门、“2、几按 逆时针顺序排列,/?, p2 x p{ p3即为法线向量N, pe与N点乘可判断可见性,若为正, 则说明两向最同向，即”点在该三角形的“上方”，〃点可见，反之亦然。

图4为不同模型的凸壳近彳以和包围盒表示，其中蓝色线条为模型報体的凸壳线框表述，绿色长方体为模型的OBB包用盒线框表述图4不同模型的凸壳近似和包围盒1.3确定初始骨架OBB （定向包围盒）是三维空间中的一个轴向任意的长方体包围盒它的最大特点就是 它的方向具有任意性，可根据物体本身的几何形状来决定盒子的大小和方向，无须与坐标轴 垂直，这样就可以选择最合适的最紧凑的包容盒将三角形顶点集合看作是三变量的概率分布函数，在对OBB包围盒的进行计算时，利用 三角形顶点的均值和协方差矩阵來计算包围盒的中心位置和轴向设三角形集的第Z个三角 形的顶点矢量为门、G和包围盒。