第2章 基本图形生成算法
- 格式：ppt
- 大小：1.01 MB
- 文档页数：95
下载文档原格式
合集下载
【华科 CAD技术与应用】第2讲 计算机图形学基础-基本图形生成
— CRT显示器工作原理 — LCD显示器工作原理
2.3．基本图形生成算法
— 直线生成算法 — 圆弧生成算法 — 其它基本图形生成
2.4．图形裁减算法 2.5．多边形填充算法（选学） 2.6．图形反走样算法（选学） 2.7．基于OpenGL图形库生成图形（选学）
华中科技大学CAD中心
思考问题：
1）图形如何在屏幕上显示出来？？ 2）CAD图形如何生成？？
象素的亮度值控制电子束对荧光屏的轰 击强度，象素在帧缓存寄存器中的位置编码 控制电子束的偏转位置。
图形系统为灵活控制图形颜色变化，往 往不直接将帧缓冲器中的数值作为显示的亮 度值，而是先经过颜色查找表（称调色板) 产生变换值来控制光点亮度。其工作方式：
显存中某位值 度
颜色表地址
华中科技大学CAD中心
为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）。
不妨设函数：
F (x, y) = x2 + y 2 - r 2
显然有： F（x，y）< 0，则（x,y)位于圆边界内 F（x，y）＝ 0，则（x,y)位于圆边界上 F（x，y）> 0，则（x,y)位于圆边界外
考虑到圆的八对称 性，不妨以第二个 八分圆进行分析， 其它八分圆则可通 过镜像实现。
华中科技大学CAD中心
刷新频率
（仅CRT）
每秒钟重绘屏幕的次数， CRT产生稳定图像所需要的最小刷新频率： = 1秒 / 荧光物质的持续发光时间 （Hz）
注：液晶显示器原理不同于CRT，不受刷新频率影响。但液晶显示 有拖尾现象，是因液晶偏转延迟所致，延时越长，拖尾越重。
帧扫描
与电视工作原理类 似，CRT电子束从上 到下、从左到右扫描 进行，每扫描一遍称 为一帧。
2.3．基本图形生成算法
— 直线生成算法 — 圆弧生成算法 — 其它基本图形生成
2.4．图形裁减算法 2.5．多边形填充算法（选学） 2.6．图形反走样算法（选学） 2.7．基于OpenGL图形库生成图形（选学）
华中科技大学CAD中心
思考问题：
1）图形如何在屏幕上显示出来？？ 2）CAD图形如何生成？？
象素的亮度值控制电子束对荧光屏的轰 击强度，象素在帧缓存寄存器中的位置编码 控制电子束的偏转位置。
图形系统为灵活控制图形颜色变化，往 往不直接将帧缓冲器中的数值作为显示的亮 度值，而是先经过颜色查找表（称调色板) 产生变换值来控制光点亮度。其工作方式：
显存中某位值 度
颜色表地址
华中科技大学CAD中心
为叙述方便，仅考虑圆心在原点的圆（其它位置圆可平移到原点位置）。
不妨设函数：
F (x, y) = x2 + y 2 - r 2
显然有： F（x，y）< 0，则（x,y)位于圆边界内 F（x，y）＝ 0，则（x,y)位于圆边界上 F（x，y）> 0，则（x,y)位于圆边界外
考虑到圆的八对称 性，不妨以第二个 八分圆进行分析， 其它八分圆则可通 过镜像实现。
华中科技大学CAD中心
刷新频率
（仅CRT）
每秒钟重绘屏幕的次数， CRT产生稳定图像所需要的最小刷新频率： = 1秒 / 荧光物质的持续发光时间 （Hz）
注：液晶显示器原理不同于CRT，不受刷新频率影响。但液晶显示 有拖尾现象，是因液晶偏转延迟所致，延时越长，拖尾越重。
帧扫描
与电视工作原理类 似，CRT电子束从上 到下、从左到右扫描 进行，每扫描一遍称 为一帧。
1-03基本图形生成算法
3基本图形生成算法由于绘图机传动机构的限制，绘图时绘图笔只能作四个基本方向及组合的运动（共8个方向）。
每送一个信号就会驱使绘图笔沿8个方向之一移动一个步距，经过多次移动（形成阶梯状折线），即可给出人们需要的由折线逼近的复杂图形。
在显示器中绘制图形时，由于图形显示器像元的点阵分布，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近于该图形的一组像素。
绘图机的移动步距及显示器的像素决定着绘图的精度。
3.1直线的生成3.1.1数值微分法直线的斜率：x y k ∆∆=/。
其中，),(),(,,11000101y x y x y y y x x x 和-=∆-=∆分别是直线的端点坐标。
然后，从直线的起点开始，确定最佳逼近于直线的y 坐标。
假定端点坐标均为整数，让x 从起点到终点变化，每步递增1，计算对应的y 坐标，y=kx+B ，并取像素（x ，round(y)）。
用这种方法既直观，又可行，然而效率较低。
这因为每步运算都需要一个浮点乘法与一个舍入运算。
注意到 xk y xk B kx Bx x k Bkx y i i i i i ∆+=∆++=+∆+=+=++)(11因此，当1=∆x 时，又k y y i i +=+1，既当x 每递增1时，y 递增k （即直线斜率）。
一开始，直线起点（x 0,y 0注意上述分析和算法仅适用于|k|<=1的情形。
在这种情况下，x 每增加1，y 最多增加1，故在迭代过程的每一步，只要确定一个像素。
而当直线斜率k 的绝对值超过1时，必须把x,y 的地位交换，y 每增加1，x 相应增加1/k 。
数值微分法的本质，是用数值方法解微分方程，通过同时对x,y 各增加一个小增量，计算下一步的x,y 值。
在一个迭代算法中，如果每一步的x,y 值是用前一步的值加上个增量来获得的，那么，这种算法就成为增量算法。
在这个算法中，y 和k 必须用浮点数表示，而且每一步运算都必须对y 进行舍入取整。
计算机地图制图原理与方法基本图形生成算法PPT课件
void MidpointLine (int x0，int y0，int x1， int y1，int color) { int a， b， d1， d2， d， x， y；
a=y0-y1； b=x1-x0；d=2*a+b； d1=2*a；d2=2* (a+b)； x=x0；y=y0； while (x<=x1) { SetPixel (x， y， color); if (d<0) {x++；y++； d+=d2; } else {x++； d+=d1;} } /* while */ } /* midPointLine */
第13页/共34页
程序改进
void Bresenhamline (int x0,int y0,int x1, int y1,int color)
{ dx = x1-x0,；dy = y1- y0,；e=-dx;
x=x0； y=y0; for (i=0; i<=dx; i++)
从速度考虑，还 有那些可以改进？
第9页/共34页
3.2.3 生成直线的Bresenham算法
Yi+1 Yi
D
B A
C
xi
Xi+1
第10页/共34页
原理：
d
d
dd
假定直线斜率,0<k<1, 起点坐标为(x,y);
下一个点亮象素可能是：(x+1,y) 或 (x+1,y+1)。这可通过d值的大小来确定:
d = d+k, 当d>1 时 d=d-1 ;
d = F(xp + 2, yp - 0.5)
a=y0-y1； b=x1-x0；d=2*a+b； d1=2*a；d2=2* (a+b)； x=x0；y=y0； while (x<=x1) { SetPixel (x， y， color); if (d<0) {x++；y++； d+=d2; } else {x++； d+=d1;} } /* while */ } /* midPointLine */
第13页/共34页
程序改进
void Bresenhamline (int x0,int y0,int x1, int y1,int color)
{ dx = x1-x0,；dy = y1- y0,；e=-dx;
x=x0； y=y0; for (i=0; i<=dx; i++)
从速度考虑，还 有那些可以改进？
第9页/共34页
3.2.3 生成直线的Bresenham算法
Yi+1 Yi
D
B A
C
xi
Xi+1
第10页/共34页
原理：
d
d
dd
假定直线斜率,0<k<1, 起点坐标为(x,y);
下一个点亮象素可能是：(x+1,y) 或 (x+1,y+1)。这可通过d值的大小来确定:
d = d+k, 当d>1 时 d=d-1 ;
d = F(xp + 2, yp - 0.5)
ch3基本图形的生成与计算
Bresenham画线算法改进
上述bresenham算法在计算直线斜率与误差 项时用到小数与除法。可以改用整数以避免 除法。由于算法中只用到误差项的符号，因 此可作如下替换：
改进的Bresenham画线算法程序：
void InterBresenhamline (int x0,int y0,int x1, int y1,int color) { dx = x1-x0, dy = y1- y0, e=-dx; x=x0, y=y0; for (i=0; idx; -e+) { drawpixel (x, y, color); x++；e=e+2*dy;
P2 Q
P=(xp,yp) P1
中点画线法
画线从(x0, y0)开始，d的初值 d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b
由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。
设偏差计算公式为：
Fk
= tg - tg=
Yk X A - YA X k X A Xk
A
K2 K1
O
’
偏差计算
可以简化为
Fk Yk X A - YA X k
根据 Fk 计算出偏差，然后确定下一步的走向。
初始： X 0 0; Y0 0; 则 F0 =0；
第一步： X 1 X 0 1 1; Y1 0;
在直线生成的算法中Bresenham算法是最有 效的算法之一。令 k=Δy/Δx，就 0≤k≤1的情况来说明Bresenham算法。 由DDA算法可知： yi+1=yi+k (1) 由于k不一定是整数，由此式求出的yi也 不一定是整数，因此要用坐标为（xi,yir） 的象素来表示直线上的点，其中yir表示 最靠近yi的整数。
电脑图形教程基本图形生成算法
P2
e’
e P P1
y方向不走步
P2
e
e’
P
P1
Bresenham画线算法（6/7）
下一步误差的计算
当e≥0时，y方向走一步
e’=2y/ x - 1 =e + y/ x - 1 e’=e + 2y - 2x
当e<0时，y方向不走步
e’=2y/ x=e + y/ x e’=e + 2y
P2
光栅图形中点的表示
Address(x,y) = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址 = k1 + k2y + x
对像素连续寻址时，如何减少计算量？
Address(x±1,y) = k1 + k2y + (x±1) = Address(x,y) ± 1 Address(x,y±1) = k1 + k2(y ±1) + x = Address(x,y) ± k2 Address(x±1,y±1) = k1 + k2(y ±1) + (x±1)
实区域填充 字符 图形反走样
光栅图形中点的表示
…
地址线性表 1D表示
(x,y)坐标
显示屏幕 2D表示
像素由其左下角坐标表示
光栅图形中点的表示
y ymax
ymin xmin
x xmax
地址 = (xmax-xmin) * (y-ymin) + (x-xmin) + 基地址
每行像素点数
行数
行中位置
P2
M (Xp+1,Yp+0.5)
P
计算机图形学ppt课件 第二章基本图形的生成与计算
for (x=x0; xx1, x++) drawpixel (x, int(y+0.5), color); y=y+k;
例：画直线段P0(0,0)--P1(5,2)
int(y+0.5) 0 0 1 1 2 2 y+0.5 0+0.5 0.4+0.5 0.8+0.5 1.2+0.5 1.6+0.5 2.0+0.5
角度DDA法
显然，确定x,y的初值及d值后，即可以增量方 式获得圆周上的坐标，然后取整可得象素坐标。 但要采用浮点运算、乘法运算、取整运算。
中点画圆法
利用圆的对称性，只须讨论1/8圆。第二个8分 圆 P（Xp ，Yp ）
P1
M P2
P为当前点亮象素，那么，下一个点亮的象素可 能是P1（Xp+1，Yp）或P2（Xp +1，Yp +1)。
pi 2 xi dy 2 yi dx 2dy (2b 1)dx
（2.4）
在1a象限内，dx总大于0，所以pi可以判断d1d2的符号。Pi+1为
pi 1 2 xi 1dy (2 yi 1 2 yi 2 yi )dx 2dy (2b 1)dx
2( xi 1)dy (2 yi 1 2 yi 2 yi )dx 2dy (2b 1)dx
本算法是Bresenham在1965年提出。
设直线起点（x1，y1）终点（x2，y2），直 线可表示为 y mx b
y2 y1 dy b y1 m x1 , m x2 x1 dx
此处讨论先将直线方向限于1a象限，当
xi 1 xi 1
第2章基本图形生成算法
)
if (Flag) { //X方向单位增量
for (n=0; n<= Length; n++) {//X方向插补过程
WritePixel(ix, Round(y), value); ix+=idx; y+=dy; } //End of for } //End of if else { //Y方向斜率增量
第 2 章 基本图形生成算法(Ⅰ)
1) Bresenham的基本原理
假定直线斜率 k在 0~1之间 。 此时 ， 只需考
虑 x方向每次递增 1个单位 ， 决定 y方向每次 递增 0或 1。
设直线的
当前点为 (xi,y) 当前光栅点为 (xi,yi)
下一个
直线的点应为 (xi+1,y+k) 直线的光栅点
y
y 2
y1
k
x x2 x1
第 2 章 基本图形生成算法(Ⅰ)
1)David F. Rogers 描述描述
如果已知第 i点的坐标 ， 可用步长 StepX 和 StepY得到
第 i+1点的坐标为 ： – xi+1=xi+ StepX – yi+1=yi+ StepY 或 yi+1=yi+ k * StepX
Bresenham算法
– 基本原理 – Bresenham算法 – 整数 Bresenham算法 – 一般整数 Bresenham算法
第 2 章 基本图形生成算法(Ⅰ)
2.1.1 DDA算法算法
1)David F. Rogers 描述描述
直线的基本微分方程是 ：
dy dx ＝ 常数 (k)
设直线通过点 P1(x1,y1)和P2(x2,y2) , 则直线方程可表示为 ：
if (Flag) { //X方向单位增量
for (n=0; n<= Length; n++) {//X方向插补过程
WritePixel(ix, Round(y), value); ix+=idx; y+=dy; } //End of for } //End of if else { //Y方向斜率增量
第 2 章 基本图形生成算法(Ⅰ)
1) Bresenham的基本原理
假定直线斜率 k在 0~1之间 。 此时 ， 只需考
虑 x方向每次递增 1个单位 ， 决定 y方向每次 递增 0或 1。
设直线的
当前点为 (xi,y) 当前光栅点为 (xi,yi)
下一个
直线的点应为 (xi+1,y+k) 直线的光栅点
y
y 2
y1
k
x x2 x1
第 2 章 基本图形生成算法(Ⅰ)
1)David F. Rogers 描述描述
如果已知第 i点的坐标 ， 可用步长 StepX 和 StepY得到
第 i+1点的坐标为 ： – xi+1=xi+ StepX – yi+1=yi+ StepY 或 yi+1=yi+ k * StepX
Bresenham算法
– 基本原理 – Bresenham算法 – 整数 Bresenham算法 – 一般整数 Bresenham算法
第 2 章 基本图形生成算法(Ⅰ)
2.1.1 DDA算法算法
1)David F. Rogers 描述描述
直线的基本微分方程是 ：
dy dx ＝ 常数 (k)
设直线通过点 P1(x1,y1)和P2(x2,y2) , 则直线方程可表示为 ：
第2章 基本图形的生成与技术(2.6)
2.6图形的剪裁内容提要(1)计算机是如何将几何图形显示到屏幕上的？(2)了解各种坐标系的定义及其作用；(3)熟悉二维观察流程；(4)掌握2维坐标变换的基本方法；(5)掌握常用的二维裁剪算法，并会编程实现。
在计算机图形显示的过程中,往往需要确定图形的哪些部分(包括点、线段、文字、多边形等)落在显示区域(即:视口或视区)之内，哪些部分落在显示区域之外，以便只显示位于显示区域内的那部分图形。
裁剪的实质就是决定图形中哪些部分位于指定的区域内。
这需要进行几何处理,以便去除落在指定区域之外的部分,保留位于指定区域以内的部分。
这个过程称为裁剪。
最直观的裁剪方法是把各种几何图素通过扫描转换等技术离散成为点的集合，再逐点判断其是否位于指定的区域内。
那样虽然简单，但是效率太低，一般不可取。
1、线段的裁剪对于一条给定的线段，其裁剪过程一般包括以下几个部分：首先测试和判断它是否完全落在裁剪区之内？如果不是，再判断它是否完全落在裁剪区之外？然后,对于既不能确定完全落在裁剪区之内又不能确定完全落在裁剪区之外的线段,要计算它与一个或多个裁剪边界的交点。
最后，对线段的端点进行测试，对于两个端点都落在裁剪区域内的线段就存储起来，否则就予以去除，即裁剪之。
一、C o h e n-S u t h e r l a n d裁剪算法这个算法的特点是：通过初始测试来快速判断线段与视区的关系，以便减少线段求交的次数，从而提高裁剪算法的速度。
C o h e n-S u t h e r L a n d裁剪算法的基本思想：对每条线段P1P2：1）判断端点在裁剪区域内、外：P1P2完全在视区内，保存之；P1P2完全在视区外，舍弃之；2）上述两条件均不满足，则计算图形与裁剪边界的交点，将该线段分为分别位于裁剪区域内、外的两段，再重复1）。
在分段时，依据端点的区域码分别计算线段与各条裁剪边界的交点，如图3.10所示，对P1就需要分别计算交点P3和P4；即只要按顺序检测端点区域码的每一位，当某位不为0时，才把线段与对应的裁剪边界进行求交。
计算机基本图形生成算法
给定圆心在原点，半径为整数R的圆，其方程为
x2 y2 R2
构造函数F(x,y)=x2+y2-R2。 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)>0； 而对于圆内的点，F(x,y)<0。
31
y
Pu
PM
Pd
x
图5.13 中点Bresenham画圆的原理
中点Bresenham画圆
y
yi
k
19
改进的Bresenham算法
kd
k d
kd
k kd
图5.10 改进的Brensemham算法绘制直线的原理
改进的Bresenham算法——原理
xi1 yi1
xi
yi yi
1
1
(d 0.5) (d 0.5)
误差项的计算
d初=0， 每走一步：d=d+k
一旦y方向上走了一步，d=d-1
中点Bresenham画圆
判别式的初始值
d0 F ( x0 1, y0 0.5) F (1, R 0.5) 1 (R 0.5)2 R2 1.25 R
36
改进：用d-0.25代替d 此时有：
d d 2xi 3
d 0.25
d d 2(xi yi ) 5 d 0.25
yi-2
(xi 2)2 ( yi 0.5)2 R2
xi xi+1 xi+2
d2 ( xi 1 1)2 ( yi 0.5)2 R2 图5.14 d≤0的情况
( xi 1)2 2xi 3 ( yi 0.5)2 R2
d1 2xi 3
误差项的递推（d>0）
yi
P
yi-1
构造判别式：
x2 y2 R2
构造函数F(x,y)=x2+y2-R2。 对于圆上的点，有F(x,y)=0； 对于圆外的点，F(x,y)>0； 而对于圆内的点，F(x,y)<0。
31
y
Pu
PM
Pd
x
图5.13 中点Bresenham画圆的原理
中点Bresenham画圆
y
yi
k
19
改进的Bresenham算法
kd
k d
kd
k kd
图5.10 改进的Brensemham算法绘制直线的原理
改进的Bresenham算法——原理
xi1 yi1
xi
yi yi
1
1
(d 0.5) (d 0.5)
误差项的计算
d初=0， 每走一步：d=d+k
一旦y方向上走了一步，d=d-1
中点Bresenham画圆
判别式的初始值
d0 F ( x0 1, y0 0.5) F (1, R 0.5) 1 (R 0.5)2 R2 1.25 R
36
改进：用d-0.25代替d 此时有：
d d 2xi 3
d 0.25
d d 2(xi yi ) 5 d 0.25
yi-2
(xi 2)2 ( yi 0.5)2 R2
xi xi+1 xi+2
d2 ( xi 1 1)2 ( yi 0.5)2 R2 图5.14 d≤0的情况
( xi 1)2 2xi 3 ( yi 0.5)2 R2
d1 2xi 3
误差项的递推（d>0）
yi
P
yi-1
构造判别式：
第二章二维基本图形的生成与二维区域的填充课件
2019y/12i+/41)作为下一个象素点。
23
2.1.2 生成直线的Bresenham算法
• 因此只要利用(d1-d2)的符号就可以决定下 一个象素点的选择。为此，我们进一步定义一 个新的判别式：
• pi=△x×(d1-d2)=2△y·xi-2△x·yi+c (2－11) 式(2-11)中的△x=(x2-x1)>0，因此pi与(d1-
三、直线Bresenham算法思想之二
•
由于象素坐标的整数性，数学点(xi，yi)与所
取象素点(xi，yir)间会引起误差(εi)，当xi列上已用
象素坐标(xi，yir)表示直线上的点(xi，yi)，下一直
线点B(xi+1，yi+1)，是取象素点C(xi+1，yir )，还是
2019D/12(/4xi＋1，y(i+1)r)呢？
(2－12)
将式(2-12)减去(2-11)，并利用xi+1=xi+1，
可得：
• pi+1= pi+2△y-2△x·(yi+1-yi) (2－13)
• 再假设直线的初始端点恰好是其象素点的 坐标，即满足：
• y1=mx1+b
(2－14)
2019/12/4
25
2.1.2 生成直线的Bresenham算法
我们知道，一幅图是由点、直线、曲线、多 边形填充区域以及字符串等组成。下面将讨论这 些基本图元的生成技术和算法。
2019/12/4
4
2.1 直线的扫描转换
一、数学直线 在数学上，理想的直线是一条由无穷多个无
限小的连续的点组成。
数学直线
2019/12/4
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
当d<0，M在直线下方，取右上方P2 当d>0，M在直线上方，取正右方P1 当d=0，选P1或P2均可，约定取P1
提出问题：判别式d是否有增量。
中点画线法
(1) 若d0, 取正右方像素点P1(xp+1,yp) 此时再下一个象素的判别式为:
d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c+a =d+a
算法特点： • 使用最广泛 • 与中点画线法的思想类似 • 由误差项符号决定下一个象素取正右方
像素还是右上方像素
Bresenham画线算法
基本原理： (k在0~1之间的情况，且保证起点坐标小于终点坐标 ) 给定直线的起点(x1, y1)，终点(x2, y2)。 设当前已确定像素点Pk (xk, yk) ，沿扫描方向，x每次 增加一个单元格，即下一个像素点Pk+1 横坐标为xk+1, 而终坐标y或保持yk不变，或为yk+1 。
k=(2-0)/(5-0)=0.4
x
y
int(y+0.5)
Line: P0(0, 0)-- P1(5, 2)
0
0
0
3
1
0.4
0
22Leabharlann 0.813
1.2
1
1
4
1.6
2
5
2.0
2
0 12 3 4 5
中点画线法
• 基本原理
只考虑斜率k(0<k<1)且保证起点坐标小于终点坐标
设当前像素点为P(Xp,Yp ), 则下一个与直线最接近的像 素只能是P1点或P2点。设M 为中点，Q为交点。 提出问题：如何确定下一个 象素点。
数值微分(DDA)法
基本原理：
已知直线段的起点、终点分别为：P0 (x0,y0), P1(x1,y1)，且坐标值都为整数。 直线的微分方程为：
dy y y1 y0 k dx x x1 x0
设|k|≤1, 则有
yi+1=kxi+1+b=k(xi+Δx)+b=yi+kΔx 若Δx=1, 则当x每递增1时, y递增k 。
其中a=y0-y1, b=x1-x0, c=x0y1-x1y0
Fx, y 0 Fx, y 0 Fx, y 0
点在直线上面 点在直线上方 点在直线下方
欲判断M点与Q点关系，只需把 M(xp+1,yp+0.5)代入F(x,y),并检查它的符号。
中点画线法
构造判别式： d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c
2.1.1 直线的扫描转换算法
三个常用算法 – 数值微分(DDA)法 – 中点画线法 – Bresenham画线法
数值微分(DDA)法
DDA算法： 根据直线的微分方程来计算Δx或Δy生成 直线的扫描转换算法。
过程描述： 在水平坐标轴上以单位间隔对线段取样, 以 决定垂直坐标轴方向上最靠近理想线段的 整数值。
增量为a
P2
Q
P=(xp,yp) P1
中点画线法
(2) 若d<0, 取右上方像素点P2(xp+1,yp+1) 此时再下一个象素的判别式为:
d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b
增量为a＋b
中点画线法
例：用中点画线法P0(0, 0)，P1(5, 2)
a=y0-y1= -2 b=x1-x0=5
d0=2a+b=1 d1=2a= -4 d2=2(a+b)=6
i xi yi d
10 0 1 3
2 1 0 -3 2
32 1 3
1
4 3 1 -1
54 2 5
0 12 3 4 5
65 2
Bresenham画线算法
第2章 基本图形生成算法
2.1 图形的扫描转换 – 直线的扫描转换 – 圆弧的扫描转换 – 椭圆弧的扫描转换
2.2 区域填充 2.3 图形裁剪
2.1.1 直线的扫描转换算法
基本原理 （1）确定最佳逼近于该直线的一组象素 （2）按扫描线顺序，对这些象素进行写操作
图5-1 用一系列的象素点来逼近直线
优点：
– 只有整数运算，不含乘除法 – 可用硬件实现
中点画线法
void MidpointLine (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y;
a=y0-y1; b=x1-x0; d=2*a+b; d1=2*a ; d2=2* (a+b); x=x0; y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++; y++; d+=d2; } else {x++; d+=d1;} drawpixel (x, y, color); } } /* 中点画线法程序 */
中点画线法
➢M在Q的下方-> P2离直线更近更近->取P2 ➢M在Q的上方-> P1离直线更近更近->取P1 ➢M与Q重合-> P1、P2任取一点->约定取P1
P2 Q
P=(xp,yp) P1
提出问题：如何判断M点与Q点的位置关系？
中点画线法
已知直线段的起点P0 (x0,y0), 终点P1(x1,y1)。 直线方程为：F(x,y)=ax+by+c=0
P2
Q
P=(xp,yp) P1
中点画线法
画线从直线起点P0(x0, y0)开始，d的初值如下： d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b
由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。
y=y+k ; // DDA算法描述
数值微分(DDA)法
算法特点： • DDA算法就是一个增量算法
增量算法：在一个迭代算法中，如果每 一步的x、y值是用前一步的值加上一个 增量来获得，则称为增量算法。 • 直观，易实现 • 不利于用硬件实现
数值微分(DDA)法
例：画直线段P0(0,0)--P1(5,2)
数值微分(DDA)法
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+0.5), color) ;
提出问题：判别式d是否有增量。
中点画线法
(1) 若d0, 取正右方像素点P1(xp+1,yp) 此时再下一个象素的判别式为:
d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c+a =d+a
算法特点： • 使用最广泛 • 与中点画线法的思想类似 • 由误差项符号决定下一个象素取正右方
像素还是右上方像素
Bresenham画线算法
基本原理： (k在0~1之间的情况，且保证起点坐标小于终点坐标 ) 给定直线的起点(x1, y1)，终点(x2, y2)。 设当前已确定像素点Pk (xk, yk) ，沿扫描方向，x每次 增加一个单元格，即下一个像素点Pk+1 横坐标为xk+1, 而终坐标y或保持yk不变，或为yk+1 。
k=(2-0)/(5-0)=0.4
x
y
int(y+0.5)
Line: P0(0, 0)-- P1(5, 2)
0
0
0
3
1
0.4
0
22Leabharlann 0.813
1.2
1
1
4
1.6
2
5
2.0
2
0 12 3 4 5
中点画线法
• 基本原理
只考虑斜率k(0<k<1)且保证起点坐标小于终点坐标
设当前像素点为P(Xp,Yp ), 则下一个与直线最接近的像 素只能是P1点或P2点。设M 为中点，Q为交点。 提出问题：如何确定下一个 象素点。
数值微分(DDA)法
基本原理：
已知直线段的起点、终点分别为：P0 (x0,y0), P1(x1,y1)，且坐标值都为整数。 直线的微分方程为：
dy y y1 y0 k dx x x1 x0
设|k|≤1, 则有
yi+1=kxi+1+b=k(xi+Δx)+b=yi+kΔx 若Δx=1, 则当x每递增1时, y递增k 。
其中a=y0-y1, b=x1-x0, c=x0y1-x1y0
Fx, y 0 Fx, y 0 Fx, y 0
点在直线上面 点在直线上方 点在直线下方
欲判断M点与Q点关系，只需把 M(xp+1,yp+0.5)代入F(x,y),并检查它的符号。
中点画线法
构造判别式： d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c
2.1.1 直线的扫描转换算法
三个常用算法 – 数值微分(DDA)法 – 中点画线法 – Bresenham画线法
数值微分(DDA)法
DDA算法： 根据直线的微分方程来计算Δx或Δy生成 直线的扫描转换算法。
过程描述： 在水平坐标轴上以单位间隔对线段取样, 以 决定垂直坐标轴方向上最靠近理想线段的 整数值。
增量为a
P2
Q
P=(xp,yp) P1
中点画线法
(2) 若d<0, 取右上方像素点P2(xp+1,yp+1) 此时再下一个象素的判别式为:
d2= F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5)+c = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b
增量为a＋b
中点画线法
例：用中点画线法P0(0, 0)，P1(5, 2)
a=y0-y1= -2 b=x1-x0=5
d0=2a+b=1 d1=2a= -4 d2=2(a+b)=6
i xi yi d
10 0 1 3
2 1 0 -3 2
32 1 3
1
4 3 1 -1
54 2 5
0 12 3 4 5
65 2
Bresenham画线算法
第2章 基本图形生成算法
2.1 图形的扫描转换 – 直线的扫描转换 – 圆弧的扫描转换 – 椭圆弧的扫描转换
2.2 区域填充 2.3 图形裁剪
2.1.1 直线的扫描转换算法
基本原理 （1）确定最佳逼近于该直线的一组象素 （2）按扫描线顺序，对这些象素进行写操作
图5-1 用一系列的象素点来逼近直线
优点：
– 只有整数运算，不含乘除法 – 可用硬件实现
中点画线法
void MidpointLine (int x0,int y0,int x1, int y1,int color) { int a, b, d1, d2, d, x, y;
a=y0-y1; b=x1-x0; d=2*a+b; d1=2*a ; d2=2* (a+b); x=x0; y=y0; drawpixel(x, y, color); while (x<x1) { if (d<0) {x++; y++; d+=d2; } else {x++; d+=d1;} drawpixel (x, y, color); } } /* 中点画线法程序 */
中点画线法
➢M在Q的下方-> P2离直线更近更近->取P2 ➢M在Q的上方-> P1离直线更近更近->取P1 ➢M与Q重合-> P1、P2任取一点->约定取P1
P2 Q
P=(xp,yp) P1
提出问题：如何判断M点与Q点的位置关系？
中点画线法
已知直线段的起点P0 (x0,y0), 终点P1(x1,y1)。 直线方程为：F(x,y)=ax+by+c=0
P2
Q
P=(xp,yp) P1
中点画线法
画线从直线起点P0(x0, y0)开始，d的初值如下： d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c = F(x0, y0)+a+0.5b = a+0.5b
由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。
y=y+k ; // DDA算法描述
数值微分(DDA)法
算法特点： • DDA算法就是一个增量算法
增量算法：在一个迭代算法中，如果每 一步的x、y值是用前一步的值加上一个 增量来获得，则称为增量算法。 • 直观，易实现 • 不利于用硬件实现
数值微分(DDA)法
例：画直线段P0(0,0)--P1(5,2)
数值微分(DDA)法
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+0.5), color) ;