2.1 直线的生成算法

^{在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。本节介绍在光栅显示器上直线光栅化的最常用的两种算法：直线DDA算法和直线Bresenham算法。}电脑爱好者网G3]y-sc#E(D:lyEO

2.1.1 直线的DDA算法

^{DDA是数字微分分析式（Digital Differential Analyzer）的缩写。设直线之起点为（x1，y1），终点为（x2，y2），则斜率m为：}电脑爱好者网tw-C2g4}5_ hL~:?

m =

^{直线中的每一点坐标都可以由前一点坐标变化一个增量（Dx, Dy）而得到，即表示为递归式：}

^xi+1=xi+Dx

^yi+1=yi+Dy电脑爱好者网PX3W2e'K`8w

^{并有关系：Dy = m · Dx}电脑爱好者网|8q0`$_Rc7q

^{递归式的初值为直线的起点（x1, y1），这样，就可以用加法来生成一条直线。具体方法是：}

^{图2.1.1 直线方向的8个象限}电脑爱好者网t1U&Xf~#H

                                             电脑爱好者网YG6b,\:P8lJS

                                                          图2.1.1电脑爱好者网A4S0S4u)mwc+{

0S$]1K2\y|{0表2.1.1

^{按照直线从（x1，y1）到（x2，y2）的方向不同，分为8个象限（图2.1.1）。对于方向在第1a象限内的直线而言，D x=1，D y=m。对于方向在第1b象限内的直线而言，取值Dy=1，Dx=1/m。各象限中直线生成时Dx, Dy的取值列在表2.1.1之中。}电脑爱好者网Aiv:c7]

^{研究表中的数据，可以发现两个规律：}电脑爱好者网OLz^3G

^{1、当|dx|>|dy|时}电脑爱好者网n9lZB h{` j5~"}

^{|D x|=1, |D y|=m；}

^否则：

^{Dx=1/m，|Dy|=1}电脑爱好者网Ko#X/x1U0?

^{2、Dx, Dy的符号与dx, dy的符号相同。}电脑爱好者网id'RS,nK.[

^{这两条规律可以导致程序的简化。由上述方法写成的程序如程序2.1.1所示。其中steps变量的设置，以及D x=dx/steps; D y=dy/steps等语句，正是利用了上述两条规律，使得程序变得简练。}

^{使用DDA算法，每生成一条直线做两次除法，每画线中一点做两次加法。因此，用DDA法生成直线的速度是相当快的。}

dda_line (xa, ya, xb, yb, c)

dnM$^+]1UT0

int xa, ya, xb, yb, c;电脑爱好者网-\0Kd(O!I5Nq

{

(a@%g5S%H7@ F D)j`0

float delta_x, delta_y, x, y;电脑爱好者网Tz:_'P8Ry0d-h

int dx, dy, steps, k;电脑爱好者网 P+hq+n V6m4OH'h

dx=xb-xa;电脑爱好者网*cP}3uA q"x7@6z

dy=yb-ya;

E4c,Bh!j0F
xn\2S0

if (abs(dx)>abs(dy)) steps=abs(dx);电脑爱好者网P{4j mL Sc

else steps=abs (dy);

X&J9fAc#C_6pV)d,~%@0

delta_x=(float)dx / (float)steps;电脑爱好者网 }Tw\/_VR}j

delta_y=(float)dy / (float)steps;

V
{r
^G5}E2{0

x=xa;

X5?"b NkV0

y=ya;电脑爱好者网C0NE+J"ny+Y,U g

set_pixel(x, y, c);电脑爱好者网bj0^FOm!r#^

for (k=1; k<=steps; k++)电脑爱好者网lG*s%I5h;e!v

{

.y/\\"D.W0SVcjF0

x+=delta_x;

`U^Q S0

y+=delta_y;电脑爱好者网]QD-ux$\7PI

set_pixel(x, y, c);

t"BhC.TCW8B0ap0

}电脑爱好者网$HK5z]3dnu}ru

   }电脑爱好者网F9ES"kb;K,n

程序2.1.1 DDA直线生成程序电脑爱好者网5cd3E^YS7{