Scan Conversion of Line with the slope (0 < m < 1)
Currently the pixel positions beside the line path are determined through sampling at Unit x intervals that is, starting from the first point. (x_{0}, y_{0}) of a provided line we step to all successive columns. That is x-position and plots the pixel that scan line y value is closest to the line path. Suppose we proceed in such fashion up to the k^{th} step. The process is demonstrated in following figure. Suppose that we have determined the pixel at (x_{k}, y_{k}). We require deciding that pixel is to be plotted in column _{xk+ 1}. Our options are either (x_{k +1}, y_{k}) or (x_{k + 1}, y_{k + 1}).
Figure: Scan conversion 0 < m < 1
On sampling position X_{k + 1} the vertical pixel or say scan line separation from mathematical line i.e. y = mx + c is say d_{1} and d_{2}.
Currently, the y coordinate on the mathematical line on pixel column position X_{k + 1} is:
y = m (x_{k + 1}) + c ---------------------(1)
By using figure of Scan conversion 0 < m < 1:
d_{1} = y - y_{k} ---------------------(2)
= m (xk + 1) + c - yk ---------------------(3) (by using (1))
Likewise, d_{2} = (y_{k + 1}) - y = y_{k + 1} - m (x_{k + 1}) - c ---------------------(4)
By using (3) and (4) we get d_{1} - d_{2}
d_{1} - d_{2} = [m (x_{k + 1}) + c - y_{k}] - [y_{k + 1} - m (x_{k + 1}) - c]
= mx_{k} + m + c - y_{k} - y_{k} _{- 1} + mx_{k} + m + c
= 2m (x_{k + 1}) - 2y_{k} + 2c - 1 ---------------------(5)
As, decision parameter p for k^{th} step that is p_{k} is specified by
p_{k} = Δx(d_{1} - d_{2} )---------------------(6)
Currently, a decision parameter p_{k} for the k^{th} step in the line algorithm can be acquired by rearranging (5) hence it involves merely integer calculations. To achieve this substitute m = Δy/Δx; here, Δy and Δx ⇒ vertical and horizontal separations of the ending point positions.
p_{k} = Δx (d_{1} - d_{2}) = Δ x [2m (x_{k + 1}) - 2y_{k} + 2c - 1]
= Δx [2(Δy/Δx) (x_{k + 1}) - 2y_{k} + 2c - 1]
= 2 Δy (x_{k + 1}) - 2 Δxy_{k} + 2 Δxc - Δx
= 2 Δy x_{k} - 2 Δx y_{k} + [2 Δy + Δx (2c - 1)]
p_{k} = 2 Δy x_{k} - 2Δxy_{k} + b -------------------- (7)
Here b is constant with value b = 2Δy + Δx (2c - 1) ---------------------(8)
Note: sign of p_{k} is as similar as sign of d_{1} - d_{2} as it is assumed like Δx > 0; here in figure of Scan conversion 0 < m < 1 , d_{1} < d_{2} i.e. (d1 - d2) is -ve that is , p_{k} is negative so pixel T_{i} is more suitable option otherwise pixel S_{i} is the proper option.
That is (1) if p_{k} < 0 choose T_{i}, hence subsequent pixel option (x_{k}, y_{k}) is (x_{k + 1}, y_{k}) else (2) if p_{k} > 0 decide S_{i}, so subsequent pixel option after (x_{k} , y_{k} ) is (x_{k + 1}, y_{k + 1}).
At step k + 1 the decision parameter is evaluated via writing (7) as:
p_{k + 1} = 2Δy x_{k + 1} - 2Δx y_{k + 1} + b ---------------------(9)
Subtracting (7) from (9) we find:
Such recursive calculation of decision parameter is preformed at all integer positions, starting along with the left coordinate ending point of line.
This first parameter p_{0} is calculated by utilizing Eq(7), and (8) at the beginning pixel position (x_{0}, y_{0}) along with m evaluated as Δy /Δx (that is intercept c = 0)
p_{0} = 0 - 0 + b = 2Δy + Δx (2 * 0 - 1) = 2Δy - Δx
p_{0} = 2Δy - Δx -----------------------(10 A)