5

I have read about DDA. But I just came across the term symmetric DDA. What is it ? How is it different from DDA ?

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
Y.E.P
  • 1,187
  • 6
  • 20
  • 40
  • where did you run into the term 'symmetric DDA'? – Colin D Aug 17 '12 at 17:47
  • @Colin D I heard two people talking about the term. – Y.E.P Aug 17 '12 at 17:51
  • you should stop and ask them next time you run into them! – Colin D Aug 17 '12 at 17:52
  • 2
    @Colin D sure,if I see them one more time.I heard them talking in the train. _Instead of posting these chatty comments ,why don't you try answering it._ – Y.E.P Aug 17 '12 at 17:53
  • I'm sure it's in my copy of Principles Of Interactive Computer Graphics by Newman & Sproull, but I can't remember where the book is, so google will have to help: http://books.google.co.uk/books?id=fGX8yC-4vXUC&pg=PA38&lpg=PA38&dq=symmetric+DDA&source=bl&ots=wa9HS0Nh_v&sig=xO8F-8n0UTK0Gw-an7AodlhrTis&sa=X&ei=MIQuUNCBM-GQ0AWyp4H4DA&ved=0CBoQ6AEwAQ#v=onepage&q=symmetric%20DDA&f=false – Andrew Morton Aug 17 '12 at 17:56
  • Here another link: http://books.google.de/books?id=3BPZXYlInKwC&pg=PT120&lpg=PT120&dq=symmetric+dda&source=bl&ots=FKIyIsfDrB&sig=IQDGj1uLMiMpMW375QjQUFiQnBs&hl=de&sa=X&ei=c48uUIecJNTa4QSSloGIBg&ved=0CEEQ6AEwAA#v=onepage&q=symmetric%20dda&f=false – phimuemue Aug 17 '12 at 18:38
  • 1
    @Y.E.P Or you could, you know, google it. Typing "symmetric DDA" into Google returned thousands of results. – user1118321 Aug 17 '12 at 18:47
  • @user1118321 really ? did you try it ? got there from something ? – Y.E.P Aug 18 '12 at 05:06
  • 1
    @Y.E.P Yes. In fact, the very PDF quoted below in Ujjwal Singh's answer was the 2nd or 3rd hit. – user1118321 Aug 18 '12 at 14:15

1 Answers1

5

The DDA (Digital Differential Analyzer) algorithm is used to find out interpolating points between any given two points, linearly (i.e. straight line). Now since this is to be done on a digital computer - speed is an important factor.

The equation of a straight line is given by m=Δx/Δy eq(i), where Δx = x(2)-x(1) & Δy = y(2)-y(1),
now using this equation we could compute successive points that lie on the line. But then this is the discrete world of raster graphics - so we require integral coordinates.

In simple DDA eq(i) is transformed to m=eΔx/eΔy where e, call it the increment factor, is a positive real number. since putting the same number in numerator and denominator does not change anything - but if suitably chosen - it can help us in generating discrete points thereby reducing the overload of having to round off the resultant points.

Basically what we need to do is: increment the coordinates by a fixed small amount, beginning from the starting point, and each time we have a new point progressing towards the end point.

In simple DDA - e is chosen as 1/max(|Δx|,|Δy|) such that one of the coordinate is integral and only the other coordinate has to be rounded. i.e. P(i+1) = P(i)+(1,Round(e*Δy)) here one coordinate is being incremented by 1 and the other by e*Δy

In symmetric DDA - e is chosen such that though both the co-ordinates of the resultant points has to be rounded off, it can be done so very efficiently, thus quickly.

Specifically e is chosen as 1/2^n where 2^(n-1) <= max(|Δx|,|Δy|) < 2^n. In other words the length of the line is taken to be 2^n aligned. The increments for the two coordinates are e*Δx and e*Δy. With suitably chosen initial fraction part of the beginning coordinates: this causes the points to be generated as mixed fractions whose fractional parts are in a cyclic series, i.e. they repeat over a small length. The resultant coordinates can thus easily be rounded off based on two fixed length look-up tables, one for each coordinate.

refer http://w3.msi.vxu.se/~gsu/DAB726-Ht06/Symm-DDA.pdf for an example.
Notice the cyclic repetition in the fractional part of the resultant coordinates.

Ujjwal Singh
  • 4,908
  • 4
  • 37
  • 54