第四讲二维图元生成算法 4.1二维线画图元的生成 4,2二维填充图元的生成 4.3反混淆算法 所谓图元的生成,是指完成图元的参数表示形式(由图形软 件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所 需的表示形式)的转换。通常也称扫描转换图元 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 1 第四讲 二维图元生成算法 4.1 二维线画图元的生成 4.2 二维填充图元的生成 4.3 反混淆算法 所谓 图元的生成，是指完成图元的参数表示形式 （由图形软 件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所 需的表示形式）的转换。通常也称扫描转换图元
4.1二维线画图元的生成 ?扫描转换直线段 DDA算法 中点画线法 ?圆弧、椭圆弧扫描转换 中点算法 内接多边形迫近法 等面积多边形逼近法 生成圆弧的正负法 ?线画图元的属性控制 北大计算机系多媒体与人机交互 2
北大计算机系多媒体与人机交互 2 4.1 二维线画图元的生成 ？扫描转换直线段 DDA算法 中点画线法 ？圆弧、椭圆弧扫描转换 中点算法 内接多边形迫近法 等面积多边形逼近法 ？生成圆弧的正负法 ？线画图元的属性控制
图形显示的几种方式 图形显 ●裁剪图元二维 扫描 ●扫描 裁剪 转换 ●扫描 存。 设备级显示算法,考虑运算方式、时间、 次数等细节。 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 3 图形显示的几种方式 图形显示前需要：扫描转换+裁剪 ●裁剪---〉扫描转换：最常用，节约计算时间。 ●扫描转换---〉裁剪：算法简单； ●扫描转换到画布--〉位块拷贝：算法简单，但耗时耗内 存。常用于字符显示。 • 设备级显示算法，考虑运算方式、时间、 次数等细节
扫描转换直线段 扫描转换直线段 求与直线段充分接近的像素集 像素间均匀网格 整型坐标系 两点假设 直线段的宽度为1 直线段的斜率:m∈[1,1 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 4 扫描转换直线段 • 扫描转换直线段 – 求与直线段充分接近的像素集 • 两点假设 – 直线段的宽度为1 – 直线段的斜率: m[−1,1] 像素间均匀网格 整型坐标系
扫描转换直线段 DDA( digital differential analyzer)算法 条件: 待扫描转换的直线段:P0(x0,y0)B(x,y) 斜率:m=y/△x 1-x0,△y=y1-y0 直线方程:y=mx+B 直接求交算法: 划分区间x0,x1:x,x2…,xn,其中x+1=x1+1 计算纵坐标:y=m·x1+B 取整:{(x,y)}→(x,y,)} yr=round (i)=(int (y,+0.5) 北大计算机系多媒体与人机交互
北大计算机系多媒体与人机交互 5 扫描转换直线段 • DDA（ digital differential analyzer）算法 – 条件： • 待扫描转换的直线段： • 斜率： • 直线方程： – 直接求交算法： • 划分区间[x0,x1]: • 计算纵坐标： • 取整： ( 0, 0) ( 1, 1) 0 1 P x y P x y x = x1− x0,y = y1− y0 m = y / x y = m• x + B x0 , x1 , , xn ,其中xi+1 = xi +1 yi = m• xi + B n i i i x y 0 {( , )} = n i i r i x y , 0 {( , )} = ( ) (int)( 0.5) yi,r = round yi = yi +