【作者】 周元峰；

【导师】 张彩明；

【作者基本信息】 山东大学 ， 计算机应用技术， 2009， 博士

【摘要】 曲线曲面造型是计算机图形学、计算机辅助几何设计以及计算机动画等领域中非常重要的研究课题之一。随着曲线曲面造型技术的提高,其应用范围也越来越广泛,如计算机辅助设计系统、医学图像三维建模以及逆向工程等。近年来,随着计算机建模技术的发展,隐式曲面造型得到了更为广泛的关注和应用,但因为其形状调整和显示的困难,应用价值得到了一定的限制。目前常用的三维造型方法之一是基于多边形网格模型,网格模型数据可通过高精度激光测量设备获取,存储信息为被测量对象表面的离散点的几何坐标,将测量对象几何形状数字化,但这样所获取的几何模型一般分为若干部分,具有较多的噪声,需要对几何数据进行去噪、点云拼接、数据平滑以及数据精简等处理。隐式曲面具有参数曲面不具备的优势:可以提供更为简洁直观的表达方法;具有很高的连续性;能够容易地表示拓扑复杂的曲面,并且容易改变曲面的拓扑结构:空间点与隐式曲面的相对位置容易判断。因此,隐式曲面可以为三维几何表示提供更为丰富多样的造型方法。如何将难以显示和控制的隐式曲面转为多边形网格表示,进行隐式曲面重建,并对重建的多边形网格进一步处理,得到更为优化的网格模型,是本文主要研究的内容。为了解决隐式曲面调整和显示困难问题,结合多边形网格模型处理技术,本文主要围绕基于隐式曲面交互造型,建立其多边形网格表示并对网格进行处理等问题展开系统性的研究,并针对隐式曲面交互调整、隐式曲面的造型方法、隐式曲面多边形化、三角形网格简化和光顺等问题进行了深入探讨,取得了由隐式曲面到多边形网格处理的一系列研究成果。本文的主要工作分为以下四个方面:(1)针对隐式曲面难以进行交互调整问题,提出了一种新的基于优化的隐式曲面交互调整方法,方法可以达到实时对隐式曲面进行形状调整。首先为隐式曲面的调整设计两种交互工具,交互工具由采样粒子进行定义,分别可以对曲面上顶点的位置调整和法向调整。该方法以调整后的位置和法向为新曲面的插值目标建立目标函数,极小化该目标函数求解曲面参数的变化量,从而确定新的隐式曲面。从优化角度对极小化问题进行研究,分别采用牛顿法和SQP(Sequential Quadratic Programming)方法求解该非线性优化问题。在调整过程中用粒子的方法对隐式曲面进行绘制,实现了对隐式曲面形状进行实时交互调整。(2)对于隐式曲面表示和显示问题,提出了两种新的隐式曲面多边形化方法,两种新方法均基于隐式曲面采样粒子,根据隐式曲面的法向和曲率信息对隐式曲面进行三角化处理,得到与隐式曲面同构的多边形网格表示。方法一:将隐式曲面的多边形化分为两个阶段:首先根据法向约束条件对隐式曲面进行采样,得到稳定的采样粒子表示:然后在每个采样粒子处沿法线正负方向分别在隐式曲面内部和外部延伸一段距离,得到两个曲面法向附加点。将法向附加点和采样顶点进行四面体化,删除法向顶点及其相关联的边,最终得到隐式曲面的三角形网格模型。方法二:基于曲率自适应的壳空间剖分隐式曲面三角形化。首先采用粒子系统对隐式曲面进行采样,通过高斯曲率约束粒子的生成,使生成的网格模型在曲率大的区域具有较多的小三角形,在曲率小的区域具有较少的大三角形,从而使网格模型更好地逼近隐式曲面。新方法在每个采样粒子处沿曲面法线正负方向延伸适当距离得到两个附加点,对所有附加点进行四面体化形成对隐式曲面逼近的壳空间四面体网格,在每个壳空间四面体中抽取三角形,所有抽取的三角形拼合得到隐式曲面的三角网格表示。与以往方法相比,新的三角网格化方法更具有鲁棒性,可一次性获得高质量的三角形网格。(3)针对隐式曲面三角化后得到的网格模型,需要进一步进行简化处理,提出了一种基于体积平方度量的三角形折叠网格简化方法。方法通过极小化误差目标函数简化三角形网格。简化误差定义为三角形简化后产生的网格模型平方体积变化,并以三角形几何形状因子和法向因子作为约束。简化误差的表示形式为一个二次目标函数,因此,每次简化后三角形网格的新顶点是一个线性问题的解。与目前简化效率最好的QEM方法相比,新方法不增加算法复杂度。如果被简化的三角形是强特征三角形,则用其高斯曲率最大的顶点作为新顶点,以保持原始模型的细节特征:对于非强特征三角形,新顶点用极小化折叠误差确定。对于边界三角形,新顶点的位置由不同于内部三角形的方法进行计算,保持了网格的边界特征。(4)提出了一种对任意三角形网格进行光顺的新方法,为去除网格模型噪声点,得到更为优化的网格模型提供了新方法。方法基于网格曲面平均曲率变化均匀的光顺思想,用网格顶点的平均曲率和邻接点平均曲率的加权平均之差定义网格光顺速度,使得网格顶点沿着法向方向进行调整。对于非封闭网格顶点,方法中也提出了一种估计其平均曲率的方法,因此可以将网格的内部顶点和边界顶点统一进行处理。更多还原

