贝塞尔曲线算法

时间：2021-05-25 05:46:44
Bezier曲线很常用，一般2D绘图软件里都有。比如photoshop，flash之类。<br>它背后的原理简单的超乎想象，体现了数学的美妙。</p>
<p>先从简单的开始，两个点之间进行线性插值。</p>
<p> 贝塞尔曲线算法<br>很容易理解，可以得到</p>
<p align="center"><img src="http://s.wordpress.com/latex.php?latex=%20B%28t%29%3DP_0%2Bt%28P_1-P_0%29%3D%281-t%29P_0%2BtP_1%2Ct%5Cin%5B0%2C1%5D%20&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt=" B(t)=P_0+t(P_1-P_0)=(1-t)P_0+tP_1,t\in[0,1] " title=" B(t)=P_0+t(P_1-P_0)=(1-t)P_0+tP_1,t\in[0,1] " class="latex"></p>
<p>当然这是最简单的情形，如果扩展到三个点该如何插值呢？</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Bezier_2_big.png/240px-Bezier_2_big.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 320px; height: 133px;" src="http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Bezier_2_big.png/240px-Bezier_2_big.png" alt="" id="Bezier_2_big.gif" border="0"></a><br>从上面图片上可以看到，可以分成三步，从P0到P1进行上面的一维情形，得到点Q0，再从P1到P2，得到Q1，那么就有</p>
<p align="center">
<img src="http://s.wordpress.com/latex.php?latex=Q_0%3D%281-t%29P_0%2BtP_1&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="Q_0=(1-t)P_0+tP_1" title="Q_0=(1-t)P_0+tP_1" class="latex"><br>
<img src="http://s.wordpress.com/latex.php?latex=Q_1%3D%281-t%29P_1%2BtP_2&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="Q_1=(1-t)P_1+tP_2" title="Q_1=(1-t)P_1+tP_2" class="latex">

</p>
<p>然后再对Q0和Q1进行线性插值，得到点B</p>
<p align="center">
<img src="http://s.wordpress.com/latex.php?latex=B%3D%281-t%29Q_0%2BtQ_1%3D%281-t%29%5E2P_0%2B2t%281-t%29P_1%2Bt%5E2P_2&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="B=(1-t)Q_0+tQ_1=(1-t)^2P_0+2t(1-t)P_1+t^2P_2" title="B=(1-t)Q_0+tQ_1=(1-t)^2P_0+2t(1-t)P_1+t^2P_2" class="latex">
</p>
<p>t从0到1增加，就得到了一条曲线，如下图</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://upload.wikimedia.org/wikipedia/commons/2/2d/Bezier_2_big.gif"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 320px; height: 133px;" src="http://upload.wikimedia.org/wikipedia/commons/2/2d/Bezier_2_big.gif" alt="" id="Bezier_2_big.gif" border="0"></a><br>同样可以推广到四个点的情形，这样的曲线中，t的最高幂是三次。三次样条曲线用的最多，因为它提供了足够的可控制性和满足大部分场合的精度，同时又保持了相对的简单。<br>依照上面的方法，可以得到三次的情形</p>
<p align="center">
<img src="http://s.wordpress.com/latex.php?latex=B%28t%29%3D%281-t%29%5E3P_0%2B3%281-t%29%5E2tP_1%2B3%281-t%29t%5E2P_2%2Bt%5E3P_3%2Ct%5Cin%5B0%2C1%5D&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="B(t)=(1-t)^3P_0+3(1-t)^2tP_1+3(1-t)t^2P_2+t^3P_3,t\in[0,1]" title="B(t)=(1-t)^3P_0+3(1-t)^2tP_1+3(1-t)t^2P_2+t^3P_3,t\in[0,1]" class="latex">
</p>
<p>这个时候可以注意到Pi点前面的系数，是不是似曾相识？没错，就是二项式公式。可以看成是相应次幂的<img src="http://s.wordpress.com/latex.php?latex=%281-t%2Bt%29%5En&amp;bg=ffffff&amp;fg=000000&amp;s=0" alt="(1-t+t)^n" title="(1-t+t)^n" class="latex">的展开。这个系数叫做Bernstein多项式。</p>

<p>最常用的三次曲线如下图，其中中间的两个就是控制点，在一些绘图软件里用钢笔拖出来的两条调整曲线形状的直线，就是调节中间两个点的位置。</p>
<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://upload.wikimedia.org/wikipedia/commons/f/ff/Bezier_3_big.gif"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 320px; height: 133px;" src="http://upload.wikimedia.org/wikipedia/commons/f/ff/Bezier_3_big.gif" alt="" id="BLOGGER_PHOTO_ID_5324424277818284530" border="0"></a><br>推广到任意中n的情况</p>
<p align="center">
<img src="http://s.wordpress.com/latex.php?latex=B%28t%29%3D%5Csum_%7Bi%3D0%7D%5E%7Bn%7D%7B%5Cbinom%7Bn%7D%7Bi%7D%281-t%29%5E%7Bn-i%7Dt%5EiP_i%7D&amp;bg=ffffff&amp;fg=000000&amp;s=2" alt="B(t)=\sum_{i=0}^{n}{\binom{n}{i}(1-t)^{n-i}t^iP_i}" title="B(t)=\sum_{i=0}^{n}{\binom{n}{i}(1-t)^{n-i}t^iP_i}" class="latex">
</p>
<p align="center">
<img src="http://s.wordpress.com/latex.php?latex=%3D%281-t%29%5EnP_0%2B%5Cbinom%7Bn%7D%7B1%7D%281-t%29%5E%7Bn-1%7DtP_1%2B..%2Bt%5EnP_n%2Ct%5Cin%5B0%2C1%5D&amp;bg=ffffff&amp;fg=000000&amp;s=1" alt="=(1-t)^nP_0+\binom{n}{1}(1-t)^{n-1}tP_1+..+t^nP_n,t\in[0,1]" title="=(1-t)^nP_0+\binom{n}{1}(1-t)^{n-1}tP_1+..+t^nP_n,t\in[0,1]" class="latex">
</p>
<p>不过n大于3的时候就很少用了，除非在一些要求比较高的场合，比如飞机汽车线形的设计。</p>
<p>更多的资料，可以看这里<br><a href="http://en.wikipedia.org/wiki/B%C3%A9zier_curve">http://en.wikipedia.org/wiki/B%C3%A9zier_curve</a>

原文链接 http://blog.lipte.com/archives/54

8 个解决方案

#1

Mark...........

#2

Lz想干什么？

#3

you有点深奥，，看不明白，

#4

贴过来好像格式有问题，感觉这篇文章解释的挺透彻的

#5

这个不错

#6

这个在研究生阶段《计算机图形学》课程里面会有深入的讲解。楼主的给出的页面只是形象化的展示，理论层面还是很浅薄的。根本没有介绍besier曲线的数学性质、局限，以及用途等。

#7

#ifndef __Bezier_H_2010_09_14_
#define __Bezier_H_2010_09_14_
//绘制贝赛尔曲线
class POINT_3D
{
public:
float x,y,z;
};
class GREATUI_EXT_DLL CBezier
{
public:
CBezier();
virtual ~CBezier();

private:
//输入 N，输出二项式系数 C
void binomialCoeffs(IN int n,OUT int *c);
//输入u 0~1 控制点 和二项式系数 输出 点坐标
void computeBezPt(IN float u,OUT POINT_3D &bezPt,IN int nCtrlPts,IN POINT_3D * ctrlPts,IN int *c);
//ctrlPts 控制点数组，nCtrlPts 控制点个数=控制点数组大小-1
public:
void bezier(IN POINT_3D *ctrlPts,IN int nCtrlPts,IN int nBezCurvePts);

public:
vector<POINT_3D> m_vecOutputPoint3D;
};
#endif
#include "StdAfx.h"
#include "Bezier.h"
#include <math.h>
CBezier::CBezier()
{

}
CBezier::~CBezier()
{

}
//输入 N，输出二项式系数 C
void CBezier::binomialCoeffs(IN int n,OUT int *c)
{
int k,j;
for(k=0;k<=n;k++)
{
c[k]=1;
for(j=n;j>=k+1;j--)
{
c[k]*=j;
}
for(j=n-k;j>=2;j--)
{
c[k]/=j;
}
}
}
//输入u 0~1 控制点 和二项式系数 输出 点坐标
void CBezier::computeBezPt(IN float u,OUT POINT_3D &bezPt,IN int nCtrlPts,IN POINT_3D * ctrlPts,IN int *c)
{
int k,n=nCtrlPts-1;
float bezBlendFcn;

bezPt.x=bezPt.y=bezPt.z=0;

for(k=0;k<nCtrlPts;k++)
{

bezBlendFcn=c[k]*pow(u,k)*pow(1-u,n-k);
bezPt.x+=ctrlPts[k].x*bezBlendFcn;
bezPt.y+=ctrlPts[k].y*bezBlendFcn;
bezPt.z+=ctrlPts[k].z*bezBlendFcn;
}

}
//
void CBezier::bezier(IN POINT_3D *ctrlPts,IN int nCtrlPts,IN int nBezCurvePts)
{
POINT_3D bezCurvePt;
float u;
int *c,k;
c=new int[nCtrlPts];
binomialCoeffs(nCtrlPts-1,c);
for(k=0;k<=nBezCurvePts;k++)
{
u=float(k)/float(nBezCurvePts);
computeBezPt(u,bezCurvePt,nCtrlPts,ctrlPts,c);
//输出 x,y,z 的坐标
m_vecOutputPoint3D.push_back(bezCurvePt);
}
}


