《计算机图形学》04二维图形生成技术

第四章二维图形生成技术4.1直线图形yx1234n1234mp1p2一.生成直线的DDA算法假设直线的起点坐标为P1(x1,y1)，终点坐标为P2(x2,y2)x方向的增量为△x＝x2－x1；y方向上增量为△y＝y2－y1直线的斜率为k＝△y／△x当△x＞△y时，让x从x1到x2变化，每步递增1，那么，x的变化可以表示为xi+1＝xi＋1y的变化可以表示为yi+1＝yi＋k用上式可求得图中直线P1P2和y方向网格线的交点，但显示时要用象素点(图中的网格结点)耒表示，所以要用舍入的办法耒找到最靠近交点处的象素点，并用其耒表示直线段。这个方法称之为数字微分分析法，简称DDA。算法描述如下：intx1，y1，x2，y2；intx；floatdx，dy，k，y；dx＝x2－x1dy＝y2－y1k＝dy／dxx＝x1y＝y1for(x＝x1；x＜＝x2；x＋＋){putpixel(x，(int)(y)，pixelcolor)y＝y＋k}该算法仅适用于｜k｜≤1的情况，而当｜k｜＞1时，则需将x和y的位置交换。二.生成直线的Bresenham算法设k＝△y／△x，先讨论0≤k≤1的情况：若以屏幕上x方向的象素点作为横坐标，则有xi+1－xi＝1而yi+1＝yi＋k(xi+1－xi)＝yi＋k(1)设b点是直线上的点，其实际坐标是(xi+1，yi+1)。在屏幕上是用象素点c还是d耒表示？设a为c、d的中点，判断。关键问题：(1)如何判断b是在a的上面还是下面，设置一个标志变量e；(2)如何建立标志变量e的递推公式。xiXi+1Yi'Yi+1Yi+1'bacd设e(xi+1)＝yi+1－yi′－0.5(2)若b在a的下面，则有e(xi+1)0若b在a的上面，则有e(xi+1)0由图中可知：当e(xi+1)≥0时y′i+1＝yi′＋1e(xi+1)0时y′i+1＝yi＇递推：由(2)、(3)式可得：e(xi+2)＝yi+2－y′i+1－0.5＝yi+1＋k－y′i+1－0.5yi+1－yi′－0.5＋k－1e(xi+1)≥0yi+1－yi′－0.5＋ke(xi+1)0e(xi+1)＋k－1e(xi+1)≥0e(xi+1)＋ke(xi+1)0==(3)算法描述如下：△x＝x2－x1△y＝y2－y1k＝△y／△xe＝k－0.5(若起始点在象素中心，则e的初始值为－0.5)x＝x1y=y1for(i＝1；i＜＝△x；i＋＋){putpixel(x，y，pixelcolor)x＝x＋1if(e＜0)e＝e＋kelse{y＝y＋1；e＝e＋k－1}}讨论：斜率不同时：以上讨论的是0≤k≤1的情况，即0＜△y＜△x的情况；若是0＜△x＜△y的情况，则需将x和y的位置交换。方向不同时：若△y＜0或△x＜0时，要将算法中的y＝y＋1换成y＝y－1、x＝x＋1换成x＝x－1。4.2二次曲线一、圆的生成算法即是找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。下面仅以圆心在原点的圆为例，讨论圆的生成算法。1.圆弧扫描算法x2+y2=r2y=Sqrt(r2-x2)在一定范围内，每给定一x值，可得一y值。当x取整数时，y须圆整。缺点：浮点运算，开方，圆整，不均匀。2.角度DDA法x=x0+rcosy=y0+rsindx=-rsinddy=rcosdxn+1=xn+dxyn+1=yn+dyxn+1=xn-(yn-y0)dyn+1=yn+(xn-x0)d显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。但要采用浮点运算、乘法运算。3.Bresenham画圆算法该算法以点(0,r)为起点，按顺时针方向生成圆时，相当于在第一象限内，所以y是x的单调递减函数。从圆上任一点出发，按顺时针方向生成圆时，为了最佳地逼近该圆，对于下一个象素的取法只有三种可能的选择，即右方象素(H)、右下角象素(D)、下方象素(V)。（0，r)yx(xi,yi)(xi,yi)(xi+1,yi)H(xi,yi-1)V(xi+1yi-1)D设△i＝(xi+1)2＋(yi-1)2－r2若△i＜0，则右下角点在圆内，此时只可能取象素点H或D设δ1＝｜(xi+1)2＋(yi)2－r2｜－｜(xi+1)2＋(yi-1)2－r2｜若δ1＜0取Hδ1＞0取Dδ1＝0二者距离相等，规定取右方象素H并可将δ1进一步化简成δ1＝2(△i＋yi)－1若△i＞0，则右下角点在圆外，此时只可能取象素点D或V设δ2＝｜(xi+1)2＋(yi-1)2－r2｜－｜(xi)2＋(yi-1)2－r2｜若δ2＜0取Dδ2＞0取Vδ2＝0二者距离相等，规定取右下角象素D并可将δ2进一步化简成δ2＝2(△i－xi)－1若△i＝0，此时圆上点正好是D，即取D。导出简单增量算法的递推公式：若设当前圆上点所在的象素为第i个象素，下一个新象素为第i+1个象素，则新象素的坐标及△值的递推公式是：新象素为H时：xi+1＝xi＋1yi+1＝yi△i+1＝△i＋2xi+1＋1新象素为D时：xi+1＝xi＋1yi+1＝yi－1△i+1＝△i＋2xi+1－2yi+1＋2新象素为V时：xi+1＝xiyi+1＝yi－1△i+1＝△i－2yi+1＋1算法描述如下：x＝0;y＝r;delta＝2*（1－r）;while（y＞＝0）{putpixel（x,y,pixelco1or）;if（delta＜0）{delta1＝2*（delta＋y）－1,if（deltal＜=0）direction＝1;elsedirection＝2;}elseif（delta＞0）{delta2＝2*（delta一x）－1;if（delta2＜＝0）direction＝2;elsedirection＝3;}elsedirection＝2;switch（direction）{case1：x＋＋;取Hdelta＋＝2＊x＋1;break：case2：x＋＋;取Dy――;delta＋＝2*（x－y＋1）;break;case3：y――;取Vdelta＋＝（－2*y＋1）;break;｝／*switch*／｝／*whi1e*／二.抛物线的参数拟合方法抛物线的参数向量方程：Q(t)=at2+bt+c(0≤t≤1)对应的参数方程：x(t)=axt2+bxt+cxy(t)=ayt2+byt+cy抛物线的参数方程的系数：cx=x0cy=y0bx=2(x1–x0)by=2(y1–y0)ax=x2–2x1+x0ay=y2–2y1+y0(0≤t≤1)抛物线的重要性质：1.曲线在t=1/2处的切线平行于P0P2。2.Pm点为P1C直线的中点。采用P0、Pm、P2三点构造抛物线时的参数方程的系数：cx=x0cy=y0bx=4xm–x2–3x0by=4ym–y2–3y0ax=2(x2–2xm+x0)ay=2(y2–2ym+y0)结论：P0、P1、P2与P0、Pm、P2所构成的抛物线是等价的，二者确定参数方程系数的公式不同，后者产生的曲线通过给定的三点。4.3自由曲线一.概述曲线：规则曲线——可用曲线方程式表示的曲线。不规则曲线——不能确切给出描述整个曲线的方程，而是由从实际测量中得到的一系列离散数据点采用曲线拟合的方法来逼近的。这类曲线也称之为自由曲线。曲线的表示方法：1.直角坐标曲线显式y=f(x)隐式f(x,y)=02.极坐标曲线Ｐ=ρ(θ)3.参数坐标曲线x=x(t);y=y(t)参变量的规格化曲线的绘制方法：离散，用小直线段来逼近曲线。型值点：是指通过测量或计算得到的曲线上少量描述曲线几何形状的数据点。控制点：是指用来控制或调整曲线形状的特殊点，曲线本身不一定通过控制点。插值和逼近：这是曲线设计中的两种不同方法。插值设计方法要求建立的曲线数学模型，严格通过已知的每一个型值点。而逼近设计方法建立的曲线数学模型只是近似地接近已知的型值点（控制点）。拟合：是指在曲线的设计过程中，用插值或逼近的方法使生成的曲线达到某些设计要求。连续性：C0连续（0阶参数连续）——前一段曲线的终点与后一段曲线的起点相同。C1连续（一阶参数连续）——两相邻曲线段的连接点处有相同的一阶导数。C2连续（二阶参数连续）——两相邻曲线段的连接点处有相同的一阶导数和二阶导数。二.抛物线参数样条曲线这是根据给定的型值点列，以抛物线作为基本曲线拟合生成的自由曲线。特点：采用插值方法生成，曲线通过每个型值点。给定型值点列Pi(i=1,2,…..,n),按抛物线的参数拟合方法，每经过相邻三点可作一段抛物线，共可作出n–2条。一般情况下，每两段曲线之间的搭接区间，两段抛物线是不可能重合的。但对于拟合曲线来说，整个型值点列必须用一条光滑的曲线连接起来。解决的办法：将两段曲线之间的搭接区间采用加权合成的方法合成一条曲线。也就是说，由Pi、Pi+1、Pi+2、Pi+3这四个型值点采用加权合成的方法可以确定Pi+1和Pi+2之间的一段曲线。结论：对于给定的型值点列Pi(i=1,2,…..,n),从P1开始依次每取四个型值点即可画出一段曲线，直到Pn为止。按这样的方法，在Pi(i=1,2,…..,n)个型值点列中只能得到n–3段曲线，但n个型值点列之间应有n–1个区段。如何得到首、末两个区段的曲线？解决的办法：添加“端点条件”(也称“边界条件”)。其中最简单的一种称为“自由端条件”，即在首、末两端各添加一个辅助点P0和Pn+1，并使P0=P1,Pn+1=Pn。.这种方法适用于对曲线的两端没有什么特殊要求的情况。P1P2P3PiPnP0Pn+1三.Bezier曲线Bezier曲线的参数方程：nQ(t)＝∑PiBi,n(t)(0≤t≤1)i=0式中：Pi(i=0,1,2,….,n)是空间给定的n＋1个点的位置向量，也称控制点，它们构成了控制Bezier曲线形状的特征多边形。Bi,n(t)为Bernstain基函数。n!i!(n-i)!ti(1–t)n-ii=0,1,….,nBi,n(t)=Betnstein基函数的性质:（1）正性（2）端点性质（3）权性由二项式定理可知：)1,0(1)(0,ttBninininininiinnittttCtB00,1])1[()1()(1,...,2,1)1,0(01,00)(,nitttBniotherwiseiBni001)0(,otherwiseniBni01)1(,Betnstein基函数的性质:（4）对称性因为（5）递推性。即高一次的Bernstein基函数可由两个低一次的Bernstein调和函数线性组合而成。因为，)()(,,tBtBninni)1()1()1()]1(1[)(,)(,tBttCttCtBniiniinininninnnin),,1,0()()()1()(1,11,,nittBtBttBninini)()()1()1()1()1()1()()1()(1,11,)1()1(111)1(1111,ttBtBttttCttCtttCCttCtBniniiniininiininiinininiinniBetnstein基函数的性质:（6）导函数（7）最大值。在处达到最大值。（8）升阶公式（9）积分;,,1,0)],()([)(1,1,1,nitBtBntBnininiBtin,()tin)(11)()11()()(11)()()11()()1(1,11,,1,1,1,,tBnitBnitBtBnittBtBnitBtninininininini10,11)(ntBniBezier曲线的性质:（1）端点性质a.）曲线端点位置矢量由Bernstein基函数的端点性质可以推得，当t=0时，P(0)=P0；当t=1时，P(1)=Pn。由此可见，Bezier曲线的起点、终点与相应的特征多边形的