【Abstract】 Curves and surfaces modeling is one of most important research fields in computer graphics, computer aided geometric design and computer animation. As curves and surfaces modeling technology developing, its application range becomes wider, such as computer aided design system, medical images three dimensions modeling and reverse engineer, etc. Recent years, as development of computer modeling technology, implicit surfaces are used more and more widely. However, for shape controlling and rendering difficulty, application value of implicit surfaces is limited at certain level.Polygon meshes are usually used as the expression in 3D modeling technology. Data of polygon mesh (the coordinates of the discrete points on 3D objects) can be obtained by the laser fixed measuring equipments. However, original geometric models always have sevel parts of points, and with high noises. Data pre-processing includes point clouds registration, data smoothing and simplification, etc. Implicit surfaces have three obvious advantages: the first is simple expression forms, the second is easy to judge the relative position to a given point, and the third is its high smoothness. Implicit surfaces can change the topology of surfaces easily, so they are very useful for describing continuous and smoothly blend surfaces with complex topology. Based on above problems, we mainly research in implicit surface interactive modeling, and construct polygon mesh expression for implicit surfaces. Furthermore, new mesh processing algorithms such as simplification and fairing for the constructed meshes are also presented. In brief, we made intensive study of implicit surfaces interactive modeling, implicit surfaces polygonization, triangular mesh simplification and triangular mesh fairing, which can be achieved following four main research contributions:(1) Point to control implicit surfaces difficult, we propose a new interactive method for controlling implicit surfaces via optimization. New method can achieve control implicit surfaces in real-time.Two interactive controlling tools are introduced: position controlling handle and normal controlling handle. New implicit surfaces are required to interpolate the adjusted positions and normal vectors at desired vertices on surfaces, which are appointed by user interaction. This problem can be treated as an optimization one. Newton and SQP (Sequential Quadratic Programming) methods are applied to solve it respectively. Particle system is used for real-time rendering of implicit surfaces. This method provides a real-time and interactive method for controlling the shape of implicit surfaces.(2) For implicit surfaces representation and display issues, we proposed two new polygonization methods, which are both based on particle system. Normal and curvature information are used for constructing isomorphic polygonal meshes with implicit surfaces.Method I: Particle system with normal constraint is used for sampling on the given implicit surface to get steady and reasonable sample particles. Two normal added vertices are obtained by extending the particle to an equal distance along the normal vector and the anti-normal vector. Dividing the normal added vertices into tetrahedrons, and then traversing all of the tetrahedrons to find the triangles on implicit surfaces and achieve the final triangular mesh.Method II: Particle system is used for sampling an implicit surface whose fission and death are guided by Gaussian curvature. This strategy leads to curvature adaptive samplings, so there are more small triangles in the high curvature region of constructed mesh. Reconstructed triangular mesh can approximate the implicit surface better. More sample points are obtained by extending a proper distance along each normal vector. These new sample points are used as a sampling on surface of the shell space. Delaunay tetrahedron of these sample points fills in the shell space. Finally, triangles around zero set form a triangulation of the implicit surface. Comparing existing methods, our method is more robust, and can achieve high quality model without post processing.(3) We proposed a new simplification method for triangular mesh obtained by the implicit surfaces based on volume square measure. New method can make as a farther processing for obtained mesh.Triangular meshes can be simplified by minimizing error objective function. Square volume error, shape factor and normal constraint factor of triangles are combined together to define the simplification error, which can be described as a quadratic objective function. New vertices replaced collapced triangles can be determined linearly. Comparing with the QEM method which is the most effective method so far, computation complexity will not be increased. Gaussian curvature factor is computed for each collapced triangle and used to identify strong feature triangle. For non-strong feature triangle, new vertex position is determined by minimizing the error objective function. For strong feature triangle, new vertex is taken the strong feature vertex of the three triangle vertices for preserving the model feature. Each collapced triangle is processing as inner triangle or boundary triangle to keep the boundary feature.(4) A new method for fairing arbitrary triangular mesh is presented. This method can remove noising point on mesh and optimize mesh can be obtained.Mean curvature normal is used to define a quasi-laplacian operator for smoothing inner vertices at a local region. Vertices are moved along the normal direction in a more appropriate velocity which can make mesh smoothing and shape preserving harmonizing well. For the boundary vertices, a new method for estimating the mean curvature normal is presented, so that for an arbitrary triangular mesh, the inner and the boundary vertices can be smoothed by the same smoothing process. Features of the original mesh can be preserved by the weighted mean curvature normal restriction of the neighbors of one vertex effectively.更多还原