JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech III COMPUTER GRAPHICS Previous Question Paper (March - 2021 - R16)

Bresenham's line algorithm is an efficient scan-conversion algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is highly preferred in computer graphics because it uses only integer addition, subtraction, and bit shifting, avoiding expensive floating-point arithmetic.

• Initialization: Given endpoints (x1, y1) and (x2, y2), calculate Δx = |x2 - x1| and Δy = |y2 - y1|.
• Decision Parameter: The algorithm calculates a decision parameter p to determine which pixel is closer to the true line path. For the first step, the initial decision parameter is defined as:
  p₀ = 2Δy - Δx
• Iterative Step: For each x position along the line, starting at k=0:
  • If pₖ < 0, the next pixel is (xₖ + 1, yₖ) and
    pₖ₊₁ = pₖ + 2Δy
  • If pₖ ≥ 0, the next pixel is (xₖ + 1, yₖ + 1) and
    pₖ₊₁ = pₖ + 2Δy - 2Δx

To find the pixels for the line segment from (5, 8) to (2, 4), we first swap the points to ensure we move from left to right: (x1, y1) = (2, 4) and (x2, y2) = (5, 8).

• Δx = 5 - 2 = 3
• Δy = 8 - 4 = 4
• 2Δy = 8, 2Δx = 6
• 2Δy - 2Δx = 2
• Initial decision parameter p₀ = 2Δy - Δx = 8 - 3 = 5

Since Δy > Δx, we iterate based on y:

The pixel coordinates are: (2, 4), (3, 5), (3, 6), (4, 7), (5, 8).