B样条曲线的光顺设计毕业论文

1、沪j、学本科生毕业论文（设计）文献综述和开题报告题目b样条曲线的光顺设计姓名与学号指导教师 年级与专业数学与应用数学浙江大学本科th毕业论文（设计诚信承诺书1.本人郑重地承诺所呈交的毕业论文（设计），是在指导教师的 指导下严格按照学校和学院有关规定完成的。2本人在毕业论文（设计）中引用他人的观点和参考资料均加 以注释和说明。3. 本人承诺在毕业论文（设计）选题和研究内容过程中没有抄 袭他人研究成果和伪造相关数据等行为。4. 在毕业论文（设计）中对侵犯任何方面知识产权的行为，由 本人承担相应的法律责任。毕业论文（设计）作者签名：年月h、毕业论文、文献综述-、开题报告四、外文翻译中文摘要在工业生产

2、几何设计中，人们大量应用b样条等数学工具来设计曲线。在 许多工业设计领域，比如造船业、汽车制造业等，设计师要求曲线要十分光顺, 因为曲线的光顺性会直接影响生成曲面的质量。在木文中，我们先对光顺的判 别准则进行讨论，结合实际牛产经验以得出更符合实际牛产需要的光顺判别准 则。基于所得的判别准则，使用l0/l1范数优化等理论给出目标函数，建立数 学模型。然后我们进行大量实验，证明该模型的有效性。关键词：b样条曲线光顺i范数l0范数压缩感知船体放样abstractb-spline are a modeling tool widely used in industrial geometric desig

3、n. in many industrial design activities, curves need to be fair enough. the fairness of curves has a direct influence on the quality of the underlying surface in this paper, we first discuss about the criterion of fairness, and then we present a reasonable criterion of fairness by considering the ex

4、perience of actual production. according to the new criterion of fairness, we present a mathematical model by using the theories about lo/ll-norm optimization. we carry out large number of experiments which show that our solution is efficient.key words: b-spline, fairness, li-norm, lo-norm, hull lof

5、ting目录1引言11.1研究的目的和意义11.2研究的问题和框架12背景介绍与相关工作22.1两种通用光顺判别准则2211 光顺判别准则cl （n. sapidis等）2212 光顺判别准则c2 （苏步青等）22. 2整体能量优化法32. 3 局部修改方法33光顺的判别准则（董光昌）33. 1实例分析与光顺判别准则c33311 典型的非光顺曲线实例3312 光顺判别准则c353.2函数样条的光顺算法简介5321 回弹法5322 直尺卡样法6323 曲尺卡样法7324 一般曲线的光顺设计算法83. 3实验结果示例93.4算法的局限性94基于l1范数优化的光顺算法104. 1向量c与向量e104

6、.2数学模型的构建10421 光顺判别准则c3与优化目标11422 曲线的拐点数与c的l0范数11423 曲线的拐点数与e的l0范数14424 曲线的拐点数与e的l2范数14425 基于l1范数的优化目标164.3实证结果分析16431 c的l2范数与c的l1范数16432 e的l2范数与c的l1范数204.4数学模型的优化215实验结果216结束语24参考文献24附录（matlab相关代码）261引言在工业生产几何设计中，“光顺”是设计师们十分关心的概念。如在造船行业中， 船体若不够光顺，那么船在航行时会受到更大的阻力，也更容易被海水腐蚀，极大降 低船体寿命。随着技术发展，b样条、nurbs

7、曲线/曲面等在生产设计屮发挥了巨大 作用；人们也越来越关心如何对着这些数字曲线进行光顺。1.1研究的目的和意义在工业生产中，为了追求生成曲面或曲线具有更良好的物理特性或其他特性，往 往要求曲面或曲线具有光顺性。例如，在造船业中，若船的水线、站线等足够光顺， 能够减少船行驶遇到的阻力，且能够延长船体使用年限。在实际的工业生产中，光顺设计一一即将己有曲线变得更光顺是十分重要的步 骤。而往往只有经验丰富的设计师或者工人才能将曲线光顺好。设计师和工人们对已 有的光顺准则并不满意，认为只有靠经验才能解决光顺的问题。我们希望结合实际生 产的经验，总结出更合理的光顺判别准则，建立数学模型，最终能应用到实际生

