文档介绍：第二章基本图形的生成算法
习题:
1. 将中点画线方法推广,使之能画出任意斜率的直线
2. 用DDA法,中点画线法和 Bresenham 算法画从(0,0)到(-10,-5)间的的直线段
3. 编写按逆时针方向生成中心在原点的第一个8分圆的中点画圆算法,导出递
推公式
4. 推导用中点画圆算法画中心在原点的第一象限椭圆弧的递推算法
习题可以交电子文挡,请用Word文件格式,以附件形式发送到:
wgz-******@tsinghua., 或 gw_99@
11/11/2017
第二章 基本图形的生成算法
11/11/2017
光栅扫描图形系统
光栅扫描图形系统的结构
光柵扫描特点: * 数据量大- 快的要求
* 显示的离散化- 准的要求
* 独立的图形显示处理器- 快速,实时硬件处理的扫描转换
CPU
系统总线
显示处理器
系统存储器
显示处理器存储器
帧缓存
视频控制器
I/O设备
监视器
11/11/2017
图形显示处理器(加速引擎)
任务:进行扫描转换(Scan Conversion)
扫描转换:将应用程序给出的图形定义数字化为一组像素强度
值,并放到帧缓存器
扫描转换的工作内容:
-基本图形的生成
-字符的生成
-填充、裁剪
-线型的处理
-彩色处理
-某些变换和管理
11/11/2017
坐标系统 为描述对象、构造场景或完成图形变换,需要不同的坐标系!
1. 建模坐标系 -定义对象
2. 世界坐标系 -定义对象与外界环境的关系
3. 设备坐标系 -定义图形显示的位置、大小
4. 规范化坐标 -为保证互换性(与设备无关)而定义的辅助坐标
建模坐标
Modeling Coordinate
Local Coordinate
Master Coordinate
世界坐标
World Coordinate
绘图仪
其它输出设备
设备坐标
Device Coordinate
Screen Coordinate
1
1
1
规范化坐标
Normalized
Coordinate
11/11/2017
光栅扫描下直线的画法
光栅扫描显示下画直线存在的问题:
(1) 显示速度问题:
例: 分辨率:1024×768, 24Bit 彩色,
帧存容量:1024×768×3= 2,359,296 Byte
刷新率 85Hz: 85× 2,359,296 =200,540,160 (Byte / S)
存储器读出时间:~5nS
(2) 显示质量问题:
阶梯状
线的粗细不一
线的亮度差异
11/11/2017
一、DDA法(Digital Differential Analyzer)
一种从直线的微分方程出发生成直线的方法,其本质是用数值法解微分方程
直线的微分方程:
k: 直线的斜率
DX,DY:直线起、终点差值
考虑当前位置(x, y), 分别构造 eDX, eDY, 从而求出下一点(x’, y’)的
坐标, 即: x’= x + eDX
y’= y + eDY
若取适当的 e, 保证eDX, eDY都小于单位步长,即每次计算增量
小于1,就可以构造如下算法模块:
11/11/2017
一、DDA法(续)
整数部分
小数部分
+
eDX
整数部分
小数部分
+
eDY
x
y
讨论:
小数部分按四舍五入原则拟合最接近的理想直线
增量值和寄存器小数部分精度不能低于显示器精度,可取e =2-n, 且取
2n-1 < max(|Dx|,|Dy|) <= 2n
需要两套寄存器和加法器等电路,电路复杂,工作量大,可简化为e=1/max(|Dx|,|Dy|),
于是将有一个 eDX 或 eDY 变为单位步长,可用简单记数代替加法运算。
需浮点运算,舍入取整运算,较费时
11/11/2017
二、中点画线法
考虑第一个八分圆内直线(x0,y0)-(x1,y1)
直线方程:F(x, y) = ax+by+c=0
其中: a=y0-y1 -整数
b=x1-x0 -整数
c=x0y1-x1y0
在直线上的点:F(x,y) = 0
直线上方的点:F(x,y) > 0
直线下方的点:F(x,y) < 0
(xp,yp)
P1
P2
M
假设已经确定点(xp,yp)为当前画的点,M是待选点P1,P2的中点
构造判别式:d = F(M) = F(xp+1, yp+)
= a(xp+1) + b(yp+) + c
若d < 0 ,M点在直线下方,取P2,否则取P1
11/11/2017
中点画线法(续)
根据上述判别式可确定下一像