Digital differential analyzer (graphics algorithm): Difference between revisions

Revision as of 07:59, 8 July 2008

Revision as of 08:08, 8 July 2008

Line 4:

In [[Computer graphics]], '''Digital Differential Analyzer (DDA)''' is an algorithm used to determine which points need to be plotted in order to draw a straight line between two given points. It employs the equation for line representation (example: y=mx+c), then scan through an axis. Each scan it would determine the value on the other axis using the equation, this way the proper pixel can be located.

== Overview Performance==

The DDA method can be implemented using [[floating-point]] or [[integer]] arithmetic. The naïve floating-point implementation requires one addition and one round operation per interpolated value (e.g. coordinate x, y, depth, color component etc.) and output result. This process is only efficient when a [[FPU]] with fast add and round operation is available.

The DDA method is not very efficient due to the need for division and rounding. [[Bresenham's line algorithm]] is a more efficient method to draw lines because it uses only addition, subtraction and bit shifting.

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.

== The algorithm in code ==