调用 前面的类生成的贝塞尔曲线。
void OnPaint(HDC hdc,HWND hWnd)
{
int nCtrlPts,nBezCurvePts=78;
//POINT_3D ctrlPts[5]=
//{
// {-40.0,-40.0,0.0},{-10.0,200.0,0.0},
// {10.0,-200.0,0.0},{40.0,40.0,0.0},{70.0,0.0}
//};
//  POINT_3D ctrlPts[]=
//  {
//  {8,78,128},{5,39,78},
//  {6,43,83},{8,66,110},{9,70,116},{12,96,148},
//  {12,105,161},{20,98,126}
//  };
POINT_3D ctrlPts[]=
{
{0,0,0},{0,255,0},
{0,0,255},{255,255,255},
{
128,128,0
}

//,{8,66,110},{9,70,116},{12,96,148},
//{12,105,161},{20,98,126}
};

nCtrlPts=sizeof(ctrlPts)/sizeof(POINT_3D);
int i;
for(i=0;i<nCtrlPts;i++)
{
int h,s,l;
RGB2HSL(ctrlPts[i].x,ctrlPts[i].y,ctrlPts[i].z,h,s,l);
ctrlPts[i].x=h;ctrlPts[i].y=s;ctrlPts[i].z=l;
}
Bitmap *pBmp=new Bitmap(1,nBezCurvePts);

CBezier bezier;
bezier.bezier(ctrlPts,nCtrlPts,nBezCurvePts);
vector<POINT_3D>::iterator it;
int num=nBezCurvePts-1;
for(it=bezier.m_vecOutputPoint3D.begin();it!=bezier.m_vecOutputPoint3D.end();it++)
{
POINT_3D p3d=*it;
HSL_GREATUI hsl((int)p3d.x,(int)p3d.y,(int)p3d.z);
Color cccc;
hsl.GetARGB(255,&cccc);
pBmp->SetPixel(0,num--,cccc);
//SetPixel(hdc,p3d.x,p3d.y,RGB(255,p3d.z,0));
}


Graphics g(hdc);
for(i=0;i<nBezCurvePts;i++)
{
g.DrawImage(pBmp,i,10);
}
delete pBmp;
}

#8

引用 6 楼 lisunlin0 的回复:
这个在研究生阶段《计算机图形学》课程里面会有深入的讲解。楼主的给出的页面只是形象化的展示，理论层面还是很浅薄的。根本没有介绍besier曲线的数学性质、局限，以及用途等。

高手，给介绍介绍，我学习学习。
市面上没有你说的深层次的。

#1

Mark...........

#2

Lz想干什么？

#3

you有点深奥，，看不明白，

#4

贴过来好像格式有问题，感觉这篇文章解释的挺透彻的

#5

这个不错

#6

这个在研究生阶段《计算机图形学》课程里面会有深入的讲解。楼主的给出的页面只是形象化的展示，理论层面还是很浅薄的。根本没有介绍besier曲线的数学性质、局限，以及用途等。

#7