8、产中 去。由于设计师和工人们对已有的光顺准则并不认可，所以fi前的光顺方法并不信 任。因此，光顺设计往往是依靠人力来完成。如果要光顺一个较大的模型，比如船体 上的全部水线、站线、横剖线，一般需要三个星期左右的时间。所以，我们希望利用 计算机进行辅助设计，找到一种合理的算法对曲线进行光顺，减少设计师与工人的工 作量。b样条曲线被大量应用于工业生产设计，我们将针对b样条曲线的光顺进行讨论, 并找到有效的办法对b样条曲线进行光顺。论文开题的目的和意义，即研究出更符合实际生产需求的光顺判别准则与基于该 准则的曲线光顺设计算法，以解决实际生产中的问题，并将光顺的概念数学规范化。1.2研究的问题与框架在造

9、船业中，放样工人们会得到一系列的插值点，他们的工作是求得光顺的曲线 来通过这些插值点。传统的放样中，一般是先在地板上画岀这些插值点(也叫型值点) 的位置，然后用细木条依次通过这些插值点。放样工人们通过肉眼来判断这些细木条 是否光顺，如果不够光顺，在通过调整插值点的位置来达到光顺的效果。我们研究的问题是：给定了一个点列pg,)") ,我们需求的新的点列a(x/, >7),其与只的距离不超过预先给定的容差值，使得我们用b样条或者nurbs 等曲线对其进行插值，所得到的曲线是光顺曲线。因此我们称之为光顺设计。我们在第2章，会介绍该问题的背景以及相关的工作。给出了两种通用的判别准 则，

