DDA 线条绘制算法的实现

• 下载源代码 - 23.8 KB

引言

DDA_Final应用程序能够绘制用户在屏幕上指定的两个点之间的线条。用户可以通过右、左、上、下键在手机屏幕上移动光标，并通过按下FIRE键指定终点。当指定了起点和终点后，屏幕上就会绘制一条线。该程序已在Sun WTK 2.5.2_01模拟器和Nokia 5130XpressMusic手机上进行了测试。

在J2ME中实现该算法的原因是，读者可以一窥真实显示设备的工作原理。要完全理解该主题，需要对像素和光栅显示设备等计算机图形学基本图元有一定了解。由于代码是用J2ME编写的，了解一些J2ME知识会很有帮助。

背景

数字微分分析器（Digital Differential Analyzer），简称DDA直线绘制算法，用于在光栅图形设备中绘制直线。在此算法中，必须提供直线的起点和终点位置。

中间像素位置将通过对起点和终点之间区间上的变量进行线性插值来计算。算法如下：

设直线的起点和终点分别为(x1, y1)和(x2, y2)。那么斜率m = (y2-y1)/(x2-x1)。根据m的值以及(x, y)所属的象限，中间像素位置的计算如下：

位置的计算方法如下：

象限	m<=1	m>1
First	x=x+1 y=y + m	x=x+1/m y=y+1
第二种	x=x-1 y=y + m	x=x+1/m y=y+1
第三部分	x=x-1 y=y-m	x=x-1/m y=y-1
第四象限	x=x+1 y=y + m	x=x-1/m y=y-1
表-1

在此，x和y的值被近似到最接近的整数值，因为像素位置不能是浮点数。

这是算法的理论方法，其中一个点可以虚拟地处于四个象限中的任何一个。实际上这是不可能的，因为物理显示设备中的像素位置不能为负。在物理显示设备中，我们只有笛卡尔坐标系的第1象限，其中x和y都大于或等于零，并且可以取整数值。在为物理显示设备实现算法时，我们只需要为第一象限进行编程。

这里还需注意的一点是，物理显示设备的朝向与几何笛卡尔坐标系不同。

在第一象限的真实坐标系中，x值向右增加，y值向左上持续增加。在物理显示设备坐标系中，原点是左上角的像素。这意味着左上角像素的坐标值为(0, 0)。x坐标值会像素化地向右增加，y坐标值会像素化地向下增加。需要注意的是，右下角像素在显示设备中将具有最高的坐标值。

为了更清晰地可视化，屏幕坐标可以看作是几何第一象限的反射版本，其中反射是通过直线y=0进行的。

Using the Code

整个程序共使用了五个类：

Main.java
GUI.java
Cursor.java 
DDAEngine.java
DDA.java

Main.java 和 GUI.java 用于创建图形用户界面和命令操作。Cursor.java 定义了用于选择起点和终点的可导航光标。J2ME的Sprite类用于创建动画。

在DDAEngine.java中，创建了Cursor的实例。

private Cursor c;
. . . . . . . .
public DDAEngine(. . . .){
c=new Cursor(CURSOR_IMAGE,CURSOR_WIDTH,CURSOR_HEIGHT);
        c.setRefPixelPosition(height/2, width/2);
        this.append(c);
}

可以使用右、左、上、下键在视口中导航光标。

if ((keyState & gui.RIGHT_PRESSED) != 0){
    c.moveRight(width);
}

if ((keyState & gui.LEFT_PRESSED) != 0){
   c.moveLeft();
}

if ((keyState & gui.UP_PRESSED) != 0){
    c.moveUp();
}

if ((keyState & gui.DOWN_PRESSED) != 0){
   c.moveDown(height);
}

按下FIRE键时，光标将分别选择起点和终点。

/*s1 and s2 indicates wheather the points are selected or not. 
   These are Boolean variables.After selecting the first point 
   the s1 is set to true and on next FIRE press the control goes 
   to the 2nd if() statement.*/  

