计算线性八叉树边界象素集的新算法
A New Algorithm for Calculating the Set of Boundary Pixels of Linear Octree
-
摘要: 八叉树作为一种新的形体表示方法,在几何造型、物性分析、动态模拟、干涉检测、计算机视觉、机器人等应用领域内有着广泛的应用前景。用其它方法表示的形体,可以转换为八叉树表示进行处理,从而弥补了这些形体表示方法的缺陷。但是,八叉树表示占有存储空间过多,为了解决这一问题,常采用线性八叉树的存储结构1,2,本文在线性八叉树的基础上,提出了一个计算八叉树边界象素集的新算法。该算法采用一种“增减”原则,根据这一原则,对八叉树的边界象素集进行不断的增减操作,最终产生形体的全部边界象素。利用本算法产生的结果,可以大大提高干涉检测、形体间最小距离计算等算法的效率。同时,也可用于医学中CT扫描图像的三维形体重建,以及由八叉树表示转换为边界表示的算法。算法的复杂性为0(nN+M),其中,n为八叉树的精度,N为线性八叉树的长度,M为形体边界象素的数目。Abstract: Using octree structure in solid modeling system to represent objects has many advantages, on the basis of linear octree, a new algorithm for calculating the set of boundary pixels of octree is presented in this paper. The Increase-Decrease manipulation rules are used in X, Y, Z direction to calculate the boundary pixels step by step. This algorithm requires O (nN + M) time, where, n is the number of levels of octree, N is the length of linear octree and M is the number of boundary pixels of the object.
下载: