Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 08:08, 8 July 2008

Revision as of 08:27, 8 July 2008

Line 10:

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.

==Naïve Floating-Point Implementation==

== The algorithm in code ==

The straightforward implementation of the 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>inspired by Watt 2000, p. 184.</ref>

{{citation}}

This is a sample implementation of the DDA algorithm in the [[C programming language]]:

<precode>

#include <math.h> /* for round() */

/* Draw a straight line between the points (xa, ya) and (xb, yb) */

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

/* Interpolate values between start (xa, ya) and end (xb, yb) */

void DDA (int xa, int ya, int dx=xb-xa;, // horizontalint differenceyb)

{

int dy=yb-ya; // vertical difference

float x = int steps, kxa;

float m = float(xb - xa) / (yb xIncrement,- yIncrementya);

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++) {

steps=abs output(dxround(x), y);

x = x + m;

}

}

</precode>

==Interpolating multiple values==

// calculate the number of steps used to draw the line (number of pixels)

Usually not only the coordinate component, but also additional values like depth, color, alpha, texture coordinates etc. are required for every point. For good performance on common architectures all values should get interpolated in the same inner loop:

if(abs(dx)>abs(dy))

steps=abs(dx);

else

steps=abs(dy);

<code>

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

#include <math.h> xIncrement=dx/* for round(float)steps; */

yIncrement=dy/(float)steps;

/* Interpolate y-coord and RGB color values between start (xa, ya, colora) and end (xb, yb, colorb) */

void DDA (int xa, int ya, int colora[3], int xb, int yb, int colorb [3])

{

float x = }xa;

float m = (xb - xa) / (yb - ya);

int y, color [3];

for (y=ya; y<=ys; y++) {

output(round(x), +=y, xIncrementcolor);

x = x + m;

color[0] += m; /* Red component */

color[1] += m; /* Green component */

color[2] += m; /* Blue component */

}

}

</code>

// point out the starting pixel

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

==Integer Implementation with seperated Fractional Part==

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

<code>

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

/* Draw a straight line between the points (xa, ya) and (xb, yb) */

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

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

{

x += xIncrement;

int dx=xb-xa; // horizontal y += yIncrement;difference

int dy=yb-ya; // vertical difference

int steps, k;

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

float setPixel(ROUND(x)xIncrement, ROUND(y))yIncrement;

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

}

}

// calculate the number of steps used to draw the line (number of pixels)

</pre>

if(abs(dx)>abs(dy))

steps=abs(dx);

else

steps=abs(dy);

// 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>

==See also==