Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 12:04, 22 March 2017

Latest revision as of 00:30, 24 July 2024

(42 intermediate revisions by 32 users not shown)

Line 1:

{{short description|Hardware or software used for interpolation of variables over an interval}}

{{About|a graphics algorithm|the digital implementation of a differential analyzer|Digital differential analyzer}}

In [[computer graphics]], a '''[[digital differential analyzer]]''' ('''DDA''') is hardware or software used for [[interpolation]] of [[Variable (computer science)|variables]] over an [[Interval (mathematics)|interval]] between start and end point. DDAs are used for [[rasterization]] of lines, triangles and polygons. They can be extended to non linear functions, such as [[texture mapping#Perspective correctness|perspective correct texture mapping]], [[quadratic curves]], and traversing [[voxels]].

In its simplest implementation for linear cases such as [[Line (geometry)|line]]s, the DDA algorithm interpolates values in interval by computing for each x_i the equations x_i = x_i−1 + 1/m, y_i = y_i−1 + m, where Δxm =is x_endthe −[[slope]] x_startof andthe line. Δy =This y_endslope −can y_startbe andexpressed min =DDA Δy/Δxas follows:

:<math>m = \frac{y_{\rm end} -y_{\rm start}}{x_{\rm end}-x_{\rm start}}</math>

== Performance ==

where ''m'' represents the slope of the line and ''c'' is the y intercept. In fact any two consecutive point(x,y)points lying on this line segment should satisfy the equation.

== Performance ==

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 [[Floating-point unit|FPU]] with fast add and rounding operation will be available.

Line 12 ⟶ 16:

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

This slope can be expressed in DDA

as

:<math>m = \frac{y_{end} -y_{start}}{x_{end}-x_{start}}</math>

where ''m'' represents the slope of the line and ''c'' is the y intercept. In fact any two consecutive point(x,y) lying on this line segment should satisfy the equation.

== Algorithm ==

Line 32 ⟶ 31:

: <math>y_{k+1} = y_k + 1</math>

Similar calculations are carried out to determine pixel positions along a line with negative slope. Thus, if the absolute value of the slope is less than 1, we set dx=1 if <math> x_{\rm start}<x_{\rm end}</math> i.e. the starting extreme point is at the left.

== Program ==

DDA algorithm program in [[C++]]:

<syntaxhighlight lang="cpp" line="1">

#include <graphics.h>

#include <iostream.h>

#include <math.h>

#include <dos.h>

#include <conio.h>

void main()

{

float x,

float y,

float x1, y1,

float x2, y2, dx, dy, step;

int i, gd = DETECT, gm;

initgraph(&gd, &gm, "C:\\TURBOC3\\BGI");

cout << "Enter the value of x1 and y1: ";

cin >> x1 >> y1;

cout << "Enter the value of x2 and y2: ";

cin >> x2 >> y2;

dx = (x2 - x1);

dy = (y2 - y1);

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

step = abs(dx);

else

step = abs(dy);

dx = dx / step;

dy = dy / step;

x = x1;

y = y1;

i = 0;

while (i <= step) {

putpixel(round(x), round(y), 5);

x = x + dx;

y = y + dy;

i = i + 1;

delay(100);

}

getch();

closegraph();

}

</syntaxhighlight>

== See also ==

* [[Bresenham's line algorithm]] is an algorithm for line rendering.

* [[incrementalIncremental error algorithm]]

* [[Xiaolin Wu's line algorithm]] is an algorithm for line anti-aliasing

Line 46 ⟶ 96:

{{no footnotes|date=June 2011}}

<references/>

* Alan Watt: ''3D Computer Graphics'', 3rd edition 2000, p.&nbsp;184 (Rasterizing edges). {{ISBN |0-201-39855-9}}

[[Category:Computer graphics algorithms]]

[[Category:Digital geometry]]

[[Category:Articles with example C++ code]]