哈尔滨工业大学计算机科学与技术学院：《计算机图形学》第3章 基本图形生成算法（一）（苏小红）

笔吕章寓 形生笔法 题影约扫数 计算机学院 苏小红

第三章 基本图 形生成算法 计算机学院 苏小红

基本图形生成算法 ·图元扫描转换 直线段扫描转换 ■圆弧扫描转换 ·实区域填充 ·图形反走样

基本图形生成算法 图元扫描转换 ◼ 直线段扫描转换 ◼ 圆弧扫描转换 实区域填充 图形反走样

光栅图形中点的表示 (xy)坐标 地址线性表 显示屏幕 1D表示 2D表示 像素由其左下角坐标表示

光栅图形中点的表示 … (x,y)坐标 地址线性表 1D表示 显示屏幕 2D表示 像素由其左下角坐标表示

光栅图形中点的表示 ym mmin 地址=( Maxmin)2( y-ymin)+(x-xmn)+基地址 每行像素点数行数 行中位置

光栅图形中点的表示 地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 x y xmin xmax ymax ymin 每行像素点数 行数 行中位置

光栅图形中点的表示 Address(x,y)=( maximin)*(yym)+(xm)+基地址 =k1+ kay+x 对像素连续寻址时,如何减少计算量? Address(x+1y)=kl+k2y+(x±1)= Address(x,y)±1 Address(x, y+1)=k1 k20 +1)+x=Address(xy)+ k2 Address(x±1y+1)=kl+k2(y±1)+(x士1) Address(x,y)±k2±1 增量法的优点?

光栅图形中点的表示 Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + x Address(x±1,y) = k1 + k2y + (x±1) = Address(x,y) ± 1 Address(x,y±1) = k1 + k2(y ±1) + x = Address(x,y) ± k2 Address(x±1,y±1) = k1 + k2(y ±1) + (x±1) = Address(x,y)± k2 ± 1 对像素连续寻址时，如何减少计算量？ 增量法的优点？

图形显示的几种方式 图形显示前需要:扫描转换+裁剪 ·裁剪→扫描转换:最常用,节约计算时间 ·扫描转换→裁剪:算法简单

图形显示的几种方式 图形显示前需要：扫描转换+裁剪 裁剪→扫描转换：最常用，节约计算时间 扫描转换→裁剪：算法简单

直线段扫描转换 假设 像素间均匀网格,整型坐标系,直线段斜率01,X、y互换

直线段扫描转换 假设 ◼ 像素间均匀网格，整型坐标系，直线段斜率0<m<1 ◼ 对m＞1，x、y互换

直线段的扫描转换算法 直线的描转换 确定最佳逼近于该直线的一组象素 按扫描线顺序,对这些象素进行写操作 三个常用算法: 1数值微分法(DDA) 2中点画线法 3 Bresenham算法

直线段的扫描转换算法 直线的扫描转换 ◼ 确定最佳逼近于该直线的一组象素 ◼ 按扫描线顺序，对这些象素进行写操作 三个常用算法： 1数值微分法（DDA） 2中点画线法 3Bresenham算法

数值微分DDA)法(1/5) 已知线段端点:Px00,P1(x1y) 直线方程 y=kX+b {(×1,y)},i=0 ●浮点数取整:y= Roundly)=(int)y+0.5) 用到浮点数的乘法、枷法和取整运算 (2+m) xi,yi (x,, round( ) (x1+1,+m)

数值微分(DDA)法(1/5) 已知线段端点：P0 (x0 ,y0 ), P1 (x1 ,y1 ) 直线方程 y=kx+b {(xi , yi )}, i=0,….n. 浮点数取整 : yi=round(yi )=(int)(yi+0.5) ◼ 用到浮点数的乘法、加法和取整运算

数值微分(DDA法(2/5) 增量算法 yi+1=kX+1+b=k(X+1)+b=yi+k a(,y)→(x+1,y+k) 点: 有浮点数取整运算 不利于硬件实现 效率低 仅适用于k≤1的情形X每增加1,y最多增加1。当 k|>1时,必须把x,y互换

数值微分(DDA)法(2/5) 增量算法 ◼ yi+1=kxi+1+b=k(xi+1)+b=yi+k ◼ (xi ,yi )→(xi+1,yi+k) 缺点： ◼ 有浮点数取整运算 ◼ 不利于硬件实现 ◼ 效率低 ◼ 仅适用于k ≤1的情形:x每增加1,y最多增加1。当 k 1时，必须把x，y互换