CN100383823C - Hole filling method in point cloud of 3D scanning - Google Patents

Abstract

The present invention discloses method for filling point cloud holes in three-dimension scanning based on a triangular domain Bessel curved surface, which comprises physical model and three-dimensional data collection, data preprocessing, the reconstruction and the analysis of curves and curved surfaces, surface fitting, CAD model modeling, data programming and processing, parts, measurement of a database, and a CAD analog library. The present invention can obtain a curved surface accurately fitting a dispersed point set around the holes by using a surface fitting method so as to ensure high fitting precision when points are selected and the holes are filled on the curved surface.

Description

Translated fromChinese

三维扫描的点云孔洞填补方法Hole filling method in point cloud of 3D scanning

技术领域technical field

本发明涉及一种对三维图形的修补方法，尤其涉及一种三维扫描的点云孔洞填补方法。The invention relates to a method for repairing three-dimensional graphics, in particular to a method for filling holes in point clouds of three-dimensional scanning.

背景技术Background technique

逆向工程(Reverse Engineering，RE)技术是20世纪80年代后期出现在先进制造领域里的新技术，其一般包括四个基本环节：三维形体检测与转换(物理数据的获得)、数据预处理(点云处理、识别、多视拼接)，CAD模型的建立(曲面重构)、CAM制件成型，其基本流程图如附图1所示。在三维形体检测与转换的过程中，通过三维数字化扫描仪对实物模型表面进行三维快速扫描测量，在满足离散采样速度和数据质量的前提下，获取产品的三维离散数据，点云孔洞的出现造成了这些数据的不完整，因此对孔洞进行补偿即对数据进行预处理是逆向工程中非常关键的承上启下的一环，直接影响重构成功与否和CAD模型的质量，对其后续环节起着非常关键的制约作用。本发明主要是涉及到在逆向工程的数字化过程中，用三维扫描系统(附图2)获取产品点云模型出现孔洞时的一种自动补偿方法。Reverse Engineering (Reverse Engineering, RE) technology is a new technology that appeared in the field of advanced manufacturing in the late 1980s. It generally includes four basic links: three-dimensional shape detection and conversion (obtaining physical data), data preprocessing (point Cloud processing, recognition, multi-view splicing), CAD model establishment (surface reconstruction), CAM part molding, the basic flow chart is shown in Figure 1. In the process of 3D shape detection and conversion, the 3D digital scanner is used to perform 3D rapid scanning measurement on the surface of the physical model, and the 3D discrete data of the product can be obtained under the premise of satisfying the discrete sampling speed and data quality. The incompleteness of these data is eliminated, so the compensation for holes, that is, the preprocessing of data, is a very critical link in reverse engineering, which directly affects the success of the reconstruction and the quality of the CAD model, and plays a very important role in the subsequent links. key constraints. The present invention mainly relates to an automatic compensation method when a hole appears in a product point cloud model acquired by a three-dimensional scanning system (accompanying drawing 2) during the digitalization process of reverse engineering.

近年来，点云孔洞的填补算法在国内外均取得了很大的进展，已发表了相当数量的文献，其中一些算法获得了较为广泛的应用，如基于能量优化和细分、三角网格模型、网格曲面模型中孔洞的填补算法。这些算法需先对三维扫描直接获得的点云模型做一定的前期处理或者对点云孔洞进行边界识别，实时性不强，复杂度也比较高。在实际的工程应用中，对出现的问题应能及时解决。In recent years, point cloud hole filling algorithms have made great progress at home and abroad, and a considerable number of documents have been published, some of which have been widely used, such as energy optimization and subdivision, triangular mesh model , Hole filling algorithm in mesh surface model. These algorithms need to do some pre-processing on the point cloud model directly obtained by 3D scanning or identify the boundary of the point cloud hole, the real-time performance is not strong, and the complexity is relatively high. In practical engineering applications, problems should be solved in time.

文献“Minimal energy surfaces using parametric splines.”(GregoryE.Fasshauer，Larry L.Schumarker.Computer Aided Geometric Design，1996，13：45~79)通过求解以“变形能量函数”为基础的优化目标函数，实现对孔洞的填补，保证了一定的光顺性，然而这类方法大多需要细分曲面，并且对多个子曲面片进行拼接，因此对曲面边界的连续性要求较高，通常很难达到曲面间的二阶连续。由于现有的三角网格模型的相关算法比较成熟，现有的算法大多都是基于此模型的，例如文献“A study of stereolithography file errors and repair”(LeongK F，Chua C K，Ng Y M.International Journal of Advanced Manufacturing，1996，12：415~422)将孔洞填补归结为一个空间多边形的三角剖分问题。但大多在构造新三角片时仅仅采用原有的孔洞多边形顶点，没有增加新的三角片顶点，因而难以获得较好的用于填补孔洞的三角片形状，填补效果不够理想。并且这类算法对于复杂的点云数据编程建立三角网格模型运算量较大，在填补孔洞的过程中还需要改变三角网格的拓扑结构，因此具有对三角网格模型修改和再设计能力不足的缺点，复杂度高，这些缺点都限制了它在实践中的应用。对一类多边形孔洞的填充算法不适用于一般的点云模型。对于一般曲面网格的填充算法均需要准确的获得孔洞边界信息，难度大，不易实现。通过对点云孔洞周围散乱点集进行曲面拟合补偿孔洞的算法过程中，散乱点的参数化必不可少。通常有均匀参数化、向心参数化和累积弦长参数化方法，而这些方法主要针对呈拓扑矩形阵列的数据点，对无规则分布的点云数据，需要对其排序，难度也比较大。The literature "Minimal energy surfaces using parametric splines." (GregoryE.Fasshauer, Larry L.Schumarker.Computer Aided Geometric Design, 1996, 13: 45~79) realizes the optimization objective function based on the "deformation energy function" The filling of the holes ensures a certain level of smoothness. However, most of these methods require surface subdivision and splicing of multiple sub-surface pieces. Therefore, the continuity of the surface boundaries is high, and it is usually difficult to achieve two-dimensionality between surfaces. order continuous. Since the relevant algorithms of the existing triangular mesh model are relatively mature, most of the existing algorithms are based on this model, for example, the literature "A study of stereolithography file errors and repair" (LeongK F, Chua C K, Ng Y M. International Journal of Advanced Manufacturing, 1996, 12: 415~422) attributed hole filling to a triangulation problem of a spatial polygon. However, most of them only use the original hole polygon vertices when constructing new triangles, without adding new triangle vertices, so it is difficult to obtain a better triangle shape for filling holes, and the filling effect is not ideal. Moreover, this type of algorithm has a large amount of computation for programming complex point cloud data to establish a triangular mesh model. In the process of filling holes, the topology of the triangular mesh needs to be changed, so it has insufficient ability to modify and redesign the triangular mesh model. The shortcomings of high complexity limit its application in practice. The filling algorithm for a class of polygonal holes is not suitable for general point cloud models. For the filling algorithm of general surface mesh, it is necessary to obtain the boundary information of holes accurately, which is difficult and difficult to realize. The parameterization of scattered points is essential in the algorithm process of compensating holes by surface fitting to the set of scattered points around holes in the point cloud. There are usually uniform parameterization, centripetal parameterization, and cumulative chord length parameterization methods, and these methods are mainly aimed at data points in a topological rectangular array. For irregularly distributed point cloud data, they need to be sorted, which is relatively difficult.

