北航计算机图形学9

1、二维图形的运算二维图形的运算基本运算基本运算1.交点计算 1.1两直线段的交点设两条直线段。和21SS4443332222,yxPyxPSyxP和的两个端点为；和则两条直线段的参数方程为：1111, yxPS的两个端点为 101101432211vvPPvvSuuPPuuS上述方程可以写成：10:10:34334321211211vvyyyyvxxxxSuuyyyyuxxxxS 如果两条直线相交，则满足vyyyuyyyvxxxuxxx343121343121即134312134312yyvyyuyyxxvxxuxx解得：当43124312131213124312431243134313yyyy

2、xxxxyyyyxxxxvyyyyxxxxyyyyxxxxu043124312yyyyxxxx时，有(1)=0 方程组无解。说明两条直线段所在直线相互平行或重合，所以不相交，没有交点产生。(2)0 方程组有唯一解。如果0u 1则说明交点P位于线段S1上。否则，交点P位于线段S1延长线上。 如果0v1则说明交点P位于线段S2上。否则，交点P位于线段S2延长线上。 所以，只有当0u1和0v1同时成立时，交点P既位于线段S1上又位于线段S2上。1.2直线与圆弧的交点设直线AB的方程为) 10 ()()(ttyyyytxxxxabaaba圆心为C(xc,yc)半径为R的圆弧的参数方程为角和终止角。分别

3、表示圆弧的起始和esesccRyyRxx)(sincos如果直线段和圆弧相交，则有：222)()(Rtyyytxxxabaaba将上式展开可得02CBtAt式中A,B,C均可由已知点的坐标求得当=B2-4AC 0时，直线和圆弧不相交。当=B2-4AC0时，前面的一元二次方程有两个不相等的实根t1和t2。当满足0 t1 1或0 t21时，直线段才有可能与圆弧相交。此时可以通过来计算RtyyyyRtxxxxabcaabca)(sin)(cos当求得的满足s e时，直线段才与圆弧相交。2.关系判断关系判断1.1.点的包含性检验 点的包含性检验是指：判断一个点是否被包含在某一个区域内。区域通常是多边形

4、。通常有两种方法：（1）夹角和检验法（2）交点数检验法l夹角和检验法 （a）被测点p在多边形外 （b）被测点p在多边形内BPABCDEACDEa1a2a3a4a5Pa1a2a3a4a5点与多边形的包含性检测点与多边形的包含性检测l射线法l由被测点P处向 y = - 方向作射线l交点个数是奇数，则被测点在多边形内部l否则，偶数，在多边形外部。PPP1P2P3P1P2l若射线正好经过多边形的顶点，当共享顶点的两边在射线的同一侧，则交点计数加2，否则加1。1.2多边形重叠性检验其思想是用包含多边形的最小矩形来检测。3.窗口运算窗口运算1.1.定义窗口和视区1.2.窗口视区转换假设在用户坐标系xoy中

5、定义一个窗口，其左下角坐标为(xl,yb)，右上角坐标为(xr,yt)；在设备坐标系x*o*y*中定义一个窗口，其左下角坐标为(xl*,yb*)，右上角坐标为(xr*,yt*)；则有：xyoxlxrybytpx*y*o*xl*xr*yb*yt*p*btbtblrlryyyyyyyyxxxxxxxxbll*从窗口到视口的转换从窗口到视口的转换WYTWXRWYBWXLVYTVXRVYBVXLvyvxwywxDCyyBAxxwvwvWYBCVYBDWYBWYTVYBVYTCWXLAVXLBWXLWXRVXLVXRA1.直线的生成算法1.1.逐点比较法（1）算法流程开始偏差判别画笔作图终点判断结束偏差

6、计算是否算法说明：偏差判别：按偏差来判断画笔的当前位置与规定图形的位置的偏差符号，以确定画笔下一步方向。画笔作图：给出x向或y向的走步信号，使画笔在该方向上移动一个步距。终点判断：判断当前画笔是否到终点。偏差计算：在新位置上计算作图偏差，作为偏差判别的依据。如果把直线的起点设置在坐标原点，则规定直线处于4个不同的象限中时，画笔的走向如图所示。（2）偏差计算一般公式设直线的终点为A(xa,ya),当前位置为M (xm,ym)。oA，oM与x轴的夹角分别为和。则偏差为amamamaammxxyxxyxyxytantan由于上述公式的分母在所有的象限为正，故偏差判别式可简化为 Fm=ymxa-xmy

7、a第一象限为例当0时，表示画笔在oA线的下方，应该走+y一步；当0，表示画笔在oA线上或上方，此时则应该走+x一步。 简化公式当Fm0时，应该走+y一步，即xm+1=xm，ym+1=ym1。则 Fm1 ym1xa-yaxm+1= Fm+xa当Fm 0时，应该走+x一步，即xm+1=xm+1，ym+1=ym。则 Fm1 ym1xa-yaxm+1= Fm-ya 起始时，设F1=0，即假设画笔在直线段的起点。其它象限中的偏差计算公式第二象限当Fm0时，应该走-x一步，即xm+1=xm-1，ym+1=ym。则 Fm1 ym1xa-yaxm+1= Fm+ya = Fm+|ya| 当Fm 0时，应该走+y

8、一步，即xm+1=xm，ym+1=ym+1。则 Fm1 ym1xa-yaxm+1= Fm+xa= Fm-| xa |三、四象限是类似的。 终点判断设绘图机的步长为t，直线段在x,y两个方向上的增量分别为x和y，则绘图笔从直线的起点走到直线的终点，在x方向应走x/t步，在y方向应走y/t步。两个方向上的总步数为(x/t+y/t)。l直线的扫描转换直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，将这些象素存入到帧缓存的相应单元中。l三个常用算法：数值微分法（DDA）中点画线法Bresenham算法。数值微分数值微分(DDA)法法l 基本思想 已知过端点 的直线段L： 直线斜率为

9、 从 的左端点 开始，向 右端点步进。步长=1(个象素)，计算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。0101xxyyk),(),(111000yxPyxPbkxyx0 xxbkxy计算当 时;即：当x每递增1，y递增k(即直线斜率)； xkyxkbkxbkxyiiii 111xkyyii1例：画直线段x int(y+0.5) y+0.5000100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5注：网格点表示象素0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)2 , 5()0 , 0(10PPvoid

10、DDALine(int x0,int y0,int x1,int y1,int color) int x；float dx, dy, y, k;dx, = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; 注意上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1, y最多增加1。当 k 1时，必须把x，y地位互换 k 1 示意图0 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)l过各行各列象素中心构造一组虚拟网格线。按直线从起

