基本图形生成算法

2015/12/22
22
பைடு நூலகம் 3.2.2 中点画线算法
d=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+c
若d<0->M在直线下方->取P2; 此时再下一个象素的判别式为 d2= F(x+2, y+1.5) =a(x+2)+b(y+1.5)+c = a(x+1)+b(y+0.5)+c +a +b =d+a+b ； 增量为a＋b
P0(0, 0)-- P1(5, 2)
2
3
4
5
2015/12/22
15
3.2.1 数值微分法(DDA法)
通常情况下，直线的 方向分为8个不同的区域， 每个区域的处理方法有所不 同。K=△y/△x
区域 1a(1) 1b(2) 2a(4) 2b(3) 3a(5) 3b(6) 4a(8) 4b(7) dx 1 1/k -1 -1/k -1 -1/k 1 1/k dy k 1 k 1 -k -1 -k -1
2015/12/22
23
3.2.2 中点画线算法
画线从(x0, y0)开始，d的初值（F(x,y)=a*x+b*y+c）
d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0+0.5)+c
= ax0 +a+by0+0.5b+c = ax0+by0+c+a+0.5b =F(x0, y0)+a+0.5b = a+0.5b 注：由于（ x0, y0）在直线上，故F(x0, y0)=0 所以，d的初始值d0 = a+0.5b
在数学上，理想的直线是没有宽度的、由 无数个点构成的集合。当我们对直线进行光栅 化时，只能在显示器所给定的有限个像素组成 的矩阵中，确定最佳逼近该直线的一组像素， 并且按扫描线顺序对这些像素进行写操作，这 就是通常所说的直线的扫描转换。 通常用于直线光栅化的算法有数值微分法（ DDA）、中点画线法和Bresenham画线算法。
2015/12/22
24
3.2.2 中点画线算法
d的初始值d0 = a+0.5b 由于只用d 的符号作判断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。用2d代替d 后，d0=2a+b d的增量都是整数(d1:2a, d2:2(a+b)) 如果进一步把算法中2*a改为a+a等等，那么这 个算法不仅只包含整数变量，而且不包含乘除法， 适合硬件实现。 演示说明
2015/12/22
6
直线光栅化算法
直线段生成 求与直线段充分接近的像素集
2015/12/22
7
3.2 直线的扫描转换
直线的绘制要求
（1）直线要直；
（2）直线的端点要准确，无定向性无断裂；
（3）直线的亮度、色泽要均匀；
（4）画线的速度要快；
（5）具有不同的色泽、亮度、线型等。
2015/12/22
8
3.2 直线的扫描转换
解 决 的 问 题 ： 给 定 直 线 两 端 点 P0(x0,y0) 和
P1(x1,y1)，画出该直线。
数值微分法(DDA算法)
中点画线算法
Bresenhan算法
2015/12/22
9
3.2.1 数值微分法(DDA法)
DDA（Digital Differential Analyzer）画线算法也 称数值微分法，是一种增量算法。它的算法实质是用数值方法 解微分方程，通过同时对x和y各增加一个小增量，计算下一 步的x、y值。 已知一条直线段L（P0, P1）,其端点坐标为：P0 (x0, y0), P1(x1, y1)。可计算出直线的斜率k为：
11
2015/12/22
3.2.1 数值微分法(DDA法)
增量算法 因为: y=kx+b,所以: yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k =yi+k
(xi,yi)→(xi+1,yi+k)
例图中 k<1 △X=1 △Y=k
将算得的直线上每个点的当前坐标，按四舍五入得到光栅点的位置 浮点数取整 : yi=round(yi)=(int)(yi+0.5)
2015/12/22 21
3.2.2 中点画线算法
d=F(M)=F(x+1, y+0.5)=a(x+1)+b(y+0.5)+c
若d0 ->M在直线上方->取P1; 此时再下一个像素的判别式为 d1=F(x+2, y+0.5)(F(x,y)=ax+by+c=0 ) =a(x+2)+b(y+0.5)+c = a(x +1)+b(y +0.5)+c +a =d+a； 增量为a
F x, y 0 F x, y 0 F x, y 0
y F(x,y)=0 F(x,y)>0 F(x,y)<0 x F(x,y)<0 F(x,y)=0 F(x,y)>0 x
（1）
点在直线上面 点在直线上方 点在直线下方
y
2015/12/22
图 直线将平面分为三个区域
2015/12/22
16
3.2.1 数值微分法(DDA法)
2015/12/22
17
数值微分法(DDA法)——特点
增量算法
直观、易实现 不利于用硬件实现
2015/12/22
18
3.2.2 中点画线算法
中点画线算法的基本思想
为了讨论方便，假设直线的斜率在0到1 之间，若直线在x方向上增加一个光栅单位，则 在y方向上的增量只能在0到1之间。设P（xp,yp ）是直线上的一点，与P点最近的网格点为（ xi, yi）,那么，下一个与直线最近的像素只能 是正右方的网格点P1（xi+1, yi）或右上方的网 格点P2（xi+1,yi+1）两者之一。再以点M（ xi+1, yi+0.5）表示P1和P2的中点，设Q是直线 与垂直线x= xi+1的交点。显然，若M在Q的下方 ，则P2离直线较近，应取P2为下一个像素点，否 则应取P1做为下一个像素点，这就是中点画线 算法的基本思想。
问题：如何判断 M与Q点的关系？

