计算机图形学chp3_Line1

1、计算机图形学计算机图形学吴 伟计算机学院E-mail: wuwei_第三讲 二维图元生成算法所谓 的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称图元。 计算机图形学课程计算机图形学课程Computer Graphics Course要求(1/2)要求（2/2) 3.1 二维线画图元的生成第第3讲讲二维图元生成算法二维图元生成算法 扫描转换直线段 1 , 1m第第1节节二维线画图元的生成二维线画图元的生成001245313245yx线的光栅表示线的数学表示象素扫描线6 扫描转换直线段) 1, 1()0, 0(10y

2、xPyxP01, 01yyyxxxxyk/Bxky1,110iinxxxxx其中Bxkyiiniiiyx0),(niriiyx0,),()5 . 0(int)()(,iiriyyroundy第第1节节二维线画图元的生成二维线画图元的生成 扫描转换直线段kykBxkBxkBxkyiiiii) 1(11第第1节节二维线画图元的生成二维线画图元的生成 扫描转换直线段中点算法中点算法 1 , 0k第第1节节二维线画图元的生成二维线画图元的生成) 1, 1()0, 0(10yxPyxP 扫描转换直线段第第1节节二维线画图元的生成二维线画图元的生成 扫描转换直线段PP2P1第第1节节二维线画图元的生成二维

3、线画图元的生成 扫描转换直线段PP2P1第第1节节二维线画图元的生成二维线画图元的生成判别式的定义判别式的定义d=F(M)=F(Xp+1,Yp+0.5) d的初始值的初始值ld0=F(X0+1,Y0+0.5)=F(X0,Y0)+a+0.5b 因(X0,Y0)在直线上，F(X0，Y0)=0,所以，d0=a+0.5bd的增量（a，a+b) 都是整数，只有初始值包含小数，可以用2d代替d, 2a改写成a+a。u算法中只有整数变量，不含乘除法，可用硬件实现。 扫描转换直线段第第1节节二维线画图元的生成二维线画图元的生成判别式的定义判别式的定义d=F(M)=F(Xp+1,Yp+0.5) 扫描转换直线段中

4、点画线法程序中点画线法程序第第1节节二维线画图元的生成二维线画图元的生成举例：（0,0) (5,2) Bresenham Bresenham画线法画线法(1/2)(1/2)P2 d+k-1 d+k d P P1第第1节节二维线画图元的生成二维线画图元的生成BresenhamBresenham画线法画线法(2/2)(2/2)n若令若令e = d - 0.5，则判断，则判断e符号即可符号即可 当e = 0时，取P2，且e = e+k-1; 当e =0时, 取P2，且e=e+2*y-2*x;当e 0时，取P1，且e = e+2*y;第第1节节二维线画图元的生成二维线画图元的生成BresenhamBr

5、esenham画线法画线法程序程序第第1节节二维线画图元的生成二维线画图元的生成举例：（0,0) (5,2) 扫描转换圆弧n处理对象：圆心在原点的圆弧处理对象：圆心在原点的圆弧n圆的八对称性圆的八对称性第第1节节二维线画图元的生成二维线画图元的生成离散点: 离散角度:u开根，三角函数运算，计算量大，不可取。 ),(,22222riiiiiyxxRyxRyx，（利用隐函数方程取整)sin(),cos(sincosiiRroundRroundRyRx利用参数方程 两种直接离散方法第第1节节二维线画图元的生成二维线画图元的生成 扫描转换圆弧扫描转换圆弧n圆弧的正负划分性圆弧的正负划分性0),(222

6、RyxyxF圆弧外的点：F(X，Y)0圆弧内的点：F(X，Y)0第第1节节二维线画图元的生成二维线画图元的生成 中点画圆法(1/4)PP1P2第第1节节二维线画图元的生成二维线画图元的生成 中点画圆法(2/4)P2P1P中点画圆法(3/4)P2P1P 中点画圆法(4/4)中点画圆法的程序第第1节节二维线画图元的生成二维线画图元的生成举例：圆心在原点，r=8(x,y)d(0,8)-7(1,8)-5(2,8)0(3,7)-7(4,7)2(5,6)1(6,5)4Bresenham画圆法（1/2)Bresenham画圆法(2/2)nDH到圆弧距离的平方为到圆弧距离的平方为： H = (x + 1)2

