计算机图形生成算法线.ppt

计算机图形生成算法
•内容：
目标：掌握二维图形学的基本思想，理解扫描转换法生成图形的基本原理。
要求：掌握图形的扫描转换、区域填充、裁剪、反走样等概念。
掌握直线段的扫描转换算法、区域填充的扫描线算法、多边形裁剪算法、反走样的基本思想。
熟悉多边形的扫描转换算法、区域采样的基本思想。
了解圆弧的扫描转换算法、字符的基本概念。
1
第三章 输出图元
直线段扫描转换
DDA算法
Bresenham画线算法
中点画线法
圆弧扫描转换
Bresenham画圆算法
中点画圆算法
椭圆弧扫描转换
填充区域图元
2
输出图元
输出图元是基本几何结构。
输出图元种类：点、直线线段、圆、圆锥曲线、二次曲面、样条线段、多边形填色区域、字符串等。
3
图元的生成
所谓图元的生成，是指完成图元的参数表示形式（由图形软件包的使用者指定）到点阵表示形式（光栅显示系统刷新时所需的表示形式）的转换。通常也称扫描转换图元。
扫描转换
顶点（参数）
表示的图形
用户
点阵表示
的图形
光栅显示系统
光栅化
4
像素逼近示意图
可寻址点,即显示器可以找到的点，（x，y）整数地址
一个象素，占有一定面积
5
直线的扫描转换算法
直线的绘制要求：

，即无不定向性和断裂情况
、色泽要均匀

、亮度、线型等
6
直线的扫描转换算法
提出问题：对于给定直线两端点P0(x0,y0)和P1(x1,y1)，如何在屏幕上画出该直线。
三个常用算法：
数值微分法（DDA）
Bresenham算法
中点画线法
7
已知端点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值是用前一步的值加上一个增量来获得,那么这种算法称为增量算法。
8
光栅中 Δ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
9
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看作自变量
10