03 输出图元1

第3章输出图元云南财经大学信息学院主讲教师：刘祖根Email:[e-mail]主要内容输出图元概念点绘制算法画线算法数值微分法（DDA）Bresenham画线算法中点画线法圆生成算法中点画圆法Bresenham画圆算法填充图元字符生成输出图元概念图形输出原语，简称图元，即图形软件包中用来描述各种图形元素（最基本的~）的函数几何图元：描述对象几何要素的输出图元输出图元种类一级元素：点、直线线段点和线是计算机图形表示的最简单的基本图元二级元素：由点、线构成的圆、圆锥曲线、二次曲面、样条线段、曲面、多边形填色区域、字符串等坐标系统为描述图形，必须首先确定一个称为世界坐标系的合适的二维或三维笛卡尔坐标系。接着通过给出世界坐标系中的位置等几何描述来定义图形中的对象例如，通过两个端点定义一条直线坐标范围：对象坐标的x、y、z最小/最大值等信息，也称为对象的包围盒（BoundingBox）,对二维图形则被称为对象的包围矩形回顾笛卡尔坐标建模坐标世界坐标规范化设备坐标设备坐标或屏幕坐标坐标系统视频监视器上的位置与帧缓存中的像素位置相对应的整数屏幕坐标进行描述屏幕刷新等硬件处理一般从屏幕的左上角开始对像素进行编址。然而，使用软件命令可以按照任何方式设定屏幕位置的参考系统。绝对坐标和相对坐标描述此前讨论的坐标均为绝对坐标，即指定值是所在坐标系统中的实际位置有些图形软件包还允许使用相对坐标来描述位置，即使用从距离最后一次引用的位置（称为当前位置）的位移量来指定坐标位置例如位置（3,8）是当前位置，则相对坐标描述（2,-1）与绝对位置（5,7）相对应主要内容输出图元概念点绘制算法画线算法数值微分法（DDA）Bresenham画线算法中点画线法圆生成算法中点画圆法Bresenham画圆算法填充图元字符生成点绘制算法思想：根据坐标(x,y)，对帧缓冲区中相应的存储单元内容进行操作以画点。主要涉及像素寻址相关因素显示分辨率色深屏幕坐标位置像素信息存放方式偏移量计算(offset)图形信息存储方式压缩像素法(线性链接法)颜色位面法图形信息存储---压缩像素法方法：像素点的全部信息被编码成一个数据字节，按照行优先顺序存储到帧缓冲区中。例子：8×8,16colors,压缩像素A0000000A0000001A0000002A0000003A000001FA000001EA000001DA000001C…….01234567xy01234567(0,0)(1,0)(2,0)(3,0)(4,0)(5,0)(6,0)(7,0)…………(0,7)(1,7)(2,7)(3,7)(4,7)(5,7)(6,7)(7,7)行优先存储（x,y）图形信息存储---颜色位面法方法：帧缓冲区分成N个存储区域（每个存储区域称为一个位面，N个位面共用地址），象素信息在每个位面中占一位，通过N个位面的同一位组成象素数据字节。例子：8×8,16colors,颜色位面(0,2)~(7,2)(0,1)~(7,1)A0000000A0000001A0000002A0000003A0000007A0000006A0000005A0000004(0,0)~(7,0)(0,3)~(7,3)(0,4)~(7,4)(0,5)~(7,5)(0,6)~(7,6)(0,7)~(7,7)(0,0)~(7,0)(0,0)~(7,0)(0,0)~(7,0)01234567xy01234567(x,y)行优先存储偏移量计算---示例例1：320×200，16色，压缩象素法，屏幕坐标(x,y)，试求地址偏移量。若采用颜色位面法，地址偏移量？解：offset=[(320*y+x)*1/2]向下取整压缩象素法offset=[(320*y+x)*1/8]向下取整颜色位面法例2：已知：分辨率640×200，单色，显示缓冲区起始地址A0000000H，屏幕第一行绘制一条水平线，Howtooperate?解：一行640个象素点，色深为1bit,一行占用存储空间640x1/8Bytes=80Bytes,因此，对A0000000~A000004F填充0xFF即可绘制出直线。例2的C语言程序实现片段inti;charfar*ptr;ptr=(charfar*)0xa0000000l;//指向起始地址for(i=0;i80;i++){*ptr=0xff;//赋值ptr++;//指向下一地址}画点函数屏幕坐标(P.67,Fig.3-2)setpixel(x,y)getpixel(x,y,color)gluOrtho2D(xmin,xmax,ymin,ymax)指定的显示窗口如右图所示OpenGL画点函数例：在斜率为2的直线上绘出3个等距离的点glBegin(GL_POINTS);glVertex2i(50,100);glVertex2i(75,150);glVertex2i(100,200);glEnd();显示窗口视频屏幕xminxmaxymaxymin主要内容输出图元概念点绘制算法画线算法数值微分法（DDA）Bresenham画线算法中点画线法圆生成算法中点画圆法Bresenham画圆算法填充图元字符生成画线算法问题直线绘制算法数值微分法（DDA）Bresenham画线算法中点画线法OpenGL画线函数直线绘制问题当我们对直线进行光栅化时，只能在显示器所给定的有限个象素组成的矩阵中，确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作，这就是通常所说的用显示器绘制直线或直线扫描转换。Eg.(10,21.51)→(10,22)光栅显示设备–数字设备屏幕位置以整数位置表示;以直线两端点间的离散点来显示线段；显示的线段具有阶梯现象。(x0,y0)(x1,y1)理想的直线dydx阶梯线离散近似画线算法已知：P1(x1,y1)，P2(x2,y2)直线的笛卡尔斜率截距方程y=m*x+bm=(y2－y1)/(x2－x1)b=y1－m*x1y=m*xx=y/m数值微分法（DDA）IDEA算法描述程序实现(P.72-73)ExampleEvaluation数值微分法---IDEADDA算法是一种线段扫描转换算法，它是在一个坐标轴上以单位间隔对线条取样，从而确定另一个轴上最靠近线段路径的对应整数值DDA算法公式直线斜率满足|m|1时，取x方向为单位步长。递推公式为：xk+1=xk1yk+1=ykmx1x2y1y2xy直线中间的各个像素点－沿x轴取样IDEADDA算法公式直线斜率满足|m|1时，取y方向为单位步长。递推公式为：yk+1=yk1xk+1=xk1/mx1x2y1y2xy|m|1求直线中间各个像素点－沿y轴取样算法描述输入直线端点坐标；确定单位间隔采样方向以及采样次数（比较dx，dy）；计算两个坐标方向的循环增量（+1，-1，m，1/m）;从第一个端点开始，循环计算直线上采样点的实际坐标值，取整，获得最接近直线路径的象素点坐标值，直至循环次数为采样次数-算法结束。ProgramImplementation#defineROUND(a)((int)(a+0.5))voidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya,steps,k;floatx_in,y_in,x=xa,y=ya;if(abs(dx)abs(dy))steps=abs(dx);elsesteps=abs(dy);x_in=dx/(float)steps;y_in=dy/(float)steps;setpixel(ROUND(x),ROUND(y));for(k=0;ksteps;k++){x+=x_in;y+=y_in;setPixel(ROUND(x),ROUND(y));}}DDAexample用DDA算法计算出端点(20,10)与(30,18)之间的中间点坐标。解：dy=8;dx=10;steps=10;x_in=1;y_in=0.8;Stepi(x,y)(xi,yi)020,1020,10121,10.821,11222,11.622,12323,12.423,12424,13.224,13525,1425,14626,14.826,15727,15.627,16828,16.428,16929,17.229,171030,1830,182021222324252627282930101112131415161718DDA算法同一般计算方法的对比一般计算方法y=mx+b，那么直线斜率为m=(y1-y0)/(x1-x0)X的步长用stepx表示，则x和y的每一次变化可用x=x+stepx，y=mx+b表示那么，(x,y)坐标可以确定为(x,round(y))。一般计算方法中每一步需要一次浮点乘法和一次舍入运算DDA算法中用的是加法，没有乘法这样的浮点运算，每一步都要做2次舍入运算DDA算法的优点比直接使用公式y=m*x+b快，没有用乘法;DDA算法还存在的缺点设置增量的除法运算、取整操作和浮点运算仍然耗时；较长线段的误差积累。Bresenham画线算法由Bresenham提出的一种精确而有效的光栅线段生成算法，可用于直线、圆(圆弧)和其它曲线的生成IDEA算法公式推导算法描述(P.75)程序实现(P.76-77)ExampleIDEA只用增量整数计算寻找最接近实际直线的整数坐标下图给出了例子以单位x间隔取样，并且需要确定每次取样时两个可能的像素位置中哪一个更接近于线路径：从端点(10,10)开始，需要确定下一个取样像素位置是(11,11)还是(11,10)10111213141516171819101112131415为解决这个问题，Bresenham算法将对整型参数的符号进行检测，整型参数的值正比于两像素与实际线段之间的偏移。Bresenham算法公式推导假定：0m1，已知(xk,yk)，求下一点(xk+1,yk+1)的两种可能：(xk+1,yk)和(xk+1,yk+1)。其中xk+1＝xk+1推导：设两点与理想直线的距离分别为d1、d2d1＝y－yk＝m*xk+1+b-yk＝m*(xk+1)+b-ykd2＝yk+1－y＝yk+1-m*(xk+1)-bd1－d2＝2m(xk+1)-2yk+2b-1xyxkykyxk+1yk+1d1d2y=mx+bBresenham算法公式推导令m=y/x，代入上述方程引入决策参数Pk，则决策参数Pk表示相对距离，其值为Pk=x(d1-d2)＝2y*xk-2x*yk+C其中C=2y+x*(2b-1)推论（选择距离理想直线更近的点，所以…）如果Pk0,则选择ykPk≥0,则选择yk+1Pk的递推公式由Pk+1=2y*xk+1-2x*yk+1+CPk=2y*xk-2x*yk+C∴Pk+1－Pk=2y－2x(yk+1－yk);由Pk+1－Pk=2y－2x(yk+1－yk);∴Pk的递推公式：P0=2y－xPk+2y(Pk0)Pk+2y－2x(Pk≥0)Pk+1=算法描述（0m1）1)输入直线端点坐标(x0,y0),(xn,yn),并将左端点存储在(x0,y0)中；2)计算常数P0,C1,C2，若P00,下一点的y坐标不变，否则下一点的y坐标加1；3)画起始点(x0,y0)；4)以单位步长增加x坐标，计算Pi+1，确定下一点；5)重复第4步，直至xi=xn。程序实现VoidlineBres(intxa,intya,intxb,intyb){intdx=abs(xa-xb),dy=abs(ya-yb);intp=2*dy-dx;inttwoDy=2*dyinttwoDyDx=2*(dy-dx);intx,y,xEnd;if(xax