Consider the midpoint (Bresenham) algorithm for rasterizing lines: (1) Input (x₁, y₁) and (x₂, y₂) (2) y = y₁ (3) d = f(x₁ + 1, y₁ + 1/2) // f is the implicit form of the line (4) for x = x₁ to x₂ (5) do (6) plot(x, y) (7) if (d < 0) (8) then (9) y = y + 1 (10) d = d + (y₁ − y₂) + (x₂ − x₁) (11) else (12) d = d + (y₁ − y₂) (13) end (14) end Which statements are true? P: For a line with slope m > 1, the outer loop in line (4) should be over y. Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f. R: The algorithm fails if d is ever 0.

1. AP only
2. BP and Q only
3. CQ and R only
4. DP , Q and R

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: B. P and Q only

Explanation

For steep lines the roles of x and y are swapped (P true). The updates add the change in f for a step in x or in x and y (Q true). d = 0 falls into the else branch, so nothing fails (R false).