CN103413175A

CN103413175A - Closed non-uniform rational B-spline curve fairing method based on genetic algorithm

Info

Publication number: CN103413175A
Application number: CN2013102894894A
Authority: CN
Inventors: 莫蓉; 马峰; 王英伟; 余旸; 万能
Original assignee: Northwestern Polytechnical University
Current assignee: Northwestern Polytechnical University
Priority date: 2013-07-10
Filing date: 2013-07-10
Publication date: 2013-11-27
Anticipated expiration: 2033-07-10
Also published as: CN103413175B

Abstract

The invention discloses a closed non-uniform rational B-spline curve smoothing method based on genetic algorithm, which is used to solve the technical problem of slow speed of the existing closed non-uniform rational B-spline curve smoothing method. The technical solution is to re-interpolate the curve by adding value points between the two value points with inverse curvature. The position of the new value points is determined by the genetic algorithm under the constraints of the fairness criterion, and then the shape of the curve is adjusted to make it smooth. The method not only makes the re-interpolated curve strictly pass through the original type value points, but also solves the problem of inverse curvature of the original curve, and is smoother than the curve disclosed in the background technology. At the same time, it effectively solves the phenomenon of pits on the closed section line at the junction of the trailing edge, the back of the leaf and the leaf pot, making the section line of the blade smoother, and this method is applicable to a variety of 3D CAD software platforms, thus effectively making up for It solves the shortcomings of the existing NURBS curve interpolation research, and improves the smoothing speed.

Description

A Smoothing Method for Closed Nonuniform Rational B-spline Curve Based on Genetic Algorithm

技术领域technical field

本发明涉及一种闭合非均匀有理B样条曲线光顺方法，特别涉及一种基于遗传算法的闭合非均匀有理B样条曲线光顺方法。The invention relates to a method for smoothing a closed non-uniform rational B-spline curve, in particular to a method for smoothing a closed non-uniform rational B-spline curve based on a genetic algorithm.

背景技术Background technique

复杂产品，如航空发动机叶片或发电机叶片的三维模型构造，通常利用来自气动（或其他计算得到）数据得到的型值点来构造叶身型面，即通过“截面曲线插值型值点—曲面过截面曲线”构造叶身型面。目前的叶片前/后缘多是给出前/后缘圆心的和半径位置作为已知条件，通过前/后缘与叶背和叶盆的一阶几何连续连接创建截面线，从而完成曲面造型。而截面线造型方法的发展趋势越来越多地使用型值点直接表示形状，通过型值点直接插值创建一条二阶几何连续的截面线。但是由于叶身后缘的曲率变化比较大，形状对气动性能非常敏感，因此在后缘附近处型值点非常密，而在叶背和叶盆上的型值点则相对稀疏，由此会造成后缘与叶背和叶盆的拼接处的封闭截面线出现凹坑，从而影响叶身型面。因此如何处理这种凹坑使其光顺时一个现实问题，已有的三维CAD软件系统无法解决此类问题。Complex products, such as the 3D model construction of aeroengine blades or generator blades, usually use the model points obtained from aerodynamic (or other calculated) data to construct the airfoil profile, that is, through the "section curve interpolation model point-surface "Cross section curve" to construct the airfoil profile. At present, the leading/trailing edge of the blade mostly gives the center and radius position of the leading/trailing edge as known conditions, and creates a section line through the first-order geometric continuous connection between the leading/trailing edge and the blade back and leaf pot, thereby completing the surface modeling. However, the development trend of section line modeling methods is to use more and more type-value points to directly represent the shape, and to create a second-order geometrically continuous section line through direct interpolation of type-value points. However, due to the relatively large curvature change of the trailing edge of the blade, the shape is very sensitive to aerodynamic performance, so the type points near the trailing edge are very dense, while the type points on the blade back and leaf basin are relatively sparse, which will cause Pimples appear on the closed section line where the trailing edge joins the blade back and the blade pot, thereby affecting the shape of the blade body. Therefore, how to deal with such pits to make them smooth is a practical problem, and the existing 3D CAD software systems cannot solve such problems.

非均匀有理B样条（以下简称NURBS，Non-Uniform Rational B-Spline）方法表示曲线曲面早已成为CAD系统的标准表达形式，它不但解决了自由曲线曲面与初等解析曲线曲面描述的不相容问题，并克服了Bezier、B样条方法的不足，同时权因子和非均匀节点矢量使得能够对曲线曲面的形状进行更加有效地控制，而且能够使得在一个CAD系统中严格地以一种统一的数学模型定义产品几何形状，使系统得以精简，易于数据管理，便于工程人员使用，同时提高了曲面造型能力。Non-Uniform Rational B-Spline (hereinafter referred to as NURBS, Non-Uniform Rational B-Spline) method to express curves and surfaces has already become the standard expression form of CAD system. It not only solves the incompatibility problem between free curves and surfaces and elementary analytical curves and surfaces. , and overcome the shortcomings of Bezier and B-spline methods. At the same time, weight factors and non-uniform node vectors enable more effective control of the shape of curves and surfaces, and can strictly use a unified mathematical method in a CAD system The model defines the product geometry, allowing the system to be streamlined, easy to manage data, and easy to use by engineers, while improving surface modeling capabilities.

