[互联网]计算机图形学-基本图形的生成与显示.ppt

《[互联网]计算机图形学-基本图形的生成与显示.ppt》由会员分享，可在线阅读，更多相关《[互联网]计算机图形学-基本图形的生成与显示.ppt（79页珍藏版）》请在三一文库上搜索。

1、跨入计算机殿堂的入门篇,计算机图形学 施智平 ,2,如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。,第2章 基本图形的生成与显示,3,图形生成的概念 直线段的扫描转换 圆的扫描转换 椭圆的扫描转换,第2章 基本图形的生成与显示,图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。 图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的像素集的过程。,4,图1. 用像素点集逼近直线,图形生成和扫描转换的概念,1 直线的扫描转换,直线的绘制要求 （1）直线要直； （2）直线的端点要准确，无断裂； （3）直线的亮度

2、、色泽要均匀； （4）画线的速度要快； （5）具有不同的色泽、亮度、线型等。,5,直线的扫描转换,6,在屏幕像素点阵中点亮最佳逼近于理想直线的像素点集的过程 解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，确定其他像素点，画出该直线 数值微分法 中点画线算法 Bresenham算法,数值微分法(DDA法),7,直线P0 P1的斜率：,图2. DDA算法原理,从P0 到P1的点坐标满足,Pi (x, round(y+0.5) 浮点乘法，假发，取整运算,数值微分法(DDA法),迭代增量计算公式：,对点阵而言，相邻的点，x和y只能为1(-1)或0,8,数值微分法(DDA法),9,|

3、k|1的情况，x方向为主位移方向，x=1：,|k|1的情况，y方向为主位移方向，y=1 ：,void DDALine(float x1,float y1, float x2,float y2, int color, HDC hdc) float k,dx,dy,x,y; dx=x2-x1; dy=y2-y1; if(fabs(dx)=fabs(dy) k=dy/dx; else k=dx/dy; /1/k x=x1; y=y1;,while(x=dy) y=y+k; x+; else x=x+k; y+; ,10,数值微分法(DDA法)特点,迭代增量算法 直观、易实现 不利于用硬件实现(浮点数

4、),11,给定理想直线的起点坐标为P0(x0，y0)，终点坐标为P1 (x1，y1)，则直线的隐函数方程为：,12,其中，直线的斜率：,直线水平方向位移： 直线垂直方向位移：,中点画线算法,中点画线算法,直线与空间的关系,13,图3 直线将平面分为三个区域,假定0k1，即0y/x1，x是最大位移方向 当前点 P 的下一点只能取 Pu 或 Pd，可用中点与直线的位置关系来判定，中点偏差判别式,图4 中点算法生成直线的原理,中点M坐标为（xi+1, yi+0.5）, 判别式：,则有：,图5 中点算法生成直线的原理,M（x i2，y i1.5）,M（x i1，y i0.5）,P（xi，yi）,M（x

5、 i1，y i0.5）,M（x i2，y i0.5）,P（xi，yi）,中点偏差判别式的递推,d0,d0,中点偏差判别式的递推公式 在主位移x方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像素? 如图所示，分两种情况讨论。,(1)当d0时, 取右上方的Pu,当d0时, 取正右方的Pd,中点偏差判别式的递推公式,直线的起点坐标为P0（x0，y0），x为主位移方向。因此，第一个中点是（x01，y00.5），相应的d的初始值为：,其中，因为P0（x0，y0）在直线上，所以,则：,中点偏差判别式的初始值,19,改进：用2dx代替d, 令D2

6、dx 则：,中点算法的改进整数化判别式,输入直线的两端点P0(x0,y0)和P1(x1,y1)。 计算初始值x、y、D=x-2y、x=x0、y=y0。 绘制点(x,y)。判断D的符号。 若D0，则(x,y)更新为(x+1,y+1)，D更新为D+2x-2y； 否则，(x,y)更新为(x+1,y), D更新为D-2y。 当直线没有画完时，重复上一步骤，否则结束。 程序演示,20,中点算法算法步骤,Bresenham画线算法,算法原理：考虑0k1的情况， x方向上每次递增一个单位，而y方向的增量为1或0，它取决于实际直线与相邻象素点的距离，这一距离称为误差项,21,假定直线段的0k1,22,Bres

7、enham算法,图10 Bresenham算法绘制直线的原理,Bresenham算法,Bresenham算法原理,24,误差项的计算 d0=0，因为P0在直线上 x每走一步, 误差项d=d+k 一旦d0.5,y+，d=d-1,改进1：令e=d-0.5，改为只判断符号,e0=-0.5， 每走一步: e=e+k if (e0) then e=e-1,y+,误差项的计算 d0=0， 每走一步：d=d+k if (d0.5) then d=d-1, y+,改进2：用E=e*2x来替换e, 去掉k,e0=-0.5 每走一步有e=e+k, x+ if (e0) then e=e-1,y+,E0=-0.5*

8、2x=-x 每走一步有E=(e+k)*2x=E+2y if (e0) then E=(e-1)*2x=E-2x,Bresenham算法算法步骤,1.输入直线的两端点P0(x0,y0)和P1(x1,y1) 2.计算初始值x、y、e=-x、x=x0、y=y0 3.绘制点(x,y) 4.e更新为e+2y，判断e的符号： 若e0，则(x,y)更新为(x+1,y+1)，将e更新为e-2x； 否则，(x,y)更新为(x+1,y) 5.当直线没有画完时，重复步骤3和4；否则结束,27,2 圆的扫描转换,解决的问题：绘出圆心在原点，半径为整数R的圆x2+y2=R2。,28,P（-y，x）,P（-y，-x）,x

9、=-y,P（-x，-y）,P（x，-y）,P（y，-x）,P（y，x）,P（x，y）,P（-x，y）,x=y,x=0,y=0,圆的对称性,八分法画圆,只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法 假定第一象限内的任意点为P(x,y)，可以顺时针确定另外7个点： P（y，x）P（y，x）,P（x,y ）, P（x，y），P（y，x）， P（y，x），P（x，y）。,圆的扫描转换,解决问题：,31,图 2 1/8圆弧,圆的扫描转换,简单方程生成圆弧 中点画圆算法 Bresenham算法,32,简单方程产生圆弧,算法原理：利用其函数方程，直接离散计算。,33,圆的

10、函数方程为：,34,圆的极坐标方程为：,简单方程产生圆弧,中点画圆,构造函数F(x,y)=x2+y2-R2。 对于圆上的点，F(x,y)=0； 对于圆外的点，F(x,y)0； 对于圆内的点，F(x,y)0。,35,给定圆心在原点，半径为整数R的圆，其方程为,理想圆,F（x，y）0,F（x，y）=0,F（x，y）0,图3 中点画圆的原理,中点画圆,当d0时，下一点取 Pu(xi +1,yi)； 当d0时，下一点取 Pd(xi +1,yi-1),38,构造判别式：,误差项的递推（d0）,图14 d0的情况,误差项的递推（d0）,图15 d0的情况,中点画圆,判别式的初始值,41,改进：用d-0.2

11、5代替d 此时有：,d为整数,中点画圆算法步骤,1.输入圆的半径R。 2.计算初始值d=1-R、x=0、y=R。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号： 若d0，d更新为d+2x+3， (x,y)更新为(x+1,y)； 否则，d更新为d+2(x-y)+5,(x,y)更新为(x+1,y-1)。 5.当xy时，重复步骤3和4。否则结束。 程序演示,43,该算法以点(0,r)为起点，按顺时针方向生成圆时，相当于在第一象限内，所以 y是 x 的单调递减函数。 已知当前点(xi, yi)，下一点(x, y)的公式为： y的计算需要简化,Bresenham画圆法,下一点只

12、能取 Pu 或Pd y的取值只能是 yi 或 yi -1 令d1、d2分别为yi到y、 yi -1到y的距离，可知： 令判别式di=d1-d2，并代入d1、d2，则有：,Bresenham画圆法,（1）当d0时，下一点取 Pu(xi +1,yi)； 递推公式为： （2）当d0时，下一点取 Pd(xi +1,yi-1) 递推公式为： （3）计算判别式的初值。初始点为（0，R），则：,算法实现,void CMyView:OnBresenhamcircle() CDC *pDC=GetDC(); int x0=100,y0=100,x,y,r=80,c=0; /黑色圆弧 float e,d; e=3

13、-2*r;x=0;y=r; while(xSetPixel(x+x0,y+y0,c);/加圆心坐标 pDC-SetPixel(-x+x0,y+y0,c); pDC-SetPixel(-x+x0,-y+y0,c); pDC-SetPixel(x+x0,-y+y0,c); pDC-SetPixel(y+x0,x+y0,c); pDC-SetPixel(-y+x0,x+y0,c); pDC-SetPixel(-y+x0,-x+y0,c); pDC-SetPixel(y+x0,-x+y0,c); ReleaseDC(pDC); ,椭圆的生成算法,1. 椭圆的特征,49,椭圆的生成算法,椭圆函数:,对于

14、椭圆上的点，F(x,y)=0； 对于椭圆外的点，F(x,y)0； 对于椭圆内的点，F(x,y)0。,1. 椭圆的特征,解决第1象限问题：以弧上斜率为1的点作为分界将第一象限椭圆弧分为上下两部分。,A（0，b）,B（a，0）,y向分量,法矢量,x向分量,C( , ),椭圆的法矢量,引理：若在当前的中点（xm,ym） ，法向量的y分量比 x 分量大，即：,而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。,法向量,1. 椭圆的特征,先推导上半部分的椭圆绘制公式,2.上部分算法推导,判别式,若 di0，取 Pu(xi+1,yi) 若 di 0，取 Pd(xi+1,yi-1),2.上部分

15、算法推导,误差项的递推 di0：,增量：,2.上部分算法推导,di0：,判别式的初始值：,增量为：,2.上部分算法推导,椭圆上法矢量的分量 x向分量为： y向分量为：,在上半部分，法矢量的x向分量小于y向分量 在C点，法矢量的x向分量等于y向分量 在下半部分，法矢量的x向分量大于y向分量 则对于上半部分椭圆上任意一点P(xi，yi)在其当前中点M（xi1，yi0.5）处，满足x向分量小于y 向分量：,3.下部分算法推导,P（xi，yi）,Pu（xi1，yi）,Pl（xi，yi1）,M（xi1，yi0.5）,Pd（xi1，yi1）= Pr（xi1，yi1）,图 下半部分的中点,3.下部分算法推导

16、,3.下部分算法推导,假定图中P(xi，yi)点是椭圆上半部分的最后一个像素，M(xi1，yi0.5)是用于判断点亮Pu和Pd像素的中点。 由于下一像素转入了下半部分，所以其中点改为判断 Pl 和 Pr 的中点 M(xi0.5，yi1),椭圆弧下半部分的绘制公式 原理,3.下部分算法推导,判别方法：,若di0，取Pl(xi,yi-1) 若di0，取Pr(xi+1,yi-1),3.下部分算法推导,判别公式：,误差项的递推 di0：,增量：,3.下部分算法推导,di0：,增量：,3.下部分算法推导,4.中点椭圆算法小结,第象限内椭圆弧的中点算法可以概括为：,算法实现,void CTestView:

17、OnMidpointellispe() CDC *pDC=GetDC(); int a=100,b=300,x,y,color=50; float d1,d2; x=0;y=b; d1=b*b+a*a*(-b+0.25); pDC-SetPixel(x,y,color); pDC-SetPixel(-x,-y,color); pDC-SetPixel(-x,y,color); pDC-SetPixel(x,-y,color); while(b*b*(x+1)a*a*(y-0.5) if(d1=0) d1+=b*b*(2*x+3); x+; else d1+=b*b*(2*x+3)+a*a*(-

18、2*y+2); x+; y-; ,pDC-SetPixel(x,y,color); pDC-SetPixel(-x,-y,color); pDC-SetPixel(-x,y,color); pDC-SetPixel(x,-y,color); /*while上半部分*/ d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b; while(y0) if(d2SetPixel(x,y,color); pDC-SetPixel(-x,-y,color); pDC-SetPixel(-x,y,color); pDC-SetPixel(x,-y,color); ,6

19、5,用离散量表示连续量引起的失真，就叫做走样（Aliasing）。,反走样,图 绘制直线时的走样现象,反走样,产生原因： 数学意义上的图形是由无线多个连续的、面积为零的点构成；但在光栅显示器上，用有限多个离散的，具有一定面积的象素来近似地表示他们。,66,67,走样现象： 一是光栅图形产生的阶梯形。 一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产生闪烁。,反走样,例子,图。 丢失细节与运动图形的闪烁,用于减少或消除这种效果的技术，称为反走样（antialiasing，图形保真）。 一种简单方法：硬件分辨率,图 分辨率提高一倍，阶梯程度减小一倍,软

20、件反走样方法,空间混色原理 人眼对某一区域颜色的识别是取这个区域颜色的平均值。 过取样（supersampling），或后滤波 区域取样（area sampling），或前滤波,70,71,过取样：在高于显示分辨率的较高分辨率下用点取样方法计算，然后对几个象素的属性进行平均得到较低分辨率下的象素属性。,反走样过取样（super sampling）,简单过取样 在x，y方向把分辨率都提高一倍，使每个象素对应4个子象素，然后扫描转换求得各子象素的颜色亮度，再对4个象素的颜色亮度进行平均，得到较低分辨率下的象素颜色亮度。,图 简单的过取样方式,重叠过取样：为了得到更好的效果，在对一个像素点进行着色处

21、理时，不仅仅只对其本身的子像素进行采样，同时对其周围的多个像素的子像素进行采样，来计算该点的颜色属性。,图 重叠过取样,基于加权模板的过取样： 前面在确定像素的亮度时，仅仅是对所有子像素的亮度进行简单的平均。 更常见的做法是给接近像素中心的子像素赋予较大的权值，即对所有子像素的亮度进行加权平均。,图 常用的加权模板,75,计算直线段与像素相交区域的面积,反走样简单的区域取样,图 重叠区域面积的计算,76,过取样中，我们对所有子像素的亮度进行简单平均或加权平均来确定像素的亮度。 在区域取样中，我们使用覆盖像素的连续的加权函数（Weighting Function）或滤波函数(Filtering Function)来确定像素的亮度。,反走样加权区域取样,图 常用的滤波函数,78,特点： 接近理想直线的象素将被分配更多的灰度值； 相邻两个象素的滤波器相交，有利于缩小直线条上相邻象素的灰度差。,反走样加权区域取样,本章小结,直线段、圆、椭圆 简单方程生成 中点扫描转换 Bresenham算法,79,