传统的三角曲面插值算法也得到了较为广泛的应用，同时也获得了较好的效果。例如文献“An Adaptive Method for Smooth Surface Approximation to Scattered3D Points.”(Park H，Kim K.Computer Aided Design，1995，27(12)：929~939)中提出的构造光滑曲面拟合散乱点的自适应插值算法。这类插值算法虽然速度比较快，但有其致命的缺点，即：1只能处理单值的非封闭曲面；2要假定偏导矢在域边界曲线上呈线性分布；3重构的曲面依赖于估算出的偏导矢，所以曲面插值方法对离散点的逼近效果并不好，并且计算量大效率低。The traditional triangular surface interpolation algorithm has also been widely used and achieved good results. For example, the paper "An Adaptive Method for Smooth Surface Approximation to Scattered3D Points." (Park H, Kim K. Computer Aided Design, 1995, 27(12): 929~939) proposes an adaptive method for fitting scattered points on a smooth surface. Interpolation algorithm. Although this type of interpolation algorithm is relatively fast, it has its fatal shortcomings, namely: 1 can only deal with single-valued non-closed surfaces; 2 it must assume that the partial derivative vector is linearly distributed on the domain boundary curve; 3 the reconstructed surface depends on Because of the estimated partial derivative vector, the surface interpolation method does not have a good approximation effect on discrete points, and the calculation load is large and the efficiency is low.

在实际的应用过程中，用三维扫描系统得到的通常是具有海量散乱点的点云原始模型。此时就不可避免的存在孔洞现象，对这些孔洞进行及时的填补是关键。为此，本发明中使用一种新算法对孔洞进行补偿。如何对散乱点参数化以及提高曲面的拟合精度是此类算法中的难点。本发明中提出的对散乱点进行参数化的方法以及对曲面的迭代逼近优化方法能达到对孔洞的光滑拟合填充。In the actual application process, the original point cloud model with a large number of scattered points is usually obtained by the 3D scanning system. At this time, there will inevitably be holes, and timely filling of these holes is the key. For this reason, a new algorithm is used in the present invention to compensate for holes. How to parameterize the scattered points and improve the fitting accuracy of the surface is the difficulty in this kind of algorithm. The method for parameterizing scattered points and the iterative approximation optimization method for curved surfaces proposed in the invention can achieve smooth fitting and filling of holes.

发明内容Contents of the invention

本发明提供一种能够提供曲面拟合精确度的三维扫描的点云孔洞填补方法。The invention provides a point cloud hole filling method of three-dimensional scanning that can provide surface fitting accuracy.

本发明采用如下技术方案：The present invention adopts following technical scheme:

一种基于三角域贝塞尔曲面的三维扫描的点云孔洞填补方法：A point cloud hole filling method based on 3D scanning of triangular Bezier surfaces:

第一步：在点云孔洞周围且在屏幕坐标平面内设定一个三角形ABC，该三角形ABC的区域范围能使点云孔洞及其周围的点向屏幕坐标平面的投影落入三角形ABC内，并将投影落入三角形ABC内的点作为补孔时拟合曲面的点P_s(s＝0，1，…，m-1)，根据拟合曲面的点P_s在三角形ABC平面的投影P_s’位置计算其曲面参数化坐标(u_s，v_s，w_s)，u_s＝(ΔAP_s’B面积)/(ΔABC面积)、v_s＝(ΔAP_s’C面积)/(ΔABC面积)、w_s＝(ΔB P_s’C面积)/(ΔABC面积)，将拟合曲面的点P_s(s＝0，1，…，m-1)的坐标及其曲面参数化坐标(u_s，v_s，w_s)代入n次Bezier曲面方程并用最小二乘法得到n次Bezier曲面的控制点，从而得到初步拟合的曲面S(u，v，w)；Step 1: Set a triangle ABC around the point cloud hole and in the screen coordinate plane. The area of the triangle ABC can make the projection of the point cloud hole and its surrounding points to the screen coordinate plane fall into the triangle ABC, and The point that the projection falls into the triangle ABC is used as the point P_s (s=0, 1, ..., m-1) of the fitted surface when filling the hole, according to the projection P_s of the point P_s of the fitted surface on the triangle ABC plane 'Position is calculated by its surface parameterized coordinates (u_s , v_s , w_s ), u_s = (ΔAP_s 'B area)/(ΔABC area), v_s = (ΔAP_s 'C area)/(ΔABC area) , w_s = (ΔB P_s 'C area)/(ΔABC area), the coordinates of the point P_s (s=0, 1,..., m-1) of the fitted surface and its surface parameterized coordinates (u_s , v_s , w_s ) into the nth degree Bezier surface equation and use the least square method to obtain the control points of the nth degree Bezier surface, so as to obtain the preliminary fitting surface S(u, v, w);

第二步：求出各个拟合曲面的点P_s(s＝0，1，…，m-1)到曲面的距离向量d(u，v，w)及曲面分别对对应点参数方向的偏微分S_u(u，v，w)，S_v(u，v，w)，S_w(u，v，w)，令：Step 2: Calculate the distance vector d(u, v, w) from the point P_s (s=0, 1, ..., m-1) of each fitted surface to the surface and the deviation of the surface to the parameter direction of the corresponding point Differentiate S_u (u, v, w), S_v (u, v, w), S_w (u, v, w), let:

