Talk:Digital differential analyzer (graphics algorithm)

Cleanup performed

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. 82.181.93.246 (talk) 19:44, 12 January 2008 (UTC)[reply]

update

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... -- 89.247.29.115 (talk) 09:08, 8 July 2008 (UTC)[reply]

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
       m = (dy << F) / dx // this integer division can also be looked up in a table
   
       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 85.19.218.76 (talk) 07:37, 6 September 2008 (UTC)[reply]

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? -- 89.247.82.229 (talk) 20:11, 27 June 2009 (UTC)[reply]

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. -- 89.247.82.229 (talk) 20:20, 27 June 2009 (UTC)[reply]

Bugs and code clarity

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)[reply]

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 dx/dy of a straight ascending/descending line, which is undefined for dy = 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 dy=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. -- 89.247.82.229 (talk) 20:04, 27 June 2009 (UTC)[reply]

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". -- 89.247.82.229 (talk) 20:16, 27 June 2009 (UTC)[reply]