对于通过插值生成的NURBS曲线，往往会在型值点较密处向型值点较疏处过渡的地方出现曲率反向，导致曲线出现不光顺的现象。目前，针对NURBS插值曲线的不光顺的情况，主要有修改坏点、调整权因子和调整节点向量等光顺方法，但是这些方法都存在着不足。如果型值点是准确的，那么采用修改坏点的方法会人为破坏原本正确的型值点；在工程应用当中，NURBS曲线插值的型值点往往都没有权因子，因此，通过修改权因子来调整NURBS曲线的形状并不能得到广泛的应用；通过实验证明，调整节点向量并不是解决曲线反曲率问题最有效的方法。For the NURBS curve generated by interpolation, the curvature reversal often occurs at the place where the denser type points transition to the sparser type point, resulting in the phenomenon that the curve is not smooth. At present, for the non-smoothness of the NURBS interpolation curve, there are mainly smoothing methods such as modifying bad points, adjusting weight factors and adjusting node vectors, but these methods all have shortcomings. If the value points are accurate, then the method of modifying bad points will artificially destroy the original correct value points; in engineering applications, the value points of NURBS curve interpolation often do not have weight factors, so by modifying the weight factors to Adjusting the shape of NURBS curves is not widely used; it has been proved by experiments that adjusting the node vectors is not the most effective way to solve the problem of curve inflection.

文献“基于遗传算法的曲线光顺的研究，中国机械工程第13卷，第13期，2002年2月上半月”公开了一种基于遗传算法的曲线光顺方法。该方法在传统光顺的基础上，提出了以曲线曲率极值的方差作为衡量曲线光顺的标准之一，引入遗传算法和模糊数学控制机制。该方法主要研究在光栅矢量化后的光顺问题，具有一定的局限性，另外在数据点较多的情况下，利用曲线曲率极值方差的方法，速度较慢。The document "Research on Curve Smoothing Based on Genetic Algorithm, China Mechanical Engineering Volume 13, No. 13, First Half of February, 2002" discloses a method of curve smoothing based on genetic algorithm. On the basis of traditional fairing, this method proposes to take the variance of the extreme value of curve curvature as one of the standards to measure the smoothness of the curve, and introduces genetic algorithm and fuzzy mathematical control mechanism. This method mainly studies the smoothing problem after raster vectorization, and has certain limitations. In addition, when there are many data points, the method of using the extreme variance of the curvature of the curve is slow.

发明内容Contents of the invention

为了克服现有闭合非均匀有理B样条曲线光顺方法速度慢的不足，本发明提供一种基于遗传算法的闭合非均匀有理B样条曲线光顺方法。该方法通过在出现反曲率的两个型值点之间增加型值点重新进行曲线插值，新增型值点的位置采用遗传算法在光顺准则的约束下确定，进而调整曲线的形状使其光顺。该方法使重新插值的曲线不仅严格通过原始型值点，并且解决了原先曲线出现的反曲率问题，比背景技术公开的的曲线更加光顺。同时有效的解决了后缘与叶背和叶盆的拼接处的封闭截面线出现凹坑的现象，使得叶片截面线更为光顺，并且该方法适用于多种三维CAD软件平台，从而有效弥补了现有NURBS曲线插值研究的不足，而且速度快。In order to overcome the disadvantage of slow speed of the existing closed non-uniform rational B-spline curve smoothing method, the invention provides a closed non-uniform rational B-spline curve smoothing method based on genetic algorithm. In this method, curve interpolation is re-interpolated by adding value points between two value points with inverse curvature. The position of the new value points is determined by the genetic algorithm under the constraints of the fairness criterion, and then the shape of the curve is adjusted to make it smooth. The method not only makes the re-interpolated curve strictly pass through the original type value points, but also solves the problem of inverse curvature of the original curve, and is smoother than the curve disclosed in the background technology. At the same time, it effectively solves the phenomenon of pits on the closed section line at the junction of the trailing edge, the back of the leaf and the leaf pot, making the section line of the blade smoother, and this method is applicable to a variety of 3D CAD software platforms, thus effectively making up for It solves the shortcomings of the existing NURBS curve interpolation research, and the speed is fast.

本发明解决其技术问题所采用的技术方案：一种基于遗传算法的闭合非均匀有理B样条曲线光顺方法，其特点是包括以下步骤：The technical solution adopted by the present invention to solve its technical problems: a method for smoothing closed non-uniform rational B-spline curves based on genetic algorithm, which is characterized in that it includes the following steps:

步骤一、确定闭合NURBS曲线插值方法，采用三次闭合NURBS曲线进行插值。设有m+1个型值点q₀,q₁,q₂,...q_m,且q₀＝q_m，取型值点为曲线内部分段连接点，即q_i有节点值u_i+3。该NURBS曲线由n+1个控制顶点d₀，d₁，d₂，....d_n和节点向量U＝[u₀,u₁,...,u_n+4]来定义，定义域为u∈[u₃,u_n+1]＝[0,1]。其中n＝m+2，共有m+3个未知控制顶点。Step 1. Determine the closed NURBS curve interpolation method, and use the cubic closed NURBS curve for interpolation. Assuming m+1 type-value points q ₀ , q ₁ ,q ₂ ,...q _m , and q ₀ =q _m , the type-value points are taken as the segment connection points inside the curve, that is, q _i has node value u _i+3 . The NURBS curve is defined by n+1 control vertices d ₀ , d ₁ , d ₂ , ... d _n and node vector U=[u ₀ ,u ₁ ,...,u _n+4 ], defined The domain is u∈[u ₃ ,u _n+1 ]=[0,1]. Where n=m+2, there are m+3 unknown control vertices in total.

1.1采用累积弦长的方法,计算出参数值序列t₀,t₁,t₂,...t_m，定义域内节点值为u₃＝t₀,u₄＝t₁,u₅＝t₂,...u_m＝u_m+3，定义域外的节点确定为u₀＝u_n-2-1，u₁＝u_n-1-1，u₂＝u_n-1，u_n+2＝u₄+1，u_n+3＝u₅+1，u_n+4＝u₆+1。1.1 Using the cumulative chord length method, calculate the parameter value sequence t ₀ , t ₁ , t ₂ ,...t _m , and the node values in the domain of definition are u ₃ =t ₀ , u ₄ =t ₁ , u ₅ =t ₂ ,... u _m ＝u _m+3 , the nodes outside the domain are defined as u ₀ ＝u _n-2 -1, u ₁ ＝u _n-1 -1, u ₂ ＝u _n -1, u _n+2 =u ₄ +1, u _n+3 =u ₅ +1, u _n+4 =u ₆ +1.

1.2反用于插值m+1个型值点q₀,q₁,q₂,...q_m且q₀＝q_m的三次闭合NURBS曲线方程表示为1.2 The reverse is used to interpolate m+1 value points q ₀ , q ₁ , q ₂ ,...q _m and the cubic closed NURBS curve equation of q ₀ =q _m is expressed as

$p p ((u u)) = = {Σ Σ}_{j j = = 00}^{n no} {d d}_{j j} {R R}_{j j,, 33} ((u u)) = = {Σ Σ}_{j j = = i i - - 33}^{i i} {d d}_{j j} {R R}_{j j,, 33} ((u u)),, u u &Element; &Element; [[{u u}_{i i},, {u u}_{i i + + 11}]] &Subset; &Subset; [[{u u}_{33},, {u u}_{n no + + 11}]],,$

其中， $R_{i, 3} (u) = \frac{w_{j} N_{j, k} (u)}{Σ_{j = 0}^{n} w_{j} N_{j, k} (u)}$ 为三次有理基函数。in, $R_{i, 3} (u) = \frac{w_{j} N_{j, k} (u)}{Σ_{j = 0}^{no} w_{j} N_{j, k} (u)}$ is a cubic rational basis function.

将曲线定义域

内的节点值代入方程，满足插值条件，即Define the domain of the curve

Substituting the node values in the equation to meet the interpolation conditions, that is

$p p (({u u}_{i i})) = = {Σ Σ}_{j j = = i i - - 33}^{i i} {d d}_{j j} {R R}_{j j,, 33} (({u u}_{i i})) = = {q q}_{i i - - 33},, i i = = 3,4 3,4,, \cdot \cdot \cdot \cdot \cdot \cdot,, n no$

上式共含n-2个方程。首末三个控制顶点重合d_n-2＝d₀，d_n-1＝d₁，d_n＝d₂，未知控制顶点个数减少为n-2。从由n-2个方程构成的线性方程组用追赶法求解n-2个未知控制顶点。The above formula contains n-2 equations in total. The first and last three control vertices overlap d _n-2 =d ₀ , d _n-1 =d ₁ , d _n =d ₂ , and the number of unknown control vertices is reduced to n-2. The pursuit method is used to solve n-2 unknown control vertices from a linear equation system composed of n-2 equations.

1.3在求解控制顶点d_i之前，需得到d_i对应的权因子w_i，i＝0,1,...，n。若已知各型值点q_i的权因子

i＝0,1,...，m，则1.3 Before solving the control vertex d _i , it is necessary to obtain the weight factor w _i corresponding to d _i , i=0,1,...,n. If the weight factor of each value point q _i is known

i=0,1,...,m, then

