文档介绍：图形显示的几种方式
设备级显示算法,考虑运算方式、时间、次数等细节。
所谓图元的生成,是指完成图元的参数表示形式(由图形软件包的使用者指定)到点阵表示形式(光栅显示系统刷新时所需的表示形式)的转换。通常也称扫描转换图元。
图形显示前需要:扫描转换+裁剪
裁剪---〉扫描转换:最常用,节约计算时间。
扫描转换---〉裁剪:算法简单;
扫描转换到画布--〉位块拷贝:算法简单,但耗时耗内存。常用于字符显示。
第3章图形显示算法基础
1
直线的生成算法
基本知识
只有画水平线,垂直线,及正方形对角线时,象素点集的位置才是准确的。
显示一条直线,实际上是用最靠近这条直线的象素点集来近似地表示这条直线.
有限的象素矩阵
画点设备
光栅显示器: 缓冲存储器,显示控制器,
数/模转换器,阴级射线管(CRT)
A(x1,y1)、
B(x2,y2)、
在纸上画一条直线和在计算机屏幕上画一条直线有什么本质的区别?
2
生成直线的一般要求是:
(数值微分法)
确定象素最佳逼近某图形的过程通常称为光栅化。
图形生成算法的工作:
在显示器所给定的有限个象素组成的矩阵中, 确定最佳逼近于图形的象素点集.
象素是均匀分布的
,且有精确的起点和终点
,且与直线的长度和方向无关。
直线光栅化的方法
3
已知端点A(x1, y1)、
B(x2, y2),
直线的微分方程:
dy/dx=(y2-y1)/(x2-x1)=常数=m
yi+1=yi+ (y2-y1)/(x2-x1)*Δx
= yi + m* Δx
yi =m xi + B
yi+1 = m xi +1 + B
= m (xi + Δx ) +B
A(x1,y1)
B(x2,y2)
Pi
(xi,yi)
Pi+1
(xi+1,yi+1)
dy=k·dx
dx
DDA算法(Digital Differential Algorithm)
通过同时对x,y各增加一个小的增量,计算下一步的x,y值。在一个迭代算法中,如果每一步的x,y值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。
4
光栅中Δx=1
直线的递推公式
yi+1=yi+ (y2-y1)/(x2-x1)
xi+1=xi+1
double x=x1, y=y1;
m=(y2-y1)/(x2-x1);
int k=abs(x2-x1);
for( int i=0; i<k; i++)
{
x=x+1;
y=y+m;
}
如果x2>x1≥0, y2>y1≥0
5
o
x
y
k>1
讨论:
o
x
y
k<1
xi+1=xi+1
yi+1=yi+k
yi+1=yi+1
xi+1=xi+1/k
(xi,yi)
(xi+1,yi+1)
(xi,yi)
(xi+1,yi+1)
因而造成隔行显示
解决办法:
将y看作自变量
6
结论:第一象限的直线DDA算法:
(round(xi+1), yi+1)
yi+1=yi+1
xi+1=xi+1/k
k>1
(xi+1,round(yi+1))
xi+1=xi+1
yi+1=yi+k
k<1
逼近直线的
象素点的坐标
直线上点的坐标
递推公式
直线的斜率
起点(x1, y1),终点(x2, y2)(x2> x1, y2> y1)
以(x1, y1)为起点
7
DDA算法的优、缺点
DDA算法的本质:
效率低,不利于硬件实现
直观可行
DDA算法也是一个增量算法。
缺陷:
做除法;
须采用浮点数据计算
要取整数->算法效率不高
算法程序实现
k=abs(x2-x1);
if(abs(y2-y1)>k)
double deltx=(x2-x1)/k;
double delty=(y2-y1)/k;
for(int i=0;i<=k;i++)
{
x+=deltx;//x=x+deltx;
y+=delty;//y=y+delty;
}
k=abs(y2-y1);
putpixel((int)x,(int)y,2);
用数值方法解微分方程(数值微分法)
8
,迅速确定直线上的点。
借助于一个决策变量 d的正负符号,来确定下一个该点亮的象素点。
最逼近Pi+1点的象素点是Ti+1点还是Si