Talk:Digital differential analyzer (graphics algorithm)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.

Article with real content[edit]

For everybody who's wondering what happened to this article, that is, where is the "content", look at the history, particularly at the revision dated 12:22, 24 September 2010 [1], the last one with all the code samples. The comment for the change immediately after cites Wikipedia:NOT, but not the specific reason why all the code samples where removed. Anyway, for who, like me, doesn't care what these reasons are and just want some useful content, just look back in history. Daniele (talk) 00:13, 21 January 2012 (UTC)

Cleanup performed[edit]

Removed the cleanup tag because the article is IMO a lot clearer and of higher quality since August 2007 when the article was tagged. I also removed the context tag for the same reason. (talk) 19:44, 12 January 2008 (UTC)


I added a reference, simplified the floating-point code sample and added codelets for multi-component interpolation and integer operation. Please review and check for bugs & errors... -- (talk) 09:08, 8 July 2008 (UTC)

Er... I think the fixed point dda must be wrong. there should be no reason for the "overflow check".

here is my version (quick and dirty. draws in 45 deg. only, with dx > dy, all vars positive ints)

   // F is num of bits in fraction
   draw (x1, y1, x2, y2)
       dx = x2 - x1
       dy = y2 - y1
       x = x1
       y = y1 << F
       while x < x2
           plot x, y >> F
           x += 1
           y += m

Hard to beat two adds and a shift, or what? /Nurse Dragonbreath —Preceding unsigned comment added by (talk) 07:37, 6 September 2008 (UTC)

I am not perfectly sure, but if the condition (dx > dy) is satisfied, you could be right. Should the article sample code get replaced by this optimized version, it is simpler, but is it intuitive to understand? Any opinions? -- (talk) 20:11, 27 June 2009 (UTC)
One more note: the original code works for (dx < dy) and is thus more generic, which may be useful for some triangle renderers. However, your code seems to handle the overflow gracefully and fits well in a hardware implementation. -- (talk) 20:20, 27 June 2009 (UTC)

Bugs and code clarity[edit]

The code samples don't work for lines with no slope. For example the line (0,0) (0,10) will cause a divide by zero error. The section "Integer implementation with separated fractional part" code has the variables yi, yf, mi, mf and mtwo_xb_minus_xa with no explanation of what the values mean. More meaningful variable names would help.--SaintD1970 (talk) 19:54, 15 May 2009 (UTC)

Index "i" means "integer part", "f" means "fractional part" of the fixed-point number. "y" is the interpolated variable (as stated in the top section), "m" is the usual variable name for dy/dx of a straight ascending/descending line, which is undefined for dx = 0. Thus abs(dydx) has to be checked in advance, and variables need to be exchanged (for line rendering), or the segment can be discarded (for triangles, where the covered area is probably zero for dx=0).
"mtwo_xb_minus_xa" is just a short name for "-2 * (xb - xa)".
Division by zero won't occur if the condition "abs(dydx) > 1" is satisfied (cf. section "DDAs for triangle and line drawing and texture samplers"). But you are right, the article text should explain this. -- (talk) 20:04, 27 June 2009 (UTC)
EDIT: If the simplified version posted above would be included in the article, yi, yf, mi and mf would need no explanation since all bits are stored in the variables "y" and "m". -- (talk) 20:16, 27 June 2009 (UTC)
What happened with this? I don't see any code sample in the article. Anyway, the equation given in the intro still doesn't work for deltaX = 0 and for negative slopes and stuff like that. A more correct algorithm would be to simply divide deltaX and deltaY by the length of the line to get the increments for xi and yi respectively, but then you would need to do a sqrt operation to get the length of the line... -Domokato (talk) 23:51, 9 December 2011 (UTC)

Description and content are limited to lines[edit]

The description states "DDAs are used for rasterization of lines, triangles and polygons." which is pretty silly since it basically is quite the same as "DDAs are used for rasterization of lines": triangles and polygons are just multiple lines.

But DDAs are quite more versatile than that: you can use them for drawing circle segments, hyperbolas, polynomial curves, NURBS... — Preceding unsigned comment added by (talk) 17:22, 13 November 2012 (UTC)

Yes I was just looking for this too. I was looking for the term describing novalogic voxel space engine, which is similar. I had 'incremental error algorithm' in my head but wasn't sure. a similar approach can also do perspective correct texture mapping. Now I am unsure: do I augment this article for non-linear cases, or stick with my (maybe made up) term? Fmadd (talk) 14:34, 8 June 2016 (UTC)