Digital Differential Analyzer Algorithm

Posted: October 10, 2011 in Computer Graphics
Tags: , ,
This article is about a graphics algorithm. For the digital implementation of a Differential Analyzer, see Digital Differential Analyzer.

In computer graphics, a hardware or software implementation of a digital differential analyzer (DDA) is used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. In its simplest implementation the DDA algorithm interpolates values in interval [(xstart, ystart), (xend, yend)] by computing for each xi the equations xi = xi−1+1, yi = yi−1 + Δy/Δx, where Δx = xend − xstart and Δy = yend − ystart.

The DDA method can be implemented using floating-point or integer arithmetic. The native floating-point implementation requires one addition and one rounding operation per interpolated value (e.g. coordinate x, y, depth, color component etc.) and output result. This process is only efficient when an FPU with fast add and rounding operation is available.

The fixed-point integer operation requires two additions per output cycle, and in case of fractional part overflow, one additional increment and subtraction. The probability of fractional part overflows is proportional to the ratio m of the interpolated start/end values.

DDAs are well suited for hardware implementation and can be pipelined for maximized throughput.

where m represents the slope the line and c is the y intercept . this slope can be expressed in DDA as

      yend-ystart
  m= -----------
      xend-xstart

in fact any two consecutive point(x,y) laying on this line segment should satisfy the equation.


Implementation of DDA Algorithm

#include<iostream.h>

#include<conio.h>

#include<graphics.h>

void main()

{

clrscr();

int gdriver = DETECT,gmode;

initgraph(&gdriver,&gmode,”c:/tc/bgi”);

int xa,ya,xb,yb,dx,dy,step,k;

float xi,yi,x,y;

cout<<“\n enter the starting points of line “;

cin>>xa>>ya;

cout<<“\n enter the end points of line “;

cin>>xb>>yb;

dx=xb-xa;

dy=yb-ya;

if(dx>dy)

step=dx;

else

step=dy;

xi=dx/step;

yi=dy/step;

x=xa;

y=ya;

putpixel(x,y,15);

for(k=1;k<=step;k++)

{

x=x+xi;

y=y+yi;

putpixel(x,y,15);

}

getch();

}

References: wikipedia.org

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s