10、以及基于这两种判别准则的相关算法。在第3章，我们会介绍董光昌先生对光顺的研究成果。我们的研究主要受到了董 先生的启发，我们的算法是基于他给岀的光顺判别准则。在第4章，我们将依照董光昌先生给出的光顺判别准则，使用l0范数与l1范 数对其建模，从而得到我们的光顺算法。在第5章，则是实验结果与分析。2背景介绍与相关工作2.1两种通用光顺判别准则曲线“光顺”的概念主要来源于实际的生产，并没有一个明确的数学定义。现在 普遍使用曲线光顺的判别准则有两种，分別由gfarin等1,与苏步青等人提出。2.1.1光顺的判别准则cl (g.farin等gfarin等人认为，曲线的光顺应该满足以下条件：(1) 曲线f

11、eg2 ,即曲线至少有2阶或2阶以上的几何连续性；(2) ,在满足一定的容差约束条件下。2.1.2光顺的判别准则c2 (苏步青等苏步青等人认为，曲线的光顺应该满足以下条件：(1) 曲线于wg2 ,即曲线至少有2阶或2阶以上的几何连续性；(2) 曲线f的拐点少；(3) 曲线f的曲率变化均匀。两种不同的判别准则都被广泛使用。基于不同的光顺判别准则，可以将现有的光 顺算法分为两类：整体能量优化法与局部调整法。2.2整体能量优化法整体能量优化法是基于判别准则c1的能量优化方法，主要有应变能法、最小二 乘法和小波法。应变能法即在满足一定的容差约束条件下，使应变能一一曲率平方的积分极小， 即判别准则c1的

12、直接建模。最小二乘法则是在满足一定的容差约束条件下，插值点（或控制点）处的曲率平 方z和求极小，即对判别准则c1的离散建模。小波法则是将曲线用小波进行分解，然后去除细节部分的小波。2.2局部修改方法局部修改方法主要基于光顺的判别准则c2o kjellander2的工作给岀了均匀参数 三次b样条的光顺方法。该方法的基本思想是曲线的几何外形在大多数型值点处是光 顺或比较光顺的，只是在少数型值点处非光顺，逐次找出这些非光顺的点即“坏点”, 修改这些“坏点”，使曲线达到光顺的要求。之后许多有许多人在发展了 kjellander 的这套方法。g.farin在kjellander方法的基础上，给出了一种节

13、点去除法。它是将一 部分坏点取出后，重新计算b样条的控制顶点以实现曲线光顺。n. sapidis与g.farin|6结合以上两种技巧，用曲率线图的方式找到引起非光顺的 “坏点”，每次对最“坏”的点进行处理，或者修改其位置，或者删除该点，或者在 附近增加辅助控制点，使其局部的拐点减少口曲率变得均匀。整体能量优化法由于往往不考虑将曲率变均匀，或者去除拐点，它并不被工人们 所接受；而局部修改方法的缺点在于每次仅处理一点，运行效率慢，且没有考虑整体, 因此，这些光顺方法始终没有解决工人们的实际需求。3光顺的判别准则（董光昌）3.1实例分析与光顺的判别准则c33.1.1典型的非光顺曲线实例董光昌先生曾经

14、在船厂从事数学放样的工作，他将所有非光顺的曲线总结为三 类，并得到具有丰富光顺经验的工人们的认可。第一类非光顺曲线：曲线拐点较多。即使对没有光顺经验的的人来说，看到曲线 凹凸不平，也会认为该曲线并不光顺。根据拐点的定义，曲线通过拐点将改变曲线的 凹凸性，因此造成凹凸不平的原因是曲线的拐点较多。如sinx ,它属于c",即无 穷阶光滑，但是应该不是光顺曲线。第二类非光顺曲线：曲率线的拐点较多。对于曲线/ = 0.5x2+sinx，易得该曲线 没有拐点，其仍然令人直观上觉得不够“光顺”，它像一条蛇一样缠绕着0.5甘。这 是因为其曲率线的拐点较多。曲率为当参数为弧长参数时的二阶导数，对于一

15、般参数， 曲率（1+严）亍当广绝对值较小时，可以用一般二阶导数近似曲率值。图2红色线表示/ = 0.5f+sin 蓝色线为0.5+第三类非光顺曲线：曲率的变化幅度大。如图中的圆弧曲线，在x=0左边，其为 半径为1的圆，在x=0右边，为半径为5的圆。由于其曲率变化幅度较大，让感觉左 边部分较“鼓”，右边部分较“瘪”，不够光顺。图3鼓瘪段实例3.1.2光顺的判别准则c3根据实例所示的非光顺曲线，为避免这些非光顺情形，董光昌先生给出了新的光 顺判别准则。判别准则c1与判别准则c2都将曲线限定了至少2阶的几何连续性， 这样在工业设计中常用的圆弧曲线就无法满足其要求。我们可以仅仅要求曲线有1 + 6阶的

16、几何连续性，6>0o光顺的判别准则c3：在满足一定的约束条件小，(1) 曲线 fe ,/>0；(2) 曲线f的拐点少；(3) 曲线f的曲率线的拐点少；(4) 曲率/的曲率线变化幅度小。其中，我们称曲线/的拐点为第一振动数，曲线/的曲率线的拐点为第二振动数。 第一振动数比第二振动数与曲率线的变化幅度要重要得多，因为第一振动数说明了曲 线本身发生了质变。因此，减少曲线本身的拐点数应该是我们的第一目标。在下文中，我们用向量c来表示插值点(或控制顶点)处的曲率构成的向量， 用向量e来表示曲率线的曲率构成的向量。如果c或者e不存在，那么用有限差分 等方法对其近似替代。3.2函数样条的光顺方法

17、简介基于以上的判别准则，董光昌先生等人以函数样条为主要对象，得出一种十分有 效的光顺算法。这个算法又由回弹法、直尺卡样法与曲尺卡样法构成912。我们的 主要工作受到了董先生这套方法的启发，因此，我们在此简单地介绍回弹法、直尺卡样法和曲尺卡样法。321回弹法由公式(1)可知，当曲线的一阶导数绝对值较小时，其曲率可以近似为其二阶 导数。令pig卩)心1,斤表示插值点向量hr+i (z=2,.n-l )分别与向量 popi构成拐角比,cr=maxa称作这-亠系列点的最大拐角。当最大拐角不超过120 度时，三次函数样条的曲率与其二阶导数十分接近，可以互相替代。而三次函数样条的二阶导数可以用追赶法得到，

18、从而得到插值点处的二阶导数gt a +1 一 a(/ = l.n 人 与 & = (i = 2.n )。xi+ i 一 xi回弹法的过程如下：(1) 初始化i二1 ,转(2)；(2) 如果etet+1 <0，转(3)；否则转(5)；(3) 求得最小的5 ,使qq+i =0成立，其中云为y/+ 8i代入后的重新计算 所得的值，转(4)；(4) j = min(&0.55), §为预设的最大偏移量。更新y =，转(5);(5) 如果i<n-l i二i+1,转(2)；否则结束。322直尺卡样法直尺卡样法的目的是减少多余的拐点，其分为三种应对不同情况的过程。其过程

19、 一如下：(1) 初始化2 2 ,转(2)；(2) 如果 ci-1 ci <= 0 且 cici+ 1 <=0 ,转(3);否则转(5);(3) 求得最小的5,使2 = 0成立，其中&为h+次 代入后的重新计算所得的值,转(4)；(4) 5 = min(§,5), f为预设的最大偏移量。更新刃=卩+5，转(5);(5) 如果i<n-l, i二i+1,转(2)；否则结束。其过程二如下：(1) 初始化心2 ,转(2)；(2) 如果ci-ia< 0> aa+i> 0且a+ia+2v0 ,转(3)；否则转(5)；(3) 求得最小的5,使a = 0成

20、立，其中a为yt+ si代入后的重新计算所得的值；求得最小的5+1 ,使 二0成立，其中玄为y+i + 5+i代入后的重新计 算所得的值，转(4)；(4) 如果|5|v|5+i| ,则 y, = yi + si ,否贝!jyi+i = y+i + 5+i ；然后在使用过程 一中的方法，去除拐点；转(5)；(5) 如果i<n-2, i=i+l,转(2)；否则结束。英过程三的主要面对的情况是c/-ic/<0,czcz+l >0,.,aa+ i >0,aa+y0 , k>2, 一般认为k<=5o首先，利用回弹法修改插值点使3+1 = 0,巴+ 2=0。这 样，相当

21、于将中间的插值点pf.,pi42删除，于是可m用过程二的方法将拐点给 去除。3.2.3曲尺卡样法我们将直尺卡样法屮的c都用e来替代，就是曲尺卡样法。即曲尺卡样法就是 对曲率线的直尺卡样法，而曲尺卡样法一般只执行过程一和过程二。其过程一如下：(1) 初始化心2 ,转(2)；(2) 如果ei-iei<= 0且e/e/+1<=0，转(3)；否则转(5)；(3) 求得最小的5,使& = 0成立，其中云为卩+次 代入后的重新计算所得的值,转(4)；(4) / = min(§,5), 为预设的最大偏移量。更新 卩=卩+5 ,转(5)；(5) 如果i<n-1, i=i+l

22、,转(2)；否则结束。其过程二如下：(1) 初始化2 2 ,转(2)；(2) 如果e-i&vo、e©+i> 0且e：+ie+2v0 ,转(3)；否则转(5)；(3) 求得最小的5 ,使成立，其中云为卩+ 5代入后的重新计算所得的值；求得最小的5+1,使 屛一0成立，其中自+1为阳+恥 代入后的重新计算所得的值，转(4)；(4) 如果|5|v|5+i| ,则yi = yt+3i ,否贝uy+i = y+i+5+i ；然后在使用过程 一中的方法，去除拐点；转(5)；(5) 如果52, i=i+l,转(2)；否则结束。324 般曲线的光顺设计算法在实际生产过程中，我们遇到的曲

23、线很多都不是函数型曲线。尽管三次函数样条 还有二次导数平方的积分最小这样良好的性质，它面对最大拐角大于120度的插值点 序列时，上述的光顺方法就显得也无能为力了。因此，我们需要对插值点进行分段，逐段进行光顺，然后将结果拼接在一起。为 了避免拼接后两段之间有明显的差界，处理的方法是相邻的两段间共用4到5个插值 点。比如，1到10为一段，下一段为7到15,这样7、8、9、10四个点是共用的插 值点。分段光顺后，被共用的点可能对应有有两个不同的新位置，这两个新位置的中 间点的位置为该共用点的新位置，这个步骤称z为混合。图4该线分成了两段（红与绿），黑色部分为共用点其算法的主要过程如下：（1）将pg

24、yd分段，每相邻两段有4到5个共用点，且每一段满足该段的插 值点列最大拐角不超过120度；（2）对于每一段，分别对其依次使用：冋弹法、直尺卡样法、曲尺卡样法进行 光顺。后没有共用点所得的结果，右图为分段共用4个点并混合后所得的结果，右图的拐点显然比左图少。3.3实验结果7f例图6鞋印，左图是原曲线，右图是曲率线。红色为光顺后，蓝色为光顺前。图7图83.4算法的局限性如3.2.4所述，对于一般曲线，这套方法需要先分段再混合。这样，在相邻两段的拼接处，原来的光顺结果可能会被破坏，从而得不到更好的结果。图9左图是图4的例子加了噪音后的原曲线，右图是曲率线图。蓝色表示光顺前的曲率线，红色则 表示按3.

25、2.4所述算法光顺后所得的曲率线。即使有分段和混合，中间部分的光顺性反而更差了。该算法比起第2章所述的整体方法，更多地考虑了局部性；而比起局部方法，又 是一段一段地去光顺，考虑了部分地整体性。因此 它可以说是“大局部”方法。我 们希望得到类似的方法，既考虑局部，乂不忽略全局整体性，从而得到更好且更鲁棒 的光顺效果。基于l1范数优化的光顺算法4.1向量c与向量e我们已知插值点(或型值点)斥a$)(匸1,.界)，我们希望反求出这些型值点 位置与其对应的曲率向量间的关系。如果我事先给定了参数如，它可以是均匀 也可以是非均匀的。那么，由参考文献11,由三次b样条的基本性质，在每个插值 点、p处的一阶导

26、数与二阶导数都可由p=x,y,.n,y 厂乘上一个矩阵得到，这个矩/11n n阵仅与参数妁,，血有关，与斥所处的位置无关。又由参数平面曲线s(r)=(xo，xo)，其曲率为._ 兀y'(/) 兀'(7) ¥(/)k= (d+灿严尽管一阶导数与二阶导数与p是线性关系，但是曲率与它却是非线性关系。为了 使优化更为简单，一种方法是将二阶导数当作是曲率；另一种方法则是在优化过程中 将一阶导数作为常数来处理，因为当型值点的偏移量较小时，可以认为一阶导数不发 生太大的变化。令c为型值点处曲率所构成的向量。当我们将曲线的一阶导数作为常数，曲率 向量c与p满足线性关系，即可以得到一个

27、矩阵a,使得c=apo具体如何求，可 以参考附录中所附的matlab代码。而©=0+1-口)/(如-堆)，当比，血为事先给定的常数时,它与曲率向量c存 在线性关系。因此，存在矩阵b,使得e二bp成立。具体如何求，可以参考附录中 所附的matlab代码。4.2数学模型的构建421光顺判别准则c3与优化目标如第3章中所述，光顺判别准则c3有三个优化目标：(1)曲线的拐点数；(2) 曲率线的拐点数；(3)曲率线的变化幅度。而第三章中，董光昌先生等提岀的曲线光顺方法，冋弹法对应减少曲率线变化的 幅度，直尺卡样法对应减少曲线的拐点数，曲尺卡样法对应减少曲率线的变化幅度。我们先考虑曲率线的变化幅

28、度，这是三个优化目标中相对容易量化的目标。向量 e中的每一个值表示该插值点处曲率的变化幅度，因此，减少向量e的l1范数或l2 范数，即可减少曲率线的变化幅度；最小化| £ 或者itlb即可对应最小化曲率的变 ii.化幅度。再考虑前两个优化目标，它们都是希望减少拐点数。曲线的拐点数，即第一振动 数，我们用m来表示；曲率线的拐点数，即第二振动数，我们用m 来表示。由第 3章所述，第一振动数代表的是曲线光顺性发生“质变”的次数，它是最重要的优化 目标。因此，我们首要考虑如何优化m。而第一振动数与第二振动数是相似的，只 要我们知道如何优化总可以用类似的方法去优化就如直尺卡样法和曲尺卡 样法一

29、样。4.2.2曲线的拐点数与c的l0范数曲率向量c的l0范数，即曲率向量c屮非零元的个数。图 10 曲率线图 c=1,2,-1,1,-1,3r图 11 曲率线图 c=1,2,0,1,-1,3r图10屮的拐点数为4,而其c的l0范数为6。图11中拐点数为2,其c的l0 范数为5o易有不等式叫 <=hc|0-l因为只有当向量c中相邻的两个非零元的符号不同，才会产生一个拐点，那么当 c的l0范数固定，最多只会产生非零元个数减一个拐点。从这点来看，c的l0范 数为拐点数的上界，优化c的l0范数，能在一定程度上减少拐点数。如果我们将向量c中某个菲零元。变成0,而其他值保持同号：（1）当g的两个相邻

30、的非零元都与它异号时，它变成零，拐点数会减少2。如 将图10中第3个元素1变成0就变成了图11,而图11的拐点数比图10的拐点 数少了2o（2）当。得相邻非零元有一个与它同号，它变成零，拐点数不会改变。我们知道优化c的l0范数，可以近似转化为优化c的l1范数。当我们去优化c的l1范数时，一般来说，c中的每个元素在优化后不会与原來异号，或者是同号， 或者是变成零，即确保不会增加拐点数。根据上述讨论，优化c的l1范数，应该能 够有效地减少曲线的拐点数。下面图示是实验论证。图12左边为原曲线，右边为曲率图。蓝色为优化c的范数前，红色为优化后。图13左边为原曲线，右边为曲率图。可以看出，优化后拐点明显

31、减少。图14左边为原曲线，右边为曲率图。通过实验，我们认为优化l0范数，可以有效地去除多余的拐点。423曲线的拐点数与e的l0范数从上小节的分析，我们知道减少曲率向量c的l0范数，可以有效地减少曲线 的拐点数。而向量e可以看成是曲率线的曲率向量，减少向量e的l0范数，可以 有效减少曲率线的拐点数。当曲线的拐点数很多时，向量c屮元素符号经常发生改变，曲率线应该是沿着横 轴上下振动，此时曲率线本身的拐点也很多。反z,当曲率线的拐点较少时，相对应 的曲率线的振动也会较少，那么曲率线穿越横轴的振动也很可能相应的较少，如此， 曲线的拐点数就会比较少。因此，减少e的l0范数，也可能会减少曲线的拐点数，4.

32、2.4曲线的拐点数与e的l2范数由前文可知，e的l2范数应该直接与曲率线的变化幅度相关。在本节中，我们 认为减少e的曲率的变化幅度，也能在一定程度上减少曲线的拐点数。我们在木节之所以考虑e的l2范数，而不是e的l1范数，是为了不受e的稀疏 性（l0范数）影响。图15中所示的曲率线图有两个拐点，在中间点处的曲率变动幅度较大。而在未 被光顺的曲线屮，在局部类似这样的曲率线图有很多。当我们减小屮间点的变化幅度， 只要减少达到一定的量，如图16所示，就很可能将拐点减少。图15曲率线图。曲率向量c=2,-1,2j,图16曲率线图。红色曲率向量为c=1.8,0.1,1.8f我们进行以下实验：在同一容差条件

33、下，即型值点的最大偏移量不超过一个固定 值，对比优化c的l1范数与e的l2范数的结果。图47实验对象的原曲线图图18：最大偏移量为0.001时的曲率线图。蓝色为原曲率，绿色为c的范数优化后结果,红色为e的l2范数优化后的结果图19：最大偏移量为0.0028时的曲率线图。可以看出，红线的拐点数已经减少2,而绿线与蓝线拐点数相同。实验说明，在有些情况下，优化e的l2范数会比优化c的l1范数更快地减少拐 点数。4.2.5基于l1范数的优化目标综合以上所述，光顺的判别准则c3可以分别对应三个优化目标:|c|() > |e|()和 忖2。我们知道，关于l0范数的优化可以转化为l1范数的优化，因此，

34、目标函数hell。 可以fflllch,来替代以进行优化。而ii e ii。可以用ii e lh来替代进行优化。而e的l1范数代表了曲率线的变化幅度, 因此我们可以不用再去优化ii e |2。光顺判别准则c3的后两项目标，我们可以用| £ |, 来表示。由此，我们确定了曲线光顺问题的两个优化目标函数：43实证结果分析4.3.1 c的l2范数与c的l1范数如第2章所述，如果我们基于光顺判别准则c1,那么可以通过优化c的l2范 数来达到光顺的效果。而在光顺判别准则c3中，减少拐点数才是我们的光顺的首 要目标。以下的实验图，是在同一容差条件下，分别优化c的l2范数与c的l1范数的 对比结果

35、。图20 (a)原曲线图图20(b)优化l2范数后曲率线与原曲率线对比图。蓝色为原曲率，绿色为优化后。图20(c)优化l1范数后曲率线与原曲率线对比图。蓝色为原曲率，红色为优化后。如图20所示，图20 (c)中的红线的拐点数明显比图20 (b)中的绿线拐点数要少。从减少拐点数这个角度来说，优化c的l1范数比优化c的l2范数更加有效。图21(a)原曲线图21(b)c的l2范数优化后曲率对比图图21 (c) c的l1范数优化后曲率对比图综合图21的例子，可以明显看出，在同一容差条件下(每个点的偏移量不超过 (max(y)-min(y)/1000)，优化c的l1范数比起优化c的l2范数更能够减少第一

36、 振动数，即曲线的拐点数。4.3.2 e的l2范数与e的l1范数图22曲率线图。蓝色为原曲率，绿色为e的l2范数优化，红色为e的范数优化。图22的原曲线为图17中的曲线，图22设定偏移量不超过0.0027的结果。可 以看出，优化e的l1范数比优化e的l2范数可能更有效地减少拐点。图屮蓝、绿 线穿过了横轴2次，而红线没有穿过横轴。综合以上所述，我们讨论了在光顺问题上优化l1范数相比l2范数的优越性。 因为l1范数还与l0范数有直接相关的关系，而l0范数是离散的量，它的变化相 比起l2范数的变化是一种“质变”，而我们想要减少的拐点，也是曲线发生了 “质变”的 点，因此，l1范数会比l2范数更加有效

37、。4.4数学模型的优化综合以上的模型的讨论，我们可以建立多目标优化的数学模型：c = co + a8;e = eo + bs;其中矩阵a, b为41中所讨论的矩阵，c。、勺分别为初始值，所求的为偏移 量，纟为给定的偏移量最大范圉，一般不能太大，因为根据4.1,我们在优化过程中 将一阶导数当成常数来处理，如果型值点位置变化较大，让一阶导数也变化较大，会 明显影响到结果。我们采用网上提供的cvx matlab凸优化包来对其进行优化。具体的代码会在附录 中给出。5实验结果本章我们将比较我们的算法与其他算法的结果。这里我们参照的算法主要是最小 二乘法（曲率的l2范数求极小）、n. sapidis与g.

38、 farin的局部修改法。这两种算法分 别属于整体方法和局部方法，也是目前光顺方法屮最具代表性的两种算法。我们进行了大量实验，证明了我们的算法的在光顺效果上的优越性。图23左图是曲线图；右图是三种方法光顺后的曲率线图。蓝色为原曲率，红色为我们的光顺方法, 黑色为n. sapidis与g. farin的局部修改法，绿色为最小二乘法（求c得l2范数极小）。曲率棒对比图如下:图24曲率棒对比图。左上为原图，右上为n. sapidis与g. farin的局部修改法的结果，左下为我们 的方法的结果，右下则是最小二乘法的结果。图25左边是原图；右边曲率线对比图。颜色对应与图23相同。图26曲率棒对比图。左

39、上为原图，右上为n. sapidis与g. farin的局部修改法的结果，左下为我 们的方法的结果，右下则是最小二乘法的结果。实验证明，我们的光顺方法比起其他两种方法的光顺效果更好。我们的算法基于光顺判别准则c3,而董光昌先牛的算法也是基于光顺判别准则c3。我们认为在董先生的算法局限性的场合我们的算法依然能有效地光顺，以下是实 验结果。图27曲率线图。该图的原曲线时图9中的曲线。蓝色为原曲率，绿色为董先th方法光顺后的曲率, 红色为我们的方法光顺后所得的曲率。6结束语我们的光顺方法主要是对向量c与向量e的l1范数进行多目标优化。通过讨论, 我们了解了影响曲线光顺性的主要原因，并针对这些原因建立

40、了数学模型。我们认为通过这篇论文所述的算法，曲线的光顺问题己经能够得到较为良好的解 决。我们希望能将这套方法往曲面上推广，从而直接解决曲面光顺的问题。参考文献111 g.farin, curves and surfaces for cagd:a practical guide. academic press, 5lh edition, 2002.2 j.kjellander, smoothing of cubic parametric splinesj. computer aided desig很 15(3):175-179, 1983.|3 h. hagen, s-hahmann and g

41、-schulze, automatic smoothing with geometric surface patchesj. computer aided geometric design. 4(3):231-235, 1987.4 j.poliakoff, an improved algorithm for automatic fairing of nonuniform parametric cubic splinesj. computer-aided design, 28(1):59-66,1996.5 x.ye, curvature continuous interpolation of

42、 curve meshesj. computer aidedgeometric design, 14:169-190, 1997.6 n. sapidis and g. farin, automatic fairing algorithm for b-spline curves j computer-aided design, 22(2):121-129, 1990./7/w. renz, interactive smoothing of digitized point dataj, computer aided design, 14:267-269, 1982.8 j. hoschek, s

43、moothing of curves and surface j computer aided geometric design, 15:175-179, 1983.9 c.zhang, p.zhang and f.cheng, fairing spline curves and surfaces by minimizing energy j. computer aided design, 33( 13):919-923,2001.10 董光昌，吴明华，洪安祥，样条曲线光顺的数学模型分析j,高校应用数学 学报a辑(中文版)，2003(04)。11 董光昌,张但，刘志诚，马利庄，curve fa

44、iringj, progress in natural science, 1997(05)o12 刘志诚，董光昌，样条曲线光顺概念及指标回弹法的应用j,数学的实践与 认识，1985(03)o13 董光昌，梁友栋，何援军，样条曲线拟合与双圆弧逼近j,应用数学学报, 1978(04)o附录(相关代码)主函数：function nx.ny = ll_fairing( x.y,tolerance )n 二 length(x);%设定多目标优化的迭代步骤kk = 8;%设定步长step = tolerance / kk / 2;% 获得参数 qx,qy: qx = 0;x;01; qy = 0;y;0;

45、% a : px = a * qx; py = a * qy;其中px、py为控制点的位置%t为节点位置，即对应文中的u% n为a的逆矩阵% n1 一阶导数求导矩阵，即 px* = nl * px; py' = n1 * py; %n2二阶导数求导矩阵 即px” = n2*px;py“ = n2*py;%df为差分矩阵，即e = df * c;a,qx,qy,t,n =cubic_bspline_m(x,y);n1,n2,df二 df_mat(t);%将(, qy合并为一个长向量,矩阵对应修改t = zeros(size(a);a = a,t;t,a;a = sparse(a);q =

46、 qx(;qy'p = a *q;% c = matc * p;matc = getcurvaturematrix(p,n 1 ,n2);% c = matc * q;matc = matc * a;% e = mate * a;mate = df * matc;n = length(p);%初始值co = matc * q;eo = mate * q;%多目标迭代优化for i = 1 : kkcvx_beginvariable dy(n);minimize(norm(matc * dy + co,l) subject tonorm(mate * dy + eo)<=norm(

47、eoj); norm(dy jnf) <= step;cvx_endhold on;q = q + dy;p 二 a*q;matc = getcurvaturematrix(p,n 1 ,n2);matc = matc * a;mate = df * matc;co = matc * q;eo = mate * q;cvx_beginvariable dy(n);minimize(norm(mate * dy + eo,l) subject tonorm(dy ?inf) v= step ;cvx_endq 二 q + dy;p = a*q;matc = getcurvaturematr

48、ix(p,n 1 ,n2);matc = matc * a;mate = df * matc;co = matc * q;eo = mate * q;end)工9)匸2ovsfzq sx 寸)卫 q 看+§"(寸+u)n(z+u)f(z+u)l puo bsae 二(2)(2 丄)ag(e 丄)xasx)uuou+fs e+le 寸hjojohsoasoasoh (一 )1puq二(-¥( 一 ±m()x,(王)xduuou+卫tu 二卫 joj o上 _(x)£cnuohu(a,x )w ju 二 dsal2qnuuzt ao,xo<u

49、owuasi00zj二 h(-+u+u)noj'uonoj'edn二ai7)n 孑佶(.u7+u)n sy(u7+u)n6fy(i+u7+u)n 二 y(e+u7+u)n圧a寸zch5 )ngh5 )nca二)n oh(z+u)aooh(z+u)xo "(i )<(eq+zq+ - qr( i -)v(eq+ 一 qlr寸wj(一)v(eq+eq+sr( i .r§+1 q)，0)v(zq+ - q)a i)v(zq+ - qr(t)<i qdewj-(r) v(zq+1 q)+( r)v(eq+1 qr(.)<q+(r) v i (r )<qd i m_(tu¥(§h2xuv(一+u)feq xi+u)工 z+u)fiq二)<(