逐点画线算法(3/19)
根据所画图线的已知条件(如直线两个 端点坐标等)计算画图所需要的一系列中间 点(即折线的端点)的坐标，称为插补运算。 插补运算可用软件或硬件实现，不少绘图 机采用插补器(或称线发生器、弧发生器) 来完成插补运算，目的在于提高图线生成 速度。逐点比较法可用于插补运算。
逐点画线算法(4/19)
什么是光栅图形学？
光栅显示器 －> 图形光栅化、 光栅化图形的处理
光栅显示器上显示的图形，称之为光栅图 形。光栅显示器可以看作是一个象素矩阵， 在光栅显示器上显示的任何一个图形，实 际上都是一些具有一种或多种颜色和灰度 象素的集合。由于对一个具体的光栅显示 器来说，象素个数是有限的，象素的颜色 和灰度等级也是有限的，象素是有大小的， 所以光栅图形只是近似的实际图形。如何 使光栅图形最完美地逼近实际图形，便是 光栅图形学要研究的内容。以后，我们提 到“显示器”时，如未特别声明，均指光 栅显示器。
2.2 逐点画线算法 在数学上，理想的直线是没有宽度 的，由无数个点构成的集合。当我 们对直线进行光栅化时，只能在显 示器所给定的有限个像素中，确定 最佳逼近于该直线的一组像素。用 写点方式对像素进行写操作，这就 是通常所说的用显示器绘制直线， 或直线的扫描转换
逐点画线算法(1/19)
逐点比较法算法的基本思想是：在绘制直线 的过程中，每绘制一个点就与原直线进行比 较，根据比较的结果决定下一步的走向，这 样一步一步逼近直线，逐点比较法的执行过 程如下：
第二章 直线扫描转换算法
1.光栅图形学 2.逐点画线算法
3.DDA画线算法
4.BRESENHAM画线算法
5.关于线宽线型
6.Visual
C++中基本绘图函数
2.1 光栅图形学
计算机图形学已成为计算机技术中
发展最快的领域，计算机图形软件 也相应得到快速发展。计算机绘图 显示有屏幕显示、打印机打印图样 和绘图机输出图样等方式，其中用 屏幕显示图样是计算机绘图的重要 内容。
逐点画线算法(16/19)
case 1 : { xx=x1; yy=y1; for (i=0;i<=k;i++) { pDC->SetPixel(xx,yy,color); if (((x2-x1)*(yy-y1)-(xx-x1)*(y2-y1))>=0) xx=xx+1; else yy=yy+1; } } return;
的终点为止。终点判断可由X及Y向总走步数
J(J=|x(a)|+|y(a)|)来控制，每走一步J减去1，当
J=0 时即到达终点。
逐点画线算法(8/19)
对其他象限内直线段生 成计算走步方向的规定 如下图所示。偏差的递 推计算均按以下两式进 行： 当沿X方向走步时， F(k+1)=F(k)-|y(a)|； 当沿Y方向走步时， F(k+1)=F(k)+|x(a)|。
一个对象，实质上是往帧缓存 寄存器的相应单元中填入数据。 画一条从（x1, y1）到 （x2, y2）的直线，实质上是一 个发现最佳逼近直线的象素序 列，并填入色彩数据的过程。 这个过程也称为直线光栅化。
直线扫描转换的本质
直线的扫描转换
确定最佳逼近于该直线的一组象素 按扫描线顺序，对这些象素进行写操作，
Y Fk＜0 Fk＜0
Fk≥0 O
Fk≥0
X Fk≥0 Fk＜0
Fk＜0
Fk≥0
逐点画线算法(9/19)
画点
LINE(0,0)TO(5,2)
F(0)=0 F(1)<0
(0,0)
(1,0) (1,1)
2
1
F(2)>0
F(3)>0 F(4)<0 F(5)>0 F(6)>0
(2,1)
(3,1) (3,2) (4,2) (5,2)
对一维图形，不考虑线宽，则用一个像 素宽的直线来显示图形。 任何图形的光栅化，必须显示在一个窗 口内，否则不予显示。即确定一个图形 的哪些部分在窗口内，哪些在窗口外， 即裁剪。
图形显示前需要：扫描转换+裁剪 裁剪---〉扫描转换：最常用，节约计算 时间。 扫描转换---〉裁剪：算法简单；
if (a1<a2&&b1>b2) { x1=a1; y1=b1; x2=a2; y2=b2; itype=2; } if (a1>a2&&b1<b2) { x1=a2; y1=b2; x2=a1; y2=b1; itype=2; }
逐点画线算法(14/19)
逐点画线算法(18/19)
注意：从一个理论上的算法提炼到具体一 个编译器可以运行编译的程序，可能会有 多种不同的编写程序方法，但执行效果是 一样的，都能体现算法的精髓。 上面的逐点画线算法没有实现计算误差中 F(K)的递推工作，效率可能会低点，同学 们可以考虑把这个可执行无误算法改进一 下。 优秀的程序不仅要求无误执行，还要有良 好的性能，茁壮性（出错处理好）等要求。
当K在OA上时，F(k)=0;
K在OA上方时，F(k)>0; K在OA下方时，F(k)<0。
逐点画线算法(6/19)
对第一象限内直线的生成规定如下： 当F(k)≥0时，绘图笔从当前位置沿+X方向走 一步，记作+Δx； 当F(k)<0时，绘图笔从当前位 置沿+Y方向走一步，记作+Δy；在绘图笔到达新 的位置时，应计算出新位置的偏差，为判断绘图 笔下一步走向作准备。 绘图笔走+Δx时，新点坐标为 X(k+1)=x(k)+1, y(k+1)=y(k) 这时新点偏差为 F(k+1)=x(a)y(k+1)-x(k+1)y(a)=x(a)y(k)x(k)y(a)-y(a)=F(k)-y(a)
逐点画线算法(17/19)
case 2 : { xx=x1; yy=y1; for (i=0;i<=k;i++) { pDC->SetPixel(xx,yy,color); if (((x2-x1)*(y1-yy)-(xx-x1)*(y1-y2))>=0) xx=xx+1; else yy=yy-1; } } return; } }
逐点画线算法(15/19)
//前面的代码具有我自己的风格，因为VC的 工作区坐标的特性，我们分析以后，画线存 在二个类型，即把理论中的分四个象限画线 情况归结为二类，画线起点和始点我们灵活 变化一下，简化编程。 int k=abs(x2-x1)+abs(y2-y1); // 书上的终点判别不是这么求的 xx=x1; yy=y1; switch (itype) {
逐点画线算法(5/19)
若画第一象限的直线OA，如上页图所示， 起点为O(0，0)， 终点为A(xa, ya)，设绘 图笔当前的位置为K(xk,yk)，这里坐标均 为局部坐标。点K相对于直线OA的位置有三 种情况：点K在OA上方，点K在OA上以及点K 在OA下方。为判断点K与OA的相对位置，引 入偏差函数F(k)。 F(k)=x(a)y研究内容
直线段的扫描转换算法 圆弧的扫描转换算法 多边形的扫描转换与区域填充
字符
裁剪 反走样 消隐
直线段是最基本的图形，因此直线段生成 的质量好坏与速度快慢将直接影响整个图 形生成的质量和速度。所以直线段生成算 法在图形软件设计中起着关键的作用。 如果已知屏幕中直线段的二个端点，可以 有多种不同的数学方法来决定应改变在二 端点之间的哪些像素的亮度值才能显示出 二点间的直线，生成直线段的算法之间区 别主要是判别和生成x，y增量过程和方法 不同，所能适应的设备环境也不同。下面 介绍三种基本的画线算法。
void CMyView::OnPointline() { CDC *pDC=GetDC(); COLORREF color=RGB(255,0,0); // 前面四句就是设备环境，当然表现形式可以不
一样
逐点画线算法(12/19)
int a1=30; int b1=30; int b2=800; int a2=600; //我们实现最简单的画线算法，二点已经确定 //后面我们再讲如何交互 int x1,y1,x2,y2; //起始点坐标 int itype; //画线不同循环类型 int i; int xx,yy;
0
1
2
3
4
5
逐点画线算法(10/19)
优点： 整个算法实现可以使用整数，没有使 用浮点数运算，没有乘除运算，所以适合 硬件实现，大多数绘图仪使用这个算法。 缺点： 逐点画线法一次只能位移一步，所以 画出来的直线粗细不均匀。
逐点画线算法(11/19)
逐点画线算法VC源代码（不包含交互内
容，直接内置画线段的起始点，并且没 有实现F(k)计算的递推工作）
逐点画线算法(19/19)
上面这个程序还有些bug，那就是 不能绘制水平或竖直的直线，还有 未能实现F(k)的递推工作，这些留 给同学们去做，可以在程序中加入 一些代码来解决这个问题。同学们 还可以根据自己对算法的理解重新 编写代码，不用和我编写的思路一 样。比如实现四象限方向画图，判 断F(k)的正负，如果为正，分四种 象限情况走步，如果为负，分四种 象限情况走步。
计算机上常见的显示器为光栅图形显示器，光栅 图形显示器可以看作像素的矩阵。像素是组成图 形的基本元素，一般称为“点”。通过点亮一些 像素，灭掉另一些像素，即在屏幕上产生图形。 在光栅显示器上显示任何一种图形必须在显示器 的相 应像素点上画上所需颜色，即具有一种或 多种颜色的像素集合构成图形。确定最佳接近图 形的像素集合，并用指定属性写像素的过程称为 图形的扫描转换或光栅化。对于一维图形，在不 考虑线宽时，用一个像素宽的直、曲线来显示图 形。二维图形的光栅化必须确定区域对应的像素 集，并用指定的属性或图案进行显示，即区域 填充。
