计算机应用 ›› 2011, Vol. 31 ›› Issue (01): 16-19.

• 第八届中国计算机图形学大会优秀论文 • 上一篇    下一篇

基于广义势场的三维形体多层次线骨架构建

马锐,伍铁如   

  1. 吉林大学数学学院
  • 收稿日期:2010-07-09 修回日期:2010-09-01 发布日期:2011-01-12 出版日期:2011-01-01
  • 通讯作者: 马锐
  • 基金资助:
    基于图形处理器的高性能计算;基于图形处理器的高性能计算

Computing hierarchical curve-skeletons of 3D objects based on generalized potential field

Rui Ma1,   

  • Received:2010-07-09 Revised:2010-09-01 Online:2011-01-12 Published:2011-01-01
  • Contact: Rui Ma

摘要: 在Cornea建立的基于广义势场的骨架生成算法的基础上,提出一种新的多层次线骨架构建算法。通过选取不同的r值简化边界点,减少了斥力场的计算时间。与Cornea算法不同,选取曲面变分替代曲率,并选取局部曲面变分值较高的边界点作为种子点生成多层次的骨架。由于曲面变分比曲率更适用于反映点云形体表面的性质且计算速度较快,因此该算法更适于处理点云,且具有一定的鲁棒性。同时分析了不同的r值与骨架连通性和计算时间的关系。实验结果表明,经边界点简化处理,斥力场计算时间比原来减少一半左右,且以此生成的骨架能够保持较好的光滑性和连通性。还尝试了另一种基于曲面变分简化边界点的准则,并仔细考查了高曲面变分点、邻域半径k以及不同的空间划分尺度n对多层次骨架生成的影响。

关键词: 线骨架, 势场, 曲面变分, 多层次

Abstract: The curve-skeleton is an abstraction representation of a 3D object in one dimention. It can reflect the essential topology of the object and be widely used in animation, virtual navigation and matching. This paper give a new algorithm to compute hierarchical curve-skeletons based on the algorithm of generalized potential field given by Cornea. The algorithm reduces the force field computing time by using different r to simplify the boundary points. The difference is that it uses surface variation to replace curvature and uses the boundary points with higher local surface variation as seed points to get hierarchical curve-skeletons. Because the surface variation is more applicable to reflect the properties of point-sample surface than curvature and faster to compute, it is more applicable to deal with point cloud and robust. The paper analyses the relationship between different r and the connectivity and the computing time. Experiment results indicate that computing time of the force field by using simplified boundary points reduces about half to the original algorithm, and the result curve-skeletons keep good smoothness and connectivity. The paper also tries another rule to simplify the boundary points based on surface variation and studies carefully the influences of higher surface variation points, neighbourhood size k and different spatial division n to the hierarchical curve-skeletons.

Key words: curve-skeleton, potential field, surface variation, hierarchical