I have spend whole day understanding the logic behind digital differential analyser algo(for drawing line).Please make me understand this algo.

Printable View

- 01-06-2006vaibhavDDA algo logic
I have spend whole day understanding the logic behind digital differential analyser algo(for drawing line).Please make me understand this algo.

- 01-06-2006Salem
What are you expecting us to say that inumerable web pages haven't said already?

- 01-06-2006iMalc
The whole point is to get rid of the need to perform slow calculations such as using multiply or divide, and replace them with fixed sized steps, which we can simply add on every step and will obviously be much faster. However, this isn't quite enough. With this alone, the line will usually drift away from the exact line should be.

So what we also do is work out how often we'll need to adjust the line to compensate. We'll only ever need to compensate by 1 pixel, because we wont let ourselves get any furthur out than that thanks to our initial calculations. As we go along, when we've acculumated enough error for our line to otherwise drift away from the true line, then we add 1 to bring it right again.

For example, lets say our line needs to go down by 100 pixels, and across by 228 pixels.

As you can see, our constant step size will be 2 pixels, and stepping by that amount each time will head in the correct general direction. Then for every 100 pixels we need to add another 28.

So each step we add 2 to the line, and also add 28 to another variable (err). If err reaches 100, then we adjust the line by adding 1, and subtract 100 from err.

Over the course of traversing the line, we will have added 28*100 = 2800 to err. It will have gone across an extra pixel for each 100 we added, so over the length of the line it will have added an extra 28 pixels. Our fixed size step gave us 2*100 pixels, so we stepped a total of 228 pixels, exactly as desired, in a smooth manner, and no divide per step.