Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 00:11, 17 February 2017

Latest revision as of 00:30, 24 July 2024

(45 intermediate revisions by 35 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.

The [[Fixed-point arithmetic|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 bal chero bokachodathroughput.

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 rightleft.

== 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]]