**Rasterization**

**Definition:**Discretization of a shape, line or polygon specified by continuum of vector coordinates into pixel coordinates used to render it.

**Line Rasterization: Bresenham Line Algorithm**

**Assumption:**The start and end point lie on integer pixel coordinate

**Problem:**Which pixels to render while drawing a line joining $(x_0,y_0)$ and $(x_1,y_1)$

**Step 1:**

Project the line into first octant such that $(x_0,y_0)$ is projected to origin and $(x_1,y_1)$ is mapped to $(x',y')$ such that

- $x' \geq 0$

- $y' \geq 0$

- $x' \geq y$

**Step 2:**

$P \rightarrow $ the start pixel

$M \rightarrow $ the first midpoint

$M_{E} \rightarrow $ the next midpoint given we choose to render E

$M_{NE} \rightarrow $ the next midpoint given we choose to render NE pixel

Define $f(x,y) = mx + b - y$ where $y = mx + b$ is the equation of the line projected in first octant.

$f(M) = f(P_x + 1, P_y + \frac{1}{2}) = f(P) + m - \frac{1}{2}$

$f(M_E) = f(M) + m$

$f(M_{NE}) = f(M) + m - 1$

Now, $m = \frac{\Delta y}{\Delta x} \geq 0$. So define

$F(M) = 2 \Delta x f(M)$

$F(M_E) = 2 \Delta x f(M_E) = F + 2 \Delta y $

$F(M_{NE}) = 2 \Delta x f(M_{NE}) = F + 2 \Delta y - 2 \Delta x$

$F(M_{init}) = 2 \Delta y - \Delta x$

**Final Algorithm:**

$y = y_0$

$F = 2 \Delta y - \Delta x$

for $x=x_0:x_1$

**Render $(x,y)$**

**if$(F \leq 0 )$ \* Take the East *\**

$F = F + 2 \Delta y$

else$(F > 0)$ \* Take the North East *\

$F = F + 2 \Delta y - 2 \Delta x$

end

**Polygon Rasterization**

First enforce consistent set of rules for when does a pixel belong to a polygon. The ambiguous case is when the edge passes through the pixel center. The other case is trivial.

The polygon will be rasterized one scanline at a time where the scanline progressively moves up.

Each edge is represented by coordinates $(x_{lower},y_{lower}),(x_{upper},y_{upper})$.

Maintain an

*Active Edge*data structure with the following three fields

- $x$ coordinate where a scan line intersects the edge

- $\frac{dx}{dy}$

- $y_{upper}$

The entries (basically edges and their properties) in this data structure are sorted in order of $x$ first and $\frac{dx}{dy}$ next.

**Algorithm:**

- Add edges with $y = y_{lower}$ along with their attributes in the Active Edge data structure

- For every pair $(2i-1,2i)$ render pixels in the range $\lceil x_i \rceil$ to $\lceil x_{i+1} \rceil - 1 $

- Remove edges with $y_{upper} = y$

- Update $x$ by $x = x + \frac{dx}{dy}$

**Gouraud Interpolation**

While rasterizing polygons, we need to interpolate vertex attributes such as colors to get the colors at the rendered pixels.

To do this:

- Maintain the attribute value along the edges of the polygon in the Active Edge data structure

- Whenever we move the scan line up, update the attribute by $val = val + \frac{val_{upper}-val_{lower}}{y_{upper}-y{lower}}$

- When scanning from left to right the pixels are assigned attributes by $val = val + \frac{val_{right}-val_{left}}{x_{right} - x_{left}}$