【作者】 刘丽；

【导师】 张彩明；

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

【摘要】 随着计算机科学的迅速发展和现代制造技术的进步，逆向工程技术受到学术界和工业界越来越多的重视，将继续是CAD／CAM技术领域的一个研究热点。通过逆向工程技术，可以根据实物模型的数字化信息重建实物的CAD模型，使得那些以实物为制造基础的产品在设计和制造过程中，充分利用CAD／CAM等先进制造及管理技术；同时，由于能在很短的时间内复制实物样件，从而可以缩短产品的开发周期，提高生产能力、产品质量和企业的市场竞争力，增加企业的经济效益。逆向工程由数据获取、数据预处理与曲面重建三部分组成。数据获取是通过特定的测量设备和测量方法获取产品表面离散点的几何坐标数据，将产品的几何形状数字化；数据预处理的工作主要包括数据格式的转化、数据点集间的拼接、数据平滑、数据精简和数据分块等，是逆向工程的一项重要的技术环节，它决定了后续CAD模型重建过程能否方便、重建的模型能否满足应用需求；曲面重建的目的是寻找某种数学描述形式，在满足给定精度的条件下、简洁有效地描述一个给定物理曲面的形状，并在此基础上对曲面本身进行分析、计算、修改和绘制。曲面重建是逆向工程中最重要和最困难的问题，虽然其研究已经取得了很大成绩，但是仍然存在着一些有待解决和完善的关键问题和难点问题。例如，对于海量数据点集的曲面重建计算速度较慢；复杂拓扑的数据点集重建质量较差；自动化程度不高，需要大量人机交互等。本文就逆向工程中复杂曲面重建的一些关键技术进行研究，提出了散乱数据点的四边形网格重建、网格细分和网格参数化的新算法，为构造不同形式的重建曲面提供了有用的理论依据，主要贡献包括以下几点：(1)给出了散乱数据点集曲线重建的最短路逼近算法，提高了重建曲线的质量，为旋转面、螺旋面和可展曲面的重建提供了有效方法。散乱数据点集的曲线重建是曲面重建的基础，已有的曲线重建算法很难自动识别多连通和封闭数据点集的拓扑结构。最短路逼近算法首次将图论中最短路径理论引入到曲线重建中，根据散乱数据点的分布构造带权连通图，通过求解带权连通图的最短路径，将散乱数据点集的曲线重建问题转化为有序数据点集的曲线重建问题。散乱数据点的势函数值反映了数据点的相互作用对重建曲线的影响，所以在此基础上建立的最短路径体现了数据点集的形状和走向。此外，该算法通过删除数据点集的Delaunay三角化网格中长度大于采样密度的边，自动识别出数据点集的拓扑结构。因此最短路逼近算法有效地解决了单连通、多连通和封闭的数据点集的曲线重建问题，较好地保持了数据点集的形状和走向，尤其是带尖点的数据点集的形状特征，为旋转面、螺旋面和可展曲面面的重建提供了有效方法和技术。(2)提出了基于多分辨率的四边形网格重建算法，为解决重建网格面片数量过多的问题提供了新方法。散乱数据点的重建网格大多数基于三角形网格，对于规模较大的数据点集，重建网格的面片数目过多，不能满足实时处理的要求。另一方面，对于现有CAD和图形系统，采用四边形网格重建比采用三角形网格重建具有更广泛的应用价值。本文提出的四边形网格重建算法，通过最小包围盒方法对散乱数据点集进行简化，按一定规则连接相邻简化点生成多边形网格。通过对多边形网格细分和优化，得到质量较高的重建四边形网格。四边形网格重建算法通过改变数据点的精简程度，调整重建网格的精度；通过对多边形网格的细分，调整重建网格的密度；通过对四边形网格的优化，提高重建网格的质量。四边形网格重建算法具有计算效率高，可操控性强，减少重建网格数量，提高网格质量等优点，适合海量数据点集的网格重建。(3)提出了四边形网格的三分细分模式，为解决重建网格的曲面细分效率不高的问题提供了新的途径。细分曲面能实现任意拓扑网格中面片裁剪和片间光滑连接，也是重建曲面的一种重要表示形式。四边形网格细分技术较多，但是大多数研究都试图减小网格的增长速度，这对于网络传输非常必要，但不适合构造重建网格的细分曲面。本文提出一种新的细分模式，对正则和非正则四边形网格分别采用不同的细分模板。根据双三次B样条推导出正则四边形网格的细分模板，极限曲面C~2连续；对非正则四边形网格的细分矩阵进行傅立叶变换，在收敛的条件下推导出细分模板，极限曲面C~1连续。三分细分模式的特点是收敛速度快，适合快速构建大规模重建网格的细分曲面。(4)提出了基于网格简化的四边形网格参数化算法，为构造重建网格的参数曲面提供了新方法。为了构造重建四边形网格的参数曲面，必须对网格进行参数化，但是目前的参数化方法大多基于三角形网格，为此本文给出了四边形网格的参数化方法。计算网格顶点的高斯曲率，对网格边界顶点和高斯曲率较大的内部顶点进行全局参数化；引入带权的能量函数，通过能量极小将高斯曲率较小的内部顶点映射到参数域内；调整参数网格的顶点，删除重叠网格，实现网格优化。四边形网格参数化方法的创新在于引入带权能量函数，减少了角度和面积的扭曲变形，增加了曲面设计的灵活性。此外，该方法避免求解大型方程组，提高了计算效率，可为构造重建四边形网格的参数曲面提供有效方法。更多还原

