1

I was studying a book explaining DDA algorithm and got stuck at a point .According to the rule the points should be rounded up so here in this case It should be (4,6) at the place of (4,5) isn't it .Check the picture below I've encircled the points I feel incorrect in the book ,so Am I taking it wrong or the book got a misprint here ? enter image description here

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
user1938918
  • 65
  • 2
  • 3
  • 7
  • Everyone thinks of the DDA in terms of slopes, think of it as "how many x dots per single yi" instead. Say y <= x, how many dots on the x axis do you need for a single yi, answer: x / y. Remember that x and y are distances after all. – user1095108 Jun 09 '13 at 10:47
  • Also see [Simplified Bresenham's line algorithm: What does it *exactly* do?](http://stackoverflow.com/a/8113883/837847) – James Waldby - jwpat7 Jun 09 '13 at 14:02

1 Answers1

2

In order to draw a continuous line on a discreet plan (x,y), x, y integer, that algorithm, based on the slope of the line, makes either x or y the "carrier" (always incremented by one) and the other coordinate is interpolated. Reason are:

  • the drawing should be as close as possible to the line equation
  • there should be no "hole" in the drawn line
  • there is no need to calculate more values than necessary (eg, having x "carrier", x+0.1, x+0.2 etc...)

The document seems to be this PDF, where you can see that the continuous line, is not always in the center of the pixels it crosses. Thanks to that algorithm, a dot will have an immediate neighbor, either at x+1 or y+1 depending on the slope (the interpolated coordinate could be twice (or more) in a row the same rounded value. Eg if y is interpolated, you could have (10,20), (11, 20), (12, 21) having twice y=20).

Considering only the quarter [0, 90] degrees, the line start from coordinates (0,0). If the line slope is below 45 degrees, it is better to have x as "carrier" (incremented by 1), and y interpolated. Example

      +++
   +++
+++

here x is always incremented by one, but y takes sometimes the same value as for the previous x (eg, for x=0, x=1, x=2 we have the same y)

Back to rounding

In the same document, it is said page 47

in order to plot a pixel on the screen, we need to round off the coordinates to a nearest integer

which is usually the case when doing an interpolation. It is better to take the nearest integer. That means, usually,

  • take integer part + 1 if first decimal is >= .5 (eg. 4.71 => 5)
  • take only integer part if 1st decimal is < .5 (eg 5.42 => 5)

so that:

  • the integer pixel coordinates are closer to the equation value with decimals
  • the sum of the rounded value (eg for x) is more likely to be close to the sum of the calculated value from the equation.

In this particular case, (4, 38/7) ~= (4, 5.43), 5.43 is rounded to the nearest integer, ie 5 and not 6.

Déjà vu
  • 28,223
  • 6
  • 72
  • 100