$\left\{\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\end{array}\right.$

拟合曲面的点P_s的参数化坐标为(u_s，v_s，w_s)，以(u_s，v_s，w_s)为初始估计值，根据牛顿迭代法求解以上方程组，有：The parameterized coordinates of the point P_s of the fitted surface are (u_s , v_s , w_s ), taking (u_s , v_s , w_s ) as the initial estimated value, and solving the above equations according to the Newton iterative method, there are:

Hσ^T＝κ^THσ^T =κ^T

式中：In the formula:

σ＝(δu，δv，δw)，其中，δu，δv，δw为曲面u，v，w三个方向上的迭代步长。σ=(δu, δv, δw), where δu, δv, δw are the iteration step sizes in the three directions of surface u, v, w.

κ＝-(f(u_s，v_s，w_s)，g(u_s，v_s，w_s)，h(u_s，v_s，w_s))κ=-(f(u_s , v_s , w_s ), g(u_s , v_s , w_s ), h(u_s , v_s , w_s ))

$\mathrm{<span><span>H</span>h</span>}<span><span>=</span>=</span>\left[\begin{array}{ccc}{\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>w</span>w</span>}}\\ {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>w</span>w</span>}}\\ {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>w</span>w</span>}}\end{array}\right]<span><span>=</span>=</span>\left[\begin{array}{ccc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}\end{array}\right]$

式中，d＝d(u_s，v_s，w_s)；f_u，f_v，f_w，g_u，g_v，g_w，h_u，h_v，h_w分别表示在点(u_s，v_s，w_s)处相应的向量对u，v，w的一阶偏导数；S_uu，S_uv，S_uw，S_vv，S_vu，S_vw，S_ww，S_wu，S_wv是曲面S(u，v，w)在点(u_s，v_s，w_s)处分别对u，v，w的二阶偏导数。In the formula, d=d(u_s , v_s , w_s ); f_u , f_v , f_w , g_u , g_v , g_w , h_u , h_v ,_hw respectively represent , v_s , w_s ) corresponding to the first-order partial derivative of the vector pair u, v, w; S_uu , S_uv , S_uw , S_vv , S_vu , S_vw , S_ww , S_wu , S_wv are The second order partial derivatives of surface S(u, v, w) at point (u_s , v_s , w_s ) with respect to u, v, w respectively.

则可得：Then you can get:

