直线的绘制(光栅化).ppt

第3章基本光栅图形生成技术
本章的主要内容
本章介绍基本二维图形的绘制,包括直线、圆弧、椭圆弧的生成,多边形的填充以及更一般区域的填充。
显示器是由离散像素组成的矩阵,在绘制具有连续性质的直线、曲线或区域等基本图形时,需要确定最佳逼近它们的像素,这个过程称为光栅化。当光栅化按照扫描线的顺序进行时,它被称为扫描转换。
光栅化和扫描转换是光栅图形学的基本问题,其算法的好坏对系统的效率有直接的关系。
线的生成算法
直线的生成算法
问题所在:
在数学上,直线是连续的,由无数个点构成的集合。x,y坐标均为实数。
但在显示器上,只能用有限的像素表示,像素的坐标是整数值。
因此,绘制时,需要将直线段离散化为有限的像素,这些像素应该尽可能地连续、尽量避免出现锯齿,并最佳逼近于给定的直线段。此外,绘制直线是非常基本的绘图操作,一个图中往往包括成千上万条直线,所以,算法应该尽可能地快。
对于水平线、垂直线和45°线,选择哪些光栅元素是显而易见的,而对于其它方向的直线,像素的选择较为困难。
缺点:每步都需要一个浮点乘法运算和一个四舍五入运算,所以效率太低。由于一个图中可以包含成千上万条直线,所以要求绘制算法应尽可能的快。
给定直线段的两个端点P0(x0,y0)和
P1(x1,y1),斜率截距直线方程:
从起点到终点,x每次增加(或减少)1,用直线方程计算对应的y值,再用SetPixel(x, int(y+),color)输出该像素。上述方法称为直线绘制基本算法。复杂度:乘法+加法+取整
直线绘制基本算法
数值微分(DDA)法
画线过程从x的左端点x0开始,向x右端点步进,x+=x,计算相应的y坐标:y=kx+b,取像素点(round(x), round(y))作为当前点的坐标。
图3-1 DDA算法基本原理
给定直线段的两个端点P0(x0,y0)和 P1(x1,y1),直线方程:
设第i个点(xi,yi), yi= kxi+b
第i+1个点(xi+1,yi+1),
令xi+1= xi+ x,
则yi+1=k(xi+ x)+b=yi+kx
= yi+y, y= kx
当x =1时 yi+1 = yi+k
复杂度:加法+取整
上述采用的增量计算方法称为数值微分算法(Digital Differential Analyzer,简称DDA)。数值微分法的本质,是用数值方法解微分方程,通过同时对x和y各增加一个小增量,计算下一步的x、y值。
注意: x, y的选择.
void DDALine(int x0,int y0,int x1,int y1,int color)
 int i;
float dx, dy, length,x,y;
if (fabs(x1-x0)>=fabs(y1-y0)) length=fabs(x1-x0);
else length=fabs(y1-y0);
dx = (x1-x0)/length; dy=(y1-y0)/length;
i=1;x= x0;y= y0;
while(i<=length)
{
SetPixel (int(x+), int(y+), color);
x=x+dx; y=y+dy; i++;


DDA算法与基本算法相比,减少了浮点乘法,提高了效率。但是x与dx、y与dy用浮点数表示,每一步要进行四舍五入后取整,不利于硬件实现,因而效率仍有待提高。
Bresenham算法
Bresenham算法1965年提出,基本原理是:借助于一个误差量(直线与当前实际绘制像素点的距离),来确定下一个像素点的位置。算法的巧妙之处在于采用增量计算,使得对于每一列,只要检查误差量的符号,就可以确定该下一列的像素位置。
Yi +1
y
yi
xi
xi+1
d2
d1
图3-3 根据误差量来确定理想的像素点
假设当前直线上的像素坐标为(xi, yi),那么下一步需要在列xi+1上确定扫描线y的值。y值要么不变,要么递增1,可通过比较d1和d2来决定。
如图3-3所示,对于直线斜率k在0~1之间的情况,从给定线段的左端点P0(x0, y0)开始,逐步处理每个后续列(x位置),并在扫描线y值最接近线段的像素上绘出一点。
判别式(误差参数):
设Δy=y1-y0, Δx=x1-x0,则k=Δy/Δx,代入上式,得;
是常量,与像素位置无关。令
则di的计算仅包括整数运算,其符号与(d1-d2)的符号相同,可以作为判别式。下一点的选取规则;
当di<0时,直线上理想位置与像素(xi+1,yi)更接近,应取右方像素;
当di>0时,像素(xi+1,yi+1