基本图形生成算法..ppt

哈尔滨工业大学计算机学院
唐好选
2018年6月5日
基本图形生成算法
基本图形生成算法
图元扫描转换
直线段扫描转换
圆弧扫描转换
实区域填充
图形反走样技术
光栅图形中点的表示
…
(x,y)坐标
地址线性表
1D表示
显示屏幕
2D表示
像素由其左下角坐标表示
光栅图形中点的表示
地址= (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址
x
y
xmax
xmin
ymax
ymin
每行像素点数
行数
行中位置
光栅图形中点的表示
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
对像素连续寻址时,如何减少计算量?
增量法的优点?
图形显示的几种方式
图形显示前需要:扫描转换+裁剪
裁剪→扫描转换:最常用,节约计算时间
扫描转换→裁剪:算法简单
直线段扫描转换
假设
像素间均匀网格,整型坐标系,直线段斜率0<m<1
对m>1,x、y互换
直线段的扫描转换算法
直线的扫描转换
确定最佳逼近于该直线的一组象素
按扫描线顺序,对这些象素进行写操作
三个常用算法:
- 数值微分法(DDA)
- 中点画线法
- Bresenham算法
数值微分(DDA)法(1/5)
已知线段端点:P0(x0,y0), P1(x1,y1)
直线方程
y=kx+b, {(xi, yi)}, i=0,….n.
浮点数取整: yi=round(yi)=(int)(yi+)
用到浮点数的乘法、加法和取整运算
数值微分(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互换。