what is meant by symmetric DDA?

Question

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

Answer 1

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.