Unit 2: Scan conversion and area filling

• Scan conversion (rasterisation): converting a geometric object defined by continuous coordinates into a set of discrete pixels that best approximate it.
• Problems: aliasing (staircase or jagged edges), unequal brightness of lines at different slopes, and speed; anti-aliasing smooths edges by varying pixel intensities.

• DDA: simpler than the direct method, but uses floating-point addition and rounding, so errors accumulate.

• Uses only integer addition and subtraction; at each step chooses between two candidate pixels using a decision parameter.

• Derivation outline: at x = xk + 1 the true y is m(xk + 1) + c. Distances to the two candidates are d1 = y − yk and d2 = (yk + 1) − y. pk = Δx (d1 − d2) = 2Δy·xk − 2Δx·yk + constant has the same sign as d1 − d2, so its sign picks the nearer pixel; subtracting pk from pk+1 gives the update rules above.

• Eight-way symmetry: compute one octant and plot (±x, ±y) and (±y, ±x), so only 1/8 of the circle is calculated.

• Derivation idea: f(x, y) = x² + y² − r² is negative inside the circle, zero on it and positive outside. Evaluate f at the midpoint (xk + 1, yk − ½) between the two candidate pixels; its sign tells which pixel is closer.

• Bresenham's circle: d0 = 3 − 2r; if d < 0 then d = d + 4x + 6, else d = d + 4(x − y) + 10 and y decreases.

• Midpoint (Bresenham) ellipse algorithm: uses four-way symmetry and divides the first quadrant into two regions — region 1 where the slope magnitude is less than 1 (step in x) and region 2 where it is greater than 1 (step in y).

cvoid floodFill(int x, int y, int oldColor, int newColor) {
    if (getpixel(x, y) == oldColor) {
        putpixel(x, y, newColor);
        floodFill(x + 1, y, oldColor, newColor);   /* 4-connected */
        floodFill(x - 1, y, oldColor, newColor);
        floodFill(x, y + 1, oldColor, newColor);
        floodFill(x, y - 1, oldColor, newColor);
    }
}

• 4-connected fill checks four neighbours; 8-connected also checks diagonals. Recursion can overflow the stack for large areas, so scan-line seed fill with an explicit stack is used in practice.