$\left[\begin{array}{ccc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}\end{array}\right]\left[\begin{array}{c}\mathrm{<span><span>\&delta;u</span>\&delta;u</span>}\\ \mathrm{<span><span>\&delta;v</span>\&delta;v</span>}\\ \mathrm{<span><span>\&delta;w</span>\&delta;w</span>}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$

根据三角Bezier曲面的定义可知δu+δv+δw＝0，即δw＝-δu-δv，因此得到如下迭代方程组：According to the definition of triangular Bezier surface, it can be known that δu+δv+δw=0, that is, δw=-δu-δv, so the following iterative equations are obtained:

$\left[\begin{array}{cc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>\end{array}\right]\left[\begin{array}{c}\mathrm{<span><span>\&delta;u</span>\&delta;\; u</span>}\\ \mathrm{<span><span>\&delta;v</span>\&delta;v</span>}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$

其中，δu，δv为u，v两个方向上的迭代步长。S_uu，S_uv，S_uw，S_vv，S_vu，S_vw，S_ww，S_wu，S_wv是曲面S(u，v，w)在点(u_s，v_s，w_s)处分别对u，v，w的二阶偏导数，迭代求解直到$1/m\underset{s=0}{\overset{m-1}{\&Sum;}}\left|\right|d(u_s+\mathrm{\&delta;u},v_s+\mathrm{\&delta;v},w_s+\mathrm{\&delta;w})-d(u_s,v_s,w_s)\left|\right|\&le;\mathrm{\&epsiv;},$ε为预置曲面拟合精度，从而得到最终确定的三角Bezier曲面S’(u，v，w)；Among them, δu and δv are the iteration step sizes in the two directions of u and v. S_uu , S_uv , S_uw , S_vv , S_vu , S_vw , S_ww , S_wu , S_wv are surfaces S(u, v, w) at points (u_s , v_s , w_s ) respectively For the second-order partial derivatives of u, v, w, iteratively solve until$1/m\underset{\mathrm{the\; s}=0}{\overset{m-1}{\&Sum;}}\left|\right|d(u_{\mathrm{the\; s}}+\mathrm{\&delta;u},v_{\mathrm{the\; s}}+\mathrm{\&delta;v},w_{\mathrm{the\; s}}+\mathrm{\&delta;w})-d(u_{\mathrm{the\; s}},v_{\mathrm{the\; s}},w_{\mathrm{the\; s}})\left|\right|\&le;\mathrm{\&epsiv;},$ ε is the preset surface fitting accuracy, so as to obtain the final triangular Bezier surface S'(u, v, w);

第三步：在所述的三角Bezier曲面S’(u，v，w)上取线，再在线上取点，用于填补点云孔洞。Step 3: Take a line on the triangular Bezier surface S'(u, v, w), and then take points on the line to fill the hole in the point cloud.

本发明主要用于对三维扫描系统中各种具有复杂曲面形状的点云原始模型中孔洞进行填补的应用场合。利用本发明中的曲面拟合算法，即可得到一张精确逼近孔洞周围散乱点的曲面，随后在面上取点可以即可实现对孔洞的光滑填补。该方法主要有以下优点：The invention is mainly used in the application occasion of filling holes in various point cloud original models with complex curved surface shapes in a three-dimensional scanning system. Using the surface fitting algorithm in the present invention, a curved surface that accurately approximates the scattered points around the hole can be obtained, and then the holes can be filled smoothly by taking points on the surface. This method mainly has the following advantages:

(1)由于传统的曲面插值方法对离散点的逼近效果并不好，本发明采用曲面拟合的方法能得到一张精确拟合孔洞周围散乱点集的曲面，从而在曲面上取点补孔时能保证较高的拟合精度。(1) Since the traditional surface interpolation method does not have a good approximation effect on discrete points, the present invention adopts the surface fitting method to obtain a curved surface that accurately fits the scattered point sets around the hole, thereby taking points on the curved surface to fill holes It can guarantee a high fitting accuracy.

(2)采用基于三角域上的曲面拟合方法，比四边域的曲面更容易表现无规则的表面，因此对具有复杂表面的物体，在补孔时更容易控制填补孔洞的曲面的形状，保证了补完孔的表面具有一定的光顺性和保形性。(2) Using the surface fitting method based on the triangular domain, it is easier to express the irregular surface than the surface of the quadrilateral domain. Therefore, for objects with complex surfaces, it is easier to control the shape of the surface that fills the hole when filling the hole. Guarantee In order to ensure that the surface of the filled hole has a certain degree of smoothness and shape retention.

(3)三角网格模型、网格曲面模型中孔洞的填补算法，这些算法需先对三维扫描直接获得的点云模型做一定的前期处理或者对点云孔洞进行边界识别，实时性不强，复杂度也比较高相比较多数算法中的网格化处理，本发明主要针对三维扫描系统得到的原始点云模型，不需要任何的网格化处理，适用性广，速度快。(3) Hole filling algorithms in triangular mesh models and mesh surface models. These algorithms need to do some pre-processing on the point cloud model directly obtained by 3D scanning or identify the boundary of the point cloud holes, and the real-time performance is not strong. The complexity is also relatively high. Compared with the grid processing in most algorithms, the present invention is mainly aimed at the original point cloud model obtained by the 3D scanning system, does not require any grid processing, and has wide applicability and high speed.

(4)拟合曲面时，交互选取孔洞周围的散乱点，无需对点云孔洞进行边界识别，所以当孔洞边界形状比较复杂时，也同样适用。(4) When fitting the surface, the scattered points around the hole are selected interactively, and there is no need to recognize the boundary of the hole in the point cloud, so it is also applicable when the shape of the hole boundary is complex.

(5)对散乱点参数化时，无需拟合孔洞的边界曲线，由于避免了孔洞的边界识别，因此对于绝大多数具有任意形状的孔洞也同样适用。(5) When parameterizing scattered points, there is no need to fit the boundary curve of the hole. Since the recognition of the boundary of the hole is avoided, it is also applicable to most holes with arbitrary shapes.

(6)由于对散乱点进行曲面拟合采用了初步拟合和迭代逼近优化两步方法，能够使拟合的曲面获得更高的精度。(6) Since the two-step method of preliminary fitting and iterative approximation optimization is adopted for surface fitting of scattered points, the fitted surface can obtain higher precision.

(7)操作过程比较简单，只要交互选定孔洞周围的离散点，接下来的的步骤都可自动完成，速度快。并且该方法具有很强的通用性。(7) The operation process is relatively simple, as long as the discrete points around the hole are interactively selected, the next steps can be completed automatically, and the speed is fast. And the method has strong versatility.

此外要注意的是，选取散乱点时，尽量在孔洞周围大范围内选取，可以避免自适应增加散乱点数量，以进一步提高算法的效率。In addition, it should be noted that when selecting scattered points, try to select them in a wide range around the hole, which can avoid adaptively increasing the number of scattered points, so as to further improve the efficiency of the algorithm.

附图说明Description of drawings

图1是逆向工程流程图。Figure 1 is a flow chart of reverse engineering.

图2是光栅式三维扫描系统组成图。Figure 2 is a composition diagram of the raster type three-dimensional scanning system.

图3是算法整体流程图。Figure 3 is the overall flowchart of the algorithm.

图4是选取圆盖点云中的孔洞附近的点集实例示意图。Fig. 4 is a schematic diagram of an example of selecting a point set near a hole in a dome point cloud.

图5是散乱点参数化流程图Figure 5 is a flow chart of parameterization of scattered points

图6是对圆盖点云中的孔洞附近的点集拟合曲面实例示意图。。Fig. 6 is a schematic diagram of an example of fitting a surface to a point set near a hole in a dome point cloud. .

图7是曲面初步拟合流程图。Figure 7 is a flow chart of the preliminary fitting of the curved surface.

图8是对圆盖点云中的孔洞填补实例示意图。Fig. 8 is a schematic diagram of an example of hole filling in a dome point cloud.

图9是曲面迭代逼近优化流程图。Fig. 9 is a flowchart of surface iterative approximation optimization.

具体实施方式Detailed ways

一种基于三角域贝塞尔曲面的三维扫描的点云孔洞填补方法：A point cloud hole filling method based on 3D scanning of triangular Bezier surfaces:

第一步：在点云孔洞周围且在屏幕坐标平面内设定一个三角形ABC，该三角形ABC的区域范围能使点云孔洞及其周围的点向屏幕坐标平面的投影落入三角形ABC内，并将投影落入三角形ABC内的点作为补孔时拟合曲面的点P_s(s＝0，1，…，m-1)，根据拟合曲面的点P_s在三角形ABC平面的投影P_s’位置计算其曲面参数化坐标(u_s，v_s，w_s)，u_s＝(ΔAP_s’B面积)/(ΔABC面积)、v_s＝(ΔAP_s’C面积)/(ΔABC面积)、w_s＝(ΔB P_s’C面积)/(ΔABC面积)，将拟合曲面的点P_s(s＝0，1，…，m-1)的坐标及其曲面参数化坐标(u_s，v_s，w_s)代入n次Bezier曲面方程并用最小二乘法得到n次Bezier曲面的控制点，从而得到初步拟合的曲面S(u，v，w)；Step 1: Set a triangle ABC around the point cloud hole and in the screen coordinate plane. The area of the triangle ABC can make the projection of the point cloud hole and its surrounding points to the screen coordinate plane fall into the triangle ABC, and The point that the projection falls into the triangle ABC is used as the point P_s (s=0, 1, ..., m-1) of the fitted surface when filling the hole, according to the projection P_s of the point P_s of the fitted surface on the triangle ABC plane 'Position is calculated by its surface parameterized coordinates (u_s , v_s , w_s ), u_s = (ΔAP_s 'B area)/(ΔABC area), v_s = (ΔAP_s 'C area)/(ΔABC area) , w_s = (ΔB P_s 'C area)/(ΔABC area), the coordinates of the point P_s (s=0, 1,..., m-1) of the fitted surface and its surface parameterized coordinates (u_s , v_s , w_s ) into the nth degree Bezier surface equation and use the least square method to obtain the control points of the nth degree Bezier surface, so as to obtain the preliminary fitting surface S(u, v, w);

第二步：求出各个拟合曲面的点P_s(s＝0，1，…，m-1)到曲面的距离向量d(u，v，w)及曲面分别对对应点参数方向的偏微分S_u(u，v，w)，S_v(u，v，w)，S_w(u，v，w)，令：Step 2: Calculate the distance vector d(u, v, w) from the point P_s (s=0, 1, ..., m-1) of each fitted surface to the surface and the deviation of the surface to the parameter direction of the corresponding point Differentiate S_u (u, v, w), S_v (u, v, w), S_w (u, v, w), let:

$\left\{\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\end{array}\right.$

拟合曲面的点P_s的参数化坐标为(u_s，v_s，w_s)，以(u_s，v_s，w_s)为初始估计值，根据牛顿迭代法求解以上方程组，有：The parameterized coordinates of the point P_s of the fitted surface are (u_s , v_s , w_s ), taking (u_s , v_s , w_s ) as the initial estimated value, and solving the above equations according to the Newton iterative method, there are:

Hσ^T＝κ^THσ^T =κ^T

式中：In the formula:

σ＝(δu，δv，δw)σ = (δu, δv, δw)

其中，δu，δv，δw为曲面u，v，w三个方向上的迭代步长。Among them, δu, δv, and δw are the iteration steps in the three directions of surface u, v, and w.

κ＝-(f(u_s，v_s，w_s)，g(u_s，v_s，w_s)，h(u_s，v_s，w_s))κ=-(f(u_s , v_s , w_s ), g(u_s , v_s , w_s ), h(u_s , v_s , w_s ))

$\mathrm{<span><span>H</span>h</span>}<span><span>=</span>=</span>\left[\begin{array}{ccc}{\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>w</span>w</span>}}\\ {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>w</span>w</span>}}\\ {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>w</span>w</span>}}\end{array}\right]<span><span>=</span>=</span>\left[\begin{array}{ccc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}\end{array}\right]$