【Abstract】 With the rapid development of computer science and modern manufacturing technology, more and more attention has been paid to the studies on the reverse engineering, which now is a research focus. In the reverse engineering, CAD model can be reconstructed by the numerical information of the object, which can make full use of the advanced manufacturing and management technology such as CAD/CAM. Besides, due to the ability of duplicating object in short time, the technology can sharpen the productivity, the product quality and enterprises’s market competition strength, and increase economic efficiency.The reverse engineering consists of data acquirement, data pre-processing and surface reconstruction. Data acquirement can obtain the coordinates of the discrete points by the fixed measuring equipment and methods. Data pre-processing includes the transformation of data format, data splicing, data smoothing and data cracking. The process decides whether the following CAD model reconstruction process is convenient, and whether the reconstruction model meets the application need. The goal of surface reconstruction is to seek some mathematics description form, which satisfies the given precision, effectively describes the shape of physical surface, and carries on the analysis, the computation, the revision and the rendering of the surface itself in this foundation.Surface reconstruction is the most important and difficult problem in the reverse engineering, but there still are key and difficult questions to wait for the solution and consummation. To large-scale data set, the surface reconstruction speed is slow; the reconstruction quality is not high and it needs massive human-computer interaction operations, and so on. In this paper, complex surface reconstruction technologies in the reverse engineering are studied, and new algorithms for quadrilateral mesh reconstruction as well as mesh subdivision and mesh parameterization are put forward, which provide the basis for the reconstruction of different surface types. The main contributions are as follows:(1) The shortest path algorithm for the curve reconstruction of scattered points is presented. It improves the quality of the reconstruction curve, and provides the effective rechnology for the screw reconstruction.The curve reconstruction is the base of the surface reconstruction, but now the present solutions can’t ensure the quality of reconstruction curve especially for the multiply connected scattered points. The shortest path approximation algorithm builds a weighted graph from the given set of scattered points using the distribution of these data points. By computing the shortest path in the weighted graph, the problem of curve reconstruction from scattered data points is transformed into that of curve reconstruction from a set of ordered data points.The potential function reflects the relationship between the scattered points, so the shortest path of the point set based on the potential function can keep the whole shape well. Besides, Delaunay triangulation and the deletion of some edges help identify the topology of the scattered point set. The proposed method can reconstruct curves from data set with arbitrary topology, such as simply connected, multiple connected and closed scattered points, keep the shape characteristic of point set well, especially in the segments with high curvature, and provide effective methods and technologies for the screw reconstrucion.(2) To reduce the face number of reconstruction meshes, a new method for quadrilateral mesh reconstruction is proposed.The reconstruction meshes of scattered point set are based on triangular meshes mainly, which makes the number of the meshes too large and can’t operate them in real time. The process of the quadrilateral mesh reconstruction proposed in this paper is as follows: Firstly, the least bounding box of scattered points is split into several cubic voxels, and the scattered points of every cubic voxel are simplified into one point. Secondly, each simplified point is connected with other simplified ones associated with its neighboring voxels, and then polygonal meshes are formed. Finally, the polygonal meshes are subdivided into quadrilateral meshes. The quadrilateral meshes with different precision can be obtained by adjusting the size of the cubic voxel. Compared with the triangular meshes, the proposed method reduces the number of the meshes, and makes it easier to reconstruct the surface, so it is suitable for the surface reconstruction of large-scale data set.(3) A new ternary stationary subdivision scheme for quadrilateral mesh is put forward, which provides new way to increase the subdivision efficiency.Subdivision technology is able to realize the trimming of any topological meshes, and the subdivision surface is an important expression form of reconstruction surfaces. There are many subdivision technologies on quadrilateral meshes, but most of them try to reduce the increasing speed of face number. This is extremely essential to the net transmission, but does not suit to construct the reconstruction surface.For regular and irregular quadrilateral meshes, different subdivision schemes are adopted respectively. The face number of the refined mesh is about nine times the face number of the coarse mesh every refinement. The limit surface of regular mesh is C~2 and the limit surface of irregular mesh is C~1. The characteristic of the ternary subdivision scheme is fast convergence speed, and is suitable for the reconstruction subdivision surface of large-scale data set.(4) To construct the parameterization form of reconstruction surface, a new algorithm for the planar parameterization of quadrilateral meshes is presented.To construct the parametric surface, the first step is to parameterize the quadrilateral meshes, but the present methods are almost used to parameterize the triangular meshes, so the parameterization technique for non-closed quadrilateral meshes based on mesh simplification is proposed. In the parameterization process, the global optimal parametric coordinates are attained by deleting interior vertices with low Gaussian curvature while preserving the whole shape as much as possible; then a local coordinate frame is chosen to adjust the positions of the deleted vertices through the weighted discrete mapping and minimize the local distortion; finally the parameterization meshes are optimized to avoid the overlapping.The weighted mapping is adopted to parameterize the vertices with low Gaussian curvature, which minimizes both the local and global distortion of the parameterization meshes. Different parameterization results can be obtained by adjusting the weight values in the energy function, thus it is very suitable for computer graphics applications that require parameterization with low geometric distortion. Besides, the solution of large equation set can be avoided and the computation efficiency can be increased using the algorithm for the planar parameterization of quadrilateral meshes, so it provides the basis for the reconstruction of parameterization surfaces for quadrilateral meshes.更多还原