Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 08:24, 8 January 2019

Latest revision as of 00:30, 24 July 2024

(19 intermediate revisions by 16 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, 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 =as Δy/Δxfollows:

:<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_{\rm end} -y_{\rm start}}{x_{\rm end}-x_{\rm 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 35 ⟶ 34:

== Program ==

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

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

#include <graphics.h>

#include <iostream.h>

#include <math.h>

Line 45 ⟶ 43:

#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: ";

Line 58 ⟶ 59:

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 = 10;

while(i <= step) {

while putpixel(x,i y,<= 5step); {

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

x = x + dx;

y = y + dy;

Line 74 ⟶ 78:

delay(100);

}

getch();

closegraph();

Line 82 ⟶ 87:

* [[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 95 ⟶ 100:

[[Category:Computer graphics algorithms]]

[[Category:Digital geometry]]

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