计算机图形学bezier.doc

30 / 30计算机图形学课程设计报告Bezier曲线的算法实现学号：201005070214姓名：赵凯学院：信息科学与技术学院指导教师：邓飞学校：成都理工大学一、 选题的意义及目的：贝塞尔曲线就是这样的一条曲线，它是依据四个位置任意的点坐标绘制出的一条光滑曲线。在历史上，研究贝塞尔曲线的人最初是按照已知曲线参数方程来确定四个点的思路设计出这种矢量曲线绘制法。贝塞尔曲线的有趣之处更在于它的“皮筋效应”，也就是说，随着点有规律地移动，曲线将产生皮筋伸引一样的变换，带来视觉上的冲击。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+语言算法描述如下：（1） BH_BSpline.cpp#include stdafx.h#include BH_BSpline.h#include BH_BSpline:BH_BSpline(int Row, int Column, int uOrder, int vOrder, int utype, int vtype, int Precision, double* dpCtlPts)iRow=Row;iColumn=Column;memset(dpControlPoints, 0, MAXCONTROLPOINTS*sizeof(double);if ( dpCtlPts != NULL )set_dpControlPoints(dpCtlPts);elsesrand( (unsigned)time( NULL ) );int u, v;for (v = 0; v = iColumn; v+) for (u = 0; u = iRow; u+) if ( iRow = 0 )dpControlPoints(v*(iRow+1)+u)*3+0 = -0.5; elsedpControlPoints(v*(iRow+1)+u)*3+0 = (GLdouble)u/iRow-0.5; if ( iColumn = 0 ) dpControlPoints(v*(iRow+1)+u)*3+1 = -0.5 ; elsedpControlPoints(v*(iRow+1)+u)*3+1 = (GLdouble)v/iColumn-0.5; dpControlPoints(v*(iRow+1)+u)*3+2 = (GLdouble)4/(iRow+iColumn)*(rand()%2); memset(dpKnotsU, 0, MAXKNOTS*sizeof(double);memset(dpKnotsV, 0, MAXKNOTS*sizeof(double);UType=utype;VType=vtype;iUOrder=uOrder;iVOrder=vOrder;update_dpKnots(U);update_dpKnots(V);iPrecision=Precision;bDrawControlPoints=false;bDrawDiffVector=false;bWireFrame=true;bTexture=false;bLight=false; for ( int v = 0; vMAXN; v+) for ( int u = 0; uMAXN; u+) bControlPointsSelectedvu = false ;void BH_BSpline:set_dpControlPoints(double* value)memcpy(dpControlPoints, value, (iRow+1)*(iColumn+1)*3*sizeof(double);return;void BH_BSpline:set_dpKnotsU(double* value)memcpy(dpKnotsU, value, (iRow+iUOrder+1)*sizeof(double);return;void BH_BSpline:set_dpKnotsV(double* value)memcpy(dpKnotsV, value, (iColumn+iVOrder+1)*sizeof(double);return;double* BH_BSpline:get_dpKnotsU()return dpKnotsU ;double* BH_BSpline:get_dpKnotsV()return dpKnotsV ;const int BH_BSpline:get_iPrecision() constreturn iPrecision;void BH_BSpline:set_iPrecision(int value)iPrecision = value;return;const int BH_BSpline:get_iRow() constreturn iRow;const int BH_BSpline:get_iColumn() constreturn iColumn;void BH_BSpline:set_iUOrder(int value)if ( value iRow )AfxMessageBox(阶次k必须大于等于0且小于等于n);return;iUOrder = value ;update_dpKnots(U) ;return;void BH_BSpline:set_iVOrder(int value)if ( value iColumn )AfxMessageBox(阶次k必须大于等于0且小于等于n);return;iVOrder = value ;update_dpKnots(V) ;return;void BH_BSpline:set_UType(int type)UType=type;update_dpKnots(U);void BH_BSpline:set_VType(int type)VType=type;update_dpKnots(V);const int BH_BSpline:get_UType() constreturn UType;const int BH_BSpline:get_VType() constreturn VType;const int BH_BSpline:get_iUOrder() constreturn iUOrder;const int BH_BSpline:get_iVOrder() constreturn iVOrder;void BH_BSpline:Draw(int mode)if ( mode = GL_SELECT & !bDrawControlPoints )/选取模式 return ;glDisable(GL_LIGHTING);glDisable(GL_BLEND);int u, v;if (bDrawControlPoints)/绘制控制网格 glPointSize(8.0f); int index=0; for ( v = 0; v=iColumn; v+) for ( u = 0; u=iRow; u+) if ( mode = GL_SELECT )glLoadName(v*MAXN+u); if ( bControlPointsSelectedvu )glColor3f(1.0, 0.0, 0.0); else glColor3f(1.0, 1.0, 1.0); float x, y, z; x=dpControlPoints(v*(iRow+1)+u)*3+0; y=dpControlPoints(v*(iRow+1)+u)*3+1; z=dpControlPoints(v*(iRow+1)+u)*3+2; glBegin(GL_POINTS);glVertex3f(x, y, z); glEnd(); if ( mode = GL_SELECT )/选取模式 return ; glLineWidth(2.0); for ( u = 0; u=iRow; u+) glBegin(GL_LINE_STRIP); for ( v = 0; v=iColumn; v+) glColor3f(0.0, (GLdouble)(u)/(iRow+1), 1.0-(GLdouble)(u)/(iRow+1); float x, y, z; x=dpControlPoints(v*(iRow+1)+u)*3+0; y=dpControlPoints(v*(iRow+1)+u)*3+1; z=dpControlPoints(v*(iRow+1)+u)*3+2;glVertex3f(x, y, z); glEnd(); for ( v = 0; v=iColumn; v+) glBegin(GL_LINE_STRIP); for ( u = 0; u=iRow; u+) glColor3f(0.0, (GLdouble)(u)/(iRow+1), 1.0-(GLdouble)(u)/(iRow+1); float x, y, z; x=dpControlPoints(v*(iRow+1)+u)*3+0; y=dpControlPoints(v*(iRow+1)+u)*3+1; z=dpControlPoints(v*(iRow+1)+u)*3+2;glVertex3f(x, y, z); glEnd(); /End Draw Control Points Gridsdouble d1MAXPRECISION3, d2MAXPRECISION3;/记录两个相邻等u线ui, ui+1点的数据double dpCtrlPointsVMAXN*3;/记录等u线对应的控制点double dpDiffVectorCtrlPointsUMAXN*3, dpDiffVectorUMAXPRECISION3, dpDiffVectorVMAXPRECISION3, dpNormalMAXPRECISION3;CVertex vertex; /由于浮点数存在累计误差，所以在此uv采用整型 for( u=0; u=iPrecision; u+=1) bool bDraw=true; for(int v=0; v=iColumn; v+)/计算u/iPrecision处的控制点 vertex=get_Vertex(U, (double)u/iPrecision, (double*)(dpControlPoints+v*(iRow+1)*3); dpCtrlPointsVv*3+0=vertex.dX; dpCtrlPointsVv*3+1=vertex.dY; dpCtrlPointsVv*3+2=vertex.dZ; vertex=get_TangentVector(U,(double)u/iPrecision,(double*)(dpControlPoints+v*(iRow+1)*3); dpDiffVectorCtrlPointsUv*3+0=vertex.dX; dpDiffVectorCtrlPointsUv*3+1=vertex.dY; dpDiffVectorCtrlPointsUv*3+2=vertex.dZ; glLineWidth(1.0); glColor3f(0, (GLdouble)u/(iPrecision), 1-(GLdouble)u/(iPrecision); glBegin(GL_LINE_STRIP); for(v=0; v0 & bWireFrame )/绘制等v线 for (v=0; v=iPrecision; v+) glBegin(GL_LINES); glVertex3f(d1v0, d1v1, d1v2); glVertex3f(d2v0, d2v1, d2v2); glEnd(); /计算切矢 double divider; for(v=0; v0 & (!bWireFrame | bTexture) ) if(bLight)glEnable(GL_LIGHTING); if(bTexture)glEnable(GL_TEXTURE_2D); glColor3f(1.0, 0, 0); for (v=0; viPrecision; v+)/面填充模式 if (u%2=1) glBegin(GL_QUADS); glNormal3f(dpNormalv0, dpNormalv1, dpNormalv2); if(bTexture)glTexCoord2f( (double)(u-1)/(iPrecision), (double)(v)/(iPrecision) ); glVertex3f(d1v0, d1v1, d1v2); if(bTexture)glTexCoord2f( (double)(u)/(iPrecision), (double)(v)/(iPrecision) ); glVertex3f(d2v0, d2v1, d2v2); if(bTexture)glTexCoord2f( (double)(u)/(iPrecision), (double)(v+1)/(iPrecision) ); glVertex3f(d2v+10, d2v+11, d2v+12); if(bTexture)glTexCoord2f( (double)(u-1)/(iPrecision), (double)(v+1)/(iPrecision) ); glVertex3f(d1v+10, d1v+11, d1v+12); glEnd(); else glBegin(GL_QUADS); glNormal3f(dpNormalv0, dpNormalv1, dpNormalv2); if(bTexture)glTexCoord2f( (double)(u-1)/(iPrecision), (double)(v)/(iPrecision) ); glVertex3f(d2v0, d2v1, d2v2); if(bTexture)glTexCoord2f( (double)(u)/(iPrecision), (double)(v)/(iPrecision) ); glVertex3f(d1v0, d1v1, d1v2); if(bTexture)glTexCoord2f( (double)(u)/(iPrecision), (double)(v+1)/(iPrecision) ); glVertex3f(d1v+10, d1v+11, d1v+12); if(bTexture)glTexCoord2f( (double)(u-1)/(iPrecision), (double)(v+1)/(iPrecision) ); glVertex3f(d2v+10, d2v+11, d2v+12); glEnd(); glDisable(GL_LIGHTING); glDisable(GL_TEXTURE_2D); for(v=0; v=iPrecision; v+=20)/绘制切矢 if (u%20=0 & bDrawDiffVector) glColor3f(1, 0, 0);glBegin(GL_LINES); glVertex3f(d1v0, d1v1, d1v2); glVertex3f(d1v0+dpDiffVectorVv0/10, d1v1+dpDiffVectorVv1/10, d1v2+dpDiffVectorVv2/10); glEnd(); glColor3f(0, 1, 0);glBegin(GL_LINES); glVertex3f(d1v0, d1v1, d1v2); glVertex3f(d1v0+dpDiffVectorUv0/10, d1v1+dpDiffVectorUv1/10, d1v2+dpDiffVectorUv2/10); glEnd(); glColor3f(0, 0, 1);glBegin(GL_LINES); glVertex3f(d1v0, d1v1, d1v2); glVertex3f(d1v0+dpNormalv0/10, d1v1+dpNormalv1/10, d1v2+dpNormalv2/10); glEnd(); CVertex BH_BSpline:get_Vertex(int direction, double t, double* dpCtrlPoints)double* knots;int iCtrlPoints, iOrder;CVertex vertex;double aMAXORDER, dMAXORDER*3;if ( direction = U )knots = dpKnotsU ;iCtrlPoints = iRow ;iOrder = iUOrder ;else if ( direction = V )knots = dpKnotsV ;iCtrlPoints = iColumn ;iOrder = iVOrder ;elsereturn vertex;int i;for ( i = iOrder; i =knotsi) & (t ( iCtrlPoints + 1 ) )return vertex ;memcpy(d, dpCtrlPoints+(i-iOrder)*3, (iOrder+1)*3*sizeof(double) ) ;for ( int k=iOrder; k=1; k- )/第k次迭代for ( int j=0; jk; j+ )/第j个a， dif ( knotsi+j+1=knotsi+j+1-k )/规定0/0=0aj=0;elseaj=(t-knotsi+j+1-k)/(knotsi+j+1-knotsi+j+1-k) ;dj*3+0 = (1-aj)*dj*3+0 + aj*d(j+1)*3+0 ;dj*3+1 = (1-aj)*dj*3+1 + aj*d(j+1)*3+1 ;dj*3+2 = (1-aj)*dj*3+2 + aj*d(j+1)*3+2 ;vertex.dX=d0;vertex.dY=d1;vertex.dZ=d2;return vertex;CVertex BH_BSpline:get_TangentVector(int direction, double t, double* dpCtrlPoints, int iTanOrder)double* knots;int iCtrlPoints, iOrder;CVertex vertex;double aMAXORDER, dMAXORDER*3;if ( direction = U )knots = dpKnotsU ;iCtrlPoints = iRow ;iOrder = iUOrder ;else if ( direction = V )knots = dpKnotsV ;iCtrlPoints = iColumn ;iOrder = iVOrder ;elsereturn vertex ; int i;for ( i = iOrder; i =knotsi) & (t ( iCtrlPoints + 1 ) )return vertex ;memcpy(d, dpCtrlPoints+(i-iOrder)*3, (iOrder+1)*3*sizeof(double) ) ;for ( int l = 1 ; l = iTanOrder ; l+ )for ( int j = 0 ; j =1; k- )/第k次迭代for ( int j=0; jk; j+ )/第j个a， dif ( knotsi+j+1=knotsi+j+1-k )/规定0/0=0aj=0;elseaj=(t-knotsi+j+1-k)/(knotsi+j+1-knotsi+j+1-k) ;dj*3+0 = (1-aj)*dj*3+0 + aj*d(j+1)*3+0 ;dj*3+1 = (1-aj)*dj*3+1 + aj*d(j+1)*3+1 ;dj*3+2 = (1-aj)*dj*3+2 + aj*d(j+1)*3+2 ;vertex.dX=d0;vertex.dY=d1;vertex.dZ=d2;return vertex ;bool BH_BSpline:Save(LPCTSTR path)FILE *stream=NULL; stream = fopen( path, w );if(stream=NULL)return false; fprintf( stream, BH_BSPline_File.n);fprintf( stream, Row=%d, Column=%dn, iRow, iColumn);for ( int v = 0; v=iColumn; v+) for ( int u = 0; u=iRow; u+) float x, y, z; x=dpControlPoints(v*(iRow+1)+u)*3+0; y=dpControlPoints(v*(iRow+1)+u)*3+1; z=dpControlPoints(v*(iRow+1)+u)*3+2; fprintf( stream, %f,t%f,t%fn, x, y, z); int i;int iUKnotsNumber=iRow+iUOrder+1;fprintf(stream, UKnotsNumber=%d, UOder=%d, Type=%dn, iUKnotsNumber, iUOrder , UType);for ( i = 0; i = iUKnotsNumber; i+)fprintf(stream, %ft, dpKnotsUi);fprintf(stream, n);int iVKnotsNumber=iColumn+iVOrder+1;fprintf(stream, VKnotsNumber=%d, VOder=%d, Type=%dn, iVKnotsNumber, iVOrder ,VType);for ( i = 0; i = iVKnotsNumber; i+)fprintf(stream, %ft, dpKnotsVi);fprintf(stream, n);fprintf(stream, Precision=%dn, iPrecision); fclose( stream );return true;bool BH_BSpline:Open(LPCTSTR path)FILE *stream=NULL; stream = fopen( path, r );if(stream=NULL)return false;char header32; fscanf( stream, %sn, header);if ( memcmp( header, BH_BSPline_File.n, 16 ) != 0 )AfxMessageBox(该文件非B样条数据文件。);return false;fscanf( stream, Row=%d, Column=%dn, &iRow, &iColumn);for ( int v = 0; v=iColumn; v+) for ( int u = 0; u=iRow; u+) float x, y, z; fscanf( stream, %f,t%f,t%fn, &x, &y, &z); dpControlPoin