式中，d＝d(u_s，v_s，w_s)；f_u，f_v，f_w，g_u，g_v，g_w，h_u，h_v，h_w分别表示在点(u_s，v_s，w_s)处相应的向量对u，v，w的一阶偏导数；S_uu，S_uv，S_uw，S_vv，S_vu，S_vw，S_ww，S_wu，S_wv是曲面S(u，v，w)在点(u_s，v_s，w_s)处分别对u，v，w的二阶偏导数。In the formula, d=d(u_s , v_s , w_s ); f_u , f_v , f_w , g_u , g_v , g_w , h_u , h_v ,_hw respectively represent , v_s , w_s ) corresponding to the first-order partial derivative of the vector pair u, v, w; S_uu , S_uv , S_uw , S_vv , S_vu , S_vw , S_ww , S_wu , S_wv are The second order partial derivatives of surface S(u, v, w) at point (u_s , v_s , w_s ) with respect to u, v, w respectively.

则可得：Then you can get:

$\left[\begin{array}{ccc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}\end{array}\right]\left[\begin{array}{c}\mathrm{<span><span>\&delta;u</span>\&delta;\; u</span>}\\ \mathrm{<span><span>\&delta;v</span>\&delta;v</span>}\\ \mathrm{<span><span>\&delta;w</span>\&delta;w</span>}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$

根据三角Bezier曲面的定义可知δu+δv+δw＝0，即δw＝-δu-δv，因此得到如下迭代方程组：According to the definition of triangular Bezier surface, it can be known that δu+δv+δw=0, that is, δw=-δu-δv, so the following iterative equations are obtained:

$\left[\begin{array}{cc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>\end{array}\right]\left[\begin{array}{c}\mathrm{<span><span>\&delta;u</span>\&delta;\; u</span>}\\ \mathrm{<span><span>\&delta;v</span>\&delta;\; v</span>}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$

其中，δu，δv为u，v两个方向上的迭代步长。S_uu，S_uv，S_uw，S_vv，S_vu，S_vw，S_ww，S_wu，S_wv是曲面S(u，v，w)在点(u_s，v_s，w_s)处分别对u，v，w的二阶偏导数，迭代求解直到$1/m\underset{s=0}{\overset{m-1}{\&Sum;}}\left|\right|d(u_s+\mathrm{\&delta;u},v_s+\mathrm{\&delta;v},w_s+\mathrm{\&delta;w})-d(u_s,v_s,w_s)\left|\right|\&le;\mathrm{\&epsiv;},$ε为预置曲面拟合精度，从而得到最终确定的三角Bezier曲面S’(u，v，w)；Among them, δu and δv are the iteration step sizes in the two directions of u and v. S_uu , S_uv , S_uw , S_vv , S_vu , S_vw , S_ww , S_wu , S_wv are surfaces S(u, v, w) at points (u_s , v_s , w_s ) respectively For the second-order partial derivatives of u, v, w, iteratively solve until$1/m\underset{\mathrm{the\; s}=0}{\overset{m-1}{\&Sum;}}\left|\right|d(u_{\mathrm{the\; s}}+\mathrm{\&delta;u},v_{\mathrm{the\; s}}+\mathrm{\&delta;\; v},w_{\mathrm{the\; s}}+\mathrm{\&delta;w})-d(u_{\mathrm{the\; s}},v_{\mathrm{the\; s}},w_{\mathrm{the\; s}})\left|\right|\&le;\mathrm{\&epsiv;},$ ε is the preset surface fitting accuracy, so as to obtain the final triangular Bezier surface S'(u, v, w);

第三步：在所述的三角Bezier曲面S’(u，v，w)上取线，再在线上取点，用于填补点云孔洞。Step 3: Take a line on the triangular Bezier surface S'(u, v, w), and then take points on the line to fill the hole in the point cloud.

下面参照附图，对本发明加以详细描述：Below with reference to accompanying drawing, the present invention is described in detail:

在逆向工程中，面对的是密集的点云散乱数据。拟合曲面时，如果曲面的对象边界和形状极其复杂时，一般不便直接运用常规的曲面构造方法，而Bezier曲面由于其构造灵活，边界适应性好，具有构造复杂形状的潜力，而且其本身具有良好的性质：光滑性、局部性和保形性。基于三角域曲面的拟合方法最适合表现无规则型面的物体，特别是人面，地貌等自然物体以及玩具等产品，基于四边域参数曲面的拟合方法，通常要求数据点是有序的，这个条件比较苛刻，综合以上，因此本发明采用三角域上的Bezier曲面对孔洞部分进行拟合填充。总体算法流程见附图3。In reverse engineering, what is faced is dense point cloud scattered data. When fitting a surface, if the object boundary and shape of the surface are extremely complex, it is generally inconvenient to use the conventional surface construction method directly, but the Bezier surface has the potential to construct complex shapes due to its flexible structure and good boundary adaptability, and it has its own Good properties: smoothness, locality and shape retention. The fitting method based on triangular domain surfaces is most suitable for objects with irregular shapes, especially natural objects such as human faces and landforms, and toys and other products. The fitting method based on quadrilateral domain parametric surfaces usually requires that the data points are in order , this condition is relatively harsh, and based on the above, the present invention uses the Bezier surface on the triangular domain to fit and fill the hole part. The overall algorithm flow is shown in Figure 3.

本发明主要包括以下步骤：The present invention mainly comprises the following steps:

1)散乱点的选定及参数化过程1) Selection and parameterization process of scattered points

在圆盖点云孔洞屏幕二维坐标系附近选择不共线的三点A、B、C，构成需要初步拟合的三角Bezier曲面片的三个角点，将孔洞周围的点向这三点所构成的三角形平面投影，如果点落在三角形平面内，则认为是拟合曲面时所需的点P_s(s＝0，1，…，m-1)，见附图4。Select three non-collinear points A, B, and C near the two-dimensional coordinate system of the hole screen of the dome point cloud to form the three corner points of the triangular Bezier surface patch that needs to be initially fitted, and move the points around the hole to these three points For the formed triangular plane projection, if the point falls within the triangular plane, it is considered as the point P_s (s=0, 1, . . . , m-1) required for fitting the curved surface.

根据选取的点P_s在三角形ABC平面的投影位置计算其曲面参数化坐标。即如果P_s在三角形平面ABC内相对应的投影点为P_s’，那么P_s的参数化坐标(u_s，v_s，w_s)分别为u_s＝(ΔAP_s’B面积)/(ΔABC面积)、v_s＝(ΔAP_s’C面积)/(ΔABC面积)、w_s＝(ΔB P_s’C面积)/(ΔABC面积)。算法流程图见附图5。According to the projected position of the selected point P_s on the triangle ABC plane, its surface parameterized coordinates are calculated. That is, if the corresponding projection point of P_s in the triangular plane ABC is P_s ', then the parameterized coordinates (u_s , v_s , w_s ) of P_s are u_s = (ΔAP_s 'B area)/( ΔABC area), v_s =(ΔAP_s 'C area)/(ΔABC area), w_s =(ΔB P_s 'C area)/(ΔABC area). The flowchart of the algorithm is shown in Figure 5.

2)最小二乘自适应初步拟合2) Least square adaptive preliminary fitting

三角域ABC上n次Bezier曲面的表达式为：The expression of n degree Bezier surface on triangular domain ABC is:

$\mathrm{<span><span>S</span>S</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\underset{\mathrm{<span><span>i</span>i</span>}<span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}}{\overset{\mathrm{<span><span>n</span>no</span>}}{<span><span>\&Sum;</span>\&Sum;</span>}}\underset{\mathrm{<span><span>j</span>j</span>}<span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}}{\overset{\mathrm{<span><span>n</span>no</span>}<span><span>-</span>-</span>\mathrm{<span><span>i</span>i</span>}}{<span><span>\&Sum;</span>\&Sum;</span>}}{\mathrm{<span><span>B</span>B</span>}}_{\mathrm{<span><span>ijk</span>ijk</span>}}^{\mathrm{<span><span>n</span>no</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span>{\mathrm{<span><span>b</span>b</span>}}_{\mathrm{<span><span>ijk</span>ijk</span>}}$

式中$B_{\mathrm{ijk}}^n(u,v,w)=\frac{n!}{i!j!k!}{u}^i{v}^j{w}^k\&GreaterEqual;0\left\{\begin{array}{c}0\&le;u,v,w\&le;l,u+v+w=l\\ 0\&le;i,j,k\&le;n,i+j+k=n\end{array}\right.$In the formula$B_{\mathrm{ijk}}^{\mathrm{no}}(u,v,w)=\frac{\mathrm{no}!}{i!j!k!}{u}^i{v}^j{w}^k\&Greater\; Equal;0\left\{\begin{array}{c}0\&le;u,v,w\&le;l,u+v+w=l\\ 0\&le;i,j,k\&le;\mathrm{no},i+j+k=\mathrm{no}\end{array}\right.$

根据上步已知，可以求得三角域上n次Bezier曲面的表达式中P_s的参数化坐标(u_s，v_s，w_s)，According to the knowledge in the previous step, the parameterized coordinates (u_s , v_s , w_s ) of P_s in the expression of the nth Bezier surface on the triangular domain can be obtained,

(n+1)(n+2)/2个控制顶点为n次Bezier曲面的表达式中的未知量，所以只要求出(n+1)(n+2)/2个控制顶点坐标b_ijk(0≤i，j，k≤n，i+j+k＝n)，即可确定出一个三角Bezier曲面。(n+1)(n+2)/2 control vertices are the unknowns in the expression of nth Bezier surface, so only (n+1)(n+2)/2 control vertex coordinates b_ijk are required (0≤i, j, k≤n, i+j+k=n), a triangular Bezier surface can be determined.

根据三角Bezier曲面的性质可知三角Bezier曲面的三个角点正好是其控制多面体网格的三个控制顶点，那么所选三角形的三个顶点A、B、C即可做为三个已知控制顶点b_00n，b_0n0，b_n00，把P_s(s＝0，1，…，m-1)的坐标代入三角Bezier曲面方程，构成以(n+1)(n+2)/2-3个未知控制顶点为未知量的m个线性方程组。在所选三角形内部的三维坐标点数m一般大于(n+1)(n+2)/2-3，在不满足此条件即待求方程组系数矩阵奇异时，以三角形ABC的重心为基点，扩大三角形ABC的面积来增加m的个数。最后采用最小二乘法求解此过约束方程组，确定出曲面其它的未知控制顶点，得到初步拟合的曲面S(u，v，w)，见附图6。算法流程图见附图7。According to the properties of the triangular Bezier surface, the three corner points of the triangular Bezier surface are just the three control vertices of its control polyhedral mesh, then the three vertices A, B, and C of the selected triangle can be used as the three known control vertices Vertices b_00n , b_0n0 , b_n00 , put the coordinates of P_s (s=0, 1,..., m-1) into the triangular Bezier surface equation, and form the equation of (n+1)(n+2)/2-3 A system of m linear equations whose unknown control vertices are unknown quantities. The number of three-dimensional coordinate points m inside the selected triangle is generally greater than (n+1)(n+2)/2-3. When this condition is not satisfied, that is, when the coefficient matrix of the system of equations to be obtained is singular, the center of gravity of the triangle ABC is used as the base point. Expand the area of triangle ABC to increase the number of m. Finally, the least square method is used to solve the over-constrained equations, determine other unknown control vertices of the surface, and obtain a preliminary fitting surface S(u, v, w), see Figure 6. The flowchart of the algorithm is shown in Figure 7.

3)曲面逼近优化3) Surface approximation optimization

经过最小二乘初步拟合后，散乱点集P_s与曲面S(u，v，w)的距离误差还比较大，因此需要进一步修正控制顶点，改变控制多面体的形状，从而改变曲面的形状，使曲面逼近点集。本发明采用了以牛顿迭代法为基础的迭代逼近算法，提高拟合精度，最终确定出曲面S’(u，v，w)，见附图8。After preliminary fitting by least squares, the distance error between the scattered point set P_s and the surface S(u, v, w) is relatively large, so it is necessary to further correct the control vertices and change the shape of the control polyhedron, thereby changing the shape of the surface. Make a surface approximate to a set of points. The present invention adopts an iterative approximation algorithm based on Newton's iterative method to improve the fitting accuracy and finally determine the curved surface S'(u, v, w), see Figure 8.

具体步骤如下：Specific steps are as follows:

(1)求出各个散乱点到曲面的距离向量d(u，v，w)及曲面分别对对应点参数方向的偏微分S_u(u，v，w)，S_v(u，v，w)，S_w(u，v，w)，组成待求方程组如下：(1) Calculate the distance vector d(u, v, w) from each scattered point to the surface and the partial differential of the surface to the parameter direction of the corresponding point S_u (u, v, w), S_v (u, v, w ), S_w (u, v, w), form the system of equations to be obtained as follows:

$\left\{\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\end{array}\right.$

(2)采用基于牛顿迭代法的方法求解此方程组，最终可求得的迭代方程组为：(2) Using the method based on Newton's iterative method to solve this system of equations, the final iterative system of equations that can be obtained is:

$\left[\begin{array}{cc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>\end{array}\right]\left[\begin{array}{c}\mathrm{<span><span>\&delta;u</span>\&delta;\; u</span>}\\ \mathrm{<span><span>\&delta;v</span>\&delta;v</span>}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>,</span>,</span>{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$

(3)迭代求解以上方程组，当拟合曲面的点数少于迭代方程组的未知数个数时，及方程组系数奇异时，同样以三角形ABC的重心为基点，自适应扩大三角ABC的面积来增加m的个数，重复(2)。(3) Iteratively solve the above equations. When the number of points of the fitted surface is less than the number of unknowns of the iterative equations, and the coefficients of the equations are singular, the center of gravity of the triangle ABC is also used as the base point to adaptively expand the area of the triangle ABC. Increase the number of m, repeat (2).

算法流程图见附图9。The flowchart of the algorithm is shown in Figure 9.

4)面上取点补孔4) Take points on the surface to fill holes

在最终拟合好的Bezier曲面上取点填充孔洞，首先在曲面上取线，再在线上取点，实现孔洞的光滑填补。Take points on the final fitted Bezier surface to fill holes, first take lines on the surface, and then take points on the lines to achieve smooth filling of holes.

Claims (3)

Translated fromChinese

1.一种基于三角域贝塞尔曲面的三维扫描的点云孔洞填补方法，其特征在于：1. a kind of point cloud hole filling method based on the three-dimensional scanning of triangular domain Bezier surface, it is characterized in that:第一步：在点云孔洞周围且在屏幕坐标平面内设定一个三角形ABC，该三角形ABC的区域范围能使点云孔洞及其周围的点向屏幕坐标平面的投影落入三角形ABC内，并将投影落入三角形ABC内的点作为补孔时拟合曲面的点P_s，s＝0，1，...，m-1，根据拟合曲面的点P_s在三角形ABC平面的投影P_s’位置计算其曲面参数化坐标(u_s，v_s，w_s)，u_s＝(ΔAP_s’B面积)/(ΔABC面积)、v_s＝(ΔAP_s’C面积)/(ΔABC面积)、w_s＝(ΔB P_s’C面积)/(ΔABC面积)，将拟合曲面的点P_s，s＝0，1，...，m-1的坐标及其曲面参数化坐标(u_s，v_s，w_s)代入n次Bezier曲面方程并用最小二乘法得到n次Bezier曲面的控制点，从而得到初步拟合的曲面S(u，v，w)；Step 1: Set a triangle ABC around the point cloud hole and in the screen coordinate plane. The area of the triangle ABC can make the projection of the point cloud hole and its surrounding points to the screen coordinate plane fall into the triangle ABC, and The point that the projection falls into the triangle ABC is used as the point P_s of the fitting surface when filling the hole, s=0, 1,..., m-1, according to the projection P of the point P_s of the fitting surface on the plane of the triangle ABC_s ' position calculates its surface parameterized coordinates (u_s , v_s , w_s ), u_s = (ΔAP_s 'B area)/(ΔABC area), v_s = (ΔAP_s 'C area)/(ΔABC area ), w_s =(ΔB P_s 'C area)/(ΔABC area), the point P_s of the fitting surface, s=0, 1,..., m-1 coordinates and its surface parameterization coordinates ( u_s , v_s , w_s ) are substituted into the nth degree Bezier surface equation and the control points of the nth degree Bezier surface are obtained by the least square method, so as to obtain the preliminary fitting surface S(u, v, w);第二步：求出各个拟合曲面的点P_s，s＝0，1，...，m-1到曲面的距离向量d(u，v，w)及曲面分别对对应点参数方向的偏微分S_u(u，v，w)，S_v(u，v，w)，S_w(u，v，w)，令：Step 2: Calculate the distance vector d(u, v, w) of each point P_s of each fitting surface, s=0, 1, ..., m-1 to the surface and the parameter direction of the corresponding point of the surface respectively Partial differential S_u (u, v, w), S_v (u, v, w), S_w (u, v, w), let:$\left\{\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>d</span>d</span>}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>(</span>(</span>\mathrm{<span><span>u</span>u</span>}<span><span>,</span>,</span>\mathrm{<span><span>v</span>v</span>}<span><span>,</span>,</span>\mathrm{<span><span>w</span>w</span>}<span><span>)</span>)</span><span><span>=</span>=</span>\mathrm{<span><span>0</span>0</span>}\end{array}\right.$拟合曲面的点P_s的参数化坐标为(u_s，v_s，w_s)，以(u_s，v_s，w_s)为初始估计值，根据牛顿迭代法求解以上方程组，有：The parameterized coordinates of the point P_s of the fitted surface are (u_s , v_s , w_s ), taking (u_s , v_s , w_s ) as the initial estimated value, and solving the above equations according to the Newton iterative method, there are:Hσ^T＝κ^THσ^T =κ^T式中：In the formula:σ＝(δu，δv，δw)，其中，δu，δv，δw为曲面u，v，w三个方向上的迭代步长；σ=(δu, δv, δw), wherein, δu, δv, δw are the iterative step sizes in the three directions of surface u, v, and w;κ＝-(f(u_s，v_s，w_s)，g(u_s，v_s，w_s)，h(u_s，v_s，w_s))κ=-(f(u_s , v_s , w_s ), g(u_s , v_s , w_s ), h(u_s , v_s , w_s ))$\mathrm{<span><span>H</span>h</span>}<span><span>=</span>=</span>\left[\begin{array}{ccc}{\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>f</span>f</span>}}_{\mathrm{<span><span>w</span>w</span>}}\\ {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>g</span>g</span>}}_{\mathrm{<span><span>w</span>w</span>}}\\ {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>u</span>u</span>}}& {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>v</span>v</span>}}& {\mathrm{<span><span>h</span>h</span>}}_{\mathrm{<span><span>w</span>w</span>}}\end{array}\right]<span><span>=</span>=</span>\left[\begin{array}{ccc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}\end{array}\right]$式中，d＝d(u_s，v_s，w_s)；f_u，f_v，f_w，g_u，g_v，g_w，h_u，h_v，h_w分别表示在点(u_s，v_s，w_s)处相应的向量对u，v，w的一阶偏导数；S_uu，S_uv，S_uw，S_vv，S_vu，S_vw，S_ww，S_wu，S_wv是曲面S(u，v，w)在点(u_s，v_s，w_s)处分别对u，v，w的二阶偏导数，则可得：In the formula, d=d(u_s , v_s , w_s ); f_u , f_v , f_w , g_u , g_v , g_w , h_u , h_v ,_hw respectively represent , v_s , w_s ) corresponding to the first-order partial derivative of the vector pair u, v, w; S_uu , S_uv , S_uw , S_vv , S_vu , S_vw , S_ww , S_wu , S_wv are The second order partial derivatives of the surface S(u, v, w) at the point (u_s , v_s , w_s ) with respect to u, v, w respectively, then we can get:$\left[\begin{array}{ccc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}\end{array}\right]\left[\begin{array}{c}{\mathrm{<span><span>\&delta;</span>\&delta;</span>}}_{\mathrm{<span><span>u</span>u</span>}}\\ {\mathrm{<span><span>\&delta;</span>\&delta;</span>}}_{\mathrm{<span><span>v</span>v</span>}}\\ {\mathrm{<span><span>\&delta;</span>\&delta;</span>}}_{\mathrm{<span><span>w</span>w</span>}}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$根据三角Bezier曲面的定义可知δu+δv+δw＝0，即δw＝-δu-δv，因此得到如下迭代方程组：According to the definition of triangular Bezier surface, it can be known that δu+δv+δw=0, that is, δw=-δu-δv, so the following iterative equations are obtained:$\left[\begin{array}{cc}{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uu</span>u\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uv</span>uv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>uw</span>uw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vu</span>v\; u</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>& {<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vv</span>vv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>vw</span>vw</span>}}<span><span>)</span>)</span>\\ {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>u</span>u</span>}}<span><span>\&CenterDot;</span>\&Center\; Dot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&CenterDot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wu</span>wu</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>& {\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>v</span>v</span>}}<span><span>\&CenterDot;</span>\&CenterDot;</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>-</span>-</span>{<span><span>|</span>|</span><span><span>|</span>|</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>w</span>w</span>}}<span><span>|</span>|</span><span><span>|</span>|</span>}^{\mathrm{<span><span>2</span>2</span>}}<span><span>+</span>+</span>\mathrm{<span><span>d</span>d</span>}<span><span>\&CenterDot;</span>\&Center\; Dot;</span><span><span>(</span>(</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>wv</span>wv</span>}}<span><span>-</span>-</span>{\mathrm{<span><span>S</span>S</span>}}_{\mathrm{<span><span>ww</span>ww</span>}}<span><span>)</span>)</span>\end{array}\right]\left[\begin{array}{c}{\mathrm{<span><span>\&delta;</span>\&delta;</span>}}_{\mathrm{<span><span>u</span>u</span>}}\\ {\mathrm{<span><span>\&delta;</span>\&delta;</span>}}_{\mathrm{<span><span>u</span>u</span>}}\end{array}\right]<span><span>=</span>=</span><span><span>-</span>-</span>\left[\begin{array}{c}\mathrm{<span><span>f</span>f</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>g</span>g</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\\ \mathrm{<span><span>h</span>h</span>}<span><span>(</span>(</span>{\mathrm{<span><span>u</span>u</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>v</span>v</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}<span><span>,</span>,</span>}{\mathrm{<span><span>w</span>w</span>}}_{\mathrm{<span><span>s</span>the\; s</span>}}<span><span>)</span>)</span>\end{array}\right]$其中，δu，δv为u，v两个方向上的迭代步长，S_uu，S_uv，S_uw，S_vv，S_vu，S_vw，S_ww，S_wu，S_wv是曲面S(u，v，w)在点(u_s，v_s，w_s)处分别对u，v，w的二阶偏导数，迭代求解直到$1/m\underset{s=0}{\overset{m-1}{\mathrm{\&Sigma;}}}\left|\right|d(u_s+\mathrm{\&delta;u},v_s+\mathrm{\&delta;v},w_s+\mathrm{\&delta;w})-d\left(u_{s,}{v}_{s,}{w}_s\right)\left|\right|\&le;\mathrm{\&epsiv;},$ε为预置曲面拟合精度，从而得到最终确定的三角Bezier曲面S’(u，v，w)；Among them, δu and δv are the iterative step sizes in the directions of u and v, and S_uu , S_uv , S_uw , S_vv , S_vu , S_vw , S_ww , S_wu , and S_wv are surface S(u, v, w) at the point (u_s , v_s , w_s ) respectively with respect to the second order partial derivatives of u, v, w, iteratively solve until$1/m\underset{\mathrm{the\; s}=0}{\overset{m-1}{\mathrm{\&Sigma;}}}\left|\right|d(u_{\mathrm{the\; s}}+\mathrm{\&delta;u},v_{\mathrm{the\; s}}+\mathrm{\&delta;v},w_{\mathrm{the\; s}}+\mathrm{\&delta;w})-d\left(u_{\mathrm{the\; s},}{v}_{\mathrm{the\; s},}{w}_{\mathrm{the\; s}}\right)\left|\right|\&le;\mathrm{\&epsiv;},$ ε is the preset surface fitting accuracy, so as to obtain the final triangular Bezier surface S'(u, v, w);第三步：在所述的三角Bezier曲面S’(u，v，w)上基于曲率的等参数取线，再在线上等参数取点，用于填补点云孔洞。Step 3: On the triangular Bezier surface S'(u, v, w), take a line based on curvature isoparameters, and then take points on the line and other parameters to fill the hole in the point cloud.2.根据权利要求1所述的三维扫描的点云孔洞填补方法，其特征在于拟合曲面的点数少于曲面控制顶点数时，扩大所设定三角形ABC的面积，使拟合曲面的点数大于曲面控制顶点数。2. The point cloud hole filling method of three-dimensional scanning according to claim 1, wherein when the number of points of the fitted curved surface is less than the number of control vertices of the curved surface, the area of the set triangle ABC is expanded so that the number of points of the fitted curved surface is greater than The surface controls the number of vertices.3.根据权利要求1所述的三维扫描的点云孔洞填补方法，其特征在于拟合曲面的点数少于迭代方程组的未知数个数时，扩大所设定三角形ABC的面积，使拟合曲面的点数大于或等于迭代方程组的未知数个数。3. The point cloud hole filling method of three-dimensional scanning according to claim 1, wherein when the number of points of the fitting surface is less than the number of unknowns of the iterative equation system, the area of the set triangle ABC is expanded so that the fitting surface The number of points is greater than or equal to the number of unknowns in the iterative equation system.

Images