11、点到终点的顺序计算直线与各垂直网格线的交点，然后根据误差项的符号确定该列象素中与此交点最近的象素。dddd Bresenham算法算法设直线方程为： ，其中k=dy/dx。 因为直线的起始点在象素中心，所以误差项d的初值d00。X下标每增加1，d的值相应递增直线的斜率值k，即ddk。一旦d1，就把它减去1，这样保证d在0、1之间。l当d0.5时，最接近于当前象素的右上方象素（ ）l而当d0.5时，更接近于右方象素（ ）。为方便计算，令ed-0.5，e的初值为-0.5，增量为k。l当e0时，取当前象素（xi，yi）的右上方象素（ ）；l而当e0时，更接近于右方象素（ ）。kyxxkyyiiiii

12、)(1111,iiyxiiyx,111,iiyxiiyx,1void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; 2.圆弧的生成算法圆弧的生成算法 2.1逐点比较法用逐点比较法生成圆弧是在绘图笔每走完一步，就要把绘

13、图笔当前的位置距圆心的距离与半径进行比较，根据比较结果决定下一步的走向。这种方法是用阶梯折线来逼近圆弧。如图所示：xyO由于画圆的方向有顺时针和逆时针两种，所以讨论圆弧的生成算法时，要分成顺时针和逆时针及4个象限8种情况。xyOxyO 1)偏差计算(1)一般公式设圆弧的起点为A(xa,ya)，终点为B(xb,yb)，圆心在原点。则圆弧的半径为R=(xa2+ya2)1/2设画笔的当前位置为M(xm,ym)，则画笔至圆心的距离为Rm=(xm2+ym2)1/2记 Fm Rm2 -Ra2 =(xm2+ym2)-(xa2+ya2)以第一象限为例，当Fm0时，即画笔在圆外或圆上，此时应向x走步；当Fm 0时，即画笔在圆内，此时应向y走步； (2)简化公式当Fm0时，此时应向x走步，则xm+1=xm-1，ym+1=ym,从而 Fm1(xm+12+ym+12)-(xa2+ya2) (xm2-2xm+ 1+ ym2)-(xa2+ya2) Fm-2xm+ 1当Fm 0时，此时应向y走步，则xm+1=xm，ym+1=ym 1,从而Fm1(xm+12+ym+12)-(xa2+ya2) (xm2+ ym2 2ym+ 1)-(xa2+ya2) Fm+2ym+ 1 2)公式的推广以逆圆第三