唐磊的个人博客

Bezier曲线曲面算法

发表于 | 分类于 |

将按照如下目录记录在学习bezier曲线曲面的相关知识.

  1. Bezier曲线
    • 定义
    • Bernstein基函数的性质
    • Bezier曲线性质
    • de Casteljau算法
    • 直接法
  2. Bezier曲面
    • 定义
    • Bezier曲面性质
    • 算法

一. Bezier曲线

1. 定义

clip_image002

clip_image004其中,C__(_t_) 称为Bezier曲线,Bi,n(_t_) 称为Bernstein基函数,P_i_ 称为控制顶点;

2 . Bernstein基函数的性质

1) 非负性

clip_image002[5]

2) 权性(1**的1**个划分)

clip_image002[8]

clip_image002[10](根据二项式定理)

3) 对称性

clip_image002[12]

4) 最大值

对于i=1,2,…, (n-1), Bi,n(t)在区间[0, 1]上的最大值只能在一点处取得, 即: clip_image002[14]

5) 收敛性 (Weierstrass**第一定理, 1885)**

对于任意的函数f(t) ∈C1[0,1],

clip_image002[16]

6) 递推性

Bi,n(_t_)=(1-_t_)Bi,n-1(_t_)+tBi-1,n-1(_t_)

即高一次的Bernstein基函数可由两个低一次的Bernstein调和函数线性组合而成。

3. Bezier曲线性质

1) 端点插值性

clip_image002[18]**

2) 端点切向量

clip_image004[5]

Bezier曲线在起点处的切线位于前两个控制点的连线上，而终点处的切线位于最后两个控制点的连线上，即曲线起点和终点处的切线方向与起始折线段和终止折线段的切线方向一致.

3) 导数性质

clip_image006 其中: ΔP_i_=P_i+1-Pi_

导数可以通过差分表示

4) 对称性

Bernstein基函数的对称性

5) 凸包性

Bezier曲线各点均落在控制多边形各顶点构成的凸包之中，这里的凸包指的是包含所有顶点的最小凸多边形。Bezier曲线的凸包性保证了曲线随控制点平稳前进而不会振荡。**

6) 几何不变性

Bezier曲线的形状仅与控制多边形各顶点的相对位置有关，而与坐标系的选择无关，即具有几何不变性。

7) 变差缩减性

Bezier曲线的变差减少性是指如果控制多边形是一个平面图形，则该平面内的任意直线与该Bezier曲线的交点个数不多于该直线与控制多边形的交点个数；如果控制多边形不是平面图形，则任意平面与Bezier曲线的交点个数不会超过它与控制多边形的交点个数。变差减少性反映了Bezier曲线比控制多边形波动得少，即比控制多边形更加光滑。

4. de Casteljau算法

计算Bezier曲线上一点C(t)

decasteljau算法

具体而言，实现可以用递归如下：

CP_Vector2D getBezierPoint(vector<CP_Vector2D> controlPoints, double t, int i, int j)
{
	if (j == 0)
	{
		return controlPoints[i];
	}
	return getBezierPoint(controlPoints, t, i-1, j-1) * (1-t)+ getBezierPoint(controlPoints, t, i, j-1) * t;
}

后来实验发现，递归算法太慢，换成非递归，效果明显好转。

CP_Vector2D getBezierPointNotRecurrent(vector<CP_Vector2D> controlPoints, double t)
{
	vector<CP_Vector2D> tempPoints(controlPoints);
	for (unsigned int i = 1; i <= tempPoints.size(); i++){
		for (unsigned int j = 0; j < tempPoints.size()-i; j++)
			tempPoints[j] = tempPoints[j] * (1-t) + tempPoints[j+1] * t; 
	}
	return tempPoints[0];
}

代码见https://github.com/tl3shi/cagd/tree/master/task3(说明，配图为当前代码演示结果，你现在看到的代码运行结果不是下面展示得到图片)效果如图.

bezier曲线,控制点

5. 直接法

直接通过上面的定义计算出每个点，然后再画出来。如下所示：