$\{\begin{matrix} {Σ Σ}_{j j = = i i - - 33}^{i i} {w w}_{j j} {R R}_{j j,, 33} (({u u}_{i i})) = = \overset{&OverBar; &OverBar;}{{w w}_{i i - - 33}},, i i = = 3,4 3,4,, . . . . . .,, n no \\ {w w}_{n no - - 22} = = {w w}_{00},, {w w}_{n no - - 11} = = {w w}_{11},, {w w}_{n no} = = {w w}_{22} \end{matrix}$

联立上述方程组，求出控制顶点d_i的权因子w_i。Simultaneously combine the above equations to obtain the weight factor w _i of the control vertex d _i .

步骤二、确定点q_k和点q_k+1，其中在q_k和q_k+1两个型值点之间出现反曲率不光顺。Step 2: Determine point q _k and point q _k+1 , where inverse curvature is not smooth between the two type-value points q _k and q _k+1 .

步骤三、采用遗传算法计算点q_k和点q_k+1之间的新增型值点的位置。Step 3: Using the genetic algorithm to calculate the position of the new value point between point q _k and point q _k+1 .

3.1假设在q_k和q_k+1两个型值点之间出现反曲率不光顺，其中q_k和q_k+1是手动选择的。

是q_k(x_k,y_k)和q_k+1(x_k+1,y_k+1)之间新增加的型值点，Δx是q_k+0.5(x_k+0.5,y_k+0.5)沿

方向的偏置值，Δy是垂直于方向上的偏置值。经过计算，得到：3.1 Assume that the inverse curvature is not smooth between the two type value points q _k and q _k+1 , where q _k and q _k+1 are manually selected.

is a newly added value point between q _k (x _k ,y _k ) and q _k+1 (x _k+1 ,y _k+1 ), and Δx is q _k+0.5 (x _k+0.5 ,y _{k+ 0.5} ) along

Orientation bias value, Δy is perpendicular to The offset value in the direction. After calculation, get:

$\{\begin{matrix} {x x}_{k k + + 0.5 0.5} = = {x x}_{k k} + + Δx Δx \cdot &Center Dot; cos cos θ θ + + Δy Δy \cdot &Center Dot; cos cos η η \\ {y the y}_{k k + + 0.5 0.5} = = {y the y}_{k k} + + Δx Δx \cdot \cdot sin sin θ θ + + Δy Δy \cdot &Center Dot; sin sin η η \end{matrix}$

其中， $θ = \arctan \frac{y_{k + 1} - y_{k}}{x_{k + 1} - x_{k}},$ $η = \arctan (- \frac{x_{k + 1} - x_{k}}{y_{k + 1} - y_{k}}),$ $0 < Δx < | \overset{&RightArrow;}{q_{k} q_{k + 1}} | .$ in, $θ = \arctan \frac{{the y}_{k + 1} - {the y}_{k}}{x_{k + 1} - x_{k}},$ $η = \arctan (- \frac{x_{k + 1} - x_{k}}{{the y}_{k + 1} - {the y}_{k}}),$ $0 < Δx < | \overset{&Right Arrow;}{q_{k} q_{k + 1}} | .$

计算出Δx和Δy，获取新增型值点q_k+0.5(x_k+0.5,y_k+0.5)，因此，Δx和Δy作为遗传算法染色体上的两个基因。Calculate Δx and Δy, and obtain the new type value point q _k+0.5 (x _k+0.5 , y _k+0.5 ), therefore, Δx and Δy are regarded as two genes on the chromosome of the genetic algorithm.

3.2曲线的能量定义为E＝∫k²ds，其中k为曲率，s为弧长；定义一个变量Q表示曲率变化的最大值，

曲线光顺的目标函数为min(f)，其中f＝α·E+β·Q，α是曲线应变能变化值的权因子，β是曲线最大曲率变化值的权因子，α+β＝1。3.2 The energy of the curve is defined as E=∫k ² ds, where k is the curvature and s is the arc length; define a variable Q to represent the maximum value of the curvature change,

The objective function of curve smoothing is min(f), where f=α·E+β·Q, α is the weight factor of the change value of the strain energy of the curve, β is the weight factor of the maximum curvature change value of the curve, α+β=1 .

曲线光顺的目标函数为min(f(Δx,Δy))；适应度确定为

其中

Δx和Δy为染色体上的两个基因。The objective function of curve smoothing is min(f(Δx,Δy)); the fitness is determined as

in

Δx and Δy are two genes on the chromosome.

3.3采用编码方式为浮点数编码，染色体上的两个基因Δx和Δy分别保留小数点后三位；种群的规模大小为10，初始种群每个个体随机产生。3.3 The encoding method is floating-point encoding, and the two genes Δx and Δy on the chromosome respectively retain three decimal places; the size of the population is 10, and each individual of the initial population is randomly generated.

3.4遗传算子包括选择、交叉和变异。选择方法采用轮盘赌注法；交叉方法采用单点交叉，交叉点随机产生；变异方法采用高斯变异法。3.4 Genetic operators include selection, crossover and mutation. The selection method adopts roulette method; the crossover method adopts single-point crossover, and the crossover point is randomly generated; the variation method adopts Gaussian variation method.

3.5启动遗传算法，计算出新增型值点的位置。3.5 Start the genetic algorithm to calculate the position of the new value point.

步骤四、通过原始型值点和新增型值点，插值出新的NURBS曲线。Step 4: Interpolate a new NURBS curve through the original type value points and the new type value points.

步骤五、若曲线还存在反曲率，则跳转到步骤二，再次对曲线进行光顺；若曲线已满足光顺要求，则输出当前插值曲线作为最终结果。Step 5. If the curve still has inverse curvature, jump to step 2 and smooth the curve again; if the curve meets the smoothing requirements, output the current interpolation curve as the final result.

所述曲线应变能变化值的权因子α＝0.7。The weight factor α=0.7 of the curve strain energy change value.

所述曲线最大曲率变化值的权因子β＝0.3。The weight factor β of the maximum curvature change value of the curve is 0.3.

本发明的有益效果是：由于该方法通过在出现反曲率的两个型值点之间增加型值点重新进行曲线插值，新增型值点的位置采用遗传算法在光顺准则的约束下确定，进而调整曲线的形状使其光顺。该方法使重新插值的曲线不仅严格通过原始型值点，并且解决了原先曲线出现的反曲率问题，比背景技术公开的的曲线更加光顺。同时有效的解决了后缘与叶背和叶盆的拼接处的封闭截面线出现凹坑的现象，使得叶片截面线更为光顺，并且该方法适用于多种三维CAD软件平台，从而有效弥补了现有NURBS曲线插值研究的不足，而且提高了光顺速度。The beneficial effects of the present invention are: because the method re-performs curve interpolation by adding value points between two value points where inflection occurs, the position of the new value point is determined under the constraints of the fairness criterion using a genetic algorithm , and then adjust the shape of the curve to make it smooth. The method not only makes the re-interpolated curve strictly pass through the original value points, but also solves the problem of inverse curvature of the original curve, and is smoother than the curve disclosed in the background technology. At the same time, it effectively solves the phenomenon of pits on the closed section line at the junction of the trailing edge, the back of the leaf and the leaf pot, making the section line of the blade smoother, and this method is applicable to a variety of 3D CAD software platforms, thus effectively making up for It solves the shortcomings of the existing NURBS curve interpolation research, and improves the smoothing speed.

下面结合附图和实施例对本发明作详细说明。The present invention will be described in detail below in conjunction with the accompanying drawings and embodiments.

附图说明Description of drawings

图1是新增型值点示意图。Figure 1 is a schematic diagram of the newly added value points.

图2是叶身截面线数据点的示意图。Fig. 2 is a schematic diagram of the data points of the airfoil section line.

图3是叶身截面尾缘部分数据点的局部放大图。Figure 3 is a partial enlarged view of the data points on the trailing edge of the blade body section.

图4是通过叶身截面线数据点构造的初始叶身截面线。Fig. 4 is the initial airfoil section line constructed by the data points of the airfoil section line.

图5是叶身截面线出现反曲率处的曲率梳。Figure 5 is the curvature comb where the inverse curvature appears on the section line of the blade body.

图6是叶身截面线出现反曲率处的型值点示意图，其中在型值点p₁和p₂之间出现反曲率不光顺，在型值点q₁和q₂之间出现反曲率不光顺。Fig. 6 is a schematic diagram of the shape points where the inflection occurs on the section line of the blade body, where the inversion is not smooth between the shape points _p1 and _p2 , and the inflection is not smooth between the shape points _q1 and _q2 Shun.

图7是光顺后的叶身截面线示意图。Fig. 7 is a schematic diagram of the section line of the blade body after smoothing.

图8是曲线光顺后的曲率梳。Figure 8 is the curvature comb after curve smoothing.

具体实施方式Detailed ways

参照图1-8，以某型叶片的叶身截面线插值为例，以VisualStudio2010为开发工具，在设计软件NX7.5平台上利用NXOpen API开发实现详细说明本发明。Referring to Figures 1-8, taking the blade body section line interpolation of a certain type of blade as an example, using VisualStudio2010 as a development tool, using NXOpen API to develop and realize the present invention in detail on the design software NX7.5 platform.

步骤1：确定闭合NURBS曲线插值方法，采用三次闭合NURBS曲线进行插值。设有m+1个型值点q₀,q₁,q₂,...q_m,且q₀＝q_m，取型值点为曲线内部分段连接点，即q_i有节点值u_i+3。该NURBS曲线由n+1个控制顶点d₀，d₁，d₂，....d_n和节点向量U＝[u₀,u₁,...,u_n+4]来定义，定义域为u∈[u₃,u_n+1]＝[0,1]。其中n＝m+2，即控制顶点的数目比型值点数目多2个，共有m+3个未知控制顶点。Step 1: Determine the closed NURBS curve interpolation method, and use the cubic closed NURBS curve for interpolation. Assuming m+1 type-value points q ₀ , q ₁ ,q ₂ ,...q _m , and q ₀ =q _m , the type-value points are taken as the segment connection points inside the curve, that is, q _i has node value u _i+3 . The NURBS curve is defined by n+1 control vertices d ₀ , d ₁ , d ₂ , ... d _n and node vector U=[u ₀ ,u ₁ ,...,u _n+4 ], defined The domain is u∈[u ₃ ,u _n+1 ]=[0,1]. Where n=m+2, that is, the number of control vertices is 2 more than the number of type value points, and there are m+3 unknown control vertices in total.

1.1确定节点矢量。采用累积弦长的方法,计算出参数值序列t₀,t₁,t₂,...t_m，定义域内节点值为u₃＝t₀,u₄＝t₁,u₅＝t₂,...u_m＝u_m+3，定义域外的节点确定为u₀＝u_n-2-1，u₁＝u_n-1-1，u₂＝u_n-1，u_n+2＝u₄+1，u_n+3＝u₅+1，u_n+4＝u₆+1。1.1 Determine the node vector. Using the method of accumulative chord length, the parameter value sequence t ₀ , t ₁ , t ₂ ,...t _m is calculated, and the node values in the definition domain are u ₃ =t ₀ , u ₄ =t ₁ , u ₅ =t ₂ , ...u _m ＝u _m+3 , the nodes outside the domain are determined as u ₀ ＝u _n-2 -1, u ₁ ＝u _n-1 -1, u ₂ ＝u _n -1, u _n+2 ＝ u ₄ +1, u _n+3 = u ₅ +1, u _n+4 = u ₆ +1.

1.2反算控制顶点。用于插值m+1个型值点q₀,q₁,q₂,...q_m且q₀＝q_m的三次闭合NURBS曲线方程表示为1.2 Inverse calculation control vertices. The cubic closed NURBS curve equation for interpolating m+1 type-valued points q ₀ , q ₁ , q ₂ ,...q _m and q ₀ =q _m is expressed as

其中 $R_{i, 3} (u) = \frac{w_{j} N_{j, k} (u)}{Σ_{j = 0}^{n} w_{j} N_{j, k} (u)}$ 为三次有理基函数。in $R_{i, 3} (u) = \frac{w_{j} N_{j, k} (u)}{Σ_{j = 0}^{no} w_{j} N_{j, k} (u)}$ is a cubic rational basis function.

将曲线定义域

$p p (({u u}_{i i})) = = {Σ Σ}_{j j = = i i - - 33}^{i i} {d d}_{j j} {R R}_{j j,, 33} (({u u}_{i i})) = = {q q}_{i i - - 33},, i i = = 3,4 3,4,, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, n no$

1.3确定控制顶点权因子。在求解控制顶点d_i之前，需得到d_i对应的权因子w_i，i＝0,1,...，n。若已知各型值点q_i的权因子

i＝0,1,...，m，则1.3 Determine the control vertex weight factor. Before solving the control vertex d _i , it is necessary to obtain the weight factor w _i corresponding to d _i , i=0,1,...,n. If the weight factor of each value point q _i is known

i=0,1,...,m, then

步骤2：自行确定点q_k和点q_k+1，其中在q_k和q_k+1两个型值点之间出现反曲率不光顺。Step 2: Determine the point q _k and point q _k+1 by yourself, where the inverse curvature is not smooth between the two type value points q _k and q _k+1 .

步骤3：采用遗传算法计算点q_k和点q_k+1之间的新增型值点的位置。Step 3: Use the genetic algorithm to calculate the position of the new value point between point q _k and point q _k+1 .

3.1确定遗传算法的染色体。假设在q_k和q_k+1两个型值点之间出现反曲率不光顺，其中q_k和q_k+1是手动选择的。q_k+0.5(x_k+0.5,_yk+0.5)是q_k(x_k,y_k)和q_k+1(x_k+1,y_k+1)之间新增加的型值点，Δx是q_k+0.5(x_k+0.5,y_k+0.5)沿

方向的偏置值，Δy是垂直于方向上的偏置值。经过计算，得到：3.1 Determine the chromosomes of the genetic algorithm. Assume that inverse curvature is not smooth between two type-value points q _k and q _k+1 , where q _k and q _k+1 are manually selected. q _k+0.5 (x _k+0.5 , _yk+0.5 ) is a newly added value point between q _k (x _k ,y _k ) and q _k+1 (x _k+1 ,y _k+1 ), Δx is q _k+0.5 (x _k+0.5 ,y _k+0.5 ) along

$\{\begin{matrix} {x x}_{k k + + 0.5 0.5} = = {x x}_{k k} + + Δx Δx \cdot &Center Dot; cos cos θ θ + + Δy Δy \cdot &Center Dot; cos cos η η \\ {y the y}_{k k + + 0.5 0.5} = = {y the y}_{k k} + + Δx Δx \cdot &Center Dot; sin sin θ θ + + Δy Δy \cdot &Center Dot; sin sin η η \end{matrix}$

3.2计算遗传算法适应度。一条光顺的曲线一般要满足以下几个条件:曲线二阶几何连续；没有奇点和多余拐点；曲率变化均匀；应变能小。本文综合考虑曲率变化和应变能两个方面，提出一种合理的光顺准则。3.2 Calculation of genetic algorithm fitness. A smooth curve generally meets the following conditions: the second-order geometric continuity of the curve; no singularity and redundant inflection points; uniform curvature change; small strain energy. In this paper, a reasonable fairing criterion is proposed considering the two aspects of curvature change and strain energy.

曲线的能量定义为E＝∫k²ds，其中k为曲率，s为弧长；定义一个变量Q表示曲率变化的最大值，

即将曲线离散为1000个点，利用分析曲线曲率的功能就出E和Q。进而求得曲线光顺的目标函数为min(f)，其中f＝α·E+β·Q，α和β分别为曲线应变能和最大曲率变化值的权因子，本例取α＝0.7和β＝0.3。遗传算法的适应度

fitness = \frac{1}{f (Δx, Δy)} .

The energy of the curve is defined as E=∫k ² ds, where k is the curvature, and s is the arc length; define a variable Q to represent the maximum value of the curvature change,

That is, the curve is discretized into 1000 points, and E and Q can be obtained by using the function of analyzing the curvature of the curve. Furthermore, the objective function of obtaining the smoothness of the curve is min(f), where f=α E+β Q, α and β are respectively the weight factors of the curve strain energy and the maximum curvature change value, and in this example, α=0.7 and β=0.3. Fitness of Genetic Algorithms

fitness = \frac{1}{f (Δx, Δy)} .

遗传算法中，以个体适应度的大小来评价个体的优劣程度，从而决定其遗传机会的大小。曲线光顺的目标函数为min(f(Δx,Δy))，f(Δx,Δy)值越小个体越优秀，因此，适应度确定为

其中

Δx和Δy为染色体上的两个基因。In the genetic algorithm, the degree of individual fitness is evaluated to determine the size of its genetic opportunity. The objective function of curve smoothing is min(f(Δx,Δy)), the smaller the value of f(Δx,Δy), the better the individual, therefore, the fitness is determined as

in

Δx and Δy are two genes on the chromosome.

3.3确定编码及初始种群。采用编码方式为浮点数编码,染色体上的两个基因Δx和Δy分别保留小数点后三位；种群的规模大小为10，即种群由10个个体组成，初始种群每个个体随机产生。3.3 Determine the coding and initial population. The encoding method is floating-point encoding, and the two genes Δx and Δy on the chromosome retain three decimal places respectively; the size of the population is 10, that is, the population consists of 10 individuals, and each individual in the initial population is randomly generated.

3.4确定遗传算子。遗传算子包括选择、交叉和变异。选择方法采用轮盘赌注法；交叉方法采用单点交叉，交叉点随机产生；变异方法采用高斯变异法。3.4 Determine the genetic operator. Genetic operators include selection, crossover, and mutation. The selection method adopts roulette method; the crossover method adopts single-point crossover, and the crossover point is randomly generated; the variation method adopts Gaussian variation method.

利用遗传算法的适应度对种群进行评价。如果满足遗传代数，则结束程序，输出最终曲线；否则，染色体的基因进行选择、交叉和变异的运算，其中选择方法采用轮盘赌注法；交叉方法采用单点交叉，交叉概率Pc取0.8，交叉点随机产生；变异方法采用高斯变异法，变异概率Pm取0.8。The fitness of the genetic algorithm is used to evaluate the population. If the genetic algebra is satisfied, the program is ended and the final curve is output; otherwise, the genes of the chromosome are selected, crossed and mutated, and the selection method adopts the roulette method; The points are randomly generated; the variation method adopts Gaussian variation method, and the variation probability Pm is set to 0.8.

步骤4：通过原始型值点和新增型值点，插值出新的NURBS曲线。Step 4: Interpolate a new NURBS curve through the original type value points and new type value points.

步骤5：若曲线还存在反曲率的地方，则跳转到步骤2，再次对曲线进行光顺；若曲线已满足光顺要求，则输出当前插值曲线作为最终结果。Step 5: If the curve still has inverse curvature, jump to step 2 and smooth the curve again; if the curve meets the smoothing requirements, output the current interpolation curve as the final result.

Claims

1. A closed non-uniform rational B-spline curve fairing method based on a genetic algorithm is characterized by comprising the following steps:

step one, determining a closed NURBS curve interpolation method, and performing interpolation by adopting a three-time closed NURBS curve; is provided with m +1 type value points q₀,q₁,q₂,...q_mAnd q is₀＝q_mThe point of the shape value is the connection point of the segment in the curve, i.e. q_iHas a node value u_i+3(ii) a The NURBS curve consists of n +1 control vertices d₀，d₁，d₂，....d_nAnd node vector U ═ U₀,u₁,...,u_n+4]To define the domain as u e [ u ∈ [ [ u ]₃,u_n+1]＝[0,1](ii) a Wherein n is m +2, and m +3 unknown control vertexes are total;

1.1 calculating parameter value sequence t by cumulative chord length method₀,t₁,t₂,...t_mDefining an intra-domain node value as u₃＝t₀,u₄＝t₁,u₅＝t₂,...u_m＝u_m+3Nodes outside the domain of definition are determined as u₀＝u_n-2-1，u₁＝u_n-1-1，u₂＝u_n-1，u_n+2＝u₄+1，u_n+3＝u₅+1，u_n+4＝u₆+1；

1.2 inverse for interpolating m +1 type value points q₀,q₁,q₂,...q_mAnd q is₀＝q_mThe equation of the three-time closed NURBS curve is expressed as

p (u) = Σ_{j = 0}^{n} d_{j} R_{j, 3} (u) = Σ_{j = i - 3}^{i} d_{j} R_{j, 3} (u), u &Element; {[u}_{i}, u_{i + 1}] &Subset; [u_{3}, u_{n + 1}],

Wherein,

is a cubic rational basis function;

defining a curve into a domain

The node value in the equation is substituted into the equation to satisfy the interpolation condition, i.e.

p (u_{i}) = Σ_{j = i - 3}^{i} d_{j} R_{j, 3} (u_{i}) = q_{i - 3},

i＝3,4,…,n

The above formula contains n-2 equations in total; coincidence of the first and the last three control vertexes d_n-2＝d₀，d_n-1＝d₁，d_n＝d₂The number of unknown control vertexes is reduced to n-2; solving n-2 unknown control vertexes by a catch-up method from a linear equation set consisting of n-2 equations;

1.3 solving for control vertex d_iBefore, d is obtained_iCorresponding weight factor w_iIf the value of each type q is known, i is 0,1, …, n_iWeight factor of

I is 0,1, …, m, then

\{\begin{matrix} Σ_{j = i - 3}^{i} w_{j} R_{j, 3} (u_{i}) = \overset{&OverBar;}{w_{i - 3}}, i = 3,4, . . ., n \\ w_{n - 2} = w_{0}, w_{n - 1} = w_{1}, w_{n} = w_{2} \end{matrix}

Simultaneously establishing the above equation set to obtain the control vertex d_iWeight factor w of_i；

Step two, determining a point q_kAnd point q_k+1Wherein at q_kAnd q is_k+1The two model points have inverse curvature and incompliance;

step three, calculating a point q by adopting a genetic algorithm_kAnd point q_k+1The position of the new addition value point;

3.1 suppose that q is_kAnd q is_k+1Between two type value points, there appears inverse curvature irregularity, where q_kAnd q is_k+1Is manually selected; q. q.s_k+0.5(x_k+0.5,y_k+0.5) Is q_k(x_k,y_k) And q is_k+1(x_k+1,y_k+1) A new type value point therebetween, Δ x is q_k+0.5(x_k+0.5,y_k+0.5) Edge of

Bias value of direction, Δ y, perpendicular to

A bias value in a direction; through calculation, the following results are obtained:

\{\begin{matrix} x_{k + 0.5} = x_{k} + Δx \cdot \cos θ + Δy \cdot \cos η \\ y_{k + 0.5} = y_{k} + Δx \cdot \sin θ + Δy \cdot \sin η \end{matrix}

wherein,

θ = \arctan \frac{y_{k + 1} - y_{k}}{x_{k + 1} - x_{k}},

η = \arctan (- \frac{x_{k + 1} - x_{k}}{y_{k + 1} - y_{k}}),

0 < Δx < | \overset{&RightArrow;}{q_{k} q_{k + 1}} |;

calculating delta x and delta y to obtain a newly added value point q_k+0.5(x_k+0.5,y_k+0.5) Thus, Δ x and Δ y act as two genes on the chromosome of the genetic algorithm;

the energy of the 3.2 curve is defined as E ═ k-²ds, where k is the curvature and s is the arc length; a variable Q is defined representing the maximum value of the curvature change,

the target function of the curve fairing is min (f), wherein f is alpha.E + beta.Q, alpha is a weight factor of the change value of the strain energy of the curve, beta is a weight factor of the maximum curvature change value of the curve, and alpha + beta is 1;

the objective function of the curve fairing is min (f (Δ x, Δ y)); the fitness is determined as

Wherein

Δ x and Δ y are two genes on the chromosome;

3.3, encoding the two genes delta x and delta y on the chromosome by adopting an encoding mode as floating point numbers, and respectively reserving three bits after decimal point; the size of the population is 10, and each individual of the initial population is randomly generated;

3.4 genetic operators including selection, crossover and mutation; the selection method adopts a roulette method; the crossing method adopts single-point crossing, and crossing points are randomly generated; the mutation method adopts a Gaussian mutation method;

3.5 starting a genetic algorithm to calculate the position of the new incremental value point;

step four, interpolating a new NURBS curve through the original model value points and the newly added model value points;

if the curve has reverse curvature, jumping to the second step, and smoothing the curve again; and if the curve meets the fairing requirement, outputting the current interpolation curve as a final result.

2. The closed non-uniform rational B-spline curve fairing method based on genetic algorithm as recited in claim 1, characterized in that: the weight factor alpha of the strain energy change value of the curve is 0.7.

3. The closed non-uniform rational B-spline curve fairing method based on genetic algorithm as recited in claim 1, characterized in that: the weight factor beta of the maximum curvature change value of the curve is 0.3.