#ifndef __Bezier_H_2010_09_14_
#define __Bezier_H_2010_09_14_
//绘制贝赛尔曲线
class POINT_3D
{
public:
float x,y,z;
};
class GREATUI_EXT_DLL CBezier
{
public:
CBezier();
virtual ~CBezier();

private:
//输入 N，输出二项式系数 C
void binomialCoeffs(IN int n,OUT int *c);
//输入u 0~1 控制点 和二项式系数 输出 点坐标
void computeBezPt(IN float u,OUT POINT_3D &bezPt,IN int nCtrlPts,IN POINT_3D * ctrlPts,IN int *c);
//ctrlPts 控制点数组，nCtrlPts 控制点个数=控制点数组大小-1
public:
void bezier(IN POINT_3D *ctrlPts,IN int nCtrlPts,IN int nBezCurvePts);

public:
vector<POINT_3D> m_vecOutputPoint3D;
};
#endif
#include "StdAfx.h"
#include "Bezier.h"
#include <math.h>
CBezier::CBezier()
{

}
CBezier::~CBezier()
{

}
//输入 N，输出二项式系数 C
void CBezier::binomialCoeffs(IN int n,OUT int *c)
{
int k,j;
for(k=0;k<=n;k++)
{
c[k]=1;
for(j=n;j>=k+1;j--)
{
c[k]*=j;
}
for(j=n-k;j>=2;j--)
{
c[k]/=j;
}
}
}
//输入u 0~1 控制点 和二项式系数 输出 点坐标
void CBezier::computeBezPt(IN float u,OUT POINT_3D &bezPt,IN int nCtrlPts,IN POINT_3D * ctrlPts,IN int *c)
{
int k,n=nCtrlPts-1;
float bezBlendFcn;

bezPt.x=bezPt.y=bezPt.z=0;

for(k=0;k<nCtrlPts;k++)
{

bezBlendFcn=c[k]*pow(u,k)*pow(1-u,n-k);
bezPt.x+=ctrlPts[k].x*bezBlendFcn;
bezPt.y+=ctrlPts[k].y*bezBlendFcn;
bezPt.z+=ctrlPts[k].z*bezBlendFcn;
}

}
//
void CBezier::bezier(IN POINT_3D *ctrlPts,IN int nCtrlPts,IN int nBezCurvePts)
{
POINT_3D bezCurvePt;
float u;
int *c,k;
c=new int[nCtrlPts];
binomialCoeffs(nCtrlPts-1,c);
for(k=0;k<=nBezCurvePts;k++)
{
u=float(k)/float(nBezCurvePts);
computeBezPt(u,bezCurvePt,nCtrlPts,ctrlPts,c);
//输出 x,y,z 的坐标
m_vecOutputPoint3D.push_back(bezCurvePt);
}
}


调用 前面的类生成的贝塞尔曲线。
void OnPaint(HDC hdc,HWND hWnd)
{
int nCtrlPts,nBezCurvePts=78;
//POINT_3D ctrlPts[5]=
//{
// {-40.0,-40.0,0.0},{-10.0,200.0,0.0},
// {10.0,-200.0,0.0},{40.0,40.0,0.0},{70.0,0.0}
//};
//  POINT_3D ctrlPts[]=
//  {
//  {8,78,128},{5,39,78},
//  {6,43,83},{8,66,110},{9,70,116},{12,96,148},
//  {12,105,161},{20,98,126}
//  };
POINT_3D ctrlPts[]=
{
{0,0,0},{0,255,0},
{0,0,255},{255,255,255},
{
128,128,0
}

//,{8,66,110},{9,70,116},{12,96,148},
//{12,105,161},{20,98,126}
};

nCtrlPts=sizeof(ctrlPts)/sizeof(POINT_3D);
int i;
for(i=0;i<nCtrlPts;i++)
{
int h,s,l;
RGB2HSL(ctrlPts[i].x,ctrlPts[i].y,ctrlPts[i].z,h,s,l);
ctrlPts[i].x=h;ctrlPts[i].y=s;ctrlPts[i].z=l;
}
Bitmap *pBmp=new Bitmap(1,nBezCurvePts);

CBezier bezier;
bezier.bezier(ctrlPts,nCtrlPts,nBezCurvePts);
vector<POINT_3D>::iterator it;
int num=nBezCurvePts-1;
for(it=bezier.m_vecOutputPoint3D.begin();it!=bezier.m_vecOutputPoint3D.end();it++)
{
POINT_3D p3d=*it;
HSL_GREATUI hsl((int)p3d.x,(int)p3d.y,(int)p3d.z);
Color cccc;
hsl.GetARGB(255,&cccc);
pBmp->SetPixel(0,num--,cccc);
//SetPixel(hdc,p3d.x,p3d.y,RGB(255,p3d.z,0));
}


Graphics g(hdc);
for(i=0;i<nBezCurvePts;i++)
{
g.DrawImage(pBmp,i,10);
}
delete pBmp;
}

#8

引用 6 楼 lisunlin0 的回复:
这个在研究生阶段《计算机图形学》课程里面会有深入的讲解。楼主的给出的页面只是形象化的展示，理论层面还是很浅薄的。根本没有介绍besier曲线的数学性质、局限，以及用途等。

高手，给介绍介绍，我学习学习。
市面上没有你说的深层次的。
标签：

相关文章