Bezier曲面的最佳逼近

D0I:10.13374/j.issn1001-053x.1996.05.021 第18卷第5期 北京科技大学学报 Vol.18 No.5 1996年10月 Journal of University of Science and Technology Beijing 0ct.1996 Bezier 曲面的最佳逼近 王兵团”张志刚”王军团2》王萍) 1)北京科技大学数力系，北京1000832)东风汽车公司技工学校 摘要提出一种用于计算机辅助几何设计的分片最佳通近Bezier曲面控制点的方法，这种方法只 用有限次最小二乘计算就可以完成最佳逼近的目的 关键词Bezier曲面，逼近，外形设计 中图分类号0174.410187.1 Bezier曲线和Bezier曲面是几何造型的一种重要方法，由于它们有很好的几何性质，使得 其在船舶、飞机和汽车等的外型设计中应用甚广，通常在进行外型设计时，要利用一组已知 数据来获得由Bezier曲线或曲面表示的参数方程.为此，人们尝试着不同的方法来达到这个 目的.文献[l]中提出了用一次最小二乘计算来获得Bezier曲面方程的方法.本文在该文献 的基础上，提出用有限次最小二乘计算可使逼近结果达到最佳. 1 Bezier曲线的逼近 设给定一组空间点列{9，}0,1,2，…，r,求 一条m次Bezier曲线Bm,使其在离差绝对值最 大者极小的意义下最佳通近点列{2，（见图1）： 令曲线B的方程为： 图1最佳逼近的Bezier曲线Bm 0=2B050s1s1 (1) k■0 式中Bm)=C点：气l-)*是Bernstein基函数，{⑥为曲线的特征多边形顶点. 对每个数据点Q,应该怎样选取Bm上的对应点户()？本文选取规范化的累加弦长平方 作为1，即 i=0 i≠0 上式中1。=Q-2表示相邻两数据之间的距离. 在选定t,后，曲线Bm逼近{Q}的问题转化为求解包含m+1个未知向量，r+1向量方程的 方程组： 1995-0801收稿 第一作者男38岁副教授硕士

第 18 卷 1 9 9 6年 第 5期 1 0 月 北 京 科 技 大 学 学 报 J o u r n a l o f U n i v e r si yt o f S e i e n e e a n d T e e h n o l o gy B e ij i n g V o l 。 1 8 N 0 . 5 O Ct . 1 9 9 6 B e iz e r 曲面 的最佳逼近 王兵 团 ` ) 张志 刚 ` ) 王 军 团 2 ) 王 萍)l l )北京 科技大学数 力系 , 北 京 10 0 0 8 3 2) 东风汽 车公 司技工 学校 摘要 提 出一 种用于 计算机辅助几何设计的分 片最佳逼近 B ez ier 曲面 控制点的方法 , 这种方法只 用 有限 次最小二 乘计算就可 以 完成最 佳逼 近 的 目的 . 关键词 B ez ie r 曲面 , 逼 近 , 外形 设计 中图分类号 0 1 7 4 4 1 0 1 8 7 . 1 B ez le r 曲线 和 B e iz e r 曲面是 几何 造 型 的一 种重 要方 法 , 由于 它 们有 很好 的几何 性质 , 使得 其在 船舶 、 飞 机和 汽 车等 的外 型设 计 中应 用 甚广 . 通常 在进 行外 型设 计 时 , 要 利 用一 组 已 知 数据来 获 得 由 B ez i e r 曲线 或 曲面表示 的参数方 程 . 为此 , 人们 尝试 着不 同的方 法来 达到这 个 目的 . 文献 l[ 〕中提 出了 用 一 次最 小 二乘计算 来 获得 B ez i er 曲面 方程 的 方法 . 本 文在 该文 献 的基 础上 , 提 出用 有 限 次最小 二 乘计算 可使 逼 近结果 达 到最 佳 . 1 B e z i e r 曲线的逼近 尹G 设 给定 一组 空 间点 列 { q } i一 0 , l , 2 ,… , r , 求 一 条 m 次 B ez ie r 曲线 B m , 使其 在离 差 绝对值 最 大 者极 小 的意 义下 最 佳 逼近 点列 {以}( 见 图 l .) 令 曲线 B 。 的方程 为: 节 。 笋( , ) 一 艺 。 、 。 ( )t 砚 o “ ` 图 l 最佳逼 近的 B e z i e r 曲线刀, ( l ) 式 中 B * 。 ()t 一 C 知 ` l( 一 )t ’ 一 k是 B e m st e in 基 函 数 , 笼灭} 为曲线 的特 征 多边形 顶 点 . 对每 个 数 据 点 Q , 应 该 怎样 选 取 B 。 上 的对 应点 万.(t ?) 本 文选 取规范 化 的累 加 弦长 平 方 作 为 l , , 即 。 一 {鬓 Z` /客 ` 军 i 羊 0 上式 中 l * 一 瓦三石;表示 相邻 两数 据 之 间的距 离 . 在 选定 t ,后 , 曲线 B 。 逼 近 {q } 的 问题 转化 为求 解 包含 m +l 个 未 知 向量 , : +l 向量 方 程 的 方程 组: 19 9 5 一 0 8 一 01 收 稿 第 一作 者 男 38 岁 副 教 授 硕 士 DOI: 10. 13374 /j . issn1001 -053x. 1996. 05. 021

·492· 北京科技大学学报 1996年No.5 A.05=g1=0.1,… (2) =0 由于m一般≤5，而~比m大得多，所以式(2)是超定线性方程组在外形设计中，要求： 瓦=g。,万=9，，于是式(2)成为： m二 ∑B)5=g-(B00。+BnnQ}i=12,…,r-1 (2’) 文献[]是求式(2′)的最小二乘解，而本文求它的最佳逼近解. 2 Bezier曲面的逼近 设给定一组空间点阵{Q,},i=0,1,…,;广=0,1，…，S把每相邻两点用直线连接起来， 组成一个拓扑意义下的矩形网格.我们的问题是求一块m×n次Bezier曲面片Smm,使其能 最佳逼近给定的点阵{Q}.设Sm的方程为： F(u.w)= 22BBw50≤4w≤1 (3) k=01▣0 式中Bm(),B,(w)为Bernstein基函数；b,是Smn的特征网格的控制顶点. 对每个点，如何选坂Smn上的点F(,w,)作为Q,的对应点是一个很敏感的问题. 用文献[)的双累加弦长参数来确定（以，”，）进行最佳逼近时，精度比文献[山好，但我们 采用规范化双累加弦长平方参数来确定(“，W,)能达到更好的效果.这种选取能保持内在不 变的几何性质，这里4y,w,为： 0 i=0 ,= i=1,2,…,r 0 j=0 w.= j=1,2,…,s 这里1，及1分别表示两个方向的相应弦长，即↓，=-2，；=，-② 显然0≤“，”，≤1，令武4，”，)=，可以得到(V+(s+)个向量线性方程组： B.u)8mi=0,i=01,八j=01. (4) 它含有(m+1)(n+1)个未知量b,k=0,l,,m；1=0,1,…,n. 在外型设计中，通常把实测数据点分成几组，分别用每组数据进行Bezier曲面的逼近， 然后按某种光滑连接条件把它们拼接起来步骤大致为： (1)令4个角点相等，即 buo 200 bom=Con 6mo -2r0bmn=2rs (2)分别用Bezier曲线逼近4条边界线，u=0,u=l,w=0和w=1,从而得到Bezier曲面 的边界控制点0，b可，b,和6

