[转载] Hermite 与 Bezier 曲线的绘制

发信人: william@cis_nctu (何陋居主), 信区: programming
标 题: [转载] Hermite 与 Bezier 曲线的绘制
发信站: 交大资科_BBS (May 25 00:32:41 1995)
转信站: cis_nctu


From: Chi'u I-Nan * Area: 90 C 语言
To: All Date: 03 May 95 22:37:26
Subj: Hermite 与 Bezier 曲线的绘制

**********************************************************************
* Hermite与Bezier曲线绘制方法研究 *
* 作者：邱奕南 (Chi'u I-Nan) *
* 版权声明：以下文章内容本人仅同意供BBS 站上流传学习，但必须完整流传 *
* （含版权声明及程序），其余权利一概保留。任何未经本人同意 *
* ，将本文贩卖、刊登、节录、或其它一切侵害本人著作权之行为 *
* 者，皆需负担刑事责任及民事赔偿责任。 *
**********************************************************************

Hermite及Bezier曲线为三度空间曲线的常用表示法，以下我们先说明一
下这两个曲线的定义：

1.Hermite曲线

Hermite曲线为给定两端点及两端点向量所得的三次曲线。令三次曲线：

3 2
x(t) = Ax * t + Bx * t + Cx * t + d

3 2
y(t) = Ay * t + By * t + Cy * t + d

且令给定的两端点为(x1,y1)、(x2,y2)，以及两端点向量(xr1,yr1)、(xr2,yr2)，
则：

x(0) = x1, y(0) = y1
x(1) = x2, y(1) = y2
x'(0) = xr1, y'(0) = yr1
x'(1) = xr2, y'(1) = yr2

绘出(x(t),y(t))，0<=t<=1，即为Hermite曲线。

2.Bezier曲线

Bezier曲线为给定两端点及另两参考点所得的三次曲线，它可说是Hermite
曲线的另一种表示方式。假设两端点为P1、P2，以及两参考点Pr1、Pr2，则
Bezier曲线换算成Hermite曲线的方式为：

R1 = 3*(Pr1-P1)
R2 = 3*(P2-Pr2)

R1、R2即为Hermite曲线的两端点向量。

由于Bezier曲线和Hermite曲线可以说是相同的，因此以下之说明我们便以
Hermite曲线为主。由Hermite曲线的定义，首先我们必须求出Ax,Bx...等值。
由定义中的条件：

x(0) = x1, x(1) = x2, x'(0) = xr1, x'(1) = xr2

以及

2
x'(t) = 3 * Ax * t + 2 * Bx * t + Cx

可得：

┌ 0 0 0 1 ┐┌ Ax ┐ ┌ x1 ┐
│ 1 1 1 1 ││ Bx │＝│ x2 │
│ 0 0 1 0 ││ Cx │ │ xr1 │
└ 3 2 1 0 ┘└ Dx ┘ └ xr2 ┘

解之得：

┌ Ax ┐ ┌ 2 -2 1 1 ┐┌ x1 ┐
│ Bx │＝│ -3 3 -2 1 ││ x2 │
│ Cx │ │ 0 0 1 0 ││ xr1 │
└ Dx ┘ └ 1 0 0 0 ┘└ xr2 ┘

因此

x(t) = (2*t^3 - 3*t^2 + 1) * x1 + (-2*t^3 + 3*t^2) * x2 +
(t^3 - 2*t^2 + t) * xr1 + (t^3 - t^2) * xr2

同理

y(t) = (2*t^3 - 3*t^2 + 1) * y1 + (-2*t^3 + 3*t^2) * y2 +
(t^3 - 2*t^2 + t) * yr1 + (t^3 - t^2) * yr2

上述的公式中，由于t的值是介于0与1之间，这对于我们在实际绘图上较不
方便，而且运算速度也比较慢。因此假设我们以n条直线来仿真Hermite曲线，
则我们必须将t值化成整数，使它成为0<=t<=n（注意n条连续直线需有n+1个点）。
令i=n*t代入上述公式，化简后可得：

x(i) = (m1*x1 + m2*x2 + m3*xr1 + m4*xr2) / n^3
y(i) = (m1*y1 + m2*y2 + m3*yr1 + m4*yr2) / n^3

其中

m1 = 2*i^3 - 3*n*i^2 + n^3 , 0 <= i <= n
m2 = -2*i^3 + 3*n*i^2
m3 = i^3 - 2*n*i^2 + n^2*i
m4 = i^3 - n*i^2

如此我们便能很方便地求出仿真直线的各端点。然而上述公式中的乘法仍相当
多，对于m1～m4的计算上至少需5次乘法、2次移位乘法和6次加法（或4次乘法、
3次移位乘法和7次加法），在计算上仍然会浪费相当多时间（PC上的乘法约为
加法的近20倍，移位乘法则和加法相当），因此有必要再予以化简。如何简化
呢？由上述公式可发现，主要的乘法来自于i^3的计算，因此欲将之简化的最简
单的方式便是由前一个m1～m4值来求得后一个m1～m4值，藉此消减掉这个三次
方值的运算：

m1(i+1) = m1(i) + 6*i^2 + 6*i + 2 - 3*n*(2*i+1)
m2(i+1) = m2(i) - 6*i^2 - 6*i - 2 + 3*n*(2*i+1)
m3(i+1) = m3(i) + 3*i^2 + 3*i + 1 - 2*n*(2i+1) + n^2
m4(i+1) = m4(i) + 3*i^2 + 3*i + 1 - n*(2*i+1)

现在便是要化简各式中后面的计算项次。由于这些项次有相当多的重复，故可
将之写成：

m1(i+1) = m1(i) + a
m2(i+1) = m2(i) - a
m3(i+1) = m3(i) + d - c + n^2
m4(i+1) = m4(i) + d
a = 2*b - 3*c
b = 3*i^2 + 3*i + 1
c = n*(2*i+1)
d = b-c

再进一步简化为：

e = 2*i + 1
c = n*e
b = 3*i^2 + 3*i + 1
= (3*i+1)*i + (2*i+1)
= (e+i)*i + e

整理一下成为（依计算顺序）：

e = 2*i + 1
b = (e+i)*i + e
c = n*e
d = b-c
m4 = m4 + d
f = d-c
m3 = m3 + f + n^2
a = d + f
m2 = m2 - a
m1 = m1 + a

共计2次乘法、1次移位乘法和11次加法，等于是以两次加法代替了两次乘法，
其速度必然较快。记得m1～m4的初值为：

m1(0) = n^3
m2(0) = m3(0) = m4(0) = 0

接下来我们要探讨一下模拟线数n的问题。倒底取多少模拟线数较为恰当？
采用的仿真线数太少，曲线将不够平滑，但若模拟线数太多，曲线绘制速度又
会太慢。据作者实际的测试，一般取n=20以上曲线便已相当平滑，但对于弯度
太大的曲线，其转折处仍约略可见，不过并不严重。由于在绘制曲线时，大都
以整数来运算（为求速度），因此仿真线数最好不要超出32，以避免运算结果
超出整数运算的值域。以下便是Hermite曲线和Bezier曲线的绘制程式：


#define Iterative 24 /* 曲线仿真的线数(必须小于32) */
#define Iterative2 (Iterative*Iterative)
#define Iterative3 (Iterative2*Iterative)

void DrawHermiteCurve(int x1,int y1,int x2,int y2,int xr1,int yr1,
int xr2,int yr2)
{
/* ------------------------------------------------------------
作用：画出Hermite曲线
输入：x1,y1,x2,y2 = 曲线端点
xr1,yr1,xr2,yr2 = 曲线两参考向量
作者：邱奕南 Chi'u I-Nan
------------------------------------------------------------ */
int i, oldx, oldy, m1, m2, m3, m4, x, y, k1, k2;

oldx = x1;
oldy = y1;
m1 = Iterative3;
m2 = m3 = m4 = 0;
for (i=0; i<Iterative; i++) /* 用Iterative条直线仿真 */
{
k1 = (i << 1) + 1;
k2 = (k1+i)*i + k1;
m4 += (k2 -= (k1 *= Iterative));
m3 += (k1 = k2 - k1) + Iterative2;
m2 -= (k2 += k1);
m1 += k2;
x = (int) (((long) x1*m1 + (long) x2*m2 + (long) xr1*m3 +
(long) xr2*m4) / Iterative3);
y = (int) (((long) y1*m1 + (long) y2*m2 + (long) yr1*m3 +
(long) yr2*m4) / Iterative3);
DrawLine(oldx,oldy,x,y);
oldx = x;
oldy = y;
}
}

void DrawBezierCurve(int x1,int y1,int x2,int y2,int xr1,int yr1,
int xr2,int yr2)
{
/* ------------------------------------------------------------
作用：画出Bezier曲线
输入：x1,y1,x2,y2 = 曲线端点
xr1,yr1,xr2,yr2 = 曲线两参考点
作者：邱奕南 Chi'u I-Nan
------------------------------------------------------------ */
DrawHermiteCurve(x1,y1,x2,y2,3*(xr1-x1),3*(yr1-y1),3*(x2-xr2),3*(y2-yr2));
}

＊ 青衫诗客 -- 小邱 ＊

-- Via 中文银版快信 V2.28C
! Origin: 档案货柜, 欢迎您来挖宝, ２８８００ BPS, 04-230-2080; (90:2010/622)
________________________________________
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
≡ 何陋居 ≡ 中学生以伏案读书为主, 大学生则应起而高瞻远瞩。 Whitehead.
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --