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

一种基于凸壳与OBB包围盒的骨架提取方法 林佼1), 李重1), 金小刚2), 李亮1) 1) 数学科学系, 浙江理工大学, 杭州, 浙江, 310018 2) CADCG国家重点实验室, 浙江大学, 杭州, 浙江, 310058 摘 要： 线性骨架作为几何及拓扑信息表示的一种常用形式，在三维模型研究领域中有着广泛应用。本文提出一种基于凸壳与OBB包围盒的线性骨架提取方法:首先将三维网格模型进行分割，生成多个子网格模型；接着对各子网格中的点集求取凸壳，作为该子网格点集的近似，凸壳顶点的形心构成原始骨架点；然后用OBB包围盒进行重叠计算，求出相交点集，用以生成关节骨架点；最后对原始骨架点与关节骨架点进行连接，最终形成完整骨架。实验结果表明，本算法快速、有效，提取出的骨架能保证连通性与中心性，且能很好地提取出关节骨架点，可为蒙皮关节动画、模型形状分析等提供有效信息。 关键词： 骨架；凸壳；有向包围盒；分割 A skeleton extraction algorithm based on convex hull and OBB LIN Jiao1), LI Zhong1), JIN Xiaogang2), LI Liang1) 1) Department of Mathematical Sciences, Zhejiang Sci-Tech University, Hangzhou, 310018 2) State Key Lab of CADCG, Zhejiang University, Hangzhou, 310058 Abstract: Skeleton as a simplification representation of the geometry and topology for a 3D object, is widely used in the field of 3D model research. In 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 hull’s centroid as the original skeleton point. Then we find out the overlapping point set between two adjacent parts by using OBB, determine the centroid of the overlapping point set as the joint point. We finally connect original skeleton points with joint points to get the entire curve-skeleton. Experimental results show that our skeleton extraction method is simple, fast and effective. It guarantees the connectivity and centrality of the skeleton, which can provide useful information for skinning joint animation, 3D model shape analysis, etc. Key words: Skeleton; Convex Hull; Oriented bounding box; Segmentation 0 引言 3D模型的线性骨架提取是计算机图形学及可视化研究中的一个重要研究课题。线性骨架，即一维骨架，是3D物体几何和拓扑信息的一维表示，可应用于三维模型的形状分析中，在计算机动画、对象识别和匹配、模型重建、虚拟导航等领域中也有着重要的应用价值[1,2]。 近年来，已有多种算法应用于网格模型的线性骨架提取，常用方法有：（1）细化算法。通过多次迭代收缩，在不破坏物体连通性的情况下剔除边界点，且确保不剔除端点，最终推进到物体内部形成骨架。(2)基于计算几何和图论的方法。Amenta等人[1]提出了基于Voronoi图及其对偶图Delaunay三角化的中轴提取方法，该方法可