三下-图形学第5-10讲

1Chapter3

BasicRasterGraphicsAlgorithmsforDrawing2DPrimitives

基本二维图元的生成算法2本章内容(outline)直线的扫描转换(SCANCONVERTINGLINES)圆与椭圆的扫描转换(SCANCONVERTINGCIRCLEANDELLIPSE)区域填充(FILLINGREGION)字符生成(GENERATINGCHARACTERS)反走样(ANTIALIASING)二维裁剪(2DCLIPPING)3图形扫描转换(scan-conversion)Scan-conversion:确定一个象素集合及其颜色，用于显示一个图形的过程，称为图形的扫描转换或光栅化。图形扫描转换分为两步：

确定有关（组成图形的）象素；用图形的颜色或其他属性对象素进行写操作。4TheoutputpipelineToclipaprimitivepriortoscanconversionMostoftenforlines,rectangles,polygonsToscanconvertaprimitivepriortoclippingGeneralizestoarbitraryclipregionsGeneratetheentirecollectionofprimitivesintoatemporarycanvasandthentocopyPixelonlythecontentsofthecliprectangletothedestinationcanvasOftenusedfortext5Scanconvertinglines用离散点集逼近采用几何方式定义的直线段(注意斜率slope)6SCANCONVERTINGLINES(直线的扫描转换)问题

给定直线段的两个端点(x0,y0)和(x1,y1),

把其在光栅扫描显示器上显示出来.描述

理想的直线段:没有线宽,由无数个点构成光栅扫描显示器上:有限个象素组成,有线宽.7ScanconvertinglineEqualsto：GiventheendpointsandthecolorofthelineComputingthecoordinatesofthepixelsthatlieonornearanideallineWritingthepixelsbythecolor8p0p1●●●●●●表示:用最靠近直线的一些网格点来代表它直线的表示直线的表示(therepresentationoflines)9两种基本的直线扫描转换算法数值微分法(DigitalDifferentialAnalyzer－DDA)也称为基本增量法(BasicIncrementalAlgorithm)中点画线法(MidpointLineAlgorithm)BresenhamLineAlgorithm10PrincipleofBasicIncrementalAlgorithm(1)(xi,Round(yi))(xi,yi)(xi+1,Round(yi+k))(xi+1,yi+k)11方法数值微分法(DDA---DigitalDifferentialAnalyzer)

12数值微分法(DDA)13令yir=round(yi)所求点坐标为(round(xi+1),round(yi+1))其中,xi+1=xi+1,yi+1=yi+m;数值微分法(DDA)14数值微分法(DDA)●●●●●p1p0●●问题若|m|>1,则x向每变化1个单位,y向有可能超出1个步长15数值微分法(DDA)最大步长(步距)步进方向:的方向16数值微分法(DDA)17数值微分法(DDA)算法：18数值微分法(DDA)voidLine(/*Assumes-1<m<l,x0<x1*/int

x0,int

y0,/*Leftendpoint*/

int

x1,int

y1,/*Rightendpoint*/int

value)/*Valuetoplaceinline'spixels*/{int

x;/*xrunsfromx0tox1inunitincrements*/double

dy=y1-y0:double

dx=x1-x0;double

m=dy/dx;double

y=y0;for

(x=x0;x<=x1;x++){PutPixel(x,Round(y),value);/*Setpixeltovalue*/y+=m;/*Stepybyslopem*/}}/*Line*/

Theincrementallinescan-conversionalgorithm.19算法优点：简单、自然。算法缺点：用到了浮点运算，计算效率低。自变量的选择可根据斜率确定，以得到最佳的直线效果：数值微分法(DDA)20中点画线法(MidpointLineAlgorithm)问题引出

为解决DDA算法中需要浮点数进行运算，且输出时需取整的不利条件，可以用中点画线法。假设直线的斜率m∈[0,1]，两个端点分别是（x0,y0）,（x1,y1）。21P(xp,yp)P1(xp+1,yp)中点判别方法示意图QP2(xp+1,yp+1)MMidpointLineAlgorithm(1)22思想当前一点已确定,用P(xp,yp)来代表时，下一点仅有可能在P1和P2中选，用M表示P1,P2的中点，M(xp+1,yp+0.5)。Q是理想直线上x=xp+1处的点.比较M和Q的位置关系,以确定下一点的走向.MidpointLineAlgorithm(2)23比较M和Q:若M位于Q的下方,即ym<yq,则应取p2点;若M位于Q的上方,即ym>yq,则应取p1点;原则:

当两侯选点的中点落在直线下方时，选较高点，否则选较低点。MidpointLineAlgorithm(3)24直线的正负划分性l=F(x,y)=0(x0,y0)F(x0,y0)>0F(x0,y0)<025直线的正负划分性则该直线将其所在空间一分为二：设平面直线方程为：26MidpointLineAlgorithm(4)定义直线函数：特点：其中：27MidpointLineAlgorithm(5)Definedecisionfunction(构造判别函数)：Definedecisionvariable(引入判别参数):其中：28MidpointLineAlgorithm(6)算法描述：（假设X方向的步长为1）问题：如何快速计算判别参数的值？采用增量计算方法优化判别公式的计算29如黄色线所示情形如蓝色线所示情形MidpointLineAlgorithm(7)30MidpointLineAlgorithm(8)P(xp,yp)P2(xp+1,yp+1)P1(xp+1,yp)QMM1P4(xp+2,yp+1)P3(xp+2,yp)(xp+2,yp+0.5)31MidpointLineAlgorithm(9)32MidpointLineAlgorithm(10)ThefirstdecisionvariabledstartisThefirstmidpointisat(x0+1,y0+0.5),33算法的递推公式是：MidpointLineAlgorithm(11)递推公式：34消除浮点数的算法公式是：MidpointLineAlgorithm(12)当直线斜率的绝对值大于1时，x，y互换；此时应判别点在直线的左/右侧关系。35例：用中点画线法光栅化一条连接两点(0,0)和(5,2)的直线段，写出计算过程。Example(1)36xydOutpixel初始x=012340123450011221-33-151(0,0)(1,0)(2,1)(3,1)(4,2)(5,2)递推如下：Example(2)37456321001234567Example(3)Thepixelsthatapproximatethelinefrompoint(0,0)topoint(5,2)usingmidpointalgorithmandtheidealline.381.思考题：请考虑如何将该算法推广到任意