基本图形生成算法.ppt

计算机图形学基本图形生成算法
目录
画线
数值微分(DDA)法
中点画线法
Bresenham算法
画圆
中点画圆法
Bresenham画圆法
画椭圆
画线
画线概述
在数学上，理想的点和直线都是没有宽度的。光栅显示器只能近地似显示直线。当我们对直线进行光栅化时，需要在显示器有限个像素中，确定最佳逼近该直线的一组像素，并且按扫描线顺序，对这些像素进行写操作，这个过程称为用显示器绘制直线或直线的扫描转换。
对于水平线、垂直线和45o斜线，选择哪些像素是显而易见的，但是对于其它的直线，确定用哪些像素来表示它就不那麽简单了。因此如何逼近的表示一条直线是画线算法需要解决的第一个问题。
由于在一个图形中，可能包含成千上万条直线，所以要求绘制算法应尽可能地快。如何更快的画线是画线算法需要解决的第二个问题。
目录
画线
数值微分(DDA)法
中点画线法
Bresenham算法
画圆
画线---DDA法
数值微分法（Digital Differential Analyzer）
已知过端点P0 (x0, y0), P1(x1, y1)的直线段L，表示为y=kx+b
直线斜率为
从x的左端点x0开始，向x右端点步进，步长=1(个像素)
X步进后，用y=kx+B，计算相应的y坐标
最后取像素点(x, round(y))作为当前点的坐标。
注意： round(y)为取计算后y的整数，取整函数
画线---DDA法
计算
当 时;
即：当x每递增1，y递增k(即直线斜率)；

数值微分法（Digital Differential Analyzer）
进一步化简计算过程
画线---DDA法
数值微分法（Digital Differential Analyzer）
void DDALine(int x0,int y0,int x1,int y1,int color)

int x；
float dx, dy, y, k;
dx, = x1-x0, dy=y1-y0;
k=dy/dx, y=y0;
for (x=x0; xx1, x++)
 drawpixel (x, int(y+), color);
y=y+k;


画线---DDA法
例：画直线段
x int(y+) y+
0 0
1 0 +
2 1 +
3 1 +
4 2 +
5 2 +
注：假设网格点表示像素
问题：
当 k 1时，会如何？？？
画线---DDA法
注意上述分析的算法仅适用于k ≤1的情形。在这种情况下，x每增
加1,y最多增加1。当 k 1时，必须把x，y地位互换
　　综合考虑，按照从(x1, y1)到(x2, y2)方向不同，分8个象限
()。对于方向在第1a象限内的直线而言，取增量值Dx=1，
Dy=m。对于方向在第1b象限内的直线而言，取增量值Dy=1，Dx=1/m。
画线---DDA法
数值微分法的思考
优点：
最简单，最直接的画线算法
采用增量的思想，每计算一个像素，只需计算一个加法
缺点：
由于斜率很可能是小数（浮点数），因此每个加法都意味着是浮点运算
每次加法 后还必须进行一次四舍五入后的取整运算
浮点运算不利于硬件实现