7、+ y2 - R2 ; D = (x + 1)2 + (y - 1)2 - R2 ; 比较 |H| 与 | D |的大小：若|H | = | D |, 取H；否则取Dn D 0时时，取D或H； 令 DH HD2D + 2y - 1，则： DH = 0时， |H | 0时， |H | | D |, 取D;n D 0时时，D和H都在圆外，取D； D可用增量法计算：可用增量法计算： H: (x, y) = (x+1, y) , D = D + 2x +1 D: (x, y) = (x+1, y-1), D = D + 2x 2y 2 Bresenham画圆法 程序/取D/取H/取D/取H/取D椭圆的

8、扫描转换(1/6)n椭圆方程椭圆方程: F(x, y)=b2x2 + a2y2 a2b2 = 0； a, b为xy轴长短半轴长；n椭圆的对称性，只考虑第一象限椭圆弧生成，分椭圆的对称性，只考虑第一象限椭圆弧生成，分上下两部分，以切线斜率为上下两部分，以切线斜率为-1-1的点作为分界点。的点作为分界点。 区域1 dy/dx-1区域2 dy/dx-1M1M2(Xp1，Yp-0.5)(Xp+0.5，Yp-1)PPdy/dx=-1l斜率dy/dx = -b2x/a2yl移出区域1的条件：dy/dx=-1, 即 椭圆的扫描转换(2/6)l先讨论椭圆弧的上部分先讨论椭圆弧的上部分(Xp，Yp)中点(Xp+

9、1,Yp-0.5) 椭圆的扫描转换(3/6)n根据d1的符号来决定下一像素是取正右方(Xp+1,Yp)，还是右下方(Xp+1,Yp-1)。 d1=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3) d1的增量为的增量为 b2(2Xp+3) d1=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2) d1的增量为的增量为 b2(2Xp+3)+a2(-2Yp+2)d1=F(Xp+1,Yp-0.5) = b2(Xp+1)2+a2(Yp-0.5)2-a2b2椭圆的扫描转换(4/6)nd1的初始条件：椭圆弧起点为(0，b)，第一个中点为(1,b-0.5) n初始判别式： d1

10、0=F(1,b-0.5)=b*b+a*a(-b+0.25)d1=F(Xp+1,Yp-0.5) = b2(Xp+1)2+a2(Yp-0.5)2-a2b2椭圆的扫描转换 直线,圆,椭圆的算法小结n中点画线法中点画线法, 画圆法画圆法,画椭圆法画椭圆法 构造中点判别式构造中点判别式,利用中点与图形的关利用中点与图形的关系系(上下上下,内外内外)nBresenham画线法画线法,画圆法画圆法 与整数网格系的下一个交点更接近于与整数网格系的下一个交点更接近于哪个坐标点哪个坐标点?并行画线与画圆n将顺序算法中的计算平衡分割到各个处将顺序算法中的计算平衡分割到各个处理器上理器上;n线线: 分段分段,段数由处

11、理器个数段数由处理器个数Np决定决定;起始起始x坐标坐标 Xk = X0 + k Xp Xp = ( X + Np -1)/Np n圆圆: 分成等长子圆弧分成等长子圆弧(建立初始建立初始y值值,初始判别式初始判别式)帧缓冲器的装载 n用增量方法计算帧缓冲器地址 addr(x, y) = addr(0,0) + y(xmax+1) + x沿扫描线移动沿扫描线移动: addr(x+1, y) = addr(x,y)+1 沿对角方向沿对角方向: addr(x+1, y+1) = addr(x,y)+xmax+2Xmax0(x,y)ymax像素编址和物体的几何表示n象素在数学上一个无限小的点象素在数学上一个无限小的点,但是在屏幕上但是在屏幕上是一个