. 4 9 2 . 北 京 科 技 大 学 学 报 19 9 6年 N o . 5 艺 。 * 。 ( ti )不 一 口 k = O 二 O , l , . ’ . ,r 由于 m 一 般 ` 5 , 而 : 比 m 大 得 多 , 所 以 式 ( 2) 是 超定 线性 方程 组 . 在外 形设计 中 , 砚 = Q 。 , 砚 一 Q ; , 于是 式 ( 2) 成 为: (2 ) 要求 : m 一 1 艺 B * , ( , , )砚 一 口 * 一 渭 。 二 ( ` : )。 。 + B 。 , ( ` : ) Q r } ` 一 ’ , 2 , 二 ’ , r 一 ` k 二 l 文献 l[ 」是求 式 ( 2 ` ) 的最 小二 乘 解 , 而本 文求 它 的最 佳 逼近解 . 2 B e z i e r 曲面 的逼近 设 给定 一 组 空 间点 阵 笼Q , , } , i 一 0 , l , … , ;r j 一 0 , l , … , s, 组成 一个 拓 扑意 义下 的矩形 网格 . 我 们 的 问题 是求 一 块 m 最 佳 逼近 给定 的 点 阵 {Q ; , } . 设 S 。 。 的方程 为 : 把 每相 邻 两 点用 直 线 连 接起来 , x n 次 B ez ie r 曲面 片 S , 。 , 使 其 能 梦( u , w ) 一 艺 艺 。 * 。 ( u ) B , 。 ( w )砚 ( 3 ) k = 0 , = 式 中 , * , ( u ) , 。 , 。 ( w ) 为 B e rn s t e i n 基 函 数 ; 瓦 是 s 。 。 的特 征 网格 的控 制顶点 . 对每 个 点 以 , , 如何 选取 S 用 。 上 的点入 。 , , , w 口作 为 级 , 的对应 点是 一个 很敏 感 的 问题 . 用 文 献 l[ ] 的双累 加 弦 长参数来 确 定 u(t , , w 沪进行 最 佳逼 近 时 , 精 度 比文献 l[ 」好 , 但我 们 采 用规范 化双 累加 弦长 平方 参数 来确 定 (u, , , 、 lj ) 能达 到更 好 的效果 · 这种 选取 能保 持 内在不 变 的几 何性 质 . 这里 。 ; , , w ` , 为 : = 1 , 2 , … , r j = 0 j 二 l , 2 , … , 、 ! 嘴 l W 尹 一 这里 l , , 及 l万分 别表 示 两个 方 向的相 应 弦长 , 即 气 Q ` 一 。 Q , , , 毛丁 = Q , , 一 , Q , , 显 然 0 丛 u , , , w ; , ` l , 令 尹( u , , , w = Q , , , 可 以 得到 (r +l ) (s +l ) 个 向量 线性 方程 组: 艺 艺 B 、 。 ( u ; , )B , 。 ( w , , )可 一 Q ` , ` 一 O , ` , … , r ; 、 一 0 , ` , … ( 4 ) 它含 有 (m + l ) ( n + l ) 个 未 知 量砚 , k 一 0 , ` , … , m ; l 一 0 , l , … , n · 在外 型设 计 中 , 通 常 把 实测数 据点 分 成几组 , 分 别用 每组 数 据进行 B ez ie r 曲 面 的逼 近 , 然后 按某 种光 滑 连接 条件 把它 们拼 接起 来 . 步 骤大 致 为: ( l ) 令 4 个 角 点相 等 , 即 b 。 。 = Q 。。 b 。 。 = Q 。 , , b m 。 一 Q ; 。 , b 。 。 = Q : , ( 2 ) 分别 用 B e z i e r 曲线 逼 近4 条边 界 线 , u 一 。 , u 一 l , w 一 。 和 w = l , 从而得 到 B e z i e : 曲 面 的边 界控 制 点 砚 , 砚 , 砚 和砚 ·

Vol.18 No.5 王兵团等：Bezier曲面的最佳通近 ·493· (3)逼近曲面Sm的中间控制点.此时将(2)得到的全部边界控制点代入式(4)，得： 宫2Ae85-Q,0,城 (5) 式中，i=1,2,…,r-1；j=1,2,…心-1，以及 BQ=Bo(u)Bo(W)200+Bo(u)BW)Qo:+B()Bo(W+Bm(u)BBW) BB,=∑Bu[B(w,b0+B,w,5a+∑B.w,Bnu)i+Bnn(ub 这是一个包含(m-1)(n-1)个未知向量bk=1,2,,m-1;1=1,2,…,n-l,有(r-1)s-1)个 方程的超定线性方程组.余下的问题是怎样去求这些方程组的最佳逼近解. 对超定线性方程组的最佳逼近解，已经有许多算法，如文献[2]中的Polya算法，上升算 法等，这些算法对本文的方程都有计算量过大的缺点.本文采用文献[3]中的有限次最小二 乘逼近来得到最佳通近解的方法.用这种方法可以同时给出最小二乘解和最佳逼近解以及 它们之间的若干中间解.这对Bezier曲面逼近问题是很方便的，我们可以根据问题的具体特 点和精度要求来选用.由于式(5)的系数矩阵中所有行向量满足Haar条件，因此它可以满足 文献[3]中的条件和结论.再者由于m通常≤5，这样对边界线的方程组，每组最多含4个 未知向量，由文献[3]的结论，最多做5次最小二乘法就可得到边界上的最佳逼近解，考虑 到逼近的整体性，可以对式(5)也做5次最小二乘法求出Sm的中间网格点.如果还想提高 精度，可以继续对式(5)做最小二乘法，最多做到(m-I)(n-1)次就求出(5)的最佳逼近解，从 而得到最佳逼近的Bezier曲面. 利用有限次最小二乘法求(5)的最佳解，是通过对扰动后的剩余向量按模减少的趋势 给出的，即‖(b)‖x0的一片，为此在x0y面上取如下11×11个分割节点(，y: x=-1+02ii=0,1,2,…,10 (y=0.少 j=0,1,2,…,10 再由S算出2的对应值，得到原始数据点，=（化，y,乙，j=01,2,…,10,按式(5）选 用4×4 Bezier曲面片S44,用本文的方法通近上述11×11个数据点2，y,得到部分结果见表1. 从上表1可以看出，最佳通近的效果是十分满意的.例如x=0.4,y=0.7时，逼近值与 解析值是一致的.计算结果表明，解析曲面与逼近曲面之间的最大误差是3.87×10一6.文 献[1]也用此例进行计算，但它的误差最大为2×10-4，本方法在通近程度上提高了1个多 数量级.计算是在IBM PC机上完成的

V o l . 1 8 N o 石 王 兵 团等 : B ez ier 曲面 的最佳逼近 . 4 9 3 . 3( )逼 近 曲面 S 。 。 的 中 间控制 点 . 此 时将 (2 )得 到 的全 部边 界控 制点 代人 式 ()4 , 得 : m 一 I n 一 l 艺 艺 B * 。 ( u , , )B , 。 ( w ` , )瓦 一 。 , , 一 B 。 * , 一 B , , k = l , = l ( 5 ) 式 中 , B Q ` , : i = l , 2 , 二 B 。 。 ( u , , ) B · , 犷 一 ;l j 二 1 , 2 , 二 ,s 一 1 , 以及 。 。 ( w , , ) Q 。 。 + B 。 。 ( u ` , )B 。 。 ( w , , ) Q 。 , + B 。 。 ( u , , )B 。 。 ( w ; , ) Q ; 。 + B m m ( u , , ) B B 。 。 ( w 。 )Q 。 : B , , 一 艺B * , ( u ` , ) [B 。 。 ( w ; , )砚 + B 。 。 ( w , , )叨 + 艺 B , 。 ( w , , ) [B 。 。 ( u ` , )可 + B m m ( u , , 这是 一 个包 含 (m 一 l )( 。 一 1 )个 未知 向量 瓦 , k 一 l , 2 , … , m 一 1 ; 卜 l , 2 , … , n - )动 , 有 ( r 一 l ) ( s 一 1) 个 方 程 的超定 线性 方程 组 . 余下 的 问题是 怎样 去求 这些 方程组 的最 佳 逼近解 . 对超 定线 性方 程组 的最 佳逼 近解 , 已 经有许 多 算法 , 如 文献 [2] 中的 P ol ay 算 法 , 上 升算 法 等 , 这些 算 法对本 文 的方 程都有计 算量 过大 的缺 点 . 本 文采 用文 献 [3] 中 的有 限次 最小 二 乘 逼 近来 得 到 最佳 逼 近解 的 方 法 . 用 这 种方 法 可 以 同 时 给 出最小 二 乘 解 和最 佳 逼 近解 以 及 它 们之 间 的若干 中 间解 . 这 对 B ez ie r 曲面 逼 近 问题 是很 方便 的 , 我们 可 以 根 据 问题 的具体 特 点 和精 度要 求来 选用 . 由于 式 ( 5 ) 的 系数矩 阵 中所有行 向量 满 足 H a r 条件 , 因此 它 可 以满 足 文 献 3[ 〕中 的条 件 和结论 . 再 者 由于 m 通 常 ` 5 , 这样 对边 界 线的方 程 组 , 每组 最 多含 4 个 未 知 向量 , 由文 献 [3] 的结论 , 最 多做 5 次最小 二乘 法 就可 得 到 边界 上 的最 佳逼 近解 . 考虑 到 逼 近 的整体性 , 可 以 对式 (5 ) 也 做 5 次 最小 二 乘法 求 出 S 。 , 的 中 间网 格点 . 如果 还 想 提高 精 度 , 可 以 继续 对式 (5 )做 最小 二乘 法 , 最多 做到 (m 一 l ) ( n 一 l) 次 就求 出 ( 5 ) 的 最佳 逼近解 , 从 而 得到 最佳 逼近 的 B ez ie r 曲面 . 利 用有 限 次最小 二 乘法求 ( 5 ) 的最 佳 解 , 是通 过 对 扰 动后 的剩 余 向量按 模 减 少的 趋 势 给 出的 , 即 }}万(b (k) )l 一二 0 的一 片 , 为此 在 xoy 面 上取 如下 1 1 ` 1 个分 割节 点 (x ` , 沙 nU曰n , . 1 1 .1 = 一 l + 0 . 2 1 二 0 . lj , 2 , ` 二 , , 2 , … , X l 叼犷 户 l 才 I 、 再 由 S 算 出 “ , , 的 对应值 ,得到 原 始数 据点 Q 。 用 4 x 4 B e iz er 曲面片 凡 4 , 用本文 的方 法逼 近 上 述 1 1 ` yj , z , , ) , i , j 一 0 , l , 2 , ` ’ ` , 10 , 按 式 ( 5 ) 选 1 1个 数据 点 Q ` , , 得到 部分 结果 见表 L 一一 0,10x(, 从上 表 l 可 以 看 出 , 最 佳逼 近 的效果 是 十分满 意 的 . 例 如 x 一 0 . 4 , y 一 0 . 7 时 , 逼近值 与 解 析值 是 一致 的 . 计 算结 果 表 明 , 解 析 曲面 与逼 近 曲面 之 间的最 大 误 差是 3 . 87 x lo 一 “ . 文 献 l[ 〕也用 此 例进行 计算 , 但 它 的误差 最大 为 2 x lo 一 4 , 本方 法 在逼 近程 度 上提 高 了 1 个多 数量 级 . 计算 是 在 BI M P C 机 上完 成 的

·494· 北京科技大学学报 1996年No.5 表1不同x,y下的z计算结果 ×101 y 0.1 0.3 0.5 0.7 0.9 原始值 9.987430E-1 9.8868590E-1 9.6824580E-1 9.3674960E-1 8.9302840E-1 0.0 拟合值9.9874610E-1 9.8868540E-1 9.6822450E-19.3674560E-1 8.9302660E-1 0.4原始值 9.8980920E-1 9.7965410E-1 9.5902150E-19.2721210E-1 8.8301880E-1 拟合值 9.8980800E-1 9.7965670E-1 9.59021400E-19.2721210E-1 8.8302260E-1 。原始值 9.6249100E-1 9.5204440E-1 9.30800020E-18.9799170E-1 8.5228460E-1 0. 拟合值 9.6248720E-1 9.5204520E-1 9.3080040E-18.9798790E-18.5228420E-1 4结论 本文所提的方法具有用较小的计算达到较大精度的优点，它的计算简单，数据存贮少， 对于实际的Bezier曲面的外形设计问题是完全可行的，可供有关部门试用. 致谢：刘钦圣教授对本文提出许多宝贵意见，在此表示感谢 参考文献 1刘鼎元，胡康生.Bezier曲面的拟合.应用数学学报，1984(7)：250~256 2切尼EW.逼近论导引.徐献喻等详.上海：上海科技出版社，1981 3杨曙光.用有限次最小二乘法求解超定线性方程组的T解.高等学校计算数学学报，1986,18(3)：15~19. 4苏步肯，刘鼎元，计算几何.上海：上海科技出版社，1981 Best approximation of Bezier Surface Wang Bingtuan"Zhang Zhigan Wang Juntuan Wang Ping Department of Mathewatics and dfMechanics,USTB,Beijing 100083 2)Dong Feng Auto Co Polytechnic ABSTRACT Best approximation method of Bezier Surface is posed here.It can get the purpose by doing Least square computation finite times.The Best approximation of Bezier curves is also included. KEY WORDS Bezier curved surface,approxmation,appearance design

. 4 9 4 . 北 京 科 技 大 学 学 报 1 9 9 6年 N o . 5 表 1 不同 x , y 下的 : 计 算结果 火 1 0 - 0 . 0 0 . 4 0 . 8 原始值 拟合值 原始值 拟合值 原始值 拟合值 9 . 9 8 7 4 3 0 E 一 l 9 . 9 8 7 4 6 l OE 一 l 9 . 8 9 8 0 9 2 0 E 一 l 9 . 8 9 8 0 8 0 0E 一 l 9 . 6 2 4 9 10 0 E 一 1 9 . 6 2 4 8 7 2 0E 一 l 9 . 8 8 6 8 5 9 0 E 一 l 9 . 8 8 6 8 5 4 0 E 一 l 9 . 7 9 6 5 4 1 0E 一 l 9 . 7 9 6 5 6 7 0 E 一 l 9 . 5 2 0 4 4 4 0E 一 l 9 . 5 2 0 4 5 2 0E 一 l 9 . 6 8 2 4 5 8 0 E 一 l 9 . 6 8 2 2 4 5 0 E 一 l 9 . 5 9 0 2 15 0E 一 1 9 . 5 9 0 2 14 0 0 E 一 l 9 . 30 8 0 0 0 2 0 E 一 l 9 . 3 0 8 0 0 4 0E 一 l 9 . 3 6 7 4 9 6 0 E - 9 . 3 6 7 4 5 6 0 E - 9 . 2 7 2 1 2 1 0E - 9 . 2 7 2 1 2 1 0 E - 8 . 9 7 9 9 17 0E - 8 . 9 7 9 8 7 9 0 E - 8 . 9 3 0 2 8 4 0 E 一 l 8 . 9 3 0 2 6 6 0 E 一 1 8 . 8 3 0 1 8 8 0 E 一 1 8 . 8 3 0 2 2 6 0 E 一 1 8 . 5 2 2 8 4 6 0 E 一 1 8 . 5 2 2 8 4 2 0 E 一 l 4 结 论 本 文所 提 的方法 具 有用 较小 的计 算达 到较大 精度 的优 点 , 它 的计算 简单 , 数 据存贮少 , 对于 实 际 的 B ez ie r 曲面 的外形 设计 问题是 完全 可行 的 , 可 供 有 关部 门试用 . 致 谢 : 刘钦 圣教 授对本文 提 出 许多宝 贵意 见 , 在此 表示 感谢 . 参 考 文 献 1 刘鼎元 , 胡康 生 . B ez ie r 曲面 的拟 合 . 应用 数学学报 , 19 8 4 (7) : 2 50 一 2 56 2 切尼 E w . 逼近 论导引 . 徐 献瑜 等译 . 上 海 : 上海科技 出版社 , 19 81 3 杨曙光 . 用 有限 次最小二乘法求解超定线性方程 组的 T 解 . 高等 学校计 算数学学报 , 1 9 86 , 1 8 (3) : 巧 一 19 4 苏步青 , 刘鼎元 . 计算几何 . 上海 : 上海 科技 出版社 , 19 81 B e s t a P P r o x im a t i o n o f B e z i e r S u r af c e 肠 n g B i n g tu a n ’ ) 肋 a n g 肋心a n ` ) 肠 n g 九 n r u a n Z) 肠 n g 尸i n g ` ) D e P a rt m e n t o f M a t h e w a t i c s a n d d f入4 e e h a n i e s , U S T B , B e ij i n g 10 0 0 83 2 ) D o n g F e n g A u t o C o P o A B S T R A C T B e s t a P P r o x lm a t i o n m e t h o d o f B e z l e r S u r fa e e P u rp o s e b y d o i n g L e a s t s q u a r e e o m P u t a t i o n if n i t e t im e s . 1 5 P o s e d h e r e . It l yt e e hn i e e a n g e t t h e T h e B e s t a P P r o x im a t i o n o f B C z l C r K E Y C U f V e S 1 5 、 V O R D S a l s o i n e l u d e d . B e z i e r c u vr e d s u r fa e e , a P P r o x m a t i o n , a P P e a r a n e e d e s ig n