三维数据处理中曲面建模问题研究

【作者】 杨兴强；

【导师】 张彩明；

【作者基本信息】 山东大学 ， 计算机软件与理论， 2005， 博士

【摘要】 现代探测技术的发展,大大加强并普及了人们获得三维空间数据的能力。象三维扫描仪、CT、GPS等设备所获得的空间数据在质量和数量上都有了快速的提高。如何充分利用这些空间数据,从中提取物体的特性和形状等有关信息,并以直观的方式表达出来,满足工业制造、医疗、军事等领域日益增长的需求,是一个难度极大的挑战性问题。尽管三维数据的来源和应用领域各不相同,但它们都是通过高密度的数据描述空间几何形状。如何从这些看似杂乱无章的数据中,找出数据点间的关系,建立高精度的曲面模型,是海量空间数据在所有应用领域中面临的共性科学问题,是本文研究的核心问题。 曲面建模的目标是真实再现客观世界中物体的形状,对绝大多数物体而言,难以用一个整体函数表示其外形,因此分片表示复杂物体形状成为构造曲面模型的通用的手段。面片所采用的数学表达式和相邻面片之间的连续性依赖于所要解决的问题和原数据的形式。相邻面片之间达到C~0连续性是物体曲面建模的基本要求。为达到C~0连续,需要确定物体表面上的顶点以及顶点之间的连接关系,得到曲面的多边形网格表示。对海量数据点拟合的另一种方法是用简化后的数据点构造多边形网格,不是多边形网格顶点的数据点可用来在多边形上构造更光滑的曲面(C~1连续)。例如,将密集的三角网格简化为稀疏的三角网格,多余的数据点用来在简化后的三角形边界上构造边界曲线及跨界导矢或者使三角形上的曲面片具有较高的多项式逼近精度。 C~0和C~1连续的曲面模型在目前可视化和计算机辅助几何设计中具有广泛的应用。本文研究了C~0和C~1连续的曲面模型,提出了由三维海量数据点构造相应C~0和C~1曲面模型的方法,并分别应用于基于CT的三维虚拟人体建模和相关的计算机辅助几何设计建模技术的研究中。这些工作的主要内容体现在如下三个方面: 1.子像素精度的轮廓提取。从CCD、CT、扫描仪和遥感等设备可以获取大量的影像数据,尽管这些设备的分辨率越来越高,但人们总是希望能从所得的影像数据中获得比像素更精细的物体轮廓,本文提出了两种方法获得物体在像素内的边界。更多还原

【Abstract】 With the development of the modern detecting technology, people have more and more abilities to obtain 3D data. How to make use of the 3D data, extract the information of number and shape, and display them in an intuitionistic way, so as to satisfy the increasingly need of medical treatment, manufacture industry, is a challenge. Although 3D data can be obtained with various ways, they all describe the shape of objects. It is the common problem to find the relations among 3D data points and create surface models. This is also the kernel problem of this paper.The surface model is used to reconstruct the shape of an object, and it is impossible to express the object’s shape with one mathematic function, so surface patches become the general tool for complex shapes. The mathematic expressions used by patches and the continuum among surface patches depend on the type of 3D data and application. C~0 continuum is a basic condition for the surface model. To achieve C~0 continuum, we must determine the positions of vertexes on the object surface and topology relations among them, and obtain the polygon mesh. In an another way, we can fit the 3D data with a simplified mesh which is consisted of key vertexes, the spare vertexes make surface more smooth. For example, they can be used for computation of values and cross-boundary slopes on the boundary.The surface model with C~0 and C~1 continuum find wide use in visualization and CAGD. This paper studies the surface model with C° and C~1, and presents methods to construct them, which are shown as three aspects below.(1) 3D reconstruction with sub-pixel precision. The resolution of images obtained from CCD,CT, scanner and so on gets higher and higher, but people still hope to obtain finer profile than pixels. Two new methods are presented in this paper. The first method distinguishes the pixels inside, across or outside of the boundary by a threshold, and determines the position of the boundary point according to the values of the three adjacent pixels(inside, across and outside). Based on the boundary points, a new interpolation method is used to obtain the more accurate iso-point, which adopts two interpolating points which are different from those used by the Marching Cubes method. The second method determines boundary points using the geometric method without interpolation. Under the assumption that the object boundary can bethought as straight line in two pixels extent, the geometric method discusses the relation among pixel values, the area occupied by the object in pixels, and boundary, and proves that the object edge can be determined by the values of two adjacent pixels. Theoretical analysis shows that this method can find the accurate boundary points when the boundary is a straight line at two pixels extent. These two methods above can determine the position and direction of boundary with values of adjacent pixels in boundary’ tangent and normal direction respectively.(2) A modified cuberille method with linear precision. A new method is presented for removing the shortages of the Cuberille method which are lower precision and poor image quality. Iso-surface(cube sides) produced by Cuberille method is taken as a framework, and is covered with a polygon grid. The polygon grid is produced by expending the cube sides with a linear interpolation. This expansion improves the precision of the Cuberille method, and makes the polygon grid have linear precision. How to determine the position and normal at each polygon vertex and how to construct the polygon grid are discussed. The normal vectors computed with new method are compared with those produced with Marching cube method, the result shows that the smoothness of the image is obviously improved.(3) C1 continuum polynomial interpolation surface on Triangular meshes. How to construct surface patch on a triangle is all along important problem in CAGD field. The constructed surface patches have not only the same function values but also the same cross-boundary slope on the triangular boundaries. First this paper presents a new method to construct C1 continuum surface. The constructed surface patch can be regarded as comprised of a basic patch and three transition patches. The basic patch is formed by forcing the three subdivision curves to intersect at a common point inside the triangle and they share a common tangent plane at the intersection point. The resultant patch satisfies the given boundary curves and keeps cross-boundary slope continuity. In comparison with Nielson’s side-vertex method, the new surface has the precision of polynomial surfaces of degree 4. In 2004 a new method was presented to obtain the triangular surface patch that interpolates the given boundary curves and cross-boundary slopes by a basic approximation operator plus an additional interpolation operator. This method makes the triangular patch satisfies the giveninterpolation conditions with polynomial approximation precision of degree five. Based on the Zhang’s research, we present a new method to construct the basic approximation operator of degree 6. The polynomial of degree 6 has more free condition, so it can approximate the boundary of triangular meshes. The innovations in this paper are below:(1) Presents the new method for the computation of the boundary vertex, which has more precision then Marching Cubes method.(2) Obtain the position and direction of boundary outline with geometry method. The geometry method can obtain accurate boundary when the boundary is a straight segment in the extent of two pixels.(3) Based on Cuberille method, a new method for reconstruction of the polygon mesh is presented, which approximates the object’s shape better and has satisfied visual effect.(4) Presents a new method for constructing degree 4 interpolating polynomial surface with C1 continuum, degree 4 polynomial precision, depending the triangle’s boundary conditions.(5) Depending the triangle’s boundary conditions, presents a new method for constructing degree 6 interpolating polynomial surface with C1 continuum and 5th polynomial precision, which has more parameter to satisfy the boundary conditions. This degree 6 interpolating polynomial has better effect than degree 5 interpolating polynomial under the same polynomial precision of degree 5.This paper is consisted of 5 chapters: The chapter 1 summarizes the correlative researches;The chapter 2 analyzes the relation between pixel values and object’s edge;The chapter 3 presents sub-pixel method for mesh vertexes;The chapter 4 discusses the reconstruction of polygon mesh;The chapter 5 presents new methods for constructing interpolation surface on triangle mesh;更多还原