计算机图形学-201005070214.docx

计算机图形学课程设计报告Bezier曲线的算法实现学号：姓名：学院：信息科学与技术学院指导教师：邓飞学校：成都理工大学一、 选题的一样及目的：贝塞尔曲线就是这样的一条曲线，它是依据四个位置任意的点坐标绘制出的一条光滑曲线。在历史上，研究贝塞尔曲线的人最初是按照已知曲线参数方程来确定四个点的思路设计出这种矢量曲线绘制法。贝塞尔曲线的有趣之处更在于它的“皮筋效应”，也就是说，随着点有规律地移动，曲线将产生皮筋伸引一样的变换，带来视觉上的冲击。1962年，法国数学家Pierre Bzier第一个研究了这种矢量绘制曲线的方法，并给出了详细的计算公式，因此按照这样的公式绘制出来的曲线就用他的姓氏来命名是为贝塞尔曲线。由于用计算机画图大部分时间是操作鼠标来掌握线条的路径，与手绘的感觉和效果有很大的差别。即使是一位精明的画师能轻松绘出各种图形，拿到鼠标想随心所欲的画图也不是一件容易的事。这一点是计算机万万不能代替手工的工作，所以到目前为止人们只能颇感无奈。使用贝塞尔工具画图很大程度上弥补了这一缺憾。贝塞尔曲线贝塞尔曲线是计算机图形图像造型的基本工具，是图形造型运用得最多的基本线条之一。它通过控制曲线上的四个点（起始点、终止点以及两个相互分离的中间点）来创造、编辑图形。其中起重要作用的是位于曲线中央的控制线。这条线是虚拟的，中间与贝塞尔曲线交叉，两端是控制端点。移动两端的端点时贝塞尔曲线改变曲线的曲率（弯曲的程度）；移动中间点（也就是移动虚拟的控制线）时，贝塞尔曲线在起始点和终止点锁定的情况下做均匀移动。注意，贝塞尔曲线上的所有控制点、节点均可编辑。这种“智能化”的矢量线条为艺术家提供了一种理想的图形编辑与创造的工具。它的主要意义在于无论是直线或曲线都能在数学上予以描述。通过本次课程设计使我们对贝塞尔曲线更加熟悉！二、 方法原理及关键技术：（1）原理：贝塞尔曲线于1962年，由法国工程师皮埃尔贝塞尔（PierreBzier）所广泛发表，他运用贝塞尔曲线来为汽车的主体进行设计。贝塞尔曲线最初由PauldeCasteljau于1959年运用deCasteljau算法开发，以稳定数值的方法求出贝塞尔曲线。线性贝塞尔曲线给定点P0、P1，线性贝塞尔曲线只是一条两点之间的直线。这条线由下式给出：且其等同于线性插值。二次方贝塞尔曲线的路径由给定点P0、P1、P2的函数B(t)追踪：TrueType字型就运用了以贝塞尔样条组成的二次贝塞尔曲线。P0、P1、P2、P3四个点在平面或在三维空间中定义了三次方贝塞尔曲线。曲线起始于P0走向P1，并从P2的方向来到P3。一般不会经过P1或P2；这两个点只是在那里提供方向资讯。P0和P1之间的间距，决定了曲线在转而趋进P3之前，走向P2方向的“长度有多长”。曲线的参数形式为：现代的成象系统，如PostScript、Asymptote和Metafont，运用了以贝塞尔样条组成的三次贝塞尔曲线，用来描绘曲线轮廓。一般化：P0、P1、Pn，其贝塞尔曲线即。 例如 ：。 如上公式可如下递归表达： 用 表示由点 P0、P1、Pn 所决定的贝塞尔曲线。则用平常话来说， 阶贝塞尔曲线之间的插值。一些关于参数曲线的术语，有即多项式又称作 n 阶的伯恩斯坦基底多项式，定义 00 = 1。点 Pi 称作贝塞尔曲线的控制点。多边形以带有线的贝塞尔点连接而成，起始于 P0 并以 Pn 终止，称作贝塞尔多边形（或控制多边形）。贝塞尔多边形的凸包（convex hull）包含有贝塞尔曲线。线性贝塞尔曲线函数中的 t 会经过由 P0 至P1 的 B(t) 所描述的曲线。例如当 t=0.25 时，B(t) 即一条由点 P0 至 P1 路径的四分之一处。就像由 0 至 1 的连续 t，B(t) 描述一条由 P0 至 P1 的直线。为建构二次贝塞尔曲线，可以中介点 Q0 和 Q1 作为由 0 至 1 的 t： 由 P0 至 P1 的连续点 Q0，描述一条线性贝塞尔曲线。 由 P1 至 P2 的连续点 Q1，描述一条线性贝塞尔曲线。 由 Q0 至 Q1 的连续点 B(t)，描述一条二次贝塞尔曲线。 为建构高阶曲线，便需要相应更多的中介点。对于三次曲线，可由线性贝塞尔曲线描述的中介点 Q0、Q1、Q2，和由二次曲线描述的点 R0、R1 所建构：对于四次曲线，可由线性贝塞尔曲线描述的中介点 Q0、Q1、Q2、Q3，由二次贝塞尔曲线描述的点 R0、R1、R2，和由三次贝塞尔曲线描述的点 S0、S1 所建构：P(t)=(1-t)P0+tP1 , 。矩阵表示为：P(t)=(1-t)2P0+2t(1-t)P1+t2P2, 。矩阵表示为：P(t)=(1-t)3P0+3t(1-t)2P1+3t2(1-t)P2+t3P3 。三次B样条曲线的算法实现：从三次B样条曲线的定义可知：当n=3时，3 l=0Qi,3(t)=Pi+l Fl,3(t)= Pi F0,3(t)+ Pi+1 F1,3(t)+ Pi+2 F2,3(t)+ Pi+ 3 F3,3(t) 因为四个调和函数F0,3(t)、F1,3(t)、F2,3(t)和F3,3(t) 已知（参看公式7-5-3）因此只要给出四个控制点的位置矢量的坐标，当t在0，1范围内取离散地取100个点时（dt=0.01），分别求出每一个曲线上点，相邻点用直线段连接起来，就可以得到相应的B样条曲线。设控制点的个数为PointNum，要求PointNum4，则可以生成（PointNum-3）段三次B样条曲线。其中第i段三次B样条曲线的代数形式为：Qi,3(t)x= Pi x F0,3(t)+ P (i+1) x F1,3(t)+ P (i+2) x F2,3(t)+ P (i+3) x F3,3(t)Qi,3(t)y= Pi y F0,3(t)+ P (i+1) y F1,3(t)+ P (i+2) y F2,3(t)+ P (i+3) y F3,3(t)其中，i=1,2, PointNum-3三、 程序设计和实现：Bezier曲线的C语言算法描述如下：#include #include void computeCoefficients(int n, int *c) int k, i; for (k=0;k=k+1; i-) /*求ck=n*(n-1)(k+1) */ ck*=i; for (i=n-k; i=2; i-) /*求ck/(n-k)!*/ ck/=i; void computepoint(float t,wcPt3 *pt,int ncontrols,wcPt3 *controls,int *c) int i, n=ncontrols-1; float blend; pt-x=0.0; pt-y=0.0; pt-z=0.0; for (i=0; ix+=controlsi.x*blend; /*求x(t)*/ pt-y+=controlsi.y*blend; /*求y(t)*/ pt-z+=controlsi.z*blend; /*求z(t)*/ void Bezier(wcPt3 *controls, int ncontrols, int m, wcPt3 *curve) int *c=(int *) malloc(ncontrols *sizeof(int);int i;computecoefficients(ncontrols-1,c);for (i=0; i=m; i+)computepoint(i/(float)m,&curvei,ncontrols,controls,c);free(c); 在主程序中提供特征多边形的各个顶点坐标放入controls数组中，ncontrols为顶点的个数，m为曲线上取的样点数，比如m=100表示取100个样点。计算出曲线上的各个样点坐标放入curve数组中，这样可以通过相邻点连线绘出生成的Bezier曲线。程序实现步骤：（工程名:BezierCurve）（）C m n的函数实现，定义成成员函数，命名为Multiply_n。（m+1）(m+2)(n-1).nn! (n-m)!m!(n-m)!C mn = = int Multiply_n(int m,n) int i,j,a; if (m!=0) a=1; for (i=m+1;i=n;i+) /求（m+1）(m+2)(n-1).n a=a*i; for (j=1;j=n-m;j+) /求(n-m)!和C mn a=a/j; return a; else return 1; （）伯恩斯坦多项式Bm,n(t)的函数实现 Bm,n(t)= C mn tm(1-t)n-m Double Bernstein(int m,int n,double t) int i,j; double sum; sum=Multiply_n(m,n); /求C mn for (i=1;i=m;i+) sum=sum*t; / C mn tm for (j=1;jSelectObject(&PenBlue); pDC-MoveTo(array00,array01); for (i=0;iLineTo(arrayi0,arrayi1); /绘制Bezier曲线 pDC-MoveTo(array00,array01); /回到起点 pDC-SelectObject(&PenRed); t=0.0;for (i=0;i=(int)1/dt;i+) curx=0; cury=0; for(j=0;jLineTo(curx,cury); t=t+dt; 编译、运行后查看结果，如图1所示。t=t+dt;这时Bezier曲线的通用程序设计。通过这个程序，我们绘出二次、三次甚至高次Bezier曲线。读者可以通过修改程序来实现，并观察程序的结果。（2）三次Bezier曲线的绘制如果仅仅是绘制三次Bezier曲线，可以通过3i=0 Q(t)=PiBi,3(t) = P0B0,3(t)+ P1B1,3(t)+ P2B2,3(t)+ P3B3,3(t) ，t0,1来简化程序设计。程序如下：(工程名：Bezier) 将调和函数设计成成员函数： double CBezierView:b03(double t) return(pow(1-t,3);double CBezierView:b13(double t) return(3*t*pow(1-t,2);double CBezierView:b23(double t) return(3*(1-t)*t*t);double CBezierView:b33(double t) return(t*t*t); 在OnDraw()函数中输入下面代码：void CBezierView:OnDraw(CDC* pDC)CBezierDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/ TODO: add draw code for native data here int i; int x0,y0,x1,y1,x2,y2,x3,y3,curx,cury; double t,dt; / 创建两个不同颜色的画笔 CPen PenRed(PS_SOLID,1,RGB(255,0,0); CPen PenBlue(PS_SOLID,1,RGB(0,0,255); / 设置控制点，绘出特征多边形 x0=220;y0=10;x1=410;y1=10;x2=225;y2=150;x3=410;y3=100; pDC-SelectObject(PenBlue); /使用蓝色画笔 pDC-MoveTo(x0,y0); pDC-LineTo(x1,y1); pDC-LineTo(x2,y2); pDC-LineTo(x3,y3); /绘制Bezier曲线 pDC-MoveTo(x0,y0); t=0; dt=0.01; /t从0到1，每步增加0.01,取100个点 pDC-SelectObject(PenRed); /使用红色画笔 for (i=0;iLineTo(curx,cury); t=t+dt; 读者可以使用鼠标实现交互式绘制Bezier曲线。使用数组ControlsPoints3记录鼠标选择的P0，P1，P2，P3 四个控制点，然后根据算法，当t从0到1取100个值，分别求出Bezier曲线上的点的坐标（curx,cury）。相邻点通过直线段连接构成Bezier曲线。三次B样条曲线的算法实现(1)将调和函数定义为成员函数，函数形式如下：double CBSpringView:f03(double t) return (-pow(t,3)+3*pow(t,2)-3*t+1)/6);double CBSpringView:f13(double t) return (3*pow(t,3)-6*pow(t,2)+4)/6);double CBSpringView:f23(double t) return (-3*pow(t,3)+3*pow(t,2)+3*t+1)/6);double CBSpringView:f33(double t) return (pow(t,3)/6);（2）编写OnDraw()函数，程序如下：int n,m,pointnum,i,j;int x10,y10,curx,cury; /(xi,yi)为顶点坐标double t,dt; n=3; pointnu