if ((keyState & gui.FIRE_PRESSED) != 0){
      if(!s1){
          x1=c.getRefPixelX();  //x co-ordinate of the start point
          y1=c.getRefPixelY();  //y co-ordinate of the start point
          s1=true;              // s1 is set to true as first point is chosen
          hit=false;
          . . . . . . . .. 
      }
     if( hit & !s2 ){
         x2=c.getRefPixelX();      //x co-ordinate of the end point
         y2=c.getRefPixelY();      //y co-ordinate of the end point
         s2=true;                   // s2 is set to true as end point is chosen
         
         . . . . . . . . . .
     }
        }
      if(s1){
          hit=true;
      }

当我们选择了两个点后，DDA算法将从DDAEngine.java类调用，该算法实现在DDA.java类中。

if(s1 & s2){
  dda=new DDA(x1,y1,x2,y2);
}

在DDA.java类中，我们有一个drawLine()方法，用于计算(x1, y1)和(x2, y2)之间的中间像素位置。在这里，我们首先计算起点和终点x和y坐标之间的差值。

void drawLine(. .. . ){
  dx=(double)(x2-x1);
  dy=(double)(y2-y1);
  . . . . . . . .. 
}

接下来，我们需要检查斜率<= 1还是斜率> 1。

void drawLine(. .. . ){
. . . . . . . .. 
len=Math.abs(dx);
 if(Math.abs(dy)>Math.abs(dx))len=Math.abs(dy);
. . . . . . . . . 
}

我们可以将算法模型化，使其适用于斜率为90度的直线。直线的斜率为90度意味着起点和终点的x坐标相等。这可以建模为：

void drawLine(. .. . ){
. . . . . . . .. 
if((x1==x2)&& dy<0)len=dy;
. . . . . . . . . 
}

接下来，选择栅格单位，即计算x增量和y增量。

void drawLine(. .. . ){
. . . . . . . .. 
xinc=dx/len;            //x-increment
yinc=dy/len;            //y-increment    
if((x1==x2)&& dy<0)yinc=Math.abs(dy)/len; //y-increment for line having slope = 90 degree
. . . . . . . . . 
}

这里需要注意的一点是，xinc或yinc将为一，因为len要么是(x2-x1)，要么是(y2-y1)。

因此，x或y的增量将为一。

接下来，通过执行一个循环来计算和绘制中间点。

void drawLine(. .. . ){
    . . . . . . . .. 
    fx=(double)x1;
    fy=(double)y1;
    double i=1;

    if(x1!=x2){
        while(i<=len){
            g.setColor(200,0,0);
            g.drawLine((int)Math.floor(fx),(int)Math.floor(fy),
                       (int)Math.floor(fx),(int)Math.floor(fy));
            fx=fx+xinc;
            fy=fy+yinc;
            i=i+1;
        }
    }
    else if(x1==x2){
        i=(double)y1;
        while(i!=(double)y2){
        g.setColor(200,0,0);
        g.drawLine((int)Math.floor(fx),(int)Math.floor(fy),
                    (int)Math.floor(fx),(int)Math.floor(fy));
        fx=fx+xinc;
        fy=fy+yinc;
        i=i+yinc;
       }
    }
    . . . . . . . . . 
}

整个项目是使用NetBeans IDE 6.9.1构建的。成功执行后，用户将在屏幕上看到一个星形光标，如图3所示。

可以通过按下右、左、上、下键来导航此光标。按下Fire键后，点将以粉红色星形显示在屏幕上，如图4所示。

在图4中，显示了起点。在指定终点后，将绘制如图1所示的直线。还将显示起点和终点的坐标。

关注点

通过这个程序，程序员可以看到几何坐标和屏幕坐标之间的区别。此外，它还能让读者初步了解如何为真实设备创建简单的图形内容。