Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 08:33, 8 July 2008

Revision as of 08:46, 8 July 2008

Line 5:

==Algorithm (Naïve Floating-Point Implementation)==

The straightforward DDA algorithm requires a fast floating-point add and round() operation for good performance. Here an example in the [[C programming language]] interpolating a single value <code>x</code> between start and end point:<ref>Code is inspired by Watt 2000, p. 184.</ref>

<code>

Line 50:

==Integer Implementation with seperated Fractional Part==

By splitting the integer and fractional part of all floating-point numbers, the algorithm can get converted to fixed-point arithmetics, so that it achieves good performance on architectures without floating-point support. Now the inner-loop rounding is replaced by a fractional-part overflow handler:

<code>

/* DrawInterpolate a straight linevalues between the pointsstart (xa, ya) and end (xb, yb) */

void line DDA (int xa, int ya, int xb, int yb)

{

int xi = int dx=xb-xa; // horizontal difference

int xf = -(yb int- dy=yb-ya); // vertical difference

int mi = (xb int- xa) / (yb steps,- kya);

int mi = 2 float* xIncrement,((xb yIncrement- xa) % (yb - ya));

int }y;

float x=xa, y=ya; // the drawing points x and y are initiated to one endpoint of the line

for for(ky=0ya; ky<steps=ys; ky++) {

// calculate the number of steps used to draw the line output(number ofx, pixelsy);

if(abs(dx)>abs(dy)) xi = xi + mi;

stepsxf =abs(dx) xf + mf;

else if (xf > 0) {

steps=abs(dy); xf -= 2 * (yb - ya);

xi++;

// calculate the increment for x and y in each step}

xIncrement=dx/(float)steps ;}

yIncrement=dy/(float)steps;

// point out the starting pixel

setPixel(ROUND(x), ROUND(y));

// loop through the line from one end to the other and point out the pixels

for(k=0; k<steps; k++) {

// the points are incremented an equal amount for every step

x += xIncrement;

y += yIncrement;

// since the values for x and y are float they are rounded before they are plotted

setPixel(ROUND(x), ROUND(y));

}

}

</code>

==DDAs for line drawing==

The above implementations interpolate only x values and iterate y values. This is a perfect approach when rasterizlng triangles with horizontal lines (two DDAs interpolate x coordinate, colors etc. for the left and right edge, a third DDA interpolates colors etc on the horizontal line inbetween). But when rasterizing lines, then gaps will occur, when abs(mx) < 1. So a line drawing algorithm using DDAs has to check whether abs(mx) < 1, and interpolate y instead of x if required (since my < 1 if mx > 1).

==Performance==