const int maxControlPoint = 4;
	CP_Vector2D controlPoints[maxControlPoint];
	controlPoints[0] = CP_Vector2D(0.0, 0.0);
	controlPoints[1] = CP_Vector2D(1.0, 3.0);
	controlPoints[2] = CP_Vector2D(2.0, 1.0);
	controlPoints[3] = CP_Vector2D(3.0, 3.0);
	
	glColor3d(1.0, 0, 0);
	glBegin(GL_LINE_STRIP);
	double t = 0;
	for (unsigned int i = 0; i < besierSegment; i++)
	{
		t += 1.0/besierSegment;
		CP_Vector2D p = getBezierPoint(controlPoints, t, 3, 3);
		glVertex2d(p.m_x / 10, p.m_y / 10);
	}
	glEnd();
	
	glLoadIdentity();
	glTranslated(-0.5, 0.0, 0.0);   
	glColor3d(1.0, 0, 1.0);
	glBegin(GL_LINE_STRIP);
	t = 0;
	for (unsigned int i = 0; i < besierSegment; i++)
	{
		t += 1.0/besierSegment;
		CP_Vector2D p;
		for (unsigned kk = 0 ; kk < maxControlPoint; kk++) 
		{
			p += controlPoints[kk] * B(kk, 3, t);
		}

		glVertex2d(p.m_x / 10, p.m_y / 10);
	}

	glEnd();
	glFlush();

结果如图：

bezier curve

二、Bezier曲面

1、定义

clip_image002[20]

其中，clip_image004[7] **,S(_u_,_v_)称为Bezier曲面，Bi,n(_t_)称为Bernstein基函数，P_i_,j称为控制顶点。

2. bezier曲面性质

1) 角点性质

Bezier曲面特征网格的四个角点正好是Bezier曲面的四个角点。S(0,0)=P0,0,S(0,1)=P0,n,S(1,0)=P_m,0,S(1,1)=Pm_,n.

2) 边界线

Bezier曲面特征网格最外一圈顶点定义Bezier曲面的四条边界：S(0,v),S(1,v),S(u,0)S(u,1)

3) 凸包性、对称性、几何不变性等

3. Bezier曲面算法

可以对定义的公式进行如下的变化

Bezier曲面算法

clip_image004[9]

Bezier曲面算法

Bezier曲面算法

de Casteljau算法：参考http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/surface/bezier-de-casteljau.html

Input: a m+1 rows and n+1 columns of control points and (u,v). 
Output: point on surface p(u,v) 
Algorithm: 
for i := 0 to m do 
begin 
    Apply de Casteljau's algorithm to the i-th row of control points with v; 
    Let the point obtained be qi(v); 
end
Apply de Casteljau's algorithm to q0(v), q1(v), ..., qm(v) with u; 
The point obtained is p(u,v);

想像Bezier曲面由bezier曲线拼接而成，可以先把点给求出来。

besierSegment = 30;
	const int uNum = 30, vNum = 30;
	CP_Vector3D bezierPoints [uNum][vNum];

	for (unsigned int u = 0; u < uNum; u++)
	{
		t = u * 1.0 / besierSegment;
		vector<CP_Vector3D> newControl;
		for (unsigned int k = 0; k < 4; k++)
		{
			CP_Vector3D p = getBezierPointNotRecurrent(controlPoints[k], t);
			newControl.push_back(p);
		}
		
		glBegin(GL_LINE_STRIP);
		for (unsigned int v = 0; v < vNum; v++)
		{
			t = v * 1.0 / besierSegment;
			CP_Vector3D p = getBezierPointNotRecurrent(newControl, t);
			glVertex3d(p.m_x / 1.0, p.m_y / 1.0, p.m_z / 1.0);
			bezierPoints[u][v] = p;
		}
		glEnd();
	}

上面把一条条bezier曲线给画出来了，并求出bezier曲面上的点。然后通过四边形(三角形也可以)拼接出来即可，如下图：

bezier曲面拼接

相邻的4个点构成四边形，分别是bezierPoints[u][v]，[u+1][v]，[u+1][v+1]，[u][v+1]，遍历即可得到。

for (unsigned u = 0; u < uNum -1; u++)
	{
		for(unsigned v = 0; v < vNum - 1; v++ )
		{  
			glBegin(GL_QUADS);
			CP_Vector3D p = bezierPoints[u][v];
			glVertex3d(p.m_x / 1.0, p.m_y / 1.0, p.m_z / 1.0);
			p = bezierPoints[u+1][v];
			glVertex3d(p.m_x / 1.0, p.m_y / 1.0, p.m_z / 1.0);
			p = bezierPoints[u+1][v+1];
			glVertex3d(p.m_x / 1.0, p.m_y / 1.0, p.m_z / 1.0);
			p = bezierPoints[u][v+1];
			glVertex3d(p.m_x / 1.0, p.m_y / 1.0, p.m_z / 1.0);
			glEnd();
		}
	}

优化的话，求法向量，加点颜色之类的可以更好看。

bezier曲面

本例结果如上图所示，左边是最后画出的bezier曲面，右边红色的是由控制顶点连线构成的，灰色的是多条bezier曲线构成。参考程序见https://github.com/tl3shi/cagd/tree/master/task4 (说明，程序可能会修改，记录本文时结果如上图所示)。

tanglei wechat
欢迎扫码加入互联网大厂内推群 & 技术交流群，一起学习、共同进步