19
2015/12/22
3.2.2 中点画线算法
假设直线的起点、终点分别为：（X0,Y0),(X1,Y1) 则直线方程可表示为： F(x,y)=a*x+b*y+c 其中： a=Y0-Y1, b=X1-X0, c=X0*Y1-X1*Y0 空间某点（x,y）与直线的关系： 当：
2015/12/22 25
例:按照中点画线算法，确定直线（0，0）（5，2）
的点亮像素。列出计算过程，并列出所选像素坐标。
解: K=dy/dx=2/5=0.4<1,故x方向增1,y方向根据d的符号判断. a=y0-y1=-2; b=x1-x0=5; d0=2a+b=1; d1=2a=-4; d2=2(a+b)=6; x y d 0 0 1 1 0 -3 2 1 3 3 1 -1 4 2 5 5 2 1
yi+1=yi+k
当 k 1时，必须把x，y地位互换
2015/12/22 14
程序实现：
void DDALine(int x0,int y0,int x1,int y1,int color) { Line: int x; 3 float dx,dy,k,y; dx=x1-x0; dy=y1-y0; 2 k=dy/dx; 1 y=y0; for(x=x0;x<=x1;) 0 1 { drawpixel(x,int(y+0.5),Color); x++; y=y+k; } }
在d≥0的情况下，取正右方像素P1， 判断再下一像素应计算 d1=a(x+2)+b(y+0.5)+c =d+a ,故d的增量为a. 在d<0的情况下，取右上方像素P2， 判断再下一像素应计算 d2=a(x+2)+b(y+1.5) = d+a+b,故d的增量为a+b. 2015/12/22 d的初始值d0 = a+0.5b
y1 y0 k x1 x0
2015/12/22 10
3.2.1 数值微分法(DDA法)
假定端点坐标均为整数，取 直线起点P0 (x0, y0)作为初 始坐标。画线过程从x的左端 点x0开始，向x右端点步进， 每步x递增1，计算相应的y 坐标， y=kx+b，取像素点 （x，round（y））作为当 前点的坐标。 问题:每步需要用到浮点数的 乘法、加法和取整运算，效 率不高。怎么办??
2015/12/22 3
3.1 图形生成的概念
图形的生成：是在指定的
输出设备上，根据坐标描
述构造二维几何图形。
图形的扫描转换：在光栅
显示器等数字设备上确定
一个最佳逼近于图形的像 素集的过程。
2015/12/22
用像素点集逼近直线
4
3.1 图形生成的概念
2015/12/22
5
3.2 直线的扫描转换
2015/12/22 27
3.2.3 Bresenham画线算法 这是计算机科学教授Jack